선형 수학 프로그래밍. 선형 프로그래밍 방법

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

심플렉스법의 주요 내용은 다음과 같다.

1. 최적의 참조 솔루션을 찾는 방법을 나타냅니다.
2. 하나의 참조 솔루션에서 다른 참조 솔루션으로 전환하는 방법을 나타냅니다. 여기서 목적 함수의 값은 최적의 값에 더 가까워집니다. 참조 솔루션을 개선하는 방법을 나타냅니다.
3. 최적의 솔루션에서 지원 솔루션 검색을 즉시 중지하거나 최적의 솔루션이 없다는 결론을 내릴 수 있는 기준을 설정합니다.

선형 계획법 문제를 해결하기 위한 단순 방법의 알고리즘

심플렉스 방법을 사용하여 문제를 해결하려면 다음을 수행해야 합니다.

1. 문제를 정식 형식으로 가져오기
2. "단위 기반"으로 초기 지원 솔루션 찾기(지원 솔루션이 없으면 제약 시스템의 비호환성으로 인해 문제에 솔루션이 없음)
3. 참조 솔루션을 기반으로 벡터 분해 추정값을 계산하고 단순 방법의 표를 채웁니다.
4. 최적해의 고유성 기준이 만족되면 문제 해결은 종료됩니다.
5. 최적해 집합의 존재 조건이 충족되면 모든 최적해는 간단한 열거로 구됩니다.

Simplex 방법을 사용하여 문제를 해결하는 예

예제 26.1

Simplex 방법을 사용하여 문제를 해결합니다.

해결책:

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

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

우리는 다음을 얻습니다:

초기 지원 솔루션을 찾습니다. 이를 위해 자유(해결되지 않은) 변수를 0 x1 = x2 = x3 = 0과 동일시합니다.

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

우리는 계산한다 벡터 분해 추정다음 공식에 따라 기준 솔루션을 기반으로 한 조건:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., cm m) - 기본 변수에 대한 목적 함수의 계수 벡터
• X k = (x 1k, x 2k, ..., x mk) - 기준 솔루션의 기초에 따라 해당 벡터 A k의 확장 벡터
• C k는 변수 x k에 대한 목적 함수의 계수입니다.

기저에 포함된 벡터의 추정치는 항상 0과 같습니다. 참조 솔루션, 확장 계수 및 참조 솔루션을 기반으로 한 조건 벡터의 확장 추정치는 다음과 같이 작성됩니다. 단순한 테이블:

표 상단에는 추정 계산의 편의를 위해 목적 함수의 계수가 기록되어 있습니다. 첫 번째 열 "B"에는 기준 솔루션의 기초에 포함된 벡터가 포함됩니다. 이러한 벡터가 기록되는 순서는 제약 방정식에서 허용되는 미지수의 수에 해당합니다. 표 "C 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을 기저에 도입할 때 목적 함수의 증가를 찾습니다.

결과적으로 최적의 솔루션에 대한 더 빠른 접근 방식을 위해서는 매개변수 θ 03의 최소값이 첫 번째 행에서 달성되므로 기준 A6의 첫 번째 벡터 대신 참조 솔루션의 기준에 벡터 A3을 도입해야 합니다. 내가 = 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을 사용하여 조던 변환을 수행하고 세 번째 기준 솔루션 X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5)를 얻습니다(표 26.3).

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

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

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

경제분석에서의 선형계획법

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

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

이 기간은 분석된 경제 현상이 선형적이고 엄격한 함수 종속성으로 연결된 경우 선형 방정식 시스템을 푸는 데 기반을 둡니다. 선형 프로그래밍 방법은 특정 제한 요소가 있는 변수를 분석하는 데 사용됩니다.

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

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

이 작업은 근무 시간 자금뿐만 아니라 가용 직원 수에 대한 제한 조건 하에서 서비스를 받는 고객 수를 최대화하는 것입니다.

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

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

비선형 프로그래밍은 목적 함수나 제약 조건, 또는 둘 다의 비선형 특성에 의존합니다. 이러한 조건에서 목적 함수의 형태와 제한의 불평등은 다를 수 있습니다.

비선형 프로그래밍은 특히 조직 활동의 효율성과 활동 규모, 생산 비용 구조, 시장 상황 등을 표현하는 지표 간의 관계를 설정할 때 경제 분석에 사용됩니다.

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

볼록 프로그래밍은 비선형 프로그래밍의 한 유형입니다. 이러한 유형의 프로그래밍은 조직 활동 결과와 비용 간의 관계의 비선형 특성을 표현합니다. 볼록(또는 오목) 프로그래밍은 볼록 목적 함수와 볼록 제약 시스템(타당성 점)을 분석합니다. 볼록 프로그래밍은 비용 최소화를 목표로 경제 활동을 분석하는 데 사용되며, 반대로 분석된 지표에 영향을 미치는 요인의 작용에 대한 기존 제한 하에서 소득 최대화를 목표로 오목 프로그래밍을 사용합니다. 결과적으로, 고려 중인 프로그래밍 유형에 따라 볼록 목적 함수는 최소화되고 오목 목적 함수는 최대화됩니다.

선형 계획법은 극값(수표 또는 최소)을 찾는 특정 종류의 문제를 해결하는 방법을 나타냅니다. 이는 종속성이 엄격하게 함수적일 때 선형 방정식 시스템을 푸는 데 기반을 둡니다. 선형 계획법 모델에는 목표(최대화 또는 최소화) 함수, 제약 조건 시스템, 변수의 비음성 조건이라는 세 가지 구성 요소가 있습니다. 선형 계획법의 수학적 장치는 경제, 기술, 군사 등의 문제를 해결하는 데 사용됩니다.

최적 계획의 경제적 문제에서 목적 함수의 해결은 이익, 생산량, 노동 생산성 또는 현재 비용, 자본 투자, 작업 완료 시간 등의 최소값 등의 최대값을 찾는 것으로 귀결됩니다.

동시에 모든 최적 계획 문제가 선형 프로그래밍 프레임워크 내에서 공식화되고 해결될 수 있는 것은 아니라는 점에 유의해야 합니다. 그러기 위해서는 네 가지 기본 조건이 충족되어야 한다.

• 1. 문제는 명확하게 공식화되고 수량화되어야 ​​합니다. 최적성 기준,실제로는 그렇게 쉽지 않습니다. 기업의 성과는 생산량, 제품 범위 및 품질, 생산 수익성 등 다양한 지표로 판단되는 경우가 많습니다. 한 기준의 선택은 다른 기준의 관점에서 볼 때 최고와는 거리가 멀 수 있으며 그 반대의 경우도 마찬가지입니다. .
• 2. 선형 계획법 문제의 중요한 부분은 다음과 같습니다. 제한,사용 가능한 자원, 요구 사항 또는 기타 요인과 관련이 있습니다. 실물 경제에서는 너무 많은 요인의 상호 작용을 고려하는 것이 항상 가능한 것은 아니므로 실제 성격을 보다 밀접하게 반영하는 단순화된 모델이 작성됩니다.
• 3. 선형 프로그래밍에는 옵션 선택이 포함되며 경제 문제의 특정 조건이 이를 결정하는 경우에만 적용 가능합니다. 선택의 자유.
• 4. 모델에는 다음이 포함되어야 합니다. 선형 방정식 또는 부등식만저것들. 모든 문제 변수는 1제곱이어야 합니다. 실제 경제적 종속성은 항상 선형적이지는 않습니다.

선형 계획법 문제를 해결하기 위해 해당 조건을 고려하고 경제적 상황을 근사화하는 경우 가변 수량에 너무 엄격한 제한을 가하면 문제의 초기 조건에 대한 전체 시스템의 불일치가 발생할 수 있다는 점도 고려해야 합니다.

해결하려는 문제의 성격에 따라 선형 프로그래밍 방법은 두 그룹으로 나눌 수 있습니다.

• 1.보편적인 방법.이들의 도움으로 모든 선형 프로그래밍 문제를 해결할 수 있습니다. 가장 일반적인 것은 단순 방법, J. Dantzig가 제안한, 승수를 해결하는 방법, 해외에 등장하기 약 10년 전인 1939년에 학자 L.V. Kantorovich가 개발했습니다.
• 2. 특별한 방법.이러한 방법은 보편적인 방법보다 간단하지만 모든 작업에 적용할 수 있는 것은 아닙니다. 여기에는 다음이 포함됩니다 유통방식교통문제를 해결하기 위해 용어 해결 방법 A. L. 루리, 차등 임대료 방법 가. L. 브루드노, 헝가리 방식.

선형 프로그래밍 방법의 특수 그룹에는 다음이 포함됩니다. 대략적인 방법, 이는 문제에 대한 최적의 솔루션을 엄격하게 보장하지는 않지만 간단하고 수동 계산에 잘 적용된다는 점에서 다른 것과 다릅니다. 여기에는 다음이 포함됩니다 인덱스 방법, 보겔 근사 방법등등

단순 방법.단순 방법의 아이디어를 더 잘 이해하려면 최대 이익을 달성하기 위해 자원 사용을 최적화하는 문제를 해결하는 것을 고려하십시오.

예제 2.21

본생산에서 남은 재료를 활용하는 보조생산이 있습니다. 이 생산 시설에서는 유리를 사용한 도어(LAN 제품군)와 유리를 사용하지 않은 도어(DV 제품군) 등 다양한 종류의 도어를 생산합니다. 이러한 제품의 판매가 보장됩니다. 제품은 어떤 비율로든 생산할 수 있지만 작업장의 작업 수와 기본 재료 자원에는 제한이 있습니다. 임무는 가능한 최대 이익을 제공하는 월간 생산량을 워크숍에서 계획하는 것입니다.

이 작업은 전체 리소스 볼륨의 필수 사용 조건을 설정하지 않습니다. 작업 시간의 소비는 지정된 한도를 초과하지 않아야 합니다.

고려해 봅시다 프로그램 1은 생산에 유리를 사용하지 않고 DV 제품군의 문만 생산하는 것을 포함합니다.

사용 가능한 모든 리소스를 사용하여 TV만 출시하는 경우 다음을 출시하기에 충분합니다.

• - 작업 시간별: 520/9.2 = 56(개);
• - 목재: 24/0.3 = 80(개).

따라서 모든 자원은 56개의 문만 생산하는 데 충분합니다.

이 문제의 이익은 168,000 루블입니다. (56 3000).

프로그램 2는 LAN 범위에서 문만 생산한다고 가정합니다. 이 경우 릴리스할 리소스가 충분합니다.

• - 단, 작업 시간: 520/4 = 130(개);
• - 목재: 24/0.6 = 40(개);
• - 유리: 40/2 = 20(개).

최적으로 LAN 도어는 20개만 생산할 수 있지만 이는 유리의 존재로 인해 제한됩니다. 이렇게 하려면 12m의 목재가 필요하며 나머지 부분에서 40개를 더 생산할 수 있습니다. DV 제품군의 문. 20개 생산용입니다. ICE 및 40개 DV에는 448시간이 소요됩니다.

이익은 160,000 루블이 될 것입니다. (20-2 + ​​40-3). 따라서 첫 번째 프로그램이 바람직합니다. 다른 옵션이 있습니다.

이 작업의 제한 사항은 다음과 같습니다.

그래프에 직선을 그리자 루첫 번째 부등식에 해당: 두 번째 부등식은 직선에 해당합니다. b 2:

그래프의 세 번째 부등식은 가로축 L 3에 평행한 직선에 해당합니다.

릴리스 계획은 문제의 다섯 가지 제약 조건을 모두 기반으로 해야 하므로 이 경우 실현 가능한 솔루션의 영역은 음영처리된 다각형이 됩니다.

이전 계산에서 찾은 목적 함수의 최대값은 직선의 점에 해당합니다.

다각형은 문제에 대한 실현 가능한 솔루션 영역을 제한합니다. 수많은 솔루션 중에서 이익 가치가 최대인 솔루션을 선택해야 합니다. 우리의 경우 자아는 선들의 교차점이 될 것입니다 엘(그리고 1 2 . 다음으로 선형 방정식 시스템이 해결됩니다.

시스템을 해결하면 다음을 얻습니다. 따라서 이익은 다음과 같습니다.

(그래픽 방법에서) 목적 함수에 해당하는 직선이 다각형의 꼭지점을 통과하는 경우 문제에는 단일 최적 옵션이 있습니다. 다각형의 측면과 일치하면 문제에 대한 해결책이 많이 있습니다.

최적의 솔루션은 꼭지점이나 다각형의 측면을 통과해야 합니다. 따라서 꼭지점 중 하나가 최적의 솔루션에 해당하지만 처음에는 어떤 솔루션인지 알 수 없습니다.

그래픽 방식은 간단하고 시각적이지만 적용이 제한적입니다.

세 개의 변수를 사용하면 다차원 좌표계에서 다면체를 구성해야 합니다. 변수가 4개 이상인 경우 그래픽 표현이 불가능합니다. 그러나 다차원 공간을 추상적으로 상상하는 것은 가능합니다. 문제의 조건이 일관적이라면 허용값 영역(ADV)은 n차원 공간에서 볼록한 다각형을 형성합니다.

이 경우 최적의 솔루션이 존재한다면 반드시 다면체의 일부 꼭지점(아마도 둘 이상)에서 달성됩니다.

따라서 선형 계획법 문제에 대한 해결책을 찾으려면 다면체의 꼭지점에 해당하는 옵션을 열거하는 것으로 충분합니다. 이를 참조 계획이라고 합니다. 그러나 복잡한 문제에는 문제가 너무 많을 수 있으며 참조 계획을 결정하려면 엄청난 양의 계산이 필요합니다.

심플렉스 방법을 사용하면 다면체의 정점에 대해 순서화된 검색을 수행할 수 있습니다.

예를 들어 심플렉스법을 사용한 계산 순서를 살펴보겠습니다.

예제 2.23

기업에는 4가지 유형의 제품(A, B, C, D)이 제조되는 3가지 장비 그룹(I, II, III)이 있습니다. 모든 제품은 무제한 판매되므로 기업은 이 범위 내에서 구색 프로그램을 계획할 수 있습니다.

다음 제한 사항이 적용됩니다.

• - 기본 장비의 가용성;
• - 각 그룹의 장비에서 각 유형의 제품을 처리하는 시간 표준
• -특정 유형의 제품 단위당 기업이받는 이익 금액.

최대의 이익을 얻어야 합니다.

찾고 있는 문제: 엑스(- 에드. ㅏ; 엑스 2 - 에드. 비; 엑스 3 - 에드. 안에; 엑스 4 - 에드. G.

최대 이익:

제한:

심플렉스 방법을 사용하여 문제를 해결하기 위해 모든 불평등을 평등으로 변환합니다. 이를 위해 문제에 음수가 아닌 세 가지 변수를 추가로 도입합니다. 엑스 5 , x6, x 7 부등식의 왼쪽에 추가합니다.

경제적 의미에서 추가 변수는 특정 장비의 사용되지 않은 작동 시간에 지나지 않습니다. 단순 방법을 사용하여 문제를 해결하기 위해 특수 단순 테이블이 컴파일됩니다.

맨 위 줄에는 목적 함수의 계수가 포함됩니다. 추가 변수는 0 계수에 해당합니다. 사용하지 않는 장비는 이익을 창출하지 않습니다. 동일한 0 표시기가 열에 있습니다. 와 함께각 추가 변수에 대해.

라인을 채우는 중 Zj - CJ자신의 특성을 가지고 있습니다. 고려 Zj각 열마다. 열 값의 곱의 합으로 구해집니다. 와 함께해당 열 계수로 제이.열의 원래 버전 이후 와 함께 0이면 값 Zj모든 열에 대한 값은 0이고 값은 Zj-Cj= -Cj.따라서 초기 버전에서는 여기에서 목적 함수의 계수가 반대 부호로 설정됩니다. 모든 주요 변수는 0으로 설정되어 있으며 문제의 기본에 포함되지 않습니다. 추가 변수는 원래 방정식에 따른 한계값과 동일합니다. 이는 아무것도 생산되지 않고, 자원이 사용되지 않으며, 목적 함수의 값이 0(이익 없음)임을 의미합니다.

문제에 대한 해결책은 최적의 솔루션을 얻을 때까지 주요 변수를 계획에 순차적으로 도입하는 것으로 구성됩니다. 이 경우 계산의 각 단계에서 하나의 변수만 입력할 수 있습니다. 이 경우 세 가지 제한 사항이 있으면 기저에 3개 이상의 변수가 있을 수 없으므로 다른 변수가 기저에서 제거됩니다.

문제는 다음과 같이 해결되므로 최대이익을 얻으려면 가장 수익성이 높은 제품부터 시작해야 합니다. 우리의 경우 이것은 ed입니다. D. 기초에 도입 x 4.출판물의 출시가 어떻게 예상되는지 결정합시다. D. 자원의 양과 비용 기준에 따라 다릅니다. 그룹 I 장비는 3000개의 아이템을 처리할 수 있습니다. (24,000/8), 그룹 II는 G 생산에 관여하지 않으며, 그룹 III은 30,000개의 항목을 처리하는 데 사용할 수 있습니다. "기초" 열의 표에서 가장 작은 값(3000 ed.)을 허용합니다. 엑스 4 제자리에 놓다 엑스 5 (그룹 I의 장비는 완전히 사용되었으므로 0과 같습니다). 교차로의 8번 ×A그리고 엑스 5 ~라고 불리는 가이드 요소또는 일반적인, 열쇠, 허용적이다.

선 엑스 4 새 테이블에서는 출력 변수의 행을 나누어 얻습니다. 엑스 5 가이드 요소에 이전 표의 내용을 적용합니다. 열에 와 함께 0.8이 입력됩니다 - 출판 단위당 이익 금액입니다. D. 이후 “계획” 열이 다시 계산됩니다. 그룹 II 에드의 장비에. G는 처리되지 않으며 새 버전에서는 해당 시간의 단위가 변경되지 않습니다(12,000분).

그룹 III 장비의 시간 기금은 3000분(1분 x 3000개)만큼 감소하므로 27,000분은 사용되지 않은 상태로 남습니다. "계획"열의 다음 숫자는 2400 루블입니다. (0.8 3000) - 이 옵션의 이익입니다. "계획" 열 이후에는 입력 변수의 행을 제외하고 단순 테이블의 다른 모든 열이 다시 계산됩니다. 동시에, 기초에 포함된 모든 변수의 열에는 동일한 이름의 행과 열의 교차점에 항상 단위가 있고 열의 나머지 요소는 동일하다는 점을 명심해야 합니다. 0으로.

따라서 즉시 열을 채울 수 있습니다 4개, 6개그리고 x 7."삼각형 규칙"에 따라 다시 계산하는 것이 좋습니다. 새 버전에서 계수를 계산하려면 심플렉스 테이블에서 세 개의 숫자를 찾아야 합니다. 이전 버전에서 이 계수를 대신하는 숫자입니다.

• - 이전 옵션과 같은 줄에 있지만 입력 변수 열에 있는 숫자입니다.
• - 원하는 계수가 있는 동일한 열에 있는 새 버전의 숫자이지만 새로 입력된 변수 행에 있습니다(이 행의 요소는 이미 이전에 계산되었습니다).

표의 세 숫자는 직각삼각형을 이룹니다. 필요한 계수를 결정하려면 직각의 꼭지점에 있는 숫자에서 다른 두 각도의 곱을 빼야 합니다.

예를 들어, column.gr의 경우

우리는 다음과 같이 계산합니다.

라인별 계수에 대해

행 인수 x 7의 경우:

라인 표시기 Zj - CJ두 가지 방법으로 계산할 수 있습니다.

a) 공식에 따르면

b) "삼각형" 규칙에 따르면:

새 버전의 단순 테이블의 다른 열에 대해서도 유사한 계산을 수행합니다.

이제 우리는 두 번째 옵션이 최적인지, 아니면 개선할 수 있는지 알아내야 합니다. 이렇게하려면 라인을보십시오 Zj-Cj.음수가 포함되어 있으면 옵션을 개선할 수 있습니다.

0.3 문지름. 도입된 제품 단위마다 기본 숫자를 입력하면 수익이 증가합니다! (ed. A) 및 0.1 문지름. 숫자 3을 소개할 때(ed. B). 이 수치는 원본 데이터와 모순되는 것처럼 보일 수 있습니다. 그리고 그것은 0.4 루블을 가져옵니다. 이익, B - 0.5 문지름. 그러나 사실은 작업의 이 단계에서 이러한 제품을 계획에 도입하면 이전에 도입된 일정 수의 제품이 대체된다는 것입니다. D, 생산을 위해 그룹 I 장비를 확보하기 위해.

다음 단계에서는 소개하는 것이 더 적절합니다. 엑스((ed. A), 절대값으로는 가장 큰 음수에 해당하기 때문이다. 이전 옵션과 유사하게 ed 수를 설정합니다. 또는 이미 출판물의 출시가 포함되어 있다는 사실을 고려하여 계획에 포함될 수도 있습니다. D. 이를 위해 "계획" 열의 숫자를 입력 변수 열의 해당(양수만) 계수로 나눕니다. 엑스(얻은 몫에서 가장 작은 것을 선택합니다.

따라서 새 버전의 계산에는 항목을 4000개 이상 입력할 수 없습니다. 그리고 제한 요소는 그룹 II의 장비이기 때문입니다. 따라서 변수는 엑스(기본적으로 변수를 대체합니다. x세기

기둥의 교차점에서 x x그리고 문자열 x 6가이드 요소를 찾아서 강조 표시합니다. - 3. 다음으로 문자열 요소를 나누어 입력된 변수의 문자열을 계산합니다. x 6가이드 요소에 이전 버전의 그런 다음 "계획" 열을 계산합니다.

새로운 옵션의 이익은 다음과 같습니다:

설명된 규칙에 따라 다음 열을 채웁니다. 라인을 살펴보며 Zj - CJ여기에는 0과 양수 요소만 포함되어 있으며 이는 옵션 3이 최적의 솔루션이며 개선할 수 없음을 의미합니다. 4가지 제품 중 2가지 유형만 포함되어 있습니다. 변하기 쉬운 x 3마지막 줄은 0에 해당합니다. 이는 후속 단계에서 계획을 소개한다는 의미입니다. x 3이익은 증가하지 않지만 감소하지도 않으며 결과도 최적입니다. "계획" 열의 숫자를 열 계수로 나눕니다. x 3그리고 얻은 것 중에서 최소값을 선택하여 이 변수가 변수^ 대신 기초에 도입되어야 한다고 결정합니다. 후속 변환의 결과로 우리는 2182 에디션 출시를 제공하는 새로운 최적의 계획을 얻었습니다. ㅏ (엑스()및 5455 ed. B(.g 3). 문제를 해결하기 위한 몇 가지 최적의 옵션을 더 찾아보겠습니다. 옵션/: 첫 번째 프로그램에서 50%, 두 번째 프로그램에서 50%:

옵션 II:첫 번째 프로그램에서 80%, 두 번째 프로그램에서 20%:

이러한 옵션은 또한 RUB 3,600의 이익을 제공합니다.

실질적으로 동일하고 효과적인 여러 계획이 있으면 경제 문제에서 가장 수용 가능한 분석 및 질적 선택을 위한 추가 기회를 제공하는 여러 중간 옵션을 결정할 수 있습니다.

단순 방법을 사용하여 문제를 해결할 때 "퇴화" 사례가 발생할 수 있습니다. ~에 티제한 사항, 비퇴화 계획에는 항상 다음이 포함됩니다. 티양의 변수, 그리고 나머지 피 - 티문제의 변수는 기저에 포함되지 않으며 0과 같습니다. 그러나 기저에 포함된 하나 이상의 변수가 0과 같을 수도 있습니다. 단순 테이블의 "계획" 열에 하나 이상의 0이 존재합니다. 이 계획은 퇴화하다.퇴화 계획을 사용하면 줄에 음수가 존재합니다. Zj-Cj이는 다음 옵션이 목적 함수의 값을 증가시킨다는 의미는 아닙니다. 이는 한 단계뿐만 아니라 여러 연속 단계에서도 변경되지 않은 상태로 유지될 수 있습니다. 이런 일이 일어난다 루핑, 이는 추가 계산을 방지하고 특수 기술의 도움을 통해서만 극복할 수 있습니다.

현재 개인용 컴퓨터는 최적화 문제를 해결하는 데 널리 사용됩니다. 스프레드시트 시스템을 사용합니다. "마이크로 소프트 엑셀».

최적화 문제를 해결하려면 MS 엑셀"도구" 기본 메뉴 항목에서 호출되는 솔루션 추가 기능 검색을 사용하세요.

버전인 경우 뛰어나다컴퓨터에 설치된 경우 "서비스" 메뉴의 하위 항목이 누락된 경우 "추가 기능" 메뉴 항목을 호출하고 제안된 추가 모듈 목록에서 "솔루션 검색"을 선택해야 합니다.

이 추가 기능을 사용하여 생산 계획 문제를 해결하는 예를 살펴보겠습니다.

예제 2.24

회사는 세 가지 유형의 자원을 사용하여 제품 A, B, C, D를 생산합니다. 수학적 모델의 형식은 다음과 같습니다: check/(X) = 7.5π* 1 +3x2+ 6dg 3 + 12.g 4 (목적 함수 - 총 산출 비용).

자원 보유량 및 변수의 비음수성에 대한 제한은 다음과 같습니다.

편집기에서 템플릿을 만들어 보겠습니다. 뛰어나다.

이제 이 문제에 숫자 정보를 추가해 보겠습니다.

선택한 빈 셀(목적 함수의 값과 부등식의 왼쪽)에 바탕 화면의 숫자 간의 연결과 관계를 표시하는 수식을 입력해야 합니다.

세포 C 4 - F a가 호출됩니다. 뛰어나다변경 가능합니다(우리 모델에서는 알 수 없는 변수입니다). 이를 변경할 때 솔루션을 검색하면 목적 함수의 최적 값을 찾을 수 있습니다. 이러한 셀에 처음 입력된 값은 일반적으로 0입니다(채워지지 않은 셀은 기본적으로 0 값을 포함하는 것으로 처리됩니다).

이제 수식을 입력해야 합니다. 우리의 수학적 모델에서 목적 함수는 계수 벡터와 미지수 벡터의 곱입니다. 실제로 표현은 고려될 수 있다.

벡터(.g, 엑스 2, i-*, xA).

안에 뛰어나다벡터의 스칼라 곱을 찾을 수 있는 SUMPRODUCT 함수가 있습니다. 이 함수는 셀 #5에서 호출되어야 하며 방정식의 계수(이 경우 C5)가 포함된 셀의 주소는 곱셈된 벡터로 지정되어야 합니다. F5) 및 솔루션의 결과로 값이 배치될 셀 x와 x2, x3, x4(셀 SA : 파).

제약 조건의 각 왼쪽은 두 벡터, 즉 비용 행렬의 해당 행과 알 수 없는 벡터의 곱이기도 합니다. 표현 2배 + x 2+ 0Dg 3 + 4x1(첫 번째 제약조건의 경우 2x, + x 2 + 0.5x 3 + 4 x 4 2400)은 계수 벡터(2,1,0,5,4)와 변수 벡터의 곱으로 간주됩니다. (x 및 x 2, x 3, x 4).

첫 번째 제약 조건((79)의 왼쪽 수식을 위해 예약된 셀에서 SUMPRODUCT 함수를 호출합니다. 곱해진 벡터의 주소로 계수 C9: /0 행의 주소와 주소를 입력합니다. 변수 C4의 값: 파.

"왼쪽 부분" 열의 나머지 4개 셀에는 비용 매트릭스의 해당 행을 사용하여 유사한 수식을 입력합니다. 입력된 수식이 있는 화면의 일부는 다음과 같습니다.

'해 찾기' 서비스가 호출될 때까지 문제가 있는 바탕 화면에 제약 조건의 좌변에 대한 수식과 목적 함수의 값에 대한 수식이 입력되어야 합니다.

'서비스' 메뉴에서 '솔루션 검색'을 선택하세요. 나타나는 창에서 다음 정보를 입력하십시오.

• a) 타겟 함수 값 #5에 대한 셀 주소를 타겟 셀로 설정하는 단계;
• b) "체크박스"를 "최대값" 옵션으로 설정합니다. 이 경우 소득의 목적 함수가 최대화되기 때문입니다.
• c) 변수 C4의 값 행 주소가 변경 가능한 셀 F4로 입력됩니다.
• d) 제한사항 입력 창 오른쪽에서 "추가" 버튼을 클릭하면 제한사항 입력 양식이 나타납니다.

e) “Cell Link” 폼의 왼쪽 부분에 첫 번째 제약 조건의 왼쪽 부분에 대한 수식의 주소를 입력합니다. G 9에서는 필수 부등식 기호가 선택됩니다(우리의 경우,

f) 모든 작업 제한은 동일한 방식으로 입력된 후 "확인" 버튼을 누릅니다.

입력된 정보가 표시된 “해결책 검색” 창은 다음과 같습니다.

다음으로 "옵션" 버튼을 클릭하고 "선형 모델" 및 "음수가 아닌 값" 확인란을 선택해야 합니다. 이 경우 문제는 선형 프로그래밍과 관련이 있고 제약 조건에는 음수가 아닌 값이 필요하기 때문입니다.

그런 다음 “확인”, “실행”을 클릭하면 해결 결과 창이 나타납니다.

모든 작업의 ​​결과로 "솔루션을 찾았습니다"라는 메시지가 표시된 창이 나타나면 모델의 민감도를 분석할 때 유용한 세 가지 유형의 보고서를 받을 수 있는 기회가 제공됩니다. 이 예에서는 "확인"을 클릭하여 찾은 솔루션을 저장하면 충분합니다. 그 결과, 문제에 대한 해결책이 얻어졌습니다.

문제 해결 결과 해결책을 찾을 수 없다는 메시지가 표시된 창이 나타나면 이는 문제 공식화에 오류가 발생했음을 의미합니다 (제약 조건 공식이 채워지지 않았거나 "플래그" , 최대화(최소화) 등이 올바르게 설정되지 않았습니다).

"솔루션 검색" 창에는 "옵션" 버튼이 있습니다.

"반복 결과 표시" 확인란을 선택하고 "확인"을 클릭합니다.

그런 다음 "실행"버튼을 클릭하십시오.

MS 엑셀다음 창이 표시됩니다.

워크시트에는 첫 번째 반복의 결과가 표시됩니다.

그런 다음 "계속" 버튼을 클릭하면 두 번째 반복 결과가 워크시트에 표시됩니다.

"계속" 버튼을 다시 클릭하면 워크시트에 세 번째 반복 결과가 표시됩니다.

다음에 "계속" 버튼을 클릭하면 프로그램이 "솔루션 검색 결과" 창을 표시합니다. 여기서 찾은 솔루션을 저장하고 보고서 유형을 선택해야 합니다.

이 섹션에서는 최적화 문제를 해결하기 위한 일반적인 형식에 대해 설명합니다. 뛰어나다.경제 모델에 따라 적절한 수정이 이루어집니다.

보고서는 다음과 같습니다.

1. 결과를 보고합니다.

2. 지속가능성 보고서.

3. 한도에 대해 보고합니다.

이제 수학적 모델의 형식은 동일하지만 제약 조건의 부호가 다른 예를 생각해 보세요.

예제 2.25

L. 수학적 모델이 다음과 같다고 가정해 보겠습니다. 여기에는 다음과 같은 제한 사항이 있습니다.

지속 가능성 보고서.

B. 이제 수학적 모델에 다른 제한 사항이 있다고 가정합니다.

이 경우 보고서에서 다음과 같은 결과를 얻었습니다.

지속 가능성 보고서.

• 동일한 문제를 해결하기 위해 선형 프로그래밍 방법 중 하나인 그래픽을 사용합니다. 예제 2.22 다음 표기법을 소개하겠습니다: x( - 필요한 DV 도어 수, x2 - 필요한 ICE 도어 수.

선형 프로그래밍 방법은 경제학에서 자주 다루는 많은 극단적인 문제를 해결하는 데 사용됩니다. 이러한 문제를 해결하려면 가변 수량의 일부 기능에 대한 극단값(최대값과 최소값)을 찾는 것이 필요합니다.
선형 계획법은 연구 중인 현상 간의 관계가 엄격히 함수적인 경우 선형 방정식 시스템(방정식 및 부등식으로 변환)을 푸는 데 기반을 둡니다. 변수의 수학적 표현, 특정 순서, 계산 순서(알고리즘) 및 논리적 분석이 특징입니다. 연구중인 변수와 요인에 수학적 확실성과 정량적 한계가 있고, 알려진 계산 순서의 결과로 요인이 상호 교환 가능하고, 계산 논리, 수학적 논리가 결합되는 경우에만 사용할 수 있습니다. 연구되는 현상의 본질에 대한 논리적 이해.
예를 들어 산업 생산에서 이 방법을 사용하면 기계, 장치, 생산 라인의 최적의 전체 생산성이 계산되고(주어진 제품 범위 및 기타 주어진 값에 대해) 합리적인 자재 절단 문제가 해결됩니다(최적 수율로). 공작물의). 농업에서는 주어진 양의 사료(종류 및 함유된 영양분 기준)에 대한 사료 배급의 최소 비용을 결정하는 데 사용됩니다. 혼합물 문제는 주조 생산(야금재료 구성)에도 적용할 수 있습니다. 동일한 방법이 운송 문제, 즉 소비자 기업을 생산 기업에 합리적으로 연결하는 문제를 해결하는 데 사용됩니다.
선형 프로그래밍을 사용하여 해결되는 모든 경제적 문제는 대체 솔루션과 특정 제한 조건으로 구별됩니다. 이러한 문제를 해결한다는 것은 허용 가능한 모든 (대체) 옵션 중에서 가장 좋은 최적을 선택하는 것을 의미합니다. 경제학에서 선형 계획법 사용의 중요성과 가치는 매우 많은 수의 대체 옵션 중에서 최적의 옵션이 선택된다는 사실에 있습니다. 다른 방법으로는 이러한 문제를 해결하는 것이 거의 불가능합니다.

예를 들어 생산 장비의 가동 시간을 합리적으로 사용하는 문제를 해결하는 것을 고려하십시오.
운영 계획에 따라 연삭 부문에서는 12월 첫 주 동안 A 유형 베어링용 링 500개, B 유형 베어링용 링 300개, B 유형 베어링용 링 450개를 생산했습니다. 모든 링은 2개의 교체 가능한 기계에서 연삭되었습니다. 다른 용량. 각 기계의 기계 시간은 5000분입니다. 다양한 링 제조 시 작업의 복잡성(링당 분 단위)은 다음 데이터로 특징지어집니다(표 6.5).
표 6.5
여러 기계에 작업을 분산시키기 위한 최적의 옵션과 이 최적의 옵션에 소요되는 시간을 결정해야 합니다. Simplex 방법을 사용하여 작업을 완료해 보겠습니다.
이 문제의 수학적 모델을 작성하기 위해 다음 기호를 도입합니다. jc, x2, xъ, - 각각 기계 I에서 생산된 L, B, B 유형 베어링의 링 수입니다. x4, x5, x6 - 각각 기계 II에서 생산된 A, B, C 유형 베어링용 링 수입니다.
최적성 기준을 반영하는 선형 형태는 다음과 같습니다.
최소 a(x) = 4x,-f 10x2-f 10x3-f 6x4-f 8x5+20x6 제한 있음
4х, -f 10х2 -f 10;t3 lt; 5000
6x4 -f 8x5 -f 20x6 ~lt; 5000
엑스, = 500
x2 + x5 = 300
x3 + x6 = 450
Xj^0,j=1, ..., 6

추가(보조) 변수와 가상 변수를 도입하여 문제의 조건을 변형해 보겠습니다. 다음과 같이 조건을 작성해 보겠습니다.
배송 lt;x(x) = 4dg, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Mx9 + Mx(0+Mx(,
컴퓨터 시간과 생산되는 제품 수량의 제한적인 조건을 반영하는 방정식 시스템:
4x, + l(bc2 + 10x3 +x1 = 5000
6x4 + 8x5 + 20x6 + xs = 5000
Xj + x4 + x9 = 500
x2 + x5 + x10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
이 문제에 대한 해결책이 표에 나와 있습니다. 6.6. 7단계(iteration)에서 최적의 옵션이 얻어졌다. 기계 I가 유형 A의 베어링 링 125개, 유형 B의 베어링 링 450개를 생산하고 기계 II가 유형 A의 베어링 링 375개와 유형 B의 베어링 링 300개를 생산한다면 이러한 장비 로드로 기계 시간은 350분이 됩니다. 머신 II를 위해 해제되었습니다. 최적의 옵션에서 소요되는 총 시간은 9650분이지만 실제로는 10,000분의 컴퓨터 시간이 소요됩니다.
선형 프로그래밍을 사용하여 해결되는 매우 일반적인 문제는 운송 문제입니다. 그 의미는 제조업체에서 소비자로, 도매 창고 및 기지에서 소매점으로 소비재를 배송할 때 화물 회전율을 최소화하는 것입니다. 단순법이나 분포법을 사용하여 풀 수 있습니다.
분배방식을 이용한 교통문제의 해법은 교과서 『경제분석이론』( 『재정과 통계』, 1996) 제3판에 제시되어 있다.

단순 방법을 사용하여 공작 기계의 합리적인 사용 문제 해결

기초	와 함께	로	4	10	10	6	8	20	0	0	중	중	중
			엘	Rg	아르 자형	엘	R ъ		파이	P8	아르 자형*	엘 0	엘,
엘	0	5000	4	10	0	0	0	0	і	0	0	0	0
아르 자형,	0	5000	0	0	0	6	8	20	0	1	0	0	0
엘	중	500	1	0	0	1	0	0	0	0	1	0	0
엘 0	중	300	승	0	0	0	1	0	0	0	0	1	0
엘.	중	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		1250M	M-4	M-10	M-10	M-6	M-8	M-20	0	0	0	0	0
파이	0	3000	0	10	10	-4	0	0	0	0	-4	0	0
아르 자형*	0	5000	0	0	0	6	8	20	1	1	0	0	0
로	4	500	1	0	0	1	0	0	0	0	1	0	0
봐라	중	300	0	1	0	0	승	0	0	0	0	1	0
엘.	중	450	0	0	1	0	0	1	0	0	0	0	1
zr-9		750L/+2000	0	M-10	M-10	-2	M-8	에 대한 2	0	0	-M + 4	0	0

기초	와 함께	P0	4	파이	10	6	8	20	0	0	중	중	중
			파이	10	^3	엘	P5	p6	파이	아르 자형"	p9	파이 0	RC
파이	0	3000	0	10	10	-4	0	0	1	0	-4	0	0
아르 자형*	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
파이	4	500	1	0	0	1	0	0	0	0	1	0	0
P5	8	300	0	1	0	0	1	0	0	0	0	1	0
RP	중	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		450L/+4400	0	-2	M-10	-2	0	M-20	0	0	-M+4	-M+8	0
아르 자형	10	300	0	1	1	4 10	0	0	1 10	0	4 10	0	0
아르 자형%	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
파이	4	500	1	0	0	1	0	0	0	0	1	0	0
P5	8	300	0	1	0	0	1	0	0	0	0	1	0
RC	중	150	0	-1	0	j4_ 10	0	1	_J_ 10	0	4 10	0	1
zrCj		150L/+7400	0	-M+S	0	- M-6 10	0	M-20	- ~M+1 10	0	-±m 10	- Af+8"	0

기초	와 함께	엘,	4	10	10	6	8	20	0	0			중	중	중
			엘	Rg	엘	엘	추신	p6	파이	팸;			P9	봐라	엘.
엘	10	300	0	1	1	4	0	0	1		0		4	0	0
						“10			저것				“ 10
p6	20	130	0	4	0	3	0	1	0		1		0	4	0
				~Ї0		10					20			10
엘	4	500	1	0	0	1	0	0	0		0		1	0	0
추신	8	300	0	1	0	0	1	0	0		0		0	1	0
아르 자형\\	중	20	0	6	0	1	0	0	1		1		4	4	1
				10		~10			저것		20		저것	10
Zj-Cj		2천만+10000	0		0	-중	0	0	m+\		-m+\		--중	-*중	0
				10		10			10	20			10	10
엘	10	380	0	14	1	0	0	0	3		2		12	0	0
				10					10		10		10
아르 자형%	20	70	0	14	0	0	0	1	3		2		12	16	-3
				10					10		10		10	10
엘	4	300	1	6	0	0	0	0	1		1		-3		-10
											2
p5	8	300	0	1	0	0	1	0	0		0		0	1	0
P4	6	200	0	-6	0	1	0	0	-1		1		4	4	10
											’ 2
Z.-Ci		10000	0	0	0	0	0	0	1	1			-중	-중	-중

기초		Lgt;	4	10	10	6	8	20	0	0	중	중	엘/
	영형		엘	Rg	ръ	아르 자형*	P5	P6	엘	팸프;	p9	엘 0	엘.
Rg	10	450	0	0	1	0	0	1	0	0
아르 자형%	0	350	0	7	0	0	0	5	3 5	1
엘	4	125	1	5 2	0	0	0	5 2	1 4	0
추신	8	300	0	1	0	0	1	0	0	0
P4	6	375	0	5 2	0	1	0	5 2	1 4	0
Zj-Cj		9650	0	-7	0	0	0	-5	1 2	0

선형 계획법은 변수와 선형 최적성 기준 사이의 선형 관계를 특징으로 하는 극한 문제를 해결하기 위한 방법을 연구하는 수학의 한 분야입니다.

선형 프로그래밍이라는 용어 자체에 대한 몇 마디입니다. 올바른 이해가 필요합니다. 이 경우 프로그래밍은 물론 컴퓨터 프로그램을 편집하는 것이 아닙니다. 여기서 프로그래밍은 계획, 계획 수립, 행동 프로그램 개발로 해석되어야 합니다.

선형 계획법의 수학적 문제에는 제한된 자원의 최적 사용에 대한 문제로 어떤 형태로든 해석되는 특정 생산 및 경제 상황에 대한 연구가 포함됩니다.

선형 프로그래밍 방법을 사용하여 해결되는 문제의 범위는 상당히 넓습니다. 예를 들면 다음과 같습니다.

· 생산 계획에서 자원의 최적 사용 문제;

· 혼합문제(제품구성기획);

· 창고 보관을 위한 다양한 유형의 제품의 최적 조합을 찾는 문제(재고 관리 또는 "배낭 문제")

· 운송 업무(기업 위치 ​​분석, 물품 이동 분석).

선형 프로그래밍은 수학 프로그래밍에서 가장 개발되고 널리 사용되는 섹션입니다(여기에는 정수, 동적, 비선형, 매개변수 프로그래밍도 포함됩니다). 이는 다음과 같이 설명됩니다.

· 다수의 경제 문제에 대한 수학적 모델은 필요한 변수에 대해 선형입니다.

· 이 유형의 문제는 현재 가장 많이 연구되고 있습니다. 이러한 문제를 해결하는 데 도움이 되는 특별한 방법과 해당 컴퓨터 프로그램이 개발되었습니다.

· 많은 선형 계획법 문제가 해결되어 폭넓게 응용되고 있습니다.

· 원래 공식에서는 선형이 아닌 일부 문제는 여러 가지 추가 제한 및 가정 후에 선형이 되거나 선형 계획법으로 해결할 수 있는 형태로 축소될 수 있습니다.

선형 계획법 문제의 경제적이고 수학적 모델에는 다음이 포함됩니다. 목적 함수, 최적의 값(최대값 또는 최소값)을 찾아야 합니다. 선형 방정식 또는 부등식 시스템 형태의 제한; 변수의 비음성 요구 사항.

일반적으로 모델은 다음과 같이 작성됩니다.

목적 함수:

F = c1x1 + c2x2 + ... + cnxn → 최대(최소);

제한:

a11x1 + a12x2 + ... + a1nxn (≤ = ≥) b1,

a21x1 + a22x2 + ... + a2nxn (≤ = ≥) b2,

am1x1 + am2x2 + ... + amnxn (≤ = ≥) bm;

비음성 요구사항:

문제는 제약 조건을 만족하면서 함수의 최적 값을 찾는 것입니다.

그래서, 선형 프로그래밍은 변수와 선형 기준 사이의 선형 관계를 특징으로 하는 극한 문제를 해결하기 위한 방법을 연구하는 수학 프로그래밍의 한 분야입니다.

선형 프로그래밍 문제를 제기하기 위한 필수 조건은 자원 가용성, 수요량, 기업의 생산 능력 및 기타 생산 요소에 대한 제한입니다.

선형 계획법의 본질은 인수에 부과된 특정 제한 세트에서 특정 함수의 가장 크거나 가장 작은 값의 점을 찾고 일반적으로 무한한 수의 해를 갖는 제한 시스템을 형성하는 것입니다. 제약 조건 시스템을 만족하는 각 변수 값(함수 F의 인수) 세트를 선형 계획법 문제의 허용 가능한 계획이라고 합니다. 최대값 또는 최소값이 결정되는 함수 F를 문제의 목적 함수라고 합니다. 함수 F의 최대 또는 최소가 달성되는 허용 가능한 계획을 문제의 최적 계획이라고 합니다.

많은 계획을 결정하는 제한 시스템은 생산 조건에 따라 결정됩니다. 선형 계획법(LP)의 임무는 실행 가능한 계획 세트에서 가장 수익성이 높은(최적) 계획을 선택하는 것입니다.

단순법의 주요 내용입니다 선형 프로그래밍 . 문제 해결은 조건 다면체의 정점 중 하나를 고려하는 것으로 시작됩니다. 연구 중인 정점이 최대값(최소값)에 해당하지 않으면 이웃 정점으로 이동하여 문제를 최대값으로 해결할 때 목표 함수의 값을 늘리고 최소값으로 문제를 해결할 때 목표 함수 값을 줄입니다. 따라서 한 정점에서 다른 정점으로 이동하면 목표 함수의 값이 향상됩니다. 다면체의 정점 수는 제한되어 있으므로 유한한 수의 단계에서 최적의 값을 찾거나 문제를 해결할 수 없다는 사실을 확립하는 것이 보장됩니다.

이 방법은 보편적이며 다음의 모든 선형 계획법 문제에 적용 가능합니다. 정식 형식. 여기서 제약 조건 시스템은 미지수의 수가 방정식의 수보다 큰 선형 방정식 시스템입니다. 시스템의 순위가 다음과 같은 경우 아르 자형 , 그러면 우리는 선택할 수 있습니다 아르 자형 나머지 미지수를 통해 표현해보겠습니다. 명확성을 위해 첫 번째 연속 미지수가 선택되었다고 가정합니다. 엑스 1 , X 2 , ..., X r . 그러면 방정식 시스템은 다음과 같이 쓸 수 있습니다.

이런 형태로 가져올 수 있습니다 모든 관절 시스템 , 예를 들어 가우스 방법을 사용합니다. 사실, 나머지 첫 번째 r개의 미지수로 표현하는 것이 항상 가능한 것은 아닙니다(우리는 표기법의 명확성을 위해 이렇게 했습니다). 그러나 그러한 아르 자형 확실히 알려지지 않은 것이 있을 것입니다. 이러한 알려지지 않은 변수(변수)를 기본이라고 하며 나머지는 무료입니다.

자유 변수에 특정 값을 할당하고 기본 값(자유 변수로 표현)을 계산함으로써 제약 조건 시스템에 대한 다양한 솔루션을 얻을 수 있습니다. 따라서 모든 솔루션을 얻을 수 있습니다. 우리는 자유 변수가 0인 경우에 얻어지는 특별한 해에 관심이 있을 것입니다. 이러한 솔루션을 기초적인, 주어진 제한 시스템의 다양한 기본 유형만큼 그 수가 많습니다. 기본 솔루션이라고합니다 허용되는 기본 솔루션또는 참조 솔루션, 그 안에 있는 변수의 값이 음수가 아닌 경우. 변수를 기본으로 삼는다면 X 1 , X 2 , ..., X r , 그러면 해결책 (b 1 , b 2 ,..., br , 0, ..., 0) 지원한다면 b 1 , b 2 ,..., br ≥ 0 .

심플렉스법은 심플렉스법의 기본 정리(fundamental theorem of the simplex method)라는 정리에 기초합니다. 정규 형식의 선형 계획법 문제에 대한 최적의 계획 중에는 반드시 제약 조건 시스템에 대한 참조 솔루션이 있습니다. 문제의 최적 계획이 고유한 경우 일부 참조 솔루션과 일치합니다. 제약 시스템에 대한 지원 솔루션은 한정되어 있습니다. 따라서 표준 형식의 문제에 대한 해결책은 참조 솔루션을 열거하고 그 중에서 가치가 있는 솔루션을 선택하여 찾을 수 있습니다. 에프 가장 큰. 그러나 첫째, 모든 참조 솔루션을 알 수 없으므로 찾아야하며, 둘째, 실제 문제에는 이러한 솔루션이 많고 직접 검색이 거의 불가능합니다. 단순 방법은 지원 솔루션을 직접 열거하기 위한 특정 절차입니다. 심플렉스법의 특정 알고리즘을 사용하여 미리 찾은 특정 참조 솔루션을 기반으로 목적 함수의 값이 적용되는 새로운 참조 솔루션을 계산합니다. 에프 오래된 것보다 적지 않습니다. 일련의 단계를 거쳐 우리는 최적의 계획인 참조 솔루션에 도달합니다.

따라서 단순 방법은 첫 번째(초기) 기본 솔루션을 찾을 때와 다른 기본 솔루션으로 이동할 때 특정 순서를 도입합니다. 그의 생각은 다음과 같습니다.

데 제한 시스템 , 일반적인 형태, 즉 다음과 같은 m 선형 방정식 시스템으로 축소됩니다. N 변수 (중< n) , 찾다 모든 기본 솔루션이 시스템은 가능한 한 간단하게 찾는 데만 신경을 씁니다.

발견된 첫 번째 기본 솔루션이 다음과 같은 것으로 밝혀졌다면 받아들일 수 있는 , 그럼 확인해봐 최적성. 그 경우 최적이 아니다 , 그런 다음 반드시 다른 것으로의 전환이 수행됩니다. 수용 가능한 기본 솔루션 .

단순 방법은 이 새로운 솔루션을 사용하여 선형 형태가 최적에 도달하지 못할 경우 이에 접근하도록 보장합니다. 그들은 최적의 솔루션을 찾을 때까지 새로운 실행 가능한 기본 솔루션으로 동일한 작업을 수행합니다.

발견된 첫 번째 기본 해결책이 다음과 같다고 밝혀지면 받아들일 수 없는 , 심플렉스 방법을 사용하면 다음이 가능합니다. 다른 기본 솔루션으로 전환, 이는 어떤 결정 단계에서 기본 솔루션이 허용되고 단순 방법 알고리즘이 적용되거나 제한 시스템의 불일치를 확신할 때까지 허용 가능한 솔루션 영역에 더 가까워집니다.

따라서 단순 방법의 적용은 두 단계로 나뉩니다. 즉, 제약 조건 시스템에 대해 허용 가능한 기본 솔루션을 찾거나 비호환성 사실을 확인하는 것입니다. 최적의 솔루션을 찾는 것입니다.
또한, 각 단계는 하나 또는 다른 기본 솔루션에 해당하는 여러 단계를 포함할 수 있습니다. 그러나 기본해의 개수는 항상 제한되어 있기 때문에 단순법의 단계 수도 제한됩니다.

단순 방법의 주어진 다이어그램은 알고리즘 특성(순차 작업 실행에 대한 명확한 명령의 특성)을 명확하게 표현하므로 이 방법을 컴퓨터에서 성공적으로 프로그래밍하고 구현할 수 있습니다. 소수의 변수와 제약 조건이 있는 문제는 단순 방법을 사용하여 수동으로 해결할 수 있습니다.

알고리즘의 본질에 대해 더 자세히 설명하지 않고 계산 측면을 설명하겠습니다. 단순 방법을 사용한 계산 형태로 구성되어 있습니다 단순 테이블, 이는 정규 형식의 선형 계획법 문제를 간략하게 표현한 것입니다. 컴파일하기 전에 단순 테이블임무는 다음과 같아야합니다 변환됨 , 제한 시스템로 감소 허용되는 기본 형태, 이를 통해 기본 변수를 대상 함수에서 제외해야 합니다. 아래에서는 이러한 예비 변환 문제를 고려할 것입니다. 이제 작업이 이미 완료되었으며 작업의 형식이 다음과 같다고 가정하겠습니다.

서비스의 목적. 온라인 계산기는 다음과 같이 단순 방법을 사용하여 선형 계획법 문제를 해결하도록 설계되었습니다. KZLP그리고 SZLP. 이 경우 목적함수의 최소값을 구하는 문제는 목적함수 F*(X) = -F(X) 의 변환을 통해 최대값을 구하는 문제로 축소됩니다. 이중 문제를 만드는 것도 가능합니다.

해결 방법은 세 단계로 이루어집니다.

1. KZLP로 전환합니다. ax ≤ b , ax ≥ b , ax = b (F(X) → extr) 형식의 모든 LLP는 ax = b , F(X) → max 형식으로 축소됩니다.
2. SZLP로 전환합니다. ax = b 형식의 CLLP는 ax ≤ b 형식, F(X) → max로 축소됩니다.
3. 단순 방법을 사용한 솔루션;

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

변수의 수 2 3 4 5 6 7 8 9 10
행 수(제한 수) 1 2 3 4 5 6 7 8 9 10

목적함수 최소화 문제에서 최대화 문제로 전환

목적 함수 F(X)를 최소화하는 문제는 F*(X) = -F(X) 함수를 도입하여 동일한 제한 하에서 함수 F*(X)를 최대화하는 문제로 쉽게 축소될 수 있습니다. 두 문제 모두 동일한 해 X*를 가지며 동시에 min(F(X)) = -max(F*(X)) 를 갖습니다.
이 사실을 그래픽으로 설명해 보겠습니다.

F(x) → 최소

F(x) → 최대

목표 함수를 최적화하기 위해 다음 개념과 방법을 사용합니다.
기본 계획– 자유로운 기본 변수를 통해 정의된 계획입니다.
기본계획– 기본 변수가 없는 참조 계획.
최적의 계획– 최적의 목적함수(OF)를 만족하는 기본계획.

선행(해결) 요소는 자유 미지의 계수로 기본이 되며 계수 자체가 1로 변환됩니다.
지침- 기본 미지수가 단위 계수와 함께 위치하는 선행 요소의 선은 변환 중에 제외됩니다(최소 제한 계수가 있는 선, 아래 참조).
가이드 칼럼– 선행 요소의 열, 미지의 자유 요소가 기본 요소로 변환됩니다(최대 이점이 있는 열, 아래 참조).

시스템의 한 방정식에만 단일 계수가 포함되고 나머지 방정식에는 0 계수가 포함된 변수 x 1, …, x m을 호출합니다. 기초적인또는 매달린. 표준 시스템에서 각 방정식은 정확히 하나의 기본 변수에 해당합니다. 전환은 Gauss-Jordan 방법을 사용하여 수행됩니다. 이 방법의 주요 아이디어는 문자열에 대한 기본 연산을 사용하여 n개의 미지수가 있는 m개의 방정식 시스템을 표준 형식으로 줄이는 것입니다.
나머지 n-m 변수(x m +1 ,…, x n)는 다음과 같이 호출됩니다. 기본이 아닌또는 독립 변수.

기본 솔루션~라고 불리는 허용되는 기본 솔루션, 그 안에 포함된 기본 변수의 값이 x j ≥0인 경우, 이는 비음성 조건 b j ≥0과 동일합니다.
실현 가능한 기본 솔루션은 다음과 같습니다. 코너 포인트선형 계획법 문제의 허용 가능한 집합 S이며 때때로 호출됩니다. 참고 계획.
음수가 아닌 숫자 b j 중 0과 같으면 허용되는 기본 솔루션이 호출됩니다. 퇴화하다(축퇴된 코너 포인트) 그리고 이에 상응하는 선형 계획법 문제가 호출됩니다. 퇴화하다.

예 1. 선형 프로그래밍 문제를 표준 ZLP로 줄입니다.
F(X) = x 1 + 2x 2 - 2x 3 → 최소(제한 있음):
4x1 + 3x2 - x3 ≤10
- 2x 2 + 5x 3 ≥3
엑스 1 + 2x 3 =9
ZLP를 정식 형식으로 가져오려면 다음이 필요합니다.
1. 목적 함수의 부호를 변경합니다. 문제 F(X) → min을 문제 F(X) → max로 줄여보겠습니다. 이렇게 하려면 F(X)에 (-1)을 곱합니다. 첫 번째 의미 부등식(≤)에서 기본 변수 x 4 를 도입합니다. 두 번째 의미 부등식(≥)에서는 기본 변수 x 5를 빼기 기호로 도입합니다.
4x1 + 3x2 -1x3 + 1x4 + 0x5 = 10
0x1 -2x2 + 5x3 + 0x4 -1x5 = 3
1x1 + 0x2 + 2x3 + 0x4 + 0x5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
SZLP로 전환.
이 문제에 대한 등식 제약 조건의 확장된 매트릭스:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

조던 변환 방법을 사용하여 시스템을 단위 행렬로 축소해 보겠습니다.
1. x 4를 기본 변수로 선택할 수 있습니다.
2. x 2를 기본 변수로 선택합니다.
분해능 요소 RE=-2. 변수 x 2에 해당하는 라인은 라인 x 2의 모든 요소를 ​​분해 요소 RE = -2로 나누어 얻습니다. 해결 요소 대신 1을 얻습니다. x 2 열의 나머지 셀에는 0을 씁니다. 다른 모든 요소는 직사각형 규칙에 따라 결정됩니다. 각 요소의 계산을 표 형식으로 제시해 보겠습니다.

4-(0 3):-2	3-(-2 3):-2	-1-(5 3):-2	1-(0 3):-2	0-(-1 3):-2	10-(3 3):-2
0: -2	-2: -2	5: -2	0: -2	-1: -2	3: -2
1-(0 0):-2	0-(-2 0):-2	2-(5 0):-2	0-(0 0):-2	0-(-1 0):-2	9-(3 0):-2

우리는 새로운 행렬을 얻습니다:

4	0	6 1 / 2	1	-1 1 / 2	14 1 / 2
0	1	-2 1 / 2	0	1 / 2	-1 1 / 2
1	0	2	0	0	9

3. x 3을 기본 변수로 선택합니다.
분해능 요소 RE=2. 변수 x 3에 해당하는 라인은 라인 x 3의 모든 요소를 ​​분해 요소 RE=2로 나누어 얻습니다. 해결 요소 대신 1을 얻습니다. x 3 열의 나머지 셀에는 0을 씁니다. 다른 모든 요소는 직사각형 규칙에 따라 결정됩니다. 각 요소의 계산을 표 형식으로 제시해 보겠습니다.

4-(1 6 1 / 2):2	0-(0 6 1 / 2):2	6 1 / 2 -(2 6 1 / 2):2	1-(0 6 1 / 2):2	-1 1 / 2 -(0 6 1 / 2):2	14 1 / 2 -(9 6 1 / 2):2
0-(1 -2 1 / 2):2	1-(0 -2 1 / 2):2	-2 1 / 2 -(2 -2 1 / 2):2	0-(0 -2 1 / 2):2	1 / 2 -(0 -2 1 / 2):2	-1 1 / 2 -(9 -2 1 / 2):2
1: 2	0: 2	2: 2	0: 2	0: 2	9: 2

우리는 새로운 행렬을 얻습니다:

3 / 4	0	0	1	-1 1 / 2	-14 3 / 4
1 1 / 4	1	0	0	1 / 2	9 3 / 4
1 / 2	0	1	0	0	4 1 / 2

시스템에는 단위 행렬이 있으므로 X = (4,2,3)을 기본 변수로 사용합니다.
해당 방정식은 다음과 같습니다.
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1/4 x 1 + x 2 + 1/2 x 5 = 9 3/4
1/2 x 1 + x 3 = 4 1/2
나머지 측면에서 기본 변수를 표현해 보겠습니다.
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1/4 x 1 - 1/2 x 5 +9 3/4
x 3 = - 1 / 2 x 1 +4 1 / 2
이를 대상 함수로 대체해 보겠습니다.
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
또는

불평등 시스템:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1/4 x 1 - 1/2 x 5 +9 3/4 ≥ 0
- 1/2 x 1 +4 1/2 ≥ 0
불평등 시스템을 다음 형식으로 줄입니다.
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1/4 x 1 + 1/2 x 5 ≤ 9 3/4
1/2 x 1 ≤ 4 1/2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → 최대
시스템을 단순화해보자.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1/4 x 1 + 1/2 x 2 ≤ 9 3/4
1/2 x 1 ≤ 4 1/2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → 최대

예 2. 먼저 그래픽 방법을 사용하고 그 다음에는 단순 방법을 사용하여 문제에 대한 해결책을 찾습니다.
F(X) = x 1 + x 2 - x 3 + x 5 +15 → 최대(최소)(제한 있음):
-3x1 + x2 + x3 =3
4x1 + 2x2 - x4 =12
2x1 - x2 + x5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0