線形計画問題の解法

第6回
線形計画法の解法(4)
混合最小値問題
2003.5.1
山梨大学
1
内容と目標
内容:
 1.混合型LP問題の特例―混合最小値問題
 2.Excelを用いて最小値問題が解析する

目標:
 1.混合最小値LP問題を十分に理解する
 2.Excelで混合最小値LP問題を解析する

2003.5.1
山梨大学
2
混合最小値問題

目的関数:
Min. f = x1 + x2 + x3 + x4

(1)
制約条件:
x1 + x2
≦ 50
x3 + x4 ≦ 60
x1
+ x3
x2
≧ 45
(2)
+ x4 ≧ 55
x1 , x2, x3, x4≧0
2003.5.1
山梨大学
3
スラック変数と人為変数の導入
制約条件:
x1 + x2
x1
+λ1
= 50
x3+ x4 +λ2
= 60
+ x3
x2
2003.5.1
-λ3 +μ3
+ x4
(3)
= 45
-λ4 +μ4 = 55
山梨大学
4
目的関数
目的関数は f0 = -fとおき
Max. f0 = - x1 - x2 - x3 - x4
(4)
を最大化する問題に変える。第一段階は
f’ = -μ3 -μ4
(5)
を最大化することである。
2003.5.1
山梨大学
5
シンプレックス表に関する注意
(1) ステップ1のf0行、f’行は以下の式を用いて
作る。ただし、f0 行を作るときはμ3、μ4 に対
するcの値は0と考えて計算し、f’行を作る
ときはx1、x2、x3、x4 に対するcの値は0と
考えて作らねばならない。
c’j = c1 a1 + c2 a2 + c3 a3 - cj
2003.5.1
山梨大学
6
(2)
ステップ5ですべての人為変数が基底から
追い出されたので、f’行は表から除いた。こ
こから第2段階になる。同時に最適条件が満
たされている。したがって、
x1=0, x2=50, x3 =45, x4=5
のとき、f0は最大、すなわちfは最小で
f = ーf0 = 100
である。
2003.5.1
山梨大学
7
例2:混合最小値問題

目的関数
Min. f = 3x1 + 2x2

(6)
制約条件
x1 + x2 ≦ 20
x1 + 2x2 ≧ 11
(7)
2x1 + x2 = 16
x1 , x2 ≧ 0
2003.5.1
山梨大学
8
スラック変数と人為変数の導入

制約条件:
x1 + x2 +λ1
x1 + 2x2
2x1 + x2

= 20
ーλ2 +μ2
= 11
(8)
+μ3 = 16
目的関数:
f0 = ー3x1 ー 2x2
f’ = ーμ2 ーμ3
2003.5.1
山梨大学
(9)
(10)
9
課題
目的関数:
Min. f = 4x1+3x2+2x3+x4
制約条件:
x1+2x2 - 3x3+4x4 ≧12
2x1 - 4x2 - x3 - 2x4 ≦8
3x1- 2x2 + 3x3 + 3x4 ≧36
x1, x2, x3, x4≧0
解答:
2003.5.1
x1=0, x2=0, x3=0, x4=12, f=12
山梨大学
10