実践数理計画法

門前パソコン学習所

令和２年弥生
2020-03-28
更新 2023-11-15

実践数理計画法 -LINDOを用いて-: L.Schrage=著; 新村秀一・高森寛=訳; 1992年9月20日初版第１刷; 朝倉書店

ここの問題は上の書籍を参照した。
以下の資料では、計算実行のために LINDO は使用していない。
Pythonを使用した

td> d>

章番号	番号	最適化問題	備考
６．被覆、人員配置、分割問題
	06.1	消防署の配置計画	被覆（カバー）問題
	06.2	人員配置問題
	06.3	分割とパターン選択問題
	06.4	乗員のスケジュール問題
７．ネットワークまたは輸送問題
	07.1	(07.1)ネットワーク型の特徴
	07.3	(07.3)PERT(最長経路問題)
	07.6	(07.6)パスによる定式化
	07.7	(07.7)方向性のないネットワーク
１５．統計的推定への応用（回帰分析）
	15.2	最小絶対偏差（回帰分析）	書籍の記号を確認

６．被覆、人員配置、分割問題

(06.1)消防署の配置計画

ある都市で、要求地から5分以内に到着する場所に、消防署を作る計画がある。

また候補地での年間の維持費用が分かっている。

この問題では、消防署の候補地は最小費用で、しかし要求される場所から５分以内の場所になければならない。

費用を最小化するにはどのような配置が良いか。

		消防署の候補地
		A	B	C	D	E
要求ポイント	1			Y	Y
	2	Y	Y
	3	Y				Y
	4	Y			Y	Y
	5	Y	Y	Y	Y
	6		Y	Y	Y
	7				Y	Y

	費用	310	250	260	330	280

上の表では、Y は次のような意味である。

Y : 候補地に消防署を作った場合５分以内という要求が満たされる。
空欄 : 候補地に消防署を作らない。

問題

全ての要求ポイントから５分以内の場所に、少なくとも１か所消防署が必要であり、

かつ維持費が最小の配置を選択する。

問題定義式

決定変数

A	B	C	D	E
X1	X2	X3	X4	X5

制約条件式

0X1+0X2+1X3+1X4+0X5≧1

1X1+1X2+0X3+0X4+0X5≧1

1X1+0X2+0X3+0X4+1X5≧1

1X1+0X2+0X3+1X4+1X5≧1

1X1+1X2+1X3+1X4+0X5≧1

0X1+1X2+1X3+1X4+0X5≧1

0X1+0X2+0X3+1X4+1X5≧1

X1, X2, X3, X4, X5 ≧ 0

目的関数(min)

Z=310X1+250X2+260X3+330X4+280X5

最適解

X1 = 1.0, X4 = 1.0

Z = 640.0

Python による結果

# 4-061消防署の配置計画
from mypulp import *
#
model = Model("4061")
#
X1 = model.addVar(vtype="C",name="X1")
X2 = model.addVar(vtype="C",name="X2")
X3 = model.addVar(vtype="C",name="X3")
X4 = model.addVar(vtype="C",name="X4")
X5 = model.addVar(vtype="C",name="X5")
model.update()
#
model.addConstr(0*X1+0*X2+1*X3+1*X4+0*X5 >= 1, name="C01")
model.addConstr(1*X1+1*X2+0*X3+0*X4+0*X5 >= 1, name="C02")
model.addConstr(1*X1+0*X2+1*X3+0*X4+1*X5 >= 1, name="C03")
model.addConstr(1*X1+0*X2+0*X3+1*X4+1*X5 >= 1, name="C04")
model.addConstr(1*X1+1*X2+1*X3+1*X4+0*X5 >= 1, name="C05")
model.addConstr(0*X1+1*X2+1*X3+1*X4+0*X5 >= 1, name="C06")
model.addConstr(0*X1+0*X2+0*X3+1*X4+1*X5 >= 1, name="C07")
#
model.setObjective(310*X1+250*X2+260*X3+330*X4+280*X5, GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        #if v.X>0:
        print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#
最適値= 640.0
主要変数=
      Var. Name:        X ,     被約費用
             X1:      1.0 ,      0.0
             X2:      0.0 ,      0.0
             X3:      0.0 ,      0.0
             X4:      1.0 ,      0.0
             X5:      0.0 ,      0.0

(06.2)人員配置問題

ある有料道路は、24時間の間に以下の人員を必要とする料金所を持っている

時間	必要人員
０時～午前６時	2
午前６時～１０時	8
午前１０時～正午	4
正午～午後４時	3
午後４時～６時	6
午後６時～１０時	5
午後１０時～２４時	3

料金所の人間は、４時間働き、１時間休み、また４時間働く。

何時から働いてもよい。

目的関数は雇う人数の最小化である。

**勤務時間**
	0										1										2
変数	0	1	2	3	4	5	6	7	8	9	0	1	2	3	4	5	6	7	8	9	0	1	2	3
X1	-	-	-	-		-	=	=	=
X2		-	-	-	-		=	=	=	=
X3			-	-	-	-		=	=	=	-
X4				-	-	-	=		=	=	-	-
X5					-	-	=	=		=	-	-	-
X6						-	=	=	=		-	-	-	-
X7							=	=	=	=		-	-	-	-
X8								=	=	=	-		-	-	-	-
X9									=	=	-	-		-	-	-	-
X10										=	-	-	-		-	-	-	-
X11											-	-	-	-		-	-	-	-
X12												-	-	-	-		-	-	-	-
X13													-	-	-	-		-	-	-	-
X14														-	-	-	-		-	-	-	-
X15															-	-	-	-		-	-	-	-
X16																-	-	-	-		-	-	-	-
X17	-																-	-	-	-		-	-	-
X18	-	-																-	-	-	-		-	-
X19	-	-	-																-	-	-	-		-
X20	-	-	-	-																-	-	-	-
X21		-	-	-	-																-	-	-	-
X22	-		-	-	-	-																-	-	-
X23	-	-		-	-	-	=																-	-
X24	-	-	-		-	-	=	=																-
人員	2	2	2	2	2	2	8	8	8	8	4	4	3	3	3	3	6	6	5	5	5	5	3	3

決定変数

X₁=夜中から働く人の数

X₂=午前１時から働く人の数

・・・・・・・・・・・・・・・・・・・・

X₂₄=午後１１時から働く人の数

制約条件式

X₁+X₂₄+X₂₃+X₂₂+X₂₀+X₁₉+X₁₈+X₁₇	≧	2	夜中～午前１時
X₂+X₁+X₂₄+X₂₃+X₂₁+X₂₀+X₁₉+X₁₈	≧	2	午前１時～２時
X₃+X₂+X₁+X₂₄+X₂₂+X₂₁+X₂₀+X₁₉	≧	2	午前２時～３時
X₄+X₃+X₂+X₁+X₂₃+X₂₂+X₂₁+X₂₀	≧	2	午前３時～４時
X₅+X₄+X₃+X₂+X₂₄+X₂₃+X₂₂+X₂₁	≧	2	午前４時～５時
X₆+X₅+X₄+X₃+X₁+X₂₄+X₂₃+X₂₂	≧	2	午前５時～６時
X₇+X₆+X₅+X₄+X₂+X₁+X₂₄+X₂₃	≧	8	午前６時～７時

X₂₄+X₂₃+X₂₂+X₂₁+ X₁₉+X₁₈+X₁₇+X₁₆	≧	3	午後１１時から夜中

制約条件式

X1+X24+X23+X22+X20+X19+X18+X17 ≧ 2

X2+X1+X24+X23+X21+X20+X19+X18 ≧ 2

X3+X2+X1+X24+X22+X21+X20 ≧ 2

X4+X3+X2+X1+X23+X22+X21+X20 ≧ 2

X5+X4+X3+X2+X24+X23+X22+X21 ≧ 2

X6+X5+X4+X3+X1+X24+X23+X22 ≧ 2

・・・・・・・・・・・・・・・・・・・・

X7+X6+X5+X4+X2+X1+X24+X23 ≧ 8

X8+X7+X6+X5+X3+X2+X1+X24 ≧ 8

X9+X8+X7+X6+X4+X3+X2+X1 ≧ 8

X10+X9+X8+X7+X5+X4+X3+X2 ≧ 8

・・・・・・・・・・・・・・・・・・・・

X11+X10+X9+X8+X6+X5+X4+X3 ≧ 4

X12+X11+X10+X9+X7+X6+X5+X4 ≧ 4

・・・・・・・・・・・・・・・・・・・・

X13+X12+X11+X10+X8+X7+X6+X5 ≧ 3

X14+X13+X12+X11+X9+X8+X7+X6 ≧ 3

X15+X14+X13+X12+X10+X9+X8+X7 ≧ 3

X16+X15+X14+X13+X11+X10+X9+X8 ≧ 3

・・・・・・・・・・・・・・・・・・・・

X17+X16+X15+X14+X12+X11+X10+X9 ≧ 6

X18+X17+X16+X15+X13+X12+X11+X10 ≧ 6

・・・・・・・・・・・・・・・・・・・・

X19+X18+X17+X16+X14+X13+X12+X11 ≧ 5

X20+X19+X18+X17+X15+X14+X13+X12 ≧ 5

X21+X20+X19+X18+X16+X15+X14+X13 ≧ 5

X22+X21+X20+X19+X17+X16+X15+X14 ≧ 5

・・・・・・・・・・・・・・・・・・・・

X23+X22+X21+X20+X18+X17+X16+X15 ≧ 3

X24+X23+X22+X21+X19+X18+X17+X16≧3

目的関数(min)

X1+X2+X3・・・+X24

最適解

X2=5, X4=0.75, X5=0.75, X6=0.75, X7=0.75, X8=0.75,

X11=1, X14=1, X15=2, X16=1, X17=1, X18=1

Z=15.75

書籍解

X2=5, X3=0.75, X4=0.75, X5=0.75, X6=0.75, X7=0.75,

X11=1, X14=1, X15=2, X16=1, X17=1, X18=1

Z=15.75

解に対する検討

答えに小数が出ているが、15.75 というのは少なくとも 16 人を雇わなくてはならないことを意味する。

整数解を必要とするからである。このため X3=X4=X6=X7=1,X5=0 のように丸めればよい。

シフト、または勤務時間内に休憩がほとんどないときには、解は整数計画法を用いなくとも、値が整数になることが多い。

解の比較

X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13	X14	X15	X16	X17	X18	X19	X20	X21	X22	X23	X24
	5		0.75	0.75	0.75	0.75	0.75			1			1	2	1	1	1
	5	0.75	0.75	0.75	0.75	0.75				1			1	2	1	1	1
	5	0.75	0.75	0.75	0.75	0.75				1			1	2	1	1	1


	4		1	1	1	1	1					0.5	0.75	1.75	1.75	1.75	0.25

X3の場合、６から７の間は休憩していることに注意

解の比較の上段は、当ページ作成の（倍精度版）プログラムによる。

解の比較の中段は、書籍解による。

解の比較の下段は、当ページ作成の（単精度版）プログラムによる。

また最下部は、Python による結果である。

Python による結果

# 4-062人員配置問題2
from mypulp import *
#
model = Model("40622")
#
X1 = model.addVar(vtype="C",name="X01")
X2 = model.addVar(vtype="C",name="X02")
X3 = model.addVar(vtype="C",name="X03")
X4 = model.addVar(vtype="C",name="X04")
X5 = model.addVar(vtype="C",name="X05")
X6 = model.addVar(vtype="C",name="X06")
X7 = model.addVar(vtype="C",name="X07")
X8 = model.addVar(vtype="C",name="X08")
X9 = model.addVar(vtype="C",name="X09")
X10 = model.addVar(vtype="C",name="X10")
X11 = model.addVar(vtype="C",name="X11")
X12 = model.addVar(vtype="C",name="X12")
X13 = model.addVar(vtype="C",name="X13")
X14 = model.addVar(vtype="C",name="X14")
X15 = model.addVar(vtype="C",name="X15")
X16 = model.addVar(vtype="C",name="X16")
X17 = model.addVar(vtype="C",name="X17")
X18 = model.addVar(vtype="C",name="X18")
X19 = model.addVar(vtype="C",name="X19")
X20 = model.addVar(vtype="C",name="X20")
X21 = model.addVar(vtype="C",name="X21")
X22 = model.addVar(vtype="C",name="X22")
X23 = model.addVar(vtype="C",name="X23")
X24 = model.addVar(vtype="C",name="X24")
model.update()
#
model.addConstr(X1+X24+X23+X22+X20+X19+X18+X17 >= 2, name="C01")
model.addConstr(X2+X1+X24+X23+X21+X20+X19+X18 >= 2, name="C02")
model.addConstr(X3+X2+X1+X24+X22+X21+X20 >= 2, name="C03")
model.addConstr(X4+X3+X2+X1+X23+X22+X21+X20 >= 2, name="C04")
model.addConstr(X5+X4+X3+X2+X24+X23+X22+X21 >= 2, name="C05")
model.addConstr(X6+X5+X4+X3+X1+X24+X23+X22 >= 2, name="C06")
#・・・・・・・・・・・・・・・・・・・・
model.addConstr(X7+X6+X5+X4+X2+X1+X24+X23 >= 8, name="C07")
model.addConstr(X8+X7+X6+X5+X3+X2+X1+X24 >= 8, name="C08")
model.addConstr(X9+X8+X7+X6+X4+X3+X2+X1 >= 8, name="C09")
model.addConstr(X10+X9+X8+X7+X5+X4+X3+X2 >= 8, name="C10")
#・・・・・・・・・・・・・・・・・・・・
model.addConstr(X11+X10+X9+X8+X6+X5+X4+X3 >= 4, name="C11")
model.addConstr(X12+X11+X10+X9+X7+X6+X5+X4 >= 4, name="C12")
#・・・・・・・・・・・・・・・・・・・・
model.addConstr(X13+X12+X11+X10+X8+X7+X6+X5 >= 3, name="C13")
model.addConstr(X14+X13+X12+X11+X9+X8+X7+X6 >= 3, name="C14")
model.addConstr(X15+X14+X13+X12+X10+X9+X8+X7 >= 3, name="C15")
model.addConstr(X16+X15+X14+X13+X11+X10+X9+X8 >= 3, name="C16")
#・・・・・・・・・・・・・・・・・・・・
model.addConstr(X17+X16+X15+X14+X12+X11+X10+X9 >= 6, name="C17")
model.addConstr(X18+X17+X16+X15+X13+X12+X11+X10 >= 6, name="C18")
#・・・・・・・・・・・・・・・・・・・・
model.addConstr(X19+X18+X17+X16+X14+X13+X12+X11 >= 5, name="C19")
model.addConstr(X20+X19+X18+X17+X15+X14+X13+X12 >= 5, name="C20")
model.addConstr(X21+X20+X19+X18+X16+X15+X14+X13 >= 5, name="C21")
model.addConstr(X22+X21+X20+X19+X17+X16+X15+X14 >= 5, name="C22")
#・・・・・・・・・・・・・・・・・・・・
model.addConstr(X23+X22+X21+X20+X18+X17+X16+X15 >= 3, name="C23")
model.addConstr(X24+X23+X22+X21+X19+X18+X17+X16 >= 3, name="C24")

model.setObjective(
    X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+
    X11+X12+X13+X14+X15+X16+X17+X18+X19+X20+
    X21+X22+X23+X24, GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        #if v.X>0:
        print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#

最適値= 15.75
主要変数=
      Var. Name:        X ,     被約費用
            X01:      0.0 ,     0.25
            X02:      4.0 ,      0.0
            X03:      0.0 ,      0.0
            X04:      1.0 ,      0.0
            X05:      1.0 ,      0.0
            X06:      1.0 ,      0.0
            X07:      1.0 ,      0.0
            X08:      1.0 ,      0.0
            X09:      0.0 ,      0.0
            X10:      0.0 ,      0.0
            X11:      0.0 ,      0.0
            X12:      0.0 ,      0.0
            X13:      0.5 ,      0.0
            X14:     0.75 ,      0.0
            X15:     1.75 ,      0.0
            X16:     1.75 ,      0.0
            X17:     1.75 ,      0.0
            X18:     0.25 ,      0.0
            X19:      0.0 ,     0.25
            X20:      0.0 ,      0.5
            X21:      0.0 ,     0.75
            X22:      0.0 ,      1.0
            X23:      0.0 ,     0.75
            X24:      0.0 ,      0.5
双対変数=
    Const. Name:    Slack , Dual
            C01:     -0.0 ,  0.0
            C02:    -2.25 ,  0.0
            C03:     -2.0 ,  0.0
            C04:     -3.0 ,  0.0
            C05:     -4.0 ,  0.0
            C06:     -1.0 ,  0.0
            C07:     -0.0 , 0.25
            C08:     -0.0 , 0.25
            C09:     -0.0 , 0.25
            C10:     -0.0 , 0.25
            C11:     -0.0 , 0.25
            C12:     -0.0 ,  0.0
            C13:     -1.5 ,  0.0
            C14:    -1.25 ,  0.0
            C15:     -2.0 ,  0.0
            C16:    -2.75 ,  0.0
            C17:     -0.0 , 0.25
            C18:     -0.0 , 0.25
            C19:     -0.0 , 0.25
            C20:     -0.0 , 0.25
            C21:     -0.0 , 0.25
            C22:     -1.0 ,  0.0
            C23:     -2.5 ,  0.0
            C24:    -0.75 ,  0.0

(06.3)分割とパターン選択問題

C 社は非常に幅広い家庭用器具すなわち冷蔵庫やストーブなどを生産している。

原材料費用の重要な部分は鉄板の購入である。

現在、鉄板はコイルの形で購入されていて、３種類の幅７２，４８，３６のものがある。

製造工程では８種類の幅が要求される。

それは６０，５６，４２，３８，３４，２４，１５そして１０である。

使用に際して、同じ品質と厚さが要求される。

問題は、無駄を取り除くことである。

例えば７２幅のコイルを３８幅のコイルと１５幅のコイル２つに切り離すやり方 B0 がある。

ここで、４幅の無駄が出てしまう。

３つの異なった幅の原材料の１長さ単位の価格は、３６幅が１５，４８幅が１９，７２幅が２８である。

単純な計算により、単位価格は３６幅が 15/36 = 0.41667、４８幅が 0.395833、７２幅が 0.3888889 である。

コイルは適切な方法で切り離される。３つの幅の原材料を切り離す効率的なやり方を表に示す。

例えばパターン C4 は７２幅のコイルを、２４幅１つと１０幅４つ、無駄として８が残るように切り離すことである。

**原材料に対する分割パターン**
	要求幅のカット数										要求幅のカット数
パターン	60	56	42	38	34	24	15	10	無駄な幅	パターン	60	56	42	38	34	24	15	10	無駄な幅
７２の原材料										４８の原材料
A₁	1	0	0	0	0	0	0	1	2	D₀	0	0	1	0	0	0	0	0	6
A₂	0	1	0	0	0	0	1	0	1	D₁	0	0	0	1	0	0	0	1	0
A₃	0	1	0	0	0	0	0	1	6	D₂	0	0	0	0	1	0	0	1	4
A₄	0	0	1	0	0	1	0	0	6	D₃	0	0	0	0	0	2	0	0	0
A₅	0	0	1	0	0	0	2	0	0	D₄	0	0	0	0	0	1	1	0	9
A₆	0	0	1	0	0	0	1	1	5	D₅	0	0	0	0	0	1	0	2	4
A₇	0	0	1	0	0	0	0	3	0	D₆	0	0	0	0	0	0	3	0	3
A₈	0	0	0	1	1	0	0	0	0	D₇	0	0	0	0	0	0	2	1	8
A₉	0	0	0	1	0	1	0	1	0	D₈	0	0	0	0	0	0	1	3	3
B₀	0	0	0	1	0	0	2	0	4	D₉	0	0	0	0	0	0	0	4	8
B₁	0	0	0	1	0	0	1	1	9	３６の原材料
B₂	0	0	0	1	0	0	0	3	4	E₀	0	0	0	0	1	0	0	0	2
B₃	0	0	0	0	2	0	0	0	4	E₁	0	0	0	0	0	1	0	1	2
B₄	0	0	0	0	1	1	0	1	4	E₂	0	0	0	0	0	0	2	0	6
B₅	0	0	0	0	1	0	2	0	8	E₃	0	0	0	0	0	0	1	2	1
B₆	0	0	0	0	1	0	1	2	3	E₄	0	0	0	0	0	0	0	3	6
B₇	0	0	0	0	1	0	0	3	8
B₈	0	0	0	0	0	3	0	0	0
B₉	0	0	0	0	0	2	1	0	9
C₀	0	0	0	0	0	2	0	2	4
C₁	0	0	0	0	0	1	3	0	3
C₂	0	0	0	0	0	1	2	1	8
C₃	0	0	0	0	0	1	1	3	3
C₄	0	0	0	0	0	1	0	4	8
C₅	0	0	0	0	0	0	4	1	2
C₆	0	0	0	0	0	0	3	2	7
C₇	0	0	0	0	0	0	2	4	2
C₈	0	0	0	0	0	0	1	5	7
C₉	0	0	0	0	0	0	0	7	2

	60	56	42	38	34	24	15	10

この計画期間において要求されるさまざまな幅の長さは次のとおりである。

変数

			分割パターン

			72(T1)									48(T2)			36(T3)
要求材料			A1	--	A9	B0	--	B9	C0	--	C9	D0	--	D9	E0	--	E4
	幅	長さ	72									48			36
X1	60	500
X2	56	400
X3	42	300
X4	38	450
X5	34	350
X6	24	100
X7	15	800
X8	10	1000

この期間において使用できる原材料は、７２幅のコイルで１６００、４８幅と３６幅で１００００である。

様々な幅や要求を満たし、かつ最小費用になるように分割される、

それぞれのパターンの長さを決定するためのモデルを定式化することが求められる。

原材料に対する制約

T1 ≦ 1600

T2 ≦ 10000

T3 ≦ 10000

変数定義（原材料数）

T1	=	A1+A2+A3+A4+A5+A6+A7+A8+A9+
		B0+B1+B2+B3+B4+B5+B6+B7+B8+B9+
		C0+C1+C2+C3+C4+C5+C6+C7+C8+C9
T2	=	D0+D1+D2+D3+D4+D5+D6+D7+D8+D9
T3	=	E0+E1+E2+E3+E4

変数定義（無駄の幅）

W1	=	2A1+A2+6A3+6A4+5A6+
		4B0+9B1+4B2+4B3+4B4+8B5+3B6+8B7+9B9+
		4C0+3C1+8C2+3C3+8C4+2C5+7C6+2C7+7C8+2C9
W2	=	6D0+4D2+9D4+4D5+3D6+8D7+3D8+8D9
W3	=	2E0+2E1+6E2+E3+6E4

変数定義

X1～X8は、それぞれの幅の、過剰カット長さ。

要求１

幅６０のものを長さ５００必要とする。

この要求を満たすパターンは A1 しかない。

A1=500+X1

要求２

幅５６のものを長さ４００必要とする。

A2+A3=400+X2

要求３

幅４２のものを長さ３００必要とする。

次のパターンが利用できる。

A4+A5+A6+A7+D0=300+X3

要求４

幅３８のものを長さ４５０必要とする。

A8+A9+B0+B1+B2+D1=450+X4

要求５

幅３４のものを長さ３５０必要とする。

A8+2B3+B4+B5+B6+B7+D2+E0=350+X5

要求６

幅２４のものを長さ１００必要とする。

A4+A9+B4+3B8+2B9+2C0+C1+C2+C3+C4+2D3+D4+D5+E1=100+X6

要求７

幅１５のものを長さ８００必要とする。

A2+2A5+A6+2B0+B1+2B5+B6+B9+

3C1+2C2+C3+4C5+3C6+2C7+C8+

D4+3D6+2D7+D8+2E2+E3=800+X7

要求８

幅１０のものを長さ１０００必要とする。

A1+A3+A6+3A7+A9+B1+3B2+B4+2B6+3B7+

2C0+C2+3C3+4C4+C5+2C6+4C7+5C8+7C9+

D1+D2+2D5+D7+3D8+4D9+E1+2E3+3E4=1000+X8

変数対応表

X1	X2	X3	X4	X5	X6	X7	X8
X1	X2	X3	X4	X5	X6	X7	X8
A1	A2	A3	A4	A5	A6	A7	A8	A9
X9	X10	X11	X12	X13	X14	X15	X16	X17
B0	B1	B2	B3	B4	B5	B6	B7	B8	B9
X18	X19	X20	X21	X22	X23	X24	X25	X26	X27
C0	C1	C2	C3	C4	C5	C6	C7	C8	C9
X28	X29	X30	X31	X32	X33	X34	X35	X36	X37
D0	D1	D2	D3	D4	D5	D6	D7	D8	D9
X38	X39	X40	X41	X42	X43	X44	X45	X46	X47
E0	E1	E2	E3	E4
X48	X49	X50	X51	X52
T1	T2	T3	W1	W2	W3
X53	X54	X55	X56	X57	X58

目的関数(min) Z=28T1+19T2+15T3

制約式

T1 ≦ 1600

T2 ≦ 10000

T3 ≦ 10000

T1-A1-A2-A3-A4-A5-A6-A7-A8-A9- B0-B1-B2-B3-B4-B5-B6-B7-B8-B9-

C0-C1-C2-C3-C4-C5-C6-C7-C8-C9 = 0

T3-E0-E1-E2-E3-E4 = 0

総費用を最小にした解

最小値は 46632.1 です

無駄を最小にした解

最小値は 544.445 です

総費用を最小にした解			無駄を最小にした解
0 でない変数	パターン		0 でない変数	パターン
			x[ 3]	X3	16.6667
			x[ 4]	X4	50
x[ 9]	A1	500	x[ 9]	A1	500
x[10]	A2	400	x[10]	A2	400
x[13]	A5	171.429	x[13]	A5	200
x[15]	A7	128.571	x[15]	A7	116.667
x[16]	A8	350	x[16]	A8	350
x[17]	A9	3.57143
x[26]	B8	32.1429	x[26]	B8	33.3333
x[33]	C5	14.2857
x[39]	D1	96.4286	x[39]	D1	150
x[53]	T1	1600	x[53]	T1	1600
x[54]	T2	96.4286	x[54]	T2	150
x[55]	T3	0	x[55]	T3	0
x[56]	W1	1428.57	x[56]	W1	1400
x[57]	W2	0	x[57]	W2	0
x[58]	W3	0	x[58]	W3	0

Python による結果

# 4-063分割とパターン選択問題
from mypulp import *
#
model = Model("4063")
#
X1 = model.addVar(vtype="C",name="X1")
X2 = model.addVar(vtype="C",name="X2")
X3 = model.addVar(vtype="C",name="X3")
X4 = model.addVar(vtype="C",name="X4")
X5 = model.addVar(vtype="C",name="X5")
X6 = model.addVar(vtype="C",name="X6")
X7 = model.addVar(vtype="C",name="X7")
X8 = model.addVar(vtype="C",name="X8")
#
A1 = model.addVar(vtype="C",name="A1")
A2 = model.addVar(vtype="C",name="A2")
A3 = model.addVar(vtype="C",name="A3")
A4 = model.addVar(vtype="C",name="A4")
A5 = model.addVar(vtype="C",name="A5")
A6 = model.addVar(vtype="C",name="A6")
A7 = model.addVar(vtype="C",name="A7")
A8 = model.addVar(vtype="C",name="A8")
A9 = model.addVar(vtype="C",name="A9")
#
B0 = model.addVar(vtype="C",name="B0")
B1 = model.addVar(vtype="C",name="B1")
B2 = model.addVar(vtype="C",name="B2")
B3 = model.addVar(vtype="C",name="B3")
B4 = model.addVar(vtype="C",name="B4")
B5 = model.addVar(vtype="C",name="B5")
B6 = model.addVar(vtype="C",name="B6")
B7 = model.addVar(vtype="C",name="B7")
B8 = model.addVar(vtype="C",name="B8")
B9 = model.addVar(vtype="C",name="B9")
#
C0 = model.addVar(vtype="C",name="C0")
C1 = model.addVar(vtype="C",name="C1")
C2 = model.addVar(vtype="C",name="C2")
C3 = model.addVar(vtype="C",name="C3")
C4 = model.addVar(vtype="C",name="C4")
C5 = model.addVar(vtype="C",name="C5")
C6 = model.addVar(vtype="C",name="C6")
C7 = model.addVar(vtype="C",name="C7")
C8 = model.addVar(vtype="C",name="C8")
C9 = model.addVar(vtype="C",name="C9")
#
D0 = model.addVar(vtype="C",name="D0")
D1 = model.addVar(vtype="C",name="D1")
D2 = model.addVar(vtype="C",name="D2")
D3 = model.addVar(vtype="C",name="D3")
D4 = model.addVar(vtype="C",name="D4")
D5 = model.addVar(vtype="C",name="D5")
D6 = model.addVar(vtype="C",name="D6")
D7 = model.addVar(vtype="C",name="D7")
D8 = model.addVar(vtype="C",name="D8")
D9 = model.addVar(vtype="C",name="D9")
#
E0 = model.addVar(vtype="C",name="E0")
E1 = model.addVar(vtype="C",name="E1")
E2 = model.addVar(vtype="C",name="E2")
E3 = model.addVar(vtype="C",name="E3")
E4 = model.addVar(vtype="C",name="E4")
#
T1 = model.addVar(vtype="C",name="T1")
T2 = model.addVar(vtype="C",name="T2")
T3 = model.addVar(vtype="C",name="T3")
#
W1 = model.addVar(vtype="C",name="W1")
W2 = model.addVar(vtype="C",name="W2")
W3 = model.addVar(vtype="C",name="W3")
model.update()
#
model.addConstr(T1 <= 1600)
model.addConstr(T2 <= 10000)
model.addConstr(T3 <= 10000)
#
model.addConstr(T1-A1-A2-A3-A4-A5-A6-A7-A8-A9-
                B0-B1-B2-B3-B4-B5-B6-B7-B8-B9-
                C0-C1-C2-C3-C4-C5-C6-C7-C8-C9 == 0)
model.addConstr(T2-D0-D1-D2-D3-D4-D5-D6-D7-D8-D9 == 0)
model.addConstr(T3-E0-E1-E2-E3-E4 == 0)
model.addConstr(2*A1+A2+6*A3+6*A4+5*A6+
                4*B0+9*B1+4*B2+4*B3+4*B4+8*B5+3*B6+8*B7+9*B9+
                4*C0+3*C1+8*C2+3*C3+8*C4+2*C5+7*C6+2*C7+7*C8+2*C9-W1 == 0)
model.addConstr(6*D0+4*D2+9*D4+4*D5+3*D6+8*D7+3*D8+8*D9-W2 == 0)
model.addConstr(2*E0+2*E1+6*E2+E3+6*E4-W3 == 0)
#
model.addConstr(A1-X1 == 500)
model.addConstr(A2+A3-X3 == 400)
model.addConstr(A4+A5+A6+A7+D0-X3 == 300)
model.addConstr(A8+A9+B0+B1+B2+D1-X4 == 450)
model.addConstr(A8+2*B3+B4+B5+B6+B7+D2+E0-X5 == 350)
model.addConstr(A4+A9+B4+3*B8+2*B9+2*C0+C1+C2+C3+C4+2*D3+D4+D5+E1-X6 == 100)
model.addConstr(A2+2*A5+A6+2*B0+B1+2*B5+B6+B9+
                3*C1+2*C2+C3+4*C5+3*C6+2*C7+C8+D4+3*D6+2*D7+D8+2*E2+E3-X7 == 800)
model.addConstr(A1+A3+A6+3*A7+A9+B1+3*B2+B4+2*B6+3*B7+
                2*C0+C2+3*C3+4*C4+C5+2*C6+4*C7+5*C8+7*C9+
                D1+D2+2*D5+D7+3*D8+4*D9+E1+2*E3+3*E4-X8 == 1000)
#
model.setObjective(28*T1+19*T2+15*T3, GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        #if v.X>0:
        print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#
最適値= 46632.142849
主要変数=
      Var. Name:        X ,     被約費用
             A1:    500.0 , -8.8817842e-16
             A2:    400.0 , 1.7763568e-15
             A3:      0.0 , 2.0357143
             A4:      0.0 , 2.7142857
             A5:    200.0 ,      0.0
             A6:      0.0 , 2.0357143
             A7:    100.0 ,      0.0
             A8:    350.0 ,      0.0
             A9: 3.5714286 , -2.6645353e-15
             B0:      0.0 , 1.3571429
             B1:      0.0 , 3.3928571
             B2:      0.0 , 1.3571429
             B3:      0.0 , 1.3571429
             B4:      0.0 , 1.3571429
             B5:      0.0 , 2.7142857
             B6:      0.0 , 0.67857143
             B7:      0.0 , 2.7142857
             B8: 32.142857 , 3.5527137e-15
             B9:      0.0 , 3.3928571
             C0:      0.0 , 1.3571429
             C1:      0.0 , 0.67857143
             C2:      0.0 , 2.7142857
             C3:      0.0 , 0.67857143
             C4:      0.0 , 2.7142857
             C5:      0.0 , 2.6645353e-15
             C6:      0.0 , 2.0357143
             C7:      0.0 , 3.5527137e-15
             C8:      0.0 , 2.0357143
             C9: 14.285714 , 3.5527137e-15
             D0:      0.0 , 2.7142857
             D1: 96.428571 , -8.8817842e-16
             D2:      0.0 , 1.3571429
             D3:      0.0 , 3.5527137e-15
             D4:      0.0 , 3.3928571
             D5:      0.0 , 1.3571429
             D6:      0.0 , 0.67857143
             D7:      0.0 , 2.7142857
             D8:      0.0 , 0.67857143
             D9:      0.0 , 2.7142857
             E0:      0.0 , 0.67857143
             E1:      0.0 , 0.67857143
             E2:      0.0 , 2.0357143
             E3:      0.0 ,      0.0
             E4:      0.0 , 2.0357143
             T1:   1600.0 ,      0.0
             T2: 96.428571 ,      0.0
             T3:      0.0 ,     0.75
             W1: 1428.5714 ,      0.0
             W2:     -0.0 ,      0.0
             W3:     -0.0 ,      0.0
             X1:      0.0 , 24.428571
             X3:      0.0 , 38.678571
             X4:      0.0 , 14.928571
             X5:      0.0 , 13.571429
             X6:      0.0 ,      9.5
             X7:      0.0 , 6.1071429
             X8:      0.0 , 4.0714286
双対変数=
    Const. Name:    Slack , Dual
            c_1:     -0.0 , -0.5
            c_2: 9903.571429 ,  0.0
            c_3:  10000.0 ,  0.0
            c_4:     -0.0 , 28.5
            c_5:     -0.0 , 19.0
            c_6:     -0.0 , 14.25
            c_7:     -0.0 , -0.0
            c_8:     -0.0 , -0.0
            c_9:     -0.0 , -0.0
           c_10:     -0.0 , 24.428571
           c_11:     -0.0 , 22.392857
           c_12:     -0.0 , 16.285714
           c_13:     -0.0 , 14.928571
           c_14:     -0.0 , 13.571429
           c_15:     -0.0 ,  9.5
           c_16:     -0.0 , 6.1071429
           c_17:     -0.0 , 4.0714286

無駄を最小にした解

最適値= 544.44474

総費用を最小にした解

最小値は 46632.1 です

総費用を最小にした解			無駄を最小にした解
		書籍解		書籍解
A1	500.0	500	500	500
A2	400.0	400	400	400
A5	200.0	171.42865	200	200
A7	100.0	128.57135	100	135.5
A8	350.0	350	350	362.5
A9	3.5714286	3.57139		0
B8	32.142857	32.1429	50	0
C5		14.286		0
C9	14.285714
D1	96.428571	96.4286	200	87.5
D3		0		50
T1	1600.0	1600	1600	1600
T2	96.428571	96.429	200	137.5
T3		0		0
W1	1428.5714			0
X3		0		37.5
X4			100	0
X5		0		12.5
X6			50	0

Python による結果

# 4-063分割とパターン選択問題
from mypulp import *
#
model = Model("4063")
#
X1 = model.addVar(vtype="C",name="X1")
X2 = model.addVar(vtype="C",name="X2")
X3 = model.addVar(vtype="C",name="X3")
X4 = model.addVar(vtype="C",name="X4")
X5 = model.addVar(vtype="C",name="X5")
X6 = model.addVar(vtype="C",name="X6")
X7 = model.addVar(vtype="C",name="X7")
X8 = model.addVar(vtype="C",name="X8")
#
A1 = model.addVar(vtype="C",name="A1")
A2 = model.addVar(vtype="C",name="A2")
A3 = model.addVar(vtype="C",name="A3")
A4 = model.addVar(vtype="C",name="A4")
A5 = model.addVar(vtype="C",name="A5")
A6 = model.addVar(vtype="C",name="A6")
A7 = model.addVar(vtype="C",name="A7")
A8 = model.addVar(vtype="C",name="A8")
A9 = model.addVar(vtype="C",name="A9")
#
B0 = model.addVar(vtype="C",name="B0")
B1 = model.addVar(vtype="C",name="B1")
B2 = model.addVar(vtype="C",name="B2")
B3 = model.addVar(vtype="C",name="B3")
B4 = model.addVar(vtype="C",name="B4")
B5 = model.addVar(vtype="C",name="B5")
B6 = model.addVar(vtype="C",name="B6")
B7 = model.addVar(vtype="C",name="B7")
B8 = model.addVar(vtype="C",name="B8")
B9 = model.addVar(vtype="C",name="B9")
#
C0 = model.addVar(vtype="C",name="C0")
C1 = model.addVar(vtype="C",name="C1")
C2 = model.addVar(vtype="C",name="C2")
C3 = model.addVar(vtype="C",name="C3")
C4 = model.addVar(vtype="C",name="C4")
C5 = model.addVar(vtype="C",name="C5")
C6 = model.addVar(vtype="C",name="C6")
C7 = model.addVar(vtype="C",name="C7")
C8 = model.addVar(vtype="C",name="C8")
C9 = model.addVar(vtype="C",name="C9")
#
D0 = model.addVar(vtype="C",name="D0")
D1 = model.addVar(vtype="C",name="D1")
D2 = model.addVar(vtype="C",name="D2")
D3 = model.addVar(vtype="C",name="D3")
D4 = model.addVar(vtype="C",name="D4")
D5 = model.addVar(vtype="C",name="D5")
D6 = model.addVar(vtype="C",name="D6")
D7 = model.addVar(vtype="C",name="D7")
D8 = model.addVar(vtype="C",name="D8")
D9 = model.addVar(vtype="C",name="D9")
#
E0 = model.addVar(vtype="C",name="E0")
E1 = model.addVar(vtype="C",name="E1")
E2 = model.addVar(vtype="C",name="E2")
E3 = model.addVar(vtype="C",name="E3")
E4 = model.addVar(vtype="C",name="E4")
#
T1 = model.addVar(vtype="C",name="T1")
T2 = model.addVar(vtype="C",name="T2")
T3 = model.addVar(vtype="C",name="T3")
#
W1 = model.addVar(vtype="C",name="W1")
W2 = model.addVar(vtype="C",name="W2")
W3 = model.addVar(vtype="C",name="W3")
model.update()
#
model.addConstr(T1 <= 1600)
model.addConstr(T2 <= 10000)
model.addConstr(T3 <= 10000)
#
model.addConstr(T1-A1-A2-A3-A4-A5-A6-A7-A8-A9-
                B0-B1-B2-B3-B4-B5-B6-B7-B8-B9-
                C0-C1-C2-C3-C4-C5-C6-C7-C8-C9 == 0)
model.addConstr(T2-D0-D1-D2-D3-D4-D5-D6-D7-D8-D9 == 0)
model.addConstr(T3-E0-E1-E2-E3-E4 == 0)
model.addConstr(2*A1+A2+6*A3+6*A4+5*A6+
                4*B0+9*B1+4*B2+4*B3+4*B4+8*B5+3*B6+8*B7+9*B9+
                4*C0+3*C1+8*C2+3*C3+8*C4+2*C5+7*C6+2*C7+7*C8+2*C9-W1 == 0)
model.addConstr(6*D0+4*D2+9*D4+4*D5+3*D6+8*D7+3*D8+8*D9-W2 == 0)
model.addConstr(2*E0+2*E1+6*E2+E3+6*E4-W3 == 0)
#
model.addConstr(A1-X1 == 500)
model.addConstr(A2+A3-X3 == 400)
model.addConstr(A4+A5+A6+A7+D0-X3 == 300)
model.addConstr(A8+A9+B0+B1+B2+D1-X4 == 450)
model.addConstr(A8+2*B3+B4+B5+B6+B7+D2+E0-X5 == 350)
model.addConstr(A4+A9+B4+3*B8+2*B9+2*C0+C1+C2+C3+C4+2*D3+D4+D5+E1-X6 == 100)
model.addConstr(A2+2*A5+A6+2*B0+B1+2*B5+B6+B9+
                3*C1+2*C2+C3+4*C5+3*C6+2*C7+C8+D4+3*D6+2*D7+D8+2*E2+E3-X7 == 800)
model.addConstr(A1+A3+A6+3*A7+A9+B1+3*B2+B4+2*B6+3*B7+
                2*C0+C2+3*C3+4*C4+C5+2*C6+4*C7+5*C8+7*C9+
                D1+D2+2*D5+D7+3*D8+4*D9+E1+2*E3+3*E4-X8 == 1000)
#
#model.setObjective(28*T1+19*T2+15*T3, GRB.MINIMIZE)
model.setObjective(0.3888891*W1+0.395833*W2+0.416667*W3, GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        #if v.X>0:
        print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#
最適値= 544.44474
主要変数=
      Var. Name:        X ,     被約費用
             A1:    500.0 ,      0.0
             A2:    400.0 ,      0.0
             A3:      0.0 , 1.9444455
             A4:      0.0 , 2.3333346
             A5:    200.0 ,      0.0
             A6:      0.0 , 1.9444455
             A7:    100.0 ,      0.0
             A8:    350.0 ,      0.0
             A9:      0.0 ,      0.0
             B0:      0.0 , 1.5555564
             B1:      0.0 , 3.5000019
             B2:      0.0 , 1.5555564
             B3:      0.0 , 1.5555564
             B4:      0.0 , 1.5555564
             B5:      0.0 , 3.1111128
             B6:      0.0 , 1.1666673
             B7:      0.0 , 3.1111128
             B8:     50.0 ,      0.0
             B9:      0.0 , 3.5000019
             C0:      0.0 , 1.5555564
             C1:      0.0 , 1.1666673
             C2:      0.0 , 3.1111128
             C3:      0.0 , 1.1666673
             C4:      0.0 , 3.1111128
             C5:      0.0 , 0.7777782
             C6:      0.0 , 2.7222237
             C7:      0.0 , 0.7777782
             C8:      0.0 , 2.7222237
             C9:      0.0 , 0.7777782
             D0:      0.0 , 2.374998
             D1:    200.0 ,      0.0
             D2:      0.0 , 1.583332
             D3:      0.0 ,      0.0
             D4:      0.0 , 3.562497
             D5:      0.0 , 1.583332
             D6:      0.0 , 1.187499
             D7:      0.0 , 3.166664
             D8:      0.0 , 1.187499
             D9:      0.0 , 3.166664
             E0:      0.0 , 0.833334
             E1:      0.0 , 0.833334
             E2:      0.0 , 2.500002
             E3:      0.0 , 0.416667
             E4:      0.0 , 2.500002
             T1:   1600.0 ,      0.0
             T2:    200.0 ,      0.0
             T3:      0.0 ,      0.0
             W1:   1400.0 ,      0.0
             W2:     -0.0 ,      0.0
             W3:     -0.0 ,      0.0
             X1:      0.0 , 0.7777782
             X3:      0.0 , 0.3888891
             X4:    100.0 ,      0.0
             X5:      0.0 ,      0.0
             X6:     50.0 ,      0.0
             X7:      0.0 ,      0.0
             X8:      0.0 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
            c_1:     -0.0 ,  0.0
            c_2:   9800.0 ,  0.0
            c_3:  10000.0 ,  0.0
            c_4:     -0.0 ,  0.0
            c_5:     -0.0 ,  0.0
            c_6:     -0.0 ,  0.0
            c_7:     -0.0 , -0.3888891
            c_8:     -0.0 , -0.395833
            c_9:     -0.0 , -0.416667
           c_10:     -0.0 , 0.7777782
           c_11:     -0.0 , 0.3888891
           c_12:     -0.0 ,  0.0
           c_13:     -0.0 ,  0.0
           c_14:     -0.0 ,  0.0
           c_15:     -0.0 ,  0.0
           c_16:     -0.0 ,  0.0
           c_17:     -0.0 ,  0.0

(06.4)乗員のスケジュール問題

A 航空会社は、以下のフライトを運航している。

	フライト番号	出発地	目的地	時間
①	101	シカゴ	ロサンゼルス	午後
②	410	ニューヨーク	シカゴ	午後
③	220	ニューヨーク	マイアミ	夜
④	17	マイアミ	シカゴ	朝
⑤	7	ロサンゼルス	シカゴ	午後
⑥	13	シカゴ	ニューヨーク	夜
⑦	11	マイアミ	ニューヨーク	朝
⑧	19	シカゴ	マイアミ	夜
⑨	23	ロサンゼルス	マイアミ	夜
⑩	3	マイアミ	ロサンゼルス	午後

フライトを運用するスタッフは、低コストで乗員を割り当てたいと思っている。

基本的な問題は、１人の乗員が１度のフライトを終えたのちに彼が乗り込む次のフライトを決定することである。

この問題を理解するのに必要な基本概念は、ツアーの概念である。

ツアーの特徴を単純化すれば次のようである。

ツアーは１つから３つの接続されたフライトからなる。
ツアーは出発地で終わると、２単位のコストがかかる。
出発地以外の場所で終わる行き止まりツアーは３単位のコストがかかる。

以下はツアーの例である。

ツアー	コスト (単位)
17, 101, 23	2
220, 17, 101	3
410, 13	2

問題を解決するためにはすべてのツアーを数え上げることが必要である。

ツアーのリスト
１回フライト		コスト	２回フライト		コスト	３回フライト		コスト
1	101	3	11	101, 23	3	25	101, 23, 17	2
2	410	3	12	410, 13	2	26	101, 23, 11	3
3	220	3	13	410, 19	3	27	410, 19, 17	3
4	17	3	14	220, 17	3	28	410, 19, 11	2
5	7	3	15	220, 11	2	29	220, 17, 101	3
6	13	3	16	17, 101	3	30	220, 11, 410	3
7	11	3	17	7, 13	3	25	17,101, 23	2
8	19	3	18	7, 19	3	31	7, 19, 17	3
9	23	3	19	11,410	3	32	7, 19, 11	3
10	3	3	20	19, 17	2	33	11,417, 13	3
			21	19, 11	3	28	11,410, 19	2
			22	23, 17	3	34	19, 17,101	3
			23	23, 11	3	28	19, 11,410	2
			24	3, 23	2	25	23, 17,101	2
						35	23, 11,410	3
						36	2, 23, 17	3
						37	3, 23, 11	3

出発地点で終わる３回フライトにおいて、出発地を区別しないことにする。

だから番号が重複している。

以上で乗員は確保されているとして、
すべてのフライトを含むツアーの組み合わせの中で、
コストを最小にするもの（ツアー）を求める。

変数はツアーである。

目的関数(min)

Z= 3T1 + 3T2 + 3T3 + 3T4 + 3T5 + 3T6 + 3T7 + 3T8 + 3T9

+ 3T10+ 3T11+ 2T12+ 3T13+ 3T14+ 2T15+ 3T16+ 3T17+ 3T18

+ 3T19+ 2T20+ 3T21+ 3T22+ 3T23+ 2T24+ 2T25+ 3T26+ 2T27

+ 2T28+ 3T29+ 3T30+ 3T31+ 3T32+ 3T33+ 3T34+ 3T35+ 3T36

+ 3T37

制約条件式

F101) T1 +T11+T16+T25+T26+T29+T34=1

F410) T2 +T12+T13+T19+T27+T28+T30+T33+T35=1

F220) T3 +T14+T15+T29+T30=1

F17) T4 +T16+T20+T22+T25+T27+T29+T31+T34+T36=1

F7) T5 +T17+T18+T31+T32=1

F13) T6 +T12+T17+T33=1

F11) T7 +T15+T19+T21+T23+T26+T28+T30+T32+T33+T35+T37=1

F19) T8 +T13+T18+T20+T21+T27+T28+T31+T32+T34=1

F23) T9 +T11+T22+T23+T24+T25+T26+T35+T36+T37=1

F3) T10+T24+T36+T37=1

最適解

コスト=10

ﾂｱｰ	ﾌﾗｲﾄ	出発地		目的地	ｺｽﾄ
T17	F7	ﾛｻﾝｾﾞﾙｽ	--＞	ｼｶｺﾞ	3
	F13	ｼｶｺﾞ	--＞	ﾆｭｰﾖｰｸ	3
T24	F3	ﾏｲｱﾐ	--＞	ﾛｻﾝｾﾞﾙｽ	2
	F23	ﾛｻﾝｾﾞﾙｽ	--＞	ﾏｲｱﾐ	2
T28	F410	ﾆｭｰﾖｰｸ	--＞	ｼｶｺﾞ	2
	F19	ｼｶｺﾞ	--＞	ﾏｲｱﾐ
	F11	ﾏｲｱﾐ	--＞	ﾆｭｰﾖｰｸ
T29	F220	ﾆｭｰﾖｰｸ	--＞	ﾏｲｱﾐ	3
	F17	ﾏｲｱﾐ	--＞	ｼｶｺﾞ
	F101	ｼｶｺﾞ	--＞	ﾛｻﾝｾﾞﾙｽ

最小値は 10 です
0 でない変数の値:
x[17] = 1
x[24] = 1
x[28] = 1
x[29] = 1

Python による結果

# 4-063分割とパターン選択問題
from mypulp import *
#
model = Model("4064")
#
T1 = model.addVar(vtype="C",name="T1")
T2 = model.addVar(vtype="C",name="T2")
T3 = model.addVar(vtype="C",name="T3")
T4 = model.addVar(vtype="C",name="T4")
T5 = model.addVar(vtype="C",name="T5")
T6 = model.addVar(vtype="C",name="T6")
T7 = model.addVar(vtype="C",name="T7")
T8 = model.addVar(vtype="C",name="T8")
T9 = model.addVar(vtype="C",name="T9")
T10 = model.addVar(vtype="C",name="T10")
T11 = model.addVar(vtype="C",name="T11")
T12 = model.addVar(vtype="C",name="T12")
T13 = model.addVar(vtype="C",name="T13")
T14 = model.addVar(vtype="C",name="T14")
T15 = model.addVar(vtype="C",name="T15")
T16 = model.addVar(vtype="C",name="T16")
T17 = model.addVar(vtype="C",name="T17")
T18 = model.addVar(vtype="C",name="T18")
T19 = model.addVar(vtype="C",name="T19")
T20 = model.addVar(vtype="C",name="T20")
T21 = model.addVar(vtype="C",name="T21")
T22 = model.addVar(vtype="C",name="T22")
T23 = model.addVar(vtype="C",name="T23")
T24 = model.addVar(vtype="C",name="T24")
T25 = model.addVar(vtype="C",name="T25")
T26 = model.addVar(vtype="C",name="T26")
T27 = model.addVar(vtype="C",name="T27")
T28 = model.addVar(vtype="C",name="T28")
T29 = model.addVar(vtype="C",name="T29")
T30 = model.addVar(vtype="C",name="T30")
T31 = model.addVar(vtype="C",name="T31")
T32 = model.addVar(vtype="C",name="T32")
T33 = model.addVar(vtype="C",name="T33")
T34 = model.addVar(vtype="C",name="T34")
T35 = model.addVar(vtype="C",name="T35")
T36 = model.addVar(vtype="C",name="T36")
T37 = model.addVar(vtype="C",name="T37")
model.update()
#
model.addConstr(T1+T11+T16+T25+T26+T29+T34 == 1)
model.addConstr(T2+T12+T13+T19+T27+T28+T30+T33+T35 == 1)
model.addConstr(T3+T14+T15+T29+T30 == 1)
model.addConstr(T4+T16+T20+T22+T25+T27+T29+T31+T34+T36 == 1)
model.addConstr(T5+T17+T18+T31+T32 == 1)
model.addConstr(T6+T12+T17+T33 == 1)
model.addConstr(T7+T15+T19+T21+T23+T26+T28+T30+T32+T33+T35+T37 == 1)
model.addConstr(T8+T13+T18+T20+T21+T27+T28+T31+T32+T34 == 1)
model.addConstr(T9+T11+T22+T23+T24+T25+T26+T35+T36+T37 == 1)
model.addConstr(T10+T24+T36+T37 == 1)
#
model.setObjective(
    3*T1+3*T2+3*T3+3*T4+3*T5+3*T6+3*T7+3*T8+3*T9+3*T10+
    3*T11+2*T12+3*T13+3*T14+2*T15+3*T16+3*T17+3*T18+3*T19+2*T20+
    3*T21+3*T22+3*T23+2*T24+2*T25+3*T26+2*T27+2*T28+3*T29+3*T30+
    3*T31+3*T32+3*T33+3*T34+3*T35+3*T36+3*T37, GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        if v.X>0:
            print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#
最適値= 10.0
主要変数=
      Var. Name:        X ,     被約費用
            T17:      1.0 ,      0.0
            T24:      1.0 ,      0.0
            T28:      1.0 ,      0.0
            T29:      1.0 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
            c_1:     -0.0 ,  2.0
            c_2:     -0.0 ,  2.0
            c_3:     -0.0 ,  1.0
            c_4:     -0.0 ,  0.0
            c_5:     -0.0 ,  3.0
            c_6:     -0.0 ,  0.0
            c_7:     -0.0 ,  0.0
            c_8:     -0.0 ,  0.0
            c_9:     -0.0 ,  0.0
           c_10:     -0.0 ,  2.0

７．ネットワークまたは輸送問題

(07.1)ネットワーク型の特徴

次の図は、製品を配送するのに問屋を仲介にしている会社の配送システムである。

この会社は A, B で表される２つの工場と、X, Y, Z で表される３つの倉庫と、

1, 2, 3, 4 で表される４つの販売地域を持っている。

各節点(ノード)の横の数字は、その節点(ノード)における製品の出荷可能量を表す。

例として、工場 A は９単位の製品が出荷可能である。販売地域３では、４単位を搬入する必要がある。

流枝(アーク)上の数字は、その流枝(アーク)を用いて搬出する製品１単位当たりの費用である。

例として、工場 A の９単位のうち、５単位を倉庫 Y に搬送する場合、コストは５×２＝１０だけかかる。

問題は、すべての販売地域の需要を満たし、総費用を最小にするような各流枝(アーク)上の搬送量を決定することである。

流枝変数

AX	AY	BX	BY	BZ	X1	X2	Y1	Y2	Y3	Z2	Z3	Z4
X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13

制約式

AX+AY=9

BX+BY+BZ=8

-AX-BX+X1+X2=0

-AY-BY+Y1+Y2+Y3=0

-BZ+Z2+Z3+Z4=0

-X1-Y1=-3

-X2-Y2-Z2=-5

-Y3-Z3=-4

-Z4=-5

目的関数

AX+2AY+3BX+BY+2BZ+5X1+7X2+9Y1+6Y2+7Y3+8Z2+7Z3+4Z4=Z (MIN)

最適解


タブローシンプレックス法
          X1           8.0000        0.0000
          X2           1.0000        0.0000
          X3           0.0000        3.0000
          X4           3.0000        0.0000
          X5           5.0000        0.0000
          X6           3.0000        0.0000
          X7           5.0000        0.0000
          X8           0.0000        5.0000
          X9           0.0000        0.0000
         X10           4.0000        0.0000
         X11           0.0000   999993.0000
         X12           0.0000        1.0000
         X13           5.0000        0.0000

  *objective function *
     Z           121.0000

変数		値
X1	AX	8
X2	AY	1
X3	BX
X4	BY	3
X5	BZ	5
X6	X1	3
X7	X2	5
X8	Y1
X9	Y2
X10	Y3	4
X11	Z2
X12	Z3
X13	Z4	5

Z	101	121

Python による結果

# 4-071ネットワーク型の特徴
from mypulp import *
#
model = Model("4071")
#
AX = model.addVar(vtype="C",name="AX")
AY = model.addVar(vtype="C",name="AY")
BX = model.addVar(vtype="C",name="BX")
BY = model.addVar(vtype="C",name="BY")
BZ = model.addVar(vtype="C",name="BZ")
X1 = model.addVar(vtype="C",name="X1")
X2 = model.addVar(vtype="C",name="X2")
Y1 = model.addVar(vtype="C",name="Y1")
Y2 = model.addVar(vtype="C",name="Y2")
Y3 = model.addVar(vtype="C",name="Y3")
Z2 = model.addVar(vtype="C",name="Z2")
Z3 = model.addVar(vtype="C",name="Z3")
Z4 = model.addVar(vtype="C",name="Z4")
model.update()
#
model.addConstr(AX+AY == 9)
model.addConstr(BX+BY+BZ == 8)
model.addConstr(-AX-BX+X1+X2 == 0)
model.addConstr(-AY-BY+Y1+Y2+Y3 == 0)
model.addConstr(-BZ+Z2+Z3+Z4 == 0)
model.addConstr(-X1-Y1 == -3)
model.addConstr(-X2-Y2-Z2 == -5)
model.addConstr(-Y3-Z3 == -4)
model.addConstr(-Z4 == -5)
#
model.setObjective(
    AX+2*AY+3*BX+BY+2*BZ+5*X1+7*X2+9*Y1+6*Y2+7*Y3+8*Z2+7*Z3+4*Z4, GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        if v.X>0:
            print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#
最適値= 121.0
主要変数=
      Var. Name:        X ,     被約費用
             AX:      8.0 ,      0.0
             AY:      1.0 ,      0.0
             BY:      3.0 ,      0.0
             BZ:      5.0 ,      0.0
             X1:      3.0 ,      0.0
             X2:      5.0 ,      0.0
             Y3:      4.0 ,      0.0
             Z4:      5.0 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
            c_1:     -0.0 ,  3.0
            c_2:     -0.0 ,  2.0
            c_3:     -0.0 ,  2.0
            c_4:     -0.0 ,  1.0
            c_5:     -0.0 ,  0.0
            c_6:     -0.0 , -3.0
            c_7:     -0.0 , -5.0
            c_8:     -0.0 , -6.0
            c_9:     -0.0 , -4.0

(07.3)PERT(最長経路問題)

PERT/CPM は大きなプロジェクトの進行を監督するための手法である。

計画通りプロジェクトが終了するためには、必ず時間通り完了しなければならない仕事の集合（クリティカルパス）を決める必要がある。

次の問題、家を建てるというプロジェクト、を考える。

	活動	略記号	活動所要時間	先行活動	ノード	イベント
					A	地下室を掘り始める時期
1	基礎地盤の掘削	DIG	3	-
					B	地下室掘り完成
2	基礎コンクリート打ち込み	FOUND	4	DIG
					C	土台の完成
3	基礎床コンクリート打ち	POURB	2	FOUND
4	床梁の据え付け	JOISTS	3	FOUND
					D	床梁の完成
5	壁の据え付け	WALLS	5	FOUND
					E	壁の完成
6	たるきの取り付け	RAFTERS	3	WALLS, POURB
					G	たるきの取り付けの完成
7	床板張り	FLOOR	4	JOIST
					F	床板張りの完成
8	内装下地	ROUGH	6	FLOOR
9	屋根張り	ROOF	7	RAFTERS
					H	屋根の完成
10	内装仕上げ	FINISH	5	ROUGH, ROOF
11	造園	SCAPE	2	POURB, WALLS
					I	屋根及び内装の完成

定式化ー１

問題は、PERT における最長経路を見つけること、である。

流枝変数

DIG	FOUND	POURB	JOISTS	WALLS	RAFTERS	FLOOR	ROUGH	ROOF	FINISH	SCAPE

制約式は以下の条件のもとに作成する。

DIG は必ずクリティカルパス上にある。
先行作業の１つがクリティカルパス上にある時のみ、その仕事がクリティカルパス上にある可能性がある。ある仕事がクリティカルパス上にあるとき、その後続作業のうちただ１つはクリティカルパス上にある。
SCAPE, FINISH のうちどちらかはクリティカルパス上にある。

制約式

-DIG=-1

-FOUND+DIG=0

-JOISTS-POUR-WALLS+FOUND=0

-FLOOR+JOISTS=0

-RAFTERS-SCAPE+POURB+WALLS=0

-ROUGH+FLOOR=0

-ROOF+RAFTERS=0

-FINISH+ROUGH+ROOF=0

FINISH+SCAPE=1

目的関数

3DIG+4FOUND+2POURB+3JOISTS+5WALLS+3RAFTERS+4FLOOR+6ROUGH+

7ROOF+5FINISH+2SCAPE=Z (MAX)

最適解

DIG	FOUND	POURB	JOISTS	WALLS	RAFTERS	FLOOR	ROUGH	ROOF	FINISH	SCAPE
1	1	0	0	1	1	0	0	1	1	0

Python による結果

# 4-073PERT（最長経路問題）定式化1
from mypulp import *
#
model = Model("4071")
#
DIG     = model.addVar(vtype="C",name="DIG")
FOUND   = model.addVar(vtype="C",name="FOUND")
POURB   = model.addVar(vtype="C",name="POURB")
JOISTS  = model.addVar(vtype="C",name="JOISTS")
WALLS   = model.addVar(vtype="C",name="WALLS")
RAFTERS = model.addVar(vtype="C",name="RAFTERS")
FLOOR   = model.addVar(vtype="C",name="FLOOR")
ROUGH   = model.addVar(vtype="C",name="ROUGH")
ROOF    = model.addVar(vtype="C",name="ROOF")
FINISH  = model.addVar(vtype="C",name="FINISH")
SCAPE   = model.addVar(vtype="C",name="SCAPE")
#
model.update()
#
model.addConstr(-DIG == -1)
model.addConstr(-FOUND+DIG == 0)
model.addConstr(-JOISTS-POURB-WALLS+FOUND == 0)
model.addConstr(-FLOOR+JOISTS == 0)
model.addConstr(-RAFTERS-SCAPE+POURB+WALLS == 0)
model.addConstr(-ROUGH+FLOOR == 0)
model.addConstr(-ROOF+RAFTERS == 0)
model.addConstr(-FINISH+ROUGH+ROOF == 0)
model.addConstr(FINISH+SCAPE == 1)
#
model.setObjective(
    3*DIG+4*FOUND+2*POURB+3*JOISTS+5*WALLS+3*RAFTERS+4*FLOOR+6*ROUGH+
    7*ROOF+5*FINISH+2*SCAPE, GRB.MAXIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        if v.X>0:
            print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#
最適値= 27.0
主要変数=
      Var. Name:        X ,     被約費用
            DIG:      1.0 ,      0.0
         FINISH:      1.0 ,      0.0
          FOUND:      1.0 ,      0.0
        RAFTERS:      1.0 ,      0.0
           ROOF:      1.0 ,      0.0
          WALLS:      1.0 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
            c_1:     -0.0 , -22.0
            c_2:     -0.0 , -19.0
            c_3:     -0.0 , -15.0
            c_4:     -0.0 , -12.0
            c_5:     -0.0 , -10.0
            c_6:     -0.0 , -6.0
            c_7:     -0.0 , -7.0
            c_8:     -0.0 , -0.0
            c_9:     -0.0 ,  5.0

注目点）ネットワークの枝の長さを景色の美しさと考えれば、

以上の定式化は途中の経路が最も景色が良い。

定式化ー２

この定式化の目的はプロジェクトにかかる時間を最小にすることである。

流枝変数

A	B	C	D	E	F	G	H	I

制約式

① B-A≧3

② C-B≧4

③ E-C≧2

④ D-C≧3

⑤ E-C≧5

⑥ F-D≧4

⑦ G-E≧3

⑧ H-F≧6

⑨ H-G≧7

⑩ I-H≧5

⑪ I-E≧2

目的関数

I-A=Z (MIN)

最適解

Python による結果

# 4-073PERT（最長経路問題）定式化2
from mypulp import *
#
model = Model("4073")
#
A = model.addVar(vtype="C",name="A")
B = model.addVar(vtype="C",name="B")
C = model.addVar(vtype="C",name="C")
D = model.addVar(vtype="C",name="D")
E = model.addVar(vtype="C",name="E")
F = model.addVar(vtype="C",name="F")
G = model.addVar(vtype="C",name="G")
H = model.addVar(vtype="C",name="H")
I = model.addVar(vtype="C",name="I")
#
model.update()
#
model.addConstr(B-A >= 3)
model.addConstr(C-B >= 4)
model.addConstr(E-C >= 2)
model.addConstr(D-C >= 3)
model.addConstr(E-C >= 5)
model.addConstr(F-D >= 4)
model.addConstr(G-E >= 3)
model.addConstr(H-F >= 6)
model.addConstr(H-G >= 7)
model.addConstr(I-H >= 5)
model.addConstr(I-E >= 2)
#
model.setObjective(I-A, GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        if v.X>0:
            print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#
最適値= 27.0
主要変数=
      Var. Name:        X ,     被約費用
              B:      3.0 ,      0.0
              C:      7.0 ,      0.0
              D:     12.0 ,      0.0
              E:     12.0 ,      0.0
              F:     16.0 ,      0.0
              G:     15.0 ,      0.0
              H:     22.0 ,      0.0
              I:     27.0 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
            c_1:     -0.0 ,  1.0
            c_2:     -0.0 ,  1.0
            c_3:     -3.0 ,  0.0
            c_4:     -2.0 ,  0.0
            c_5:     -0.0 ,  1.0
            c_6:     -0.0 ,  0.0
            c_7:     -0.0 ,  1.0
            c_8:     -0.0 , -0.0
            c_9:     -0.0 ,  1.0
           c_10:     -0.0 ,  1.0
           c_11:    -13.0 ,  0.0

クリティカルパスは

1	B-A	3	1
2	C-B	4	1
3	E-C	2	0
4	D-C	3	0
5	E-C	5	1
6	F-D	4	0
7	G-E	3	1
8	H-F	6	0
9	H-G	7	1
10	I-H	5	1
11	I-E	2	0

プロジェクトにかかる時間（目的関数値）は 27 である。

流枝変数

A	B	C	D	E	F	G	H	I
0	3	7		12		15	22	27

書籍解は以下のようであるが、クリティカルパス上をたどれば一致している。

A = 0

B = 3

C = 7

D = 10

E = 12

F = 14

G = 15

H = 22

I = 27

(07.6)パスによる定式化

(07.1) の問題では、ネットワーク全体でとるパスで解を考えることが自然である。

１３個のパスがある。

A-->X-->1
A-->X-->2
A-->Y-->1
A-->Y-->2
A-->Y-->3
B-->X-->1
B-->X-->2
B-->Y-->1
B-->Y-->2
B-->Y-->3
B-->Z-->2
B-->Z-->3
B-->Z-->4

制約条件式

AX1+AX2+AY1+AY2+AY3=9

BX1+BX2+BY1+BY2+BY3+BZ2+BZ3+BZ4=8

AX1+AY1+BX1+BY1=3

AX2+AY2+BY2+BZ2=5

AY3+BY3+BZ3=4

BZ4=5

目的関数

6AX1+8AX2+11AY1+8AY2+9AY3+8BX1+10BX2+10BY1+7BY2+8BY3+10BZ2+9BZ3+6BZ4=Z (MIN)

最小値は 121 です
0 でない変数の値:
x[1] = 3
x[2] = 2
x[5] = 4
x[9] = 3
x[13] = 5

流枝変数

AX1	AX2	AY1	AY2	AY3	BX1	BX2	BY1	BY2	BY3	BZ2	BZ3	BZ4
X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13

パスによる定式化
変数	値	パス
X1	3	AX1
X2	2	AX2
X3		AY1
X4		AY2
X5	4	AY3
X6		BX1
X7		BX2
X8		BY1
X9	3	BY2
X10		BY3
X11		BZ2
X12		BZ3
X13	5	BZ4

Z	121

Python による結果

# 4-076パスによる定式化
from mypulp import *
#
model = Model("4071")
#
AX1 = model.addVar(vtype="C",name="AX1")
AX2 = model.addVar(vtype="C",name="AX2")
AY1 = model.addVar(vtype="C",name="AY1")
AY2 = model.addVar(vtype="C",name="AY2")
AY3 = model.addVar(vtype="C",name="AY3")
BX1 = model.addVar(vtype="C",name="BX1")
BX2 = model.addVar(vtype="C",name="BX2")
BY1 = model.addVar(vtype="C",name="BY1")
BY2 = model.addVar(vtype="C",name="BY2")
BY3 = model.addVar(vtype="C",name="BY3")
BZ2 = model.addVar(vtype="C",name="BZ2")
BZ3 = model.addVar(vtype="C",name="BZ3")
BZ4 = model.addVar(vtype="C",name="BZ4")
model.update()
#
model.addConstr(AX1+AX2+AY1+AY2+AY3 == 9)
model.addConstr(BX1+BX2+BY1+BY2+BY3+BZ2+BZ3+BZ4 == 8)
model.addConstr(AX1+AY1+BX1+BY1 == 3)
model.addConstr(AX2+AY2+BY2+BZ2 == 5)
model.addConstr(AY3+BY3+BZ3 == 4)
model.addConstr(BZ4 == 5)
#
model.setObjective(
    6*AX1+8*AX2+11*AY1+8*AY2+9*AY3+8*BX1+10*BX2+10*BY1+
    7*BY2+8*BY3+10*BZ2+9*BZ3+6*BZ4, GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        if v.X>0:
            print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#
最適値= 121.0
主要変数=
      Var. Name:        X ,     被約費用
            AX1:      3.0 ,      0.0
            AX2:      5.0 ,      0.0
            AY3:      1.0 ,      0.0
            BY3:      3.0 ,      0.0
            BZ4:      5.0 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
            c_1:     -0.0 ,  1.0
            c_2:     -0.0 ,  0.0
            c_3:     -0.0 ,  5.0
            c_4:     -0.0 ,  7.0
            c_5:     -0.0 ,  8.0
            c_6:     -0.0 ,  6.0

(07.7)方向性のないネットワーク

あるネットワークは５都市間の電話網である。

各枝は、容量制限はあるが、方向性はない。

通話に必要なすべてのリンクを使用できる。

ある時点での呼び出しが次のようであると考える。

		(B) DNV	(C) CHI	(D) ATL	(E) MIA
(A)	SEA	10	20	38	33
(B)	DNV		42	48	23
(C)	CHI			90	36
(D)	ATL				26

呼び出し総数＝３６６

問題は、上記需要をどれだけ多く満たせるか、である。

都市間パス

都市間	パス
A-B	A-B	X1
	A-C-D-B	X2
A-C	A-C	X3
	A-B-D-C	X4
A-D	A-B-D	X5
	A-C-D	X6
A-E	A-B-D-E	X7
	A-C-D-E	X8
B-D	B-D	X9
	B-A-C-D	X10
B-C	B-D-C	X11
	B-A-C	X12
B-E	B-D-E	X13
	B-A-C-D-E	X14
C-D	C-D	X15
	C-A-B-D	X16
C-E	C-D-E	X17
	C-A-B-D-E	X18
D-E	D-E	X19

制約条件

容量による制約

A-B を含むパス

X1+X4+X5+X7+X10+X12+X14+X16+X18≦95

A-C を含むパス

X3+X6+X8+X10+X12+X14≦80

B-D を含むパス

X2+X4+X5+X7+X9+X11+X13+X16+X18≦200

C-D を含むパス

X2+X4+X6+X8+X10+X11+X14≦110

D-E を含むパス

X7+X8+X13+X14+X17+X18+X19≦105

需要による制約

A-B) X1+X2≦10

A-C) X3+X4≦20

A-D) X5+X6≦38

A-E) X7+X8≦33

B-C) X11+X12≦42

B-D) X9+X10≦48

B-E) X13+X14≦23

C-D) X15+X16≦90

C-E) X17+X18≦36

D-E) X19≦26

目的関数

X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13+X14+X15+X16+X17+X18+X19=Z (MAX)

最適解

最小値は -353 です
0 でない変数の値:
x[1] = 10
x[3] = 20
x[5] = 38
x[7] = 33
x[9] = 48
x[11] = 42
x[13] = 23
x[15] = 90
x[17] = 36
x[19] = 13

書籍解

都市間	パス
P1SEADNV	A-B	A-B	X1
P2SEADNV		A-C-D-B	X2
P1SEACHI	A-C	A-C	X3
P2SEACHI		A-B-D-C	X4
P1SEAATL	A-D	A-C-D	X5
P2SEAATL		A-B-D	X6
P1SEAMIA	A-E	A-C-D-E	X7
P2SEAMIA		A-B-D-E	X8
P1DNVCHI	B-C	B-A-C	X9
P2DNVCHI		B-D-C	X10
P1DNVATL	B-D	B-D	X11
P2DNVATL		B-A-C-D	X12
P1DNVMIA	B-E	B-D-E	X13
P2DNVMIA		B-A-C-D-E	X14
P1CHIATL	C-D	C-D	X15
P2CHIATL		C-A-B-D	X16
P1CHIMIA	C-E	C-D-E	X17
P2CHIMIA		C-A-B-D-E	X18
P1ATLMIA	D-E	D-E	X19

制約条件

容量による制約
1	P1SEADNV	+	P2SEACHI	+	P2SEAATL	+
	X1		X4		X6
	P2SEAMIA	+	P1DNVCHI	+	P2DNVATL	+
	X8		X9		X12
	P2DNVMIA	+	P2CHIATL	+	P2CHIMIA	≦	95
	X14		X16		X18
2	P2SEADNV	+	P1SEACHI	+	P1SEAATL	+
	X2		X3		X5
	P1SEAMIA	+	P1DNVCHI	+	P2DNVATL	+
	X7		X9		X11
	P2DNVMIA	+	P2CHIATL	+	P2CHIMIA	≦	80
	X14		X16		X18
3	P2SEADNV	+	P2SEACHI	+	P2SEAATL	+
	X2		X4		X6
	P2SEAMIA	+	P2DNVCHI	+	P1DNVATL	+
	X8		X10		X11
	P1DNVMIA	+	P2CHIATL	+	P2CHIMIA	≦	200
	X13		X16		X18
4	P2SEADNV	+	P2SEACHI	+	P1SEAATL	+
	X2		X4		X5
	P1SEAMIA	+	P2DNVCHI	+	P2DNVATL	+
	X7		X10		X12
	P2DNVMIA	+	P2CHIATL	+	P1CHIMIA	≦	110
	X14		X16		X17
5	P1SEAMIA	+	P2SEAMIA	+	P1DNVMIA	+
	X7		X8		X13
	P2DNVMIA	+	P1CHIMIA	+	P2CHIMIA	+
	X14		X17		X18
	P1ATLMIA					≦	105
	X19

需要による制約
P1SEADNV	+	P2SEADNV	≦	10
X1		X2
P1SEACHI	+	P2SEACHI	≦	20
X3		X4
P1SEAATL	+	P2SEAATL	≦	38
X5		X6
P1SEAMIA	+	P2SEAMIA	≦	33
X7		X8
P1DNVCHI	+	P2DNVCHI	≦	42
X9		X10
P1DNVATL	+	P2DNVATL	≦	48
X11		X12
P1DNVMIA	+	P2DNVMIA	≦	23
X13		X14
P1CHIATL	+	P2CHIATL	≦	90
X15		X16
P1CHIMIA	+	P2CHIMIA	≦	36
X17		X18
P1ATLMIA	≦	26
X19

容量による制約

A-B を含むパス

X1+X4+X6+X8+X9+X12+X14+X16+X18≦95

A-C を含むパス

X2+X3+X5+X7+X9+X11+X14+X16+X18≦80

B-D を含むパス

X2+X4+X6+X8+X10+X11+X13+X16+X18≦200

C-D を含むパス

X2+X4+X5+X7+X10+X12+X14+X16+X17≦110

D-E を含むパス

X7+X8+X13+X14+X17+X18+X19≦105

需要による制約

A-B) X1+X2≦10

A-C) X3+X4≦20

A-D) X5+X6≦38

A-E) X7+X8≦33

B-C) X11+X12≦42

B-D) X9+X10≦48

B-E) X13+X14≦23

C-D) X15+X16≦90

C-E) X17+X18≦36

D-E) X19≦26

目的関数

X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13+X14+X15+X16+X17+X18+X19=Z (MAX)

最適解

		Python	書籍
		353	322
1	P1SEADNV	10
2	P2SEADNV
3	P1SEACHI	20	20
4	P2SEACHI
5	P1SEAATL
6	P2SEAATL	38	38
7	P1SEAMIA
8	P2SEAMIA	20
9	P1DNVCHI	27	42
10	P2DNVCHI	15
11	P1DNVATL	48	48
12	P2DNVATL
13	P1DNVMIA	23	23
14	P2DNVMIA
15	P1CHIATL	90	75
16	P2CHIATL		15
17	P1CHIMIA	36	35
18	P2CHIMIA
19	P1ATLMIA	26	26

Python による結果

# 4-077方向性のないネットワーク
from mypulp import *
#
model = Model("4077")
#
# 都市間パス
P1SEADNV = model.addVar(vtype="C",name="P1SEADNV")
P2SEADNV = model.addVar(vtype="C",name="P2SEADNV")
P1SEACHI = model.addVar(vtype="C",name="P1SEACHI")
P2SEACHI = model.addVar(vtype="C",name="P2SEACHI")
P1SEAATL = model.addVar(vtype="C",name="P1SEAATL")
P2SEAATL = model.addVar(vtype="C",name="P2SEAATL")
P1SEAMIA = model.addVar(vtype="C",name="P1SEAMIA")
P2SEAMIA = model.addVar(vtype="C",name="P2SEAMIA")
P1DNVCHI = model.addVar(vtype="C",name="P1DNVCHI")
P2DNVCHI = model.addVar(vtype="C",name="P2DNVCHI")
P1DNVATL = model.addVar(vtype="C",name="P1DNVATL")
P2DNVATL = model.addVar(vtype="C",name="P2DNVATL")
P1DNVMIA = model.addVar(vtype="C",name="P1DNVMIA")
P2DNVMIA = model.addVar(vtype="C",name="P2DNVMIA")
P1CHIATL = model.addVar(vtype="C",name="P1CHIATL")
P2CHIATL = model.addVar(vtype="C",name="P2CHIATL")
P1CHIMIA = model.addVar(vtype="C",name="P1CHIMIA")
P2CHIMIA = model.addVar(vtype="C",name="P2CHIMIA")
P1ATLMIA = model.addVar(vtype="C",name="P1ATLMIA")
model.update()
# 容量による制約 (5)
model.addConstr(P1SEADNV+P2SEACHI+P2SEAATL+
                P2SEAMIA+P1DNVCHI+P2DNVATL+
                P2DNVMIA+P2CHIATL+P2CHIMIA <= 95)
model.addConstr(P2SEADNV+P1SEACHI+P1SEAATL+
                P1SEAMIA+P1DNVCHI+P2DNVATL+
                P2DNVMIA+P2CHIATL+P2CHIMIA <= 80)
model.addConstr(P2SEADNV+P2SEACHI+P2SEAATL+
                P2SEAMIA+P2DNVCHI+P1DNVATL+
                P1DNVMIA+P2CHIATL+P2CHIMIA <= 200)
model.addConstr(P2SEADNV+P2SEACHI+P1SEAATL+
                P1SEAMIA+P2DNVCHI+P2DNVATL+
                P2DNVMIA+P2CHIATL+P1CHIMIA <= 110)
model.addConstr(P1SEAMIA+P2SEAMIA+P1DNVMIA+
                P2DNVMIA+P1CHIMIA+P2CHIMIA+
                P1ATLMIA <= 105)
# 需要による制約 (10)
model.addConstr(P1SEADNV+P2SEADNV <= 10)
model.addConstr(P1SEACHI+P2SEACHI <= 20)
model.addConstr(P1SEAATL+P2SEAATL <= 38)
model.addConstr(P1SEAMIA+P2SEAMIA <= 33)
model.addConstr(P1DNVCHI+P2DNVCHI <= 42)
model.addConstr(P1DNVATL+P2DNVATL <= 48)
model.addConstr(P1DNVMIA+P2DNVMIA <= 23)
model.addConstr(P1CHIATL+P2CHIATL <= 90)
model.addConstr(P1CHIMIA+P2CHIMIA <= 36)
model.addConstr(P1ATLMIA <= 26)
#
model.setObjective(
    P1SEADNV+P2SEADNV+P1SEACHI+P2SEACHI+P1SEAATL+
    P2SEAATL+P1SEAMIA+P2SEAMIA+P1DNVCHI+P2DNVCHI+
    P1DNVATL+P2DNVATL+P1DNVMIA+P2DNVMIA+P1CHIATL+
    P2CHIATL+P1CHIMIA+P2CHIMIA+P1ATLMIA, GRB.MAXIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        if v.X>0:
            print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#

最適値= 353.0
主要変数=
      Var. Name:        X ,     被約費用
       P1ATLMIA:     26.0 ,      0.0
       P1CHIATL:     90.0 ,      0.0
       P1CHIMIA:     36.0 ,      0.0
       P1DNVATL:     48.0 ,      0.0
       P1DNVCHI:     27.0 ,      0.0
       P1DNVMIA:     23.0 ,      0.0
       P1SEACHI:     20.0 ,      0.0
       P1SEADNV:     10.0 ,      0.0
       P2DNVCHI:     15.0 ,      0.0
       P2SEAATL:     38.0 ,      0.0
       P2SEAMIA:     20.0 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
            c_1:     -0.0 , -0.0
            c_2:     33.0 , -0.0
            c_3:     56.0 , -0.0
            c_4:     59.0 , -0.0
            c_5:     -0.0 ,  1.0
            c_6:     -0.0 ,  1.0
            c_7:     -0.0 ,  1.0
            c_8:     -0.0 ,  1.0
            c_9:     13.0 , -0.0
           c_10:     -0.0 ,  1.0
           c_11:     -0.0 ,  1.0
           c_12:     -0.0 , -0.0
           c_13:     -0.0 ,  1.0
           c_14:     -0.0 , -0.0
           c_15:     -0.0 , -0.0

１５．統計的推定への応用（回帰分析）

(15.2)最小絶対偏差（回帰分析）

誤差の絶対値の合計を最小にするように回帰係数を推定する。

記号の定義

n=オブザベーションの数（観測値数）

d_i=オブザベーション i の従属変数の値(i=1,2,・・・,n)

k=説明変数の数

e_ij=オブザベーション iにおける j 番目の従属変数の値 (i=1,2,・・・,n, j=1,2,・・・,k)

x_j=説明変数 j の回帰係数

w_i=オブザベーション i の観測値と推定値の誤差

問題定義式

MIN |w₁|+|w₂|+|w₃|+・・・+|w_n|

変数定義の変更

w_i=u_i-v_i

u_i,v_i≧0

問題の書き換え

MIN |u₁|+|v₁|+|u₂|+|v₂|+・・・ +|u_n|+|v_n|

e₀+e_i1x₁+e_i2x₂+・・・ +e_ikx_k+u_i-v_i=d_i

(i=1,2,・・・,n)

例題

d_i	e_i1	e_i2
2	1	1
3	1	2
4	1	4
5	1	6
8	1	7

目的関数

Z=U1+V1+U2+V2+U3+V3+U4+V4+U5+V5

制約条件式

U1-V1+X0+X1=2

U2-V2+X0+2X1=3

U3-V3+X0+4X1=4

U4-V4+X0+6X1=5

U5-V5+X0+7X1=8

解答

最小値は 2.66667 です

0 でない変数の値:

x[3] = 0.333333

x[8] = 0.333333

x[9] = 2

x[11] = 1.33333

x[12] = 0.666667

ここで、

x[11] と x[12] の値は回帰係数を表すから、単回帰式は

d_i=1.33333+0.666667e_i2

である。

Python による結果

以下にPython による結果を示す。


# 4-152最小絶対偏差（回帰分析）
from mypulp import *
#
XY = [
    [2,1],
    [3,2],
    [4,4],
    [5,6],
    [8,7]
]
n = len(XY)
L = [(j+1) for j in range(n)]
#print(L)
#
model = Model("4152")
#
x01 = model.addVar(vtype="C",name="x01")
x02 = model.addVar(vtype="C",name="x02")
x03 = model.addVar(vtype="C",name="x03")
x04 = model.addVar(vtype="C",name="x04")
x05 = model.addVar(vtype="C",name="x05")
x06 = model.addVar(vtype="C",name="x06")
x07 = model.addVar(vtype="C",name="x07")
x08 = model.addVar(vtype="C",name="x08")
x09 = model.addVar(vtype="C",name="x09")
x10 = model.addVar(vtype="C",name="x10")
x11 = model.addVar(vtype="C",name="x11")
x12 = model.addVar(vtype="C",name="x12")
model.update()
#
model.addConstr(x01-x02+x11+1*x12 == 2, name="C01")
model.addConstr(x03-x04+x11+2*x12 == 3, name="C02")
model.addConstr(x05-x06+x11+4*x12 == 4, name="C03")
model.addConstr(x07-x08+x11+6*x12 == 5, name="C04")
model.addConstr(x09-x10+x11+7*x12 == 8, name="C05")
#
model.setObjective(x01+x02+x03+x04+x05+x06+x07+x08+x09+x10, GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        #if v.X>0:
        print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#
最適値= 2.6666666599999997
主要変数=
      Var. Name:        X ,     被約費用
            x01:      0.0 , 1.3333333
            x02:      0.0 , 0.66666667
            x03: 0.33333333 ,      0.0
            x04:      0.0 ,      2.0
            x05:      0.0 , 1.6666667
            x06:      0.0 , 0.33333333
            x07:      0.0 ,      2.0
            x08: 0.33333333 ,      0.0
            x09:      2.0 ,      0.0
            x10:      0.0 ,      2.0
            x11: 1.3333333 ,      0.0
            x12: 0.66666667 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
            C01:     -0.0 , -0.33333333
            C02:     -0.0 ,  1.0
            C03:     -0.0 , -0.66666667
            C04:     -0.0 , -1.0
            C05:     -0.0 ,  1.0

Python による結果

ここで、絶対値の計算方法の別の方式を示す。

（線形計画法の問題番号 3-1.3 を参照）

# 4-152最小絶対偏差（回帰分析）2
from mypulp import *
#
#XY = [
#    [2,1],
#    [3,2],
#    [4,4],
#    [5,6],
#    [8,7]
#]
XY = [
    [1,2],
    [2,3],
    [4,4],
    [6,5],
    [7,8]
]
n = len(XY)
L = [(j+1) for j in range(n)]
#print(L)
#
model = Model("4152")
#
x = {}
for i in L:
    x[i] = model.addVar(vtype="C", name="x({0})".format(i))
a = model.addVar(vtype="C",name="xa")
b = model.addVar(vtype="C",name="xb")
model.update()
#
for i in L:
    model.addConstr(x[i]+XY[i-1][0]*a+b >= XY[i-1][1], name="C({0})".format(i))
    model.addConstr(-x[i]+XY[i-1][0]*a+b <= XY[i-1][1], name="c({0})".format(i))
#
model.setObjective(quicksum(x[i] for i in L), GRB.MINIMIZE)
#
model.optimize()
#
if model.Status == GRB.Status.OPTIMAL:
    opval=model.ObjVal
    print("最適値=",opval)
    print("主要変数=")
    print ("{0:>15}: {1:>8} , {2:>8}".format("Var. Name", "X", "被約費用"))
    # .VarName,        変数名
    # .X,              値
    # .RC Reduced Cost 被約費用
    for v in model.getVars():
        #if v.X>0:
        print("{0:>15}: {1:>8} , {2:>8}".format(v.VarName,v.X,v.RC))
    #
    print("双対変数=")
    print ("{0:>15}: {1:>8} , {2:>4}".format("Const. Name", "Slack", "Dual"))
    # .ConstrName,        変数名
    # .XSlack              余裕値
    # .Pi    Shadow Price 潜在価格 双対変数
    for c in model.getConstrs():
        print ("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
        #print(c.ConstrName, c.Slack, c.Pi)
#

最適値= 2.6666666599999997
主要変数=
      Var. Name:        X ,     被約費用
           x(1):      0.0 , 0.66666667
           x(2): 0.33333333 ,      0.0
           x(3):      0.0 , 0.33333333
           x(4): 0.33333333 ,      0.0
           x(5):      2.0 ,      0.0
             xa: 0.66666667 ,      0.0
             xb: 1.3333333 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
           C(1):     -0.0 ,  0.0
           c(1):     -0.0 , -0.33333333
           C(2):     -0.0 ,  1.0
           c(2): 0.6666667 ,  0.0
           C(3):     -0.0 ,  0.0
           c(3):     -0.0 , -0.66666667
           C(4): -0.6666667000000004 ,  0.0
           c(4):     -0.0 , -1.0
           C(5):     -0.0 ,  1.0
           c(5):      4.0 ,  0.0

ページ先頭

X1	X2	X3	X4	X5	X6	X7	X8
X1	X2	X3	X4	X5	X6	X7	X8
A1	A2	A3	A4	A5	A6	A7	A8	A9
X9	X10	X11	X12	X13	X14	X15	X16	X17
B0	B1	B2	B3	B4	B5	B6	B7	B8	B9
X18	X19	X20	X21	X22	X23	X24	X25	X26	X27
C0	C1	C2	C3	C4	C5	C6	C7	C8	C9
X28	X29	X30	X31	X32	X33	X34	X35	X36	X37
D0	D1	D2	D3	D4	D5	D6	D7	D8	D9
X38	X39	X40	X41	X42	X43	X44	X45	X46	X47
E0	E1	E2	E3	E4
X48	X49	X50	X51	X52
T1	T2	T3	W1	W2	W3
X53	X54	X55	X56	X57	X58

変数		値
X1	AX	8
X2	AY	1
X3	BX
X4	BY	3
X5	BZ	5
X6	X1	3
X7	X2	5
X8	Y1
X9	Y2
X10	Y3	4
X11	Z2
X12	Z3
X13	Z4	5

Z	101	121

1	B-A	3	1
2	C-B	4	1
3	E-C	2	0
4	D-C	3	0
5	E-C	5	1
6	F-D	4	0
7	G-E	3	1
8	H-F	6	0
9	H-G	7	1
10	I-H	5	1
11	I-E	2	0

変数	値	パス
X1	3	AX1
X2	2	AX2
X3		AY1
X4		AY2
X5	4	AY3
X6		BX1
X7		BX2
X8		BY1
X9	3	BY2
X10		BY3
X11		BZ2
X12		BZ3
X13	5	BZ4

Z	121

X1	X2	X3	X4	X5	X6	X7	X8
X1	X2	X3	X4	X5	X6	X7	X8
A1	A2	A3	A4	A5	A6	A7	A8	A9
X9	X10	X11	X12	X13	X14	X15	X16	X17
B0	B1	B2	B3	B4	B5	B6	B7	B8	B9
X18	X19	X20	X21	X22	X23	X24	X25	X26	X27
C0	C1	C2	C3	C4	C5	C6	C7	C8	C9
X28	X29	X30	X31	X32	X33	X34	X35	X36	X37
D0	D1	D2	D3	D4	D5	D6	D7	D8	D9
X38	X39	X40	X41	X42	X43	X44	X45	X46	X47
E0	E1	E2	E3	E4
X48	X49	X50	X51	X52
T1	T2	T3	W1	W2	W3
X53	X54	X55	X56	X57	X58

変数		値
X1	AX	8
X2	AY	1
X3	BX
X4	BY	3
X5	BZ	5
X6	X1	3
X7	X2	5
X8	Y1
X9	Y2
X10	Y3	4
X11	Z2
X12	Z3
X13	Z4	5

Z	101	121

1	B-A	3	1
2	C-B	4	1
3	E-C	2	0
4	D-C	3	0
5	E-C	5	1
6	F-D	4	0
7	G-E	3	1
8	H-F	6	0
9	H-G	7	1
10	I-H	5	1
11	I-E	2	0

変数	値	パス
X1	3	AX1
X2	2	AX2
X3		AY1
X4		AY2
X5	4	AY3
X6		BX1
X7		BX2
X8		BY1
X9	3	BY2
X10		BY3
X11		BZ2
X12		BZ3
X13	5	BZ4

Z	121

『実践数理計画法』

ここの問題は上の書籍を参照した。 以下の資料では、計算実行のために LINDO は使用していない。 Pythonを使用した

ここの問題は上の書籍を参照した。
以下の資料では、計算実行のために LINDO は使用していない。
Pythonを使用した

X1	X2	X3	X4	X5	X6	X7	X8
X1	X2	X3	X4	X5	X6	X7	X8
A1	A2	A3	A4	A5	A6	A7	A8	A9
X9	X10	X11	X12	X13	X14	X15	X16	X17
B0	B1	B2	B3	B4	B5	B6	B7	B8	B9
X18	X19	X20	X21	X22	X23	X24	X25	X26	X27
C0	C1	C2	C3	C4	C5	C6	C7	C8	C9
X28	X29	X30	X31	X32	X33	X34	X35	X36	X37
D0	D1	D2	D3	D4	D5	D6	D7	D8	D9
X38	X39	X40	X41	X42	X43	X44	X45	X46	X47
E0	E1	E2	E3	E4
X48	X49	X50	X51	X52
T1	T2	T3	W1	W2	W3
X53	X54	X55	X56	X57	X58

変数		値
X1	AX	8
X2	AY	1
X3	BX
X4	BY	3
X5	BZ	5
X6	X1	3
X7	X2	5
X8	Y1
X9	Y2
X10	Y3	4
X11	Z2
X12	Z3
X13	Z4	5

Z	101	121

1	B-A	3	1
2	C-B	4	1
3	E-C	2	0
4	D-C	3	0
5	E-C	5	1
6	F-D	4	0
7	G-E	3	1
8	H-F	6	0
9	H-G	7	1
10	I-H	5	1
11	I-E	2	0

変数	値	パス
X1	3	AX1
X2	2	AX2
X3		AY1
X4		AY2
X5	4	AY3
X6		BX1
X7		BX2
X8		BY1
X9	3	BY2
X10		BY3
X11		BZ2
X12		BZ3
X13	5	BZ4

Z	121