Topic.05
선형계획법: 그래프 방법
퀴즈 T05
퀴즈 #13
퀴즈 #14
퀴즈 #15
퀴즈 #16
최소화 문제
최소화 문제: 풍년사료(주)
최소화 문제: 제약조건식의 도해
0
최소화 문제: 제약조건식의 도해
18
0 6
최소화 문제: 제약조건식의 도해
0 12
12
최소화 문제: 제약조건식의 도해
0 5
15
최소화 문제: 가해영역의 결정
0 18
6 12
12 5
15
최소화 문제: 목적함수선
0 18
6 12
12 5
15
* |기울기|:
G
최소화 문제: 목적함수선
연립방정식
G = (3, 9)
생선의 원료량
귀리의 원료량
최소화 문제: 꼭지점 탐색
꼭지점 Z
(0, 0) infeasible
(0, 18) 90
(0, 12) infeasible
(0, 5) infeasible
(3, 9) 63
(39/8, 27/8) infeasible
(10.5, 1.5) 70.5
(15, 0) 90
(12, 0) infeasible
(6, 0) infeasible
* 꼭지점의 수 = = 10
팀 과제: 풍년사료(주)
생선에 비해 1kg 당 영양소가 적은 귀리의 원료량이 너무 많아지면, 고양이의 1회 필요 사료량이 너무 많아져서, 최 소 영양소 섭취에 필요한 사료를 다 먹지 못하게 된다는 현 실을 반영하여 한 백의 무게는 40kg 이내로 하기로 하였다.
이때, 최적해를 구하시오.
팀 과제: 연습문제 3.05
다음과 같은 모델이 주어졌을 때 물음에 답하라
가해영역은 어디인가?
가해영역의 꼭지점의 좌표를 구하라.
최적해를 구하라.
잔여
잔여 (slack, 잉여)
최적생산량을 생산할 때 사용가능한 자원을 모두 사용하지 않고 남게 되는 초과 능력
평화전자(주) 미사용 자원
잔여에 따른 제약조건식의 분류
속박제약조건식
애로공정(부족한 자원)에 대한 제약조건식
최적해점을 통과
비속박제약조건식
자원이 남는 공정(풍부한 자원)에 대한 제약조건식
최적해점을 통과하지 않고 다만 가해영역의 형성에만 영향
제약조건 최적 시 사용값 가능값 미사용 자원
조립 10(4) + 4(9) = 76 80 4
검사 1(4) + 2(9) = 22 22 0
저장공간 3(4) + 3(9) = 39 39 0
최대화 모델: 평화전자(주)
공정
대당 생산시간 및 공간
하루 가능한 시간 모델1 모델2 및 공간
조립(시간/대) 10 4 80
검사(시간/대) 1 2 22
저장공간( /대) 3 3 39
이익(만원/대) 6 7
표준형
잔여변수(slack variable, 잉여변수)의 도입
표준형
모든 제약조건식이 등식
모든 변수가 비음
평화전자(주)
표준형
풍년사료(주)
하브루타 (Quiz #13, 14)
잔여변수를 설명하시오.
팀 과제: 풍년사료(주)
최적해 (3, 9)에서의 slack을 계산하시오.
최소화 모델: 풍년사료(주)
성분
원료 최소 함유량 (단위
/백)
생선(kg) 귀리(kg)
단백질 (단위/kg) 3 1 18
비타민D (단위/kg) 1 1 12
철분 (단위/kg) 2 6 30
비용 (만원/kg) 6 5
특수한 문제
다수최적해 (multiple optimal solution)
둘 이상의 최적해를 갖는 경우
무한해 (unbounded solution)
제약조건을 위반하지 않고 목적함수의 값이 무한히 증가 (최대화) 또는 감소(최소화)할 수 있는 경우
실행불가능해 (infeasible solution)
모든 제약조건식을 동시에 만족시키는 해가 없는 경우
특수한 문제: 다수최적해
0 81 60
162 200 40
-0.3
.
.
-0.3
특수한 문제: 무한해
0 2 3
특수한 문제: 실행불가능해
0 1
1 2
2
하브루타 (Quiz #15, 16)
다수최적해(multiple optimal solution)를 설명하시오.
무한해(unbounded solution)를 설명하시오.
실행불가능해(infeasible solution)를 설명하시오.
팀 과제: 연습문제 3.08
다음 모델은 실행불가능해, 무한해, 다 수최적해 중 어느 것에 해당하는가?
(1) 𝑚𝑎𝑥 𝑍 = 3𝑥 + 2𝑥 𝑠. 𝑡.
2𝑥 + 3𝑥 ≥ 18 𝑥 + 𝑥 ≤ 5 𝑥 , 𝑥 ≥ 0
(2) 𝑚𝑎𝑥 𝑍 = 2𝑥 + 1𝑥 𝑠. 𝑡.
1𝑥 ≥ 7 1𝑥 ≤ 7 𝑥 , 𝑥 ≥ 0
(3) 𝑚𝑎𝑥 𝑍 = 5𝑥 + 5𝑥 𝑠. 𝑡.
𝑥 + 𝑥 ≤ 600 𝑥 + 𝑥 ≤ 500 𝑥 + 2𝑥 ≤ 800 𝑥 , 𝑥 ≥ 0
(4) 𝑚𝑎𝑥 𝑍 = 2𝑥 + 1𝑥 𝑠. 𝑡.
𝑥 + 𝑥 ≤ 6
−1𝑥 + 1𝑥 ≥ 7 𝑥 , 𝑥 ≥ 0
(5) 𝑚𝑎𝑥 𝑍 = 3𝑥 + 3𝑥 𝑠. 𝑡.
4𝑥 − 𝑥 ≥ 8 4𝑥 − 2𝑥 ≤ 12 𝑥 , 𝑥 ≥ 0
쪽지 질문
End
최소화 문제
