다양한 형태의 ZLP 표기법(일반, 표준, 대칭). 선형 계획법 문제를 해결하기 위한 심플렉스 방법

ax = b 형식의 선형 계획법 문제. 여기서 a는 계수 행렬이고, b는 제약 조건 벡터입니다.
예:

각 LP 문제에서 다음 조건에 따라 변수 값을 구합니다.

• 이 값은 일부 선형 방정식 또는 부등식 시스템을 충족했습니다.
• 이 값에서 목적 함수는 최소값 또는 최대값으로 변경됩니다.

지침. 변수 수와 행 수(제약 조건 수)를 선택합니다. 결과 솔루션은 Word 파일에 저장됩니다.

보편적인 LP 방법 중 하나는 단순 방법이지만 LP 문제가 표준 형식을 갖는 경우 사용할 수 있습니다.

정의. 모든 시스템 제약 조건이 방정식으로만 구성되고(변수의 비음성을 표현하는 부등식 제외) 목적 함수가 최소화되어야 하는 경우 LP 문제는 정식 형식을 갖습니다.
이러한 정규 형식의 LP 문제의 예는 문제 1입니다. 제약 조건 시스템(1)과 목적 함수(2)가 있는 균형 전송 문제입니다.
그러나 대부분의 경제 문제에서 제약 시스템에는 초기에 방정식뿐만 아니라 불평등도 포함되는 경우가 많습니다.

성명.일반적인 LP 문제는 표준 형식으로 축소될 수 있습니다.
일반적인 LP 문제를 정식 형식으로 줄이는 것은 새로운(추가라고 불리는) 변수를 도입함으로써 달성됩니다.
이 문제의 제약 조건 시스템(3)은 4개의 부등식으로 구성됩니다. 추가 변수를 도입하여 와이 1 ≥ 0, 와이 2 ≥ 0, 와이 3 ≥ 0, 와이 4 ≥ 0이면 제한 시스템으로 갈 수 있습니다.

이러한 추가 변수 와이나는 절대적으로 명확한 경제적 의미를 가지고 있습니다. 즉, 사용되지 않은 작업 시간(기계 가동 중지 시간)을 의미합니다. 나-번째 유형).
예를 들어, 첫 번째 유형의 기계가 18시간 동안 작동했다면 x + y = 18이므로 y 1 = 0입니다. 그러나 첫 번째 기계의 작동 시간을 불완전하게 사용할 가능성도 허용합니다. 엑스 + 와이<18. В этом случае 와이 1은 양수 값을 가지며 사용되지 않은 시간 제한으로 간주될 수 있습니다. 예를 들어, 3.3.2 단락에서 이 문제에 대한 해결책을 알면, 엑스 = 12, 와이= 6, 제한 시스템(3.9)으로부터 다음과 같은 결론을 내릴 수 있습니다. 와이 1 = 와이 2 = 와이 3 = 0이고, 와이 4 = 12 – 6 = 6. 즉, 첫 번째, 두 번째, 세 번째 유형의 기계는 작업 시간을 완전히 사용합니다. 그러나 네 번째 시스템은 절반만 로드되어 6시간 동안만 사용되며 최적의 계획에 따라 유휴 상태입니다. 아마도 그러한 결론을 내린 후 기업 책임자는 해당 작업에 다른 작업을 로드하고 이번에 임대하는 등의 작업을 원할 것입니다.
따라서 추가 변수를 도입함으로써 방정식에 대한 부등식 유형 제약 조건을 줄일 수 있습니다.

혼합 문제를 생각해 봅시다. 제한 시스템의 형식은 다음과 같습니다.
불평등은 "더 많은" 방향으로 바뀌었으므로 추가 변수 y 1, y 2, y 3 ≥ 0을 도입하여 오른쪽과 균등화하려면 왼쪽에서 빼야 합니다. 우리는 정식 형식의 제한 시스템을 얻습니다.
변수 y i 도 경제적으로 의미가 있습니다. 문제의 실제 내용을 기억한다면 변수 y 1은 혼합물에서 과잉 물질 A의 양을 의미하고, y 2는 과잉 물질의 양을 의미합니다. 안에혼합물에 와이 3 – 잉여 와 함께혼합물에.
목적 함수의 최대값을 찾는 작업은 함수의 최소값을 찾는 것으로 축소될 수 있습니다. 에프 max F = –min (– F) 진술의 명확성으로 인해. 사진을보세요 : 어느 시점에서 엑스= 엑스 0 기능 와이= 에프(엑스)가 최대값에 도달하면 기능이 수행됩니다. 와이= –에프(엑스), 축을 기준으로 대칭 황소, 같은 시점에 엑스 0은 최소값에 도달하며, 에프최대 = - (- 에프분) 시간 엑스 = 엑스 0 .

결론. LP 문제를 정식 형식으로 표현하려면 다음이 필요합니다.

• 추가 변수를 도입하여 문제의 제약 시스템에 포함된 불평등을 방정식으로 변환합니다.
• 목적 함수인 경우 에프→max(최대화), 이는 다음 함수로 대체됩니다. 에프→ min (최소화됨)

일반적인 경우 선형 계획법 문제는 제약 조건이 방정식과 부등식이고 변수가 음수가 아니거나 임의로 변할 수 있는 방식으로 작성됩니다. 모든 제약 조건이 방정식이고 모든 변수가 비음수 조건을 충족하는 경우 선형 계획법 문제를 정규 문제라고 합니다. 좌표, 벡터 또는 행렬 표기법으로 표시할 수 있습니다.

1. 좌표 표기법의 표준 선형 계획법 문제는 다음과 같은 형식을 갖습니다.

.

보다 간결한 형식으로 이 문제는 합계 기호를 사용하여 작성할 수 있습니다.

(1.7)

2. 벡터 표기법의 표준 선형 계획법 문제는 다음과 같은 형식을 갖습니다.

(1.8)

어디 ,

.

3. 행렬 표기법의 표준 선형 계획법 문제는 다음과 같은 형식을 갖습니다.

(1.9)

, .

여기 ㅏ– 방정식 시스템의 계수 행렬, 엑스– 작업 변수의 행렬 열 – 제약 시스템의 오른쪽 행렬 열.

선형 계획법 문제가 자주 사용됩니다. 대칭, 이는 행렬 표기법에서 다음과 같은 형식을 갖습니다.

(1.10)

(1.11)

1.4. 일반적인 선형 계획법 문제의 감소
정식 형식으로

선형 계획법 문제를 해결하기 위한 대부분의 방법에서 제약 조건 시스템은 변수의 비음수에 대한 방정식과 자연 조건으로 구성되어 있다고 가정합니다. 그러나 경제문제의 수학적 모형을 작성할 때 제약조건은 주로 불평등계로 형성되기 때문에 불평등계에서 방정식계로 이동할 수 있는 능력이 필요하다. 이를 위해 우리는 다음 정리를 증명합니다.

정리 1.1.부등식을 방정식으로 바꾸는 방법. 모든 결정 불평등

방정식의 고유한 해에 해당합니다.

불평등

, (1.14)

반대로 방정식(1.13)과 부등식(1.14)에 대한 각 해는 불평등(1.12)에 대한 고유한 해에 해당합니다.

증거.허락하다 는 불평등(1.12)에 대한 해법이고, 그러면 . 이 부등식의 오른쪽과 왼쪽 사이의 차이를 다음과 같이 표시해 보겠습니다.

확실히 . 변수 대신에 방정식 (1.13)에 값을 대입해 보겠습니다. , 우리는 얻는다

따라서 식(1.13)과 부등식(1.14)을 만족한다. 이는 정리의 첫 번째 부분이 입증되었음을 의미합니다.

이제 방정식 (1.13)과 부등식 (1.14)을 만족시키자.

그리고

마지막 평등의 왼쪽에 있는 음수가 아닌 값을 버리면, 우리는 다음을 얻습니다.

즉. 불평등(1.12)을 충족합니다. 정리가 입증되었습니다.

부등호가 이면 음수가 아닌 추가 변수를 빼기 기호를 사용하여 왼쪽에 도입해야 합니다. 즉,

방정식으로 변환하기 위해 부등식 제약 조건에 도입된 음이 아닌 변수를 호출합니다. 추가 변수. 계수가 0인 목적 함수에 추가 변수가 도입되므로 해당 값에 영향을 주지 않습니다.

문제에 임의로 변경되는 변수가 있는 경우 이러한 변수는 음수가 아닌 두 변수의 차이로 대체됩니다. , 어디 그리고 .

때로는 최소값을 찾는 것에서 최대값을 찾는 것으로 또는 그 반대로 문제를 이동해야 하는 경우도 있습니다. 이렇게 하려면 목적 함수의 모든 계수의 부호를 반대의 부호로 변경하고 그렇지 않으면 문제를 변경하지 않고 그대로 두는 것으로 충분합니다. 이렇게 얻은 최대 문제와 최소 문제의 최적해는 일치하며, 최적해에 대한 목적 함수의 값은 부호만 다릅니다.

예제 1.1.선형 계획법 문제를 정식 형식으로 가져옵니다.

해결책. 목적 함수의 최대값을 찾는 문제로 넘어가겠습니다. 이를 위해 목적 함수 계수의 부호를 변경합니다. 제약 조건 시스템의 두 번째 및 세 번째 부등식을 방정식으로 변환하기 위해 음이 아닌 추가 변수를 도입합니다(수학적 모델에서 이 연산은 문자 D로 표시됨). 변수는 부등식의 형식이 이기 때문에 "+" 기호를 사용하여 두 번째 부등식의 왼쪽에 도입됩니다. 변수는 부등식의 형식이 이기 때문에 "-" 기호를 사용하여 세 번째 부등식의 왼쪽에 도입됩니다. 변수는 계수가 0인 목적 함수에 도입됩니다. 비음성 조건이 부과되지 않은 변수는 차이로 대체됩니다. , . 문제를 정식 형식으로 작성합니다.

어떤 경우에는 표준 문제를 대칭 문제로 축소해야 할 필요가 있습니다. 예를 살펴보겠습니다.

예제 1.2.선형 계획법 문제를 대칭 형태로 가져오기

선형 계획법 문제를 해결하기 위한 분석 방법은 다음과 같습니다. 단순 방법.이를 적용하려면 다양한 방식으로 제시된 LP 문제를 표준 형식으로 줄여야 합니다. (2.1.1)~(2.1.3) 형식으로 작성된 선형 계획법 문제는 일반 선형 계획법 문제(GLP) 작성을 확장한 형태입니다.

다음 문제를 표준 선형 프로그래밍 문제(CLPT)라고 부릅니다.

평등의 형태로 제한을 받는 경우,

(2.3.1)-(2.3.4) 형식의 문제에 대해 조건이 만족되는 경우 티 = 엔,그러면 그 해는 방정식 시스템을 푸는 것으로 줄어듭니다.

• (2.3.2) . 이 경우, 다음과 같은 조건이라면 문제에 대한 해결책이 없습니다.
• (2.3.3)이 만족되지 않거나 연립방정식에 해가 없습니다.

상태 티

• 1. 가다 최대화 문제에서목적 함수(2.3.1) 최소화 문제충분한 모든 계수 Cj를 취함목적함수 역방향 기호가 있는결과 문제를 최대한 해결하십시오. 최대값을 찾은 후에는 목적함수의 값을 반대 부호로 가져와야 합니다. 최적의 솔루션은 동일하게 유지됩니다.
• 2. 가다 작거나 같음에서 동등 제약 조건그것은 필요하다 더하기 기호가 있는 경우:

3. 가다 "크거나 같음" 제약 조건에서 같음 제약 조건으로그것은 필요하다 음이 아닌 변수를 추가로 도입빼기 기호가 있는 경우:

이 경우 각 부등식은 자신만의 부등식을 도입합니다. (n +/)번째 추가 변수입니다.

• 4. 모든 것 음의 자유 조건을 갖는 평등은 다음과 같이 나뉩니다.-1, 조건 (2.3.4)이 만족되기 위해서는.
• 5. 어떤 변수에 있는 경우 Xj 부정성이 아닌 조건이 부과되지 않습니다., 저것 변수 Xj=x"를 변경합니다.- 엑스" x"j > 0, x"> 0. 변환된 문제에서 모든 변수는 음수가 아닙니다.

모든 ZLP를 표준 형식으로 축소할 수 있다는 설명이 있습니다.

예 2.3.1. 예제 2.2.2에 주어진 문제를 정식 형식으로 변환해 보겠습니다. 목적 함수와 제약 조건 시스템은 다음과 같습니다.

첫 번째 부등식에 더하기 기호가 있는 추가 변수 jc 3 > 0을 도입하고 두 번째 부등식에 추가하겠습니다. 4개> 빼기 기호가 있는 0 및 세 번째 x 5> 0에는 더하기 기호도 포함됩니다. 결과적으로 우리는 정식 형식의 문제 제약 조건 시스템을 얻습니다.

이러한 제한 사항을 고려하여 함수의 최대값을 찾아야 합니다.

자원의 최적 사용이라는 표준 문제에서 추가 변수의 경제적 의미를 고려해 보겠습니다.

예제 2.3.2. 최적의 자원 활용 문제(카펫 문제)[17J.

공장은 노동력(80인일), 원자재(480kg), 장비(130시간)의 세 가지 유형의 특정 양의 자원을 처분할 수 있습니다. 이 공장에서는 네 가지 유형의 카펫을 생산할 수 있습니다. 각 유형의 카펫 하나를 생산하는 데 필요한 각 자원의 단위 수와 각 제품 유형의 단위에서 기업이받는 수입에 대한 정보가 표에 나와 있습니다. 2.3.1.

총비용이 최대가 되는 생산계획을 찾는 것이 필요하다.

문제의 경제적, 수학적 모델 변수: x x, x 2, x 3, x 4 -각 유형의 카펫 수. 목적 함수 -최대화해야 하는 총 생산 비용은 다음과 같습니다.

자원 제한:

추가 변수 x 5를 도입하여 문제를 정식 형식으로 가져오겠습니다. x 6그리고 x 7:

최적의 생산 계획은 벡터임이 아래에 표시됩니다. X* =(0; 30; 10; 0), 목적 함수의 값은 150입니다. 즉, 총 생산 비용을 극대화하려면 두 번째 유형의 카펫 30개와 세 번째 유형의 카펫 10개를 생산해야 합니다. 최적의 벡터 값을 대체하자 엑스 KZLP의 제한사항:

우리는 "노동"과 "장비" 자원이 완전히 사용되었으며 "원자재" 자원이 풍부하게 사용 가능하다는 사실을 얻었습니다.

이 경우 x in 200kg의 원자재가 남아 있음을 보여줍니다.

그래서 주요 변수는 x v x 2, x 3, x l각 유형의 카펫 수와 추가 변수를 의미합니다. x 5, x 6 7 -활용도가 낮은 리소스의 양.

답변. 최적의 생산 계획 X* = (0; 30;

10; 0).

계획, 또는 수용 가능한 솔루션, KZLP를 벡터라고 합니다. 엑스 =(제이씨 피 엑스 2 ,..., xn), 조건 (2.3.2)-(2.3.4)을 만족합니다.

CLLP 제약 조건 시스템의 기본 솔루션의 모든 구성 요소가 음수가 아닌 경우 이러한 솔루션을 호출합니다. 참조 솔루션또는 참고 계획.참조 계획의 긍정적 구성 요소 수는 다음을 초과할 수 없습니다. 티.

참조 계획은 다음과 같습니다. 비퇴화,만약 그것이 포함되어 있다면 티긍정적인 구성요소, 그렇지 않으면 호출됩니다. 퇴화하다.

최적의 계획또는 최적의 솔루션계획은 선형함수(2.3.1)의 가장 큰(최소) 값을 전달하는 계획이라고 합니다.

PAP의 모든 계획 세트(존재하는 경우)는 다음과 같습니다. 볼록한 다면체.해 다면체의 각 꼭지점(극점)은 다음에 해당합니다. 참고 계획(KZLP 방정식 시스템의 음이 아닌 기본 해). 각 참조 계획은 시스템에 의해 결정됩니다. 티 주어진 시스템에 포함된 선형 독립 벡터 피 벡터 D, D,..., p. 최적의 계획이 있다면, 선형함수가 최대(최소) 값에 도달하는 결정다면체의 꼭지점이 있습니다.

최적의 계획을 찾으려면 참조 계획만 검토하면 충분합니다. 문제에 포함된 참조 계획 수의 상한은 조합 수에 따라 결정됩니다. 시작 (1.4항 참조)

예제 2.3.3.제한된 자원을 최적으로 사용하는 문제에 대한 솔루션을 얻습니다(ZL P 해결).

해결책. 추가 변수를 도입하여 문제를 정식 형식으로 가져오겠습니다. x 3, x4 및 x5:

이 KZLP 제한 시스템의 모든 지원 계획을 찾아보겠습니다(l? - 5; /77 - 3). 그 수는 10을 초과하지 않습니다.

Jordan-Gauss 방법(문단 1.4 참조)을 사용하여 방정식 시스템의 모든 기본 해를 작성합니다(표 2.3.2).

10가지 기본 솔루션 중에는 5가지 기본 솔루션이 있습니다.

그림에 표시된 참조 계획은 다음과 같습니다. 2.3.1은 각각 다음 코너 포인트와 그 안의 CF 값에 해당합니다.

쌀. 2.3.1.

이론에 따르면 LP 최적 솔루션은 레퍼런스 플랜에 포함되어 있습니다.

따라서 2300과 같은 최대값은 해당 지점의 목적 함수에 의해 도달됩니다. 안에 참고 계획에 엑스 5 = (70; 80; 0; 60; 0).

답변.최적의 작업 계획: x ( = 70, x 2 = 80, 목적 함수 값 f(x v x 2) = 2300.

다양한 선형 계획법 문제에서 목적 함수와 제약 조건 시스템을 기록하는 것은 동일하지 않습니다. 일부 문제에서는 목적 함수의 최소값을 찾아야 하고 다른 문제에서는 최대값을 찾아야 합니다. 어떤 경우에는 검색된 변수가 하나의 인덱스에 의존하고 다른 경우에는 두 개의 인덱스에 의존합니다. 일부 문제에서는 제약 조건이 선형 부등식 시스템의 형태로 지정되고 다른 문제에서는 선형 방정식 시스템의 형태로 지정됩니다. 실제로 제약 조건 중 일부는 선형 부등식의 형태이고 일부는 선형 방정식의 형태인 문제가 발생할 수도 있습니다. 또한 모든 문제에 음수가 아닌 변수가 필요한 것은 아닙니다.

이러한 다양한 선형 계획법 문제를 고려하려면 개별 클래스를 해결하기 위한 특별한 방법을 개발해야 합니다. 우리는 소위 표준 형식으로 작성된 선형 계획법의 일반적인 속성과 방법을 연구하는 데 중점을 둘 것입니다.

선형 계획법 문제에서 초기 제약 조건 시스템은 다음과 같은 방정식의 형태를 취합니다.

선형 목적 함수의 최대값을 찾아야 합니다.

그러면 선형 계획법 문제는 정식 형식으로 작성된 것으로 간주됩니다.

모든 선형 프로그래밍 문제는 쉽게 표준 형식으로 축소될 수 있습니다. 일반적인 경우, 이를 위해서는 첫째로 목적 함수를 최소화하는 문제를 최대화하는 문제로 줄이고, 둘째로 부등식 제약 조건에서 등식 제약 조건으로 이동하고, 세 번째로 해당 변수를 변경할 수 있으면 충분합니다. 비부정성 조건이 적용되지 않습니다.

함수의 최소값을 구해야 하는 경우 , 우리는 함수의 최대값을 찾는 것으로 진행할 수 있습니다 , 다음 진술이 참이기 때문입니다.
.

원래 문제의 부등식 제약 조건은 다음과 같습니다. "는 왼쪽에 음이 아닌 변수를 추가하고 " 형식의 부등식 제약 조건을 추가하여 방정식 제약 조건으로 바뀔 수 있습니다. ” – 왼쪽에서 음이 아닌 추가 변수를 뺍니다.

추가로 도입된 음이 아닌 변수의 수는 원래 제약 조건 시스템의 부등식 수와 항상 동일합니다.

도입된 추가 변수는 매우 구체적인 경제적 의미를 갖습니다. 따라서 원래 선형 계획법 문제의 제약 조건이 생산 자원의 비용과 가용성을 반영하는 경우 추가 변수의 수치 값은 해당 미사용 자원의 양을 나타냅니다.

또한 일부 변수가 있는 경우 음수가 아닌 조건을 따르지 않으면 음수가 아닌 두 개의 변수로 대체되어야 합니다. 그리고 , 수락한
.

예. 다음 선형 최적화 문제를 정식 형식으로 작성합니다. 함수의 최소값을 찾습니다.
제한을 받고 있는

해결책

이 문제에서는 목적 함수의 최소값을 구해야 하며 제약 조건 시스템에는 4개의 부등식이 포함됩니다. 정식 형식으로 작성하려면 부등식 제약 조건에서 방정식 제약 조건으로 이동하고 목적 함수도 변환해야 합니다.

문제의 제약 시스템에 포함된 불평등의 수는 4개이므로 이 전환은 음이 아닌 4개의 추가 변수를 도입하여 수행되어야 합니다. 게다가 두 번째와 네 번째 불평등에는 “ "이므로 왼쪽에 추가 변수를 추가합니다. 첫 번째와 세 번째 불평등에는 "라는 기호가 있습니다. ', 이는 왼쪽에서 추가 변수를 뺀다는 의미입니다.

또한 목적 함수를 변환하여 모든 부호를 반대 방향으로 변경하고 최대값을 찾습니다.

따라서 이 선형 계획법 문제는 다음과 같은 표준 형식으로 작성됩니다.

함수의 최대값 찾기

제한을 받고 있는

페이지 1

문제의 정식 형태는 다음 세 가지 특징으로 특징지어집니다: 1) 방정식 시스템 형태의 동종 제약 시스템; 2) 문제와 관련된 모든 변수에 적용되는 동질적 비음성 조건 및 3) 선형 함수의 최대화. 이 문제에서는 세 가지 기능이 모두 위반됩니다.  

문제의 정식 형태는 다음 세 가지 특징으로 특징지어집니다: 1) 방정식 시스템 형태의 동종 제약 시스템; 2) 문제와 관련된 모든 변수에 적용되는 동질적 비음성 조건 및 3) 선형 함수의 최대화. 이 문제에서는 세 가지 기능이 모두 위반됩니다.  

선형 계획법 문제의 정규 형식은 실현 가능 영역의 초기 꼭지점을 쉽게 찾을 수 있으므로 편리합니다.  

선형 계획법 문제의 표준 형식과 Jordan-Gauss 제거 방법을 고려해 보겠습니다.  

선형 계획법 문제의 표준 형식이 편리한 경우가 많습니다.  

제약 조건 시스템을 선형 계획법 문제의 정식 형식으로 변환할 때 부등식 (12)와 (13)은 등식으로 대체되어야 합니다. 이를 위해 음수가 아닌 변수가 추가로 도입됩니다.  

쌍방향 교환 실수 행렬이 직교 행렬을 사용한 유사성 변환에 의해 문제 1128의 표준 형식으로 동시에 감소됨을 증명하십시오.  

기본적으로 (4) - (5)는 비선형 프로그래밍 문제의 표준 형식으로 간주될 수 있습니다. 일반적으로 비선형 프로그래밍 문제에서는 변수가 정수일 필요가 없습니다.  

문제의 정식 형태는 방정식 시스템 형태의 제약 조건 시스템의 동질성을 특징으로 합니다. 목적함수를 최대화하는 것; 문제와 관련된 모든 변수가 음수가 아닌 조건.  

문제의 정식 형태는 고려 중인 계산 방식에 추가 기능을 추가하지 않습니다.  

먼저 최소 문제의 두 번째 표준 형식을 고려해 보겠습니다.  

Simplex-mete 알고리즘은 두 단계로 나눌 수 있습니다. 첫 번째 단계에서는 변수를 제거하여 기본적인 해결책을 찾습니다. 그것이 발견되면, 우리는 두 번째 단계로 이동하는 문제의 정식 형태를 갖게 됩니다. 두 번째 단계는 제한된 최적해가 있는지 확인하는 것입니다. 존재하는 경우 허용 가능한 기본 솔루션이 결정되고 최적의 솔루션이 선택됩니다.  

문제가 표준 형식으로 해결되면 두 번째 단락에 소개된 작업의 일부만 사용됩니다. 따라서 표준 최소 문제의 경우 3.4.1 단락의 경우만 구현되며 열의 순환 재배치, 수직 경계 영역을 통과하는 열 통과, 구조적 위반 수정 및 일부 잘림 작업만 필요합니다. 대칭적으로는 canonical maximum 문제를 풀 때 3.4.2절의 경우만 구현되며, 문자열의 순환 재배열, 수평 경계 영역을 통과하는 문자열 통과, 구조적 위반 수정, 잘림 작업의 또 다른 부분에 대한 작업은 다음과 같습니다. 필요합니다. 그렇지 않으면 문제의 정식 형식이 추가적인 특이성을 추가하지 않습니다.  

소개의 첫 번째 단락에서는 일반 선형 계획법 문제를 표준 형식 중 하나로 축소할 수 있는 방법을 보여주었습니다. 표준 문제의 경우 최적 조건을 위반하기 위한 두 가지 옵션과 다음 정점에 도달하기 위한 두 가지 옵션을 고려할 필요가 없기 때문에 순차적 개선 방법에 대한 설명이 형식적으로 단순화됩니다. 그러나 이로 인해 기저 행렬 A의 크기가 증가합니다. /, J ], 이는 주로 복잡성을 결정합니다. 그러나 많은 경우 문제의 표준 형식에 이 방법을 적용하는 것이 더 바람직한 것으로 나타났으며, 이 섹션에서는 특정 선형에 대해 얻은 방법의 변형에 대해 설명합니다. 프로그래밍 문제.  

페이지:      1