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

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

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

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

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

  A1 　 A2 A3 　A4 A5 　A6 制　　限 B1 B2 B3 110 205 160 160 420 260 4 32 13 8 4 14 2 12 54 285 22 80 2000 55 800 価　格　　 30 240 130 90　200 190 2003.5.22 山梨大学

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

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

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

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

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

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

栄養問題の解 　　これによって、最適解は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円である。 2003.5.22 山梨大学

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

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

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

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

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