LLP를 해결하기 위한 심플렉스 방법. 단순 방법에 대한 일반적인 아이디어. 선형 계획법 문제를 해결하기 위한 심플렉스 방법
쿠르스크 국가 및 지방자치 서비스 아카데미
정보기술보안학과
수필
규율에 따라 "최적의 솔루션 방법"
주제에 "단순법의 아이디어"
완료자: 2학년 학생
전문 분야 "경제학"
모스칼레바 O.S.
확인자: Ph.D., 부교수 Pogosyan S. L.
쿠르스크 - 2012
소개..........................................................................................................................3
1. 심플렉스법의 개념 ..............................................................4
2. 예제를 이용한 심플렉스 방법의 구현..................................................6
3. 간단한 단순 방법의 테이블 형식 구현...........10
결론..........................................................................................................................15
사용된 문헌 목록..........................................................16
소개.
Simplex 방법은 대부분의 최적화 문제를 해결하는 데 사용되는 반복 계산의 전형적인 예입니다.
단순 방법의 계산 체계에서는 허용 가능한 초기 모서리 지점(일반적으로 원점)에서 시작하여 최적의 솔루션에 해당하는 지점이 될 때까지 허용 가능한 한 극단 지점에서 다른 지점으로 연속적인 전환이 이루어지는 정렬된 프로세스가 구현됩니다. 설립하다.
단순 방법의 아이디어
표준 선형 계획법 문제를 해결하기 위한 보편적인 방법을 고려해 보겠습니다. N변수와 중단순 방법으로 알려진 등식 제약 조건.
정식 문제에 대한 계획 세트는 유한한 수의 꼭지점을 가진 볼록 다면체 세트입니다. 그리고 이 문제에 최적의 솔루션이 있다면 적어도 하나의 꼭지점에서 달성됩니다.
모든 꼭짓점은 문제의 기본 계획과 연관되어 있으며 변수는 0이고 나머지 변수는 조건 행렬의 선형 독립 열에 해당합니다. 이러한 선형 독립 열은 비특이 기저 행렬을 형성합니다.
모든 모서리 점을 반복하는 것은 계산 비용이 많이 들고 따라서 비효율적입니다. 1947년에 J. Danzig는 모서리 점을 열거하는 순서적인 절차를 제안했습니다. 이 절차에서는 모서리 점 중 작은 부분만 검사해도 최적의 솔루션을 찾을 수 있습니다. 이 절차를 단순 방법.
J. Dantzig는 한 극점에서 다른 극점으로 이동할 때 기본 행렬에서 하나의 벡터만 대체할 것을 제안했습니다. 이는 이러한 전환 중에 기본 변수 중 하나를 제외해야 함을 의미합니다. 이를 비기본(0과 동일)으로 만들고 그 자리에 비기본(0) 중에서 새 변수를 도입하여 기본(양수)으로 만듭니다. ).
기하학적으로 이러한 교체는 한 모서리 점에서 공통 모서리로 이전 점에 연결된 인접한 모서리 점으로의 전환으로 이어진다는 것이 밝혀졌습니다.
모든 인접 점 중에서 목적 함수가 가장 많이 증가하는 점을 선택합니다. 모서리 점의 수가 유한하기 때문에 유한한 수의 전이를 통해 목적 함수의 값이 가장 큰 꼭지점을 찾거나 목적 함수의 무한성이 무제한의 계획 집합에서 설정됩니다.
단순 방법의 일반적인 구성은 다음과 같은 주요 단계로 구성됩니다. 0단계. 초기 기준과 해당 초기 코너점(기준선)을 결정합니다.
1 단계. 최적성을 위해 현재 기준선 확인 . 최적성 기준을 만족하는 경우, 저것 계획이 최적이고 솔루션이 완료되었습니다. 그렇지 않으면 2단계로 가세요.
2 단계. 기본에 도입된 변수를 찾아보세요. (목적함수를 증가시키는 조건에서).
3단계. 기본변수에서 제외된 변수를 찾는다(문제의 제약조건을 유지하는 조건에서).
단계 4 . 새 기준선(인접한 모서리 점)의 좌표를 찾습니다. 1단계로 이동합니다.
1~4단계를 반복하면 심플렉스 방법이 한 번 반복됩니다.
이 다이어그램에서 단순 방법을 시작하려면 먼저 초기 기본 계획인 일종의 코너 포인트가 있어야 하며, 두 번째로 인접한 모든 것을 계산하지 않고 현재 코너 포인트의 최적성을 검사할 수 있어야 합니다. 정점. 이러한 문제는 정규 LP 문제가 특별한 형태를 가지면 쉽게 해결됩니다.
정의. 우리는 다음과 같은 경우에 표준 LP 문제가 "선호되는 형태"를 갖는다고 말할 것입니다: 방정식의 우변; 조건 행렬에는 단위 크기 부분 행렬이 포함되어 있습니다.
즉, 어떤 방정식에는 다른 방정식에는 없는 계수가 1인 변수가 있습니다. 첫 번째 조건은 부담스럽지 않습니다. 일부 방정식의 음의 우변의 경우 (-1)을 곱하면 충분하기 때문입니다. 우선 유형 문제에서 초기 기준선을 찾는 것은 매우 간단합니다.
예제를 이용한 심플렉스 방법 구현
예를 들어 Simplex 방법의 사용법을 살펴보겠습니다. 표준 LP 문제를 고려하십시오.
| 에프엑스(f(x)) = 엑스 1 + 2엑스 2 + 0엑스 3 + 0엑스 4 > 최대 | ||
| -엑스 1 + 2엑스 2 +x 3 = 4, | ||
| 3엑스 1 + 2엑스 2 +x 4 = 12, | ||
| xj? 0, j = 1,2,3,4. | ||
조건 매트릭스 ㅏ = (ㅏ 1 , ㅏ 2 , ㅏ 3 , ㅏ 4), 여기서
타겟 벡터 씨 =(c1, c2, c3, c4) = (1, 2, 0, 0); 오른쪽 부분으로 구성된 벡터 비=(비 1 ,비 2) = (4, 12).
0단계.시작 모서리 지점(기준선) 찾기.
방정식의 우변은 양수이고 조건 행렬의 열은 양수이므로 문제는 바람직한 형식을 갖습니다. ㅏ 3, ㅏ 4개는 단위 부분행렬을 형성합니다. 이는 초기 기본 행렬을 의미합니다. = (ㅏ 3 ,답변 4); 엑스 3 그리고 엑스 4 - 기본 변수 엑스 1 그리고 엑스 2 - 기본이 아닌 변수, ㄷB = (씨 3, 씨 4) = = (0, 0).
초기 기준선은 다음과 같습니다. x 0 =(0, 0, 엑스 3 , 엑스 4) = (0, 0, 4, 12); f(xo) = 0.
1 단계.최적의 기본계획을 확인합니다.
공식 (5.1)을 사용하여 기본이 아닌 변수에 대한 단순 추정을 계산해 보겠습니다.
? 1 = 1 > - ㄷ 1 = 0·(-1) + 0 ·3 - 1 = -1 .
? 2 = 2 > - ㄷ 2 = 0 2 + 0 2 - 2 = -2 .
추정치가 마이너스이므로 계획은 엑스- 최적이 아닙니다. 우리는 목적함수 값이 더 큰 새로운 기준선(인접한 꼭지점)을 찾을 것입니다.
2 단계. 베이시스에 도입된 변수를 찾습니다.
기본 변수에 기본이 아닌 변수 중 하나를 도입하여(양수로 만들어) 목적 함수를 늘릴 수 있습니다. 엑스 1 또는 엑스 2, 두 추정 모두 이후 ? 제이 x 2.
3단계.기저에서 파생된 변수의 정의입니다.
변수를 베이시스에 입력한 후 x 2새로운 계획은 다음과 같을 것이다
x" =(0, 엑스 2, 엑스 3 , 엑스 4).
이 계획은 0 좌표가 하나만 포함되어 있으므로 기본 계획이 아닙니다. 즉, 변수 중 하나를 0으로 만들어야 함을 의미합니다(기본에서 제외). 엑스 3 또는 엑스 4 . 계획의 좌표를 대체하자 x" =(0, 엑스 2, 엑스 3 ,엑스 4) 문제의 제약. 우리는 얻는다
2엑스 2 +x 3 = 4,
2엑스 2 + 엑스 4 = 12.
여기서부터 기본적인 변수를 표현해보자 엑스 3 그리고 엑스 4 변수를 통해 엑스 2 , 기초로 들어갔습니다.
| 엑스 3 = 4 - 2엑스 2, | ||
| 엑스 4 = 12 - 2엑스 2 . | ||
그래서 변수 엑스 3 그리고 엑스 4 음수가 아니어야 하며, 불평등 시스템을 얻습니다.
| 4 - 2엑스 2 ? 0, | ||
| 12 - 2엑스 2 ? 0. | ||
값이 높을수록 엑스 2 , 목적함수가 증가할수록. 문제의 제약조건을 위반하지 않는, 즉 조건 (2.8), (2.9)를 만족하는 새로운 기저변수의 최대값을 찾아보자.
마지막 불평등을 형식으로 다시 작성해 보겠습니다.
2엑스 2 ? 4,
2엑스 2 ? 12,
최대값은 어디에서 오는가? 엑스 2 = min ( 4/2, 12/2 ) = 2. 이 값을 식 (2.6), (2.7)에 대입하면 다음과 같습니다. 엑스 3 그리고 엑스 4 , 우리는 얻는다 엑스 3 = 0. 그러므로 x 3 기초에서 파생된 .
4단계.새 기준선의 좌표를 결정합니다.
새 기준선(인접 모서리 점)은 다음과 같습니다.
엑스" = (0, 엑스 2, 0, 엑스 4)
이 포인트의 기초는 열로 구성됩니다. ㅏ 2 및 ㅏ 4 , 그래서 =( ㅏ 2, ㅏ 4). 이 기초는 벡터가 아니기 때문에 단일성이 아닙니다. ㅏ 2 = (2,2), 따라서 문제 (2.2)-(2.5)는 새로운 기초와 관련하여 선호되는 형식을 갖지 않습니다. 새로운 기본 변수와 관련하여 선호되는 형식을 취하도록 문제 (2.3), (2.4)의 조건을 변환해 보겠습니다. 엑스 2, 엑스 4, 즉, 변수가 엑스 2 는 계수가 1인 첫 번째 방정식에 포함되었고 두 번째 방정식에는 존재하지 않았습니다. 문제의 방정식을 다시 써보자
- 엑스 1 + 2 엑스 2 + 엑스 3 = 4, (피 1)
3엑스 1 +2 엑스 2 + 엑스 4 = 12. (피 2)
첫 번째 방정식을 계수로 나누어 보겠습니다. 엑스 2 . 우리는 새로운 방정식을 얻습니다 =피원본과 동등한 1/2
1/2 엑스 1 + 엑스 2 + 1/2 엑스 3 = 2. ()
우리는 해결이라고 부르는 이 방정식을 사용하여 변수를 제거합니다. 엑스 2 두 번째 방정식에서. 이렇게하려면 방정식에 2를 곱하고 빼야합니다. 피 2 . 우리는 얻는다 =피 2 - 2=피 2 - 피 1:
4 엑스 1 - 엑스 3 + 엑스 4 = 8. ()
결과적으로 우리는 새로운 기본 변수와 관련하여 원래 문제에 대한 새로운 "선호" 표현을 얻었습니다. 엑스 2 , 엑스 4:
에프(엑스) = 엑스 1 + 2 엑스 2 + 0 엑스 3 + 0 엑스 4? 최대
1/2 엑스 1 + x 2 + 1/2 엑스 3 = 2 ()
4 엑스 1 - 엑스 3 + 엑스 4 = 8 ()
xj? 0, j = 1,2,3,4
여기에 새로운 기준선의 표현을 대체합니다. 엑스 1 = (0, 엑스 2, 0, 엑스 4) 기본 변수의 값이 방정식의 오른쪽과 동일하므로 좌표를 즉시 찾습니다.
엑스" = (0, 2, 0, 8); 에프(엑스 1)=4.
이것으로 심플렉스 방법의 첫 번째 반복이 완료됩니다. 다음으로, 문제 해결 프로세스는 1단계부터 계속됩니다. 이는 발견된 계획의 최적성을 확인하는 것으로 구성됩니다. 현재 기본 계획의 모든 단순 추정이 음수가 아닌 것으로 판명되면 솔루션이 종료됩니다.
단순 방법의 모든 계산을 표 형식으로 수행하는 것이 더 편리하기 때문에 첫 번째 계획에 따라 두 번째 반복을 수행하지 않습니다.
간단한 단순 메서드의 테이블 형식 구현
동일한 예제 (2.2)-(2.5)를 사용하여 테이블 형식 구현을 시연합니다.
0단계. 솔루션은 초기 심플렉스 테이블을 구성하는 것부터 시작됩니다. 먼저, 표의 오른쪽은 세 번째 열부터 채워집니다. 위쪽 두 줄에는 작업 변수의 이름( 엑스 1, ...,엑스 4) 및 이러한 변수에 대한 목적 함수의 계수. 다음은 방정식의 계수입니다 - 조건 행렬의 요소 ㅏ, 그래서 변수 아래에 엑스 1 위치한 열 ㅏ 1, 변수 아래 엑스 2 - 열 ㅏ 2 등. 제약 조건(숫자)의 오른쪽은 오른쪽 열에 입력됩니다. 비 나는 > 0).
그런 다음 단위 기준을 형성하는 조건 행렬의 열을 찾습니다. 이 예에서는 다음과 같습니다. ㅏ 3 및 ㅏ 4 - 및 해당 기본 변수 엑스 3, 엑스 4 두 번째 칸에 쓰세요. 마지막으로 첫 번째 열에는 기본 변수에 대한 목적 함수의 계수를 작성합니다.
1 번 테이블- 초기 심플렉스 테이블
| 기본 변수 | 기본 변수 값 ( x B =b) |
|||||
| x 1 | x 2 | x 3 | 4개 | |||
| x 3 | 11 =-1 | |||||
| 4개 | ||||||
| 평가선 ? 제이 | ? 1 = -1 | ? 2 = -2 |
문제는 선호하는 형식을 가지므로 기본 변수의 값은 마지막 열에 있는 방정식의 우변과 같습니다. 기준이 아닌 변수가 0이므로 초기 기준은 다음과 같습니다.
엑스오 = (0, 0, 엑스 3 , 엑스 4) = (0, 0, 4, 12).
1 단계.계획을 확인하려면 엑스영형 최적성을 위해 기본이 아닌 변수에 대한 단순 추정을 계산합니다. 엑스 1 그리고 엑스 2 공식에 따르면
? j = 비, Aj > -cj .
? 1 = 비, ㅏ 1 > - ㄷ 1 = 0·(-1) + 0 ·3 - 1 = -1 .
점수 계산을 위한 표 형식 구현 ? 1 첫 번째 열의 요소 곱의 합을 구해야 합니다( ㄷB)를 해당 열 요소로 ㅏ 1 기본이 아닌 변수의 경우 엑스 1 . 점수도 같은 방법으로 계산됩니다 ? 2 , 첫 번째 열의 스칼라 곱( ㄷB) 변수의 열당 x 2.
? 2 = 2 > - ㄷ 2 = 0 2 + 0 2 - 2 = -2 .
단순 추정치는 델타 행이라고 하는 단순 테이블의 마지막 행에 기록됩니다. 이 경우 기본이 아닌 변수에 대한 셀은 물론, 기본 셀도 채워집니다. 조건 행렬의 기본 단위 열에 대해 단순 추정치가 0과 같은지 쉽게 확인할 수 있습니다. 평가 라인의 마지막 셀에서 해당 지점의 목적 함수 값을 씁니다. xo.참고로 기본계획의 비기본좌표는 0이므로 다음 공식을 이용하여 목적함수를 계산하는 것이 편리하다.
에프(엑스)=cB, xB >,
테이블의 첫 번째 열과 마지막 열을 스칼라 곱합니다.
추정치 중에서 ? 제이있다 부정적인 , 그럼 계획은 엑스 o는 최적이 아니며, 기본이 아닌 변수 중에서 기본 변수 중 하나를 새로운 변수로 대체하여 새로운 기본 방안을 찾는 것이 필요하다.
2 단계.둘 다 추정이므로 ? 1 그리고 ? 2 그러면 모든 변수가 기본에 포함될 수 있습니다. 엑스 1, 엑스 2 . 절대 음수 추정치가 가장 큰 변수를 기저에 도입해 보겠습니다. 엑스 2 .
베이시스에 입력된 변수가 위치한 심플렉스 테이블의 컬럼을 선행 컬럼이라 합니다..
이 예에서 선행 열은 다음 위치에 있습니다. x 2 .
3단계.선행 열의 모든 요소가 음수이면 문제에 대한 해결책이 없으며 최대 에프(엑스) ???. 이 예에서는 선행 열의 모든 요소가 양수이므로 최대값을 찾을 수 있습니다. 엑스 2 , 이전 기본 변수 중 하나가 0이 되는 경우. 최대값을 기억하세요. x 2 =최소(4/2, 12/2)=2.
표에 따르면 이 값은 다음과 같이 계산됩니다. 기준선 구성 요소(마지막 열부터)의 비율 중 가장 작은 비율 긍정적인선행 열의 요소.
가장 작은 비율은 기본 변수가 있는 행에 있습니다. x 3.그래서 변수는 x 3기본변수에서 제외( 엑스 3 = 0).
기저에서 제외할 변수가 포함된 행을 선행선이라고 합니다.
이 예에서는 선행 줄이 첫 번째 줄이 됩니다.
선행 행과 선행 열의 교차점에 있는 요소를 선행 요소라고 합니다.
우리의 경우 주요 요소 ㅏ 12 = 2.
테이블 2- 선행 행과 열이 있는 초기 단순 테이블
| 기본 변경 사항. | 기본 변수 값 | 방정식 |
|||||
| x 2 | |||||||
| c 3 =0 | x 3 | -1 | 2 | 1 | 0 | 4 | |
| 2 | |||||||
| 평가선 ? 제이 | ? 1 = -1 | ? 2 = -2 | |||||
4단계. 새로운 기본 계획을 얻기 위해 새로운 기본 변수와 관련하여 문제를 새로운 선호 형태로 축소합니다.
이를 위해 제외된 변수 대신 두 번째 열에 새로운 단순 테이블을 구축합니다. x 3새로운 기본 변수를 작성해 봅시다 x 2, 그리고 첫 번째 열( B와 함께) 대신에 3부터목적 함수의 계수를 적어 보겠습니다. x 2: c 2 =2. 새 단순 테이블에서 다음 열은 x 2~ 해야 하다 1이 됩니다(선행 요소는 1과 같아야 하고 다른 모든 요소는 0이 되어야 합니다). 이는 다음 테이블 행 변환을 통해 달성됩니다.
ㅏ.선행 행의 모든 요소를 선행 요소로 나누고 이를 새 단순 테이블의 동일한 행에 씁니다.
결과 문자열 피 1"그것을 허용적이라고 부르자.
비.나머지 두 번째 줄에 해결 줄을 추가하고 선행 열의 요소가 0이 되는 숫자를 곱합니다.
p 2 " = p 2 + (- 2) p 1 " = p 2 - p 1.
씨.추정치를 계산하여 마지막 줄을 채워보자 ? j " = - - c j, 어디 c B ", A j " -새 단순 테이블의 해당 열과 목적 함수의 값 에프(엑스)= .
우리는 새로운 기초를 가진 두 번째 심플렉스 테이블을 얻습니다.
표 3- 첫 번째 반복 결과
| 기본 변경 사항. | 기본 변수 값 | 방정식 | ||||||
| -1/2 | ||||||||
| 4개 | 4 | 0 | -1 | 1 | 8 | 피 2 " =피 2 - 피 1 | ||
| 평가 ? 제이" | -2 | |||||||
새로운 기준 엑스 " = (0, x 2, 0, x 4) = (0, 2, 0, 8 ). 평가 이후 ? 1 = -2 다음 계획 엑스 " 최적이 아닙니다. 새로운 기본 계획(인접 모서리 점)으로 이동하기 위해 단순 방법의 또 다른 반복을 수행합니다.
왜냐하면? 1 그런 다음 변수가 기본에 도입됩니다. x 1. 다음을 포함하는 첫 번째 열 x 1 -주요한.
기본 계획의 구성 요소와 해당 구성 요소 간의 관계를 찾습니다. 긍정적인선행 열의 요소를 삭제하고 비율이 가장 작은 행을 선행 행으로 사용합니다. 표 2에서 선행 열의 두 번째 요소만 0보다 크므로(= 4) 두 번째 줄이 선두 줄이 될 것입니다, 그리고 그 안에 위치한 기초 변하기 쉬운 4개기준에서 제외됨.
우리는 선행 열과 선행 행을 선택하고 교차점에서 다음을 찾습니다. 선행 요소(= 4).
기본 변수를 대체하여 새로운(세 번째) 단순 테이블을 작성합니다. 4개 ~에 x 1 , 그리고 선행 요소가 1이 되고 선행 열의 나머지 요소가 0이 되도록 테이블 행을 다시 변환합니다. 이렇게 하려면 선행(두 번째) 줄을 4로 나누고 첫 번째 줄에 결과 두 번째 줄을 2로 나눈 값을 추가합니다. 단순 추정 공식을 사용하여 마지막 줄을 계산합니다. ? 제이"" = "", Aj""> - cj, 어디 ㄷB"", Aj"" - 새 단순 테이블의 해당 열. 새 기준선의 목적 함수 값은 다음 공식을 사용하여 구합니다. 에프(엑스"")= "",×B"" >.
표 4- 두 번째 반복 결과
| 기초적인 변화. | 기본 변수 값 | 방정식 |
|||||
| p 1 "" = p 1 "+p 2 ""/2 |
|||||||
| p 2 "" = p 2 "/4 |
|||||||
| 평가 ? 제이 "" | 에프(엑스"")= 8 | ||||||
새로운 기준 엑스 "" = (x 1 , x 2 , 0, 0) = (2, 3, 0, 0 ). 모든 추정치는 음수가 아니므로 계획은 엑스 ""- 최적의 계획.
따라서, 엑스* = (2, 3, 0, 0 ), f(x*) = 8.
결론
선형 프로그래밍 문제를 해결하기 위해 고려된 방법은 실제로 널리 사용됩니다. 그러나 주목해야 할 점은
수학적 모델은 항상 실제 경제 시스템보다 열악합니다. 이 시스템은 일부 속성을 강조하고 다른 속성은 무시하면서 대략적으로만 설명합니다. 수리경제학의 이러한 단점을 보완하기 위해 여러 유형의 모델이 개발되고 있으며, 각 모델은 경제 현실의 특정 측면을 반영하여 특정 경제 문제를 해결할 때 가장 적합한 모델을 선택할 수 있도록 설계되었습니다. .
사용된 참고문헌 목록
1. Ashmanov S.A. 선형 프로그래밍. -M .: Nauka, 1981.
이전에는 선형 계획법 문제에 최적의 솔루션이 있는 경우 최적의 솔루션 중 하나가 시스템의 허용 가능한 솔루션 다면체의 특정 모서리 지점에 해당하는 제약 조건 시스템에 허용되는 기본 솔루션인 것으로 나타났습니다.
문제의 제약 조건 시스템에 대한 기본 솔루션의 유한 검색을 사용하여 최적의 솔루션을 찾는 방법을 보여주었습니다. 그러나 문제제약계의 차원 n이 커짐에 따라 기본해를 다 열거하는 방법으로 문제를 해결하기 위한 계산량이 기하급수적으로 늘어나 현실적으로 부적합해진다.
목적 함수의 해당 값이 향상되거나 적어도 저하되지 않도록 후속적으로 허용되는 각 기본 해를 선택하는 경우 실행 가능한 기본 해의 열거만 구성하고 열거된 해의 수를 크게 줄이는 것이 가능합니다. 이 접근 방식을 사용하면 최적의 기본 솔루션을 찾을 때 단계 수를 줄일 수 있습니다. 이 아이디어를 그래픽으로 설명하겠습니다.
다각형 ABCDEFGH가 두 변수가 있는 PLP의 실행 가능한 해 집합을 나타내고 벡터 N을 다음과 같이 표현한다고 가정합니다. 목적 함수의 기울기.
우리는 목적 함수가 가장 작은 값을 취하는 이 다각형의 지점을 찾아야 합니다.
꼭지점 B에 해당하는 문제의 초기 실현 가능한 기본 해를 결정하겠습니다.
가능한 모든 기본 솔루션을 완전히 검색하려면 다각형의 8개 꼭지점에 해당하는 8개의 솔루션을 검사해야 합니다.
그러나 그림에서 볼 때 기울기 N의 방향을 고려할 때 이웃 꼭지점 C로 이동한 다음 문제의 최적 기본 솔루션에 해당하는 이웃 꼭지점 D로 이동하는 것이 더 유리하다는 것이 분명합니다.
따라서 8개의 솔루션 대신 3개의 실행 가능한 기본 솔루션만 고려하면 됩니다.
솔루션의 순차적 개선 아이디어는 선형 계획법 문제를 해결하기 위한 보편적인 방법인 심플렉스 방법의 기초를 형성합니다.
단순법과 그 이름은 1947년 미국 수학자 존 댄치히(John Danzig)에 의해 처음 제안되었지만, 이 방법의 아이디어는 러시아 수학자 L.V. Kantorovich는 1939년에 "생산을 조직하고 계획하는 수학적 방법"이라는 기사에서 돌아왔습니다.
단순 방법의 기하학적 의미는 실현 가능한 해의 다면체의 한 꼭지점에서 문제에 대한 이웃 문제로 순차적 전환이 수행된다는 것입니다. 여기서 목적 함수는 이전 꼭지점보다 나쁘지 않은 값을 갖습니다. 이러한 전환은 최적의 솔루션을 찾거나 문제에 솔루션이 없다는 것이 발견될 때까지 계속됩니다.
단순 방법은 세 가지 주요 요소로 구성됩니다.
문제에 대한 초기의 실행 가능한 기본 솔루션을 결정합니다.
허용 가능한 다음 최악의 기본 솔루션으로의 전환 규칙
발견된 솔루션의 최적성을 확인합니다.
단순법은 정규 형식으로 작성된 선형 계획법 문제에 적용됩니다.
선형 방정식 시스템의 단순 변환
표준 형식의 ZLP를 고려해 보겠습니다. 선형 방정식 시스템이 주어집니다:
우리는 이 시스템에 대해 선형 함수를 최소화하는 음이 아닌 해를 찾아야 합니다.
– 방정식 시스템 (1)의 행렬,
– 이 시스템의 확장 매트릭스.
행렬 A와 B의 순위가 동일한 경우를 고려해 보겠습니다. 시스템 (1)에 무한한 수의 해가 있을 때. 우리의 임무는 이 경우 문제에 대한 최적의 솔루션이 있는지, 그리고 이를 찾는 방법을 찾는 것입니다.
명확성을 위해 행렬 A의 첫 번째 r개 열이 선형 독립이라고 가정하고 시스템 (1)을 가우스 제거 방법을 사용하여 다음 형식으로 변환할 수 있습니다.
이 시스템은 방정식 (1) 시스템과 동일합니다. 승률 열
시스템 (2) 행렬의 열 시스템의 기초를 형성하므로 변수는 기본이고 집합은 기본 집합입니다.
간결하게 하기 위해 변수의 기준 집합을 기준이라고 부르겠습니다. 이는 계수 열의 해당 기준을 의미합니다. 나머지 변수는 무료입니다.
시스템 (3)의 기본 변수를 자유 변수로 표현하고 시스템 (4)를 구해 보겠습니다.
(4)
(4)는 방정식 (1) 시스템에 대한 일반적인 해라고 말하는 것이 관례입니다. 자유 변수에 0 값을 할당함으로써 기본 변수의 값을 결정하고 구성된 기본 변수 집합에 해당하는 기본 솔루션을 구성합니다.
따라서 시스템 (1)의 기본 솔루션입니다.
다음에서는 시스템 (1)에 허용 가능한 해가 있으면 조건 (5)가 충족되는 형식 (3)으로 변환될 수 있음을 보여줍니다.
따라서 조건 (5)가 만족된다고 가정한다. 그러면 기본 솔루션은 실행 가능한 기본 솔루션입니다.
등식(4)을 사용하여 자유 변수의 관점에서 함수 f를 표현할 수 있습니다. (6) 이제 기본 해에 해당하는 함수 f의 값을 계산할 수 있습니다.
심플렉스 방법의 아이디어를 구현하여 실행 가능한 하나의 기본 솔루션에서 다른 솔루션으로 이동하는 방법을 배웁니다. 이를 위해 기본 변수 xi 중 하나를 기본에서 제거하고 일부 자유 변수 xj로 대체합니다.
이러한 기저 변경으로 방정식 시스템(4)과 선형 함수(6)가 변환됩니다. 이를 위해서는 시스템 (3)의 i번째 방정식을 다음과 같이 풀어야 합니다. xj.
결과 방정식은 다음과 같습니다.
xj 대신 (7)의 식을 시스템(4)의 나머지 방정식과 함수(6)에 대체하면 시스템(1)과 동등한 새로운 시스템을 얻습니다. 이는 새로운 기저에 대해 해결됩니다.
기저에서 xi가 자유 변수 xj로 대체되었음을 나타내는 계수 aij를 심플렉스 테이블의 분해 요소라고 합니다. 평등 (7)으로부터 다음이 나온다.
새로운 기저 해는 허용 가능해야 하기 때문에(음수가 아니어야 함),
그러면 조건이 충족되어야 합니다. 즉, . 즉, j번째 열의 해결 요소 aij(xi는 자유 변수)를 양수로 선택해야 합니다. 다음 규칙에 따라 해결 요소 aij가 선택되면 설명된 변환 심플렉스를 호출합니다.
1. 요소 아이 양수 요소가 포함된 j번째 열에서 선택합니다.
2. 이 열에 여러 개의 양수 요소가 있는 경우 계수 akj>0에 대한 자유 항 bk의 비율을 구성합니다.
모든 비율 중에서 가장 작은 비율을 선택합니다. 순리에 맡기다 :
(8)
이 분수의 분모를 해결 요소로 선택합니다. 이러한 비율 중 여러 개가 최소(동일)인 경우 이러한 분모 중 하나를 선택합니다.
정리. 선형 방정식 시스템(4)에서 모든 자유 항이 음수가 아닌 경우 단순 변환을 적용한 후에는 음수가 아닌 상태로 유지됩니다.
증거. (4)의 단순 변환 이후의 새로운 자유 항을 다음과 같이 표시하겠습니다.
그 다음에 ~에
akj>0이면 (8)에서 다음과 같습니다.
akj라면
akj=0이면
결과. 단순 변환을 사용하면 ZLP의 허용되는 기본 솔루션에서 이 문제의 허용되는 다른 기본 솔루션으로 이동할 수 있습니다.
단순법
1. 심플렉스법의 아이디어
표준 LP 문제를 해결하기 위한 보편적인 방법을 고려해 보겠습니다.
단순법(Simplex Method)으로 알려져 있다.
2장에서 확립된 바와 같이, 표준 문제에 대한 계획 세트는 유한한 수의 꼭지점을 가진 볼록 다면체 세트입니다. 그리고 이 문제에 최적의 솔루션이 있다면 적어도 하나의 꼭지점에서 달성됩니다.
모든 꼭짓점은 문제의 기본 계획과 연관되어 있으며 변수는 0이고 나머지 변수는 조건 행렬의 선형 독립 열에 해당합니다. 이러한 선형 독립 열은 비특이 기저 행렬을 형성합니다.
모든 모서리 점을 반복하는 것은 계산 비용이 많이 들고 따라서 비효율적입니다. 1944년에 J. Dantzig는 모서리 점을 열거하는 순서적인 절차를 제안했습니다. 이 절차에서는 모서리 점 중 작은 부분만 검사해도 최적의 해를 찾을 수 있습니다. 이 절차를 단순 방법이라고 합니다.
J. Dantzig는 한 극점에서 다른 극점으로 이동할 때 기본 행렬에서 하나의 벡터만 대체할 것을 제안했습니다. 이는 이러한 전환 중에 기본 변수 중 하나를 제외해야 함을 의미합니다. 이를 비기본(0과 동일)으로 만들고 그 자리에 비기본(0) 중에서 새 변수를 도입하여 기본(양수)으로 만듭니다. ).
기하학적으로 이러한 교체는 한 모서리 점에서 공통 모서리로 이전 점에 연결된 인접한 모서리 점으로의 전환으로 이어진다는 것이 밝혀졌습니다.
모든 인접 점 중에서 목적 함수가 가장 많이 증가하는 점을 선택합니다. 모서리 점의 수가 유한하기 때문에 유한한 수의 전이를 통해 목적 함수의 값이 가장 큰 꼭지점을 찾거나 목적 함수의 무한성이 무제한의 계획 집합에서 설정됩니다.
단순 방법의 일반적인 구성은 다음과 같은 주요 단계로 구성됩니다.
· 0단계. 초기 베이시스와 해당 초기 코너 포인트(베이스라인)를 결정합니다.
· 1단계. 최적성을 위해 현재 기본 계획을 확인합니다. 최적성 기준이 충족되면 계획이 최적이고 솔루션이 완성됩니다. 그렇지 않으면 2단계로 가세요.
· 2 단계. 기본에 도입된 변수를 찾아보세요. (목적함수를 증가시키는 조건에서).
· 3단계. 기본변수에서 제외된 변수를 찾는다(문제의 제약조건을 유지하는 조건에서).
· 4단계. 새 기준선(인접한 모서리 점)의 좌표를 찾습니다. 1단계로 이동합니다.
1~4단계를 반복하면 심플렉스 방법이 한 번 반복됩니다.
이 다이어그램에서 단순 방법을 시작하려면 먼저 초기 기본 계획인 일종의 코너 포인트가 있어야 하며, 두 번째로 인접한 모든 것을 계산하지 않고 현재 코너 포인트의 최적성을 검사할 수 있어야 합니다. 정점. 이러한 문제는 정규 LP 문제가 특별한 형태를 가지면 쉽게 해결됩니다.
정의. 다음과 같은 경우 표준 LP 문제에 "선호 형식"이 있다고 말할 수 있습니다.
1. 방정식의 우변, .
조건 행렬에는 크기의 단위 부분행렬이 포함되어 있습니다.
즉, 어떤 방정식에는 다른 방정식에는 없는 계수가 1인 변수가 있습니다. 조건 1은 부담스럽지 않습니다. 일부 방정식의 음의 우변의 경우 (-1)을 곱하면 충분하기 때문입니다. 우선 유형 문제에서 초기 기준선을 찾는 것은 매우 간단합니다.
예 .
조건 행렬과 제약 조건의 우변 벡터는 다음과 같은 형식을 갖습니다.
하나의 기본 행렬은 즉시 명백해집니다. 단위 벡터를 사용하면
결과적으로 는 기본 변수이고 x2, x4는 비기본 변수입니다. 방정식 시스템에서 x2=x4 =0이라고 가정하면 즉시 x1 =10, x3 =20, x5 =8이 됩니다. 기본 변수의 값이 제약 조건의 오른쪽과 동일하다는 것을 알 수 있습니다. 이것으로부터 bi의 우변이 양수여야 한다는 요구 사항이 분명해졌습니다.
앞으로는 기본 변수를 벡터로 결합해 보겠습니다. 엑스비.
따라서, 선호 형식의 표준 문제에서 단위 부분행렬 AB =E는 초기 기저 행렬로 간주되고 해당 기저 변수는 제약 조건의 오른쪽 변과 같습니다: xB =b.
. Simplex 방법의 가장 간단한 구현
단순 방법("단순 C 방법")의 가장 간단한 구현은 "선호되는 형식"을 갖는 표준 LP 문제에 적용됩니다. 일반성을 잃지 않으면서 항등 부분행렬이 처음 m개의 열에 포함되어 있다고 가정하겠습니다. 그러면 정식 문제는 다음과 같이 작성됩니다.
f(x) = c 1엑스 1+c 2엑스 2+… +c 중 엑스 중 +c m+1 엑스 m+1 +… +c N 엑스 N ??최대(3.1)x 1+ 에 1m+1 엑스 m+1 + ... + 에 1n 엑스 N =b 1(3.2)x 2+ 에 2m+1 엑스 m+1 + ... + 에 2n 엑스 N =b 2………………………………………………………….엑스 중 + 에 mm+1 엑스 m+1 + ... + 에 백만 엑스 N =b 중 엑스 제이 ³ 0, j=1,2,…, n.(3.3)
조건 매트릭스
첫 번째 m 열에 m x m 크기의 단위 부분행렬이 포함되어 있으므로 AB =(A1, A2,…, Am)=E입니다.
심플렉스 방법의 기본 단계(이론)
단위 기준 행렬은 조건 행렬의 처음 m개 열에 있으므로 초기 기본 계획의 처음 m개 좌표는 기본이고 마지막 n-m 좌표는 비기본, 즉 0입니다.
o = (x1, x2,…, xm, 0,…, 0).
점 xo의 좌표를 제한 사항(3.2)에 대체하고 m+1 =... = xn = 0을 고려하면 x1 = b1, x2 = b2,..., xm = bm을 얻습니다. 즉, xoB = b입니다.
따라서 초기 기본 계획은 다음과 같습니다.
xo = (b1,…, bm, 0,…, 0),
여기서 сБ = (с1,…, сm)은 기본 변수에 대한 목적 함수의 계수로 구성된 벡터입니다.
1단계.
제약 조건 시스템(3.2)에서 기본 변수를 기본이 아닌 변수로 표현합니다.
엑스 1=b 1 - ㅏ 1m+1 엑스 m+1 - ... - ㅏ 1n 엑스 N, 엑스 2=b 2- ㅏ 2m+1 엑스 m+1 - ... - ㅏ 2n 엑스 N, …………………………× 중 =b 중 - ㅏ mm+1 엑스 m+1 - ... - 아멘 엑스 N, (3.4)
이 표현식을 목적 함수(3.1)로 대체해 보겠습니다.
f(x)=c 1(비 1- ㅏ 1m+1 엑스 m+1 - ... - ㅏ 1n 엑스 N) +c 2(비 2- ㅏ 2m+1 엑스 m+1 - ... - a2n 엑스 N ) +
………………………………………………..
씨 중 (비 중 - ㅏ mm+1 엑스 m+1 - ... - ㅏ 백만 엑스 N ) + ㄷ m+1 엑스 m+1 +... +cn 엑스 N .
동일한 비기본 변수를 사용하여 용어를 그룹화해 보겠습니다.
f (x) = - (c1 a1m+1 + c2 a2m+1 + … + cm amm+1 - cm+1).xm+1 - …
- (씨 1 ㅏ 1n +c 2 ㅏ 2n + … +c 중 ㅏ 백만 - 씨 N). 엑스 N. (3.5)
괄호 안의 표현식은 다음과 같이 쓸 수 있습니다.
씨 1 ㅏ 1m+1 +c 2 ㅏ 2m+1 + … +c 중 ㅏ mm+1 - 씨 m+1 = < c비 , ㅏ m+1 > - ㄷ m+1 = 디 m+1 ,
…………………………………………………………………………………………………………………………1 ㅏ 1n +c 2 ㅏ 2n + … +c 중 ㅏ 백만 - 씨 n= < c비 , ㅏ N > - ㄷ n= 디 N ,
어디서 비 = (와 1,…, 와 함께 중 )는 기본 변수 A에 대한 목적 함수의 계수로 구성된 벡터입니다. m+1 ,…, ㅏ N - 기본이 아닌 변수 x에 대한 조건 행렬 A의 열 m+1,…, x N .
표현식
디 제이 = < с비 , ㅏ 제이 > - CJ , j = m+1,…, n,(3.6)
단순 차이 또는 단순 기준선 추정이라고 합니다.
(3.6)을 고려하면 목적 함수에 대한 공식 (3.5)은 다음 형식으로 다시 작성될 수 있습니다.
이 공식을 통해 우리는 기본 계획의 최적성에 대한 신호를 얻을 수 있습니다. 기본이 아닌 숫자 D j ³ 0을 사용하여 모든 단순 추정을 수행하면 현재 기본 계획이 최적입니다.
실제로, 적어도 하나의 추정치(예: ?k)가 음수이면 해당 비기본 변수 xk에 양수 값을 제공하고 계획 x의 나머지 비기본 변수를 0으로 설정하면 다음을 얻습니다.
에프(엑스) = 에프(엑스 영형 ) - 디 케이 엑스 케이 =f(x 영형 ) + | 디 케이 | 엑스 케이 > 에프(엑스 영형 ),(3.7)
즉, 이 경우에는 plan x입니다. 영형 개선될 수 있습니다.
단위 기준 열에 해당하는 단순 추정값이 항상 0인 것을 쉽게 확인할 수 있습니다.
2 단계. 기본변수에 도입된 변수를 찾는다.
식 (3.7)에서 다음과 같이 기본 변수에 비기본 변수 x를 도입하여 목적 함수를 증가시킬 수 있습니다(양수로 만듦). 제이 , 이는 부정적인 평가에 해당합니까? 제이 < 0. Если таких оценок несколько, то обычно в состав базисных вводят небазисную переменную х에게 가장 큰 절대 음의 추정치를 갖는 것, 즉
여기서 D j =< CБ, Aj >- cj, j = m+1,…, n (기본이 아닌 변수의 개수).
이렇게 해서 우리는 새로운 계획을 세울 것이다
x1 = (x1,…, xm,0,…, xk,…, 0,…, 0).
그러나 x1은 기본이 아닌 계획입니다. 양의 좌표 수는 m+1이므로 0 좌표의 수는 n - m -1과 같습니다.
새로운 꼭지점을 얻으려면 기본 변수 중 하나를 0으로 설정해 보겠습니다. 즉, 기본 변수에서 하나의 변수를 제거합니다.
3단계.
점 x1의 좌표를 조건(3.4)으로 대체하고 변수 xj가 음수가 아니어야 한다는 점을 고려하겠습니다.
엑스 1=b 1- ㅏ 1천 엑스 케이 ³ 0x 2=b 2- ㅏ 2천 엑스 케이 ³ 0 .......................... 엑스 중 =b 중 - ㅏ MK xk ³ 0(3.8)
공식 (3.7)에서 x 값이 클수록 분명합니다. 에게 > 0일수록 목적 함수가 더 많이 증가합니다. x의 최대값을 구해보자 에게 , 문제의 제약 조건을 위반하지 않고 음이 아닌 조건(3.8)을 충족하지 않습니다.
불평등(3.8)은 다음과 같이 다시 작성할 수 있습니다.
ㅏ 1천 엑스 케이 £ 비 1 ㅏ 2천 엑스 케이 £ 비 2 ………………ㅏ MK 엑스 케이 £ 비 중 (3.9)
불평등 시스템(3.9)을 풀 때 두 가지 경우가 가능합니다. x에 대한 계수 중 에게 긍정적이지 않음: a 나는 £ 0, i=1,2,…, m. b 이후 나 > 0이면 임의로 큰 x 값에 대해 부등식(3.9)이 충족됩니다. 에게. 이는 목적 함수가 계획 세트(최대 f(x))에 제한되지 않음을 나타냅니다. ® ¥ ) 따라서 LP 문제에 대한 해결책은 없습니다.) x에 대한 계수 중 에게 긍정적인 것이 있다 나는 > 0. 불평등 시스템(3.9)을 풀면 다음을 얻습니다.
엑스 에게 £ 비 나 /ㅏ 나는 , 내가 어떤 aik에 대해 > 0.(3.10)
가장 큰 x 값 에게 는 모든 제한 사항(3.10)을 충족하며 이러한 부등식의 우변에 있는 비율 중 가장 작은 비율과 같습니다.
엑스 에게 =최소(b 나 /ㅏ 나는 ) 나 모두를 위해: aik > 0.
i = r, 즉 x에서 최소값을 달성하자 에게 ? 비 아르 자형 /ㅏ rk . 이는 기본 변수 x가 아르 자형 조건 (3.8)에서는 사라집니다.
엑스 아르 자형 =b 아르 자형 - ㅏ rk 엑스 케이 =b 아르 자형 - ㅏ rk (비 아르 자형 /방주 ) = 0, 1 ??r ??m.
변수 x 아르 자형 기준에서 제외됩니다. 결과적으로 우리는 하나의 기본 좌표와 하나의 비기본 좌표에서 원래 변수와 다른 기본 및 비기본 변수의 새로운 구성을 얻었습니다.
4단계
새로운 기준선은 다음과 같습니다
1= (엑스 1, 엑스 2,…, 0,…, x 중 , 0,…, xk ,0,…, 0),
어디에 x 아르 자형 비용은 0이고 x 에게 > 0.해당 기본 계획은 새로운 기본 매트릭스에 해당합니다.
새로운 꼭지점 x1의 좌표를 찾기 위해 표준 LP 문제는 새로운 선호 형식, 즉 행렬이 항등식(= E)이 되는 형식으로 축소됩니다. 이렇게 하려면 Ak 열을 단위 표현으로 변환해야 합니다.
R번째 라인,
여기서 계수 = 1이고 다른 모든 요소는 =0, i ??r입니다. 이는 시스템 방정식에 대한 기본 연산을 사용하여 달성할 수 있습니다. 어떤 시점에서 모든 추정치가 Dj 3 0이 되면 솔루션이 종료됩니다.
3. 예제를 이용한 심플렉스 방식 구현
2장의 예를 사용하여 심플렉스 방법의 적용을 보여드리겠습니다.
표준 LP 문제를 고려하십시오.
에프(엑스) = 엑스 1+ 2배 2 +0x 3 +0x 4최대(3.11)-x 1+ 2배 2+x 3= 4,(3.12)3 x 1 +2배 2+x 4= 12,(3.13)x 제이? 0, j = 1,2,3,4.(3.14)
조건 행렬 A = (A 1, ㅏ 2, ㅏ 3, 에이 4), 어디
대상 벡터 c =(c1, c2, c3, c4)=(1, 2, 0, 0); 우변의 벡터 b=(b1, b2) = (4, 12).
0단계.시작 모서리 지점(기준선) 찾기.
방정식의 우변이 양수이고 조건 A3, A4 행렬의 열이 단위 부분행렬을 형성하므로 문제는 바람직한 형태를 갖습니다. 이는 초기 기본 행렬 = (A3, A4)를 의미합니다. x3과 x4는 기본 변수이고, x1과 x2는 비기본 변수이며, cB = (c3, c4) = (0, 0)입니다.
초기 기준선은 다음과 같습니다.
x0 = (0, 0, x3, x4) = (0, 0, 4, 12); f(xo) = 0.
1단계.최적의 기본계획을 확인합니다.
공식 (3.6)을 사용하여 기본이 아닌 변수에 대한 단순 추정을 계산해 보겠습니다.
D1 =< cБ, A1 >- c1 = 0 ·(-1) + 0 ·3 - 1 = -1.
D2 =< cБ, A2 >- c2 = 0 · 2 + 0 · 2 - 2 = -2.
추정치는 음수이므로 계획 xo는 최적이 아닙니다. 우리는 목적함수 값이 더 큰 새로운 기준선(인접한 꼭지점)을 찾을 것입니다.
2 단계. 베이시스에 도입된 변수를 찾습니다.
기본 변수가 아닌 x1 또는 x2 중 하나가 기본 변수에 포함되면(양수로 설정됨) 두 추정 모두 Dj를 추정하므로 목적 함수가 증가할 수 있습니다.< 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x2.
3단계.기저에서 파생된 변수의 정의입니다.
변수 x2를 베이시스에 입력하면 새 계획의 형식은 1 = (0, x2, x3, x4)가 됩니다.
이 계획은 하나의 0 좌표만 포함하므로 기본 계획이 아닙니다. 즉, 변수 x3 또는 x4 중 하나를 0으로 만들어야 함을 의미합니다(기본에서 제외).
계획 좌표 x1 = (0, x2, x3, x4)를 문제 제약 조건으로 대체해 보겠습니다. 우리는 얻는다
여기서부터 기본 변수 x3과 x4를 기저에 도입된 변수 x2를 통해 표현해 보겠습니다.
엑스 3= 4 - 2x 2,(3.15)x 4= 12 - 2x2 .(3.16)
그래서 변수 x 3그리고 x 4 음수가 아니어야 하며, 불평등 시스템을 얻습니다.
4~2배 2 ³ 0 ,(3.17)12 - 2x 2 ³ 0 .(3.18)
x 값이 클수록 2, 목적함수는 증가한다. 문제의 제약조건, 즉 조건 (3.17), (3.18)을 만족하지 않는 새로운 기저변수의 최대값을 찾아보자.
부등식을 다음 형식으로 다시 작성해 보겠습니다.
x2 £ 4,
x2 £ 12,
x의 최대값은 어디에 있나요? 2= min (4/2, 12/2) = 2. 이 값을 x에 대한 식 (3.15), (3.16)으로 대체 3그리고 x 4, 우리는 x를 얻습니다 3= 0. 따라서 x 3 기초에서 파생된 .
4단계새 기준선의 좌표를 결정합니다.
새 기준선(인접 모서리 점)은 다음과 같습니다.
엑스 1= (0, x2, 0.x 4).
이 점의 기초는 A2와 A4 열로 구성되므로 = (A2, A4)입니다. 벡터 A2 = (2, 2)이므로 문제 (3.11) - (3.14)는 새로운 기저와 관련하여 선호되는 형식을 갖지 않기 때문에 이 기저가 단일 기저가 아니라는 점에 유의하십시오. 문제 (3.12), (3.13)의 조건을 변환하여 새로운 기본 변수 x2, x4에 대해 선호되는 형식을 취하도록, 즉 변수 x2가 계수가 있는 첫 번째 방정식에 포함되도록 합시다. 1과 같고 두 번째 방정식에는 존재하지 않습니다. 문제의 방정식을 다시 써보자
x1+ 2x2+ x3 = 4, (p1)
x1 +2x2 + x4 = 12. (p2)
첫 번째 방정식을 x2의 계수로 나누어 보겠습니다. 우리는 원래 방정식과 동일한 새로운 방정식 = p1 / 2를 얻습니다.
1/2 x1+ x2+ 1/2 x3 = 2. ()
우리는 해결이라고 부르는 이 방정식을 사용하여 두 번째 방정식에서 변수 x2를 제거합니다. 이렇게 하려면 방정식에 2를 곱하고 이를 p2에서 빼야 합니다. 방정식 = p2 - 2 = p2 - p1을 얻습니다.
x1 - x3 + x4 = 8. ()
결과적으로 우리는 새로운 기본 변수 x2, x4와 관련하여 원래 문제(3.11) - (3.14)의 새로운 "선호" 표현을 얻었습니다.
f(x) = x1+ 2x2 + 0 x3 + 0 x4® 최대
1/2 x1+ x2+ 1/2 x3 = 2. ()
x1 - x3 + x4 = 8. ()
xj ³ 0, j = 1,2,3,4.
여기에 새로운 기본 계획 x1 = (0, x2,0, x4)의 표현을 대입하면 기본 변수의 값이 방정식의 오른쪽과 동일하므로 좌표를 즉시 찾을 수 있습니다.
x1 = (0,2,0,8); f(x1)=4.
이것으로 심플렉스 방법의 첫 번째 반복이 완료됩니다. 다음으로, 문제 해결 프로세스는 1단계부터 계속됩니다. 이는 발견된 계획의 최적성을 확인하는 것으로 구성됩니다. 현재 기본 계획의 모든 단순 추정이 음수가 아닌 것으로 판명되면 솔루션이 종료됩니다.
단순 방법의 모든 계산을 표 형식으로 수행하는 것이 더 편리하기 때문에 첫 번째 계획에 따라 두 번째 반복을 수행하지 않습니다.
단순 변수 표준 프로그래밍
문학
1. 계량경제학: 교과서/Ed. I.I. Eliseeva. - M .: 금융 및 통계, 2002. - 344 p .: 아픈.
계량경제학 워크숍: Proc. 수당 / I.I. 엘리세바, S.V. 쿠리셰바, N.M. Gordeenko 및 기타; 에드. I.I. Eliseeva. - M .: 금융 및 통계, 2002. - 192 p .: 아픈.
Kremer N.Sh., Putko B.A. 계량경제학: 대학 교과서. -M .: UNITY-DANA, 2002. - 311 p.
Magnus Y.R., Katyshev P.K., Peresetsky A.A. 계량 경제학. 시작 과정: 교과서. -M .: Delo, 2001. - 400p.
Katyshev P.K., Magnus Y.R., Peresetsky A.A. 계량경제학 기초과정의 문제집입니다. - 3판, 개정판. -M .: Delo, 2003. - 208p.
Dougherty K. 계량경제학 입문. - M.: 재무 및 통계, 1999.
Johnston J. 계량경제학적 방법. - M .: 통계, 1980.
케인 E. 경제 통계 및 계량 경제학. 정량적 경제 분석 소개. Vol. 1. - M .: 통계, 1977.
Lange O. 계량경제학 소개 / Transl. 폴란드 출신 - M .: 진행, 1964.
Lizer S. 계량 경제학 방법 및 문제. - M .: 통계, 1971.
Malenvo E. 계량경제학의 통계적 방법. - M .: 통계, 1976.
Tintner G. 계량 경제학 소개. - M.: 금융 및 통계, 1965.
Ayvazyan S.A., Mkhitaryan V.S. 응용통계 및 계량경제학의 기초: 대학 교과서. -M .: UNITY, 1998.
벤젤 E.S. 확률 이론: 대학 교과서. - 6판. -M .: 더 높습니다. 학교, 1999.
2. 자연 기본 변수의 도입. 심플렉스 테이블의 구성. 제로 계획의 정의.
단순 방법. 단순 방법의 알고리즘.
단순법- 다차원 공간에서 볼록 다면체의 꼭지점을 열거하여 선형 계획법의 최적화 문제를 해결하기 위한 알고리즘입니다. 이 방법은 1947년 미국 수학자 조지 댄지그(George Danzig)가 개발했습니다.
단순 방법의 아이디어는 제기된 설명 문제를 수학적 형식으로 변환한다는 것입니다. 문제의 수학적 공식에는 원하는 결과를 나타내는 목적 함수의 방정식이 포함됩니다. 목적 함수의 최소값 또는 최대값을 결정합니다. 등식 또는 부등식으로 지정된 선형 제약 조건 시스템. 결과 수학적 설명은 행렬 형식으로 축소됩니다. 그런 다음 문제에 대한 매트릭스 설명이 표준 형식으로 축소됩니다. 선형 방정식 시스템이 표준 형식으로 축소된 후 선형 프로그래밍 문제를 해결하기 시작합니다. 이 문제를 해결하기 위한 알고리즘은 일련의 행렬 구성으로 구성됩니다. 솔루션의 각 단계를 통해 원하는 결과를 얻는 데 더 가까워질 수 있습니다.
단순 방법의 계산 체계에서는 허용 가능한 초기 모서리 지점(일반적으로 원점)에서 시작하여 최적의 솔루션에 해당하는 지점이 될 때까지 허용 가능한 한 극단 지점에서 다른 지점으로 연속적인 전환이 이루어지는 정렬된 프로세스가 구현됩니다. 설립하다.
심플렉스 방법 알고리즘
1. 제한 시스템을 정식 형식으로 가져옵니다(시스템이 제한되는 경우). 또한 시스템에서 단일 기반을 식별할 수 있습니다.
2. 원본 찾기 참고 계획(KZLP 방정식 시스템의 음이 아닌 기본 해). 각각의 참조 계획은 주어진 n 벡터 시스템에 포함된 m 선형 독립 벡터 시스템에 의해 결정됩니다. ㅏ 1 , ㅏ 2 ,…, 앤. 주어진 문제에 포함된 참조 계획 수의 상한은 조합 수에 따라 결정됩니다. nm로);
3. 우리는 짓는다 단순한 테이블 (단순한 테이블단순 방법을 사용하여 문제를 풀 때 (비퇴화) 선형 계획법 문제에 대해 허용되는 기본 해를 열거하는 수단으로 사용되는 행렬입니다. 이는 표준 형식으로 축소된 선형 프로그래밍 방정식 시스템의 계수 행렬로 구성됩니다. 소위 단순 알고리즘에 따른 순차적 변환을 통해 원하는 결과를 얻기 위해 제한된 수의 단계(반복)가 가능합니다. 목적 함수의 극단값).
4. 심플렉스 테이블에서 벡터의 부정성을 확인합니다. 평가 Zj - Сj줄에 쓰여진 내용은 0 이하(최소)여야 합니다. Zj – Сj ≥ 0(최대). 추정값이 최적성 조건을 만족하면 문제가 해결됩니다.
5. 일부 벡터의 경우 최적 조건을 위반하는 경우 다음에 해당하는 벡터를 기본에 도입해야 합니다.
최대[θ 0 j (Zj – Сj)] ; 최소[θ 0 j (Zj – Сj)] ; θ 0 j = 최소, 어디 x 나는> 0
벡터 요소 θj해당 θ0j허용적이라고 함; 해당 행과 열을 가이드라고 합니다. 가이드 행의 벡터는 기본을 따릅니다.
6. 새로운 기저의 모든 벡터에 대한 확장계수를 구해봅시다. 지오다노 가우스법을 적용해보자
최적의 참고플랜을 확인해보겠습니다. 추정값이 최적성 조건을 만족하면 문제가 해결되고, 그렇지 않으면 5~7단계가 수행됩니다.
2. 자연 기본 변수의 도입. 심플렉스 테이블의 구성. 제로 계획의 정의.
단순 방법은 복잡한 문제를 해결하는 데 가장 효과적이며 다음으로 시작하는 반복적인(단계별) 프로세스를 나타냅니다. 영(참조) 솔루션 (정점 N-차원 다면체). 다음으로 최적의 계획을 찾기 위해 목적함수의 값이 최대(최소)값에 도달할 때까지 꼭지점(다면체의 꼭지점)을 따라 이동한다고 가정한다. 제한된 원자재 자원을 사용하는 회전율 계획 문제의 예를 사용하여 단순 방법의 알고리즘을 고려해 보겠습니다.
회사에서 판매합니다 N제품 그룹, 보유 중제한된 물질적, 금전적 자원 비나는 ≥0 (1 ≤ 나≤m) . 모든 사람의 자원 비용이 알려져 있습니다. 나- 매트릭스 형태로 표시되는 각 그룹의 상품 단위 생산 및 판매 유형 ( ㅏ ij) 기업이 상품 단위 판매로 얻은 이익 제이- 목적 함수에 포함된 그룹 지(엑스). 선형 프로그래밍 방법은 시스템 (1) - (2)와 다르지 않습니다.
Z(X) = с 1 Х 1 + с 2 Х 2 + с 3 Х 3 + … +с n Х n →max(최소) (1)
a 11 X 1 + a 12 X 2 +…a 1n X n ≤ b 1,
a 21 X 1 + a 22 X 2 +…a 2n X n ≤ b 2 (2)
a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,
X 1 ≥0 X 2 ≥0 X 3 ≥0 … X n ≥0
단순 방법을 사용하여 문제를 해결하는 단계는 다음과 같습니다.
1) 제로 참조 계획을 작성합니다. 불평등 시스템(2)이 방정식 시스템이 되는 덕분에 새로운 음이 아닌(기본) 변수를 도입합니다.
a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1
a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)
……………………………………..
a m1 X 1 + a m2 X 2 +… a mn X n + X n+m = b m,
입력 변수를 열 벡터로 사용하면 다음을 나타냅니다. 하나의 (기초적인) 벡터. 기본 변수는 단순한 물리적 의미를 가집니다. 나머지주어진 생산 계획에 대한 창고의 특정 자원이므로 이 기준을 호출합니다. 자연스러운. 기본 변수와 관련하여 시스템 (3)을 해결합니다.
Xn+1 = b 1, -a 11 X 1 - a 12 X 2 -…a 1n X n
X n+2 = b 2 - a 21 X 1 - a 22 X 2 -…a 2n X n (4)
………………………………………..
X n+m = b m, - a m1 X 1 + a m2 X 2 +… a mn X n
목적 함수를 다음 형식으로 다시 작성합니다.
지(X) = 0-(-с 1 Х 1 -с 2 Х 2 -с 3 Х 3 -…-с n Х n) (5)
필요한 주요 변수 X 1 = X 2 = X 3 = ... = X n = 0이라고 가정하면 제로 참조 계획 X = (0, 0, ...0, b 1, b 2, b 3)을 얻습니다. ... b m), Z(X) = 0(모든 자원이 재고로 있고 아무것도 생산되지 않음)입니다. 우리는 단순 테이블에 계획을 입력합니다.
| 계획 | 기초 | C i /C j | 의미 X 나는 | × 1 | X 2 | Xn | Xn+1 | Xn+2 | Xn+ 3 | Q분 |
| Xn+1 | 비 1 | 11 | 12 | 13 | ㄴ 1/아 12 | |||||
| Xn+2 | 비 2 | 21 | 22 | 23 | ㄴ 2 / ㄱ 22 | |||||
| Xn+3 | 비 3 | 31 | 32 | 33 | ㄴ 3 / ㄴ 32 | |||||
| Z(X) = 0 | -C 1 | - C 2 | - C 3 | 색인. 선 |
2) 인덱스 라인의 음수 계수에서 절대값에서 가장 큰 값을 선택합니다. 이는 선행 열을 결정하고 다음 반복(단계)에서 어떤 변수가 기본(자유)에서 기본(실제로는 매출이 가장 높은 상품군을 선택합니다.) 그런 다음 원자재 비축량을 해당 비용 계수로 나누고 결과를 표에 입력하고 최소값 Q min을 결정합니다(선택한 제품 그룹의 생산량을 가장 크게 제한하는 매장량의 자원이 선택됨). 이 값은 선행 라인과 다음 단계(반복)에서 베이시스를 벗어나 자유로워지는 변수 Xi를 선택합니다.
3) Jordan-Gauss 방법을 사용하여 심플렉스 테이블을 다시 계산한 결과 새로운 계획으로의 전환이 수행됩니다. 먼저, 기저의 X j를 선행 열의 X i로 대체합니다. 선행 라인의 모든 요소를 분해 요소(RE)로 나누면 선행 라인의 RE 위치는 1이 됩니다. X i가 기본이 되었기 때문에 나머지 계수는 0과 같아야 합니다. 이 계획의 새로운 요소는 직사각형 규칙에 따라 발견됩니다.
NE=SE – (A*B)/RE (6)
결과 계획은 인덱스 라인의 계수를 사용하여 평가됩니다. 모두 양수이면 계획이 최적이고, 그렇지 않으면 다음 반복(단계)을 수행하여 계획을 개선할 수 있습니다.
예.생산 현장 장비 구매를 위해 20,000 루블이 할당되었습니다. 장비는 72평방미터를 초과하지 않는 면적에 배치할 수 있습니다. 6평방미터의 생산 면적이 필요하고 6,000개를 제공하는 유형 A의 두 가지 유형의 장비를 주문할 수 있습니다. 교대 당 제품 (가격 5,000 루블) 및 유형 B, 12 평방 미터의 면적이 필요하고 3,000 단위 생산 (가격 2,000 루블). 현장 생산성을 극대화하기 위한 최적의 장비 확보 방안은 무엇입니까?
유형 A와 B의 구매 장비 수량을 각각 X 1과 X 2로 표시하겠습니다.
현장 생산성(목적함수): Z(X) =6Х 1 +3Х 2.
주요 제한사항은 다음과 같습니다.
현금: 5Х 1 +2Х 2 ≤ 20,
생산 현장 면적: 6Х 1 +12Х 2 ≤ 72.
새로운 기본 변수 X 3(장비 구매 후 자금 잔액) 및 X 4(장비 배치 후 공간 잔액)를 도입하고 방정식 시스템 형태로 제한 사항을 다시 작성합니다.
5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)
6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)
이 경우 목표 함수: Z(X) = 6Х 1 +3Х 2 +0Х 3 +0Х 4 .
참조(0번째) 계획을 세웁니다. X = (0, 0, 20, 72), 즉 아직 아무것도 구매하지 않았습니다(돈을 쓰지 않았으며 공간이 비어 있습니다). 단순한 테이블 만들기
| 계획 | 기초 | C i /C j | 의미 X 나는 | × 1 | X 2 | X 3 | X 4 | Q분 | |||
| X 3 | 20/5=4 | ||||||||||
| X 4 | 72/6=12 | ||||||||||
| Z(X) = 0 | - 6 | - 3 | 인덱스 라인 | ||||||||
| →× 1 | 0,4 | 0,2 | 4/0,4=10 | ||||||||
| X 4 | 9,6 | -1,2 | 48/9,6=5 | ||||||||
| Z(X) = 6*4=24 | -0,6 | 1,2 | 인덱스 라인 | ||||||||
| × 1 | 0,25 | -1/24 | - | ||||||||
| →X 2 | -1/8 | 5/48 | - | ||||||||
| Z(X) =6*2+3*5=27 | 9/8 | 1/16 | 인덱스 라인 | ||||||||
당연히 선행 열은 가장 큰 인덱스 6을 가지므로 X 1에 해당합니다. X 3이 기본 변수에서 파생됨을 보여주는 선행 행을 정의하여 Q min = 4(가장 심각한 자원 제약)의 최소값을 찾습니다. , 1 대신 X가 입력됩니다. 선행 선의 요소를 다시 계산하여 5로 나누고 공식 (6)을 사용하여 두 번째 선과 색인 선의 요소를 결정합니다. 첫 번째 계획의 목적 함수는 Z(X) = 6*4+3*0 = 24와 같습니다.
그러나 X 2 열에 대한 인덱스 행의 계수 중 하나는 음수 -0.6으로 유지되므로 이 계획은 최적이 아니며 이를 개선하려면 또 다른 반복(단계)이 필요합니다. 두 번째 열을 선행 열로 선택하고 최소값 Q min = 5를 기준으로 기본 변수 X 4 를 사용하여 선행 행을 결정합니다. 동일한 변환을 수행한 후 모든 지수 계수가 양수이므로 최적의 두 번째 계획을 얻습니다.
얻은 결과를 분석해 보겠습니다. 최적의 솔루션을 사용하면 목적 함수의 최대 값은 27,000루블이고 두 리소스는 모두 기본에서 제거되므로 완전히 소비됩니다.
이것을 확인해 봅시다: 5*2+2*5 = 20,000 루블, 6*2+12*5=72 평방미터. 필요한 해는 X = (2; 5;0;0)입니다. 이것이 항상 발생하는 것은 아닙니다.
10강
주제: 인공 기반 문제에 대한 단순 방법
단순 해법은 단위 행렬을 형성할 수 있는 추가(기본) 변수의 도입을 기반으로 합니다. 문제 제약 조건이 부등식의 형태로 표시되는 경우:
a i1 X 1 + a i2 X 2 +…a in X n ≥ b i (1)
또는 방정식:
a i1 X 1 + a i2 X 2 +…a in X n = b i (1*),
그러면 원하는 형식의 참조 계획을 얻는 것이 불가능합니다. 이 경우 평등(1*)을 준수하기 위해 다음을 도입합니다. 인공적인 기초 와이 i 및 인공 변수는 작업 내용과 직접적인 관련이 없지만 참조(시작) 계획을 구성할 수 있도록 합니다.
a i1 X 1 + a i2 X 2 +…a in X n +Y i = b i (2)
문제를 최대한 해결할 때의 목적 함수는 다음과 같은 형식으로 작성됩니다.
Z(X) =∑C j X j +(-M)∑Y i (3),
최소한 유사한 문제를 해결할 때:
Z(X)=∑C j X j +(M)∑Y i (3*),
여기서 M은 매우 큰 양수로, 인공 변수 사용에 대한 일종의 페널티입니다.
부등식(1)의 경우 처음에 마이너스 기호를 사용하여 추가 변수 Xn + i를 도입합니다. 그들의 행렬은 단일하지 않으므로 시스템의 각 불평등에 (1) 인공 변수 У i를 도입합니다.
a i1 X 1 +a i2 X 2 +…a in X n –X n+i +Y i =b i (4)
이 경우 목적 함수는 Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (최대값 찾기)입니다. 인위적인 기초를 사용하면 단순 방법에 더 큰 유연성이 제공되고 광범위한 문제에 사용할 수 있습니다.
예 . 표에 생산 비용과 제품 단위 판매 수익성이 나와 있는 경우 두 가지 유형의 제품 A와 B 생산에 대한 최대 및 최소 이익 값을 결정합니다. 주요 조건은 기업에서 근로자를 완전 고용하는 것입니다.
수학적으로 생산량 제약은 혼합 시스템의 형태로 작성됩니다.
1X1 + 1X2 ≤ 6,
2X 1 + 1X 2 =8.
첫 번째 부등식에 대한 기본 변수 X 3과 두 번째 방정식에 대한 인공 변수 Y 1을 소개하겠습니다.
1X1 + 1X2 + X3 = 6,
2X1+1X2+Y1=8.
결과 방정식 시스템에서 X 3 및 Y 1을 표현하고 최대값을 결정하기 위해 목적 함수를 상상해 보겠습니다.
Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=
3X 1 + 2X 2 -8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M
참조 계획의 경우 - X=(0,0,6,8). 간단한 테이블을 만들어 보겠습니다.
| 계획 | 기초 | C i /C j | 의미 X 나는 | × 1 | X 2 | X 3 | Y 1 | Q분 |
| X 3 | 6/1=6 | |||||||
| Y 1 | -중 | 8/2=4 | ||||||
| Z(X) = -8M | -2M-3 | -M-2 | 인덱스 라인 | |||||
| X 3 | 0,5 | -0,5 | 2/0,5=4 | |||||
| →× 1 | 0,5 | 0,5 | 4/0,5=8 | |||||
| Z(X) = 3*4=12 | - 0,5 | M+1.5 | 인덱스 라인 | |||||
| →X 2 | -1 | - | ||||||
| × 1 | -1 | - | ||||||
| 지(엑스) =3*2+2*4=14 | M+1 | 인덱스 라인 |
일반적으로 참조 계획의 개선은 기본에서 인공 변수 Y 1을 제거하는 것으로 시작됩니다. 최적의 계획 X = (2,4,0,0)은 두 번째 반복에서 얻어졌으며 최대 수입은 14입니다. 천. 장애. , 인덱스 행의 계수는 음수가 아닙니다. 이 작업에서는 최적의 계획을 통해 리소스가 완전히 사용되는지 쉽게 확인할 수 있습니다(2*1+4*1=6; 2*2+1*4=8).
최소 수익성을 찾을 때 목적함수를 다르게 공식화합니다(+MY 1을 용어로 입력:
Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=
3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M
참조 계획은 동일하지만 심플렉스 테이블의 인덱스 행 계수가 다릅니다. 이전과 마찬가지로 선행 열은 X 1의 절대값에서 가장 큰 양의 계수로 선택되고, 선행 행은 Q min = 4의 최소값으로 결정됩니다. 첫 번째 반복에서 인공 변수 Y 1은 다음에서 파생됩니다. 기초.
| 계획 | 기초 | C i /C j | 의미 X 나는 | × 1 | X 2 | X 3 | Y 1 | Q분 | ||
| X 3 | 6/1=6 | |||||||||
| Y 1 | 중 | 8/2=4 | ||||||||
| Z(X) = 8M | 2M-3 | M-2 | 인덱스 라인 | |||||||
| X 3 | 0,5 | -0,5 | 2/0,5=4 | |||||||
| →× 1 | 0,5 | 0,5 | 4/0,5=8 | |||||||
| Z(X) = 3*4=12 | - 0,5 | -M+1.5 | 인덱스 라인 | |||||||
지수 선 X i에 있는 계수의 음수 값은 첫 번째 계획의 최적성을 나타내며 최소 소득은 12,000루블입니다.
이는 제품 A의 생산량(제품 B가 생산되지 않음)에 의해서만 제공되고 원자재는 완전히 사용되지 않은 반면(나머지 X 3 = 2t) 주요 조건이 충족되는 동안 근로자는 생산에 완전히 고용됩니다.
11강
주제: 폐쇄된 운송 문제
1. 폐쇄형 수송 문제의 수학적 공식화. 필요한 미지의 수를 결정합니다.
2. 교통 문제 해결 계획을 결정하는 단계.
강의 3.심플렉스 테이블. 단순 방법의 알고리즘.
§ 3 단순 방법
3.1. 단순 방법에 대한 일반적인 아이디어. 기하학적 해석
그래픽 방법은 매우 좁은 범위의 선형 프로그래밍 문제에 적용할 수 있습니다. 이 방법은 변수가 2개 이하인 문제를 효과적으로 해결할 수 있습니다. 선형 계획법의 기본 정리가 고려되었으며, 이에 따라 선형 계획법 문제에 최적의 해가 있는 경우 이는 해 다면체의 적어도 하나의 꼭지점에 해당하고 다음의 허용되는 기본 해 중 적어도 하나와 일치합니다. 제약 시스템. 선형 계획법 문제를 해결하는 방법이 제시되었습니다. 즉, 제약 조건 시스템에 대한 실행 가능한 기본 해의 유한한 수를 열거하고 그 중에서 목적 함수가 최적의 해를 만드는 해를 선택하는 것입니다. 기하학적으로 이는 해 다면체의 모든 꼭지점을 열거하는 것과 같습니다. 이러한 철저한 검색은 궁극적으로 최적의 솔루션(존재하는 경우)으로 이어지지만, 실제 문제의 경우 실행 가능한 기본 솔루션의 수가 유한하더라도 매우 클 수 있기 때문에 실제 구현은 엄청난 어려움과 관련됩니다.
검색이 무작위로 수행되지 않고 선형 함수의 변경 사항을 고려하면 검색할 수 있는 허용되는 기본 솔루션의 수를 줄일 수 있습니다. 선형 함수의 값에 따라 다음 솔루션이 이전 솔루션보다 "더 나은"(또는 적어도 "더 나쁘지 않은")지 확인(최대값을 찾을 때 증가, 최소값을 찾을 때 감소) 
).
이 검색을 사용하면 최적을 찾을 때 단계 수를 줄일 수 있습니다. 이를 그래픽 예를 통해 설명하겠습니다.
가능한 해의 영역을 다각형으로 표현하자 에이 비 씨 디이. 그 꼭지점을 가정해보자. ㅏ원래의 실현 가능 기저 솔루션에 해당합니다. 무작위 검색에는 다각형의 5개 꼭지점에 해당하는 5개의 실행 가능한 기본 솔루션을 테스트해야 합니다. 그러나 도면을 보면 상단 이후에 있음이 분명합니다. ㅏ인접한 꼭지점으로 이동하는 것이 유리하다 안에,그리고 최적의 지점으로 와 함께. 5개가 아닌 3개의 꼭지점만 통과하여 선형 함수를 지속적으로 개선했습니다.
솔루션을 성공적으로 개선하려는 아이디어는 선형 프로그래밍 문제를 해결하기 위한 보편적인 방법의 기초를 형성했습니다. 단순 방법 또는 계획의 순차적 개선 방법.
단순 방법의 기하학적 의미는 제약 다면체의 한 꼭지점(초기 정점이라고 함)에서 인접한 정점으로의 순차적 전환으로 구성됩니다. 여기서 선형 함수는 다음과 관련하여 최상의(적어도 최악은 아님) 값을 취합니다. 문제의 목표; 최적의 솔루션을 찾을 때까지 - 목표 함수의 최적 값이 달성되는 정점입니다(문제에 최종 최적이 있는 경우).
단순 방법은 1949년 미국 과학자 J. Danzig에 의해 처음 제안되었지만 1939년에 이 방법의 아이디어는 러시아 과학자 L.V. 칸토로비치.
모든 선형 계획법 문제를 해결할 수 있는 심플렉스 방법은 보편적입니다. 현재는 컴퓨터 계산에 사용되지만 단순법을 사용한 간단한 예제는 수동으로 풀 수 있습니다.
단순 방법(솔루션의 순차적 개선)을 구현하려면 다음을 마스터해야 합니다. 세 가지 주요 요소:
문제에 대한 초기의 실행 가능한 기본 솔루션을 결정하는 방법
최상의(더 정확하게는 나쁘지 않은) 솔루션으로의 전환 규칙
찾은 솔루션의 최적성을 확인하는 기준입니다.
단순법을 사용하려면 선형 계획법 문제를 정규 형식으로 줄여야 합니다. 즉, 제약 조건 시스템은 방정식의 형태로 표현되어야 합니다.
문헌에서는 초기 지원 계획(허용 가능한 초기 기본 솔루션) 찾기, 인공 기반 방법 사용, 최적의 지원 계획 찾기, 심플렉스 테이블을 사용한 문제 해결에 대해 충분히 자세히 설명합니다.
3.2. 단순 방법의 알고리즘.
심플렉스 방법을 사용한 ZLP의 해법을 고려하고 이를 최대화 문제와 관련하여 제시해 보겠습니다.
1. 문제의 조건에 따라 수학적 모델이 컴파일됩니다.
2. 완성된 모델은 표준형식으로 변환됩니다. 이 경우 초기 참조 계획의 기반을 식별할 수 있습니다.
3. 문제의 정식 모델은 모든 자유항이 음수가 아니도록 단순표 형식으로 작성됩니다. 초기 참조 계획이 선택된 경우 5단계로 진행합니다.
심플렉스 테이블(Simplex table): 제약 방정식 시스템과 목적 함수가 초기 기준을 기준으로 해결된 표현식 형식으로 입력됩니다. 목적 함수의 계수를 포함하는 선 
, 라고 불리는 
– 문자열 또는 대상 함수의 문자열.
4. 요소의 부호를 고려하지 않고 최소 단순 관계에 해당하는 양의 분해 요소를 사용하여 단순 변환을 수행하여 초기 참조 계획을 찾습니다. 
-윤곽. 변환 중에 자유항을 제외한 모든 요소가 0인 0행이 나타나면 문제에 대한 제약 방정식 시스템이 일관성이 없습니다. 자유 항 외에 다른 양수 요소가 없는 0행을 만나면 제한 방정식 시스템에는 음수가 아닌 해가 없습니다.
우리는 시스템 (2.55), (2.56)의 축소를 새로운 기반으로 부르겠습니다. 단순 변환 . 단순 변환을 형식적인 대수 연산으로 간주하면 이 연산의 결과로 특정 선형 함수 시스템에 포함된 두 변수 사이에 역할이 재분배된다는 것을 알 수 있습니다. 즉, 한 변수는 종속 변수에서 독립 변수로 바뀌고 다른 변수는 종속 변수로 이동합니다. , 반대로 독립에서 종속으로. 이 연산은 대수학에서 다음과 같이 알려져 있습니다. 조던 제거 단계.
5. 발견된 초기 지원 계획의 최적성을 검사합니다.
a) 만약에 
– 행에 부정적인 요소가 없으면(무료 기간은 계산하지 않음) 계획이 최적입니다. 0이 없으면 최적의 계획은 하나만 있습니다. 0이 하나 이상 있으면 최적 계획의 수는 무한합니다.
b) 만약 c라면 
– 행에 양수가 아닌 요소의 열에 해당하는 음수 요소가 하나 이상 있는 경우 
;
c) 만약에 
– 행에 하나 이상의 음수 요소가 있고 해당 열에 하나 이상의 양수 요소가 있는 경우 최적의 항목에 더 가까운 새 참조 계획으로 이동할 수 있습니다. 이렇게 하려면 지정된 열을 해결 열로 지정하고 최소 단순 비율을 사용하여 해결 행을 찾아 단순 변환을 수행해야 합니다. 결과 참조 계획의 최적성을 다시 검사합니다. 설명된 프로세스는 최적의 계획이 얻어질 때까지 또는 문제의 해결 불가능성이 확립될 때까지 반복됩니다.
기저에 포함된 변수에 대한 계수 열을 해결이라고 합니다. 따라서 음수요소에 의해 기저에 입력된 변수를 선택(또는 해결열을 선택)하는 것입니다. 
-문자열, 증가 기능 제공 
.
기저에서 제외할 변수를 결정하는 것이 조금 더 어렵습니다. 이를 위해 해결 열의 양수 요소에 대한 자유 항의 비율(이러한 관계를 심플렉스라고 함)을 구성하고 그 중에서 가장 작은 것을 찾아 제외된 변수가 포함된 행(해석)을 결정합니다. 최소 단순 관계에 따라 기초에서 제외된 변수의 선택(또는 해결 선의 선택)은 이미 설정된 대로 새 참조 계획에서 기초 구성 요소의 긍정성을 보장합니다.
알고리즘의 3번 항목에서는 자유항 열의 모든 요소가 음수가 아닌 것으로 가정합니다. 이 요구 사항은 필수는 아니지만 충족되면 이후의 모든 단순 변환은 양수 분해 요소로만 수행되므로 계산이 편리합니다. 자유 조건 열에 음수가 있는 경우 해결 요소는 다음과 같이 선택됩니다.
1) 예를 들어 부정적인 자유 용어에 해당하는 라인을 살펴보십시오. 
– 행을 선택하고 그 안의 음수 요소를 선택하면 해당 열이 해결되는 것으로 간주됩니다(문제의 제약 조건이 일관적이라고 가정합니다).
2) 자유 용어 열의 요소와 동일한 부호를 갖는 해결 열의 해당 요소(단순 관계)와의 관계를 구성합니다.
3) 단순 관계 중 가장 작은 관계를 선택합니다. 이에 따라 활성화 문자열이 결정됩니다. 예를 들어, 아르 자형-선;
4) 해결 열과 행의 교차점에서 해결 요소가 발견됩니다. 요소가 허용되는 경우 
–strings, 그러면 단순 변환 후에 이 문자열의 자유 항은 양수가 됩니다. 그렇지 않으면 다음 단계에서 다시 
-선. 문제를 해결할 수 있는 경우 특정 단계를 거친 후에는 자유 용어 열에 부정적인 요소가 남지 않습니다.
특정 실제 생산 상황을 PLP 형식으로 적용하는 경우 이를 표준 형식으로 변환하는 과정에서 모델에 도입해야 하는 추가 변수는 항상 특정 경제적 의미를 갖습니다.