심플렉스 방법을 사용하여 다음 문제를 해결하세요. 선형 프로그래밍 문제를 해결하기 위한 서비스입니다. 단순 방법을 사용하여 문제 해결

단순법을 사용하여 문제를 해결하는 예와 쌍대 문제를 해결하는 예를 고려합니다.

콘텐츠

작업

세 가지 상품 그룹을 판매하기 위해 상업 기업은 b 1 = 240, b 2 = 200, b 3 = 160 단위의 세 가지 유형의 제한된 재료 및 금전적 자원을 보유합니다. 동시에 1,000 루블에 1 개의 상품 그룹을 판매합니다. 상품 회전율, 첫 번째 유형의 자원은 11 = 2 단위, 두 번째 유형의 자원은 21 = 4 단위, 세 번째 유형의 자원은 31 = 4개 단위. 1,000루블에 2개 및 3개의 상품 그룹을 판매합니다. 회전율은 12 = 3, 13 = 6 단위의 첫 번째 유형 자원, 22 = 2, 23 = 4 단위의 두 번째 유형 자원, 자원에 따라 소비됩니다. 세 번째 유형은 a 32 = 6, a 33 = 8 단위입니다. 1,000루블에 세 가지 상품 그룹을 판매하여 이익을 얻습니다. 매출액은 각각 c 1 = 4, c 2 = 5, c 3 = 4 (천 루블)입니다. 무역 기업의 이익이 최대화되도록 계획된 무역 거래 규모와 구조를 결정합니다.

매출 계획의 직접적인 문제에 대해, 심플렉스법으로 해결, 구성하다 이중 문제선형 프로그래밍.
설치하다 변수의 켤레 쌍직접적이고 이중적인 문제.
변수의 켤레 쌍에 따르면 직접 문제의 해로부터 우리는 다음을 얻습니다. 이중 문제의 해결, 그것이 생산되는 곳 자원 평가, 상품 판매에 지출되었습니다.

단순 방법을 사용하여 문제 해결

x 1, x 2, x 3을 각각 1,000 루블, 1, 2, 3 그룹으로 판매된 상품 수로 설정합니다. 그러면 문제의 수학적 모델은 다음과 같은 형식을 갖습니다.

F = 4 x 1 + 5 x 2 + 4 x 3 -> 최대

0)))(~)" title="delim(lbrace)(행렬(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

우리는 단순 방법을 해결합니다.

불평등을 평등으로 변환하기 위해 추가 변수 x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0을 도입합니다.

x 4 = 240을 기본으로 삼아 보겠습니다. x 5 = 200; x 6 = 160.

우리는 데이터를 단순한 테이블

심플렉스 테이블 No.1

목적 함수:

0240 + 0200 + 0160 = 0

다음 공식을 사용하여 추정치를 계산합니다.

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

부정적인 추정치가 있으므로 계획은 최적이 아닙니다. 최저 점수:

변수 x 2를 기본에 도입합니다.

우리는 기초에서 나오는 변수를 정의합니다. 이를 위해 x2 열에 대해 음수가 아닌 가장 작은 비율을 찾습니다.

= 26.667

음수가 아닌 가장 작은 수: Q 3 = 26.667. 우리는 기초로부터 변수 x 6을 도출합니다.

세 번째 줄을 6으로 나눕니다.
첫 번째 줄에서 세 번째 줄을 빼고 3을 곱합니다.
두 번째 줄에서 세 번째 줄을 빼고 2를 곱합니다.


우리는 다음을 계산합니다:

우리는 새로운 테이블을 얻습니다:

심플렉스 테이블 2번

목적 함수:

0160 + 0440/3 + 580/3 = 400/3

다음 공식을 사용하여 추정치를 계산합니다.

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0(-1)/2 + 0(-1)/3 + 5 1/6 - 0 = 5/6

음수 추정치 Δ 1 = - 2/3이 있으므로 이 계획은 최적이 아닙니다.

변수 x 1을 기본에 도입합니다.

우리는 기초에서 나오는 변수를 정의합니다. 이를 위해 열 x 1에 대해 음수가 아닌 가장 작은 비율을 찾습니다.

음수가 아닌 가장 작은 값: Q 3 = 40. 우리는 기저에서 변수 x 2를 도출합니다.

세 번째 줄을 2/3로 나눕니다.
두 번째 줄에서 세 번째 줄을 빼고 8/3을 곱합니다.


우리는 다음을 계산합니다:

우리는 새로운 테이블을 얻습니다:

심플렉스 테이블 No.3

목적 함수:

0160 + 040 + 440 = 160

다음 공식을 사용하여 추정치를 계산합니다.

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0(-1)/2 + 0(-1) + 4 1/4 - 0 = 1

부정적인 평가가 없으므로 계획이 최적입니다.

문제의 해결 방법:

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; 엑스 5 = 40; x6 = 0; F 최대 = 160

즉, 첫 번째 유형의 상품을 40,000 루블로 판매해야합니다. 유형 2와 3의 제품은 판매할 필요가 없습니다. 이 경우 최대 이익은 F max = 160,000 루블입니다.

이중 문제의 해결

이중 문제의 형식은 다음과 같습니다.

Z = 240 y 1 + 200 y 2 + 160 y 3 -> 최소

Title="delim(lbrace)(행렬(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

불평등을 평등으로 변환하기 위해 추가 변수 y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0을 도입합니다.

직접 문제와 쌍대 문제의 변수 쌍은 다음과 같은 형식을 갖습니다.

직접 문제의 마지막 심플렉스 테이블 3번에서 쌍대 문제에 대한 해결책을 찾습니다.

Z 최소 = F 최대 = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Y1 = 0; y2 = 0; 와이 3 = 1; Z 최소 = 160;

단순법- 참조 계획을 순서대로 나열하는 방법입니다(다음 계획으로 이동할 때 목적 함수 값의 단조로운 변화로 순서가 보장됩니다). 이 경우 원칙을 준수해야 합니다. 다음 단계마다 목적 함수의 값이 향상되어야 하며, 극단적인 경우에는 악화되어서는 안 됩니다.

ZLP를 해결하려면 단순 방법이는 정식 형식으로 변환됩니다. 제한 - 불평등 - 제한 - 평등을 만드는 것이 필요합니다. 이를 위해 각 제약 조건에 음수가 아닌 추가 요소가 도입됩니다. 대차대조표 변수부등호가 "£"이면 "+" 기호가 있고 부등호가 "3"이면 "-" 기호가 있습니다.

목적 함수에서 이러한 추가 변수는 계수가 0인 상태로 포함됩니다. 목적 함수의 입력은 변경되지 않습니다. 비음성 조건이 적용되지 않는 각 변수는 음수가 아닌 두 변수의 차이로 표시될 수 있습니다.

작업 제약 조건이 자원의 가용성과 소비를 반영하는 경우 표준 형식으로 작성된 작업 계획의 추가 변수의 수치 값은 사용되지 않은 자원의 양과 같습니다.

Simplex 방법을 사용하여 문제를 해결하기 위해 우리는 다음을 사용할 것입니다. 단축된 선형 연립방정식 단순 표 및 수정된 조던 제거 방법.

1. 첫 번째 참고 계획 수립

작업은 동일하게 유지됩니다. 추가 균형 변수를 도입하여 부등식 시스템(1)의 표준 형식을 방정식 시스템의 표준 형식으로 가져오겠습니다. 엑스 3 , 엑스 4 , 엑스 5 ,엑스 6 .

경제적 의미에서 추가적인 변수의 값은 엑스 3 , 엑스 4 , 엑스 5 제품 판매 후 남은 원자재를 결정합니다.

결과 방정식 시스템의 행렬은 다음과 같은 형식을 갖습니다.

매트릭스에서 볼 수 있는 ㅏ 4차 기저 마이너는 추가변수에 대한 단위계수로 구성된 행렬식이다. 엑스 3 , 엑스 4 , 엑스 5 ,엑스 6, 0과 다르고 1과 같기 때문입니다. 이는 이러한 변수에 대한 열 벡터가 선형 독립임을 의미합니다. 형태 기초, 및 해당 변수 엑스 3 , 엑스 4 , 엑스 5 ,엑스 6개는 기초적인(기본). 변수 엑스 1 , 엑스 2가 호출됩니다 무료(비핵심).

자유변수인 경우 엑스 1과 엑스 2 묻다 다른 의미그런 다음 기본 변수에 대해 시스템을 풀면 무한한 부분 솔루션 세트를 얻습니다. 자유 변수에 0 값만 주어지면 특정 솔루션의 무한한 집합에서 선택할 수 있습니다. 기본 솔루션- 기본 계획.

변수가 기본이 될 수 있는지 여부를 확인하려면 이러한 변수의 계수로 구성된 행렬식을 계산해야 합니다. 이 행렬식이 0이 아닌 경우 이러한 변수는 기본 변수일 수 있습니다.


기본 해의 수와 해당 기본 변수 그룹의 수는 다음을 초과할 수 없습니다. 여기서 N– 총 변수 수, 아르 자형– 기본 변수의 수, 아르 자형≤ 중≤ N.

우리의 임무를 위해 아르 자형 = 4; N= 6. 그러면 , 즉 4개의 기본 변수로 구성된 15개 그룹(또는 15개의 기본 솔루션)이 가능합니다.

기본 변수에 대한 방정식 시스템을 풀어 봅시다 엑스 3 , 엑스 4 , 엑스 5 ,엑스 6:

자유 변수가 있다고 가정하면 엑스 1 = 0, 엑스 2 = 0이면 기본 변수의 값을 얻습니다. 엑스 3 = 312; 엑스 4 = 15; 엑스 5 = 24;엑스 6 = -10, 즉 기본 해는 = (0; 0; 312; 15; 24; –10)입니다.

이 기본 솔루션은 받아들일 수 없는, 왜냐하면 엑스 6 = –10 ≤ 0, 제한 조건에 따라 엑스 6 ≥ 0. 따라서 변수 대신 엑스 6 기본적으로 자유로운 변수 중에서 다른 변수를 가져와야 합니다. 엑스 1 또는 엑스 2 .

단축된 심플렉스 테이블을 사용하여 추가 솔루션을 수행하고 첫 번째 테이블의 행을 다음과 같은 시스템 계수로 채웁니다(표 1).

1 번 테이블

에프- 라인이 호출됩니다 색인. 함수 방정식은 다음 형식으로 표현될 수 있으므로 반대 부호를 사용하여 취한 목적 함수의 계수로 채워집니다. 에프 = 0 – (– 4엑스 1 – 3엑스 2).

무료회원란에서 비 나는부정적인 요소가 있다 비 4 = -10, 즉 시스템 솔루션이 잘못되었습니다. 실현 가능한 솔루션(참조 계획)을 얻으려면 요소 비 4는 음수가 아니어야 합니다.

선택하다 엑스 6 -음수 자유 용어가 포함된 문자열입니다. 이 줄에는 부정적인 요소가 포함되어 있습니다. 예를 들어 "-1" 중 하나를 선택하십시오. 엑스 1열 및 엑스열 1은 다음과 같이 사용됩니다. 해결 열(변수가 엑스 1은 무료에서 기본으로 이동합니다).

무료 회원을 나눕니다 비 나는해당 요소에 a는이다해결 열, 우리는 평가 관계Θ 나= = (24, 15, 12, 10). 이 중 가장 작은 양수(minΘ)를 선택합니다. 나=10)에 해당합니다. 허가선. 활성화 문자열은 변수를 정의합니다. xj, 다음 단계에서 기초에서 튀어 나와 자유로워집니다. 그렇기 때문에 엑스 6라인은 활성화 라인이고 "-1" 요소는 허용 요소. 동그라미를 치자. 변수 엑스 1과 엑스 6개가 교환되었습니다.

추정 비율 Θ 나각 줄의 값은 규칙에 따라 결정됩니다.

1) Θ 나= 만약에 비 나는그리고 a는이다가지다 다른 표시;

2) Θ 나= , 만약 비 나는= 0 및 a는이다 < 0;

3) Θ 나= , 만약 a는이다 = 0;

4) Θ 나= 0인 경우 비 나는= 0 및 a는이다 > 0;

5) Θ 나= 만약에 비 나는그리고 a는이다같은 징후가 있습니다.

우리는 해결 요소를 사용하여 수정된 조던 제거(JEME) 단계를 수행하고 다음 규칙에 따라 새 테이블(표 2)을 구성합니다.

1) 분해 요소(RE) 대신에 그 반대인 값이 설정됩니다. ;

2) 활성화 문자열의 요소는 RE로 나뉩니다.

3) 분해능 열의 요소가 RE로 분할되고 부호가 변경됩니다.

4) 나머지 요소는 직사각형 규칙에 따라 찾습니다.

테이블에서 2 자유조건이 분명하다. 비 나는- 열은 음수가 아니므로 초기 실현 가능 해를 얻습니다. - 첫 번째 참고 계획= (10; 0; 182; 5; 4; 0). 이 경우 함수의 값은 에프() = 40. 기하학적으로 이는 상단에 해당합니다. 에프(10; 0) 해 다각형(그림 1).

표 2

2. 최적의 계획을 확인합니다.참조 계획은 최적이 아닙니다. 에프-line에는 음수 계수 "-4"가 있습니다. 우리는 계획을 개선합니다.

3. 새로운 참고 계획 찾기

규칙에 따라 허용 요소를 선택합니다.

우리는 가장 작은 음의 계수를 선택합니다 에프-활성화 열을 정의하는 라인 “–4” – 엑스 6; 변하기 쉬운 엑스 6개는 기본으로 변환됩니다.

관계 Θ 찾기 나, 그중에서 해상도 선에 해당하는 가장 작은 양수를 선택합니다.

분 Θ 나 = 분(14, 5, 2, 무한) = 2, 그러므로, 엑스 5라인 – 활성화, 가변 엑스 5개는 무료로 변환됩니다(변수 엑스 5와 엑스 6개는 교환됩니다.)

해결 행과 열의 교차점에는 해결 요소 "2"가 있습니다.

SMGI 단계를 수행하고 테이블을 구축합니다. 3 위의 규칙에 따라 새로운 참조 계획 = (12; 0; 156; 3; 0; 2)을 얻습니다.

표 3

4. 최적성을 위한 새로운 참조 계획 확인

참조 계획도 최적이 아닙니다. 에프-line에는 음수 계수 "-1"이 있습니다. 기능값 에프() = 48, 기하학적으로 상단에 해당 이자형(12; 0) 해 다각형(그림 1). 우리는 계획을 개선합니다.

5. 새로운 참고 계획 찾기

엑스열 2는 허용됩니다. 에프-line에서 가장 작은 음의 계수 "-1"은 엑스 2열(Δ 2 = –1). 우리는 가장 작은 Θ를 찾습니다 나: 분 Θ 나 = 분(≒ 9, 6, , 24) = 6, 그러므로, 엑스 4줄 – 허용. 해상도 요소 "1/2". 변수 교환 엑스 2 및 엑스 4 . SMGI 단계를 수행하고 테이블을 구축합니다. 4, 새로운 참조 계획 = (9; 6; 51; 0; 0; 5)을 얻습니다.

6. 최적성을 위한 참조 계획 확인

안에 에프-line, 모든 계수는 음수가 아니므로 참조 계획이 최적입니다. 기하학적으로 점에 해당 디(9;6)(그림 1 참조). 최적의 계획은 목적 함수 c.u의 최대값을 제공합니다.

실, 단추, 천을 사용하여 세 가지 유형의 셔츠를 만듭니다. 실, 단추 및 천의 재고, 셔츠 한 장 재봉에 대한 소비 기준이 표에 표시되어 있습니다. 최대의 이익과 이를 보장하는 최적의 제품 생산 계획을 찾아보세요(find).

셔츠 1 셔츠 2 셔츠 3 예비비 스레드(m.) 1 9 3 96 버튼(개) 20 10 30 640 섬유 ( 1 2 2 44 이익 (r.) 2 5 4

문제의 해결

모델 빌딩

출시 예정인 1차, 2차, 3차 유형의 셔츠 수와 수량입니다.

그러면 리소스 제한은 다음과 같습니다.

또한, 업무의 의미에 따라

받은 이익을 표현하는 목적 함수:

다음과 같은 선형 프로그래밍 문제가 발생합니다.

선형 계획법 문제를 정규 형식으로 줄이기

문제를 정식 형식으로 줄여보겠습니다. 추가 변수를 소개하겠습니다. 모든 추가 변수를 계수가 0인 목적 함수에 도입합니다. 제한 사항이 없는 제한 사항의 왼쪽에 추가 변수를 추가합니다. 선호하는 유형, 그리고 우리는 평등을 얻습니다.

단순 방법을 사용하여 문제 해결

심플렉스 테이블을 작성하세요.

문제를 최대로 풀고 있으므로, 문제를 최대로 풀 때 인덱스 라인에 음수가 존재한다는 것은 최적의 해를 얻지 못했음을 의미하며 0번째 반복의 테이블에서 다음 단계로 넘어갈 필요가 있음을 나타냅니다. 다음으로.

다음 반복을 다음과 같이 진행합니다.

선행 열은 해당합니다.

키 행은 자유 항과 선행 열의 구성원(단순 관계)의 최소 비율에 의해 결정됩니다.

키 열과 키 행의 교차점에서 활성화 요소를 찾습니다. 9.

이제 첫 번째 반복 컴파일을 진행합니다. 단위 벡터 대신 벡터를 도입합니다.

새 테이블에서는 활성화 요소 대신 1을 쓰고 키 열의 다른 모든 요소는 0입니다. 키 문자열 요소는 활성화 요소로 구분됩니다. 테이블의 다른 모든 요소는 직사각형 규칙을 사용하여 계산됩니다.

첫 번째 반복의 키 열은 다음과 같습니다.

해결 요소는 숫자 4/3입니다. 우리는 기저로부터 벡터를 유도하고 대신 벡터를 도입합니다. 우리는 두 번째 반복의 테이블을 얻습니다.

두 번째 반복의 키 열은 다음과 같습니다.

우리는 핵심 라인을 찾습니다. 이를 위해 다음을 정의합니다.

해결 요소는 숫자 10/3입니다. 우리는 기저로부터 벡터를 유도하고 대신 벡터를 도입합니다. 우리는 세 번째 반복의 테이블을 얻습니다.

№ BP ㄷB 아오 x 1 x 2 x 3 4개 x 5 x 6 단순 2 5 4 0 0 0 관계 0 4개 0 96 1 9 3 1 0 0 32/3 x 5 0 640 20 10 30 0 1 0 64 x 6 0 44 1 2 2 0 0 1 22 Fj-cj 0 -2 -5 -4 0 0 0 1 x 2 5 32/3 1/9 1 1/3 1/9 0 0 32 x 5 0 1600/3 170/9 0 80/3 -10/9 1 0 20 x 6 0 68/3 7/9 0 4/3 -2/9 0 1 17 Fj-cj 160/3 -13/9 0 -7/3 5/9 0 0 2 x 2 5 5 -1/12 1 0 1/6 0 -1/4 -- x 5 0 80 10/3 0 0 10/3 1 -20 24 x 3 4 17 7/12 0 1 -1/6 0 3/4 204/7 Fj-cj 93 -1/12 0 0 1/6 0 7/4 3 x 2 5 7 0 1 0 1/4 1/40 -3/4 x 1 2 24 1 0 0 1 3/10 -6 x 3 4 3 0 0 1 -3/4 -7/40 17/4 Fj-cj 95 0 0 0 1/4 1/40 5/4

색인 행에서 모든 항은 음수가 아니므로 선형 계획법 문제에 대한 다음 솔루션을 얻습니다(자유항 열에서 이를 작성합니다).

첫 번째 유형의 셔츠 24개, 두 번째 유형의 셔츠 7개, 세 번째 유형의 셔츠 3개를 재봉해야 합니다. 이 경우 얻는 이익은 최대이며 95 루블에 이릅니다.

선형 계획법 문제를 해결해야 합니다.

목적 함수:

2x 1 +5x 2 +3x 3 +8x 4 →최소

제한 조건:

3x1 +6x2 -4x3 +x4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x1 +7x2 +x3 ≥1

제한 시스템을 정식 형식으로 가져오겠습니다. 이를 위해서는 추가 변수를 추가하여 불평등에서 평등으로 이동해야 합니다.

우리 문제는 최소화 문제이므로 이를 최대 탐색 문제로 변환해야 합니다. 이를 위해 목적 함수 계수의 부호를 반대 기호로 변경합니다. 첫 번째 부등식의 요소를 변경하지 않고 추가 변수 x 5를 추가하고 "≤" 기호를 "="로 변경하여 작성합니다. 두 번째 및 세 번째 부등식에는 "≥" 부호가 있으므로 계수의 부호를 반대로 변경하고 각각 추가 변수 x 6 및 x 7을 도입해야 합니다. 결과적으로 동일한 문제가 발생합니다.

3x1 +6x2 -4x3 +x4 +x5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x1 -7x2 -x3 +x7 =-1

우리는 초기 심플렉스 테이블의 형성을 진행합니다. 반대 부호를 갖는 목적 함수의 계수는 표의 F행에 입력됩니다.

무료 회원
에프
X5
X6
X7

우리가 편집한 테이블에는 자유 용어 열에 음수 요소가 있으며 그 중에서 모듈러스의 최대값을 찾습니다. 이는 요소입니다. -6, 선행 행인 X6을 설정합니다. 이 줄에서는 모듈러스 단위의 최대 음수 요소도 찾습니다. -10은 선행 열이 될 X3 열에 있습니다. 앞 행의 변수는 기저에서 제외되고, 앞 열에 해당하는 변수는 기저에 포함됩니다. 심플렉스 테이블을 다시 계산해 보겠습니다.

X1 X2 X6 X4 무료 회원
에프 0.8 8.9 0.3 6.5 -1.8
X5 4.6 0.8 -0.4 3 14.4
X3 0.4 -1.3 -0.1 0.5 0.6
X7 -2.6 -8.3 -0.1 0.5 -0.4

우리가 편집한 표에는 자유 용어 열에 음수 요소가 있으며 그 중에서 모듈러스의 최대값을 찾습니다. 이것은 요소입니다: -0.4, 선행 행인 X7을 설정합니다. 이 줄에서는 모듈러스 단위의 최대 음수 요소도 찾습니다. -8.3 이는 선행 열이 될 X2 열에 있습니다. 앞 행의 변수는 기저에서 제외되고, 앞 열에 해당하는 변수는 기저에 포함됩니다. 심플렉스 테이블을 다시 계산해 보겠습니다.

X1 X7 X6 X4 무료 회원
에프 -1.988 1.072 0.193 7.036 -2.229
X5 4.349 0.096 -0.41 3.048 14.361
X3 0.807 -0.157 -0.084 0.422 0.663
X2 0.313 -0.12 0.012 -0.06 0.048

자유항 열에 음수 요소가 없으므로 허용 가능한 해를 찾았습니다. 행 F에는 음수 요소가 포함되어 있어 결과 해가 최적이 아님을 의미합니다. 선행 열을 정의해 보겠습니다. 이를 위해 행 F에서 최대 모듈러스를 갖는 음수 요소를 찾습니다. 이는 -1.988입니다. 선행 행은 선행 열의 해당 요소에 대한 자유 항의 비율이 최소인 행이 됩니다. 선행 행은 X2이고 선행 요소는 0.313입니다.

X2 X7 X6 X4 무료 회원
에프 6.351 0.31 0.269 6.655 -1.924
X5 -13.895 1.763 -0.577 3.882 13.694
X3 -2.578 0.152 -0.115 0.577 0.539
X1 3.195 -0.383 0.038 -0.192 0.153

문자열 F에는 음수 요소가 없으므로
최적의 솔루션이 발견되었습니다. 원래 작업은 최소값을 찾는 것이었으므로 최적의 솔루션은 반대 기호를 사용하여 문자열 F의 자유항이 됩니다. F=1.924
변수 값은 다음과 같습니다: x 3 =0.539, x 1 =0.153. 변수 x 2 및 x 4는 기저에 포함되지 않으므로 x 2 =0 x 4 =0입니다.

예 번호 3. 심플렉스 방법을 사용하여 선형 프로그래밍 문제를 해결합니다.
함수의 가장 큰 값 찾기(인위적 기초)

이 솔루션은 사이트에 제시된 프로그램의 샘플입니다.


함수의 가장 큰 값 찾기

x 1 ≥ 0 x 2 ≥ 0

1. 시스템의 무료 멤버는 음수가 아니어야 합니다.

이 조건이 충족됩니다.


2. 각 시스템 제약조건은 방정식이어야 합니다.

x 1 - 2 x 2 ≤ 4
x 1 - x 2 ≥ 1
x 1 + x 2 ≤ 8
x 1 - 2 x 2 + 에스 1 = 4
x 1 - x 2 - 에스 2 = 1
x 1 + x 2 + 에스 3 = 8

S 1 ≥ 0, S 2 ≥ 0, S 3 ≥ 0. 도입된 변수 S 1, S 2, S 3 을 균형 변수라고 합니다.


3. 초기 기저와 발견된 초기 기저에 해당하는 함수 F의 값을 찾습니다.


기초란 무엇입니까?
변수가 이 방정식에 다음과 같이 포함된 경우 주어진 방정식에 대해 기본 변수라고 합니다. 계수 1나머지 방정식에는 포함되지 않습니다(단, 방정식 오른쪽에 양수가 있는 경우).
각 방정식에 기저 변수가 있으면 시스템에 기저가 있다고 합니다.
기본이 아닌 변수를 free라고 합니다.

심플렉스 방법의 아이디어는 무엇입니까?
각 기초는 단일 함수 값에 해당합니다. 그 중 하나는 가장 높은 가치기능 F.
우리는 한 기초에서 다른 기초로 이동하여 기존보다 작지 않은 함수 F의 값을 얻습니다.
분명히 어떤 문제에 대한 가능한 근거의 수는 그다지 크지 않습니다.
따라서 조만간 답변을 받게 될 것입니다.

한 기반에서 다른 기반으로의 전환은 어떻게 수행됩니까?
솔루션을 테이블 형식으로 기록하는 것이 더 편리합니다. 표의 각 행은 시스템의 방정식과 동일합니다. 강조 표시된 행은 함수의 계수로 구성됩니다(아래 표 참조). 이를 통해 매번 변수를 다시 작성하는 것을 방지하여 시간을 크게 절약할 수 있습니다.
강조 표시된 줄에서 가장 큰 양수 계수를 선택합니다(양수 계수를 선택할 수 있음).
이는 기존 함수 F보다 작지 않은 함수 F의 값을 얻기 위해 필요합니다.
열이 선택되었습니다.
선택한 열의 양수 계수에 대해 비율 Θ를 계산하고 다음을 선택합니다. 가장 작은 값.
이는 변환 후 자유 용어 열이 양수로 유지되도록 하기 위해 필요합니다.
행이 선택되었습니다.
기초가 될 요소가 결정되었습니다. 다음으로 계산합니다.

우리 시스템에 기반이 있나요?

x 1 - 2 x 2 + 에스 1 = 4
x 1 - x 2 - 에스 2 = 1
x 1 + x 2 + 에스 3 = 8

근거가 없습니다. 우리는 해결책을 시작할 수 없습니다.
우리는 그를 찾아야 할 것입니다. 이를 위해 보조 문제를 해결합니다.
기본 변수가 없는 방정식에 인공 변수를 추가해 보겠습니다.

x 1 - 2 x 2 + 에스 1 = 4
x 1 - x 2 - 에스 2 + R 1 = 1
x 1 + x 2 + 에스 3 = 8

R 1 ≥ 0. 도입된 변수 R 1 을 인공 변수라고 합니다.

함수 W를 소개하고 가장 작은 값을 찾아보겠습니다.

함수 W의 가장 작은 값을 찾는 알고리즘은 위에서 설명한 알고리즘과 한 가지 차이점만 있습니다.
스스로 알아내야 할 것입니다.


x 1x 2에스 1에스 2에스 3R 1성. 회원 Θ
1 -2 1 0 0 0 4 4: 1 = 4
1 -1 0 -1 0 1 1 1: 1 = 1
1 1 0 0 1 0 8 8: 1 = 8
-1 1 0 1 0 0 승 - 1
0 -1 1 1 0 -1 3
1 -1 0 -1 0 1 1
0 2 0 1 1 -1 7
0 0 0 0 0 1 승 - 0

우리는 자유 변수를 0과 동일시합니다. 우리는 기본 변수의 값을 구두로 찾습니다. (표 참조)
함수 W는 자유 변수로 표현됩니다. 따라서 주어진 해에 대한 함수 W의 값을 즉시 찾을 수 있습니다. (강조표시된 표 행 참조)

x 2 = 0 S 2 = 0 R 1 = 0
x 1 = 1 S 1 = 3 S 3 = 7		 => W - 0 = 0 => W = 0

선택한 행 계수 중 음수 계수가 없습니다. 결과적으로 함수 W의 가장 작은 값이 발견되었습니다.
인위적인 변수를 사용하지 않고 근거를 얻었습니다. 그것이 필요한 것입니다.
인공 변수에 해당하는 열은 지울 수 있습니다.
결과적으로 우리 시스템은 다음과 같습니다.

- x 2 + 에스 1 + 에스 2 = 3
x 1 - x 2 - 에스 2 = 1
2 x 2 + 에스 2 + 에스 3 = 7
에프 = - x 1 + 3 x 2
에프 = -
( 1 + x 2 + 에스 2)
+ 3 x 2
= -1 + 2 x 2 - 에스 2