線形計画法入門（文科系の）

門前パソコン学習所

令和２年如月
更新 2020-05-06,2023-09-16
2024-03-01

書籍	番号	最適化問題	備考
1	4.1	石炭・電力・労力を用いた生産計画
1	4.2	バター製造計画
1	4.3	残業による生産計画
1	5.1	食パンと牛乳だけの食事
1	5.2	合金の製造
1	6.1	リンゴの輸送	2-D2
1	6.2	人員の配置
1	6.3	切符の割当て
1	7.1	海水浴とレストランでの食事
1	7.2	四半期単位の年間生産販売計画	2-E1
1	7.3	最短路問題

(4.1) 石炭・電力・労力を用いた生産計画

これは、森口繁一著「線計画法入門」にある（巻頭の）例題である。

問題

ある会社で製品 A と製品 B の２種類の製品を作ろうとしている。

製品 A を 1 kg 作るには石炭が 9 トン、電力が 4 kWh、労力が 3 人日（1 日当たり 3 人）だけ必要である。

製品 B を 1 kg 作るには石炭が 4 トン、電力が 5 kWh、労力が 10 人日だけ必要である。

ところがその会社でいまのところ利用できるのは、石炭が 360 トン、電力 200 kWhが、労力が 300 人日までで、それ以上は使えない。

製品 A は 1 kg について 7 万円の利益を生じ、製品 B は 1 kg について 12 万円の利益を生む。

石炭、電力、労力について上記の制約の下で、利益が最大になるように製品 A および B の生産高を決めたい。

	製品 A	製品 B	使用可能量
	X1	X2
石炭使用量（トン/kg）	9	4	360（トン）
電力使用量（kWh/kg）	4	5	200（kWh）
労力使用量（人日/kg）	3	10	300（人日）
利益（万円/kg）	7	12	（最大化問題）

制約条件式

9X1+4X2≦360

4X1+5X2≦200

3X1+10X2≦300

X1,X2≧0

目的関数

7X1+12X2=z

これを最大化する。

最適解

X1=20, X2=24, z=428

Python による結果

最適値= 428.0

主要変数=

X1 20.0

X2 24.0

# 1-41石炭・電力・労力を用いた生産計画
from mypulp import *
master = Model("model141")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
master.update()
#
master.addConstr(9*X1+4*X2 <= 360)
master.addConstr(4*X1+5*X2 <= 200)
master.addConstr(3*X1+10*X2 <= 300)
#
master.setObjective(7*X1+12*X2,GRB.MAXIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #

(4.2) バター製造計画

問題

日吉乳業では、これまで「ピーナッツ入り」と「チョコレート入り」の２種類の「変わりバター」の製造を行ってきたが、今度新しく「果実入りバター」を製造することになった。

そこで、これらの製品をどのくらいずつ製造したら利益が最大になるか見当をつけたいと思う。

調査の結果、製品 1 ケース当たりの利益は、ピーナッツ入りが 1.6 千円、チョコレート入りが 1.5 千円、果実入りが 1.7 千円で、また製造にあたっては、次のような制約が加わることが分かった。

[1] 製品 1 ケース当たりの原料使用量は、ピーナッツ入りが 3 kg、チョコレート入りが 3 kg、果実入りが 2 kg である。資金不足なので、ここ当分は原料総量を 1 日あたり 900 kg におさえることにする。
[2] これらの製品はどれも工程Ⅰと工程Ⅱを通る。各製品の工程Ⅰにおける 1 ケース当たりの所要時間は、ピーナッツ入りが 2 分、チョコレート入りが 1 分、果実入りが 2 分で、工程Ⅱでは、ピーナッツ入りが 1 分、チョコレート入りが 2 分、果実入りが 1 分である。また、工程Ⅰにおける 1 日の総作業時間は最大 580 分、工程Ⅱでは最大 480 分である。
[3] 製造されたこれらの製品は、できあがると手持ち在庫として冷蔵庫に保管され次の日に出荷していく。1 ケースの大きさは、ピーナッツ入りとチョコレート入りは同じであるが、果実入りはピーナッツ入りの 2 倍である。冷蔵庫内での保管場所の大きさはピーナッツ入りに換算して 500 ケース分が限度である。

	ピーナッツ入り	チョコレート入り	果実入り	使用可能量
	X1	X2	X3
原料（kg/ケース）	3	3	2	900（kg）
工程Ⅰ（分/ケース）	2	1	2	580（分）
工程Ⅱ（分/ケース）	1	2	1	480（分）
冷蔵庫（P ケース/ケース）	1	1	2	500（P ケース）
利益（千円/ケース）	1.6	1.5	1.7	（最大化問題）

制約条件式

3X1+3X2+2X3≦900

2X1+1X2+2X3≦580

1X1+2X2+1X3≦480

1X1+1X2+2X3≦500

X1,X2,X3≧0

目的関数

z=1.6X1+1.5X2+1.7X3

最適解

X1 = 80.0, X2 = 120.0, X3 = 150.0, Z = 563.0

Python による結果

最適値= 563.0

主要変数=

X1 80.0

X2 120.0

X3 150.0

# 1-42バター製造計画
from mypulp import *
master = Model("model142")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
X3 = master.addVar(vtype="C",name="X3")
master.update()
#
master.addConstr(3*X1+3*X2+2*X3 <= 900)
master.addConstr(2*X1+1*X2+2*X3 <= 580)
master.addConstr(1*X1+2*X2+1*X3 <= 480)
master.addConstr(1*X1+1*X2+2*X3 <= 500)
#
master.setObjective(1.6*X1+1.5*X2+1.7*X3,GRB.MAXIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #

(4.3) 残業による生産計画

問題

住吉工業では、労働力と 2 種類の原料を用いて 3 種類の製品を生産することができる。

各製品 1 単位を生産するのに必要な労働力と各原料の量、およびそれから得られる利益（万円）を表にまとめると、次のようになる。

	製品
	A	B	C	最大値
	X1	X2	X3
労働力	1	1	1	20
原料 1	3	4	6	100
原料 2	3	5	3	100
利益	6	8	10	（最大化問題）

さて、来期の見通しによれば、労働力は 20 単位、2 種類の原料はともに 100 単位までなら確保できる。

この見通しにもとづいて、来期の利益を最大にするための生産計画、すなわち、どの製品をどれだけ生産するかを決めたい。

制約条件式

1X1+1X2+1X3≦20

3X1+4X2+6X3≦100

3X1+5X2+3X3≦100

X1,X2,X3≧0

目的関数

z=6X1+8X2+10X3

最適解

X1 = 0.0, X2 = 10.0, X3 = 10.0, Z = 180.0

Python による結果

最適値= 180.0

主要変数=

X2 10.0

X3 10.0

# 1-43残業による生産計画
from mypulp import *
master = Model("model143")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
X3 = master.addVar(vtype="C",name="X3")
master.update()
#
master.addConstr(1*X1+1*X2+1*X3 <= 20)
master.addConstr(3*X1+4*X2+6*X3 <= 100)
master.addConstr(3*X1+5*X2+3*X3 <= 100)
#
master.setObjective(6*X1+8*X2+10*X3,GRB.MAXIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #

(5.1) 食パンと牛乳だけの食事

問題

食パンと牛乳だけで、熱量、蛋白質、カルシウムという３つの栄養素を１日に必要なだけ摂取しようとしたら、食パンを何グラム食べて、牛乳を何グラム飲めばよいか。

	食パン(100g)	牛乳(100g)	最低必要量
	X1	X2
熱量(kcal)	270	60	2500
蛋白質(g)	8	3	70
カルシウム(mg)	11	100	600
値段（円）	40	25

制約条件式

270X1+60X2≧2500

8X1+3X2≧70

11X1+100X2≧600

X1, X2≧0

目的関数

Z=40X1+25X2

最適解

X1 = 8.1245, X2 = 5.1063, Z = 452.6386

Python による結果

最適値= 452.63857099999996

主要変数=

X1 8.1245254

X2 5.1063022

# 1-51食パンと牛乳だけの食事
from mypulp import *
master = Model("model151")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
master.update()
#
master.addConstr(270*X1+60*X2 >= 2500)
master.addConstr(8*X1+3*X2 >= 70)
master.addConstr(11*X1+100*X2 >= 600)
#
master.setObjective(40*X1+25*X2,GRB.MINIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #
最適値= 452.63857099999996
主要変数=
X1 8.1245254
X2 5.1063022

(5.2) 合金の製造

問題

３つの金属を表のような比率で混合して合金を作るとする。

金属	混合比率（重量）
L	60 %
M	20 % 以下
N	20 % 以上

金属 L,M,N を作るには 5 種類の原料 A,B,C,D,E を用いることができるが、これらの原料には L,M,N 以外の不純物も混ざっている。

その成分比率は次のようである。また、各原料の費用として、不純物を除去するための費用も含めた値を最後の行に示しておく。

	原料
	A	B	C	D	E
金属	X1	X2	X3	X4	X5
L (%)	40	10	20	0	50
M (%)	10	30	10	20	20
N (%)	20	10	20	10	10
不純物 (%)	30	50	50	70	20
費用 (千円/kg)	9	7	5	6	10

さて、100 kg の合金を最小費用で作るためには、原料をどのように使えばよいか。

原料 A,B,C,D,E の使用量をそれぞれ変数 X1,X2,X3,X4,X5 （単位 kg）とする。

(1) 100 kg の合金を作る：: まず、５つの原料 A,B,C,D,E から不純物を除去すると、各原料がどれだけ残るか。; 原料 A を X1 kg 使用するとすれば、それは不純物を 30 % 含んでいるから、; 不純物を除去すると、実際に使用できる量は X1 kg の 70 %、すなわち 0.7X1 kg となる。; 原料に B,C,D,E ついても実際に使用できる量は、同様な考え方で; それぞれ 0.5X2,0.5X3,0.3X4,0.8X5 となる。これらを混合して 100 kg 合金を作る。
(2) 金属 L は 60 % 含まれる：: 原料 A,B,C,D,E はそれぞれ金属 L を 40 %,10 %,20 %,0 %, 50 % 含んでいる。; それらを混合した時の金属 L の含有量をちょうど 60 % にしなければならないから、; 100 kg の合金のうちちょうど 60 kg が金属 L でなければならない。
(3) 金属 M は 20 % 以下とする：: 原料 A,B,C,D,E はそれぞれ金属 M を 10 %,30 %,10 %,20 %, 20 % 含んでいる。; それらを混合した時の金属 M の含有量を 20 % 以下にしなければならないから、; 100 kg の合金のうち金属 M は 20 kg 以下でなければならない。
(4) 金属 N は 20 % 以上とする：: 原料 A,B,C,D,E はそれぞれ金属 N を 20 %,10 %,20 %,10 %,10 % 含んでいる。; それらを混合した時の金属 N の含有量を 20 % 以上にしなければならないから、; 100 kg の合金のうち金属 N は 20 kg 以上でなければならない。

制約条件式

0.7X1+0.5X2+0.5X3+0.3X4+0.8X5=100

0.4X1+0.1X2+0.2X3+0.0X4+0.5X5=60

0.1X1+0.3X2+0.1X3+0.2X4+0.2X5≦20

0.2X1+0.1X2+0.2X3+0.1X4+0.1X5≧20

X1, X2, X3, X4, X5≧0

目的関数

Z=9X1+7X2+5X3+6X4+10X5

最適解

X1 = 66.6667, X2 = 0.0000, X3 = 0.0000, X4 = 0.0000, X5 = 66.6667

Z = 1266.6667

Python による結果

# 1-52合金の製造
from mypulp import *
master = Model("model152")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
X3 = master.addVar(vtype="C",name="X3")
X4 = master.addVar(vtype="C",name="X4")
X5 = master.addVar(vtype="C",name="X5")
master.update()
#
master.addConstr(0.7*X1+0.5*X2+0.5*X3+0.3*X4+0.8*X5 == 100)
master.addConstr(0.4*X1+0.1*X2+0.2*X3+0.0*X4+0.5*X5 == 60)
master.addConstr(0.1*X1+0.3*X2+0.1*X3+0.2*X4+0.2*X5 <= 20)
master.addConstr(0.2*X1+0.1*X2+0.2*X3+0.1*X4+0.1*X5 >= 20)
#
master.setObjective(9*X1+7*X2+5*X3+6*X4+10*X5,GRB.MINIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X,v.RC)
    else:
        print(v.VarName,v.X,v.RC)
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #
最適値= 1266.6666730000002
主要変数=
X1 66.666667
X5 66.666667

(6.1) リンゴの輸送

これは、森口繁一著「線計画法入門」にある演習問題 D 2 である。

問題

Ⅰ,Ⅱ,Ⅲの３個所で果樹園を経営している人が、三つの消費地 A, B, C にリンゴを輸送して販売しようとしている。

消費地 A, B および C での売価はそれぞれ１箱当たり 680 円, 655 円および 715 円である。

そして消費地 A の販売業者は最低 800 箱送ってほしいと要求しており、B および C からはそれぞれ最低 1200 箱および 1500 箱を要求してきている。

果樹園Ⅰ,ⅡおよびⅢの出荷能力はそれぞれ 1150 箱、 1900 箱および 1500 箱である。

製造原価は各地均一で、１箱 500円である。

利潤を最大にするためにはどのように出荷したらよいか、

ただし輸送費は生産者もちであって、１箱当たりの輸送費は次のようである。

		消費地
出荷能力	果樹園	A	B	C
1150箱	Ⅰ	X₁	X₂	X₃
		37	20	39
1900箱	Ⅱ	X₄	X₅	X₆
		14	28	24
1500箱	Ⅲ	X₇	X₈	X₉
		24	34	32

	要求量	800	1200	1500
	売価	680	655	715

X1+X2+X3≦1150, X4+X5+X6≦1900, X7+X8+X9≦1500

X1+X4+X7≧800, X2+X5+X8≧1200, X3+X6+X9≧1500

利潤＝売価-(製造原価+輸送費)

Z	=	(680-(500+37))X1+(655-(500+20))X2+(715-(500+39))X3+
		(680-(500+14))X4+(655-(500+28))X5+(715-(500+24))X6+
		(680-(500+24))X7+(655-(500+34))X8+(715-(500+32))X9

最良輸送計画

	消費地
出荷地	A	B	C
Ⅰ	0	1150	0
Ⅱ	800	0	1100
Ⅲ	0	50	1450

別解

	消費地
出荷地	A	B	C
Ⅰ	0	1150	0
Ⅱ	0	0	1900
Ⅲ	800	50	650

Z=769550

制約条件式

X1+X2+X3≦1150, X4+X5+X6≦1900, X7+X8+X9≦1500

X1+X4+X7≧800, X2+X5+X8≧1200, X3+X6+X9≧1500

目的関数

Z=(680-(500+37))X1+(655-(500+20))X2+(715-(500+39))X3+

　(680-(500+14))X4+(655-(500+28))X5+(715-(500+24))X6+

　(680-(500+24))X7+(655-(500+34))X8+(715-(500+32))X9

最適解

X1 = 0.0000, X2 = 1150.0000, X3 = 0.0000,

X4 = 800.0000, X5 = 0.0000, X6 = 1100.0000,

X7 = 0.0000, X8 = 50.0000, X9 = 1450.0000

Z = 769550.0000

Python による結果

# 1-61リンゴの輸送
from mypulp import *
master = Model("model161")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
X3 = master.addVar(vtype="C",name="X3")
X4 = master.addVar(vtype="C",name="X4")
X5 = master.addVar(vtype="C",name="X5")
X6 = master.addVar(vtype="C",name="X6")
X7 = master.addVar(vtype="C",name="X7")
X8 = master.addVar(vtype="C",name="X8")
X9 = master.addVar(vtype="C",name="X9")
master.update()
#
master.addConstr(X1+X2+X3 <= 1150)
master.addConstr(X4+X5+X6 <= 1900)
master.addConstr(X7+X8+X9 <= 1500)
master.addConstr(X1+X4+X7 >= 800)
master.addConstr(X2+X5+X8 >= 1200)
master.addConstr(X3+X6+X9 >= 1500)
#
master.setObjective((680-(500+37))*X1+(655-(500+20))*X2+(715-(500+39))*X3+
                    (680-(500+14))*X4+(655-(500+28))*X5+(715-(500+24))*X6+
                    (680-(500+24))*X7+(655-(500+34))*X8+(715-(500+32))*X9,GRB.MAXIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #
最適値= 769550.0
主要変数=
X2 1150.0
X4 800.0
X6 1100.0
X8 50.0
X9 1450.0

(6.2) 人員の配置

問題

アーベル、ベーカ、チャーリという３人の候補者を、無線士、プログラマ、事務職員という

３つの職種の養成所に配置する問題を考える。

彼らは、３つの職種に対する適性検査を受けたが、その成績は表のとおりである。

３つの職種に対する適性検査成績表

候補者/職種	無線士	プログラマ	事務職員
アーベル	5	4	7
ベーカ	6	7	3
チャーリ	8	11	2

点数が高ければ高いほど、対応する職種に対する適性が高いものとする。

アーベルは、プログラマには向かないが、事務職員か無線士ならまあまあである。

ベーカは、事務が苦手でプログラマか無線士のほうが向いている。

チャーリは、プログラマとしては抜群で、無線士としても適性があるが、事務は全く駄目である。

このような３人のうち１人を無線士養成所に、１人をプログラマ養成所に、１人を事務職員養成所に配置しなければならない。

もしアーベルを無線士に、ベーカをプログラマに、チャーリを事務職員に配置したとすれば、

適性検査の点数の合計、すなわち、総点数は

5+7+2=14

である。各人を各職種に配置した場合の点数の合計が大きいほど良い配置であるとする。

候補者が職種の養成所に配置されるかされないかを変数 X_k で表すことにする。

例えば、変数 X1 は、アーベルが無線士に配置されるかされないかを表し、配置される場合は 1、配置されない場合は 0 となる。

このようにすると候補者が３人で、職種が３つだから、変数は全部で X1,X2,X3,X4,X5,X6,X7,X8,X9 の９個となる。

９個の変数の番号 k が、どの候補者とどの職種に対応した配置であるかは下の表のとおりである。

決定変数

候補者/職種	無線士	プログラマ	事務職員
アーベル	X1	X2	X3
ベーカ	X4	X5	X6
チャーリ	X7	X8	X9

アーベルの無線士に対する変数は X1、プログラマに対する変数は X2、事務職員に対する変数は X3 である。

アーベルの各職種に対する合計は X1+X2+X3 となる。

ところで、アーベルがどれか一つの職種に配置されると、その職種に対する変数は 1 となり、

その他の職種に対する変数は 0 となる。

したがって X1 と X2,X3 のうちどれか１つだけ１となるから次の等式が成立する。

X1+X2+X3=1

ベーカもチャーリも同様である。

次に、３種類の職種について考える。

無線士のアーベルに対する変数は X1、ベーカに対する変数は X4、チャーリに対する変数は X7 だから、無線士に対する３人の候補者の変数の合計は、 X1+X4+X7 となる。

無線士には１人しか配置されないので、候補者のうちの誰か１人が配置されると、その人に対する変数は 1 となり、他の人に対する変数はすべて 0 とならなければならない。次の等式が成り立つ。

X1+X4+X7=1

制約条件式

X1+X2+X3=1

X4+X5+X6=1

X7+X8+X9=1

X1+X4+X7=1

X2+X5+X8=1

X3+X6+X9=1

X1, X2, X3, X4, X5, X6, X7, X8, X9≧0

目的関数

Z=5X1+4X2+7X3+6X4+7X5+3X6+8X7+11X8+2X9

最適解

X1 = 0.0, X2 = 0.0, X3 = 1.0

X4 = 1.0, X5 = 0.0, X6 = 0.0

X7 = 0.0, X8 = 1.0, X9 = 0.0

Z = 24.0

Python による結果

# 1-62人員の配置
from mypulp import *
master = Model("model162")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
X3 = master.addVar(vtype="C",name="X3")
X4 = master.addVar(vtype="C",name="X4")
X5 = master.addVar(vtype="C",name="X5")
X6 = master.addVar(vtype="C",name="X6")
X7 = master.addVar(vtype="C",name="X7")
X8 = master.addVar(vtype="C",name="X8")
X9 = master.addVar(vtype="C",name="X9")
master.update()
#
master.addConstr(X1+X2+X3 == 1)
master.addConstr(X4+X5+X6 == 1)
master.addConstr(X7+X8+X9 == 1)
master.addConstr(X1+X4+X7 == 1)
master.addConstr(X2+X5+X8 == 1)
master.addConstr(X3+X6+X9 == 1)
#
master.setObjective(5*X1+4*X2+7*X3+6*X4+7*X5+3*X6+8*X7+11*X8+2*X9,GRB.MAXIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #
最適値= 24.0
主要変数=
X3 1.0
X4 1.0
X8 1.0

(6.3) 切符の割当て

問題

４人の同窓生が１０年ぶりに東京に集まって旧交を温めることにした。

その４人は博多、青森、新潟、金沢に住んでいる。東京に集まって会食したのち、

それぞれ自宅に帰る予定である。

博多、青森、金沢の東京往復運賃は、片道が６００㎞を超えるので往復割引になっている。

それぞれの人が東京までの往復切符を買うことにすると、全体では、

23720+17980+10720+16500=68920（円）

である。もっと安くできないか考える。

発/着	博多	青森	新潟	金沢
博多	23720	18440	15550	17510
	X1	X2	X3	X4
青森	18440	17980	12360	14630
	X5	X6	X7	X8
新潟	15550	12360	10720	11430
	X9	X10	X11	X12
金沢	17510	14630	11430	16500
	X13	X14	X15	X16

それぞれが自分の駅からどこかの駅までの切符を東京経由で買い、東京で会食した折にお互いに切符を交換し合い、帰りは交換した切符を使って帰ることにする。

変数X_kは、特定の出発駅から東京経由で特定の帰着駅までの切符を買うか買わないかを表す。

制約条件式

X1+ X2+ X3+ X4 =1
X5+ X6+ X7+ X8 =1
X9+ X10+X11+X12=1
X13+X14+X15+X16=1
X1+ X5+ X9+ X13=1
X2+ X6+ X10+X14=1
X3+ X7+ X11+X15=1
X4+ X8+ X12+X16=1

目的関数

23720*X1+18440*X2+
15550*X3+17510*X4+
18440*X5+17980*X6+
12360*X7+14630*X8+
15550*X9+12360*X10+
10720*X11+11430*X12+
17510*X13+14630*X14+
11430*X15+16500*X16=Z

最適解

X1 = 0.0, X2 = 1.0, X3 = 0.0, X4 = 0.0

X5 = 1.0, X6 = 0.0, X7 = 0.0, X8 = 0.0

X9 = 0.0, X10= 0.0, X11= 0.0, X12= 1.0

X13= 0.0, X14= 0.0, X15= 1.0, X16= 0.0

Z = 59740.0

別解

X1 = 0.0, X2 = 0.0, X3 = 0.0, X4 = 1.0

X5 = 0.0, X6 = 0.0, X7 = 1.0, X8 = 0.0

X9 = 0.0, X10= 1.0, X11= 0.0, X12= 0.0

X13= 1.0, X14= 0.0, X15= 0.0, X16= 0.0

Z = 59740.0

Python による結果

# 1-63切符の割当て
from mypulp import *
master = Model("model163")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
X3 = master.addVar(vtype="C",name="X3")
X4 = master.addVar(vtype="C",name="X4")
X5 = master.addVar(vtype="C",name="X5")
X6 = master.addVar(vtype="C",name="X6")
X7 = master.addVar(vtype="C",name="X7")
X8 = master.addVar(vtype="C",name="X8")
X9 = master.addVar(vtype="C",name="X9")
X10 = master.addVar(vtype="C",name="X10")
X11 = master.addVar(vtype="C",name="X11")
X12 = master.addVar(vtype="C",name="X12")
X13 = master.addVar(vtype="C",name="X13")
X14 = master.addVar(vtype="C",name="X14")
X15 = master.addVar(vtype="C",name="X15")
X16 = master.addVar(vtype="C",name="X16")
master.update()
#
master.addConstr(X1+X2+X3+X4 == 1)
master.addConstr(X5+X6+X7+X8 == 1)
master.addConstr(X9+X10+X11+X12 == 1)
master.addConstr(X13+X14+X15+X16 == 1)
master.addConstr(X1+X5+X9+X13 == 1)
master.addConstr(X2+X6+X10+X14 == 1)
master.addConstr(X3+X7+X11+X15 == 1)
master.addConstr(X4+X8+X12+X16 == 1)
#
master.setObjective(23720*X1+18440*X2+
                    15550*X3+17510*X4+
                    18440*X5+17980*X6+
                    12360*X7+14630*X8+
                    15550*X9+12360*X10+
                    10720*X11+11430*X12+
                    17510*X13+14630*X14+
                    11430*X15+16500*X16,GRB.MINIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #
最適値= 59740.0
主要変数=
X12 1.0
X13 1.0
X2 1.0
X7 1.0

(7.1) 海水浴とレストランでの食事

問題

１週間の夏休みが取れたので、その間に、海水浴に何回か行きたいし、また何回かレストランで食事もしたい。

さて、海水浴に何回行き、レストランで何回食事をとったらよいかを考える。

暇とお金がいくらでもあれば何も問題はないのだが、現実はそうはいかない。

そこで、「限られた日数と小遣いの範囲内で、２つの活動、

すなわち海水浴とレストランでの食事から得られる満足度の総和を最大にするためには、

海水浴に何回行き、レストランで何回食事をとったらよいか」が問題になる。

次のようなデータがある。

	海水浴	レストランでの食事	使用頻度
	X1	X2
日数（日）	2	1	7
小遣い（万円）	1	2	5
満足度	3	2

制約条件式

2X1+1X2≦7

1X1+2X2≦5

X1, X2≧0

目的関数

3X1+2X2=Z

最適解

X1 = 3.0, X2 = 1.0, Z = 11.0

Python による結果

# 1-71海水浴とレストランでの食事
from mypulp import *
master = Model("model162")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
master.update()
#
master.addConstr(2*X1+1*X2 <= 7)
master.addConstr(1*X1+2*X2 <= 5)
#
master.setObjective(3*X1+2*X2,GRB.MAXIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
#
print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
for c in master.getConstrs():
    print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))

最適値= 11.0
主要変数=
X1 3.0
X2 1.0
    Const. Name:    Slack , Dual
            c_1:     -0.0 , 1.3333333
            c_2:     -0.0 , 0.33333333

分析

双対変数の値を見れば、夏休み一日は 1.3 で、小遣い一万円の値は 0.3 である。

夏休みが１日増えて８日間になれば満足度が 12.3 になる。

小遣いが増えて６万円になっても満足度は 11.3 にしかならない。

(7.2) 四半期単位の年間生産販売計画

これは、森口繁一著「線形計画法入門」にある演習問題 (E 1) である。

問題

ある工場で造っている製品 X の四半期ごとの需要高が毎年表のように変動する。

この工場の正規の生産能力は各四半期とも 1000 トンまでである。

だから第３四半期と第４四半期の需要は残業生産によるか、

または前の期から倉庫に貯蔵して繰り越したものでまかなわなければならない。

残業生産の能力は各四半期とも 1000 トンまでである。

残業生産をすると、トン当たり 600 円だけ余計にコストがかかる。

また在庫繰越に要するコストは１期につきトン当たり 400 円である。

四半期	需要高	通常生産力	残業生産力	残業コスト	在庫コスト	繰越
第１	500	1000	1000	600	400
		X1	X2			X3
第２	700	1000	1000	600	400
		X4	X5			X6
第３	1500	1000	1000	600	400
		X7	X8			X9
第４	2000	1000	1000	600	400
		X10	X11			X12

制約条件式

X1 ≦ 1000, X2 ≦ 1000, X4 ≦ 1000, X5 ≦ 1000

X7 ≦ 1000, X8 ≦ 1000, X10 ≦ 1000, X11 ≦ 1000

X12+X1 +X2 -X3= 500

X3 +X4 +X5 -X6= 700

X6 +X7 +X8 -X9=1500

X9 +X10+X11-X12=2000

目的関数

600(X2+X5+X8+X11)+400(X3+X6+X9+X12)=z

最適解

四半期	需要高	通常生産量	残業生産量	繰越在庫
第１	500	500	0	0
第２	700	1000	0	300
第３	1500	1000	200	0
第４	2000	1000	1000	0

Z=840000

Python による結果

# 1-72四半期単位の年間生産計画
from mypulp import *
master = Model("model172")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
X3 = master.addVar(vtype="C",name="X3")
X4 = master.addVar(vtype="C",name="X4")
X5 = master.addVar(vtype="C",name="X5")
X6 = master.addVar(vtype="C",name="X6")
X7 = master.addVar(vtype="C",name="X7")
X8 = master.addVar(vtype="C",name="X8")
X9 = master.addVar(vtype="C",name="X9")
X10 = master.addVar(vtype="C",name="X10")
X11 = master.addVar(vtype="C",name="X11")
X12 = master.addVar(vtype="C",name="X12")
master.update()
#
master.addConstr(X1 <= 1000)
master.addConstr(X2 <= 1000)
master.addConstr(X4 <= 1000)
master.addConstr(X5 <= 1000)
master.addConstr(X7 <= 1000)
master.addConstr(X8 <= 1000)
master.addConstr(X10 <= 1000)
master.addConstr(X11 <= 1000)
master.addConstr(X12+X1+X2-X3 == 500)
master.addConstr(X3+X4+X5-X6 == 700)
master.addConstr(X6+X7+X8-X9 == 1500)
master.addConstr(X9+X10+X11-X12 == 2000)
#
master.setObjective(600*X2+600*X5+600*X8+600*X11+
                    400*X3+400*X6+400*X9+400*X12,GRB.MINIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #
最適値= 840000.0
主要変数=
X1 500.0
X10 1000.0
X11 1000.0
X4 1000.0
X6 300.0
X7 1000.0
X8 200.0

(7.3) 最短路問題

問題

A 町から B 町へ行くのにいくつかの経路がある。

道は図のようになっていて、A, C, D, B 各地点間の所要時間は分単位で分かっている。

AC = 20 分, AD = 35 分, DC = 10 分, CB = 40 分, DB =15 分である。

変数 X_k は経路の流量で 1 または 0 である。

この場合、最も早く B 町へ行くためにはどのようなルートをとればよいか。

　　　　　　　 X6 → ↗ D ―――――――――――――― B ／＼／／＼／／＼／ X2↑／ X3↑＼ X4↓ ／ X5↑ ／＼／／＼／／＼／ → A ―――――――――――――― C X1 →

制約条件式

X1+X2=1

X1-X3+X4-X5=0

X2+X3-X4-X6=0

X5+X6=1

X1, X2, X3, X4, X5, X6 ≧ 0

目的関数

20X1+35X2+10X3+10X4+40X5+15X6=1

最適解

X1 = 1.0, X2 = 0.0, X3 = 1.0, X4 = 0.0, X5 = 0.0, X6 = 1.0

Z = 45.0

Python による結果

1# -73最短路問題
from mypulp import *
master = Model("model173")
X1 = master.addVar(vtype="C",name="X1")
X2 = master.addVar(vtype="C",name="X2")
X3 = master.addVar(vtype="C",name="X3")
X4 = master.addVar(vtype="C",name="X4")
X5 = master.addVar(vtype="C",name="X5")
X6 = master.addVar(vtype="C",name="X6")
master.update()
#
master.addConstr(X1+X2 == 1)
master.addConstr(X1-X3+X4-X5 == 0)
master.addConstr(X2+X3-X4-X6 == 0)
master.addConstr(X5+X6 == 1)
#
master.setObjective(20*X1+35*X2+10*X3+10*X4+40*X5+15*X6,GRB.MINIMIZE)
master.optimize()
#
opval=master.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in master.getVars():
    if v.X>0:
        print(v.VarName,v.X)
        #
最適値= 45.0
主要変数=
X1 1.0
X3 1.0
X6 1.0

ページ先頭

『線形計画法入門（文科系の）』