線形計画法

門前パソコン学習所

2023-10-22

書籍	番号	最適化問題
3	1.1	生産計画問題
3	1.2	最短路問題
3	1.3	直線の当てはめ

問題の詳細は書籍を参照ください。ここでは表で示します。

ただし、問題1.3については詳細を示します。

(1.1)生産計画問題

工場 F の１日当たりの利益を最大にするには、３種類の製品をどれだけ生産したらよいだろうか。

		製品１単位作るのに必要な原料
原料	制限	P1	P2	P3
		X1	X2	X3
M1	24	1	1	2
M2	16	3	1	0
M3	12	0	2	1

売って得られる利益		2	3	2

制約条件式

1X1+1X2+2X3≦24

3X1+1X2+0X3≦16

0X1+2X2+1X3≦12

X1, X2, X3 ≧ 0

目的関数

Z=2X1+3X2+2X3

最適解

X1 = 4.8, X2 = 1.6, X3 = 8.8

Z = 32.0

Pythonによる結果

# 3-11生産計画問題
from mypulp import *
model = Model("model2A1")
X1 = model.addVar(vtype="C",name="X1")
X2 = model.addVar(vtype="C",name="X2")
X3 = model.addVar(vtype="C",name="X3")
model.update()
#
model.addConstr(1*X1+1*X2+2*X3 <= 24)
model.addConstr(3*X1+1*X2+0*X3 <= 16)
model.addConstr(0*X1+2*X2+1*X3 <= 12)
#
model.setObjective(2*X1+3*X2+2*X3,GRB.MAXIMIZE)
model.optimize()
#
opval=model.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in model.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 model.getConstrs():
    print("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
#
最適値= 32.0
主要変数=
X1 4.8
X2 1.6
X3 8.8
     Const.Name:    Slack , Dual
            c_1:     -0.0 ,  0.5
            c_2:     -0.0 ,  0.5
            c_3:     -0.0 ,  1.0

(1.2)最短路問題

　　　　　　　 X3 → X8 → B ――――――― D ―――――― F ／＼ ↑ ／／ ↑ ＼｜／／｜＼｜ X7↓ ／ X1↑／｜＼｜ X9↑ ／ X10↑ ／ X5↑｜ X4↓＼｜／／｜＼｜／／｜＼／ → A ――――――C ――――――― E X2 → X6 →

書籍解

AB=X1,AC=X2,BD=X3,BE=X4,CB=X5,CE=X6,DE=X7,DF=X8,ED=X9,EF=X10

制約条件式

-X1-X2 =-1

X1 -X3-X4+X5 = 0

X2+X3-X4 -X6 = 0

X2 -X5-X6 = 0

X3 -X7-X8+X9 = 0

X4+X6+X7 -X9-X10 = 0

X8 +X10 = 1

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

目的関数

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

最適解

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

X6 = 0.0, X7 = 0.0, X8 = 0.0, X9 = 0.0, X10= 1.0

Z = 14.0

Pythonによる結果

# 3-12最短路問題
from mypulp import *
model = Model("model2A1")
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")
X9 = model.addVar(vtype="C",name="X9")
X10 = model.addVar(vtype="C",name="X10")
model.update()
#
model.addConstr(-X1-X2 == -1)
model.addConstr(X1-X3-X4+X5 == 0)
model.addConstr(X2+X3-X4-X6 == 0)
model.addConstr(X2-X5-X6 == 0)
model.addConstr(X3-X7-X8+X9 == 0)
model.addConstr(X4+X6+X7-X9-X10 == 0)
model.addConstr(X8+X10 == 1)
#
model.setObjective(8*X1+4*X2+6*X3+5*X4+3*X5+9*X6+X7+7*X8+X9+2*X10,GRB.MINIMIZE)
model.optimize()
#
opval=model.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in model.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 model.getConstrs():
    print("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
#
最適値= 14.0
主要変数=
X10 1.0
X2 1.0
X4 1.0
X5 1.0
     Const.Name:    Slack , Dual
            c_1:     -0.0 , -8.0
            c_2:     -0.0 ,  0.0
            c_3:     -0.0 , -1.0
            c_4:     -0.0 , -3.0
            c_5:     -0.0 ,  3.0
            c_6:     -0.0 ,  4.0
            c_7:     -0.0 ,  6.0

独自解

下図は、地点 {a,b,c,d,e,f} からなる路線図である。

a から f へ移動するとき移動距離の合計を最小にするためにはどのような経路を通ればよいか。

変数対応

ab=X1,ac=X2,cb=X3,bd=X4,be=X5,ce=X6,de=X7,df=X8,ef=X9

(6) 　　　　　　　 X4 → ⓑ―――――――――→ⓓ ↗↑＼ ↑＼／｜＼｜＼ (7) X1 ↑／｜＼ (5) ｜＼X8 ↓ (8)／｜＼ X5 ↓ ｜＼／｜＼｜X7 ↑ ↘ → ⓐ＼ X3 ↑｜＼｜(1) ↗ⓕ→ ＼ (3) ｜＼｜／ X2 ↓＼｜＼｜／ (4) ＼｜＼｜／ X9 ↑ ↘｜ ↘｜／ (2) 　 ⓒ―――――――――→ⓔ X6 → (9)

制約条件式

-X1-X2=-1

X1+X3-X4-X5=0

X2-X3-X6=0

X4+X7-X8=0

X5+X6-X7-X9=0

X8+X9=1

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

目的関数

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

最適解

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

X6 = 0.0, X7 = 0.0, X8 = 0.0, X9 = 1.0

Z = 14.0

Pythonによる結果

# 3-12最短路問題2
from mypulp import *
model = Model("model2A1")
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")
X9 = model.addVar(vtype="C",name="X9")
model.update()
#
model.addConstr(-X1-X2 == -1)
model.addConstr(X1+X3-X4-X5 == 0)
model.addConstr(X2-X3-X6 == 0)
model.addConstr(X4+X7-X8 == 0)
model.addConstr(X5+X6-X7-X9 == 0)
model.addConstr(X8+X9 == 1)
#
model.setObjective(8*X1+4*X2+3*X3+6*X4+5*X5+9*X6+X7+7*X8+2*X9,GRB.MINIMIZE)
model.optimize()
#
opval=model.ObjVal
print("最適値=",opval)
print("主要変数=")
for v in model.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 model.getConstrs():
    print("{0:>15}: {1:>8} , {2:>4}".format(c.ConstrName,c.Slack,c.Pi))
#

最適値= 14.0
主要変数=
X2 1.0
X3 1.0
X5 1.0
X9 1.0
     Const.Name:    Slack , Dual
            c_1:     -0.0 , -7.0
            c_2:     -0.0 ,  0.0
            c_3:     -0.0 , -3.0
            c_4:     -0.0 ,  0.0
            c_5:     -0.0 ,  5.0
            c_6:     -0.0 ,  7.0

(1.3)直線の当てはめ

ある年の１０人分の学生の中間試験と期末試験のデータは

	１	２	３	４	５	６	７	８	９	１０		備考	合計
中間試験	93	66	99	96	93	75	60	27	51	66		X_i	726
期末試験	82	77	97	89	92	68	62	31	70	70		Y_i	738

となる。

中間試験(X)と期末試験(Y)の間に

Y=aX+b

の関係があるとすると、aとbはどのような値になるか（aとbが変数）

残差の定義 : Y_i-aX_i-b

残差の総和を最小にする問題。

残差の定義	ε_i	=	Y_i-aX_i-b
再定義	ξ_i	=	｜ε_i｜
目的関数	min		ξ₁+ξ₂+...+ξ₁₀
条件	ξ_i	≧	Y_i-a*X_i-b
	ξ_i	≧	-(Y_i-a*X_i-b)

変数の対応は、

ξ₁	ξ₂	ξ₃	ξ₄	ξ₅	ξ₆	ξ₇	ξ₈	ξ₉	ξ₁₀	a	b
X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12

Z=X1+X2+X3+x4+X5+X6+X7+X8+X9+X10

(1)		X1	≧	82	-	93X11	-	X12
		X1	+	93X11	+	X12	≧	82
(2)		X1	≧	-82	+	93X11	+	X12
	-	X1	+	93X11	+	X12	≦	82
(3)		X2	≧	77	-	66X11	-	X12
		X2	+	66X11	+	X12	≧	77
(4)		X2	≧	-77	+	66X11	+	X12
	-	X2	+	66X11	+	X12	≦	77
(5)		X3	≧	97	-	99X11	-	X12
		X3	+	99X11	+	X12	≧	97
(6)		X3	≧	-97	+	99X11	+	X12
	-	X3	+	99X11	+	X12	≦	97
(7)		X4	≧	89	-	96X11	-	X12
		X4	+	96X11	+	X12	≧	89
(8)		X4	≧	-89	+	96X11	+	X12
	-	X4	+	96X11	+	X12	≦	89
(9)		X5	≧	92	-	93X11	-	X12
		X5	+	93X11	+	X12	≧	92
(10)		X5	≧	-92	+	93X11	+	X12
	-	X5	+	93X11	+	X12	≦	92
(11)		X6	≧	68	-	75X11	-	X12
		X6	+	75X11	+	X12	≧	68
(12)		X6	≧	-68	+	75X11	+	X12
	-	X6	+	75X11	+	X12	≦	68
(13)		X7	≧	62	-	60X11	-	X12
		X7	+	60X11	+	X12	≧	62
(14)		X7	≧	-62	+	60X11	+	X12
	-	X7	+	60X11	+	X12	≦	62
(15)		X8	≧	31	-	27X11	-	X12
		X8	+	27X11	+	X12	≧	31
(16)		X8	≧	-31	+	27X11	+	X12
	-	X8	+	27X11	+	X12	≦	31
(17)		X9	≧	70	-	51X11	-	X12
		X9	+	51X11	+	X12	≧	70
(18)		X9	≧	-70	+	51X11	+	X12
	-	X9	+	51X11	+	X12	≦	70
(19)		X10	≧	70	-	66X11	-	X12
		X10	+	66X11	+	X12	≧	70
(20)		X10	≧	-70	+	66X11	+	X12
	-	X10	+	66X11	+	X12	≦	70

制約条件式

X1+93X11+X12 ≧ 82

-X1+93X11+X12 ≦ 82

X2+66X11+X12 ≧ 77

-X2+93X11+X12 ≦ 77

X3+99X11+X12 ≧ 97

-X3+99X11+X12 ≦ 97

X4+96X11+X12 ≧ 89

-X4+96X11+X12 ≦ 89

X5+93X11+X12 ≧ 92

-X5+93X11+X12 ≦ 92

X6+75X11+X12 ≧ 68

-X6+75X11+X12 ≦ 68

X7+60X11+X12 ≧ 62

-X7+60X11+X12 ≦ 62

X8+27X11+X12 ≧ 31

-X8+27X11+X12 ≦ 31

X9+51X11+X12 ≧ 70

-X9+51X11+X12 ≦ 70

X10+66X11+X12 ≧ 70

-X10+66X11+X12 ≦ 70

目的関数

Z=X1+X2+X3+x4+X5+X6+X7+X8+X9+X10

最適解

X1 = 9.6154 0.0000

X2 = 9.6154 0.0000

X3 = 0.0000 0.0000

X4 = 5.3077 0.0000

X5 = 0.3846 0.0000

X6 = 7.4615 0.0000

X7 = 0.0000 0.0000

X8 = 1.3846 0.0000

X9 = 16.0769 0.0000

X10= 2.6154 0.0000

X11= 0.8974(a) 0.0000

X12= 8.1538(b) 0.0000

Z = 52.4615

Pythonによる結果

# 3-13直線のあてはめ
from mypulp import *
#
XY = [
    [93,82],
    [66,77],
    [99,97],
    [96,89],
    [93,92],
    [75,68],
    [60,62],
    [27,31],
    [51,70],
    [66,70]
]
n = len(XY)
L = [(j+1) for j in range(n)]
#print(L)
#
model = Model("313")
#
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)
#

最適値= 52.46153838
主要変数=
      Var. Name:        X ,     被約費用
           x(1): 9.6153846 ,      0.0
          x(10): 2.6153846 ,      0.0
           x(2): 9.6153846 ,      0.0
           x(4): 5.3076923 ,      0.0
           x(5): 0.38461538 ,      0.0
           x(6): 7.4615385 ,      0.0
           x(8): 1.3846154 ,      0.0
           x(9): 16.076923 ,      0.0
             xa: 0.8974359 ,      0.0
             xb: 8.1538462 ,      0.0
双対変数=
    Const. Name:    Slack , Dual
           C(1): -19.230770000000007 ,  0.0
           c(1):     -0.0 , -1.0
           C(2):     -0.0 ,  1.0
           c(2): 19.230769000000002 ,  0.0
           C(3):     -0.0 , 0.69230769
           c(3):     -0.0 , -0.30769231
           C(4): -10.615385000000003 ,  0.0
           c(4):     -0.0 , -1.0
           C(5):     -0.0 ,  1.0
           c(5): 0.7692310000000049 ,  0.0
           C(6): -14.923077000000006 ,  0.0
           c(6):     -0.0 , -1.0
           C(7):     -0.0 ,  0.0
           c(7):     -0.0 , -0.38461538
           C(8): -2.7692309999999978 ,  0.0
           c(8):     -0.0 , -1.0
           C(9):     -0.0 ,  1.0
           c(9): 32.153846 ,  0.0
          C(10):     -0.0 ,  1.0
          c(10): 5.230768999999995 ,  0.0

ページ先頭

『線形計画法（並木誠）』