선형 계획법 문제를 해결하기 위한 수정된 심플렉스 방법입니다. 수정된 심플렉스 방법
최적화 문제수학에서는 특정 영역에서 실수 함수의 극값을 찾는 문제입니다. 일반적으로 일련의 평등과 불평등에 속하고 이에 의해 정의되는 영역이 고려됩니다.
3.1. 설명
선형 계획법 문제는 주어진 선형 제약 조건 하에서 다차원 공간에서 일부 선형 함수를 최대화하거나 최소화해야 한다는 것입니다.
변수의 각 선형 부등식은 해당 선형 공간의 절반 공간을 제한합니다. 결과적으로 모든 부등식은 다면체 원뿔이라고도 불리는 특정 다면체(무한할 수 있음)를 묶었습니다.
W(x)가 최대화(또는 최소화)될 선형 함수인 방정식 W(x) = c는 초평면 L(c)를 생성합니다. c에 대한 의존성은 평행 초평면 계열을 생성합니다. 이 경우 극값 문제는 다음 공식을 취합니다. 초평면 L(c)가 다면체와 적어도 한 지점에서 교차하도록 하는 가장 큰 c를 찾는 것이 필요합니다. 최적의 초평면과 다면체의 교차점에는 적어도 하나의 꼭지점이 포함되며, 교차점에 모서리나 k차원 면이 포함된 경우에는 두 개 이상이 있을 것입니다. 따라서 다면체의 꼭지점에서 함수의 최대값을 찾을 수 있습니다. 단순 방법의 원리는 다면체의 꼭지점 중 하나를 선택한 후 기능 값을 증가시키는 방향으로 꼭지점에서 꼭지점으로 가장자리를 따라 이동이 시작된다는 것입니다. 현재 정점에서 더 높은 함수값을 갖는 다른 정점으로의 변이를 따라 전환하는 것이 불가능할 경우, 최적의 c 값을 찾은 것으로 간주됩니다.
단순 방법의 본질은 미지수의 수가 방정식의 수보다 크면 주어진 시스템은 무한한 수의 해로 인해 불확실하다는 것입니다. 시스템을 해결하기 위해 모든 미지수를 기본과 자유로 임의로 구분합니다. 기본 변수의 수는 선형 독립 방정식의 수에 따라 결정됩니다. 나머지 미지수는 무료입니다. 임의의 값이 부여된 다음 시스템에 대체됩니다. 임의의 자유 미지수 집합에는 무한한 수의 임의 값이 주어질 수 있으며, 이는 무한한 수의 해를 제공합니다. 모든 자유 미지수가 0으로 설정되면 솔루션은 기본 미지수 값으로 구성됩니다. 이 솔루션을 기본이라고 합니다.
선형 계획법 이론에는 시스템의 기본 해 중에서 최적의 해를 찾을 수 있고 어떤 경우에는 여러 가지 최적 해를 찾을 수 있으며 모두 목적 함수의 극한값을 제공한다는 정리가 있습니다. 따라서 몇 가지 기본 계획을 찾아 이를 개선하면 최적의 솔루션을 얻을 수 있습니다. 단순 방법은 이 원칙을 바탕으로 만들어졌습니다.
단순 방법을 사용한 계산 순서는 두 가지 주요 단계로 나눌 수 있습니다.
1. 실현 가능한 솔루션 세트의 초기 꼭지점을 찾습니다.
2. 정점에서 정점으로의 순차적 전환으로 인해 목적 함수 값이 최적화됩니다.
어떤 경우에는 초기 솔루션이 명확하거나 해당 정의에 복잡한 계산이 필요하지 않습니다. 예를 들어 모든 제약 조건이 "작거나 같음" 형식의 부등식으로 표현되는 경우(0 벡터는 절대적으로 허용되는 솔루션입니다. 그러나 아마도 최적과는 거리가 멀다). 이러한 문제에서는 단순법의 첫 번째 단계를 모두 생략할 수 있습니다. 따라서 Simplex 방법은 다음과 같이 나뉜다. 단상그리고
2상.
3.2. 단순 방법 알고리즘
강화된 문제 설명
다음 선형 계획법 문제를 고려하십시오.
이제 이 문제를 동등한 강화 형태로 제시해 보겠습니다. Z를 최대화하는 것이 필요합니다. 여기서:
여기서 x는 원래 선형 함수의 변수입니다. x s - 불평등이 평등으로 바뀌는 방식으로 이전 변수를 보완하는 새로운 변수입니다. c – 원래 선형 함수의 계수; Z는 최대화되어야 하는 변수입니다. 절반 공간과 교차점은 실행 가능한 솔루션 세트를 나타내는 다면체를 형성합니다. 변수 수와 방정식 수의 차이가 자유도를 나타냅니다. 간단히 말해서, 다면체의 꼭지점을 고려하면 이는 우리가 계속해서 이동할 수 있는 모서리의 수입니다.
그런 다음 이 변수 수에 값 0을 할당하고 호출할 수 있습니다.
1.5.1. 역행렬의 변환을 기반으로 하는 계산 방식입니다.노동강도를 추정하는 관점에서 단순법의 계산과정을 분석해 보면, 이 점에서 가장 중요한 것은 값을 재계산하는 단계임을 쉽게 알 수 있다. ㅏ그리고 비하나의 기본 계획에서 다른 기본 계획으로 이동할 때(알고리즘의 3항) 그러나 문제의 제약 개수가 많은 경우 중확실히 변수가 적다 N, 다음 반복을 수행하면 상당한 "절약"을 달성할 수 있습니다. 큐행렬이 아닌 Jordan-Gauss 변환 ㅏ(β ( 큐)), 그리고 행렬 Δ -1 (β ( 큐)). 이는 또한 필요한 경우 공식 (1.26)을 사용하여 항상 다음을 얻을 수 있다는 사실을 고려합니다. ㅏ(β ( 큐)) by Δ -1 (β ( 큐)). 또한 위에서 설명한 단순 절차의 작업을 수행하기 위해 실제로 행렬이 필요하지 않았습니다. ㅏ(β ( 큐)) 전적으로. 실제로는 등급선만 사용되었습니다. ㅏ 0 (β ( 큐)) 및 선행 열 알(β ( 큐)). 이러한 고려 사항은 역행렬의 변환을 기반으로 하는 단순 방법의 계산 체계의 기초를 형성합니다. 수정된 심플렉스 방법. 이 알고리즘은 L. V. Kantorovich의 작업에서 1951년에 처음 제안되었습니다.
수정된 심플렉스 방법의 계산 방식은 테이블 시스템에 해당합니다. 티 1과 티 2 (큐) . 테이블 티 1 (쌀. 1.7)은 모든 반복에 공통적이며 현재 기준선에 대한 추정치를 얻는 데 사용됩니다. ㅏ 0 (β ( 큐)). δ로 표시하면 나(β ( 큐)) (나Î 0: 중) 행렬 Δ -1 (β ( 큐)), 특히 (1.26)에서 다음과 같습니다.
에서 알 수 있듯이 쌀. 1.7, 티 1은 세 개의 블록으로 구성됩니다.
Ø Ø 중앙에는 행렬 A가 포함되어 있습니다.;
Ø Ø 각 반복마다 테이블의 왼쪽 블록에 행렬의 0행이 추가됩니다.Δ -1 (β ( 큐))현재 기준으로;
Ø Ø 행렬 A 아래에 있는 아래쪽 블록, 각 반복마다 공식(1.42)을 사용하여 계산된 현재 계획의 추정 라인이 보완됩니다.
심플렉스 테이블 티 2 (큐)에 표시됨 쌀. 1.8, 허용되는 KZLP 기준 β ( 큐) 에 수신됨 큐번째 반복. 열 N(β ( 큐)) 기본 열의 번호를 포함합니다(기본에서 발생 순서대로). 열 비(β ( 큐)) - 현재 기저 β에 대한 제약 벡터의 구성 요소 큐) ; Δ -1 (β ( 큐)) - 현재 기저의 확장 열 행렬에 역행렬 β ( 큐) ; 그래프 알현재 반복에서 기본에 도입된 조건의 확장된 벡터를 포함하고 다음 그래프에는 좌표가 포함됩니다. 알(β ( 큐)) 현재 베이시스의 동일한 열 β( 큐) .
단락 1.4.1과 유사하게 수정된 심플렉스 방법 알고리즘의 형식적 체계를 설명합니다.
0단계. 실현 가능한 기준선 찾기.
1. 허용 가능한 근거를 찾기 위해 단락 1.4.5에서 논의된 잔차를 최소화하는 방법을 적용할 수 있습니다. 이 경우 보조 문제를 해결하기 위해 수정된 심플렉스 방법의 절차를 사용합니다. 0단계의 결과로 우리는 실행 가능한 기준선을 얻습니다. 엑스(β (1)) 및 해당 행렬 Δ -1 (β (1)) 및 벡터 비(β(1)).
2. 표의 중앙부분을 채워주세요 티행렬을 포함하는 1개 ㅏ.
3. 행렬 Δ -1(β(1))과 벡터의 내용 비허용 가능한 기본 계획을 검색하는 단계에서 얻은 (β (1))이 테이블로 전송됩니다. 티 2 (1) .
4. 현재 반복 횟수 설정 큐 1과 동일하고 1단계로 이동합니다.
스테이지 1. 알고리즘의 표준 반복- 차기 기본계획으로 추진 엑스(β ( 큐)).
1°. 현재 기준 계획의 최적성 확인. 테이블의 0행 내용 티 2 (큐) - δ 0 (β ( 큐))는 테이블의 해당 열에 다시 작성됩니다. 티 1 . 공식 (1.42)을 사용하여 다음 줄을 계산하고 채웁니다. ㅏ 0 (β ( 큐)). 평가선을 본다 ㅏ 0 (β ( 큐)). 두 가지 옵션이 있습니다:
1. ㅏ 0 (β ( 큐))≥0 -문제의 현재 기반에 해당하는 계획, 최적.계산 과정이 완료되었습니다. 공식 (1.33)과 (1.32)에 따라 문제에 대한 최적의 계획이 작성됩니다. 엑스* = 엑스(β ( 큐)) 및 목적 함수의 최적 값 에프(엑스*) = 에프(엑스(β ( 큐))).
1". 등급 라인에서 ㅏ 0 (β ( 큐)) 적어도 하나의 요소가 있습니다 ㅏ 0, 제이(β ( 큐))<0, т. е. имеющий отрицательную оценку. Следовательно, план 엑스(β ( 큐)) - 최적이 아닌. 번호가 선택되었습니다 엘, 최소(절대값의 최대값) 음수 점수를 갖는 요소에 해당:
엘번째 행렬 열 ㅏ된다 주요한그리고 다음 베이시스에 입력되어야 합니다. 알고리즘의 2° 지점으로 넘어가겠습니다.
2°. 기준에서 파생된 열 정의. 선행 열 다시 작성 알테이블에서 티 1부터 현재 테이블까지 티 2 (큐) . 공식에 따르면 알(β ( 큐)) = Δ -1 (β ( 큐))알표의 해당 열을 채우십시오. 티 2 (큐) . 두 가지 옵션이 있습니다:
2". 모두를 위해 나오 1: 나, 나, 나(β ( 큐))≤0. 결론은 목적 함수의 무한성그리고 컴퓨팅 프로세스가 종료됩니다.
2". 인덱스가 하나 이상 있습니다. 나오 1: 중, 이를 위해 나, 나(β ( 큐))>0. 규칙(1.27)에 따라 위치가 결정됩니다. 아르 자형그리고 숫자 번호(β ( 큐)) 기준에서 파생된 열의 경우. 알고리즘의 3° 지점으로 넘어가겠습니다.
3°. b 열 요소의 새로운 기준을 기준으로 재계산그리고 행렬Δ -1. 새로운 기반으로의 전환 β ( 큐+1) , 이는 β( 큐) 열 알그리고 거기에서 열을 출력 아르는 공식 (1.28)-(1.31)과 유사한 공식에 따라 수행됩니다. 그들은 다음과 같습니다:
현재 반복 횟수를 설정합니다. 큐: =큐+l 알고리즘의 첫 번째 지점으로 이동합니다.
결론적으로, 위의 장점으로 인해 정식 선형 계획법 문제를 해결하기 위해 설계된 소프트웨어에서 실제로 사용되는 것이 수정된 심플렉스 방법임을 강조합니다.
1.5.2. 수정된 심플렉스 방법을 사용하여 ZLP를 푸는 예입니다.수정된 심플렉스 방법의 절차를 사용하여 이전에 고려한 문제 (1.34)-(1.35)에 대한 해결책을 제시해 보겠습니다. 섹션 1.4.3과 유사하게 열(5,2,3)으로 구성된 명확한 초기 기저를 선택하는 것으로 시작됩니다. 이를 위해 Δ -1 (β ( 큐)) 그리고 비(β ( 큐)), 따라서 초기 테이블을 작성합니다. 티 1과 티 2(1)은 어렵지 않습니다.
첫 번째 반복에서는 제로 라인을 다시 작성합니다.
~에서 티 2(1)인치 티 1에 행렬을 곱합니다. ㅏ, 우리는 평가 라인을 얻습니다
왜냐하면 ㅏ 0(β(1))에 음수 요소가 포함되어 있으면 기저 β(1)에 해당하는 계획이 최적이 아니라고 결론을 내리고 가장 작은 음수 추정치(-88)를 선택하여 입력된 열의 수를 얻습니다. 기본, 엘= 4.
칼럼 다시 쓰기
테이블에서 티 1인치 티 2 (1) 현재 기준을 기준으로 좌표를 다시 계산합니다. 즉, 행렬 Δ -1 (β ( 큐)), 표에 위치 티왼쪽에 2(1), ㅏ 4 .
테이블을 다 채운 후 티 2 (1) 새 기준에 입력된 열의 데이터를 사용하여 출력 열의 수를 결정할 수 있습니다. 이 절차는 기존의 심플렉스 방법과 완전히 유사하게 수행됩니다. 요소들의 관계를 고려한 결과 비 나는(β(1)) 및 나, 나(β(1))에 대한 ( 나О1: 남| 나, 나(β(1))>0) 그리고 이들 중 최소값을 결정한 후 다음을 발견합니다. 아르 자형= 2. 따라서 숫자가 있는 열은 N 2 (β ( 큐)) = 2는 기저에서 파생되어야 합니다. 따라서 우리는 문제에 대한 또 다른 허용 가능한 근거를 얻습니다. N(β(2)) = (5, 4, 3). 요소 ㅏ 2.3(β(1))이 앞서고 있습니다(원). 공식 (1.43)-(1.46)을 적용하여 두 번째 반복에 해당하는 단순 테이블로 이동합니다. 티 2 (2) , 현재 반복의 인덱스를 설정합니다. 큐 = 2.
동일한 단계를 반복합니다(여기에 제공된 표에서 쉽게 따를 수 있음). 티 2 (2) 및 티 2(3), 세 번째 반복에서는 문제의 최적 계획과 표의 두 번째 열에서 추출된 목적 함수의 최적 값을 얻습니다. 티 2 (3) . 솔루션 프로세스에서 우리는 섹션 1.4.3에서 접했던 허용 가능한 기본 계획의 동일한 순서를 "진행"했다는 것을 쉽게 알 수 있습니다.
연방교육청
고등 전문 교육을 받는 주립 교육 기관
페름 주립 기술 대학
Lysvensky 지점
경제학과
코스 작업
"시스템 분석 및 운영 연구" 분야에서
주제: "프레젠테이션 형식의 단순 방법"
VIVT-06-1 그룹의 학생이 작성함:
스타세바 N. S.
교사가 확인한 내용:
Mukhametyanov I.T.
리스바 2010
소개. 삼
수학 프로그래밍. 5
그래픽 방법. 6
표 형식의 단순 방법. 6
인공적인 기초 방법. 7
수정된 심플렉스 방법. 7
이중 단순 - 방법. 7
선형 계획법 문제의 일반적인 관점. 9
심플렉스 방법을 사용하여 선형 프로그래밍 문제를 해결합니다. 열하나
단순법의 계산 절차. 열하나
정리 1: 13
정리 2: 14
정리 3: 15
정리 4: 15
정리 5: 15
새로운 참조 계획으로 전환합니다. 15
이중 작업. 17
정리 1(첫 번째 이중성 정리) 18
정리 2(두 번째 이중성 정리) 18
결론. 20
선형 계획법 문제에 대한 최적의 솔루션은 참조 솔루션 중 하나입니다. 심플렉스 방법의 개념은 특정 규칙에 따라 그 중에서 최적의 참조 솔루션을 찾을 때까지 참조 솔루션을 정렬하는 것입니다. 기본적으로 다양한 기본 변수를 정렬하는 것입니다. , 다음 단계에서는 기본 변수 중 일부 변수가 전송되고 대신 무료 변수 수에서 기본 변수 수로 일부 변수가 전송됩니다.
7x 1 +5x 2 →최대
x 3 =19-2x 1 -3x 2 (0;0;19;13;15;18)
x 4 =13-2x 1 -x 2 원래 참조 계획
x 6 =18-3x 1 F(x 1 , x 2)=7*0+5*0=0
x i ≥0, (i=1,…n)
직관적인 수준에서는 x 1에 대한 계수가 x 2보다 크기 때문에 x 1을 늘리는 것이 자연스러울 것임이 분명합니다. x 2 =0으로 두면 x 3 , x 4 , x 5 , x 6 이 음수가 아닌 상태로 유지될 때까지 증가할 수 있습니다.
x 1 =최소(19/2;13/2;무한;18/3)=6
즉, x 1 =6, x 6 =0일 때, 즉 기본 개수에는 x 1이 들어가고, 자유 개수에는 x 6이 들어간다는 뜻입니다.
x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2
x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2
F(x 2 ; x 6) =42-7/3 x 6 +5 x 2
주어진 참조 계획(6;0;7;1;15;0) x 2를 사용하여 무료 변수에서 기본 변수로 전환합니다.
x 2 =최소(무;7/3;1/11;15/3)=1
익스프레스 x 2 ~ x 4
x 2 =1+2/3 x 6 - x 4
알 수 없는 변수와 목적 함수를 자유 변수로 표현합니다.
x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4
x 5 = 12-2x 6 +3x 4 -
F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4
x 6은 양수이므로 늘릴 수 있습니다.
x 6 =최소(18;무한대;3;6)=1
x 4 =4/3-4/9 x 6 - 1/3x 3
F=47+x 6 -5(4/3-4/9-1/3x 3)
목적 함수에서 변수의 모든 계수는 음수이며 함수의 값은 증가할 수 없습니다. 마찬가지로 나머지 변수를 변환하고 x 1, x 2를 결정하는 참조 계획을 찾습니다.
1. 닫힌 집합의 교집합, 사소하지 않은 제한 집합.
2. 선형 비엄격 부등식 및 방정식 시스템에 대한 솔루션 세트는 닫혀 있습니다.
αX=(αx 1 ,x 2 ,…, αx n)
X+Y=(x 1 +y 1, x 2 +y 2,… xn +y n)
선형 좌표 X 1 ,X 2 ,…X n을 점 P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k라고 합니다.
P=(λ 1 x 1 + λ 2 x 2 +…+ λ k x k ) 0≤ h i ≤1 for i= 1,…k n åR i =1, 1≤ i ≤k 점 x 1 ,x의 볼록 선형 조합 설정 2 ,…xn . k=2이면 이 세트를 세그먼트라고 합니다. X 1,X 2 – 세그먼트의 끝입니다. 닫힌 집합의 꼭지점은 집합의 점들(모서리 점)의 중요하지 않은 선형 조합이 아닌 점입니다.
비사소성은 λ 중 적어도 하나가 0 또는 1과 다르다는 것을 의미합니다.
 |
선형 계획법 문제에 대한 참조 솔루션은 실현 가능한 솔루션 영역의 모퉁이점입니다.
선형 프로그래밍 문제에 고유한 솔루션이 있는 경우 해당 솔루션은 ODP의 꼭지점 사이에 있습니다. 그리고 둘 이상의 솔루션이 있는 경우 솔루션 중에는 여러 각도 솔루션이 있으므로 모든 솔루션의 집합은 볼록 선형 조합입니다.
단순 방법은 먼저 문제에 대한 특정 참조 솔루션(초기 참조 계획)을 찾은 다음 의도적으로 하나의 참조 계획에서 다른 참조 계획으로 이동하여 최적의 계획을 검색하는 것으로 구성됩니다. 그 중 여러 개가 있으면 모든 모서리가 발견되고 솔루션 세트가 선형 조합으로 표시됩니다.
새로운 참조 계획으로 이동
F 1 =F(x 1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 는 증명될 수 있으며, 여기서 υ k는 위에서 고려한 최소값으로 k번째 변수를 기저에 도입하여 결정되며, Δ k =åс j x j ( 1) -С k, 여기서 n ≤ j ≤1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1))은 k 번째 변수의 추정치입니다. 따라서 최대 문제가 해결되면 ΔF 2 값은 양수여야 하고 Δk는 음수여야 합니다. 최소 문제를 풀 때 ΔF 2는 음수이고 Δk는 양수입니다. 이 값은 계산되며 ΔF 2 중 모든 값이 양수가 아닌 경우 문제를 최소한으로 해결할 때 그 반대입니다. 최대값을 풀 때 ΔF 2 중에 여러 개의 양수 값이 있는 경우 이 값이 최대값에 도달하는 벡터를 기저에 입력하고 문제가 최소값에 대해 해결되고 ΔF 2 중에 여러 개의 음수 값이 있는 경우 1이면 가장 작은 값 ΔF 2를 갖는 벡터가 기본, 즉 절대값이 가장 큰 벡터에 포함됩니다. 이러한 조건이 충족되면 함수 값의 가능한 최대 변화가 보장됩니다.
기저에 포함되지 않은 벡터 x k에 대해 Δ k ≠0을 추정하면 문제에 대한 해가 고유합니다. 이 중 적어도 하나가 Δ k = 0이면 해가 고유하지 않으므로 다른 해를 찾기 위해 이동합니다. x k 기준을 포함하는 또 다른 참조 계획(여기서 Δ k =0). 이러한 모든 지원 솔루션을 검색하면 선형 조합으로 구성되어 문제에 대한 솔루션이 됩니다.
일부 Δ k에 대해 변수 x k ≤ 0에 대한 계수가 최적 조건과 모순되는 경우 제한 시스템은 제한되지 않습니다. 즉, 최적 계획이 없습니다.
이중 문제
이중 문제(DP)는 직접 문제의 조건에서 직접 특정 규칙을 사용하여 공식화된 보조 선형 계획법 문제입니다. 이중 문제를 해결하여 직접적인 문제에 대한 최적의 솔루션을 결정하는 데 관심이 있는 이유는 DP를 해결할 때의 계산이 직접 문제(DP)를 해결할 때보다 덜 복잡할 수 있다는 사실 때문입니다. LLP를 풀 때 계산의 복잡성은 변수 수보다는 제약 조건 수에 따라 크게 달라집니다. PD로 가려면 PD를 표준 표준 형식으로 작성해야 합니다. 보호프로파일을 표준 형식으로 표시할 때 변수 xj에는 중복 변수와 잔차 변수도 포함됩니다.
이중 문제는 다음과 같습니다.
1. 직접 문제의 제약 조건 수에 해당하는 m개의 변수;
2. 직접 문제의 변수 수에 해당하는 n개의 제한 사항.
이중 문제는 다음 규칙에 따라 직접 문제의 조건을 대칭 구조로 변환하여 얻습니다.
· 각 제약 조건 b i PD는 변수 y i PD에 해당합니다.
· 각 변수 xjPD는 제약조건 CjPD에 해당합니다.
· PD 제약조건의 xj에 대한 계수는 해당 PD 제약조건의 왼쪽 계수가 됩니다.
· PD의 목표 함수에서 xj에 대한 계수 Cj는 PD 제약 조건의 오른쪽에서 일정해집니다.
· 제약 상수 b i PD 는 목표 함수 PD의 계수가 됩니다.
다음 두 가지 문제를 고려하십시오.
F = С 1 x 1 +С 2 x 2 +... +С n x n →최대
|
a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m
xj ≥0 j=1,…,n
Z = b 1 x 1 +b 2 x 2 +... +b n x n →min
|
a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2
. . . . . . . . . . . . . . . . . . . . . . .
a 1 n y n + a 2 m y n + ... + a nm y n ≤C n
이 과정은 선형 프로그래밍 문제를 해결하기 위한 수학적 방법의 기초를 마련했습니다. 따라서 다음 섹션에 더 많은 관심을 기울였습니다.
1. 수학적 방법의 기초와 그 적용
2. 단순 방법을 사용하여 문제를 해결합니다.
선형 계획법 문제를 해결하는 방법에는 여러 가지가 있습니다. 그 중 하나인 개선된(수정된) 심플렉스 방법을 고려해 보겠습니다.
먼저 심플렉스법(Simplex Method)이 무엇인지 알려드리겠습니다. 일반적인 의미에서 SIMPLEX라는 단어는 COMPLEX와는 반대로 단순하고 비복합적이라는 의미를 갖습니다.
이 방법은 여러 가지 다른 형태(수정)를 거쳐 1947년 G. Danzig에 의해 개발되었습니다.
단순 방법의 본질은 미지수의 수가 방정식의 수보다 크면 주어진 시스템은 무한한 수의 해로 인해 불확실하다는 것입니다. 시스템을 해결하기 위해 모든 미지수를 기본과 자유로 임의로 구분합니다. 기본 변수의 수는 선형 독립 방정식의 수에 따라 결정됩니다. 나머지 미지수는 무료입니다. 여기에는 임의의 값이 부여되어 시스템에 대체됩니다. 임의의 자유 미지수 집합에는 무한한 수의 임의 값이 주어질 수 있으며, 이는 무한한 수의 해를 제공합니다. 모든 자유 미지수가 0으로 설정되면 솔루션은 기본 미지수 값으로 구성됩니다. 이 솔루션을 기본이라고 합니다.
선형 프로그래밍 이론에는 시스템의 기본 솔루션 중에서 최적의 솔루션을 찾을 수 있고 어떤 경우에는 여러 가지 최적의 솔루션을 찾을 수 있지만 모두 목적 함수의 극한값을 제공한다는 정리가 있습니다. 따라서 몇 가지 기본 계획을 찾아 이를 개선하면 최적의 솔루션을 얻을 수 있습니다. 단순 방법은 이 원칙을 바탕으로 만들어졌습니다.
심플렉스 방법의 변형 중 하나는 향상된 심플렉스 방법입니다. 문헌에서는 이 방법을 역행렬법(Inverse Matrix Method) 또는 변형 심플렉스법(Modified Simplex Method)이라는 이름으로도 찾아볼 수 있다.
n(변수 수)이 m(제약 조건 수)보다 훨씬 큰 선형 계획법 문제를 풀 때 개선된 심플렉스 방법은 다른 방법에 비해 훨씬 적은 계산 작업과 컴퓨터 메모리를 필요로 합니다.
개선된 단순 방법은 기존 단순 방법과 동일한 기본 아이디어를 구현하지만 여기에서는 각 반복에서 제약 행렬 A의 역행렬인 전체 행렬 A -1이 다시 계산되지 않고 현재 기저 A와 관련된 부분만 다시 계산됩니다. 엑스.
향상된 심플렉스 방법을 사용하여 선형 계획법 문제를 해결하는 단계를 단계별로 살펴보겠습니다.
- 1. 첫 번째 사이클이 시작될 때 우리는 기본 해 x b = b인 역행렬(단위 행렬)을 알게 됩니다.
- 2. 각 비기본 변수에 대해 다음 방정식을 사용하여 특성 차이 j를 형성합니다.
j = c j -- = c j -- P j , (2)
다음과 같이 찾을 수 있는 이중 변수는 어디에 있습니까?
여기서 c x는 기본 변수에 대한 목적 함수의 계수 벡터입니다.
3. 입력 열을 선택하는 표준 규칙이 사용된다고 가정하면 다음과 같습니다.
- 4. s 0이면 절차가 중지됩니다. 현재 기본 솔루션이 최적입니다.
- 5. s 0이면 변환된 열을 계산합니다.
= (, ...,) . (2.4)
모두 0이면 절차가 중지됩니다. 최적값은 무제한입니다.
7. 그렇지 않으면 기저에서 파생된 변수를 찾습니다.
8. 확대된 매트릭스를 구축합니다.
그리고 이를 선행 요소로 변환합니다. 처음 m개의 열은 새로운 기저의 역행렬을 제공합니다.
9. 기본 솔루션을 변환합니다.
x b i x b i -- * , i r, (2.7)
그리고 2단계로 넘어갑니다.
이 옵션은 각 단계에서 계산량이 줄어들기 때문에 수정된 심플렉스 방법이라고도 합니다. 아이디어는 각 단계에서 현재 기준에 대한 문제의 표준 형식을 표준 LP 문제의 원본 기록에서 직접 다른 형식과 독립적으로 얻을 수 있다는 것입니다.
이렇게 하려면 다음이 필요합니다.
- 1. 방법의 전체 작업 전반에 걸쳐 작업의 원본 기록을 유지합니다. 이는 더 나은 성능을 위해 지불해야 하는 대가입니다.
- 2. 문제의 원래 기록에서 현재 표준 기반 형식으로 직접 전환하기 위해 소위 단순 - 승수 p - 계수를 사용합니다.
- 3. 각 단계에서 선행 열 aґs를 계산하고 단순 요소 p를 업데이트할 수 있는 m x m 크기의 행렬인 역기저 BODF를 사용합니다.
향상된 심플렉스 방법은 표준 형식에 비해 상당한 이점을 가지고 있습니다. 이는 정확성, 속도 및 메모리 요구 사항에 적용됩니다. 이러한 장점의 대부분은 일반적으로 큰 선형 문제(즉, n>m>100)의 행렬이 약하게 채워지고 0이 아닌 요소의 작은 비율을 포함한다는 사실에 의해 결정됩니다.
5% 이하의 밀도가 일반적입니다. 개선된 형태의 단순 방법은 이러한 사실에서 발생하는 이점을 더 잘 활용할 수 있습니다. 이 형식에서는 특성 차이와 선행 벡터가 원본 데이터에서 직접 계산됩니다. 원래 행렬이 제대로 채워지지 않아 두 요소가 모두 0이 아닌 경우에만 곱셈을 수행해야 하므로 계산 시간이 크게 줄어듭니다.
또한, 원본 데이터만을 사용한다는 것은 반올림 오류가 누적될 가능성이 줄어든다는 것을 의미합니다. 대조적으로, 표준 단순 테이블은 초기에 드물게 채워지더라도 반복 프로세스를 통해 0이 아닌 요소로 빠르게 채워집니다. 따라서 계산 시간이 늘어나고, 각 테이블이 이전 테이블로부터 계산되기 때문에 오류의 누적이 더욱 심각한 역할을 하기 시작할 수 있습니다.
심플렉스 방법의 아이디어를 이용하여 CPU 문제를 해결하는 방법을 생각해 봅시다. CPU 작업의 주요 특징은 목표 함수의 설계와 원하는 목표 달성 수준의 편차를 나타내는 변수입니다. 이러한 기능을 고려하면 일반적인 단순 방법을 사용하여 이러한 문제를 해결할 수 있습니다. 앞에서 설명한 예를 사용하여 이를 설명하겠습니다. 초기 기본 해법이 명백하기 때문에 알고리즘은 어느 정도 단순화되었습니다. 여기서 초기 계획에 대한 기본 변수의 역할은 계수 +1을 사용하여 모델에 포함된 음수 편차 "d"에 의해 수행됩니다. 목적 함수의 계수에 대한 선을 사용하면 더 어렵습니다. 즉, 평가선으로. 우리가 알고 있듯이 CPU 작업의 목적 함수 편차에 대한 계수는 우선순위에 따라 목표의 순위를 매기는 가중치입니다. 일반적으로 수치는 결정되지 않습니다. 우선순위가 더 높은 목표 제약조건에 대한 편차 계수가 우선순위가 낮은 목표로부터의 편차에 대한 계수보다 훨씬 더 큰 것이 중요합니다. 따라서 계산의 편의를 위해 평가라인을 여러 라인으로 나누어(우선순위 수에 따라) 각 라인별로 개별적으로 계산을 수행합니다.
따라서 문제를 해결하려면 min Z = P 1 d 1 - + P 2 d 2 - + P 3 d 3 + + P 4 d 4 - ,
제공
7x 1 + 6x 2 + d 1 - – d 1 + = 30;
2x 1 + 3x 2 + d 2 - – d 2 + = 12;
6x 1 + 5x 2 + d 3 - – d 3 + = 30;
x 2 + d 4 - – d 4 + = 7;
x 1 , x 2 , d i - , d i + ³ 0 (i = ).
초기 심플렉스 테이블(표 5.1)을 생성해 보겠습니다.
표 5.1 - 원래 단순 표
| CJCB | 기초 | 해결책 | 0x1 | 0x2 | 피 1d 1 - | 피 2d 2 - | d 3 - | 피 4d 4 - | 디 1 + | 일 2 + | 피 3d 3 + | 디 4 + | 큐 |
| 피 1 피 2 피 4 | d 1 - d 2 - d 3 - d 4 - | 7 | -1 | -1 | -1 | -1 | 30/7 30/6 - | ||||||
| Zj – Сj | 피4피3피2피1 | -1 | -1 | -1 | -1 |
알려진 바와 같이, 평가 라인(Z j – C j)의 요소는 다음 규칙에 따라 계산됩니다. "맨 위 행의 요소는 "C in" 열 요소의 곱의 합에서 다음과 같이 뺍니다. 해당 열의 요소.” 예를 들어 "해결책" 열의 경우 "Z j – C j" 요소는 다음과 같습니다. Р 1 *30 + Р 2 *12 + 0* 30 + р 4 *7 – 0 = 30Р 1 + 12Р 2 + 7Р 4 및 해당 Pi에 대한 계수 (i = )는 "Z j – C j"블록의 이 열에 기록됩니다(아래에서 위로 읽음). "x 1" 열의 경우: P 1 *7 + P 2 *2 + 0 * 6 + P 4 *0 – 0 = 7P 1 + 2P 2, 이는 블록 "의 P 1 및 P 2에 대한 계수입니다. Z j – C j " 등
CPU 문제는 항상 최소로 해결되므로 평가선의 모든 요소가 긍정적이지 않으면 솔루션이 최적이 됩니다. 우리의 경우 두 개의 추정치(“x 1” 및 “x 2” 열)가 양수이므로 계획이 최적이 아닙니다. 기본에 포함된 변수를 결정하기 위해 첫 번째 반복에서 가장 큰 양수 추정치를 결정합니다. P 1에서 계수의 부호에 의해 결정됩니다. 왜냐하면 P1 >> P2 >> P3 >> P4 . P 1의 계수가 동일하면 위의 선으로 "위로 이동"하여 거기에서 가장 큰 계수를 선택합니다. 모든 행이 완전히 동일한 경우에는 그 중 하나가 선택됩니다. 우리의 경우 해결 열은 "x 1" 열이 됩니다(7 > 6이므로). 해결 행은 가장 작은 단순 비율 q에 따라 단순 방법과 동일한 방식으로 선택됩니다(“솔루션” 열의 요소를 해결 열의 양수 요소로 나눕니다). 표 5.1에서 가장 작은 비율 q는 첫 번째 행에 있습니다. 따라서 다음 반복에서는 변수 “x 1”이 베이시스에 입력되고 “d 1 -”이 출력됩니다. 일반적인 단순 방법(표 5.2)과 같이 테이블을 다시 계산합니다.
표 5.2 – 두 번째 심플렉스 테이블
| CJCB | 기초 | 해결책 | x 1 | x 2 | 피 1d 1 - | 피 2d 2 - | d 3 - | 피 4d 4 - | 디 1 + | 일 2 + | 피 3d 3 + | 디 4 + | 큐 |
| 피 2 피 4 | x 1 d 2 - d 3 - d 4 - | 30/7 24/7 30/7 | 6/7 9/7 1/7 | 1/7 2/7 6/7 | 1/7 2/7 6/7 | -1 | -1 | -1 | 30/6 24/9 - | ||||
| Zj – Cj | 피4피3피2피1 | 24/7 | 9/7 | 2/7 -1 | 2/7 | -1 | -1 | -1 |
보시다시피 두 번째 반복에서는 d 2 -가 기본에서 제거되고 x 2가 기본에 도입됩니다. 최적의 솔루션을 얻을 때까지 계속됩니다. 4번째 반복 후에 우리는 표 5.3을 얻습니다.
표 5.3 - 최종 단순표
| CJCB | 기초 | 해결책 | x 1 | x 2 | 피 1d 1 - | 피 2d 2 - | d 3 - | 피 4d 4 - | 디 1 + | 일 2 + | 피 3d 3 + | 디 4 + |
| 피 4 | d 2 + x 2 d 1 + d 4 - | 1,6 1,2 0,2 -1,2 | -1 | -1 | 0,6 0,2 1,2 -0,2 | -0,6 -0,2 -1,2 0,2 | -1 | |||||
| Zj – Cj | 피4피3피2피1 | -1,2 | -1 | -1 | -0,2 | 0,2 -1 | -1 |
P 4 행(d 3 + 열)에 긍정적인 요소가 있다는 사실은 네 번째 목표가 완전히 달성되지 않았음을 의미합니다. 이 경우 목표 함수는 P 4와 같으며 이것이 가능한 최소값입니다. 일반적으로 변수 d 3 + 의 추정치는 (0.2 P 4 - P 3)과 같으며, P 3 >> P 4이므로 최종적으로 음수가 됩니다. 다른 모든 추정치는 양수가 아니므로 단순 방법의 관점에서 계획이 최적입니다.
이 문제에 대한 해결책은 다음과 같이 논평될 수 있다. 작업을 완료하려면 두 번째 제품을 6개 단위로 생산해야 합니다. (x 2 = 6). 첫 번째 제품을 출시하지 마십시오. 동시에 1차, 2차 목표도 6개 이상 초과했다. (d 1 + = d 2 + = 6), 네 번째는 1단위만큼 부족하게 채워집니다. (d 4 - =1). 따라서 얻은 이익은 6 단위였습니다. 원하는 수준 이상으로 첫 번째 자원이 정상 한도를 6단위 초과하여 사용되었으며, 두 번째 유형의 제품은 7단위 대신 원하는 양으로 생산할 수 없었습니다. 릴리스 6(두 번째 리소스가 누락되었습니다. "저장"이 더 높은 우선순위 목표입니다.)
결론적으로 CPU 작업에 대한 모델 생성의 예로 다른 작업에 대한 모델을 생성해 보겠습니다.
예제 5.2. 시정부는 체육시설을 확충할 계획이다. 이러한 목적으로 시 예산은 540만 루블을 할당했습니다. 테니스장, 수영장, 마이크로스타디움(운동장), 체육관 등 4개 유형의 체육시설을 추가로 건설할 계획이었다. 이들 프로젝트에 관한 데이터는 다음과 같다(표 5.4).
표 5.4 - 건설 중인 객체에 대한 정보
해결책.시는 이러한 목적을 위해 20헥타르의 여유 공간을 할당했지만 필요한 경우 이 면적을 늘릴 수 있습니다. 이 프로젝트를 시행하면서 행정부는 중요도에 따라 다음과 같은 목표를 설정합니다.
1) 예산 금액을 충족합니다.
2) 건설된 스포츠 시설은 주당 최소 14,000회 방문을 제공해야 합니다.
3) 가능한 한 스포츠 시설에 대한 예상 수요를 충족시킵니다. 이러한 목적 제약 조건에 대한 목적 함수를 생성할 때 예상 사용량에 비례하는 가중치를 사용하세요.
4) 프로젝트 시행 시, 가능하다면 할당된 여유 공간인 20헥타르 이상을 차지하지 마십시오.
이 작업에 대한 모델을 작성할 때 목표를 공식화할 때의 제한 사항은 범주형이 아니며 과도하게 또는 부족하게 달성될 수 있다는 점을 명심할 것입니다.
가변 작업: x 1, x 2, x 3, x 4 - 각각 건설된 구조물 수: 테니스 코트, 수영장, 운동장 및 체육관.
모든 제한 사항이 대상으로 지정되며 시스템 제한 사항은 없습니다.
첫 번째 목표는 할당된 금액을 충족하는 것입니다.
120x1 + 600x2 + 480x3 + 1,200x4 + d1 - – d1 + = 5,400.
"과잉 지출"을 최소화합니다: min Z = P 1 d 1 + .
두 번째 목표는 주당 최소 14,000회 방문입니다.
500 x 1 + 1,000 x 2 + 2,000 x 3 + 1,500 x 4 + d 2 - – d 2 + = 14,000
'미달 방문'을 최소화합니다. 우리가 가진 첫 번째 목표를 고려하면 다음과 같습니다.
최소 Z = P 1 d 1 + + P 2 d 2 - .
세 번째 목표를 구현하려면 각 구조 유형에 대해 4가지 제한 사항을 구현해야 합니다.
x 1 + d 3 - – d 3 + = 8;
x 2 + d 4 - – d 4 + = 3;
x 3 + d 5 - – d 5 + = 3;
x 4 + d 6 - – d 6 + = 2.
우리는 "이행 부족"을 최소화합니다. 이는 세 번째로 중요한 목표이므로 목적 함수에서 4개 항 모두 계수 P 3을 가지지만 가중치는 다릅니다.
최소 Z = P 1d 1 + + P 2d 2 - + 0.5P 3d 3 - + P 3d 4 - + 2P 3d 5 - + 1.5P 3d 6 - .
네 번째 목표: 0.8x 1 + 5x 2 + 3.2x 3 + 1.6x 4 + d 7 - – d 7 + = 20.
모든 목표를 고려한 목적 함수:
최소 Z = P 1d 1 + + P 2d 2 - + 0.5P 3d 3 - + P 3d 4 - + 2P 3d 5 - + 1.5P 3d 6 - + P 4d 7 + .
따라서 문제 모델은 다음과 같은 형식을 취합니다.
최소 Z = P 1 d 1 + + P 2 d 2 - + 0.5P 3 d 3 - + P 3 d 4 - + 2P 3 d 5 - + 1.5P 3 d 6 - + P 4 d 7 +
제공
120x1 + 600x2 + 480x3 + 1200x4 + d1 - – d1 + = 5400,
500x1 + 1,000x2 + 2,000x3 + 1,500x4 + d2 - – d2 + = 14,000,
x 1 + d 3 - – d 3 + = 8,
x 2 + d 4 - – d 4 + = 3,
x 3 + d 5 - - d 5 + = 3,
x 4 + d 6 - – d 6 + = 2,
0.8x 1 + 2x 2 + 3.2x 3 + 1.6x 4 + d 7 - – d 7 + = 20.
x j ³ 0 (j = ) ; d i - , d i + ³ 0 (i = ).
일반적인 심플렉스 방법을 사용하여 이 문제를 해결하는 경우 가중치 Pi에 특정 값을 지정해야 하지만 P 1 >> P 2 >>...>> P 7 을 고려해야 합니다. 이러한 문제를 해결하기 위해 특별한 프로그램이 개발되었습니다. 그 중 하나(Windows용 QM 프로그램)를 구현하여 다음과 같은 최적의 솔루션을 얻습니다(표 5.5).
표 5.5 – 예제 5.2의 문제에 대한 해결책
(타겟 프로그래밍)
x 1 = 8, x 2 = 3, x 3 = 3, x 4 = 1, d 2 + = 500, d 6 - = 1, d 7 + = 3.6. (d 7 + = –653,994는 인코딩된 숫자 3.6입니다. 이는 우선순위 4 라인에 표시됩니다.) 우선순위 3 행에 표시된 미달성(성취 미달)은 1.5와 동일하며 )의 목적 함수에 있는 가중치 계수를 고려합니다.
따라서 할당된 자금으로 테니스장 8개, 수영장 3개, 미니 경기장 3개, 체육관 1개를 지을 수 있습니다. 보시다시피, 네 번째 목표는 1만큼(d = 1) 충족되지 않습니다. 즉, 계획된 두 개의 체육관 대신 하나의 체육관이 건설됩니다. 두 번째 목표가 초과되었습니다(d 2 + = 500). 즉, 14,000회 방문 대신 14,500회 방문도 가능합니다(d 7 + = 3.6). 이러한 스포츠 시설에 할당된 20헥타르 대신 23.6헥타르가 필요합니다.
6장. 네트워크 계획 및 관리 방법
네트워크 계획 방법을 사용하면 상호 관련된 수많은 작업을 포함하는 일련의 작업을 분석할 수 있습니다. 모든 작업의 예상 기간, 비용, 시간 또는 비용 절감 가능성은 물론 프로젝트 전체를 지연시키지 않고 지연할 수 없는 작업도 결정할 수 있습니다. 자원 확보 문제도 중요하다. 네트워크 분석 방법을 사용하여 기존 리소스 제약을 충족하는 작업 일정을 만들 수 있습니다.
모든 프로젝트의 분석은 세 단계로 수행됩니다.
1. 프로젝트를 여러 개의 개별 작업(또는 작업)으로 나눈 후 논리적 다이어그램을 작성합니다.
2. 각 작업의 기간 추정 프로젝트 일정을 작성하고 프로젝트 전체의 완료를 결정하는 작업을 강조합니다.
3. 각 작업의 자원 요구 사항을 평가합니다. 자원 제공을 고려한 운영 계획 수정 또는
계획을 개선할 자금이나 기타 자원의 재분배.
목록이 컴파일되면 그래프를 사용하여 작업의 논리적 순서를 설명할 수 있습니다. 그래프에는 다양한 종류가 있지만 가장 널리 사용되는 것은 소위 정점 및 화살표 그래프입니다.