문제 해결의 예. ZLP를 해결하기 위한 그래픽 방법. 단순 방법을 사용하여 선형 프로그래밍 문제 해결 그래픽 선형 프로그래밍 해결의 예

30.11.2023

선형 프로그래밍(LP)의 가장 간단하고 시각적인 방법은 그래픽 방법입니다. 두 개의 변수가 있는 LP 문제를 해결하는 데 사용됩니다. 표준 형식의 LP 문제를 고려하십시오.

최대 f(x 1 , x 2 , ..., x n) = ,

, 나는 = 1, 2, …, m,

xj 0, j = 1, 2, …, n.

넣어보자 n=2비행기에서 문제를 고려해보겠습니다. 불평등 시스템을 일관되게 유지하세요(적어도 하나의 솔루션이 있어야 함).

이 시스템의 각 부등식은 경계선 a i 1 x 1 + a i 2 x 2 = bi i, i = 1, 2, …, 중. 음이 아닌 조건은 각각 경계 직선 x 1 = 0, x 2 = 0으로 반평면을 정의합니다. 시스템은 일관성이 있으므로 교차하는 볼록 세트와 같은 반평면은 공통 부분을 형성합니다. 이는 볼록 세트이자 점의 모음이며 각 점의 좌표는 이 시스템에 대한 솔루션입니다. 이러한 점 집합을 솔루션 다각형이라고 합니다. 점, 세그먼트, 광선, 경계가 있는 다각형 또는 경계가 없는 다각형이 될 수 있습니다.

따라서 기하학적으로 ZLP는 좌표가 목표의 선형 함수에 최대(최소) 값을 제공하는 솔루션 다각형의 지점을 검색하는 것이며 솔루션 다각형의 모든 지점은 허용되는 솔루션입니다.

선형 방정식은 동일한 선 위에 있는 일련의 점을 설명합니다. 선형 부등식은 평면의 일부 영역을 설명합니다. 평면의 어느 부분이 부등식 2x 1 + 3x 2 12로 설명되는지 결정해 보겠습니다.

먼저 직선 2x 1 + 3x2= 12. 점 (6; 0)과 (0; 4)를 통과합니다. 어떤 반평면이 부등식을 만족하는지 결정하려면 그래프에서 선에 속하지 않는 점을 선택하고 그 좌표를 부등식으로 대체해야 합니다. 부등식이 성립하면 주어진 점이 실현 가능한 해이고 해당 점을 포함하는 반평면이 부등식을 충족합니다. 부등식에 대입하려면 원점을 이용하면 편리합니다. x 1 = x 2 = 0을 부등식 2x 1 + 3x 2 12에 대입합니다. 우리는 2x0 + 3x0 12를 얻습니다. 이 진술은 사실이므로 부등식 2x 1 + 3x 2 12는 점을 포함하는 아래쪽 절반 평면에 해당합니다. (0; 0). 이는 그림 1의 그래프에 반영되어 있습니다. 1.1.

마찬가지로 LP 문제의 모든 제약 조건을 그래픽으로 표현할 수 있습니다.

ZLP 제약 조건 시스템의 각 부등식에 대한 해는 경계선을 포함하고 경계선의 한 쪽에 위치하는 반평면입니다. 각각이 시스템의 해당 부등식에 의해 결정되는 반평면의 교차점을 허용 가능한 해 영역 또는 정의 영역이라고 합니다. 실현 가능한 해의 영역은 비음성 조건을 충족한다는 점을 기억해야 합니다( xj 0, j = 1, 2, ..., N). 정의 영역에 속하는 모든 점의 좌표는 문제에 대한 유효한 솔루션입니다.

LP 문제를 그래픽으로 풀 때 목적 함수의 극값을 찾기 위해 기울기 벡터가 사용되며 그 좌표는 목적 함수의 부분 파생물입니다.

이 벡터는 목적 함수의 가장 빠른 변화 방향을 보여줍니다. 1 x 1 + 2 x 2 =의 직통 라인 에프(x0)기울기 벡터에 수직인 는 목적 함수의 수준선입니다. 수준선의 어느 지점에서나 목적 함수는 동일한 값을 갖습니다. 목표 함수를 상수 값과 동일시하자 "ㅏ". "a"의 값을 변경하면 평행선군을 얻을 수 있으며, 각 평행선은 목적 함수의 수준선입니다.

선형 함수의 수준선의 중요한 특성은 선이 한 방향으로 평행하게 이동하면 수준이 증가하고, 다른 방향으로 이동하면 감소한다는 것입니다.

기하학적 관점에서 볼 때, 선형 계획법 문제에서 우리는 허용 가능한 해 세트에서 가장 높은(최저) 레벨 선에 도달하고 더 멀리(가까이) 위치한 코너 점 또는 점 집합을 찾고 있습니다. 다른 것들은 가장 빠른 성장 방향으로 향하고 있습니다.

ZLP를 해결하기 위한 그래픽 방법은 다음 단계로 구성됩니다.

1. PLP의 허용 가능한 솔루션(ADS)의 다각형 영역이 구성됩니다.

2. 목적 함수(TF)의 기울기 벡터는 ODR에 속하는 x 0 지점에서 구성됩니다.

3. 레벨 라인 c 1 x 1 + c 2 x 2 = a(a는 상수 값) - 그래디언트 벡터에 수직인 직선 - f(x 1, x 2) ODR을 떠날 때까지. 이 이동 중 영역의 한계점(또는 지점)은 최대점 f(x 1, x 2)입니다.

4. 최대점의 좌표를 찾으려면 해당 제한에서 얻은 두 개의 직선 방정식을 풀고 교차점에 최대점을 제공하면 충분합니다. 결과 지점에서 찾은 값 f(x 1, x 2)가 최대값입니다.

함수 f(x 1, x 2)를 최소화(최대화)하면 레벨 선이 그래디언트 벡터의 반대 방향으로 이동합니다. 레벨 라인에 해당하는 직선이 이동 중에 ODR을 벗어나지 않으면 함수 f(x 1, x 2)의 최소값(최대값)이 존재하지 않습니다.

레벨 라인이 문제의 기능적 제약 조건과 평행한 경우 CF의 최적 값은 두 개의 최적 꼭지점 사이에 있는 이 제약 조건의 임의 지점에서 달성되며 따라서 이러한 점 중 하나는 다음의 최적 솔루션입니다. ZLP. LP 문제를 그래픽적으로 해결하기 위한 가능한 상황이 표에 나와 있습니다. 1.3.

표 1.3

№	ODR 유형	최적의 솔루션 유형	노트
	닫힌 다각형	유일한 결정
	유일한 결정

	다각형	CF는 아래로부터 제한되지 않습니다
	CF는 위에서 제한되지 않습니다
	다각형 개방	유일한 결정
	끝없는 솔루션
	선분	유일한 결정

다음 예제를 사용하여 선형 계획법 문제의 그래픽 솔루션을 고려해 보겠습니다.

예제 1.1. 봉제 기업의 생산 계획 (양복에 관한 문제).

남성복과 여성복 2종의 슈트를 출시할 예정이다. 여성복 한 벌에는 양모 1m, 라브산 2m, 하루 1인의 노동이 필요합니다. 남성복의 경우 양모 3.5m, 라브산 0.5m, 1인/일 노동. 전체적으로 350m의 양모, 240m의 lavsan 및 150인/일의 노동력이 있습니다. 여성복 판매 수익이 10 화폐 단위이고 남성 정장 판매 수익이 20 화폐 단위인 경우 최대 이익을 보장하기 위해 각 유형의 정장 수를 만들어야 하는지 결정해야 합니다. 적어도 60 벌의 남성복을 재봉해야한다는 점을 명심해야합니다.

다음 표기법을 소개하겠습니다. x 1 - 여성복 수; x 2 – 남성용 정장 수. 여성복 판매 수익은 10x1이고 남성복 판매 수익은 20x2입니다. 목적 함수를 최대화하는 것이 필요합니다.

10x1 + 20x2

작업 제약 조건의 형식은 다음과 같습니다.

x 1 + x 2 150,

2x1 + 0.5x2240,

x 1 + 3.5x 2 350,

x 2 60,

x 1 0.

첫 번째 노동 제한은 x 1 + x 2 150입니다. 직선 x 1 + x 2 = 150은 점 (150; 0)과 (0; 150)을 통과합니다(그림 1.2).

lavsan의 두 번째 제약 조건은 2 x 1 + 0.5x 2 240입니다. 직선 2 x 1 + 0.5x 2 = 240은 점 (120; 0)과 (0; 480)을 통과합니다. 양모에 대한 세 번째 제한 x 1 + 3.5x 2 350. 남성 정장 수에 대한 네 번째 제한 x 2를 추가하겠습니다. 60. 이 부등식에 대한 해는 직선 x 2 = 60 위에 있는 반평면입니다. 1.3 실현 가능한 해의 영역은 음영 처리되어 있습니다. 최적을 향한 이동 방향을 결정하기 위해 좌표가 목적 함수의 부분 도함수인 기울기 벡터를 구성합니다.

이러한 벡터를 구성하려면 점(10;20)을 원점에 연결해야 합니다. 목적함수를 최대화할 때는 그래디언트 벡터 방향으로 이동해야 하고, 최소화할 때는 반대 방향으로 이동해야 합니다. 편의상 벡터에 비례하는 벡터를 구성할 수 있습니다. 그래서, 그림에서. 1.4는 기울기 벡터(30;60)를 보여줍니다.

최적을 향한 이동 방향을 결정하기 위해 좌표가 목적 함수의 부분 파생인 기울기 벡터를 구성합니다.

우리의 경우에는 가능한 솔루션 영역을 벗어날 때까지 레벨 라인을 이동합니다. 극한의 모서리 지점에서는 목적 함수의 최대값이 달성됩니다. 이 점의 좌표를 찾으려면 해당 제한에서 얻은 두 개의 직선 방정식을 풀고 교차점에 최대 점을 제공하는 것으로 충분합니다.

x 1 + 3.5x 2 = 350,

x 1 + x 2 = 150.

여기에서 원본 ZLP에 대한 솔루션을 쉽게 기록할 수 있습니다. 최대 f(x)= 2300이고 x 1 = 70 및 x 2 = 80에서 달성됩니다(그림 1.4 참조).

1.3.Excel 환경에서 Solution Search Add-On을 사용하여 선형 프로그래밍 문제를 해결하는 기술

1.3.1. Excel 스프레드시트 프로세서 작업에 대한 일반 정보

최적화 문제를 해결하는 데 필요한 계산을 단순화하는 Excel 스프레드시트 프로세서 작업의 몇 가지 측면을 고려해 보겠습니다. 테이블 프로세서는 테이블 형식 데이터 처리를 자동화하도록 설계된 소프트웨어 제품입니다.

엑셀 화면 요소. Excel을 실행하면 화면에 표가 나타나며 그 모양은 그림 1.5에 나와 있습니다.

이 이미지를 워크시트라고 합니다. 행과 열의 그리드이며, 그 교차점은 셀이라고 불리는 직사각형을 형성합니다. 워크시트는 데이터 입력, 계산 수행, 정보 기반 구성 등을 위해 설계되었습니다. Excel 창에는 제목 표시줄, 메뉴 표시줄, 상태 표시줄, 창 제어 버튼 등 주요 프로그램 요소가 표시됩니다.

수식 작업.스프레드시트 프로그램은 수식을 사용하여 다양한 계산을 수행합니다. Excel을 사용하면 수식을 빠르게 만들 수 있습니다. 공식은 세 가지 주요 부분으로 구성됩니다.

1) 등호;

2) 계산이 수행되는 셀의 값 또는 참조 세트

3) 운영자.

4) 등호가 없으면 Excel은 데이터를 수식이 아닌 셀에 입력된 데이터로 해석합니다. 수식은 셀이나 수식 입력줄에 직접 입력할 수 있습니다(텍스트 또는 숫자). 이 경우 다음 단계를 수행해야 합니다.

· 수식을 포함해야 하는 셀을 선택하고 기호(=)를 입력합니다.

· 연산자 또는 동작 기호를 입력합니다.

· 수식에 포함된 다른 셀을 선택합니다.

· Enter 키를 누릅니다.

입력한 수식이 수식 입력줄에 나타나고, 계산 결과가 셀에 나타납니다.

수식에 함수를 사용합니다. 수식을 더 쉽게 입력하려면 Excel 기능을 사용할 수 있습니다. 함수는 Excel에 내장된 수식입니다. Excel에는 많은 수식이 포함되어 있습니다. 논리, 수학, 공학, 통계 등 다양한 유형으로 그룹화됩니다.

특정 수식을 활성화하려면 삽입, 함수 버튼을 클릭하세요. 왼쪽에 나타나는 함수 마법사 창에는 함수 유형 목록이 포함되어 있습니다. 유형을 선택하면 오른쪽에 기능 자체의 목록이 표시됩니다. 해당 이름을 클릭하면 기능이 선택됩니다.

다양한 함수는 특정 규칙에 따라 다양한 유형의 계산을 수행합니다. 함수가 워크시트 셀의 단일 개체인 경우 함수는 (=) 기호로 시작하고 그 뒤에 함수 이름, 괄호로 묶인 함수에 대한 인수가 옵니다.

솔루션 찾기는 최적화 문제를 해결할 수 있는 Excel 추가 기능입니다. 도구 메뉴에서 솔루션 검색 명령을 사용할 수 없는 경우 이 추가 기능을 다운로드해야 합니다. 도구 => 추가 기능 명령을 선택하고 솔루션 추가 기능 검색을 활성화하십시오. 이 추가 기능이 추가 기능 대화 상자에 없으면 Windows 제어판으로 이동하여 프로그램 추가/제거 아이콘을 클릭하고 Excel(또는 Office) 설치 프로그램을 사용하여 솔루션 찾기 추가를 설치해야 합니다. -안에.

도구 => 솔루션 검색 명령을 선택하면 솔루션 검색 대화 상자가 나타납니다.

솔루션 찾기 대화 상자에는 세 가지 주요 옵션이 있습니다.

대상 셀을 설정합니다.

셀 변경.

제한.

먼저 대상 셀 설정 필드를 작성해야 합니다. 솔루션 찾기 도구의 모든 작업에서 워크시트 셀 중 하나의 결과가 최적화됩니다. 대상 셀은 수식을 사용하여 해당 워크시트의 다른 셀과 관련됩니다. 솔루션 찾기 도구는 대상 셀에서 결과를 생성하는 수식을 사용하여 가능한 솔루션을 테스트합니다. 대상 셀의 가장 작은 값이나 가장 큰 값을 찾도록 선택하거나 특정 값을 설정할 수 있습니다.

솔루션 찾기 도구의 두 번째 중요한 옵션은 셀 변경 옵션입니다. 여기서는 대상 셀의 결과를 최적화하기 위해 값이 변경될 셀을 지정합니다. 솔루션을 찾기 위해 최대 200개의 변경 가능한 셀을 지정할 수 있습니다. 이 셀에는 두 가지 주요 요구 사항이 있습니다. 수식이 포함되어서는 안 되며, 해당 값의 변경 사항이 대상 셀의 결과 변경 사항에 반영되어야 합니다. 즉, 대상 셀은 수정되는 셀에 따라 달라집니다.

솔루션 검색 탭에 입력해야 하는 세 번째 매개변수는 제한사항입니다.

문제를 해결하려면 다음이 필요합니다.

1) 결정 결과가 포함될 셀의 주소를 나타냅니다(변경 가능한 셀).

2) 초기 데이터를 입력합니다.

3) 목적 함수에 대한 의존성을 도입합니다.

4) 제한사항에 대한 종속성을 도입합니다.

5) 솔루션 검색 명령을 실행합니다.

6) 셀을 대상 기능에 할당합니다(대상 셀 설정).

7) 제한사항을 도입합니다.

8) LLP를 풀기 위한 매개변수를 입력합니다.

예제 1.1(슈트 문제)의 조건을 이용한 해결 기술을 생각해 보자.

문제의 경제적, 수학적 모델

x 1을 여성용 정장의 수라고 하자. x 2 - 남성복 수,

10 x x 1 + 최대 20 x x 2

작업 제약 조건의 형식은 다음과 같습니다.

x 1 + x 2 150 - 노동 제한;

2××1 + 0.5× 엑스 2,240 - lavsan 제한;

x 1 + 3.5 x x 2 350 - 양모 한계;

x 2 60 - 남성 정장 제한;

x 1 0 - 여성복에 대한 제한.

1. 풀이 결과가 들어갈 셀(변경 가능한 셀)의 주소를 지정합니다.

x 1 , x 2 각 유형의 슈트 수를 나타냅니다. 우리 문제에서 벡터 = (x 1, x 2)의 최적 값은 목적 함수의 최적 값인 셀 S3에 있는 셀 A2:B2에 배치됩니다.

2. 초기 데이터를 입력합니다.

그림과 같이 초기 작업 데이터를 입력합니다. 1.6.

3. 목적 함수에 대한 종속성을 도입합니다.

· “NW” 셀에 커서를 놓으면 해당 셀이 선택됩니다.

· 도구 모음에 있는 기능 마법사 버튼에 커서를 놓습니다.

· 엔터를 입력하세요. 함수 마법사 2단계 중 1단계 대화 상자가 화면에 나타납니다.

· Functions 창에서 SUMPRODUCT 라인을 선택합니다(그림 1.7). 화면에

· SUMPRODUCT 대화 상자가 나타납니다(그림 1.8).

· Array 1 라인에 입력 A2:B2.

· 어레이 2 라인에 AZ:VZ를 입력합니다.

제약 조건에 대한 종속성을 입력할 때 배열 1이 사용되므로 이 배열에 대한 절대 참조를 만들어야 합니다. 그림에서. 그림 1.9에서는 셀 SZ에 함수가 도입되었음을 보여줍니다.

5. 제약조건에 대한 종속성을 입력합니다(그림 1.10).

· 커서를 NW 셀에 놓습니다.

· 도구 모음에는 클립보드로 복사 버튼이 있습니다.

· 셀 C4에 커서를 놓습니다.

· C5 셀에 커서를 놓습니다.

· 도구 모음의 클립보드에서 붙여넣기 버튼.

· Sat 셀에 커서를 놓습니다.

· 도구 모음의 클립보드에서 붙여넣기 버튼.

· 셀 C7에 커서를 놓습니다.

· 도구 모음에서 클립보드에서 붙여넣기 버튼을 클릭합니다. (C4-C7 셀의 내용을 확인해야 합니다. 그림 1.11의 예와 같이 정보를 포함해야 합니다. 셀 C5의 내용은 예로 표시됩니다.)

· 메뉴 라인에서 서비스에 마우스 포인터를 놓습니다. 확장된 메뉴에서 솔루션 검색 명령을 선택합니다. 솔루션 검색 대화 상자가 나타납니다(그림 1.12).

5. 솔루션 검색 명령을 실행합니다.

6. 대상 기능에 셀을 할당하고(대상 셀 설정) 변경할 셀의 주소를 표시합니다.

· 대상 셀 설정 라인에 커서를 놓습니다.

· $С$3 셀의 주소를 입력하세요.

· 문제의 조건에 따라 목적함수 유형을 입력합니다. 이렇게 하려면 목적 함수가 최대값 또는 최소값과 같은지 확인하세요.

· 셀을 변경하여 커서를 행에 배치합니다.

· 필요한 변수 A$2:B$2의 주소를 입력합니다(그림 1.13).

7. 제한사항을 도입하세요.

· 추가 버튼 위에 마우스 포인터를 놓습니다. 제약 조건 추가 대화 상자가 나타납니다.

· 제한 표시를 입력하세요.

· 제한 라인에 주소 $D$4를 입력합니다(그림 1.14).

· 추가 버튼 위에 마우스 포인터를 놓습니다. 제한 추가 대화 상자가 다시 나타납니다.

· 위에서 설명한 알고리즘을 사용하여 문제의 나머지 제약 조건을 입력합니다.

· 마지막 제한 사항을 입력한 후 확인 버튼을 클릭합니다. 입력된 조건이 포함된 솔루션 검색 대화 상자가 화면에 나타납니다(그림 1.15).

8. 선형 프로그래밍 문제를 해결하기 위한 매개변수를 입력합니다.

· 대화 상자에서 옵션 버튼에 마우스 포인터를 놓습니다. 솔루션 검색 옵션 대화 상자가 화면에 나타납니다(그림 1.16).

· 선형 모델(이렇게 하면 단순 방법을 사용할 수 있음) 및 음수가 아닌 값의 상자를 선택합니다.

· 확인 버튼 위에 마우스 포인터를 놓습니다. 솔루션 검색 대화 상자가 화면에 나타납니다.

· 실행 버튼에 마우스 포인터를 놓습니다.

잠시 후, 솔루션 검색 결과 대화 상자와 x i 값에 대한 AZ:VZ 셀과 목적 함수의 최대값이 있는 셀 SZ가 채워진 초기 테이블이 나타납니다(그림 1.17).

보고서 유형 안정성을 지정하면 최적의 솔루션에 대한 추가 정보를 얻을 수 있습니다(그림 1.18).

문제를 해결한 결과 70개를 재봉해야 한다는 답변을 받았습니다. 여성복 및 80개. 남성복은 최대 2300달러의 이익을 얻습니다.

1.4. 선형 프로그래밍 문제의 이중성. 획득된 최적의 솔루션 분석

1975년에 우리 동포 L.V. Kantorovich는 자원의 최적 사용 이론을 개발한 공로로 미국 경제학자 T. Koopmans와 함께 노벨 경제학상을 수상했습니다(부록 1 참조).

모든 선형 계획법 문제와 밀접하게 관련된 문제는 쌍대 문제라고 불리는 또 다른 선형 문제입니다. 원래 문제를 원본 또는 직접이라고 합니다. 원래 문제와 이중 문제 사이의 연결은 특히 그 중 하나의 솔루션이 다른 문제의 솔루션에서 직접 얻을 수 있다는 사실에 있습니다.

이중 문제 y i의 변수는 객관적으로 결정된 추정치, 이중 추정치, 자원의 "가격" 또는 그림자 가격이라고 합니다.

쌍쌍 문제 각각은 실제로 독립적인 선형 계획법 문제이며 서로 독립적으로 풀 수 있습니다.

원본 문제와 관련된 이중 문제는 다음 규칙에 따라 구성됩니다.

1) 원래 문제의 목적 함수는 최대로 공식화되고 쌍대 문제의 목적 함수는 최소로 공식화되는 반면, 최대 문제에서는 함수 제약 조건의 모든 불평등이 최소 문제에서 () 형식을 갖습니다. 그들은 형태를 가지고 있습니다 ( );

2) 원래 문제의 시스템에서 알려지지 않은 제약 조건에 대한 계수로 구성된 행렬 A와 이중 문제의 유사한 행렬 A T를 서로 전치하여 얻습니다.

3) 이중 문제의 변수 수는 원래 문제의 기능적 제약 조건 수와 같고, 이중 문제 시스템의 제한 수는 원래 문제의 변수 수와 같습니다.

4) 쌍대 문제의 목적 함수에서 미지수에 대한 계수는 원래 문제의 제약 조건 시스템의 자유 항이고, 쌍대 문제의 제한 사항에서 우변은 다음의 미지수에 대한 계수입니다. 원본의 목적 함수; j 0.

제시된 두 가지 문제는 한 쌍의 대칭 쌍대 문제를 형성합니다. 상호 쌍대 문제에 대한 주요 설명은 다음 두 가지 정리에 포함되어 있습니다.

첫 번째 이중성 정리. 상호 이중 문제의 경우 상호 배타적인 사례 중 하나가 발생합니다.

1. 직접 문제와 이중 문제에는 최적의 솔루션이 있습니다.
동시에 최적의 솔루션에 대한 목적 함수의 값
성냥

2. 직접 문제에서 허용 가능한 집합은 비어 있지 않으며 이 집합의 목적 함수는 위에서 제한되지 않습니다. 이 경우 이중 문제에는 허용 가능한 빈 세트가 있습니다.

3. 쌍대 문제에서 허용되는 세트는 비어 있지 않으며 이 세트의 목적 함수는 아래로부터 제한되지 않습니다. 이 경우 허용 가능한 직접 문제 세트는 비어 있는 것으로 나타납니다.

4. 고려 중인 두 문제 모두 허용 가능한 세트가 비어 있습니다.

두 번째 이중성 정리(상보적 비강성 정리). 하자 = ( 1개, 2개,..., x n)은 직접 문제에 대해 허용되는 해이고, a = (y 1,y 2,...,y t)는 쌍대 문제에 대해 허용되는 해입니다. 직접적 문제와 이중적 문제 각각에 대한 최적의 솔루션이 되기 위해서는 다음 관계가 충족되는 것이 필요하고 충분합니다.

조건 (1.4)와 (1.5)를 사용하면 상호 이중 문제 중 하나의 최적 솔루션을 알면 다른 문제의 최적 솔루션을 찾을 수 있습니다.

또 다른 정리를 고려해 보겠습니다. 그 결론은 더 자세히 사용될 것입니다.

추정 정리. 쌍대 문제의 최적해에서 변수 y i의 값은 직접 문제의 제약 조건(부등식) 시스템의 자유 항 b i가 값에 미치는 영향에 대한 추정치를 나타냅니다.

심플렉스 방법을 사용하여 ZLP를 해결함으로써 듀얼 ZLP를 동시에 해결합니다. 쌍대 문제 y i 의 변수를 객관적으로 결정된 추정치라고 합니다.

카펫 문제를 예로 들어 이중 문제의 경제적 해석을 고려해 보겠습니다.

실시예 1 .2. 카펫 문제에 대한 설명을 사용하여 다음 작업을 완료하세요.

1. 표의 데이터를 사용하여 최대 총 생산 비용에 대한 카펫 문제의 경제-수학적 모델을 공식화하십시오. 1.1.

2. 솔루션 찾기를 통해 총 생산 비용이 최대가 되는 생산 계획을 찾습니다.

3. 카펫 문제에 대한 이중 문제의 경제-수학적 모델을 공식화합니다.

4. 쌍대성 정리를 사용하여 쌍대 문제에 대한 최적의 계획을 찾고 X 1과 X 4의 0이 같음을 설명합니다.

5. 솔루션 검색 프로토콜을 사용하여 원래 문제에 대한 최적의 솔루션 결과를 분석합니다.

6. 파이프 사용 수명이 12개 증가할 때 총 비용과 생산 계획이 어떻게 변경되는지 결정합니다.

1. 문제의 경제적, 수학적 모델을 공식화합시다.

각 유형의 카펫 수를 X 1, X 2, X 3, X 4로 표시하겠습니다. 목적 함수는 다음과 같은 형식을 갖습니다.

F(X) = ZX 1 + 4X 2 + ZX 3 + 최대 X 4,

및 자원 제한

7Х 1 + 2Х 2 + 2Х 3 + 6X4 80,

5Х 1 + 8Х 2 + 4 엑스 3 + ZH 4 480,

2X1 + 4 X 2 + X 3 + 8X 4 130,

엑스 1, 엑스 2, 엑스 3, 엑스 4 0.

2. 최적의 출시 계획을 검색합니다.

Excel 추가 기능인 솔루션 검색을 사용하여 문제를 해결해 보겠습니다. 문제를 해결하기 위한 기술은 의상 문제에서 자세히 다루었습니다. 우리 문제에서 벡터 X = (X 1, X 2, X 3, X 4)의 최적 값은 목적 함수의 최적 값인 VZ:EZ 셀에 배치됩니다. F4.

초기 데이터를 입력해 보겠습니다. 먼저 SUMPRODUCT(그림 1.19) 기능을 사용하여 대상 기능을 설명합니다. 그런 다음 제한 사항의 왼쪽 부분에 대한 데이터를 입력합니다. 해 찾기에서는 목적 함수의 방향, 찾고 있는 변수의 주소를 입력하고 제한 사항을 추가합니다. 입력된 조건이 포함된 솔루션 검색 대화 상자가 화면에 나타납니다(그림 1.20).

문제 해결을 위한 매개변수를 입력한 후 실행 버튼을 클릭합니다. 해결책을 찾았다는 메시지가 화면에 나타납니다(그림 1.21).

결과 솔루션은 최대 소득이 150,000 루블임을 의미합니다. 공장은 생산 시 두 번째 유형의 카펫 30개와 세 번째 유형의 카펫 10개를 받을 수 있습니다. 이 경우 자원 “노동”과 “장비”가 모두 사용되며, 480kg의 실(자원 “원자재”) 중 280kg이 사용됩니다.

솔루션 검색 결과를 기반으로 보고서를 작성합니다. Excel을 사용하면 솔루션 검색 결과를 보고서 형식으로 표시할 수 있습니다(표 1.4). 이러한 보고서에는 세 가지 유형이 있습니다.

· 결과(답변). 보고서에는 대상 셀과 수정된 셀의 초기 및 최종 값과 제한 사항에 대한 추가 정보가 포함됩니다.

· 안정성(감도). 수정되는 셀이나 제약 조건 공식의 작은 변화에 대한 솔루션의 민감도에 대한 정보가 포함된 보고서입니다.

· 한계. 보고서에는 영향을 받는 셀과 대상 셀의 소스 및 대상 값 외에도 제약 조건이 충족되는 경우 영향을 미치는 셀이 허용할 수 있는 값의 상한 및 하한이 포함됩니다.

먼저 LLP에 정확히 두 개의 변수가 포함되는 가장 간단한 경우를 고려해 보겠습니다.

문제(3.8)의 제약 조건 시스템의 각 부등식(a)-(b)는 각각 경계선 X 1 =0 및 X 2 =0을 사용하여 반평면을 기하학적으로 정의합니다. 각 경계선은 평면 x 1 Ox 2를 두 개의 반 평면으로 나눕니다. 원래 부등식에 대한 모든 해는 형성된 반평면(반평면의 모든 점) 중 하나에 있으므로 해당 점의 좌표를 해당 부등식으로 대체하면 이를 진정한 항등식으로 바꿉니다. 이를 고려하여 불평등에 대한 해가 결정되는 반평면은 다음과 같습니다. 반평면에서 임의의 점을 선택하고 해당 좌표를 해당 부등식으로 대체합니다. 주어진 점에 대해 부등식이 성립하면 동일한 반평면의 다른 점에도 적용됩니다. 그렇지 않으면 부등식에 대한 해법은 또 다른 반면에 있습니다.

부등식 (a)-(b) 시스템이 일관성이 있는 경우 해당 해의 영역은 표시된 모든 반평면에 속하는 점 집합입니다. 이러한 반면의 교차점 집합은 볼록하므로 문제(3.8)에 대해 허용되는 해의 영역은 해 다각형이라고 하는 볼록 집합입니다(이전에 소개된 용어 "해 다면체"는 일반적으로 n이 3인 경우 사용됩니다). ). 이 다각형의 측면은 직선 위에 놓여 있으며, 그 방정식은 부등 기호를 정확한 등호 기호로 대체하여 원래 제약 조건 시스템에서 얻은 것입니다.

따라서 초기 ZLP는 목적 함수 F가 최대(최소) 값을 취하는 결정 다각형의 지점을 찾는 것으로 구성됩니다.

이 점은 해 다각형이 비어 있지 않고 그 목적 함수가 위에서 제한되어 있을 때 존재합니다. 지정된 조건에서 해 다각형의 정점 중 하나에서 목적 함수는 최대값을 취합니다. 이 꼭지점을 결정하려면 기울기 벡터에 수직이고 솔루션 다각형을 통과하는 레벨 라인 L: c 1 x 1 +c 2 x 2 =h(여기서 h는 상수)를 구성하고 기울기 벡터를 따라 평행하게 이동합니다. 솔루션 다각형과의 마지막 공통 교차점을 통과할 때까지(그라디언트 벡터를 구성할 때 점(c 1 ; c 2)이 x 1 Ox 2 평면에 배치되고 방향이 있는 세그먼트가 이 평면에 그려집니다. 좌표의 원점). 지정된 지점의 좌표에 따라 이 작업에 대한 최적의 계획이 결정됩니다.

위의 모든 내용을 요약하여 ZLP를 해결하는 그래픽 방법에 대한 알고리즘을 제시합니다.

ZLP를 해결하는 그래픽 방법 알고리즘

1. 원본 ZLP의 제한 시스템에 의해 지정된 솔루션의 다각형을 구성합니다.

2. 구성된 해의 다각형이 빈 세트인 경우 원래 ZLP에는 해가 없습니다. 그렇지 않으면, 기울기 벡터를 구성하고 최대 문제를 풀 때 벡터 방향(또는 최소 문제의 경우 반대 방향)으로 이동하여 해 다각형의 극점을 결정하는 임의의 레벨 라인 L을 그립니다. 문제의 목적 함수의 최대(최소)가 달성되는 곳입니다.

3. 교차하는 두 경계선의 방정식 시스템을 풀어 찾은 최적 지점의 좌표를 계산합니다.

4. 찾은 최적해를 문제의 목적 함수에 대입하여 최적값을 계산합니다. 즉: .

PLP(솔루션 다각형)의 허용 가능한 솔루션 세트를 그래픽으로 구성할 때 다음 상황이 가능합니다.

운영 연구에서 수학적 모델링은 한편으로는 매우 중요하고 복잡한 과정이지만, 다른 한편으로는 과학적으로 공식화하는 것이 사실상 불가능한 과정입니다. 수학적 모델을 만들기 위한 일반 원칙을 식별하려는 반복적인 시도로 인해 매우 일반적인 성격의 권장 사항이 선언되어 특정 문제를 해결하는 데 적용하기 어렵거나 반대로 실제로 특정 문제에만 적용할 수 있는 방법이 출현하게 되었습니다. 문제의 범위가 좁습니다. 따라서 구체적인 예를 활용하여 수학적 모델링 기법을 익히는 것이 더 유용할 것 같습니다.

선형 프로그래밍 문제는 다음 방법을 사용하여 해결할 수 있습니다.

플로이드 알고리즘;

그래프에 대한 Dijkstra의 알고리즘;

그래픽 방식;

심플렉스 테이블 방식 등

그래프에서 Dijkstra의 방법을 사용하여 선형 프로그래밍 문제를 해결하는 알고리즘입니다.

가장 간단한 구현에서는 숫자 배열을 사용하여 숫자 d[i]를 저장할 수 있고 부울 변수 배열을 사용하여 집합 U에 있는 요소의 구성원을 저장할 수 있습니다.

알고리즘 시작 시 초기 정점의 거리는 0으로 설정되고 다른 모든 거리는 큰 양수(그래프에서 가능한 최대 경로보다 큰)로 채워집니다. 플래그 배열은 0으로 채워집니다. 그런 다음 메인 루프가 시작됩니다.

사이클의 각 단계에서 최소 거리와 플래그가 0인 꼭지점 U를 찾아야 합니다. 그런 다음 플래그를 1로 설정하고 인접한 모든 정점 U를 확인해야 합니다. 거리가 현재 정점까지의 거리와 가장자리 길이의 합보다 크면 거리를 줄여야 합니다. 모든 정점의 플래그가 1이 되거나 모든 정점의 플래그가 0이 되면 사이클이 종료됩니다. 후자의 경우는 그래프 G가 연결되지 않은 경우에만 가능합니다.

그래픽 방법을 사용하여 선형 프로그래밍 문제를 해결하는 방법입니다.

선형 계획법 문제를 해결하기 위한 그래픽 방법은 선형 계획법 문제의 기하학적 해석을 기반으로 하며 주로 2차원 공간의 문제를 풀 때 사용되며 3차원 공간의 일부 문제에만 사용됩니다. 반쪽 공간이 교차하여 형성된 용액 다면체. 일반적으로 3차원보다 큰 공간의 문제를 그래픽으로 표현하는 것은 불가능합니다.

선형 계획법 문제를 2차원 공간에서 지정합니다. 즉, 제약 조건에는 두 개의 변수가 포함됩니다.

함수의 최소값은 식 (1)에 의해 결정됩니다.

(1)

제한 사항은 공식 (2)와 (3)으로 표시됩니다.

(2)

(3)

조건 (3)의 시스템 (2)가 일관성을 유지하도록 합니다. 시스템 (2)와 (3)의 각 부등식은 식 (4)로 표시되는 경계선이 있는 반평면을 정의합니다.

Z의 고정 값에 대한 선형 함수(1)는 직선의 방정식입니다.

제약 조건 시스템(2)에 대한 해의 다각형과 Z=0에서의 선형 함수 그래프(1)를 구성하는 것이 필요합니다. 그러면 제기된 선형 계획법 문제는 다음과 같이 해석될 수 있습니다.

선이 있는 해 다각형의 점을 찾으십시오.
기준 및 기능 Z는 최소값에 도달합니다.

가치
벡터 방향으로 감소
따라서 직선 Z=0은 벡터 N의 방향으로 자신과 평행하게 이동해야 합니다.

솔루션 다각형에 경계가 있는 경우 직선은 솔루션 다각형(점 B 및 E)에 대해 두 번 기준선이 되며 점 E에서 최소값을 갖습니다. 점의 좌표
는 직선 DE와 EF의 연립방정식을 풀어서 구해야 합니다.

솔루션 다각형이 경계가 없는 다각형 영역인 경우 두 가지 경우가 가능합니다.

사례 1. 직접
, 벡터 N 방향 또는 그 반대 방향으로 이동하면 솔루션 다각형과 지속적으로 교차하며 어떤 지점에서도 이를 지원하지 않습니다. 이 경우 선형 함수는 위나 아래에서 솔루션 다각형에 제한되지 않습니다.

사례 2. 이동하는 동안 직선은 솔루션 다각형에 대한 지지대가 됩니다. 그런 다음 도메인 유형에 따라 선형 함수는 위에서 유계이고 아래에서 유계가 없으며, 아래에서 유계가 있고 위에서 유계가 없으며, 아래와 위 모두에서 유계일 수 있습니다.

이 문제를 해결하기 위해 선형 계획법 문제를 해결하기 위해 실제로 가장 잘 알려지고 널리 사용되는 심플렉스 방법이 선택되었습니다. 단순법은 응용 선형 계획법 문제를 해결하는 데 좋은 결과를 보여준 상당히 효과적인 알고리즘이라는 사실에도 불구하고 지수적으로 복잡하다는 알고리즘입니다.

선형 계획법 문제의 단순 방법은 목적 함수의 값이 증가하거나 감소하는 한 참조 계획에서 다른 참조 계획으로의 전환을 기반으로 합니다.

단순 테이블을 컴파일하기 전에 문제를 변환해야 하며 제약 조건 시스템을 허용 가능한 기본 형식으로 가져와 그림 1과 같이 목적 함수에서 기본 변수를 제외해야 합니다.

그림 1 - 제약 시스템의 초기 변환

여기서 표기법의 명확성을 위해 변수 X1, X2, ..., Xr을 기본 변수로 취할 수 있고 b1, b2,..., br ≥ 0이라고 가정합니다(해당 기본 해는 참조 하나).

문제 설명의 모든 등식에서 단순 테이블을 컴파일하기 위해 변수를 포함하는 용어는 왼쪽으로 이동되고 자유 항목은 오른쪽에 남습니다. 문제는 그림 2와 같이 평등 시스템의 형태로 작성됩니다.

그림 2 – 불평등 시스템의 변형

다음 테이블로 이동하는 알고리즘은 다음과 같습니다.

테이블의 마지막 행(인덱스)을 살펴보고 이 행의 계수(자유항 제외) 중에서 최대값을 찾을 때는 가장 작은 음수가 선택되고, 최소값을 찾을 때는 가장 큰 양수가 선택됩니다. 없는 경우 원래의 기본 솔루션이 최적이며 이 테이블이 마지막입니다.

마지막 행에서 선택한 음수(양수) 계수에 해당하는 테이블 열을 살펴봅니다. 즉, 키 열과 양수 계수가 이 열에서 선택됩니다. 아무것도 없으면 목적 함수는 허용되는 변수 값 범위에서 무제한이며 문제에는 해결책이 없습니다.

열의 선택된 계수 중에서 이 요소에 대한 해당 자유항(자유항 열에 위치)의 비율의 절대값이 최소인 것이 선택됩니다. 이 계수를 분해 계수라고 하며 이 계수가 위치한 선이 핵심입니다.

앞으로는 해결 요소의 행에 해당하는 기본 변수를 자유 범주로 이동하고 해결 요소의 열에 해당하는 자유 변수를 기본 변수 개수에 입력해야 합니다. 기본 변수의 새 이름을 포함하는 새 테이블이 작성됩니다.

키 라인의 각 요소(자유항 열 제외)를 해결 요소로 나누고 결과 값을 새로운 심플렉스 테이블의 기본 변수가 변경된 라인에 써보겠습니다.

허용 요소의 문자열은 이 요소로 나누어지고 결과 문자열은 같은 위치의 새 테이블에 기록됩니다.

새 테이블에서 항상 1인 절단 열을 제외하고 키 열의 모든 요소는 0입니다.

키 행에 0이 있는 열은 새 테이블에서도 동일합니다.

키 열에 0이 있는 행은 새 테이블에서도 동일합니다.

그림 3과 같이 이전 테이블의 요소를 변환한 결과가 새 테이블의 나머지 셀에 기록됩니다.

그림 3 – 심플렉스 테이블의 새 요소 컴파일

결과적으로 새로운 기본 솔루션에 해당하는 새로운 심플렉스 테이블이 얻어집니다.

이제 목적함수(지수)의 행을 살펴봐야 합니다. 음수 값(최대값 찾기 문제에서) 또는 양수 값(최소값 찾기 문제에서)이 포함되어 있지 않은 경우 다음을 제외합니다. 가만히 서 있는 것(자유 컬럼)에 대해서는 최적의 솔루션이 수신되었음을 의미합니다. 그렇지 않으면 위에서 설명한 알고리즘을 사용하여 새로운 단순 테이블로 이동합니다.

본 교과목의 문제를 해결하기 위해 기업 내 최적의 자금배분을 위한 문제의 방향을 선택하였다. 선형 계획법 문제에 대한 최적 계획 또는 최적 솔루션은 목표 값이 증가(감소)하는 계획입니다.

수집된 정보를 분석한 후 부품이 페인팅되는 페인팅 컨베이어에서 NefAZ OJSC의 8번 워크샵에 대한 선형 프로그래밍 문제가 작성되었습니다. 이익을 극대화하려면 1교대 근무 시 최적의 부품 수를 도장하는 것이 필요합니다.

문제를 더욱 해결하려면 문제에 대한 설명과 문제의 수학적 모델을 만드는 것이 필요합니다.

Nikolai Kuznetsov는 소규모 기계 공장을 운영하고 있습니다. 다음 달에 그는 두 가지 제품(A와 B)을 생산할 계획이며, 구체적인 한계 이익은 각각 2,500루블과 3,500루블로 추정됩니다.

두 제품을 생산하려면 가공, 원자재 및 노동 비용이 필요합니다. 제품 A 1개당 가공 시간은 3시간, 원자재 16단위, 노동 6단위가 필요합니다. 제품 B에 해당하는 단위 요구 사항은 10, 4, 6입니다. Nicholas는 다음 달에 가공 시간 330시간, 원자재 400단위, 노동 240단위를 공급할 수 있을 것으로 예상합니다. 생산 공정의 기술은 특정 달에 최소 12개 제품 B 단위를 생산해야 하는 것과 같습니다.

리소스 이름	ㅏ	비	자원의 양
가공시간	3	10	330
원자재 단위	16	4	400
노동 단위	6	6	240

Nikolai는 공헌 이익을 최대화하기 위해 다음 달에 생산해야 하는 제품 A와 B의 단위 수를 결정하는 모델을 구축하려고 합니다.

문제의 해결

1단계: 변수 정의

최적화, 즉 최대화 또는 최소화(예: 이익, 수익 또는 비용)해야 하는 목표 변수(Z라고 부르겠습니다)가 있습니다. Nikolay는 공헌 마진을 최대화하려고 하므로 목표 변수는 다음과 같습니다.

Z는 제품 A와 B의 생산 결과로 다음 달에 받는 총 한계 이익(루블 단위)입니다.

목적 함수의 최적 값을 얻기 위해 값을 결정해야 하는 알려지지 않은 알려지지 않은 변수(x 1, x 2, x 3 등으로 표시)가 많이 있습니다. 우리의 경우에는 총 한계 이익. 이 기여 마진은 생산된 제품 A와 B의 수량에 따라 달라집니다. 이러한 수량의 값을 계산해야 하므로 모델에서 원하는 변수를 나타냅니다. 따라서 다음을 표시해 보겠습니다.

x 1은 다음 달에 생산되는 제품 A의 단위 수입니다.

x 2는 다음 달에 생산되는 제품 B의 단위 수입니다.

모든 변수를 명확하게 정의하는 것이 매우 중요합니다. 측정 단위와 변수가 참조하는 기간에 특별한 주의를 기울이십시오.

단계. 2. 목적함수의 구축

목적 함수는 최대화되거나 최소화되어야 하는 선형 방정식입니다. 목표변수를 이용하여 표현된 목표변수, 즉 x1, x2,...로 표현된 Z를 선형방정식의 형태로 담고 있다.

이 예에서 제조된 각 제품 A는 2,500루블을 가져옵니다. 한계 이윤, 제품 A를 1개 생산할 때 한계 이윤은 2500×1이 됩니다. 마찬가지로, 제품 B를 x 2단위 생산할 때 발생하는 한계 이익은 3500 x 2입니다. 따라서 다음 달에 제품 A x 1개와 제품 B x 2개를 생산하여 받는 총 한계 이익, 즉 목표 변수 Z는 다음과 같습니다. Z = 2500x 1 +3500x 2.

Nikolay는 이 지표를 극대화하기 위해 노력합니다. 따라서 우리 모델의 목적 함수는 다음과 같습니다.

단계. 3. 제약 조건 정의

제약 조건은 원하는 변수의 값을 제한하는 선형 방정식 및/또는 부등식 시스템입니다. 이는 자원의 가용성, 기술적 요인, 마케팅 조건 및 기타 요구 사항을 수학적으로 반영합니다. 제약 조건에는 "작거나 같음", "크거나 같음", "완전히 같음"의 세 가지 유형이 있습니다.

이 예에서 제품 A와 B를 생산하려면 가공 시간, 원자재, 노동력이 필요하며 이러한 자원의 가용성은 제한되어 있습니다. 따라서 이 두 제품의 생산량(즉, x 1과 x 2의 값)은 생산 프로세스에 필요한 자원의 양이 사용 가능한 자원의 양을 초과할 수 없다는 사실로 인해 제한됩니다. 기계 처리 시간에 따른 상황을 생각해 봅시다. 제품 A의 각 단위를 생산하려면 3시간의 기계 가공이 필요하며, x 1개 단위가 생산되면 이 자원의 3x 1시간이 소비됩니다.

제품 B의 각 단위를 생산하는 데 10시간이 필요하므로 x 2개의 제품이 생산되면 10 x 2시간이 필요합니다. 따라서 제품 A 1개와 제품 B 2개를 생산하는 데 필요한 총 기계 시간은 3x 1 + 10x 2입니다. 이 총 기계 시간은 330시간을 초과할 수 없습니다. 수학적으로 이는 다음과 같이 작성됩니다.

3x1 +10x2 ≤330

원자재와 노동력에도 유사한 고려 사항이 적용되므로 두 가지 제한 사항을 더 기록할 수 있습니다.

16x1 +4x2 ≤400

6x1 +6x2 ≤240

마지막으로, 최소 12개 단위의 제품 B를 생산해야 한다는 조건이 있다는 점에 유의해야 합니다.

단계. 4. 부정문이 아닌 조건 작성

필수 변수는 음수가 될 수 없으며 부등식 x 1 ≥0 및 x 2 ≥0 형식으로 작성해야 합니다. 이 예에서는 x 2가 12보다 작을 수 없다고 위에서 결정되었으므로 두 번째 조건은 중복됩니다.

\[\왼쪽\( (\시작(배열)()
(3(x_1) + 10(x_2) \le 330)\\
(16(x_1) + 4(x_2) \le 400)\\
(6(x_1) + 6(x_2) \le 240)\\
((x_1)\ge 0)\\
((x_2)\ge 12)
\end(배열)) \right.\]

심플렉스법을 이용한 해법

심플렉스 방법은 정규 형식으로 제시된 거의 모든 문제를 해결할 수 있으므로 선형 계획법 문제를 해결하기 위한 보편적인 방법입니다.

심플렉스 방법의 아이디어는 특정 기준 솔루션에서 시작하여 시스템의 기준 솔루션을 따라 최적의 기준 솔루션까지 순차적으로 이동하는 것입니다. 지원 솔루션의 수는 유한하므로 유한한 수의 단계를 거쳐 최적의 솔루션을 찾습니다.

단순 방법 알고리즘은 다음과 같이 설명할 수 있습니다.

문제를 정식 형식으로 가져오기
제약 조건 시스템에 대한 음이 아닌 기본 해 찾기
다음 공식을 사용하여 자유 변수의 추정치를 계산합니다.

\[(\Delta)_j = \sum\limits_(i = 1)^r ((c_i)(h_(ij)) – (c_j)) ,\;j = \overline (1,n) ,\]

여기서 h ij는 자유 변수 x j의 계수이고,

c i – 목적 함수의 기본 변수에 대한 계수,

c j – 목적 함수의 자유 변수 계수,

최적성을 위해 찾은 지원 솔루션을 확인하십시오.

a) 모든 추정값이 $(\Delta)_j \ge 0$이면 찾은 솔루션이 최적이고 문제가 해결됩니다.

b) 적어도 하나의 추정치 $(\Delta)_j인 경우< 0$ , а при соответствующей переменной x j нет ни одного положительного коэффициента, то задача не имеет оптимального решения из-за ограниченности целевой функции

c) 적어도 하나의 추정치 $(\Delta)_j인 경우< 0$ , а при соответствующей переменной x j есть хотя бы один положительный коэффициент, то решение не оптимально и его можно улучшить переходом к новому базису. Если отрицательных оценок несколько,то в базис ввести переменную с наибольшей по абсолютной величине отрицательной оценкой.

문제를 줄여보자 정식 형식.

Nikolai의 생산 문제에 대한 완전한 선형 프로그래밍 모델은 다음과 같이 작성할 수 있습니다.

\[\왼쪽\( (\시작(배열)()
(3(x_1) + 10(x_2) + (x_3) = 330)\\
(16(x_1) + 4(x_2) + (x_4) = 400)\\
(6(x_1) + 6(x_2) + (x_5) = 240)\\
(-(x_2) +(x_6) = 12)\\
((x_j) \ge 0\;j = \overline (1,n))
\end(배열)) \right.\]

B.p.	x 1	x 2	x 3	4개	x 5	x 6	비 나는
x 3	3	10	1	0	0	0	330
4개	16	4	0	1	0	0	400
x 5	6	6	0	0	1	0	240
x 6	0	-1	0	0	0	1	12

\[\bar(x)_(\text(support))=(0;0;330;400;20;12)\]

심플렉스 테이블에서 자유 변수를 찾아 이 솔루션의 최적성을 확인해 보겠습니다. 계산은 lp_simplex.xlsx 파일에 표시됩니다.

이 솔루션은 최종 결과에 음수 값이 있으므로 최적이 아닙니다. 양수 계수가 있으므로 솔루션을 개선할 수 있습니다. 이를 위해 변수 x 2를 기저에 도입합니다. x2 열에는 여러 개의 양수 계수가 있으므로 이 열의 해당 계수에 대한 자유 항 b i 의 비율을 결정하고 가장 작은 결과를 선택합니다.

테이블을 변환하고 계산을 반복해 보겠습니다.

이 솔루션은 최종 결과에 음수 값이 있으므로 최적이 아닙니다. 양수 계수가 있으므로 솔루션을 개선할 수 있습니다. 이를 위해 변수 x 1을 기저에 도입합니다.

결과 솔루션(10, 30)이 최적입니다.

Excel과 LibreOffice를 활용한 솔루션

Excel의 솔루션은 단순 방법을 사용하는 "솔루션 검색" 추가 기능을 사용하여 수행됩니다.

LibreOffice의 Solver를 사용하여 비슷한 문제를 해결할 수 있습니다. LibreOffice에서는 Excel과 달리 변수 수에 제한이 없습니다.

R의 솔루션

다음 패키지는 GNU R의 선형 프로그래밍 문제를 해결하는 데 사용할 수 있습니다.

lp해결
린프로그

두 번째 패키지는 첫 번째 패키지의 추가 기능으로 더 많은 진단 정보를 표시할 수 있습니다.

lpSolve 패키지를 사용한 솔루션

library(lpSolve) # 포함된 라이브러리 f.obj<- c(2500, 3500) # Описали целевую функцию names(f.obj) <-c("A","B") a.mat<-rbind(c(3,10), # матрица c(16,4), # коээфициентов c(6,6), # при ограничениях c(1,0), c(0,1)) a.dir<-c("<=","<=","<=",">=",">=") b.vec<-c(330,400,240,0,12) # вектор ограничений result<-lp ("max", f.obj, a.mat, a.dir, b.vec)

결과

result ## 성공: 목적 함수는 130000입니다. result$solution ## 10 30

따라서 목적 함수의 최대값은 130000이고 x 1과 x 2가 각각 10과 30일 때 달성됩니다.

linprog 패키지를 사용한 솔루션

패키지이기 때문에 린프로그이전 패키지에 추가된 경우 변수는 이미 모두 초기화되었습니다.

Library(linprog) ## 경고: "linprog" 패키지는 R 버전 3.2.2에서 빌드되었습니다(결과<-solveLP(f.obj, b.vec, a.mat, TRUE,const.dir=a.dir,lpSolve=T)) ## ## ## Results of Linear Programming / Linear Optimization ## (using lpSolve) ## ## Objective function (Maximum): 130000 ## ## Solution ## opt ## A 10 ## B 30 ## ## Constraints ## actual dir bvec free ## 1 330 <= 330 0 ## 2 280 <= 400 120 ## 3 240 <= 240 0 ## 4 10 >= 0 10 ## 5 30 >= 12 18

결과는 동일했고 추가적으로 무료 리소스에 대한 정보도 표시되었습니다. 따라서 GNU R은 선형 프로그래밍 문제를 해결하는 데 매우 편리한 메커니즘을 제공합니다.

접촉 중

심플렉스 테이블을 사용하여 선형 프로그래밍 문제를 해결해야 하는 경우 당사의 온라인 서비스가 큰 도움이 될 것입니다. 심플렉스 방법은 함수가 극한값을 취하는 꼭지점을 찾기 위해 허용 가능한 값 범위의 모든 꼭지점을 순차적으로 검색하는 것입니다. 첫 번째 단계에서는 일부 솔루션이 발견되며 이는 각 후속 단계에서 개선됩니다. 이 솔루션을 기본이라고 합니다. 다음은 심플렉스 방법을 사용하여 선형 프로그래밍 문제를 풀 때 수행되는 일련의 작업입니다.

첫 번째 단계. 컴파일된 테이블에서 먼저 free 멤버가 있는 컬럼을 살펴봐야 합니다. 부정적인 요소가 있으면 두 번째 단계로 이동하고, 그렇지 않은 경우 다섯 번째 단계로 이동해야 합니다.

두번째 단계.

두 번째 단계에서는 단순표를 다시 계산하기 위해 기본에서 제외할 변수와 포함할 변수를 결정해야 합니다. 이렇게 하려면 자유 용어가 포함된 열을 살펴보고 그 안에 있는 부정적인 요소를 찾으세요. 음수 요소가 있는 줄을 행간이라고 합니다. 여기에서 모듈러스의 최대 음수 요소를 찾고 해당 열은 슬레이브 열입니다. 자유 용어 사이에 음수 값이 있지만 해당 행에는 없는 경우 해당 테이블에는 솔루션이 없습니다. 자유항 열에 위치한 앞 행의 변수는 기저에서 제외되고, 앞 열에 해당하는 변수는 기저에 포함됩니다.

1 번 테이블.	기본 변수	제한이 있는 무료 회원
1 번 테이블.	기본 변수	x 1	x 2	...	기본이 아닌 변수	...	xl
xn	xn+1	비 1	11	...	12	...	1리터
1n	xn+2	비 2	21	...	22	...	2리터
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
2n	xn+r	b2	r1	...	r2	...	rl
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
아른	xn+m	비엠	m1	...	m2	...	1ml
백만	F(x)최대	F 0	-c 1	...	F 0	...	-c 2

-cn

세 번째 단계. 세 번째 단계에서는 특수 공식을 사용하여 전체 심플렉스 테이블을 다시 계산합니다.

다섯 번째 단계. 다섯 번째 단계에 도달했다면 받아들일 수 있는 해결책을 찾은 것입니다. 그러나 이것이 최적이라는 의미는 아닙니다. F-문자열의 모든 요소가 양수인 경우에만 최적입니다. 그렇지 않은 경우 다음 알고리즘을 사용하여 다음 재계산을 위한 선행 행과 열을 찾는 솔루션을 개선해야 합니다. 처음에는 함수 값을 제외하고 문자열 F에서 최소 음수를 찾습니다. 이 번호가 있는 열이 선두 열이 됩니다. 선행 행을 찾기 위해 해당 자유 항과 선행 열의 요소(양수인 경우)의 비율을 찾습니다. 최소 비율을 사용하면 선행선을 결정할 수 있습니다. 공식을 사용하여 테이블을 다시 계산합니다. 3단계로 이동하세요.