第九回 問題の定式化練習と 自主研究課題 2003.5.22 山梨大学.

Presentation on theme: "第九回 問題の定式化練習と 自主研究課題 2003.5.22 山梨大学."— Presentation transcript:

1 第九回 問題の定式化練習と 自主研究課題 山梨大学

2 内容と目標 内容： １．線形計画問題の定式化 ２．LP問題の解法の選択と決定 目標： １．実際の線形計画問題を定式化する
山梨大学

3 演習した内容 LP問題の定式化練習 連立１次方程式の掃出し解法 シンプレックス法：標準LP問題 シンプレックス法の２段階法：各種LP問題
双対問題：解法と解釈 LP問題の定式化と解法・解釈 山梨大学

4 LP問題の例 ー栄養問題 　　食堂におけるある6種類の献立食品オートミール(A1), 鶏肉(A2), 卵(A3), 牛乳(A4), チェリーパイ(A5), ポークビーンズ(A6)の各１単位中に含まれる栄養エネルギー(kcal)B1, 蛋白質(g)B2とカルシウム(mg)B3の量は以下の表のとおりである。１日にB1, B2, B3は少なくともそれぞれ2,000kcal, 55g, 800mgはとる必要がある。 山梨大学

5 　　オートミール, 鶏肉, 卵, 牛乳, チェリーパイ, ポークビーンズの各１単位(オートミール-28g, 鶏肉-100g, 卵-2個, 牛乳-237cc, チュリーパイ-170g, ポークビーンズ-260g)の価格はそれぞれ30, 240, 130, 90, 200, 190円で、その食品を一日にとる限量はそれぞれ4, 3, 2, 8, 2, 2単位であるとき、これらの食品からB1, B2, B3の必要量を最も安くとるには、一日に各食品をどれだけ食べればよいか？ 山梨大学

6 A1 　 A2 A3 　A4 A5 　A6 制　　限 B1 B2 B3 2000 55 800 価　格　　 　 山梨大学

7 　　この問題は栄養の問題という名でよく知られている。一日にオートミール, 鶏肉, 卵, 牛乳, チェリーパイ, ポークビーンズをそれぞれx1, x2, x3 , x4 , x5 , x6単位食べるとすると、各栄養が必要量以上（以下）になるためには、 山梨大学

8 また、食品を食べる制限によって、以下の制限条件
110x1+205x2 +160x3+160x4 +420x5+260x6 ≧ 2000 4x x x x x5 + 14x6 ≧ (1) 2x1 + 12x x x4 + 22x5 +80x6 ≧ 800 また、食品を食べる制限によって、以下の制限条件 山梨大学

9 x1 ≦ 4 x2 ≦ 3 x3 ≦ 2 (2) x4 ≦ 8 x5 ≦ 2 x6 ≦ 2 x1, x2, x3, x4, x5, x6≧0
がある。 山梨大学

10 この時の目標 f は以下 f=30x1+240x2+130x3+90x4+200x5+190x6 (3) のとおりである。
山梨大学

11 110x1+205x2 +160x3+160x4+420x3+260x4 -λ μ = 2000 4x1 + 32x x x x x4 -λ μ = 55 2x1+12x x3 +285x4 + 22x5 + 80x λ μ3 = 800 x λ = 4 x λ = (4) x λ = 2 x λ = 8 x λ = 2 x λ9 = 2 x1, x2, x3, x4, x5, x6≧0 になる。目的関数は-f=f0とおき、 山梨大学

12 f0 = -30x1-240x2-130x3-90x4-200x5-190x6 (5) を最大化する問題に変える。第一段階は
を最大化することである。 山梨大学

13 栄養問題の解 　　これによって、最適解はx1=4, x2=0, x3=0, x4=2.23, x5=2, x6 =1.4, f=986.5である。すなわち、一日中に必要な栄養を満たす最も経済的な献立はオートミール4単位(112g), 牛乳2.23単位(529cc), チェリーパイ2単位(340g), ポークビーンズ1.4単位(364g)で、費用は986.5円である。 山梨大学

14 自主研究課題 実際のLP問題をつくれ、そして、 (1) LP問題を定式化せよ (2) LP問題の最適解を求めよ
　(3)    シンプレックス表の経済的解釈をせよ (4)　各制約条件のシャドープライスを求め 　　　て、説明せよ 山梨大学

15 　　問題作成の条件　 (1) 変数は５以上(≧ 5) (2) 制約条件（X ≧0以外)は５以上 (≧ 5) 山梨大学

16 注意事項 レポートには表紙を付け、以下の内容を含むものとする。 シンプレックス表（印刷したもの） 計算ステップの説明
注意事項　 　レポートには表紙を付け、以下の内容を含むものとする。 シンプレックス表（印刷したもの） 計算ステップの説明 計算結果の説明或いは解釈 レポートは発表した内容をそのまま印刷するものではない 山梨大学

17 自主研究課題の要求 来週に準備（5/29） 再来週から発表（6/5, 6/12, 6/19） 発表が全員終了する週にレポートを提出する
発表の評価方法（成績） 教官とTAがそれぞれ評価する １～１０点で点を付ける レポートも１～１０点で評価する 山梨大学

18 自主研究発表評価要点 発表はPower Pointを用いる。評価は担当教官とTA二人がそれぞれ10点、計30点満点で行う。
１. 概念（4点）: 主にLP問題の作成内容、解析結果の妥当性 2. Power Pointの見やすさ（2点）: 工夫して見やすいものを作る 3. 説明方法（2点）: 順序立てて分かりやすく説明する 4. 時間（2点）: 初めから決った順番で一人5分から7分以内で発表する 以上の点に考慮して各自で発表準備を進めること。 山梨大学