第６回 線形計画法の解法（４） 混合最小値問題 2003.5.1 山梨大学.

Presentation on theme: "第６回 線形計画法の解法（４） 混合最小値問題 2003.5.1 山梨大学."— Presentation transcript:

1 第６回 線形計画法の解法（４） 混合最小値問題 山梨大学

2 内容と目標 内容： １．混合型LP問題の特例―混合最小値問題 ２．Excelを用いて最小値問題が解析する 目標：
目標： １．混合最小値LP問題を十分に理解する ２．Excelで混合最小値ＬＰ問題を解析する 山梨大学

3 混合最小値問題 目的関数： Min. f = x1 + x2 + x3 + x4 (1) 制約条件： x1 + x2 ≦ 50
山梨大学

4 スラック変数と人為変数の導入 制約条件： x1+ x2 +λ1 ＝ 50 x3+ x4 +λ2 ＝ 60 (3)
山梨大学

5 目的関数 目的関数は f0 = -fとおき Max. f0 = - x1 - x2 - x3 - x4 (4)
を最大化する問題に変える。第一段階は 　　　　　　f’ = -μ3 -μ4　　 　 　　(5) を最大化することである。 山梨大学

6 シンプレックス表に関する注意 (1) ステップ１のf0行、f’行は以下の式を用いて作る。ただし、f0行を作るときはμ3、μ4に対するｃの値は０と考えて計算し、f’行を作るときはx1、x2、x3、x4に対するｃの値は０と考えて作らねばならない。 c’j = c1 a1 + c2 a2 + c3 a3 - cj 山梨大学

7 (2)　ステップ5ですべての人為変数が基底から追い出されたので、f’行は表から除いた。ここから第２段階になる。同時に最適条件が満たされている。したがって、
　　　　　x1=0, x2=50, x3 =45, x4=5 　のとき、f0は最大、すなわちfは最小で 　　　　　　　f = ーf0 = 100 　である。 山梨大学

8 例２：混合最小値問題 目的関数 Min. f = 3x1 + 2x2 (6) 制約条件 x1 + x2 ≦ 20
山梨大学

9 スラック変数と人為変数の導入 制約条件： x1 + x2 +λ1 ＝ 20 x1 + 2x2 ーλ2 +μ2 ＝ 11 (8)
目的関数： 　　 　 f0 = ー3x1 ー 2x2　 　　　 　 (9) 　 　 f’ = ーμ2 ーμ3　　　 　　 　(10) 山梨大学

10 課 題 目的関数: Min. f = 4x1+3x2+2x3+x4 制約条件: x1＋2x2 - 3x3＋4x4 ≧12
解答：　x1=0, x2=0, x3=0, x4=12, f=12 山梨大学