실제로 선형 계획법 문제의 제약 조건은 종종 방정식이 아니라 부등식으로 주어집니다.
불평등 제약 조건이 있는 문제에서 선형 계획법의 주요 문제로 넘어가는 방법을 보여 드리겠습니다.
변수에 부과된 제약 조건이 선형 부등식의 형태를 갖는 변수에 대한 선형 계획법 문제가 있다고 가정합니다. 그들 중 일부에서는 불평등 기호가 될 수 있고 다른 것도 가능합니다 (두 번째 유형은 두 부분의 부호를 간단히 변경하여 첫 번째 유형으로 축소됩니다). 따라서 모든 부등식 제약 조건을 표준 형식으로 설정합니다.
부등식(4.1)을 만족하고 또한 선형 함수를 최소화하는 음수가 아닌 값 세트를 찾아야 합니다.
이런 식으로 제기된 문제에서 선형 계획법의 주요 문제로 쉽게 넘어갈 수 있습니다. 실제로 다음과 같은 표기법을 소개합니다.
여기에 "추가"라고 하는 몇 가지 새로운 변수가 있습니다. 조건(4.1)에 따르면 이러한 추가 변수는 음수가 아니어야 합니다.
따라서 우리는 다음 공식에서 선형 계획법의 문제에 직면합니다. 방정식 (4.3) 시스템을 충족하는 음수가 아닌 변수 값을 찾고 동시에 이러한 변수의 선형 함수를 최소화합니다.
보시다시피, 선형 계획법(LPP)의 주요 문제는 순수한 형태로 우리 앞에 있습니다. 식(4.3)은 기본 변수에 대해 이미 해결된 형태로 주어지며 자유변수로 표현된다. 함수 L은 "초기" 변수에 대해서만 표현됩니다("추가" 변수의 계수는 0과 같습니다).
따라서 우리는 불평등 제약 조건이 있는 선형 계획법 문제를 선형 계획법의 주요 문제로 축소했지만 원래 문제에 있었던 것보다 많은 수의 변수를 사용합니다.
예 1 부등식 제약 조건이 있는 선형 계획법 문제가 있습니다. 조건을 충족하는 변수의 음이 아닌 값을 찾습니다.
선형 함수 최소화
이 문제를 OLP 형태로 줄이는 것이 필요하다.
결정. 우리는 불평등(4.4)을 표준 형식으로 가져옵니다.
추가 변수를 소개합니다.
작업은 변수의 음이 아닌 값을 찾는 것입니다.
방정식(4.6)을 충족하고 선형 함수(4.5)를 최소화합니다.
우리는 부등식 제약 조건이 있는 선형 계획법 문제에서 ELP(등식 제약 조건) 문제로 전달하는 것이 가능한 방법을 보여주었습니다. 역전이는 항상 가능합니다 - LLP에서 부등식 제약 문제로. 첫 번째 경우에 변수의 수를 늘린 다음 두 번째 경우에는 기본 변수를 제거하고 자유 변수만 남겨두고 줄입니다.
예 2. 등식 제약 조건(OLP)이 있는 선형 계획법 문제가 있습니다.
그리고 최소화할 기능
부등식 제약 조건이 있는 선형 계획법 문제로 작성해야 합니다.
결정. , 우리는 변수 중 몇 개를 자유 변수로 선택합니다. 변수는 첫 번째 방정식(4 7)과 관련이 있기 때문에 자유 변수로 선택할 수 없습니다. 그 중 하나의 값은 다른 하나의 값에 의해 완전히 결정되고 자유 변수는 독립적이어야 합니다.
같은 이유로 변수를 자유 변수로 선택하는 것은 불가능합니다(두 번째 방정식으로 연결됨). 우리는 자유 변수로 선택하고 나머지는 모두 다음과 같이 표현합니다.
조건 (4 9)는 부등식으로 대체될 수 있기 때문에:
선형 함수 L의 표현을 자유 변수에 전달해 보겠습니다. 가져 오기.
T10. 선형 계획법 문제에 대한 설명
수학적 모델경제적 문제는 경제적 과정을 설명하는 일련의 수학적 관계입니다.
수학적 모델을 컴파일하려면 다음이 필요합니다.
1. 작업 변수를 선택합니다.
2. 제한 시스템을 작성합니다.
3. 목적 함수를 설정합니다.
작업 변수수량 x 1 , x 2 ,… , x n이 호출되며 이는 경제적 과정을 완전히 특성화합니다. 일반적으로 벡터 X \u003d (x 1, x 2, ..., x n)로 작성됩니다.
작업 제약 시스템는 문제의 변수에 의해 충족되고 제한된 자원 및 기타 경제적 조건(예: 변수의 긍정성)에 따라 발생하는 방정식과 불평등의 집합입니다. 일반적으로 다음과 같습니다.
목적 함수는함수 F(X) = f(x 1 , x 2 ,…
수학 프로그래밍의 일반적인 문제는 다음과 같이 공식화됩니다. 목적 함수의 극한값을 제공하는 작업 변수 x 1 , x 2 ,… , x n을 찾습니다.
F (X) \u003d f (x 1, x 2, ..., x n) ® 최대 (최소) (2)
제약 조건 시스템(1)을 충족합니다.
목적 함수(2)와 제약 조건 시스템(1)이 선형이면 수학적 프로그래밍 문제는 다음과 같습니다. 선형 계획법 문제(LPP).
벡터 X(작업 변수 집합)는 수용 가능한 솔루션, 또는 PLP 계획이 제한 시스템(1)을 충족하는 경우. 목적 함수의 극한값을 제공하는 실현 가능한 계획 X라고 합니다. 최적의 솔루션 ZLP.
2. 경제 문제의 수학적 모델 컴파일의 예
특정 생산 상황에 대한 연구는 제한된 자원의 최적 사용의 문제로 해석되는 ZLP로 이어집니다.
1.최적의 생산 계획 문제
두 가지 유형의 제품 T 1 및 T 2를 생산하기 위해 세 가지 유형의 자원 S 1 , S 2 , S 3 이 사용됩니다. 자원 재고, 생산 단위 제조에 소비되는 자원 단위 수 및 생산 단위 판매로 인한 이익이 표에 나와 있습니다.
판매 이익이 최대가 될 제품 생산 계획을 찾아야합니다.
결정.
x 1, x 2 - 생산을 위해 계획된 각각 T 1 및 T 2의 생산 단위 수를 표시합시다. 제조를 위해서는 (x 1 + x 2) 자원 S 1 단위, (x 1 + 4x 2) 자원 S 2 단위, (x 1) 자원 S 3 단위가 필요합니다. 자원 S 1 , S 2 , S 3의 소비는 각각 8, 20 및 5 단위의 매장량을 초과해서는 안됩니다.
그러면 문제의 경제-수학적 모델은 다음과 같이 공식화될 수 있습니다.
제한 시스템을 충족하는 생산 계획 X \u003d (x 1, x 2)를 찾으십시오. 
그리고 조건
그 아래에서 기능 최대값을 취합니다.
m 종류의 자원을 사용하여 n 종류의 제품을 생산하는 경우로 문제를 쉽게 일반화할 수 있습니다.
2.최적의 다이어트 문제
영양소 S 1 , S 2 및 S 3 을 함유한 식품 K 1 과 K 2 에는 두 가지 유형이 있습니다. 각 사료 유형 1kg의 영양소 단위 수, 필요한 최소 영양소 및 사료 1kg의 비용이 표에 나와 있습니다.
각 유형의 영양소 함량이 설정된 한도보다 적지 않은 최소 비용의 일일 배급량을 작성해야합니다.
결정.
x 1, x 2 - 일일 식단에 포함 된 사료 K 1 및 K 2의 양을 표시합시다. 그런 다음 이 식단에는 (3x 1 + x 2) 영양소 S 1 단위, (x 1 + 2x 2) 물질 S 2 단위, (x 1 + 6x 2) 영양소 S 3 단위가 포함됩니다. 식단에서 영양소 S 1 , S 2 및 S 3 의 함량은 각각 9, 8 및 12 단위여야 하므로 문제의 경제-수학적 모델은 다음과 같이 공식화할 수 있습니다.
제한 시스템을 충족하는 일일 식단 X \u003d (x 1, x 2)를 작성하십시오.
그리고 조건
그 아래에서 기능 최소값을 취합니다.
PLP 녹음 형식
LLP에서는 선형 목적 함수의 극한값을 찾아야 합니다.
제한 사항:
음이 아닌 조건
여기서 a ij , b i , c j ( , ) 에는 상수가 제공됩니다.
ZLP는 다음과 같이 작성됩니다. 일반형태. 제약 시스템이 부등식만 포함하는 경우 LLP는 다음과 같이 표시됩니다. 기준형태. 표준(기본) ZLP 표기법의 형식은 제약 시스템이 등식만을 포함하는 표기법입니다. 따라서 위의 LLP는 표준 형식으로 작성됩니다.
LLP의 일반, 표준 및 표준 형식은 각각 간단한 변환을 통해 다른 형식으로 다시 작성할 수 있다는 점에서 동일합니다. 즉, 이러한 문제 중 하나를 해결할 수 있는 방법이 있으면 문제에 대한 최적의 계획이 결정될 수 있습니다.
LLP 표기법의 한 형식에서 다른 형식으로 이동하려면 부등식 제약 조건에서 등식 제약 조건으로 또는 그 반대로 이동할 수 있어야 합니다.
부등식 제약 조건(£)은 왼쪽에 음이 아닌 변수를 추가하여 등식 제약 조건으로 변환할 수 있으며, 부등식 제약 조건(³)은 음수가 아닌 변수를 추가하여 등식 제약 조건으로 변환할 수 있습니다. 왼쪽. 추가로 도입된 음이 아닌 변수의 수는 변환된 부등식 제약 조건의 수와 같습니다.
도입 추가 변수가 경제적인 의미가 있음. 따라서 원본 PLP의 제약 조건이 리소스의 소비 및 가용성을 반영하는 경우 표준 형식의 추가 변수 PLP 값은 사용되지 않은 해당 리소스의 양과 같습니다.
실시예 1. 표준 형식 ZLP로 작성:
제한 사항:
결정.
목적 함수는 변경되지 않은 상태로 유지됩니다.
불평등 시스템은 평등 시스템으로 변환됩니다.
그래픽 방식으로 LLP를 풀 때 표준 형식에서 표준 형식으로의 전환이 필요합니다.
LLP를 표준 형식으로 가져오려면 다음을 사용하십시오. 요르단-가우스 방법 SLAU 솔루션. 시스템의 확장 행렬이 계단 형태로 축소되는 가우스 방법과 달리 Jordan-Gauss 방법에서는 단위 행렬이 확장 행렬의 일부로 형성됩니다. 따라서 여기서 역방향 이동이 필요하지 않습니다.
원본 표준 LLP를 동등한 표준 LLP로 변환하려면:
a) 0이 아닌 요소 a qp는 제약 시스템의 확장 행렬에서 선택됩니다. 이 요소는 관대한, 및 q - i 행 및 p번째 열 활성화 행 및 활성화 열이라고 함.
b) 해석 문자열은 변경 없이 다시 작성되고 해석 열을 제외한 해석 열의 모든 요소는 0으로 대체됩니다. 증강 행렬의 나머지 요소는 "사각형 규칙"을 사용하여 결정됩니다.
확장 행렬의 네 가지 요소인 변환할 요소 a ij , 해결 요소 a qp 및 요소 a ip 및 a qj 를 고려하십시오. 요소 a ij를 찾으려면 요소 a ij에서 직사각형의 반대쪽 꼭짓점에 있는 요소 a ip와 a qj의 곱을 뺀 값을 분해 요소 a qp로 나눈 값을 뺍니다.
c) 허용된 미지수는 동시에 목적 함수에서 제외됩니다. 이를 위해 목적 함수의 계수는 마지막 행의 확장 행렬에 기록됩니다. 계산은 마지막 줄의 활성화 요소를 선택할 수 없다는 점을 고려합니다.
실시예 2. 표준 형식으로 변경:
결정.
Jordan-Gauss 방법을 사용하여 LLP 제약 방정식 시스템을 등가 부등식 시스템으로 가져옵니다. 첫 번째 행의 세 번째 요소를 해결 요소로 선택하겠습니다.
마지막 행의 마지막 열에서 얻은 숫자 -9는 반대 부호로 목적 함수에 써야 합니다. 변환의 결과로 LLP는 다음과 같은 형식을 취합니다.
왜냐하면 변수 x 2 와 x 3 은 음수가 아니고 그것들을 버리면 대칭 형식으로 ZLP를 쓸 수 있습니다:
LLP의 표준 형식에서 목적 함수는 최소화 및 최대화될 수 있습니다. 최대값 찾기에서 최소값 찾기로 또는 그 반대로 이동하려면, 목적 함수 계수의 부호를 변경하는 것으로 충분합니다. F 1 = - F. 결과 문제와 원래 LLP는 동일한 최적 솔루션을 가지며 이 솔루션의 목적 함수 값은 다음과 같은 점에서만 다릅니다. 징후.
ZLP 속성
1. 선형 계획법 문제의 제약 시스템의 모든 허용 가능한 솔루션 세트는 볼록합니다.
점 집합이라고 합니다. 볼록한, 이 집합의 두 점을 연결하는 전체 세그먼트를 포함하는 경우.
이 정의에 따르면 그림 1a의 다각형은 볼록 집합이지만 그림 1b의 다각형은 볼록 집합이 아닙니다. 두 점 M과 N 사이의 선분 MN은 이 다각형에 완전히 속하지 않습니다.
볼록 세트는 다각형일 수 없습니다. 볼록 세트의 예로는 원, 섹터, 세그먼트, 큐브, 피라미드 등이 있습니다.
2. LLP에 최적의 솔루션이 있으면 선형 함수는 결정 다면체의 꼭짓점 중 하나에서 최대(최소) 값을 취합니다. 선형 함수가 둘 이상의 모서리 점에서 최대(최소) 값을 취하는 경우 이러한 점의 볼록 선형 조합인 임의의 점에서 취합니다.
점 X가 호출됩니다. 볼록 선형 조합점 X 1 , X 2 ,… , X n 다음 조건이 충족되면:
X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,
αj ≥ 0, Σαj = 1.
n = 2에 대한 특별한 경우 두 점의 볼록 선형 조합은 두 점을 연결하는 선분임이 분명합니다.
3. 표준 LLP 제약 시스템의 각 허용 가능한 기본 솔루션은 솔루션 다면체의 꼭지점에 해당하고 그 반대의 경우도 마찬가지입니다.
LLP에 최적의 솔루션이 있는 경우 허용 가능한 기본 솔루션 중 하나 이상과 일치한다는 것은 마지막 두 속성에서 비롯됩니다.
따라서, LLP 선형 함수의 극한은 허용 가능한 기본 솔루션의 유한한 수 중에서 찾아야 합니다.
정의. 선형 계획법(LP) -연구 방법의 과학 및 선형 제한이 부과되는 미지의 선형 함수의 극한(최대 및 최소) 값 찾기.
이 선형 함수는 표적,수학적으로 방정식 또는 부등식으로 작성된 제약 조건을 제한 시스템.
정의.목적 함수와 그 제약의 수학적 표현은 경제 문제의 수학적 모델.
에 일반보기선형 계획법(LP) 문제의 수학적 모델은 다음과 같이 작성됩니다.
제한 사항:
어디 x j- 알려지지 않은; 아이즈, 나, 씨제이상수가 주어집니다.
제약 시스템의 전체 또는 일부 방정식은 부등식으로 작성할 수 있습니다.
더 짧은 표기법의 수학적 모델은 다음과 같은 형식을 갖습니다.
제한 사항:
정의.선형 계획법 문제의 실현 가능한 솔루션(계획)은 벡터 = ( 엑스 1 , 엑스 2 ,..., x p),제한 시스템을 충족합니다.
허용 가능한 솔루션 세트는 허용 가능한 솔루션(ODD) 영역을 형성합니다.
정의.목적 함수가 극한 값에 도달하는 실현 가능한 솔루션은 선형 계획법 문제의 최적 솔루션이라고 하며 opt로 표시됩니다.
기본 허용 솔루션 (엑스 1 , 엑스 2 ,..., 엑스아르 자형 , 0, …, 0)은 참조 솔루션입니다. 여기서 아르 자형-제약 시스템의 순위입니다.
LP 문제의 수학적 모델은 정규적이거나 비정규적일 수 있습니다.
7. 그래픽 방식으로 선형 계획법 문제 풀기. 제약 조건 함수의 그래프. 레벨 라인.
선형 계획법 문제를 푸는 그래픽 방법
선형 계획법의 가장 간단하고 시각적인 방법은 그래픽 방법입니다. 두 개 이하의 자유 변수를 포함하는 경우 비정규 형식으로 제공된 두 개의 변수와 정규 형식의 많은 변수를 사용하여 LP 문제를 해결하는 데 사용됩니다.
기하학적 관점에서 선형 계획법 문제에서 허용 가능한 솔루션 집합에서 이러한 모서리 점 또는 점 집합이 검색되며, 여기서 가장 높은(낮은) 수준 선에 도달하고 가장 빠른 성장의 방향으로 다른.
LP 문제의 그래픽 솔루션에서 목적 함수의 극단값을 찾기 위해 벡터가 사용됩니다. 엘() 표면에 엑스 1 오 2 , 우리가 나타내는 . 이 벡터는 목적 함수에서 가장 빠르게 변화하는 방향을 보여줍니다. 즉, 벡터는 레벨 라인의 법선입니다. 엘()
어디 이자형 1 및 이자형 2 - 축을 따른 단위 벡터 황소 1 및 황소각각 2개; 따라서 = (∂L/∂x 1 , ∂L/∂х 2 ).
벡터 좌표는 목적 함수 계수입니다. 엘().레벨 라인의 구성은 실제 문제를 해결할 때 자세히 고려됩니다.
문제 해결 알고리즘
1. 우리는 문제의 제약 시스템에 대한 가능한 솔루션 영역을 찾습니다.
2. 벡터 만들기 .
3. 수평 라인을 그립니다 엘 0 , 수직인 것 .
4. 작업의 벡터 방향으로 레벨 라인을 최대로 반대 방향으로 이동합니다. , 최소한의 작업을 위해.
레벨 라인은 실현 가능한 솔루션 영역과 하나의 공통점만 가질 때까지 이동합니다. LP 문제의 고유한 해를 결정하는 이 점이 극한점이 됩니다.
레벨 라인이 ODT의 측면 중 하나와 평행한 것으로 판명되면 이 경우 해당 측면의 모든 지점에서 극한값에 도달하고 LP 문제는 무한한 수의 솔루션을 갖게 됩니다. 그러한 LP 문제가 있다고합니다. 대안 최적그리고 그 해는 다음 공식으로 주어진다.
여기서 0 ≤ 티≤ 1, 1 및 2 - ODS의 모서리 지점에서 최적의 솔루션을 제공합니다.
LP 문제를 정의하는 제약 조건이 모순되는 것으로 판명되면 LP 문제를 해결할 수 없습니다.
5.
우리는 극점의 좌표와 그 안에 있는 목적 함수의 값을 찾습니다.
실시예 3선택 최선의 선택제품 출시
이 회사는 크림과 초콜릿의 2가지 유형의 아이스크림을 생산합니다. 아이스크림 제조를 위해 우유와 필러의 두 가지 초기 제품이 사용되며 아이스크림 1kg당 비용과 일일 공급이 표에 나와 있습니다.
시장 조사에 따르면 버터 아이스크림에 대한 일일 수요는 초콜릿 아이스크림에 대한 수요를 초과하지만 100kg을 넘지 않습니다.
또한 초콜릿 아이스크림에 대한 수요는 하루 350kg을 초과하지 않는 것으로 나타났습니다. 크림 같은 아이스크림 1kg의 소매 가격은 16루블, 초콜릿 - 14루블입니다.
판매 수익을 극대화하기 위해 기업은 각 유형의 아이스크림을 얼마나 생산해야 합니까?
결정.나타내다: 엑스 1 - 크림 아이스크림의 일일 생산량, kg; 엑스 2 - 초콜릿 아이스크림의 일일 생산량, kg.
문제의 수학적 모델을 만들어 봅시다.
아이스크림 가격은 각각 16루블과 14루블로 알려져 있으므로 목적 함수는 다음과 같습니다.
아이스크림에 대한 우유에 대한 제한을 설정합니다. 크림 아이스크림의 소비량은 0.8kg이고 초콜릿 아이스크림의 경우 0.5kg입니다. 우유 400kg 재고. 따라서 첫 번째 부등식은 다음과 같습니다.
0.8x 1 + 0.5x 2 ≤400 - 첫 번째 부등식은 제한입니다. 나머지 부등식도 비슷한 방식으로 구성됩니다.
결과는 불평등의 시스템입니다. 각 불평등의 솔루션 영역은 무엇입니까? 이것은 각 부등식에 점 O(0:0)의 좌표를 대입하여 수행할 수 있습니다. 결과적으로 다음을 얻습니다.
수치 OABDEF-허용 가능한 솔루션의 영역. 벡터(16, 14)를 만듭니다. 레벨 라인 엘 0은 방정식 16x 1 +14x 2 =Const에 의해 제공됩니다. 예를 들어 숫자 0을 선택한 다음 16x 1 +14x 2 =0과 같은 숫자를 선택합니다. 그림에서 라인 L 0에 대해 0이 아닌 일부 양수가 선택됩니다. 모든 레벨 라인은 서로 평행합니다. 레벨 라인의 법선 벡터.
레벨 라인을 벡터 방향으로 이동합니다. 출구 지점 엘실현 가능한 솔루션 영역에서 0이 포인트입니다. 디, 좌표는 다음 방정식으로 주어진 선의 교차로 정의됩니다.
시스템을 풀면 점의 좌표를 얻습니다. 디(312.5; 300), 최적의 솔루션, 즉
따라서 회사는 하루에 버터 아이스크림 312.5kg과 초콜릿 아이스크림 300kg을 생산해야 하며 판매 수입은 9,200루블이 됩니다.
8. 임의의 선형 계획법 문제를 주요 문제로 축소.부등식에 의해 주어진 제약을 해당 방정식으로 변환합니다.
9.단순 방법. 방법의 특성 및 알고리즘, 적용 가능성.
심플렉스 방법으로 문제를 해결하려면 다음이 필요합니다.:
1. 최적의 참조 솔루션을 찾는 방법을 나타냅니다.
2. 한 참조 솔루션에서 다른 참조 솔루션으로의 전환 방법을 지정합니다. 여기서 목적 함수의 값은 최적에 더 가깝습니다. 즉, 참조 솔루션을 개선하는 방법을 나타냅니다.
3. 최적 솔루션에 대한 참조 솔루션 열거를 적시에 중지하거나 최적 솔루션이 없다는 결론을 전달할 수 있는 기준을 설정합니다.
선형 계획법 문제를 해결하기 위한 심플렉스 방법의 알고리즘
1. 문제를 표준 형식으로 가져오기
2. "단위 기준"으로 초기 지원 솔루션 찾기(지원 솔루션이 없는 경우 제약 시스템의 비호환성으로 인해 문제에 솔루션이 없음)
3. 참조 솔루션을 기준으로 벡터 확장의 추정치를 계산하고 심플렉스 방법의 표를 채웁니다.
4. 최적해의 유일성에 대한 기준이 만족되면 문제의 해가 종료된다.
5. 최적 솔루션 세트의 존재 조건이 충족되면 간단한 열거에 의해 모든 최적 솔루션이 발견됩니다.
10. 운송 작업.운송 문제의 초기 솔루션을 찾기 위한 정의, 유형, 방법.
운송 문제는 가장 일반적인 선형 계획법 문제 중 하나입니다. 그 목표는 과도하게 장거리, 다가오는 반복 운송을 제거하여 가장 합리적인 상품 운송 방법과 수단을 개발하는 것입니다.
1. 초기 참조 솔루션 찾기;
2. 이 솔루션의 최적성을 확인합니다.
3. 하나의 기본 솔루션에서 다른 솔루션으로 전환합니다.
1.
2. 매트 사용 지침. 경제의 모델.
수학적 모델을 사용하면 알려지지 않은 매개 변수의 최적 값을 결정할 수 있습니다. 경제 시스템의사결정 과정에서 중요한 것입니다. 수학 프로그래밍은 경제 시스템의 관리 과정에서 계획에 대한 최상의 옵션을 선택하는 과정을 최적화할 수 있는 장치를 제공할 뿐입니다.
수학적 통계, 최적화 방법, 경제 방법에 사용됩니다. 사이버네틱스, 실험 문제.
경제의 복잡한 프로세스와 현상을 연구할 때 모델링이 매우 자주 사용됩니다. 즉, 연구 대상의 고려된 특성을 잘 정의된 구체적인 표시입니다. 그 본질은 연구중인 현상이 다른 시간 및 공간 규모의 모델을 사용하여 실험 조건에서 재현된다는 사실에 있습니다. 모델은 연구 중인 시스템의 특정 특성을 연구하기 위해 재현하는 데 도움을 받아 특별히 생성된 개체입니다. 수학적 모델링은 연구 대상에 대한 정보를 얻는 가장 완벽하고 동시에 효과적인 방법입니다. 경제학에서 분석을 위한 강력한 도구입니다. 모델을 사용한 연구 결과는 구성된 모델이 고려 중인 현상에 충분히 적합할 때, 즉 실제 상황을 충분히 반영합니다.
2. 과학으로서의 수학 프로그래밍, 그 구조. 최적화 문제. 경제적 문제를 해결하는 데 고전적인 최적화 방법을 적용하는 데 어려움이 있습니다.
수학 프로그래밍극한 문제를 해결하기 위한 이론적 토대와 방법을 개발하는 응용 수학의 한 분야입니다.
수학 프로그래밍에는 여러 섹션이 포함되며 주요 섹션은 다음과 같습니다.
1. 선형 프로그래밍.이 섹션은 미지의 변수가 1차 수학적 관계에 포함되는 문제를 포함합니다.
2. 비선형 계획법.이 섹션에는 목적 함수 및(또는) 제약 조건이 비선형일 수 있는 문제가 포함됩니다.
3. 동적 프로그래밍.이 섹션에는 솔루션 프로세스를 별도의 단계로 나눌 수 있는 작업이 포함됩니다.
4. 정수 프로그래밍.이 섹션에는 알 수 없는 변수가 정수 값만 사용할 수 있는 작업이 포함되어 있습니다.
5. 확률적 프로그래밍.이 섹션에는 목적 함수 또는 제약 조건에 확률 변수가 포함된 작업이 포함됩니다.
6. 매개변수 프로그래밍.이 섹션에는 목적 함수 또는 제약 조건에서 알려지지 않은 변수의 계수가 일부 매개변수에 의존하는 문제가 포함됩니다.
수학적 프로그래밍 문제를 해결하기 위해 극한값을 찾는 고전적 방법을 사용하는 것은 어렵습니다. 수학적 프로그래밍 문제에서 목적 함수는 미지 변수의 허용 가능한 값 영역 경계에서 극한값에 도달하고 도함수가 존재하지 않기 때문입니다 경계 지점에서. 허용 가능한 점수의 완전한 열거는 중요한 숫자로 인해 불가능합니다.
3. 수학적 모델의 개념, 매트 유형. 모델
수학적 모델수학적 기호 및 표현으로 작성된 실제 현상 또는 프로세스의 추상화입니다. 경제 과정 및 현상의 수학적 모델을 경제 및 수학적 모델이라고합니다.
모델은 다음과 같이 나뉩니다.
1. 선의모든 종속성이 선형 관계로 설명되는 ,
2. 비선형, 비선형 관계가 있습니다.
3. 확률론적, 연구 중인 프로세스의 무작위 특성을 고려하여,
4. 결정론적, 모든 매개 변수의 평균 값을 고려합니다.
5. 동적연구 중인 시스템이 여러 기간에 걸쳐 개발 중인 것으로 간주되는 모델,
6. 공전, 시간 요소는 고려되지 않습니다.
7. 최적화에 따라 선택되는 모델 극단화어떤 기준,
8. 최적화되지 않은, 최적성 기준이 없습니다.
9. 매크로 모델(가정 전체)
10. 마이크로모델(경제의 개별 연결 또는 프로세스).
수학적 모델 유형: 선형, 비선형, 2차, 정수, 이산, 매개변수, 선형 분수, 동적, 확률론적
4. 수학 프로그래밍 문제에 대한 일반적인 설명.
수학 프로그래밍 문제에 대한 일반적인 설명을 고려하십시오.
수학적 프로그래밍의 일반적인 문제는 목적 함수의 최적 값을 결정하는 것이며 변수의 값은 허용 가능한 값의 특정 범위에 속해야 합니다. 수학적으로 최적해의 정의는 많은 변수의 함수의 극한값(최대값 또는 최소값)을 찾는 것으로 표현됩니다.
Z = f(x1, x2, …, xn)
이 변수의 주어진 변화 범위에서
기(x1, x2,…, xn)리비(i = 1, 2,…, m),
여기서 Ri는 ≥, =, ≤ 기호 중 하나입니다.
5. 생산 계획을 최적화하는 문제. 문제의 수학적 모델의 경제적 공식화 및 구성.
경제 환경:
회사가 생산 N사용하는 제품의 종류 중원료의 종류. 생산 단위 생산을 위해 엄격하게 정의된 한 가지 유형의 원자재가 사용됩니다. 기업의 각 유형의 원자재는 제한되어 있습니다. 회사는 생산 단위 판매로 일정 이익을 얻습니다. 기업이 최대 총 이익을 얻을 수있는 생산 계획을 찾아야합니다.
수학적 설정:
j를 제품 유형 j = 1, n의 인덱스라고 가정합니다.
i - 리소스 유형의 인덱스 i = 1, m
ij는 원자재 비용 나- 생산 단위 생산을 위한 유형 제이-번째 유형;
Аi는 i번째 유형의 사용 가능한 리소스 볼륨에 대한 주어진 제한입니다.
Pj - j 번째 유형의 생산 단위 판매로 얻은 이익.
xj는 j번째 유형의 출력 볼륨입니다.
z \u003d P1x 1 + P2x 2 + ... + Pnx n → 최대
a11x 1 + a12x 2 +…+ a1nx n ≤ A1
a21x 1 + a22x 2 +…+ a2nx n ≤ A2
…………………………….
a m1x1 + a m2x2 +…+ a m n x n ≤ Am
xj ≥ 0, j = 1, n
6. 다이어트의 임무. 문제의 수학적 모델의 경제적 공식화 및 구성.
경제 환경
일부 농장에서는 동물에게 먹이를 줍니다. 살찌는 데 사용 N사료의 종류. 영양소(칼슘, 인 등)의 함량은 각 종의 사료 단위당 알려져 있습니다. 동물의 적절한 영양을 위해서는 규정된 양 이상의 영양소를 섭취해야 합니다. 각 사료의 단가는 알려져 있습니다. 총 살찌는 비용이 최소화되는 동물에게 먹이를주기위한 식단을 결정할 필요가 있습니다.
수학적 설정:
j는 피드 유형의 인덱스, j = 1, n
i – 영양소 유형 지수, i = 1, m
Аi는 i번째 유형의 영양소의 일일 요구 섭취량입니다.
Сj는 j 번째 유형의 사료 단위 비용입니다.
알려지지 않은 변수를 소개하겠습니다.
хj - 동물 사료의 일일 양 j번째 보기고물.
도입된 표기법의 관점에서 이 문제는 다음과 같이 쓸 수 있습니다.
a11x1 + a12x2 +…+ a1nxn ≥ A1
a21x1 + a22x2 +…+ a2nxn ≥ A2
…………………………….
am1x1 + am2x2 +…+ 및 mnxn ≥Am
xj ≥ 0, j = 1, n
7. 운송 업무 . 문제의 수학적 모델의 경제적 공식화 및 구성.
경제 환경 :
사용 가능 중균질한 제품의 공급업체 및 N이 제품의 소비자. 각 공급자에서 각 소비자에게 생산 단위를 배송하는 데 필요한 알려진 단위 비용. 공급업체 재고가 제한되어 있습니다. 각 소비자의 제품에 대한 요구 사항도 알려져 있습니다.
총 운송 비용이 최소화되는 공급 업체에서 소비자로의 제품 운송 계획을 결정할 필요가 있습니다.
수학적 설정 :
표기법을 소개하자면 매개변수 설정:
j – 소비자 지수, j = 1, n
i – 공급업체 지수, i = 1, m
Аi는 i번째 공급업체에서 구할 수 있는 제품의 양입니다.
Bj - j 번째 소비자의 제품에 대한 수요량;
Cij는 i번째 공급자로부터 j번째 소비자에게 제품 단위를 운송하는 단위 비용입니다.
알려지지 않은 변수를 소개하겠습니다.
хij는 i번째 공급자에서 j번째 소비자까지의 제품 운송량입니다.
z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → 분
작업 제한.
I. 각 공급업체로부터 다음과 같은 가용 수량 이하로 제품을 인출할 수 있습니다.
x11 + x12 +…+ x1n ≤ A1
x21 + x22 +…+ x2n ≤ A2 (2)
…………………….
xm1 + xm2 +…+ xmn ≤ 오전
Ⅱ. 제품에 대한 각 소비자의 요구가 충족되어야 합니다.
x11 + x21 +…+ xm1 ≥B1
x12 + x22 +…+ xm2 ≥B2
……………………. (3)
x1n + x2n +…+ xmn ≥Bn
III. 비음성 조건: xij ≥0, i = 1, m ; j = 1, n
수학적 진술을 접힌 형태로 작성하는 것이 종종 편리합니다.
, 나는 = 1, m 
, j = 1, n
8. 과제 또는 과제를 선택하는 문제. 문제의 수학적 모델의 경제적 공식화 및 구성.
경제 환경 :
사용 가능 N일의 종류와 N공연자. 각 수행자는 하나의 작업만 수행할 수 있습니다. 각 출연자별로 각 작품을 수행하는 비용이 설정됩니다. 작업을 완료하는 데 드는 총 비용이 최소화되도록 수행자를 작업에 할당해야 합니다.
수학적 설정 .
주어진 매개변수에 대한 표기법을 소개하겠습니다.
나는 – 작품의 색인, 나는 = 1, m
j는 수행자 인덱스, j = 1, n
Cij는 j번째 실행자가 i번째 작업을 수행하는 비용입니다.
알려지지 않은 변수를 소개하겠습니다. 이 문제에서 알 수 없는 변수는 0 또는 1의 두 가지 값만 사용할 수 있습니다. 이러한 변수를 널 변수라고 합니다.
1 - j번째 수행자가 i번째 작업에 할당된 경우;
0 - 그렇지 않으면.
도입된 표기법의 관점에서 이 문제는 다음과 같이 쓸 수 있습니다.
z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → 최소
I 그룹 제한.
각 작업에는 한 명의 연주자만 지정되어야 합니다.
x11 + x12 +…+ x1n = 1
x21 + x22 +…+ x2n = 1
……………………..
xn1 + xn2 +…+ xnn = 1
Ⅱ. 제한 그룹.
각 실행자는 하나의 작업만 수행할 수 있습니다.
x11 + x21 +…+ xn1 = 1
x12 + x22 +…+ xn2 = 1
……………………..
x1n + x2n +…+ xnn = 1
x ij = ( 0,1) 나는 = 1, n ; j = 1, n
9. 재료 절단 문제. 문제의 수학적 모델의 경제적 공식화 및 구성.
경제 환경 .
절단을 위해 동일한 크기의 원료가 공급됩니다. 총 폐기물이 최소화되도록 주어진 양의 주어진 크기의 공백으로 절단해야합니다.
수학적 설정 .
표기법을 소개하겠습니다.
나는 공백의 인덱스이고,
Аi - i 번째 유형의 필요한 공백 수.
j - 절단 옵션 지수,
Cj는 옵션 j에 따라 초기 재료 단위를 절단할 때 폐기물의 크기입니다.
ij는 옵션 j에 따라 초기 재료의 단위를 절단할 때 i번째 유형의 블랭크의 수입니다.
알려지지 않은 변수의 표기법을 소개하겠습니다.
xj는 옵션 j에 따라 절단된 원료의 양입니다.
도입된 표기법의 관점에서 이 문제는 다음과 같이 쓸 수 있습니다.
z \u003d С1x1 + С2x2 + ... + Сnxn → 최소
a11x1 + a12x2 +…+ a1nxn = A1
a21x1 + a22x2 +…+ a2nxn = A2
…………………………….
am1x1 + am2x2 +…+ amnxn = 오전
xj ≥ 0, j = 1, n
수학적 모델을 사용하면 원자재를 최대 20%까지 절약할 수 있습니다.
절단의 수학적 모델은 두 단계로 구성됩니다.
첫 번째 단계에서 절단 옵션이 구성되며 그 결과 옵션 수 n의 값, 다른 절단 옵션(aij)으로 얻은 각 유형의 블랭크 수 및 값 폐기물(Cj)이 결정됩니다.
소스 재료 단위 절단 옵션의 구성은 다음 표의 형식으로 수행됩니다.
| 옵션 번호 |
공백 i1 |
i2 공백 |
빈 메신저 |
블랭크는 크기가 증가하지 않는 순서로 배열됩니다. 변형의 구성은 완전한 열거 방법으로 수행됩니다.
10. LP 문제 모델의 일반적인 형태와 특징
LLP의 일반적인 형식은 다음과 같습니다.
z \u003d С1x1 + ... + Сnxn 최대(최소)
a11 X1 + a12 X2 + … + a1n Xn R1 a1
a21 X1 + a22 X2 + … + a2n Xn R2 a2
………………………………………………….
am1 X1 + am2 X2 +…+ amnxn Rm 오전
xj ≥ 0, j = 1, k, k ≤ n
일반적으로 각 기호 R1 , R2 ,… , Rm 은 ≥, = 또는 ≤ 기호 중 하나를 의미합니다.
LP 문제 모델의 일반적인 형태는 다음과 같은 특징을 갖는다.
1. 제약 시스템은 방정식(강성 조건)과 부등식(비강성 조건)의 형태로 제시됩니다.
2. 모든 변수에 음수가 아닌 조건이 부과되지는 않습니다.
3. 목적 함수는 최대 또는 최소로 경향이 있습니다.
11. LP 문제 모델의 표준 형태와 특징
표준 형식은 다음과 같습니다.
목적 함수 z의 최대값 또는 최소값 찾기:
z = С1x1 + … + Сnxn → 최대(최소) (1)
다음 제한 사항이 적용됩니다.
a11 X1 + a12 X2 + … + a1n Xn ≤ a1
a21 X1 + a22 X2 + ... + a2n Xn ≤ a2
…………………………………………..
am1 X1 + am2 X2 +… + amn Xn ≥ am
xj ≥ 0, j = 1, k, k ≤ n
LP 문제 모델의 표준 형식의 특징은 다음과 같습니다.
1. 제한 시스템이 불평등(비경직 조건)의 형태로 제시됨
2. 모든 변수에 음수가 아닌 조건이 부과됩니다.
3. 목적 함수는 최대 또는 최소가 되는 경향이 있습니다.
12. LP 문제 모델의 정준적 형태와 그 특징
표준 형식은 다음과 같습니다.
목적 함수 z의 최소값 찾기:
z = С1x1 + … + Сnxn → 최소
다음 제한 사항이 적용됩니다.
a11 X1 + a12 X2 + ... + a1n Xn = a1
a21 X1 + a22 X2 + ... + a2nxn = a2
…………………………
am1x1 + am2 X2 +… + amn Xn = 오전
Xj ≥0, j = 1, n
표준 형식의 특징은 다음과 같습니다.
1. 제한 시스템은 방정식(엄격한 조건)의 형태로 제시됩니다.
2. 모든 변수에 음수가 아닌 조건이 적용됩니다.
3. 목적 함수는 다음과 같은 경향이 있습니다.
일부 출처에서는 표준 형식으로 제시된 LP 문제의 목적 함수가 최대가 되는 경향이 있습니다. 이것은 최대 목적 함수를 위해 개발된 알고리즘에 따라 문제를 해결하는 편의를 위해 수행됩니다.
13. LP 작업의 가능하고 허용 가능하며 최적의 기본 작업 계획, ODZ
정의 1.선형 계획법 문제의 모든 제약 조건을 충족하는 미지의 변수 값을 호출 허용 변수 값 또는 계획 .
정의 2.선형 계획법 문제에 대한 모든 계획의 집합을 변수의 허용 가능한 값 영역이라고 합니다( 오즈 ).
정의 3.목적 함수가 ODZ에서 최소(또는 최대) 값을 취하는 선형 계획법 문제의 계획을 호출합니다. 최적의 .
14. LP 작업의 레코드 유형: 확장, 접힘, 매트릭스, 벡터.
LP 문제 모델은 다양한 형태로 작성할 수 있습니다.
1. 모델 레코드의 확장 보기
Z = c1 X1 + c2 X2 + … + cn Xn → 최소
a11 X1 + a12 X2 + … + a1n Xn = a1,
a21 X1 + a22 X2 + … + a2n Xn = a2,
……………………………………………
a m1 X1 + am2 X2 + … + amn Xn = 오전,
Xj ≥ 0, j = 1, n.
2. 축소 보기:
,
Xj ≥ 0, j = 1, n.
3. 행렬 형식의 LP 문제 모델:
X ≥ 0
어디에 
a11 a12 … a1n X1 a1
A= a21 a22 … a2n , X= X2 , A0 = a2
… … … … … …
오전 1시 2시 ... 오전 X 3시
4. 벡터 형식의 LP 문제 모델:
어디에
X1 a11 a12 a1n a1
X2, a21, a22, a2n, a2
… … … … …
오전 1시 오전 2시 오전 2시
15. LP 문제의 표준 및 일반 형식에서 표준 문제로의 전환.연결 정리
일반 또는 표준 형식에서 표준 형식으로 이동하려면 다음 기술이 사용됩니다.
1. 변수 변환. 일부 변수 Xk가 양수가 아닌 경우(Xk ≤ 0), 새로운 변수 Xk "가 도입되어 Xk " = –Xk 가 됩니다. 분명히, Xk " ≥ 0. 그 후, 각 제약 조건 및 목적 함수에서 변수 Xk는 [ – 엑스 "].
어떤 변수 Xt가 어떤 값을 취할 수 있다면, 그것은 두 개의 음이 아닌 변수 Xt'와 Xt''의 차이로 대체됩니다. 즉, xt = Xt' – Xt''라고 가정합니다. 여기서 Xt' 0 ≥ Xt'' ≥ 0.
2. 제약 조건 변환.모델의 제약 조건 중 부등식의 형태가 있는 경우 왼쪽에서 더하기(부등식 유형이 ≤인 경우) 또는 빼기(부등식이 유형 ≥인 경우)를 통해 등식으로 변환됩니다. 이러한 변수를 균형 변수라고 합니다. 균형 변수는 계수가 0인 목적 함수에 포함됩니다. Balance 변수는 이미 존재하는 인덱스 값 이후에 순차적으로 인덱스 값을 취합니다. 예를 들어, 제한 시스템에 5개의 변수가 있는 경우 첫 번째 균형 변수는 X6이고 두 번째 변수는 X7 등입니다.
16. ZLP 모델의 표준 형식에서 표준으로의 전환
표준 형식에서 표준 형식으로 전달하려면 각각
부등식 시스템으로 대체될 방정식:
또 다른 방법은 연립방정식을 특수한 형태로 가져오고 일부 변수를 추가로 제거하는 것입니다.
Jordan-Gauss 방법을 사용하여 각 방정식에서 기본 변수를 선택합니다. 이러한 선택은 등가(기본) 가우스 변환의 도움으로 수행됩니다. 여기에는 다음이 포함됩니다.
a) 0이 아닌 상수에 의한 방정식의 곱
b) 다른 방정식의 방정식에 상수를 곱한 덧셈.
행렬이나 표의 형태로 변환하기 전에 선형 방정식의 초기 시스템을 작성하는 것이 편리합니다.
문제를 표준 형식으로 작성합니다.
17. 지지하는 초평면인 반평면의 초평면 개념.
18. 기하학적. 제약 조건 시스템의 해석 및 LP 문제의 목적 함수
19. 볼록 집합: 집합의 극단(모서리) 점. 볼록 다면체
정의집합 M은 다음에 속하는 임의의 두 점과 함께 볼록한 경우 주어진 세트, 그것은 또한 그들을 연결하는 세그먼트를 포함합니다.
 |
볼록 세트
정의집합 M의 점 x는 주어진 집합에 완전히 속하는 세그먼트의 내부가 아닌 경우 모서리 또는 극점이라고 합니다.
정리 1. 세그먼트의 모든 점은 모서리 점의 볼록 조합으로 표시될 수 있습니다.
x \u003d λ 1 A + λ 2 B
λ 1 , λ 2 ≥ 0 꼭짓점 A와 B의 점의 볼록 조합
λ1 + λ2 = 1
정리 2. 볼록 닫힌 집합의 모든 점은 모서리 점의 볼록 조합으로 나타낼 수 있습니다.
20. LP 문제를 해결하기 위한 그래픽 방식의 알고리즘
1. 원본 LPP가 표준 형식인지 확인하고 그렇지 않은 경우 작업을 표준 형식으로 변환해야 합니다.
2. 알 수 없는 변수의 수를 확인합니다. 이 숫자가 3보다 크면 그래픽 방식으로 문제를 해결할 수 없습니다(다른 방법이 있음). 효과적인 방법그러한 문제를 해결).
3. ZLP에 대한 변수의 허용 가능한 값 영역은 건설 중입니다.
4. 가이드 벡터를 구축 중입니다. 씨 .
5. 초기 등각선은 ODZ(방향 벡터에 수직)를 통해 그려집니다.
6. 벡터 방향으로 초기 등축의 정신적 움직임이 수행됩니다. 씨, 목적 함수의 최대값이 결정되면 반대 방향으로, 최소값이 결정되면 isoobjective가 ODZ에 대한 참조가 될 때까지. 기준 isocoel과 ODZ의 교차점이 문제의 최적점이 됩니다.
7. 최적점의 좌표를 결정하려면 해당 선형 방정식의 시스템을 풀어야 합니다.
8. 목적함수의 최적값을 찾기 위해서는 변수의 최적값을 목적함수에 대입하여 그 값을 계산하는 것이 필요하다.
20. 그래픽 알고리즘. LP 문제 해결 방법
그래픽 방식의 알고리즘.
1. 문제의 제약 시스템의 각 조건의 연속적인 구성에 의해 ODZ의 구성이 수행됩니다.
2. 방향 벡터 C는 목적 함수의 변수에 대한 계수로 구성됩니다.
3. 초기 등축선은 원점을 통해 방향 벡터에 수직으로 그려집니다.
4. 초기 isogoal은 isogoal이 a가 될 때까지 목적 함수의 최대값이 결정된 경우 벡터 C의 값이 증가하는 방향으로, 또는 최소값이 결정된 경우 반대 방향으로 정신적으로 이동합니다. ODZ에 대한 참조. 기준 isocoel과 ODZ의 교차점이 문제의 최적점이 됩니다.
5. 최적점의 좌표를 결정하려면 최적점이 위치한 교차점에서 해당 조건의 선형 방정식 시스템을 풀어야 합니다.
6. 목적함수의 최적값을 찾기 위해서는 최적점의 좌표를 목적함수에 대입하여 그 값을 계산할 필요가 있다.
23. LP 문제의 허용 가능한 값 범위 및 목적 함수에 대한 정리
ODZ 정리. LP 문제의 허용 가능한 솔루션 영역은 볼록 집합입니다(n차원 공간에서 닫히고 경계가 지정됨).
정리 2. 선형 계획법 문제의 목적 함수에 대해.
LLP 목적 함수는 변수의 허용 가능한 값 영역의 모서리 지점 중 하나에서 최적의 값을 취합니다. 목적 함수가 여러 모서리 점에서 최적의 값을 취하는 경우 이러한 모서리 점의 볼록 조합인 임의의 점에서 동일한 값을 취합니다.
24. 꼭지점에 대한 정리. 충분하고 필요한 조건
25. LP 문제 및 결론에 대한 솔루션의 속성에 대한 정리의 결과. 기준선의 개념입니다.
정리의 결과.
정의. 계획 = 양의 좌표가 선형 독립 벡터에 해당하는 (х1,х2,…,хn)을 호출합니다. 기본계획 PLP .
결과 1. 참조 계획에는 m개의 양수 좌표가 있습니다.
정확히 m개의 양의 좌표가 있는 경우 이러한 지지 설계를 비축퇴라고 하고 그렇지 않으면 퇴화합니다.
결과 2. ODZ의 각 코너 포인트는 참조 계획입니다.
27. 심플렉스 방법의 알고리즘.
심플렉스 방법으로 LP 문제를 풀 때 다음과 같은 일련의 작업을 수행해야 합니다.
1. LP 문제가 canonical 형태인지 확인한다. 그렇지 않은 경우 원본 모델을 표준 형식으로 변환해야 합니다.
2. 이 참조 계획에 대해 초기 참조 계획 및 목적 함수 값이 선택됩니다.
3. 초기 심플렉스 테이블이 구성됩니다.
4. 인덱스 라인의 최적성 추정값을 확인합니다. 긍정적인 추정치가 없으면 최적의 솔루션이 작성되고 알고리즘이 작업을 종료합니다. 그렇지 않으면 5번 항목이 충족됩니다.
5. 기본적으로 가장 큰 양수 추정치에 해당하는 벡터가 도입됩니다. 이 열을 활성화 열이라고 합니다.
6. 벡터는 기초에서 파생되며, 이는 공식 0으로 계산된 심플렉스 비율에 해당합니다.< Ө ≤ . 주어진 라인활성화 문자열이라고 합니다.
7. 새로운 심플렉스 테이블이 구축됩니다. 열 B와 C B는 그에 따라 변경됩니다. 나머지 테이블은 가우스 변환을 사용하여 이전 테이블에서 채워지며 인덱스 행은 m+1 행으로 간주되고 가우스 변환을 사용하여 변환됩니다. 우리는 이 알고리즘의 단락 4의 구현을 진행합니다.
각 테이블을 작성한 후 이전 단락에서 제공된 추정치를 계산하기 위한 공식을 사용하여 계산의 정확성을 확인할 수 있습니다.
28. 심플렉스 방법으로 문제를 해결하기 위한 기본 참조 계획의 선택 및 구성.
29. 심플렉스 테이블, 채우기. 인덱스 행 계수 계산 공식.
30 . 선형 계획법 문제의 계획에 대한 최적성 정리는 심플렉스 방법으로 문제를 해결하기 위한 최적성 추정 정리의 결과입니다.
정리 1: 시스템의 일부 벡터 Ā j에 대해
X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1
X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2
…………………………………………………..
X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m
Z j – c j > 0 관계가 충족되면 계획 X B0이 최적이 아니며 Z(X B1) ≤ Z(X B0)가 되도록 계획 X B1에 전달할 수 있습니다.
여기서 Z j = (С, Ā j)는 벡터의 스칼라 곱입니다.
C는 목적 함수 Z의 기본 변수에서 계수로 구성된 벡터입니다.
Ā j는 해당 벡터의 확장 계수를 기저 벡터로 나타낸 벡터이다.
c j는 변수 X j가 있는 목적 함수 Z의 계수입니다.
결과 ~에서 정리: 어떤 참조 계획의 모든 벡터 Ā 1 , Ā 2 , …< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.
따라서 정리와 결과를 통해 다음 지원 계획이 최적인지 여부를 설정할 수 있으며 그렇지 않은 경우 목적 함수의 값이 더 낮은 다른 지원 계획으로 전환해야 합니다.
논평. 정리와 결과는 문제가 최소 목적 함수를 갖는 표준 형식이라고 가정합니다. 그러나 심플렉스 방법은 최대 목적 함수를 사용하여 문제를 해결하는 데 사용할 수도 있습니다. 이 경우 추정치의 값을 분석할 때 그 반대의 의미가 사용됩니다. 즉, 모든 최적성 추정치가 음수(양수 또는 음수)가 아닌 경우 계획이 최적이 됩니다.
31. 기저에 진입하고 기저로부터 유도되는 벡터의 선택. 심플렉스 관계.
새 참조 계획으로 전환하려면 자유 벡터 중 하나가 필요합니다. 
기저에 입력하고 기저 벡터의 일부를 출력합니다. 기초에 도입하기 위해 우리는 적어도 하나의 양의 좌표를 갖는 벡터를 선택합니다. 벡터 A m+1을 그러한 벡터라고 하자.
분해 -
대응 벡터, 고양이. 좌표가 음수가 아니고 양수 좌표의 수가 m인 경우 참조 계획이 됩니다.
X1 벡터 좌표는 음수가 아니어야 합니다. .
만약 
, 이 좌표는 음수가 아닙니다.
i = 1에서 관계식 (5)의 최소값을 얻으면 다음을 취하면
그런 다음 벡터 1의 첫 번째 좌표 엑스제로가 됩니다.
관계식 (6)이 호출됩니다. 심플렉스 관계. 따라서 우리는 원래 기준선 0에서 이동했습니다. 엑스(기본 벡터 A1, A2, ... Am) 참조 계획 1 엑스(기본 벡터 А2,А3,…,Аm, Am+1).
32. 테이블의 허용 요소, 선택. 심플렉스 테이블 재계산을 위한 전체 조던 제거 규칙.
33. 심플렉스 테이블 재계산을 위한 사변형 규칙
34. 심플렉스 방법으로 LP 문제를 해결할 때 최적 계획의 고유성, 최적 계획 세트 및 최적 계획의 부재의 표시.
심플렉스 방법으로 문제를 해결할 때 다음 유형의 최적 솔루션이 가능합니다.
1. 독창성 . 모든 자유 벡터의 추정값이 완전히 음수이면 얻은 지원 설계가 최적이고 고유합니다. (이전 단락의 예를 참조하십시오).
2. 대안적 최적(최적 솔루션 세트).
자유 벡터의 비양성 추정치 중 하나 이상의 0 추정치가 있으면 얻은 지원 설계가 최적이지만 유일한 것은 아닙니다. 이 경우 다른 지원 계획(0 추정치에 해당하는 벡터를 기저에 도입)으로 이동한 다음, 얻은 최적 지원 계획의 볼록 조합으로 일반 최적 솔루션을 작성할 수 있습니다.
3. LLP는 목적 함수가 아래에서 경계가 없기 때문에 최적의 솔루션이 없습니다. . 심플렉스 테이블에 양수 추정치가 있고 이 열의 모든 요소가 음수이고 0이면 이 벡터를 기저에 도입할 수 있습니다. 그러나 기저 벡터는 기저에서 추론할 수 없습니다. 이로부터 비지원 계획으로 전환할 때 목적 함수의 추가 감소가 가능하다는 것을 알 수 있습니다.
4. 제약 조건 시스템이 일관되지 않기 때문에 LLP에는 최적의 솔루션이 없습니다. LLP를 풀 때 일반적인 심플렉스 방법은 초기 참조 계획이어야 하므로 선형 방정식 시스템은 확실히 일관성이 없습니다. 따라서 일반적인 심플렉스 방법으로 풀면 이러한 경우가 발생할 수 없습니다.
5. ODZ가 하나의 점으로 구성된 경우 이러한 문제의 솔루션은 간단하며 심플렉스 방법을 사용하지 않고도 얻을 수 있습니다.
35. 인공기저법은 언제 사용하나요?
인공의.
36. 인공기저법에서 M 문제의 구성
그러나 선형 계획법 문제가 정준 형식이면 모든 방정식에 기본 변수가 포함되지 않습니다. 즉, 원래 기준선이 없습니다. 이 경우 기본 변수가 없는 방정식에서 계수가 +1인 음이 아닌 변수를 추가해야 합니다. 이와 같은 변수를 인공의.
인공 변수는 매우 큰 양수로 목적 함수에 추가되어야 합니다(목적 함수는 최소값을 찾는 것이기 때문입니다). 이 숫자는 라틴 문자 M으로 표시됩니다. +∞와 같은 것으로 간주할 수 있습니다. 이와 관련하여 때때로 인공 기저 방법을 M-방법이라고 합니다. 이러한 원래 문제의 변형을 확장 문제의 구성이라고 합니다. 인공 변수를 찾기 위해 목적 함수로 문제를 해결하는 경우 매우 큰 양수를 목적 함수에 추가해야 합니다(목적 함수는 최소값을 찾는 것이기 때문에). 이 숫자는 라틴 문자 M으로 표시됩니다. +∞와 같은 것으로 간주할 수 있습니다. 이와 관련하여 때때로 인공 기저 방법을 M-방법이라고 합니다. 이러한 원래 문제의 변형을 확장 문제의 구성이라고 합니다. 최대값을 찾기 위해 목적 함수로 문제를 해결하는 경우 인공 변수는 계수 -M을 사용하여 목적 함수에 들어갑니다.
따라서 확장된 문제에는 기준선이 있습니다(일부 기본 변수는 인위적이지만).
초기 심플렉스 테이블이 구성됩니다.
37. 인공 베이시스 방식으로 인덱스 라인 구축
추정치가 두 개의 항으로 구성되기 때문에 인덱스 행이 두 개의 행으로 분할되는 초기 단순 테이블이 작성됩니다. 상단 라인은 M이 없는 추정치의 항을 포함하고, 하단 라인은 M의 계수를 보여줍니다. 추정치의 부호는 M이 없는 항의 값과 부호에 관계없이 M 계수의 부호에 의해 결정됩니다. M은 매우 큰 양수입니다.
따라서 베이시스에 도입되는 벡터를 결정하기 위해서는 하위 지수선을 분석할 필요가 있다. 인공 벡터가 기저에서 파생된 경우 이중 문제에 대한 솔루션을 얻을 필요가 없는 경우 후속 단순 테이블의 해당 열을 생략할 수 있습니다(다음 항목 참조).
모든 인공 벡터가 기저에서 제거된 후 맨 아래 행은 인공 벡터에 해당하는 추정값을 제외하고 모든 요소가 0입니다. 그들은 -1과 같을 것입니다. 이러한 선은 고려 사항에서 제거할 수 있으며 이중 문제에 대한 솔루션을 얻을 필요가 없는 경우 일반적인 단순 방법으로 추가 솔루션을 수행할 수 있습니다(다음 항목 참조).
38. 인공 기반 방법의 최적성 기준. 기호는 원래 작업의 초기 기본 계획의 구성입니다.
39. 이중 심플렉스 방법의 알고리즘
이중 심플렉스 방법의 알고리즘:
1. 무료 회원의 표시에 관계없이 일반적인 방법으로 첫 번째 심플렉스 테이블을 채 웁니다. 그러한 문제는 초기 단위 기반이 있어야 한다고 믿어집니다.
2. 자유 회원 A0 열의 절대 음수 요소 중 가장 큰 기준선 선택
3. 가이드 라인의 음수 요소에 대한 인덱스 라인의 요소 비율의 최소 절대값에 따라 가이드 컬럼이 선택됩니다.
4. 전체 Jordan 제거 규칙에 따라 심플렉스 테이블을 다시 계산합니다.
5. 접수된 계획이 허용 가능한지 확인합니다. 수용 가능한 참조 계획을 얻는 신호는 A0 열에 부정적인 요소가 없다는 것입니다. A0 열에 부정적인 요소가 있으면 두 번째 단락으로 이동하십시오. 아무 것도 없으면 일반적인 방법으로 문제를 해결합니다.
6. 이중 심플렉스 방법으로 최적해를 구한다는 신호는 일반 심플렉스 방법의 최적성 기준이다.
41. 개방형 및 폐쇄형 운송 모델. 개방형 운송 모델에서 폐쇄형 운송 모델로의 전환.
운송 작업의 유형.
사용 가능 중제품 재고가 알려진 동종 제품 공급업체 및 N주어진 양의 수요를 가진 이러한 제품의 소비자. 운송의 단위 비용도 알려져 있습니다.
제품 재고량의 합이 모든 소비자의 요구량과 같으면 그러한 문제를 폐쇄 운송 작업
(즉, ∑ Ai = ∑ Bj인 경우), 그렇지 않으면 운송 문제를 호출합니다. 열려 있는. 운송 문제를 해결하려면 닫을 필요가 있습니다.
열린 운송 작업은 다음과 같은 방법으로 닫힌 작업으로 변환할 수 있습니다.
∑Ai > ∑Bj라고 하자. 이 경우 수요량이 ∑Ai – ∑Bj인 가상의 n + 1 소비자를 도입해야 합니다. 공급자로부터 가상의 소비자까지 운송하는 단위 비용은 실제로 그러한 운송이 아니므로 0으로 가정합니다. 수행되며 제품의 일부는 공급업체에 남습니다.
만약 ∑Bj > ∑Ai . 이 경우, 재고량이 ∑Bj – ∑Ai 인 가상의 m + 1 공급자를 도입해야 합니다. 가상의 공급자에서 소비자까지 운송하는 단위 비용은 실제로 그러한 운송이 수행되지 않고 소비자가 제품의 일부를 받지 못할 것이기 때문에 0과 같다고 가정합니다.
42. 수송 문제에서 초기 분포를 구성하는 방법: 북서쪽 모서리 방법 및 행렬의 최소 요소 방법.
참조 계획을 구성하기 위한 노스웨스턴 기법. 이 기술에 따르면 트래픽 값의 형성은 s.-z로 시작됩니다. 테이블 코너, 즉 x11 셀에서. 이 방법에 따르면 우선 1차 공급자의 상품이 유통된다. 또한 1차 공급자가 먼저 1차 소비자를 최대한 만족시킨다. 그런 다음 공급자가 여전히 상품을 보유하고 있는 경우
행렬에서 가장 작은 요소의 방법입니다.
이 방법의 본질은 가능한 최대 공급이 항상 매트릭스의 가장 낮은 관세에 해당하는 셀에 있다는 사실에 있습니다.
먼저 라인의 최저 가격이 관찰되는 라인의 셀에 표시(예: ▼ 기호)를 만듭니다. 그런 다음 테이블을 열별로 이동하고 가장 낮은 가격이 열별로 있는 셀에 동일한 메모를 작성합니다.
추가 분포는 먼저 두 개의 표시가 있는 셀에 대해 가능한 한 멀리 만든 다음 - 하나의 표시로 이루어진 다음 문제가 (m + n - 1) 채우기로 재조정됩니다. 테이블을 왼쪽에서 오른쪽으로, 위에서 아래로 전달할 때 채우기를 구성합니다.
43. 운송 업무의 속성
수송 문제는 다음 정리에 반영될 수 있는 몇 가지 속성을 가지고 있습니다.
정리 1. 닫힌 운송 문제에는 항상 솔루션이 있습니다.
정리 2. 제품 재고량과 수요량이 정수이면 운송 문제의 해도 정수가 됩니다.
정리 3. 닫힌 운송 문제의 제약 조건 시스템은 항상 선형 종속적입니다.
이 정리에 따르면 폐쇄된 운송 문제의 분포는 항상 m + n – 1개의 기본 변수와 (m – 1) (n – 1)개의 자유 시간 변수를 갖습니다.
44. 운송 문제의 분포를 퇴화하여 퇴화를 제거합니다. 교차된 조합입니다.
세포의 수가 m + n - 1보다 작으면 분포를 퇴화라고 합니다.
45. 수송 문제에 대한 최적성 정리.
정리.운송 작업의 일부 배포를 위해
조건이 충족됩니다:
ㅏ). ui+vj = 점유 셀의 경우 cij
비) ui+vj ≤ сij, 자유 셀의 경우,
이 분포가 최적입니다.
ui 값을 행 전위라고 하고 vj 값을 열 전위라고 합니다.
46. 잠재력 및 계산 방법.
행과 열의 가능성을 찾기 위해 최적성 정리의 조건)에 따라 다음과 같은 추론이 사용됩니다.
이 조건에 따른 방정식의 수는 m + n – 1이고 미지수 ui와 vj의 수는 m + n입니다. 저것. 변수의 수가 방정식의 수보다 많고 모든 방정식은 선형 독립입니다. 이러한 선형 방정식 시스템의 솔루션은 무한하므로 전위 중 하나에 값을 할당해야 합니다. 실제로, ui = 0. m + n – 1개의 미지수 변수가 있는 m + n – 1 방정식의 시스템이 획득됩니다. 이 시스템은 어떤 방법으로도 해결할 수 있습니다. 실제로 전위를 계산하기 위해 전위 중 하나가 알려진 점유 셀이 고려되고 정리의 조건 a)에 따라 나머지 알려지지 않은 전위의 값이 계산됩니다.
47. 운송 작업 분배의 최적성 추정치 및 최적성 기준 계산.
정리의 관계 b)를 기반으로 추정치를 계산하기 위해 다음 공식을 작성할 수 있습니다. δ 아이= ui + vj – сij. 추정치를 교통량과 혼동하지 않기 위해 추정치를 원으로 묶습니다.
자유 TK 세포의 최적성 추정치는 최적성에 대한 분포를 확인하는 최적성 기준입니다. 모든 자유 셀의 추정치가 0보다 작거나 같으면 이 분포가 최적입니다.
48. 운송 문제의 보급품 재분배
분배가 최적이 아니면 공급을 재분배해야 합니다.
재분배를 위해 재계산 주기가 구축됩니다. 가장 높은 양성 점수를 받은 셀이 셀로 선택됩니다. 이 셀에는 "+"기호가 표시되어 있습니다. 즉, 일정량의 배달을 기록해야합니다. 그러나이 열의 균형이 방해를 받으므로이 열의 점유 셀 중 하나에 "-"기호를 표시해야합니다. 즉, 공급량을 같은 양만큼 줄여야합니다. 그러나이 라인의 균형이 변경되므로이 라인의 일부 점유 셀에 "+"기호를 표시해야합니다. 이 과정은 원래 셀이 있던 줄에 "-" 기호가 놓일 때까지 계속됩니다.
모든 자유 셀의 경우 재계산 주기가 있으며 또한 유일한 주기가 있습니다.
49. 재분배 사슬, 그 유형.
고려중인 운송 계획이 최적이 아닌 경우, 즉 긍정적인 상대 추정치가 있습니다. 그런 다음 비우호적인 셀(비호의적 셀 중 하나)을 선택하고 이에 대한 재계산 주기가 구축되며 이에 따라 계획된 운송이 재분배됩니다. 주기는 닫힌 닫힌 선의 형태로 만들어지며, 이 선의 세그먼트는 기둥을 따라 또는 선을 따라 실행됩니다. 파선의 모서리 중 하나에는 제품을 주장하는 불리한 셀이 있고 다른 모서리에는 셀이 채워져 있습니다. 주기를 구성할 때 우리는 후보 셀에서 시작하여 점선을 따라 후보 셀로 돌아오지만 채워진 셀(기본 변수에 해당)에서만 회전할 수 있습니다. 불리한 셀이 제품 Q에 대한 소유권을 주장하게하십시오. 테이블의 불균형을 방지하려면 다음이 필요합니다.
사용 가능한 트래픽에 Q를 더하거나 뺍니다. 모서리의 수가 짝수이므로 셀의 절반에 Q를 더하고 나머지 절반에서 뺍니다. 주기는 후보 셀에서 시계 방향 또는 시계 반대 방향으로 시작되어 거기에 좋은 Q를 배치한 다음 인접 셀에서 Q를 뺀 다음 추가하는 방식으로 진행됩니다. Q 자체의 값은 셀 중 하나가 비어 있지만 공급이 음수가 되지 않도록 선택됩니다.
이렇게 하려면 Q를 빼는 셀 중 가장 작은 환원과 동일한 Q를 선택해야 합니다. 다음 그림에서. 7.1 및 7.2에서는 주기와 계산 규칙의 예를 보여줍니다.
이 경우 두 개의 셀이 비워집니다. 그러나 하나의 셀만 서로 비어 있어야 합니다. 그들은 이것을 합니다: 비우는 셀 중 하나는 새 테이블에서 비워지고 다른 비우는 셀에는 0이 놓입니다. 이 셀은 새 테이블에서 기본(채워진) 것으로 간주됩니다.
50. 재분배 양의 선택.
운송된 제품의 부피 결정. 실사 주기를 통해 이동된 제품의 양을 결정할 때 다음 두 가지 고려 사항에서 진행해야 합니다.
a) 테이블의 셀에서 변환한 후 음수를 얻지 않아야 합니다.
b) 점유된 셀 중 하나가 비어 있어야 합니다.
이러한 조건을 충족하려면 다음과 같이 운송되는 제품의 부피를 선택해야 합니다. θ=min(хij) - 여기서 (хij)는 "-로 표시된 재계산 주기의 셀에서 운송되는 부피입니다. ".
θ = 최소(20;30)=20
θ는 "+"기호로 표시된 셀의 값에 추가됩니다. θ는 "-"기호로 표시된 셀의 값에서 뺍니다. 나머지 셀의 공급 값은 변경 없이 덮어씁니다. 결과적으로 다음 표를 얻습니다.
53. 전위 방법의 알고리즘.
연산:
1. 작업에 대한 방정식이 만족되는지 확인 
그렇지 않은 경우 가상의 공급자 또는 소비자가 작업에 도입됩니다.
2. 작업 조건은 transport.table 형식으로 작성됩니다.
3. 초기 베이스라인 구축 중
4. 공급 및 소비자의 잠재력이 결정됩니다.
5. 자유 세포 점수가 계산됩니다. 모두 부정적이지 않은 경우 계획이 최적이며 답을 작성해야 합니다. 운송 매트릭스 X 및 운송 비용의 금액을 결정합니다. 계획이 최적이 아닌 경우, 즉 추정치 중 음수 값이 있는 경우 가장 큰 음수 값을 가진 유망한 셀을 선택하십시오. 다음으로 크기를 추정하고 전달합니다.
6. 퍼스펙티브 셀을 로드합니다. 운송 테이블의 형태로 새로운 기본 계획을 준비하십시오. 4번 항목으로 이동합니다.
54. 제품의 생산 및 운송 비용에 대한 회계. 공급이 금지된 운송 작업.
일부 문제를 해결할 때 상품 운송 비용뿐만 아니라 운송 제품 생산 비용도 고려해야 합니다. 이렇게 하려면 매트릭스 transp. 작업
여기서 Cij '는 생산량 한 단위를 생산하는 데 드는 절감된 비용입니다.
Cij "- 한 생산 단위를 운송하는 비용.
공급 금지 작업.
어떤 경우에는 어떤 경로로든 제품을 운송할 수 없습니다.
이를 위해 운송이 금지된 운송 태스크의 매트릭스에 금지 관세 M을 입력하고, 또한 통상적인 방법으로 태스크를 해결하지만, 이 셀은 항상 음의 셀 점수에 해당하게 된다. .
55. 운송 문제에서 특정 배달의 의무적 특성을 고려하여 경로 처리량에 대한 제한을 고려합니다.
경로 처리량에 대한 제한을 고려합니다.
일부 운송 작업에서는 일부 경로에서 더 작은 처리량소비 지점의 수요를 충족시키는 데 필요한 것보다.
운송 문제에서 특정 배송의 필수 특성을 고려합니다.
경우에 따라 작업은 예를 들어 Ak B 경로를 따라 볼륨 A 단위의 배송을 수행해야 합니다. 이 경우 A점의 생산량과 S Bs의 생산량에서 의무공급량을 차감하고 선택공급량에 대한 문제를 해결한다. 최적의 솔루션을 얻은 후 공급은 반드시 Ak Bs 셀에 서 있는 볼륨에 추가됩니다.
56. 경제적으로 가능한 결론. 열린 운송 문제에 대한 최적 분포의 해석.
최적의 분배를 받은 후에는 원래의 문제로 돌아가 적절한 경제성을 확보해야 합니다. 결과. 그것들은 다음과 같습니다:
1. 소비 지점이 도입되는 경우, 이는 분석 시스템에 과도한 생산량이 있음을 의미하며 고려 중인 시스템을 침해하지 않고 해당 생산 지점의 용량을 구속력 있는 양만큼 감소시킬 수 있음을 의미합니다. 그것은 가상의 소비 지점과 연결되어 있습니다.
2. 가상의 생산지가 도입된다면, 이는 실제 생산지의 생산능력이 충분하지 않고 증가될 필요가 있음을 의미한다. 가상의 생산 지점에 연결된 소비 지점에 가장 가까운 생산 지점의 용량이 증가합니다. 바인딩 값만큼 제조업체의 용량이 증가합니다. 이렇게하려면 가상의 생산 지점과 연결된 소비 지점 열을 고려하고 가장 낮은 관세를 찾으십시오. 이 관세에 해당하는 생산점의 생산능력을 구속력만큼 증가시키는 것이 가장 효율적이다.
57. 이중성의 개념. 생산 계획 최적화 문제의 예에 대한 이중 문제의 경제적 공식화.
이중 문제는 원래 문제 또는 직접 문제의 조건에서 직접 특정 규칙을 사용하여 공식화된 선형 계획법의 보조 문제입니다.
생산 계획을 최적화하는 작업이 있습니다. 다음과 같습니다.
초기 작업:
a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1
a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | 2시에
……………….. |.. (1)
ㅏ 티 1 x 1 +a 티 2 x 2 + ... + 에이 티 n x n ≤v 1 | ~에 티
x j ≥0, j = 1,n(2)
z = c 1 x 1 +c 2 x 2 +…+c n x n ->최대(3)
X \u003d (x 1, x 2, ..., x n)
a ij - j 번째 유형의 제품 생산에 사용되는 i 번째 유형의 원자재 수
이중 문제
어떤 이유로 든 기업이 제품을 생산할 수 없도록하십시오. 다운타임 비용을 줄이기 위해 회사는 보유한 원자재를 판매할 수 있습니다. 원자재를 얼마에 팔아야 할까?
i - 기업에서 사용 가능한 i 번째 유형의 원자재 가격.
에이 11 y 1 + 에이 21 y 2 + ... + 에이 티 1년 티≥s 1
a 12 x 1 + a 22 y 2 + ... + a 티 2 x n ≥s 2
……………….. (1’)
ㅏ 1p y 1 +a 2p y 2 +…+ 에이 티피~에 티≥s 피
나는 ≥0, j = 1,m(2')
F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3')
58. 직접 및 이중 문제의 구조적 요소 간의 대응
각 선형 계획법 문제는 연관될 수 있습니다.
다음 규칙에 따른 이중 작업:
1. 원래 문제의 모든 제약 조건에서 자유 항은 다음과 같아야 합니다.
오른쪽에 있고 미지수가 있는 항이 왼쪽에 있습니다.
2. 제약 조건 - 원래 문제의 부등식에는 부호가 있어야 합니다.
한 방향으로 향합니다.
3. 원래 문제의 목적 함수가 최소화되면 부등식 제약 조건은 "≤" 기호로 작성되어야 합니다. 그러면 이중 문제에서 목적 함수는 최소화되고 부등식 제약 조건의 기호는 "≥"가 됩니다.
4. 원래 문제의 각 제약 조건은 다음의 변수에 해당합니다.
이중 작업. 변수가 부등식에 해당하면 음수가 아니며, 동일성에 해당하면 변수는 부호에 대한 제한이 없습니다("임의").
5. 이중 문제의 제약 조건에서 변수의 계수는 다음으로 구성된 행렬을 전치하여 얻습니다.
원래 문제의 변수에 대한 계수.
6. 원래 문제의 자유 항은 다음의 계수입니다.
쌍대 문제의 목표 함수에 있는 변수 및 자유
쌍대 문제의 항은 다음 변수의 계수입니다.
우리는 또한 이중성 관계가 상호적이라는 점에 주목합니다. 이중 작업에 대한 이중 작업은 원래 작업과 일치합니다. 이중 작업 쌍은 대칭 및 비대칭으로 나뉩니다. 대칭 쌍에서 원시 및 쌍대 문제의 제약 조건은 엄격하지 않은 부등식이므로 두 문제의 변수는 음수가 아닌 값만 사용할 수 있습니다.
59. 모델의 표준, 정준 및 일반 형식으로 작성된 원래 문제에 대한 이중 문제 구성(대칭 및 비대칭 이중 문제 구성)
표준형(원본)
Σ a ij x j ≤ b i , i=1,n(1)
x j ≥0, j=1,n(2)
z = Σ c j x j ->최대(3)
이중 표준
Σ a ij y i ≤ c j , j=1,n(1)
y ≥0, j=1,m(2)
F = Σ b i y i ->min(3)
표준 형식의 원래 문제:
Σ a ij x j = b i , i=1,m(1)
x j ≥0, j=1,n(2)
z = Σ c j x j ->min(3)
이중 표준
Σ a ij y i ≤ c j , j=1,n(1)
y 나는 - 모든 (2)
F = Σ b i y i ->최대(3)
한 쌍의 이중 문제에 대한 경제적 해석을 해보자. 자원의 합리적인 사용의 문제를 고려하십시오. 기업이 n-유형 제품을 생산하는 데 사용할 수 있는 자원 b1,b2,…bm을 갖게 하십시오. 또한 j형 제품 cj(j=1,n)의 단위 비용과 한 단위 생산을 위한 i번째 자원(i=1,m)의 소비율을 알자 j번째 생산– aij.총 비용을 최대화하여 각 유형 xj(j=1,n)의 생산량을 결정해야 함
f= c1x1+…+cnxn (1)
동시에 리소스 소비는 가용성을 초과해서는 안됩니다.
a11x1+…+a1nxn<=b1 }
…………………….. } (2)
am1x1+…+amnxn<=bm }
경제적 의미로 알려진 모든 것은 음수가 아닙니다.
Xj>=0(j=1,n). (삼)
이 문제는 대칭 이중 문제를 형성합니다.
비대칭 이중 문제.
ZLP를 표준 형식으로 최대화해 보겠습니다.
최대 Z=(n;j=1)Σcj*xj
(n;j=1)Σaij*xj=bi (i=1,m)
Xj>=0(j=1,n).
60. 주 이중성 정리 및 두 번째 이중성 정리(상태 정리 및 설명)
첫 번째 이중성 정리.
정리: 이중 문제 중 하나에 최적의 계획이 있으면 다른 문제도 해결할 수 있습니다. 옵트 플랜이 있습니다. 이 경우 목적함수의 극단값은 일치한다(j=1에서 n까지) Σcjxj*= (i=1에서 m까지)Σbiyi* 인 경우 원본. 문제 목적 함수는 계획 집합에 제한이 없으며 이중 문제에서는 제약 시스템이 일관되지 않습니다.
두 번째 이중성 정리와 그 경제적 해석.
쌍대 문제 쌍의 실행 가능한 솔루션이 최적이 되기 위해서는 다음 조건이 충족되는 것이 필요하고 충분합니다. xj*(∑aij yi*-cj)=0, j 1에서 n, yi*( ∑aij xj*-bi)=0, 나는 1에서 m까지. 이것은 보완적인 느슨함의 조건입니다. 이중 문제의 제한 사항이 최적 계획에 의해 엄격한 평등으로 변환되면 opt의 해당 구성 요소가 따릅니다. 이중 문제의 계획은 0과 같아야 합니다. 일부 구성 요소가 선택되면. 계획이 0과 같으면 이중 문제의 해당 제한이 opt.plan에 의해 완전 동등 xj*>0으로 변환되므로 (i= 1에서 m까지)Σaij yi*=cj opt.plan, 다음 경우 비용>가격, 생산량=0 Σaij yi* >cj 따라서 xj*=0
yi*>0 따라서 (j=1에서 n까지) Σaij xj*=bi(자원 경쟁 = 자원 재고).
(j=1 ~ n) Σaij xj* 정리의 의미는 다음과 같습니다. prod-ii \u003d 가격 단위 생산을 위한 자원 소비의 비용 추정치인 경우 이러한 유형의 prod-ii가 최적 계획에 포함됩니다. 비용이 가격을 초과하면 제품을 생산하지 않아야 합니다. 자원 소비 = 재고인 경우 이 자원의 비용 추정치는 양수입니다. 그러한 자원을 희소성이라고 합니다. 가장 결함이 있는.res-가 가장 높은 점수를 받습니다. 자원이 완전히 소비되지 않은 경우 비용 추정치는 0입니다. 61. 원래 문제의 심플렉스 테이블에서 이중 문제에 대한 최적의 지원 계획 구성 최적의 결과를 가져온 선형 변환의 역행렬 열의 정보입니다. 행렬 D-1의 열은 매우 유용한 정보를 제공합니다. 열 A3: 리소스 S2의 "그림자" 가격은 y01=0이고 열은 그대로 유지됩니다. 단일이고 첫 번째 줄에서 x3=9, 즉 찾은 최적의 계획을 실행할 때 첫 번째 자원이 초과되고 이 초과(저활용)는 9개의 기존 장치에 해당합니다. 열 A4: 자원 S2의 "그림자" 가격은 y02=1과 같으며 자원은 완전히 사용되며 가능한 증가는 목적 함수(즉, 수입)의 증가로 이어집니다. 때문에 y02=1이면 자원 S2가 1 c.u 증가합니다. 소득 측면에서 .Z = y02· .w2 = = 1.1 = 1(천 UAH)만큼 추가됩니다(여기서 w2는 자원 S2의 증분이고 .Z는 해당 소득 증분입니다). 리소스 S2의 이러한 증분으로 최대 수입은 이미 Zmax=58,000 UAH가 됩니다. + 1,000 UAH = 59,000 UAH. 무화과에. 6.2는 이러한 상황을 설명하며 이에 대한 설명은 아래에서 제공됩니다. 또한 열 A4에서 리소스 S2가 1 c.u 증가합니다. 새로운 최적점에 대해 제품 T1의 생산량은 ½톤 감소하고(기본 변수 x1의 행과 A4 열의 교차점에는 "-1/2"가 있음) 제품 T2의 생산량은 다음과 같이 증가합니다. 3/2톤(A4 열의 기본 변수 x2가 있는 행에 "3/2"가 있기 때문입니다. A4 열에 대해 언급한 내용은 아래에서 그래픽 구성을 사용하여 설명할 것입니다(그림 6.2). A5 열: " 섀도우" 리소스 S3의 가격은 y03=2와 같습니다. 이것은 리소스 S3이 1 c.u 증가한다는 것을 의미합니다. Z에서 추가를 가져옵니다.Z = y03 · .v3 = 2.1 =2(천 그리브냐) Zmax=58천 그리브냐가 됩니다. + 2,000 UAH = 60,000 UAH. 동시에 표의 A5 열에서 다음과 같이. 3, T1의 출력은 ½ ton 증가하고 T2는 ½ ton 감소합니다. 원자재 재고 S1(1행 참조)은 c.u.의 3/2 증가합니다. 62. 동적 프로그래밍 방법의 아이디어와 기하학적 해석. Bellman의 최적성 원리. 동적계획법에 의한 문제의 최적해는 함수방정식에 기초하여 구한다. 정의하려면 다음이 필요합니다. 1. 프로세스의 마지막 상태에 대한 기능 방정식을 기록하십시오(l \u003d n-1에 해당). fn-1(Sl-1)=최적(Rn(Sn-1,Un)+f0(Sn)) 2. 해당 허용 영역(f0(Sn)=0, f1(Sn-1)= 이후)에서 일부 고정 Sn-1 및 Un에 대한 개별 값 집합에서 Rn(Sn-1,Un)을 찾습니다. 최적(Rn(Sn-1,Un) 결과적으로, 첫 번째 단계 후에 솔루션 Un과 함수 f1(Sn-1)의 해당 값을 알 수 있습니다. 3. l 값을 1 감소시키고 해당 기능 방정식을 기록하십시오. l=n-k(k= 2,n)의 경우 다음과 같습니다. fk(Sn-k)=최적(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2) 4. 식 (2)를 기반으로 조건부 최적 솔루션 찾기 5. l의 값이 무엇인지 확인 l=0이면 조건부 최적해 계산이 완료되고 프로세스의 첫 번째 상태에 대한 문제의 최적해를 찾습니다. l이 0이 아니면 3단계로 이동합니다. 6. 계산의 끝에서 시작으로 이동하면서 프로세스의 각 후속 단계에 대한 문제의 최적 솔루션을 계산합니다. 프로그램 방법의 역동성은 많은 변수가 있는 하나의 문제를 더 적은 수의 변수를 사용하여 연속적으로 해결된 여러 문제로 대체할 수 있도록 합니다. 결정은 단계적으로 이루어집니다. 다단계 프로세스의 최적화의 기반이 되는 주요 원리와 계산 방법의 특징은 Bellman 최적성 원리입니다. 최적의 행동은 초기 상태와 초기 결정이 무엇이든 초기 결정으로 인한 상태에 대해 후속 결정이 최적이어야 한다는 속성이 있습니다. 수학적으로는 다음과 같은 형식의 표현으로 작성됩니다. fn-1(Sl)=최적(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1) (l=0,n-1)식에서 최적은 문제의 조건에 따라 최대 또는 최소를 의미합니다. 63. DP 방식으로 해결되는 문제에 대한 요구 사항 동적 계획법은 다단계 문제에 대한 최적의 솔루션을 찾기 위한 수학적 방법입니다. 다단계 프로세스는 시간이 지남에 따라 발전하고 여러 단계 또는 단계로 세분화되는 프로세스입니다. 동적 프로그래밍 방법의 특징 중 하나는 다단계 프로세스와 관련된 결정이 단일 행위가 아니라 상호 관련된 결정의 전체 복합체로 간주된다는 것입니다. 이러한 상호 연관된 결정의 순서를 전략이라고 하며 최적 계획의 목표는 미리 선택된 기준에 따라 최상의 결과를 제공하는 전략을 선택하는 것입니다. 이러한 전략을 최적이라고 합니다. 이 방법의 또 다른 중요한 특징은 선사 시대의 다음 단계에서 취해진 최적의 결정의 독립성입니다. 최적화 중인 프로세스가 현재 상태에 도달한 방법. 최적의 솔루션은 현재 프로세스를 특성화하는 요소만을 고려하여 선택됩니다. 동적 프로그램의 방법은 또한 각 단계에서 최적의 솔루션을 선택하는 것이 미래의 결과를 고려하여 이루어져야 한다는 사실이 특징입니다. 즉, 각 개별 단계에서 프로세스를 최적화하는 동안 어떤 경우에도 이후의 모든 단계를 잊어서는 안 됩니다. 64. DP 방법으로 해결된 문제의 수학적 모델의 경제적 공식화 및 구성(자본 투자 분배 문제의 예). 벨만 회귀 관계. 동적 프로그래밍 방법은 최적화되는 프로세스(또는 상황)가 공간이나 시간, 또는 둘 다에 배치되는 문제에 주로 적용된다는 것을 미리 설명하겠습니다. 프로세스(상황) 자체가 너무 복잡하여 알려진 방법을 사용하여 최적화할 수 있는 방법이 없습니다. 그런 다음 동적 프로그래밍 방식에 따라 COMPLEX 프로세스(동작, 상황)를 여러 단계(단계)로 분할(분할)합니다. 이 고장은 많은 경우 자연스럽지만 일반적으로 인위적으로 도입됩니다. .
예를 들어, 체스 게임을 고려할 때 각 플레이어의 움직임은 전체 배치를 별도의 단계(단계)로 나눕니다. 그리고 하나의 미사일을 다른 미사일에 대항하기 위한 군사작전에서 전체 연속과정은 예를 들어 1초의 관찰과 같이 인위적으로 단계로 나누어져야 한다. 동적 프로그래밍 방법을 사용하면 전체 복잡한 프로세스의 최적화를 각 단계에 대한 조건부 최적화로 대체할 수 있습니다. (단계) 전체 프로세스의 최적 제어의 합성이 뒤따릅니다. 동시에 이 방법은 별도의 단계(단계)에서 조건부 최적화가 우선 전체 작업의 이익을 위해 수행된다는 것을 제공합니다. n 단계에서 달성된 효과의 최적값 fn(S0)을 찾을 수 있게 하는 모든 계산은 기본 벨만 함수 방정식 또는 반복 관계라고 하는 공식 (1)에 따라 수행됩니다. 함수 fn-1의 다음 값을 계산할 때, 이전 단계에서 구한 함수 fn-(l+1)의 값을 사용하고, 효과 Rl+1(Sl,Ul+1)의 직접값, 주어진 상태 S1 시스템에 대해 솔루션 U1+1을 선택한 결과로 달성됩니다. 함수 fn-1(l=0,n-1)의 값을 계산하는 과정 자연 초기 조건 f0(Sn)=0에서 수행되며, 이는 시스템의 최종 상태 외부에서 효과가 0임을 의미합니다. 65. 자본 투자 분배 문제(예시). 자본 투자의 최적 분배 문제를 해결하기 위해 함수 벨만 방정식을 사용합니다. 먼저 가장 간단한 상황을 사용하여 Bellman 기능 방정식의 유도를 설명하고 예제를 사용하여 이 방정식을 사용하여 관심 문제를 해결하는 방법을 증명할 것입니다. 두 기업 사이에 K의 양으로 할당된 자본 투자의 최적 분배부터 시작하겠습니다. 기업의 계획 부서는 계산을 기반으로 기업 P1에 대한 소득 함수 q(x)와 기업 P2에 대해 h(x)를 구성했습니다. 이러한 기능은 첫 번째 또는 두 번째 기업이 x의 금액에 대한 투자를 받으면 첫 번째 기업이 수입 q(x), 두 번째 h(x), x의 값은 0에서 K까지 연속적이거나 알려진 이산 값을 취할 수 있습니다. 따라서 회사 P1에 금액 x의 자본 투자를 할당하고 회사 P2에 K - x 금액을 할당합니다. 이 경우 소득 q(x)는 첫 번째 기업에서 받고 h(K - x)는 두 번째 기업에서 받습니다. 투자 K가 한 계획 기간 동안 할당된 경우 두 기업의 총 수입은 R(K, x) = q(x) + h(K - x)입니다. 분명히 x와 그에 따른 K - x는 R(K, x)가 최대값을 취하도록 선택해야 하며, 이를 F(K)로 표시합니다. 이 항목은 보다 완전한 항목을 위한 스켈레톤과 같습니다. 함수 벨만 방정식. 두 개의 계획 기간(2단계)에 걸쳐 자본 투자를 분배하여 작업을 복잡하게 만듭니다. .
처음에 금액 x를 첫 번째 기업 P1에 할당하고 x를 두 번째 기업 P1에 할당하기로 결정했습니다. 일반적으로 소득은 R(K, x) = q(x) + h(K - x). 투자가 2 기간 (2 단계)에 걸쳐 분배된다는 것을 염두에 두는 경우 첫 번째 기업에서 투자 잔액은 x, 여기서 , 두 번째 - .(K - x), 여기서 두 번째 기간은 첫 번째 시설에 따라 q( .x) - 두 번째 시설에 따라 h[.(K - x)]입니다. 동적 프로그래밍 최적화는 원칙적으로 마지막 단계에서 시작됩니다. 따라서 F1은 두 번째 단계에서 두 기업의 최대 가능한 소득을 나타내는 두 번째 단계부터 시작합니다. 단계. 얻다 그런 다음 고려된 마지막(우리의 경우 두 번째) 단계에 이전(우리의 경우 첫 번째) 단계를 추가하고 두 단계에서 함께 최대 수입을 찾습니다. 마찬가지로 n 단계에 대해 다음을 얻습니다. 여기서 Fn-1은 마지막(n - 1) 단계에 대해 최상의 결과를 제공하는 목적 함수입니다. 결과 함수 벨만 방정식은 반복적입니다. Fn 값을 Fn-1 값과 연결합니다. 보다 일반적으로 벨만 방정식은 다음과 같은 형식을 갖습니다. 여기서, Fn-1 - (n - 1) 마지막 단계에 대한 최대 소득, Fn - 모든 n 단계에 대한 최대 수입. 66. 비선형 계획법 문제 해결의 개념 비선형 계획법의 문제를 다음과 같은 일반 형식으로 제시합니다. 조건을 충족하는 변수 x1, x2, ..., xn의 값을 찾습니다. 목적 함수의 필요한 극한값(최대값 또는 최소값)을 가져옵니다. f = f(x1, x2,…, xn), (13.2) 여기서 f(х1, …, хn) 및 qi(х1, …, хn) (m , 1 i =)는 실수 비선형이고, n개의 실수 변수의 일반 함수. 일반적인 속성에 따라 비선형 계획법 문제는 선형과는 확연히 다릅니다. 예를 들어, 실현 가능한 솔루션의 영역은 이미 볼록하지 않을 수 있으며 목적 함수의 극한값은 실현 가능한 영역의 모든 지점에서 관찰될 수 있습니다. 비선형 문제를 해결하는 방법도 크게 다릅니다. 이러한 문제를 해결하기 위한 몇 가지 접근 방식만 고려해 보겠습니다. 우선, 그래픽 접근 방식은 비선형 계획법의 가장 간단한 문제를 해결하는 데에도 유효합니다. 따라서 변수 x1과 x2가 문제의 인수인 경우 먼저 이러한 변수의 평면에 실행 가능한 솔루션 영역을 만든 다음 목적 함수 f(x1,x2)의 수준을 사용합니다. ), 해당 영역의 최적점이 결정됩니다. 비선형 계획법에서 기울기 접근 방식은 많은 문제를 해결하는 데 사용됩니다. 여러 가지 그라디언트 방법이 있으며, 그 핵심은 고려 중인 점에 대한 목표의 최대 증가 방향을 나타내는 벡터인 목적 함수의 그라디언트를 사용하여 최적의 결과를 찾는 것입니다. 일반적으로 탐색 절차는 처음에 선택된 지점에서 가장 좋은 지표가 있는 지점까지 반복 모드로 수행됩니다. 예를 들어 . -
허용 가능한 솔루션의 영역 문제로 간주되고 계산의 반복 프로세스는 해당 지점에서 시작됩니다. 또한 먼저 목적 함수의 기울기를 따라 천이한 다음 해당 영역으로 돌아갑니다. O2 O3 영역의 교란된 경계까지 기울기를 따라. 13.3 인덱스가 홀수인 Ai는 해당 영역에 속하고 인덱스가 짝수인 Ai는 그렇지 않음 최적점 Q에 접근함에 따라 작업 기울기의 방향이 수렴됩니다. 따라서 프로세스를 중지하기 위한 이상적인 기준은 목표 기울기와 경계 기울기 기울기의 공선성입니다. 67. 매개변수 및 정수 계획법의 개념
. ZCLP의 진술 및 수학적 모델. 나눌 수 없는 객체의 문제에서 정수 조건은 변수에 부과됩니다. 때로는 이러한 조건이 모든 변수에 적용되고 때로는 일부 변수에 적용됩니다. 완전 정수 문제를 고려하십시오. f=(n,j=1)∑CjXi 최대 (n,j=1)∑AijXj=bi, i=1,m xi-정수,j=1,n 이제 일반적인 선형 계획법 문제와 달리 최적 계획이 반드시 계획 다면체의 꼭짓점에 있는 것은 아닙니다.정수 문제를 푸는 방법은 다음과 같습니다. 1. 클리핑 방법 2.조합 3.대략적인 방법.. 매개변수 프로그래밍은 허용 조건과 목적 함수가 일부 결정적 매개변수에 의존하는 최적화 문제 연구에 전념하는 수학적 프로그래밍의 한 분야입니다.
