Tele2, 관세, 질문에 대한 도움말

심플렉스 방법 - 이것은 선형 계획법 문제의 제약 시스템의 기본 솔루션(해 다면체의 꼭짓점)에서 목표 함수가 최적 값(최대 또는 최소)을 취할 때까지 다른 기본 솔루션으로 연속적으로 전환하는 방법입니다.

심플렉스 방법은 모든 문제를 해결할 수 있는 보편적인 방법입니다. 선형 계획법 문제, 그래픽 방법은 2변수 제약 시스템에만 적합합니다.

심플렉스 방법은 1947년 미국 수학자 R. Danzig에 의해 제안되었으며, 그 이후로 업계의 요구에 따라 이 방법은 종종 수천 개의 변수와 제약 조건이 있는 선형 계획법 문제를 해결합니다.

심플렉스 방법 알고리즘으로 이동하기 전에 몇 가지 정의.

제약 시스템에 대한 음이 아닌 솔루션을 호출합니다. 수용 가능한 솔루션 .

체계가 있게 하라 중부터의 제한 N변수 ( 중 N).

허용되는 기본 솔루션 를 포함하는 솔루션입니다. 중음이 아닌 주요한 (기초적인 ) 변수 및 N - 중 비핵심 . (기본적이지 않거나 무료 ) 변수. 기본 솔루션의 기본이 아닌 변수는 0과 같지만 기본 변수는 원칙적으로 0이 아닙니다. 즉, 양수입니다.

어느 중시스템 변수 중선형 방정식 N변수가 호출됩니다 기본 , 계수의 행렬식이 0과 다른 경우. 그럼 나머지 N - 중변수가 호출됩니다 비핵심 (또는 무료 ).

심플렉스 방법 알고리즘

• 1 단계. 선형 계획법 문제를 표준 형식으로 가져옵니다. 이렇게 하려면 자유 항을 오른쪽으로 이동하고(이 자유 항 중 음수인 경우 해당 방정식 또는 부등식을 -1로 곱함) 각 제약 조건에 추가 변수를 도입합니다( 원래 부등식 기호는 "보다 작거나 같음"이고 "크거나 같음"인 경우 빼기 기호가 있음).
• 2 단계. 결과 시스템에서 중방정식, 다음 중변수를 주요 변수로 하여 기본 변수가 아닌 변수로 주요 변수를 표현하고 해당 기본 솔루션을 찾습니다. 발견된 기본 솔루션이 허용 가능한 것으로 판명되면 허용 가능한 기본 솔루션으로 이동합니다.
• 3단계. 실현 가능한 기본 솔루션의 소수 변수로 목표 함수를 표현합니다. 선형 형식의 최대값(최소값)이 발견되고 표현에 음수(양수) 계수가 있는 비기본 변수가 없으면 최적성 기준이 충족되고 결과 기본 솔루션이 최적이 됩니다. 솔루션이 종료됩니다. 선형 형식의 최대값(최소값)을 찾을 때 해당 표현식에 음수(양수) 계수가 있는 기본이 아닌 변수가 하나 이상 포함되어 있으면 새 기본 솔루션으로 이동합니다.
• 4단계. 음(양) 계수의 선형 형태에 포함된 비기저 변수 중에서 가장 큰(모듈로) 계수에 해당하는 것을 선택하여 주요 변수로 전달합니다. 2단계로 이동합니다.

중요한 조건

몇 가지 특별한 경우는 별도의 문서에서 설명합니다. 최대 목적 함수 - 무한대, 언제 시스템에 솔루션이 없습니다, 그리고 언제 최적의 솔루션은 유일한 솔루션이 아닙니다. .

다음으로, 제약 시스템이 일관되고 유한 최적이 하나만 있는 일반적인 예를 분석합니다. 심플렉스 방법의 변형은 운송 문제를 해결하기 위한 배포 방법 .

심플렉스 테이블이 있는 심플렉스 방법

심플렉스 테이블을 구성하면 다음 단락에 나와 있는 대수 변환보다 선형 계획법 문제를 해결하는 것이 훨씬 쉽습니다. 심플렉스 테이블은 매우 시각적입니다. 심플렉스 테이블 작업에는 여러 유형의 규칙이 있습니다. 가장 흔히 선행 열 및 선행 행 규칙이라고 하는 규칙을 분석합니다.

새 창에서 분수가 있는 수동 작업을 여는 것이 유용할 것입니다. 간단히 말해서 간단한 방법에 문제가 있는 분수가 충분합니다.

예시.

음이 아닌 추가 변수를 도입하고 이 부등식 시스템을 등가 방정식 시스템으로 축소합니다.

.

이것은 다음 규칙에 따라 수행되었습니다. 원래 제약 조건의 부호가 "작거나 같음"이면 추가 변수를 추가해야 하고 "크거나 같음"이면 추가 변수를 추가해야 합니다. 뺀.

도입된 추가 변수는 기본(기본)으로 간주됩니다. 그런 다음 및 는 비기본(자유) 변수입니다.

기본(기본) 변수를 비기본(무료)으로 표현하면 다음을 얻습니다.

또한 비기본(자유) 변수의 관점에서 목표 함수를 표현합니다.

변수의 계수(알 수 없음)에서 첫 번째 심플렉스 표를 구성합니다.

목적 함수와 자유 변수의 계수를 포함하는 테이블의 마지막 행을 인덱스 행이라고 합니다.

인덱스 행의 자유 변수 계수가 음수이므로 결과 솔루션은 최적이 아닙니다. 즉, 최적의 솔루션은 인덱스 행의 자유 변수 계수가 0보다 크거나 같을 것입니다.

다음 표로 이동하려면 숫자 중 가장 큰(모듈로) 및 . 이 숫자는 2입니다. 따라서 선행 열은 기록되는 열입니다.

선행 행을 결정하기 위해 선행 열의 요소에 대한 자유 구성원의 비율의 최소값을 찾고 분자가 양수이고 분모가 음수이면 비율은 무한대로 간주됩니다.

.

따라서 선두 행은 그것이 쓰여진 행입니다.

따라서 선행 요소는 -2입니다.

우리는 두 번째 심플렉스 테이블을 구성합니다.

첫 번째 줄에 새로운 기본 요소를 입력하고 그것이 서 있던 열을 입력하고 새로운 자유 변수를 입력합니다

첫 번째 줄을 채우십시오. 이를 위해 표 1의 선행 행에 있는 모든 숫자를 선행 요소로 나누고 선행 열의 숫자를 제외하고 표 2의 첫 번째 행의 해당 열에 씁니다. 요소가 기록됩니다(즉, 하나를 선행 요소로 나눈 값).

보조 계수 열을 채우십시오. 표 1의 선행 열 수에 대해 선행 요소 외에도 표 2의 보조 계수 열에 반대 기호로 씁니다.

분수가 있는 수동 작업을 새 창에서 아직 열지 않은 사람은 시간이 되었기 때문에 지금 할 수 있습니다.

표 2의 나머지 행을 얻으려면 이미 이 표의 첫 번째 행에 있는 숫자에 채워지는 행의 보조 계수를 곱하고 결과에 다음과 같은 행에 있는 표 1의 숫자를 더합니다. 해당 변수.

예를 들어, 두 번째 행의 자유 멤버를 얻으려면 숫자 1에 1을 곱하고 테이블 1의 숫자 -4를 추가합니다. 우리는 -3을 얻습니다. 같은 방식으로 두 번째 줄에서 에 대한 계수를 찾습니다. . 이전 테이블에는 새 자유 변수가 있는 열이 없으므로 새 자유 변수 열에서 두 번째 행의 계수는 다음과 같습니다. (즉, 테이블 1에 열 c가 없기 때문에 테이블 1에서 0을 추가합니다).

인덱스 라인은 같은 방식으로 채워집니다.

인덱스 행의 자유 변수 계수가 다시 음수이기 때문에 이렇게 얻은 솔루션은 다시 최적이 아닙니다.

다음 심플렉스 테이블로 이동하기 위해 숫자와 , 즉 인덱스 라인에서 계수의 모듈 중 가장 큰(모듈로)를 찾습니다. 이 숫자는 2입니다. 따라서 선행 열은 를 포함하는 열입니다.

선행 행을 검색하기 위해 선행 행의 요소에 대한 자유 구성원의 최소 비율을 찾아보겠습니다. 우리는 다음을 얻습니다.

.

따라서 선행 행은 쓰여진 행이고 선행 요소는 -3/2입니다.

세 번째 심플렉스 테이블 컴파일

첫 번째 줄에 새로운 기본 변수를 씁니다. 그것이 있던 열에 새로운 자유 변수를 입력합니다.

첫째 줄:

보조 계수:

인덱스 행에서 자유 미지수의 계수가 다시 음수이기 때문에 결과 솔루션은 다시 최적이 아닙니다.

네 번째 심플렉스 테이블로 이동하려면 숫자와 . 이것은 숫자입니다.

따라서 선행 열은 가 있는 열입니다.

선행 열의 요소에 대한 자유 구성원의 최소 관계 계수:

.

따라서 선행 행은 쓰여진 행이고 선행 요소는 1/3입니다.

네 번째 심플렉스 테이블에서 첫 번째 줄에 새 기본 변수를 씁니다. 그것이 있던 열에 새로운 자유 변수를 씁니다.

첫째 줄:

보조 계수:

두 번째 행의 예를 사용하여 나머지 행 계산:

결과 솔루션도 최적은 아니지만 인덱스 행의 자유 변수에 대한 계수 중 하나가 음수가 아니기 때문에 이미 이전 솔루션보다 낫습니다.

계획을 개선하기 위해 다음 심플렉스 테이블로 이동하겠습니다.

4와 . 중에서 가장 큰 수를 찾으십시오. 이 숫자는 4입니다. 따라서 선행 열은 입니다.

선행 행을 찾으려면

.

따라서 선행 행은 를 포함하는 행입니다. 그러나 그들은 이미 자유 변수 사이에 함께 있었습니다. 따라서 다음 변수를 무료에서 기본으로 전송하기 위해 다른 선행 열, 즉 쓰여진 열을 선택합니다.

선행 행을 찾으려면

.

따라서 핵심 행은 쓰여진 행이고 선행 요소는 1입니다.

다섯 번째 단순 테이블에서 새 기본 변수는 첫 번째 줄에 작성됩니다. 그것이 있던 열에 새로운 자유 변수를 씁니다.

첫째 줄:

보조 계수:

솔루션이 최적이 아닌지 즉시 알아 보겠습니다. 따라서 나머지 행에 대해서는 자유 항(자유 변수가 0일 때 기본 변수의 값을 찾기 위해)과 색인 행의 자유 변수에 대한 계수만 계산합니다.

무료 회원:

두 번째 줄에서 ;

세 번째 줄에서 ;

네 번째 줄에서.

인덱스 라인:

우리는 심플렉스 표 5를 봅니다. 인덱스 행의 자유 미지수에 대한 계수가 음이 아니기 때문에 최적의 솔루션이 얻어졌음을 알 수 있습니다.

대수 변환을 사용한 심플렉스 방법

이전 단락과 동일한 예를 대수 변환으로 해결합시다. 이러한 유형의 심플렉스 방법을 해결할 때 목표 함수를 다음 형식으로 작성하지 않는 것이 좋습니다. , 표지판에서 혼동하기 쉽기 때문입니다. 그러나 이 경우 최적성 기준을 결정하는 알고리즘의 포인트는 다음과 같이 수정된다.

선형 형식의 최대(최소)가 발견되고 표현에 양수(음수) 계수가 있는 비기본 변수가 없는 경우 최적성 기준이 충족되고 결과 기본 솔루션이 최적입니다. 솔루션이 종료됩니다. 선형 형식의 최대값(최소값)을 찾을 때 해당 표현식에 양수(음수) 계수가 있는 기본이 아닌 변수가 하나 이상 포함되어 있으면 새 기본 솔루션으로 이동합니다.

예시.제약 조건에서 함수의 최대값 찾기

1단계. 음이 아닌 변수를 추가로 도입하고 이 부등식 시스템을 등가 방정식 시스템으로 줄입니다.

.

이 경우 시스템의 기본 솔루션을 쉽게 찾을 수 있으므로 도입된 추가 변수를 주요 변수로 사용합니다. 그런 다음 및 는 사소한 변수입니다.

비 기본 변수의 관점에서 주요 변수를 표현하면 다음을 얻습니다.

결과적으로 이러한 변수의 기본 및 비기본 분할은 기본 솔루션에 해당합니다. , 유효하지 않으므로(두 변수는 음수임) 최적이 아닙니다. 이 기본 솔루션에서 개선된 솔루션으로 이동해 보겠습니다.

어떤 변수를 비주체에서 원수로 이전해야 하는지 결정하려면 두 번째와 같이 음의 자유 항이 있는 마지막 시스템의 사용 가능한 두 방정식 중 하나를 고려하십시오. 이 방정식에서 양의 계수를 갖기 때문에 및 주 변수로 변환될 수 있음을 보여줍니다(따라서 증가할 때 주 변수로 변환하면 변수가 증가할 것입니다).

주요 변수로 번역해 보겠습니다. 기본 변수에서 기본 변수가 아닌 변수로 이동해야 하는 변수를 결정하기 위해 시스템의 자유 구성원과 계수의 가장 작은 비율의 절대값을 에서 찾습니다. 우리는 . 이는 변수가 원래 기본 솔루션에서 양수인 비기본 변수로 변환되어야 함을 보여주는 세 번째 방정식에서 얻습니다. 결과적으로 얻은 기본 솔루션은 원래 솔루션과 마찬가지로 두 가지 부정적인 구성 요소를 포함합니다. 즉, 이러한 기본 솔루션으로의 전환이 개선되지 않을 것입니다.

선형 프로그래밍 제한된 자원의 사용을 최적화하도록 설계된 수학적 모델링 기술입니다. LP는 군사 분야, 산업, 농업, 운송 산업, 경제, 의료 시스템 및 사회 과학 분야에서도 성공적으로 적용되었습니다. 이 방법의 광범위한 사용은 또한 이 방법을 구현하는 매우 효율적인 컴퓨터 알고리즘에 의해 지원됩니다. 최적화 알고리즘은 정수, 비선형 및 확률적 프로그래밍을 포함하여 더 복잡한 유형의 모델 및 연산 연구(OR) 문제에 대한 선형 프로그래밍 알고리즘을 기반으로 합니다.

최적화 문제 목적 함수의 최적(최대 또는 최소) 값을 찾는 것으로 구성된 경제적, 수학적 문제이며 변수의 값은 허용 가능한 값의 특정 범위에 속해야 합니다.

가장 일반적인 형태의 선형 계획법 문제는 수학적으로 다음과 같이 작성됩니다.

어디 X = (x 1 , x 2 , ... , x N ) ; 여– 변수의 허용 가능한 값 범위 엑스 1 , x 2 , ... , x N ;f(X)대상 기능입니다.

최적화 문제를 해결하기 위해서는 최적의 솔루션을 찾는 것으로 충분합니다. ~을 나타내다 어떠한 것도 .

최적화 문제는 최적 솔루션이 없으면 해결할 수 없습니다. 특히 목적 함수가 다음과 같은 경우 최대화 문제를 해결할 수 없습니다. f(X)허용 가능한 집합에서 위에서부터 무한 여.

최적화 문제를 해결하는 방법은 목적 함수의 유형에 따라 다릅니다. f(X), 그리고 허용 가능한 집합의 구조 여. 문제의 목적 함수가 함수인 경우 N변수를 사용하는 경우 솔루션 방법을 수학적 프로그래밍 방법이라고 합니다.

선형 계획법 문제의 특징은 다음과 같습니다.

최적의 지표 f(X)솔루션 요소의 선형 함수입니다. X = (x 1 , x 2 , ... , x N ) ;

가능한 솔루션에 부과되는 제한 조건은 선형 등식 또는 부등식의 형태를 갖습니다.

선형 계획법 문제 작업 연구의 문제라고 하며, 그 수학적 모델은 다음과 같은 형식을 갖습니다.

(2) (3) (4) (5)

이 경우 문제에 대한 허용 가능한 솔루션 세트를 결정하는 선형 방정식 (3) 및 부등식 (4), (5) 시스템 여, 라고 한다 제한 시스템 선형 계획법 문제와 선형 함수 f(X)~라고 불리는 목적 함수 또는 최적성 기준 .

유효한 솔루션 숫자 모음입니다 계획 ) 엑스 = (엑스 1 , 엑스 2 , ... , 엑스 N ) 문제의 제약 조건을 충족합니다. 최적의 솔루션 목적 함수가 최대(최소) 값을 취하는 계획입니다.

선형 계획법 문제의 수학적 모델이 다음 형식을 갖는 경우:

그런 다음 그들은 작업이 정형 .

모든 선형 계획법 문제는 정규 형식의 선형 계획법 문제로 축소될 수 있습니다. 이렇게 하려면 일반적으로 최대화의 문제를 최소화의 문제로 줄일 수 있어야 합니다. 부등식 제약 조건에서 등식 제약 조건으로 이동하고 음이 아닌 조건을 따르지 않는 변수를 대체합니다. 일부 기능의 최대화는 반대 부호로 취한 동일한 기능의 최소화와 동일하며 그 반대의 경우도 마찬가지입니다.

선형 계획법 문제를 정준 형식으로 줄이는 규칙은 다음과 같습니다.

원래 문제에서 선형 함수의 최대값을 결정해야 하는 경우 부호를 변경하고 이 함수의 최소값을 찾아야 합니다.

제한의 오른쪽이 음수이면 이 제한에 -1을 곱해야 합니다.

제약 조건 사이에 불평등이 있는 경우 추가로 음이 아닌 변수를 도입하여 평등으로 변환합니다.

만약 어떤 변수가 엑스 제이부호 제한이 없으면 (목적 함수 및 모든 제한에서) 음이 아닌 두 개의 새로운 변수 간의 차이로 대체됩니다. 엑스 3 = x 3 + - 엑스 3 - , 어디 엑스 3 + , x 3 - ≥ 0 .

실시예 1. 선형 계획법 문제의 정준 형태로 축소:

최소 L = 2x 1 + x 2 - 엑스 3 ; 2배 2 - 엑스 3 ≤ 5; 엑스 1 + x 2 - 엑스 3 ≥ -1; 2배 1 - 엑스 2 ≤ -3; 엑스 1 ≤ 0 엑스 2 ≥ 0; 엑스 3 ≥ 0.

제약 시스템의 각 방정식에 균등화 변수를 도입합시다. 엑스 4 , x 5 , x 6 . 시스템은 평등의 형태로 작성되며 제약 시스템의 첫 번째 및 세 번째 방정식에서 변수 엑스 4 , x 6 "+" 기호로 왼쪽에 입력하고 두 번째 방정식에서 변수 엑스 5 "-" 기호로 입력했습니다.

2배 2 - 엑스 3 + x 4 = 5; 엑스 1 + x 2 - 엑스 3 - 엑스 5 = -1; 2배 1 - 엑스 2 + x 6 = -3; 엑스 4 ≥ 0; 엑스 5 ≥ 0; 엑스 6 ≥ 0.

표준 형식의 자유 항은 양수여야 합니다. 이를 위해 마지막 두 방정식에 -1을 곱합니다.

2배 2 - 엑스 3 + x 4 = 5; -엑스 1 - 엑스 2 + x 3 + x 5 = 1; -2배 1 + x 2 - 엑스 6 = 3.

선형 계획법 문제를 해결하기 위한 심플렉스 방법.

심플렉스 방법 알고리즘은 제한된 수의 유효한 기본 솔루션을 고려하여 최적의 솔루션을 찾습니다. 심플렉스 방법 알고리즘은 항상 몇 가지 실행 가능한 기본 솔루션으로 시작한 다음 목적 함수의 값을 "향상"하는 다른 실행 가능한 기본 솔루션을 찾으려고 합니다. 이는 0(기본이 아닌) 변수의 증가가 목적 함수 값의 개선으로 이어지는 경우에만 가능합니다. 그러나 기본이 아닌 변수가 양수가 되려면 현재 기본 변수 중 하나를 0으로 만들어야 합니다. 기본이 아닌 것으로 변환합니다. 이것은 새로운 솔루션이 정확히 중기본 변수. 심플렉스 방법의 용어에 따라 선택한 null 변수는 도입 (기준으로), 삭제할 기준 변수 - 제외된 (기준에서).

심플렉스 방법에서 입력 및 배타적 변수를 선택하기 위한 두 가지 규칙이 호출됩니다. 최적 조건 그리고 허용 조건 . 이러한 규칙을 공식화하고 심플렉스 방법을 구현할 때 수행되는 일련의 작업도 고려하겠습니다.

최적 조건. 최대화(최소화) 문제의 입력 변수는 다음에서 가장 큰 음(양) 계수를 갖는 비기저 변수입니다. 표적-끈. 만약에 표적-line에 이러한 계수가 여러 개 포함되어 있으면 입력 변수의 선택이 임의로 이루어집니다. 최적의 솔루션은 다음과 같은 경우에 도달합니다. 표적-line, 기본이 아닌 변수에 대한 모든 계수는 음이 아닌(양이 아닌) 값이 됩니다.

허용 조건. 최대화 문제와 최소화 문제 모두에서 기본 변수가 제외된 변수로 선택되며, 이에 대해 선행 열의 양수 계수에 대한 제약 조건의 오른쪽 값의 비율이 최소입니다. 이 속성을 가진 기본 변수가 여러 개 있는 경우 제외된 변수의 선택은 임의로 수행됩니다.

심플렉스 테이블을 사용하여 최대값을 찾는 선형 계획법 문제를 해결하는 알고리즘을 제시합니다.

F \u003d s 1 x 1 + s 2 x 2 + ... + s n x n max

x 1 0, x 2 0,…, x n 0.

첫 번째 단계. 우리는 추가 변수를 소개하고 결과 시스템의 방정식과 확장 시스템의 형태로 선형 함수를 기록합니다.

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.

2단계.초기 심플렉스 표를 작성합니다.

3단계.마지막 행에 음수 계수가 있는지 최적성 기준의 충족 여부를 확인합니다. 없는 경우 솔루션이 최적이고 F * =co , 기본 변수는 해당 계수 b j 와 같고, 비기본 변수는 0과 같습니다. 즉, X * =(b 1 ,b 2 ,…, b m , 0, …, 0).

4단계. 최적성 기준이 충족되지 않으면 마지막(평가) 행의 절대값에서 가장 큰 음수 계수가 해상도 열 s를 결정합니다.

허용 문자열을 결정하기 위해 예상 비율을 계산합니다. 테이블의 마지막 열을 채우십시오.

i 번째 라인의 추정 비율은 다음과 같습니다.

 b i 와 is 의 부호가 다른 경우

 b i = 0이고 a가<0;

 a가 0이면;

b i = 0이고 a가 >0이면 0;

추정 관계 열에서 최소 요소 최소값을 찾습니다. 활성화 문자열 g를 정의합니다.

최솟값이 없으면 문제에 유한 최적 I가 없고 풀 수 없습니다.

허용 행과 열의 교차점에는 허용 요소 a gs 가 있습니다.

다섯 번째 단계. 우리는 다음 테이블을 만듭니다. 이를 위해

세 번째 단계로 넘어갑시다.

M-방법 LLP를 풀 때 알려지지 않은 제약 조건에 대한 계수 행렬에서 단위 행렬을 구성할 수 있는 단일 열이 없는 경우가 있습니다. 기본 변수 선택에 문제가 있거나 초기 솔루션이 유효하지 않습니다. 이러한 경우 사용 인공 기초 방법 (M - 방법).기본 변수가 없는 모든 제약 조건에서 다음을 도입합니다. 인공 변수. 인공 변수는 최대 작업의 경우 계수(-M)와 최소 작업의 경우 계수(+ M)를 사용하여 목적 함수에 도입됩니다. 여기서 M은 충분히 큰 양수입니다.. 그런 다음 확장된 문제는 심플렉스 방법의 규칙에 따라 해결됩니다. 모든 인공 변수가 0으로 판명되면, 즉 기초에서 제외된 경우 원래 문제의 최적해를 얻거나 원래 문제를 추가로 해결하여 최적해를 찾거나 해결할 수 없음이 설정됩니다. 인공 변수 중 적어도 하나가 0과 다른 것으로 판명되면 원래 문제에는 솔루션이 없습니다.

LP 문제를 푸는 보편적인 방법을 심플렉스 방법이라고 합니다. 이 방법의 적용 및 가장 일반적인 수정 - 2상 심플렉스 방법.

LP 문제를 해결하기 위한 그래픽 방법을 사용하여 실제로 목적 함수의 값이 최대(최소)에 도달한 정점과 같은 부등식 시스템의 솔루션 세트의 경계에 속하는 정점 세트를 선택했습니다. 두 변수의 경우 이 방법은 매우 명확하며 문제에 대한 솔루션을 빠르게 찾을 수 있습니다.

문제에 3개 이상의 변수가 있고 이것이 바로 실제 경제 문제의 상황이라면 제약 시스템에 대한 솔루션의 영역을 시각화하기 어렵습니다. 그러한 작업은 다음의 도움으로 해결됩니다. 심플렉스 방법 또는 연속적인 개선 방법. 방법의 아이디어는 간단하며 다음으로 구성됩니다.

일정한 규칙에 따라 초기 참조 평면(제약 영역의 일부 정점)을 찾습니다. 계획이 최적인지 여부를 확인합니다. 그렇다면 문제가 해결된 것입니다. 그렇지 않은 경우 다른 개선된 계획인 다른 정점으로 이동합니다. 이 계획의 목적 함수 값(이 정점에서)은 확실히 이전 것보다 좋습니다. 전이 알고리즘은 몇 가지 계산 단계의 도움으로 수행되며, 이는 심플렉스 테이블 . 유한한 수의 정점이 있기 때문에 유한한 수의 단계에서 최적의 솔루션에 도달합니다.

계획 작성 작업의 특정 예에서 심플렉스 방법을 고려해 보겠습니다.

다시 한번, 우리는 심플렉스 방법이 기저, 양의 우변, 비기저 변수로 표현된 목적 함수를 갖는 특수한 형태로 축소된 정규 LP 문제를 푸는 데 적용할 수 있음을 주목합니다. 문제가 특별한 형태로 축소되지 않으면 추가 단계가 필요하며 나중에 논의합니다.

이전에 모델을 만들고 특별한 형태로 축소한 생산 계획의 문제를 고려해 보겠습니다.

작업.

제품 제조용 하지만그리고 에창고는 80개 이하의 원자재를 출시할 수 있습니다. 그리고 제품의 제조를 위해 하지만두 단위가 소비되고 제품 에- 원료 1단위. 제품의 경우 최대의 이윤이 확보될 수 있도록 생산을 계획하는 것이 필요합니다. 하지만 50개 이하의 제품을 생산해야 하며, 에- 40개 이하. 또한, 하나의 제품을 판매하여 얻은 이익은 하지만- 5 루블부터 에- 3 문지름.

다음을 나타내는 수학적 모델을 구성해 보겠습니다. 엑스 1 제품 A의 수 엑스 2 - 제품 수 에. 제약 조건 시스템은 다음과 같습니다.

x 1 ≤50
x2 ≤40
2x1 +x2 ≤80
x 1 ≥0, x 2 ≥0
5x1 +3x2→최대

추가 변수를 도입하여 문제를 표준 형식으로 가져옵니다.

x 1 + x 3 =50
x2 +x4 =40
2x1 +x2 +x5 =80
x 1 ≥0, x 2 ≥0
5x1 +3x2→최대
-F = -5x 1 - 3x 2 → 최소

이 문제는 특별한 형태를 가지고 있습니다(기본적으로 우변은 음수가 아님). 심플렉스 방법으로 해결할 수 있습니다.

나단계.단순 테이블에 작업 쓰기. 문제의 제약 시스템(3.10)과 심플렉스 테이블 사이에는 일대일 대응 관계가 있습니다. 제약 시스템의 평등 수만큼 테이블에 행이 있고 자유 변수가 있는 만큼 열이 있습니다. 기본 변수는 첫 번째 열을 채우고 자유 변수는 테이블의 맨 위 행을 채웁니다. 맨 아래 라인은 인덱스 라인이라고 하며 목적 함수의 변수에 대한 계수를 포함합니다. 함수에 자유 멤버가 없으면 오른쪽 아래 모서리에 처음에 0이 기록됩니다. 있는 경우 반대 기호로 씁니다. 이 위치(오른쪽 하단 모서리)에는 한 테이블에서 다른 테이블로 이동할 때 모듈로를 증가시켜야 하는 목적 함수의 값이 있습니다. 따라서 우리의 제한 시스템은 표 3.4에 해당하며 솔루션의 두 번째 단계로 진행할 수 있습니다.

표 3.4

II단계. 최적의 기본 계획을 확인합니다.

이 표 3.4는 다음 기준에 해당합니다.

(엑스 1 , 엑스 2 , 엑스 3 , 엑스 4 , 엑스 5) = (0, 0, 50, 40, 80).

자유 변수 엑스 1 , 엑스 2는 0입니다. 엑스 1 = 0, 엑스 2 = 0. 그리고 기본 변수 엑스 3 , 엑스 4 , 엑스 5 가치를 취하다 엑스 3 = 50, 엑스 4 = 40, 엑스 5 = 80 - 무료 회원 열에서. 목적 함수 값:

-에프 = - 5엑스 1 - 3엑스 2 = -5 0 - 3 0 = 0.

우리의 임무는 주어진 기본 계획이 최적인지 확인하는 것입니다. 이렇게 하려면 인덱스 라인 - 목적 함수의 라인을 봐야 합니다. 에프.

다양한 상황이 가능합니다.

1. 인덱스에서 에프-string에는 음수 요소가 없습니다. 따라서 계획이 최적이며 문제의 솔루션을 작성할 수 있습니다. 목표 함수는 반대 부호로 취한 오른쪽 하단 모서리의 숫자와 동일한 최적 값에 도달했습니다. IV 단계로 넘어갑시다.

2. 인덱스 행에 최소한 하나의 음수 요소가 있고 열에는 양수 요소가 없습니다. 그런 다음 목적 함수가 에프→∞가 무기한 감소합니다.

3. 열에 하나 이상의 양수 요소가 포함된 인덱스 행에 음수 요소가 있습니다. 그런 다음 다음 단계 III으로 넘어갑니다. 테이블을 다시 계산하여 기준선을 개선합니다.

III단계. 기본 계획의 개선.

인덱스의 부정적인 요소 중 에프-행 우리가 가장 큰 모듈로 선택, 우리는 해결에 해당하는 열을 호출하고 ""를 표시합니다.

해결 행을 선택하려면 자유 멤버 열의 요소 비율을 계산해야 합니다. 뿐에게 긍정적인권한 열 요소. 얻은 비율에서 최소값을 선택하십시오. 최소값에 도달하는 해당 요소를 해결 요소라고 합니다. 우리는 그것을 사각형으로 강조 할 것입니다.

이 예에서 요소 2는 허용적입니다. 이 요소에 해당하는 문자열을 해석이라고도 합니다(표 3.5).

표 3.5

해결 요소를 선택하면 규칙에 따라 테이블을 다시 계산합니다.

1. 이전과 동일한 크기의 새 테이블에서 해결 행 및 열 변수가 교체되며 이는 새 기준으로의 전환에 해당합니다. 우리의 예에서: 엑스대신 1이 기본에 포함됩니다. 엑스 5 , 기본을 떠나 이제 무료입니다(표 3.6).

표 3.6

2. 분해 요소 2 대신 역수 ½을 씁니다.

3. 허용 라인의 요소를 허용 요소로 나눕니다.

4. 결의란의 요소는 결의요소로 나누어 반대 부호로 쓴다.

5. 표 3.6의 나머지 요소를 채우기 위해 직사각형 규칙에 따라 다시 계산합니다. 50번 위치에 있는 요소를 계산한다고 가정해 보겠습니다.

이 요소를 해결하는 요소와 정신적으로 연결하고 제품을 찾고 결과 사각형의 다른 대각선에 위치한 요소의 곱을 뺍니다. 차이는 해결 요소로 나뉩니다.

그래서, . 50이었던 자리에 10을 씁니다. 유사하게:
, , , .

표 3.7

새 테이블 3.7이 있으며 기본 변수는 이제 변수입니다(x 3 ,x 4 ,x 1 ). 목적 함수의 값은 -200, 즉 감소. 이 기본 솔루션의 최적성을 확인하려면 2단계로 돌아가야 합니다. 프로세스는 분명히 유한하며 중지 기준은 단계 II의 포인트 1과 2입니다.

문제에 대한 솔루션을 완성해 봅시다. 이를 위해 인덱스 행을 확인하고 그 안에 음수 요소 -½을 보고 해당 열을 해결이라고 부르고 III 단계에 따라 테이블을 다시 계산합니다. 비율을 만들고 그 중에서 최소값 = 40을 선택하여 해결 요소 1을 결정했습니다. 이제 규칙 2-5에 따라 재계산이 수행됩니다.

표 3.8

테이블을 다시 계산한 후 인덱스 행에 음수 요소가 없는지 확인하므로 문제가 해결되고 기본 계획이 최적입니다.

IV단계. 최적의 솔루션을 작성합니다.

2단계의 1번 항목에 따라 심플렉스법이 멈춘 경우 문제의 해는 다음과 같이 작성한다. 기본 변수는 각각 자유 멤버 열의 값을 취합니다. 우리의 예에서 엑스 3 = 30, 엑스 2 = 40, 엑스 1 = 20. 자유 변수는 0, 엑스 5 = 0, 엑스 4 = 0. 목적 함수는 반대 부호를 가진 자유 항 열의 마지막 요소 값을 취합니다. - 에프 = -220 → 에프= 220, 이 예에서 함수는 최소값으로 검사되었으며 처음에는 에프→ 최대, 그래서 부호가 실제로 두 번 변경되었습니다. 그래서, 엑스* = (20, 40, 30, 0, 0), 에프* = 220. 문제에 대한 답:

출시 계획에 해당 유형의 제품을 20개 포함해야 합니다. 하지만, 유형 B의 40 제품, 이익은 최대이며 220 루블과 같습니다.

이 섹션의 끝에서 우리는 단계를 정확히 반복하는 심플렉스 방법 알고리즘의 블록 다이어그램을 제시하지만, 아마도 일부 독자에게는 화살표가 명확한 동작 방향을 나타내기 때문에 사용하는 것이 더 편리할 것입니다.

순서도의 상자 위 링크는 해당 변환 그룹이 속한 단계 또는 하위 항목을 보여줍니다. 초기 기준선을 찾기 위한 규칙은 단락 3.7에서 공식화됩니다.

예시. 심플렉스 방법을 사용하여 다음 LP 문제를 정준 형식으로 풉니다.
f(x)=x 1 +9x 2 +5x 3 +3x 4 +4x 5 +14x 6 → 최소
x1 +x4 =20
x2 +x5 =50
x 3 + x 6 =30
x 4 + x 5 + x 6 = 60
x i ≥ 0, i = 1,…,6
LP 문제는 모든 제약 조건(변수의 음이 아닌 조건 제외)이 등식의 형식을 갖고 모든 자유 항이 음이 아닌 경우 정규 형식을 갖는다고 합니다. 그래서 우리는 표준 형식에 문제가 있습니다.
심플렉스 방법의 아이디어는 다음과 같습니다. 먼저, 허용 가능한 솔루션(초기 허용 가능한 기본 솔루션)의 다면체의 일부 (초기) 꼭짓점을 찾아야 합니다. 그런 다음 이 솔루션의 최적성을 확인해야 합니다. 최적이면 솔루션을 찾습니다. 그렇지 않은 경우 다면체의 다른 꼭짓점으로 이동하여 최적성을 다시 확인합니다. 다면체 정점의 유한성을 고려하여(LP 문제의 유한성의 결과) 유한한 수의 "단계"에서 원하는 최소 또는 최대 점을 찾을 수 있습니다. 한 정점에서 다른 정점으로 이동할 때 목적 함수의 값은 감소(최소 문제에서) 또는 증가(최대 문제에서)된다는 점에 유의해야 합니다.
따라서 심플렉스 방법의 아이디어는 LP 문제의 세 가지 속성을 기반으로 합니다.
해결책.초기 실행 가능한 기본 솔루션을 찾으려면 기본 변수를 결정하려면 시스템(5.6)을 "대각선" 형식으로 줄여야 합니다. 가우스 방법(미지수의 연속 제거 방법)을 적용하면 (5.6)에서 다음을 얻습니다.
x 2 + x 1 + x 3 \u003d 40
x4+x1=20
x5 -x1 -x3 =10
x6+x3=30
따라서 변수는 기본 x 2 , x 4 , x 5 , x 6 ,우리는 그들에게 해당 라인의 자유 구성원과 동일한 값을 제공합니다. x 2 \u003d 40, x 4 \u003d 20, x 5 \u003d 10, x 6 \u003d 30,. 변수 x 1그리고 x 3비기본: x 1 \u003d 0, x 3 \u003d 0.
초기 허용 가능한 기본 솔루션을 구성해 보겠습니다.
x 0 = (0.40,0.20,10.30) (5.9)
찾은 솔루션의 최적성을 확인하려면 x0목적 함수에서 기본 변수를 제외하고(시스템(5.8)의 도움으로) 특수 심플렉스 테이블을 구성해야 합니다.
변수를 제거한 후 목적 함수를 다음 형식으로 작성하는 것이 편리합니다.
f(x) = -7x 1 - 14x 3 +880(5.10)
이제 (5.8) -(5.10)을 사용하여 초기 심플렉스 테이블을 구성합니다.

0선에는 목적 함수에 대한 해당 변수의 부호가 반대인 계수가 포함됩니다. 최적성 기준(최소 탐색 문제에 대한): 허용 가능한 기본 솔루션( x0)는 0 행에 엄격하게 양수 하나가 없는 경우 최적입니다(목적 함수(880)의 값을 계산하지 않음). 이 규칙은 다음 반복(테이블)에도 적용됩니다. 0 행의 요소를 열 추정이라고 합니다.
따라서 초기 허용 가능한 기본 솔루션(5.9)은 최적이 아닙니다. 7>0, 14>0 .
0 열에는 기본 변수의 값이 포함됩니다. 반드시 음수가 아니어야 합니다(방정식 (5.7) 참조). 첫 번째 줄부터 네 번째 줄까지 시스템(5.8)의 변수 계수가 기록됩니다.
왜냐하면 x0최적이 아닌 경우 허용 가능한 솔루션의 다면체의 다른 꼭지점으로 이동해야 합니다(새 d.b.r. 구성). 이를 위해서는 선행 요소를 찾아 특정 변환(단순 변환)을 수행해야 합니다.
먼저, 선행 열(가장 높은 양수 점수를 가진 열)과 선행 행(0 열의 요소 대 요소의 최소 비율에 해당하는 행의 교차점에 있는 테이블의 선행 요소를 찾습니다. 선행 열의 해당 요소(엄격히 양수).
표 1에서 선행 열은 세 번째 열이고 선행 행은 네 번째 행입니다. (최소(40/1,30/1)=30/1)화살표로 표시되고 선행 요소가 원으로 표시됩니다. 선행 요소는 기본 변수가 x6기본이 아닌 것으로 대체해야 함 x 3. 그러면 새로운 기본 변수는 x 2 , x 3 , x 4 , x 5 ,, 그리고 비기본 - x 1 , x 6 ,. 이것은 허용 가능한 솔루션의 다면체의 새로운 정점으로의 전환을 의미합니다. 새로운 실현 가능한 기본 솔루션의 좌표 값을 찾으려면 x00새로운 심플렉스 테이블을 만들고 기본 변환을 수행해야 합니다.
ㅏ)선행 행의 모든 ​​요소를 ​​선행 요소로 나누어 선행 요소를 1로 바꿉니다(쉽게 계산하기 위해).
비)선행 요소(1과 같음)를 사용하여 선행 열의 모든 요소를 ​​0으로 바꿉니다(미지수를 제거하는 방법과 유사).
결과적으로 새로운 기본 변수의 값은 0 열에서 얻습니다. x 2 , x 3 , x 4 , x 5 ,(표 2 참조) - 새로운 탑의 기본 구성요소 x00(비기본 구성 요소 x 1 \u003d 0, x 6 \u003d 0,).

표 2에서 알 수 있듯이 새로운 기본 솔루션은 x00 =(0,10,30,20,40,0)비최적(0 행에는 음수가 아닌 추정값 7이 있음). 따라서 선행 요소 1(표 2 참조)을 사용하여 새로운 심플렉스 테이블, 즉 우리는 새로운 허용 가능한 기본 솔루션을 구성합니다.

표 3은 허용되는 기본 솔루션에 해당합니다. x000 =(10,0,30,10,50,0)최적이기 때문에 제로 라인에는 긍정적인 표시가 없습니다. 그렇기 때문에 f(x000)=390목적 함수의 최소값입니다.
대답: x000 =(10, 0, 30, 10, 50, 0)- 최소 포인트, f(x000)=390.

조건부 표준 선형 계획법 문제

1. 직접 문제에 대한 최적의 계획 찾기:
   a) 그래픽 방식
   b) 심플렉스 방법(초기 참조 계획을 구성하는 데 인공적인 기초 방법을 사용하는 것이 좋습니다).
2. 이중 문제를 만드십시오.
3. 보완 느슨함의 조건을 사용하여 직선의 그래픽 솔루션에서 쌍대 문제의 최적 계획을 찾습니다.
4. 직접 문제를 해결하여 얻은 최종 심플렉스 표를 사용하여 첫 번째 이중성 정리에 의해 이중 문제에 대한 최적의 계획을 찾습니다(섹션 1b 참조). "최적 솔루션에 대한 한 쌍의 이중 문제의 목적 함수 값이 동일합니다."라는 문장을 확인하십시오.
5. 심플렉스 방법을 사용하여 쌍대 문제를 푼 다음 쌍대 문제의 최종 단순 테이블을 사용하여 첫 번째 이중성 정리를 사용하여 직접 문제에 대한 최적의 계획을 찾습니다. 결과를 그래픽 방법으로 얻은 결과와 비교하십시오(단락 1a 참조).
6. 최적의 정수 솔루션 찾기:
   a) 그래픽 방식
   b) 고모리 방법.
   정수 솔루션과 정수가 아닌 솔루션의 함수 값 비교

자제를 위한 질문

1. 심플렉스 테이블은 어떻게 구성됩니까?
2. 베이시스 변경은 테이블에 어떻게 반영됩니까?
3. 심플렉스 방법에 대한 중지 기준을 공식화하십시오.
4. 테이블 재계산을 구성하는 방법은 무엇입니까?
5. 테이블 재계산을 시작하는 것이 편리한 줄은 무엇입니까?

이 방법은 선형 계획법 문제의 참조 솔루션을 의도적으로 열거하는 방법입니다. 최적의 솔루션을 찾거나 최적의 솔루션이 없음을 확인하는 유한한 수의 단계를 허용합니다.

1. 최적의 참조 솔루션을 찾는 방법 지정
2. 목적 함수의 값이 최적에 더 가깝도록 한 참조 솔루션에서 다른 참조 솔루션으로의 전환 방법을 지정합니다. 참조 솔루션을 개선하는 방법을 나타냅니다.
3. 최적의 솔루션에 대한 지원 솔루션의 열거를 적시에 중지하거나 최적의 솔루션이 없다는 결론을 따를 수 있는 기준을 설정하십시오.

선형 계획법 문제를 해결하기 위한 심플렉스 방법의 알고리즘

1. 문제를 표준 형식으로 가져오기
2. "단위 기준"으로 초기 참조 솔루션 찾기(참조 솔루션이 없으면 제약 조건 시스템의 비호환성으로 인해 문제에 솔루션이 없음)
3. 참조 솔루션을 기준으로 벡터 확장의 추정치를 계산하고 심플렉스 방법의 표를 채우십시오.
4. 최적 솔루션의 고유성에 대한 기준이 충족되면 문제의 솔루션이 종료됩니다.
5. 최적해 세트의 존재 조건이 충족되면 간단한 열거에 의해 모든 최적해가 발견됩니다.

심플렉스 방법으로 문제를 해결하는 예

심플렉스 방법을 사용하여 문제를 해결합니다.

해결책:

우리는 문제를 표준 형식으로 가져옵니다.

이를 위해 첫 번째 부등식 제약 조건의 왼쪽에 계수가 +1인 추가 변수 x 6을 도입합니다. 변수 x 6은 계수가 0인 목적 함수에 포함됩니다(즉, 포함되지 않음).

우리는 다음을 얻습니다.

초기 참조 솔루션을 찾습니다. 이를 위해 우리는 자유(미해결) 변수를 0 x1 = x2 = x3 = 0과 동일시합니다.

우리는 얻는다 참조 솔루션 X1 = (0.0.0.24.30.6) 단위 기준 B1 = (A4, A5, A6).

계산하다 벡터 분해 추정다음 공식에 따른 기준 용액을 기준으로 한 조건:

Δ k \u003d C b X k - c k

• C b = (с 1 , с 2 , ... , с m)은 기본 변수가 있는 목적 함수 계수의 벡터입니다.
• X k = (x 1k , x 2k , ... , x mk) 는 참조 솔루션의 기저에 대한 대응 벡터 A k 의 확장 벡터입니다.
• C k - 변수 x k에 대한 목적 함수의 계수.

기저에 포함된 벡터의 추정치는 항상 0과 같습니다. 참조 솔루션, 확장 계수 및 참조 솔루션의 기초 측면에서 조건 벡터의 확장 추정치는 다음과 같이 작성됩니다. 심플렉스 테이블:

표 위에는 추정치 계산의 편의를 위해 목적함수의 계수를 기재하였다. 첫 번째 열 "B"에는 참조 솔루션의 기초에 포함된 벡터가 포함됩니다. 이러한 벡터를 쓰는 순서는 제약 방정식에서 허용된 미지수의 수에 해당합니다. "With b"표의 두 번째 열에는 목적 함수의 계수가 동일한 순서로 기본 변수로 작성됩니다. "C b" 열에서 목적 함수의 계수를 올바르게 배열하면 기저에 포함된 단위 벡터의 추정치가 항상 0과 같습니다.

"A 0 "열의 Δ k 추정치가있는 테이블의 마지막 행에서 목적 함수의 값은 기준 솔루션 Z(X 1)에 기록됩니다.

최대 문제에서 벡터 A 1 과 A 3 에 대한 추정값 Δ 1 = -2, Δ 3 = -9가 음수이기 때문에 초기 기준 솔루션은 최적이 아닙니다.

참조 솔루션 개선 정리에 따르면 최대 문제에서 하나 이상의 벡터가 음수 추정값을 갖는 경우 목적 함수의 값이 더 큰 새로운 참조 솔루션을 찾는 것이 가능합니다.

두 벡터 중 어느 것이 목적 함수의 더 큰 증분으로 이어질 것인지 결정합시다.

목적 함수 증분은 다음 공식으로 찾을 수 있습니다.

다음 공식을 사용하여 첫 번째 및 세 번째 열에 대한 매개 변수 θ 01의 값을 계산합니다.

l = 1에 대해 θ 01 = 6, l = 1에 대해 θ 03 = 3을 얻습니다(표 26.1).

첫 번째 벡터 ΔZ 1 = - 6 * (- 2) = 12가 기저에 도입되고 세 번째 벡터 ΔZ 3 = - 3 * (- 9) = 27일 때 목적 함수의 증분을 찾습니다.

따라서 최적 해에 대한 더 빠른 접근을 위해서는 기저 A6의 첫 번째 벡터 대신 참조 솔루션의 기저에 벡터 A3를 도입해야 합니다. 왜냐하면 매개변수 θ 03의 최소값이 첫 번째 행에서 도달하기 때문입니다 (l = 1).

요소 X13 = 2로 조던 변환을 수행하고 B2 = (A3, A4, A5)를 기준으로 두 번째 참조 솔루션 X2 = (0.0.3.21.42.0)를 얻습니다. (표 26.2)

벡터 A2가 음수 추정값 Δ2 = -6을 가지므로 이 솔루션은 최적이 아닙니다. 솔루션을 개선하려면 벡터 A2를 기준 솔루션의 기초에 도입해야 합니다.

우리는 기저에서 파생된 벡터의 수를 결정합니다. 이를 위해 두 번째 열에 대한 매개변수 θ 02를 계산하고 l = 2에 대해 7과 같습니다. 따라서 기본에서 두 번째 기본 벡터 A4를 유도합니다. 요소 x 22 = 3으로 Jordan 변환을 수행하고 세 번째 참조 솔루션 X3 = (0.7.10.0.63.0) B2 = (A3, A2, A5)를 얻습니다(표 26.3).

이 솔루션은 기저에 포함되지 않은 모든 벡터에 대해 추정치가 양수이기 때문에 유일한 최적의 솔루션입니다.

Δ 1 \u003d 7/2, Δ 4 \u003d 2, Δ 6 \u003d 7/2.

대답:최대 Z(X) = X = (0.7,10,0.63)에서 201.

경제 분석의 선형 계획법 방법

선형 계획법생산에 사용되는 자원(고정 자산, 자재, 노동 자원)과 관련된 엄격한 제한에 직면하여 가장 최적의 경제적 솔루션을 정당화할 수 있습니다. 경제 분석에 이 방법을 적용하면 주로 조직 활동 계획과 관련된 문제를 해결할 수 있습니다. 이 방법은 출력의 최적 값과 조직에서 사용할 수 있는 생산 자원을 가장 효율적으로 사용하기 위한 방향을 결정하는 데 도움이 됩니다.

이 방법을 사용하여 극단값, 즉 변수 함수의 최대값과 최소값을 찾는 것으로 구성된 소위 극단 문제의 해결이 수행됩니다.

이 기간은 분석된 경제 현상이 선형적이고 엄격한 기능적 종속성에 의해 연결된 경우 선형 방정식 시스템을 푸는 것을 기반으로 합니다. 선형 계획법은 특정 제한 요인이 있는 변수를 분석하는 데 사용됩니다.

선형 계획법을 사용하여 소위 전송 문제를 해결하는 것은 매우 일반적입니다. 이 작업의 내용은 최대 고객 수에 서비스를 제공해야 하는 경우 차량 수, 운반 용량, 작업 기간에 대한 기존 제한 사항에 따라 차량 운영과 관련하여 발생하는 비용을 최소화하는 것입니다. .

또한 이 방법은 스케줄링 문제를 해결하는 데 널리 사용됩니다. 이 작업은이 직원의 구성원과 조직의 고객 모두에게 가장 적합한이 조직 직원의 기능 시간 분배로 구성됩니다.

목표는 사용 가능한 직원 수와 근무 시간을 제한하면서 서비스를 제공하는 클라이언트 수를 최대화하는 것입니다.

따라서 선형 계획법 방법은 다양한 유형의 자원 배치 및 사용 분석뿐만 아니라 조직의 활동을 계획하고 예측하는 과정에서 매우 일반적입니다.

그럼에도 불구하고 수학적 프로그래밍은 이러한 경제 현상에도 적용될 수 있으며, 그 사이의 관계는 선형이 아닙니다. 이를 위해 비선형, 동적 및 볼록 프로그래밍 방법을 사용할 수 있습니다.

비선형 계획법은 목적 함수나 제약 조건 또는 둘 모두의 비선형 특성에 의존합니다. 이러한 조건에서 목적 함수 및 제약 조건 부등식의 형태는 다를 수 있습니다.

비선형 프로그래밍은 경제 분석, 특히 조직 활동의 효율성을 나타내는 지표와이 활동의 ​​양, 생산 비용 구조, 시장 상황 등의 관계를 설정할 때 사용됩니다.

동적 프로그래밍은 의사 결정 트리 구축을 기반으로 합니다. 이 트리의 각 계층은 이전 결정의 결과를 결정하고 이 결정의 비효율적인 변형을 제거하는 단계로 사용됩니다. 따라서 동적 프로그래밍에는 다단계, 다단계 특성이 있습니다. 이러한 유형의 프로그래밍은 현재와 미래의 조직 발전을 위한 최상의 옵션을 찾기 위해 경제 분석에 사용됩니다.

볼록 계획법은 비선형 계획법의 한 유형입니다. 이러한 유형의 프로그래밍은 조직 활동의 결과와 조직에서 발생하는 비용 간의 관계의 비선형 특성을 나타냅니다. 볼록(그렇지 않으면 오목) 프로그래밍은 볼록 목적 함수와 볼록 제약 조건 시스템(특징점)을 분석합니다. 볼록 계획법은 비용을 최소화하기 위해 경제 활동 분석에 사용되며, 오목 계획법은 분석된 지표에 반대 방향으로 영향을 미치는 요인의 작용에 대한 기존 제한 조건에서 소득을 최대화하기 위해 사용됩니다. 결과적으로 고려 중인 프로그래밍 유형에서 볼록 목적 함수는 최소화되고 오목 함수는 최대화됩니다.

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

문제의 해결책

모델 빌딩

1차, 2차, 3차 유형의 셔츠를 통해 출시 예정인 셔츠의 수.

그러면 리소스 제한이 다음과 같이 표시됩니다.

또한 작업의 의미에 따라

받은 이익을 표현하는 대상 함수:

다음 선형 계획법 문제가 발생합니다.

선형 계획법 문제를 표준 형식으로 축소

문제를 표준 형식으로 가져오도록 합시다. 추가 변수를 소개하겠습니다. 계수가 0인 목적 함수에 모든 추가 변수를 도입합니다. 선호하는 형식이 없는 제약 조건의 왼쪽 부분에 추가 변수를 추가하고 동등성을 얻습니다.

심플렉스 방식으로 문제 풀기

심플렉스 테이블을 채우십시오.

최대값에 대한 문제를 풀고 있기 때문에 최대값에 대한 문제를 풀 때 인덱스 라인에 음수가 있으면 최적의 솔루션을 받지 못했고 0번째 반복의 테이블에서 다음으로 이동해야 함을 나타냅니다. 다음 것.

다음 반복으로의 전환은 다음과 같이 수행됩니다.

선행 열 일치

키 행은 사용 가능한 구성원과 선행 열의 구성원의 최소 비율(단순 비율)에 의해 결정됩니다.

키 열과 키 행의 교차점에서 활성화 요소, 즉 9.

이제 첫 번째 반복 컴파일을 시작하겠습니다. 단위 벡터 대신 vector를 도입합니다.

새 테이블에서 허용 요소 자리에 1을 쓰고 키 열의 다른 모든 요소는 0입니다. 키 문자열 요소는 허용 요소로 나뉩니다. 테이블의 다른 모든 요소는 직사각형 규칙에 따라 계산됩니다.

첫 번째 반복 일치에 대한 키 열

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

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

이를 위해 다음과 같이 정의하는 핵심 라인을 찾습니다.

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

인덱스 행에서 모든 멤버는 음수가 아니므로 선형 계획법 문제에 대한 다음 솔루션을 얻습니다(자유 멤버 열에서 작성).

1유형 셔츠 24벌, 2유형 셔츠 7벌, 3유형 셔츠 3벌을 재봉해야 합니다. 이 경우 수령 한 이익은 최대가되며 95 루블에 이릅니다.