数理計画 2001年度 期末試験問題

解答上の注意

問題1

以下の線形計画問題に関して次の問いに答えよ．


線形計画問題(P)：

min. z=  3x1+x2+2x3 　 　
s.t. 　 2x1-x2+2x3 ≧ 12 … 制約式(1)
　 　 2x1+x2-3x3 ≧ 16 …

制約式(2)
　 　 x1, x2, x3 ≧ 0

(1) 上記の線形計画問題（P)の最適解と最適値を求めよ．
(2) 線形計画問題（P)の制約式（1），制約式（2）に関する限界価値を各々求めよ．
(3) 線形計画問題（P)の制約条件式（1）において，条件式の右辺の定数「12」のみが変化する場合を考える．小問（1）で求めた最適解が変化しないのは，右辺の定数「12」がどの範囲内で変化するときか．その範囲を求めよ．
(4) 線形計画問題（P)の目的関数において，変数x2の係数のみが変化する場合を考える．小問（1）で求めた最適解が変化しないのは，目的関数の変数x2の係数がどのように変化するときか，その範囲を求めよ．
(5) 線形計画問題（P)の双対問題（D）を適当な変数を導入して書け．
(6) 双対問題（D）の最適解と最適値を求めよ．

問題2　

湘北地区の6市町村（A〜F）で広域防災協定を結ぶことになった．この協定を結ぶことにより1市町村でひとつの救急センターを設置し運営している現状から，6市町村で必要なだけの救急センターを設置すればよくなり，行政コストの削減につながる．

さて，協定を結ぶ最終段階で具体的にどこの救急センターを残し，どこの救急センターを廃止するかで結論が出ないで困っている．行政コストを削減するという観点から，6市町村の話し合いで

  • 残す救急センターの数はできる限り少なくする
  • 救急センターの新設はしない

という2点は合意している．
一方，法律の規制で，広域防災協定で救急センターを整理統合する場合は，廃止する救急センターの20Km以内の地点には少なくともひとつの稼動する救急センターがなくてはならないと定めてある．

現在の各市町村の救急センター間の距離をまとめたのが以下の表１である．
表1：6市町村(A〜F)の現在の救急センター間の距離（Km)
　 A B C D E F
A 0 18 22 12 21 29
B 18 0 5 18 28 17
C 22 5 0 18 30 19
D 12 18 18 0 24 14
E 17 28 30 24 0 18
F 29 22 19 14 18 0

（Km)

以下の問いに答えよ．

（1）
 上記の問題を数理計画問題として定式化しなさい．
（2）

上記で定式化した数理計画問題の最適解をLINDOを用いて求めたい．どのようなプログラムを書けばよいか記述せよ．

問題3

次の問いに答えなさい．

文教化学では表2の4種類のアルコール溶液（A〜D）から何種類かを購入し，それらを混合することにより，注文に応じて要求された成分を持つアルコール溶液を販売している．

さて，アルコール分の割合が重量の90%以上であるアルコール溶液10000kl（キロリットル）の注文が入った．できるだけコストを安く注文に沿ったアルコール溶液を卸したい．. 

　

表2：各アルコール溶液に関連するデータ

　 溶液A 溶液B 溶液C 溶液D
比重(=重量/体積)(t/kl) 0.85 0.9 0.95 0.92
重量に対するアルコール分の割合(%) 100 95 70 80
使用可能限度量(kl) 5000 7000 15000 6000
購入価格(円/kl) 15000 10000 7000 8000
　

最適な各アルコール溶液の混合計画を提案したいと考え，数理計画問題に定式化し，LINDOを用いて最適解を導出した．その結果は以下のように出力された．ここで，変数a,b,c,dは各アルコール溶液の購入量である．

　
LP OPTIMUM FOUND AT STEP 1

OBJECTIVE FUNCTION VALUE

1) 0.9421469E+08

VARIABLE    VALUE               REDUCED COST
A                553.672302          0.000000
B                6000.000000         0.000000
C                0.000000             214.689270
D                3446.327637         0.000000


ROW   SLACK OR SURPLUS    DUAL PRICES
2)       0.000000                      -22.598869
3)       4446.327637                 0.000000
4)       0.000000                     1096.045166
5)       8000.00000                  0 0.000000
6)       1553.672363                0.000000
7)       0.000000                     -10079.095703

NO. ITERATIONS= 1
(以下略)
　

次の問いに答えよ．
(1) 上記の最適化問題を数理計画問題として定式化せよ．
(2) LINDOの出力を参考に，最適な混合計画を提案せよ．
作成： 根本 俊男(文教大学情報学部経営情報学科)
　 e-mail: nemoto@shonan.bunkyo.ac.jp
実施： 2001年7月6日