运筹与决策（三）求解线性规划、运输问题和0-1整数规划问题
一、實驗目的及要求
1、分別用excel、matlab和lingo求解線性規劃、運輸問題和0-1整數規劃問題
2、撰寫實驗報告2
?
二、實驗設備（環境）及要求
Microsoft Excel2016、matlab2017、lingo17
?
三、實驗內容
線性規劃
①加載宏—規劃求解加載項
②根據分析題目填寫約束條件、目標函數
D2=B5
D3=C5
D4=B5+2*C5
F6= =2*B5+5*C5
③添加線性求解
④求解結果
?
- ?
max S=2x1+5x2
? ? ? ? ? x1 ≤4
? ? ? ? ? x2≤3
s.t.???? x1+ 2x2≤8
? ? ? ? ? ?x1≥0
? ? ? ? ? ?x2≥0
?
將目標函數轉化為求函數-S的最小值,根據目標函數和約束條件，可以得出目標函數系數矩陣f=[2;5]，不等式約束系數矩陣A =[1 ?0;0? 1;1? 2 ]，不等式約束常向量b=[4; 3; 8], 調用MATLAB中lingprog函數求出-S的最小值，其相反數就是MaxS，如下圖所示:
結果:
>> f=[2;5];
A =[1? 0;0? 1;1? 2 ];
b=[4; 3; 8];
[x,fmin]=linprog(-f,A,b)
?
Optimal solution found.
?
?
x =
?
??? 2.0000
??? 3.0000
?
?
fmin =
?
?? -19
則MaxS=19
?
?
代碼:
max=2*X1+5*X2;
X1<=4;
X2<=3;
X1+2*X2<=8;
結果:
Global optimal solution found.
? Objective value:????????????????????????????? 19.00000
? Infeasibilities:????????????????????????????? 0.000000
? Total solver iterations:???????????????????????????? 1
? Elapsed runtime seconds:????????????????????????? 0.53
?
? Model Class:??????????????????????????????????????? LP
?
? Total variables:????????????????????? 2
? Nonlinear variables:????????????????? 0
? Integer variables:??????????????????? 0
?
? Total constraints:????? ??????????????4
? Nonlinear constraints:??????????????? 0
?
? Total nonzeros:?????????????????????? 6
? Nonlinear nonzeros:?????????????????? 0
?
?
?
??????????????????????????????? Variable?????????? Value??????? Reduced Cost
???????????????????????????????? ?????X1??????? 2.000000??????????? 0.000000
????????????????????????????????????? X2??????? 3.000000??????????? 0.000000
?
???????????????????????????????????? Row??? Slack or Surplus????? Dual Price
?????????????????????????????????????? 1??????? 19.00000 ???????????1.000000
?????????????????????????????????????? 2??????? 2.000000??????????? 0.000000
?????????????????????????????????????? 3??????? 0.000000??????????? 1.000000
?????????????????????????????????????? 4??????? 0.000000??????????? 2.000000
?
?
運輸問題
?
Let xij = the number of truckloads to ship from cannery i to warehouse j
?????? (i = 1, 2, 3; j = 1, 2, 3, 4)
Minimize Cost = $464x11 + $513x12 + $654x13 + $867x14
????????????????????????? + $352x21 + $416x22+ $690x23 + $791x24
????????????????????????? + $995x31 + $682x32 + $388x33 + $685x34
subject to
?????? Cannery 1:????? x11 + x12 + x13 + x14 = 75
?????? Cannery 2:????? x21 + x22 + x23 + x24 = 125
?????? Cannery 3:????? x31 + x32 + x33 + x34 = 100
?????? Warehouse 1:? x11 + x21 + x31 = 80
?????? Warehouse 2:? x12 + x22 + x32 = 65
?????? Warehouse 3:? x13 + x23 + x33 = 70
?????? Warehouse 4:? x14 + x24 + x34 = 85
and?????????? xij ≥ 0 (i = 1, 2, 3;? j = 1, 2, 3, 4)
?
①輸入問題的數據，
- 根據分析題目填寫約束條件、目標函數
C15=C10+C11+C12
D15=D10+D11+D12
E15=E10+E11+E12
F15=F10+F11+F12
?
I10=C10+D10+E10+F10
I11=C11+D11+E11+F11
I12=C12+D12+E12+F12
?
I15=C3*C10+D3*D10+E3*E10+F3*F10+C4*C11+D4*D11+E4*E11+F4*F11+C5*C12+D5*D12+E5*E12+F5*F12
?
- 求解結果
?
?
?
函數Min Cost的值,根據目標函數和約束條件，可以得出目標函數系數矩陣f=[464 513 654 867 352 416 690 791 995 682 388 685]，不等式約束系數矩陣A=[0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 1]，不等式約束常向量b=[75 125 100 80 65 70 85], 調用MATLAB中lingprog函數求出Min Cost的值，如下圖所示:
結果:
>> f=[464 513 654 867 352 416 690 791 995 682 388 685]
A=[0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 1]
b=[75 125 100 80 65 70 85]
c=[0 0 0 0 0 0 0 0 0 0 0 0 ];
[v,e]= linprog(f,[],[],A,b,c)
x=reshape(v,4,3);
x=x';
?
?
f =
?
?? 464?? 513?? 654?? 867?? 352?? 416?? 690?? 791?? 995?? 682?? 388?? 685
?
?
A =
?
???? 0???? 1???? 0???? 1???? 0???? 0???? 0???? 0???? 0???? 0???? 0???? 0
???? 0???? 0???? 0???? 0???? 1???? 1???? 0???? 0???? 0???? 0???? 0?? ??0
???? 0???? 0???? 0???? 0???? 0???? 0???? 0???? 0???? 0???? 0???? 1???? 1
???? 0???? 0???? 0???? 0???? 1???? 0???? 0???? 0???? 0???? 0???? 0???? 0
???? 0???? 1???? 0???? 0???? 0???? 1???? 0???? 0???? 0???? 0???? 0???? 0
???? 0???? 0???? 0???? 0???? 0?? ??0???? 0???? 0???? 0???? 0???? 1???? 0
???? 0???? 0???? 0???? 1???? 0???? 0???? 0???? 0???? 0???? 0???? 0???? 1
?
?
b =
?
??? 75?? 125?? 100??? 80??? 65??? 70??? 85
?
?
Optimal solution found.
?
?
v =
?
???? 0
??? 20
???? 0
??? 55
??? 80
??? 45
???? 0
???? 0
??? ?0
???? 0
??? 70
??? 30
?
?
e =
?
????? 152535
?
?
?
代碼:
min=464*X11+513*X12+654*X13+867*X14
????????????????????????? +352*X21+416*X22+690*X23+791*X24
????????????????????????? +995*X31+682*X32+388*X33+685*X34;
X11+X12+X13+X14=75;
X21+X22+X23+X24=125;
X31+X32+X33+X34=100;
X11+X21+X31=80;
X12+X22+X32=65;
X13+X23+X33=70;
X14+X24+X34=85;
結果:
Global optimal solution found.
? Objective value:????????????????????????????? 152535.0
? Infeasibilities:????????????????????????????? 0.000000
? Total solver iterations:???????????????????????????? 7
? Elapsed runtime seconds:????????????????????????? 0.11
?
? Model Class:??????????????????????????????????????? LP
?
? Total variables:???????????????????? 12
? Nonlinear variables:????????????????? 0
? Integer variables:??????????????????? 0
?
? Total constraints:?? ?????????????????8
? Nonlinear constraints:??????????????? 0
?
? Total nonzeros:????????????????????? 36
? Nonlinear nonzeros:?????????????????? 0
?
?
?
??????????????????????????????? Variable?????????? Value??????? Reduced Cost
????????????????????????????? ???????X11??????? 0.000000??????????? 15.00000
???????????????????????????????????? X12??????? 20.00000??????????? 0.000000
???????????????????????????????????? X13??????? 0.000000??????????? 84.00000
???????????????????????????????????? X14??????? 55.00000??????????? 0.000000
???????????????????????????????????? X21??????? 80.00000??????????? 0.000000
???????????????????????????????????? X22??????? 45.00000??????????? 0.000000
???????????????????????????????????? X23??????? 0.000000??????????? 217.0000
?? ??????????????????????????????????X24??????? 0.000000??????????? 21.00000
???????????????????????????????????? X31??????? 0.000000??????????? 728.0000
???????????????????????????????????? X32??????? 0.000000??????????? 351.0000
??????????????????????????? ?????????X33??????? 70.00000??????????? 0.000000
???????????????????????????????????? X34??????? 30.00000??????????? 0.000000
?
???????????????????????????????????? Row??? Slack or Surplus????? Dual Price
?????????????????????????????????????? 1??????? 152535.0?????????? -1.000000
?????????????????????????????????????? 2??????? 0.000000?????????? -513.0000
?????????????????????????????????????? 3??????? 0.000000?????????? -416.0000
?????????????????????????????????????? 4??????? 0.000000?????????? -331.0000
?????????????????????????????????????? 5??????? 0.000000??????????? 64.00000
?????????????????????????????????????? 6??????? 0.000000??????????? 0.000000
?????????????????????????????????????? 7??????? 0.000000?????????? -57.00000
???????????????????????? ??????????????8??????? 0.000000?????????? -354.0000
?
?
0-1整數規劃問題
Maximize Z=9x1+5x2+6x3+4x4
?
Subject to
6x1+3x2+5x3+2x4≤10
x3+x4≤1
-x1????? + x3?? ≤0
-x1????????? +x4≤0
xj≤1
xj≥0
and
? xj ?is integer,? for j=1,2,3,4
? xj? is binary?? for j=1,2,3,4
?
①輸入問題數據
②分析題目添加約束條件、填寫目標函數
F2 =B2*B7+C2*C7+D2*D7+E2*E7
F3 =D3*D7+E3*E7
F4 =B4*B7+D4*D7
F5 =C5*C7+E5*E7
?
B7=X1;C7=X2;D7=X3;E=X4
?
H8 =B8*B7+C8*C7+D8*D7+E8*E7
?
③求解結果:
?
?
將目標函數轉化為求函數的f=-1*[9 5 6 4];根據目標函數和約束條件，可以得出目標函數系數矩陣A=[6 3 5 2
0 0 1 1
-1 0 1 0
0 -1 0 1]
b=[10 1 0 0];不等式約束常向量b=[10 1 0 0]; 調用MATLAB中intlinprog函數求出f的值，則-1*fval則為最終結果，如下圖所示:
結果:
>> f=-1*[9 5 6 4];
intcon=[1 2 3 4];
A=[6 3 5 2
0 0 1 1
-1 0 1 0
0 -1 0 1]
b=[10 1 0 0];
lb=zeros(4,1);
ub=ones(4,1);
[x,fval,exitflag,output]=intlinprog(f,intcon,A,b,[],[],lb,ub);
x
-1*fval
?
A =
?
???? 6???? 3???? 5???? 2
???? 0???? 0???? 1???? 1
??? -1???? 0???? 1???? 0
???? 0??? -1???? 0???? 1
?
LP:??????????????? Optimal objective value is -16.500000.??????????????????????????????????????????
?
Cut Generation:? ??Applied 1 implication cut.??????????????????????????????????????????????????????
?????????????????? Lower bound is -14.000000.??????????????????????????????????????????????????????
?????????????????? Relative gap is 0.00%.?????????????????????????????????????????????????????????
?
?
Optimal solution found.
?
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value,
options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05
(the default value).
?
?
x =
?
???? 1
???? 1
???? 0
???? 0
?
?
ans =
?
14
?
則結果為 14
?
3、lingo
代碼:
max=9*x1+5*x2+6*x3+4*x4;
6*x1+3*x2+5*x3+2*x4<=10;
x3+x4<=1;
-x1+x3<=0;
-x1+x4<=0;
?
結果:
Global optimal solution found.
? Objective value:????????????????????????????? 16.66667
? Infeasibilities:????????????????????????????? 0.000000
? Total solver iterations:???????????????????????????? 0
? Elapsed runtime seconds:????????????????????????? 0.44
?
? Model Class:??????????????????????????????????????? LP
?
? Total variables:????????????????????? 4
? Nonlinear variables:????????????????? 0
? Integer variables:??????????????????? 0
?
? Total constraints:??????????????????? 5
? Nonlinear constraints:??????????????? 0
?
? Total nonzeros:????????????????????? 14
? Nonlinear nonzeros:?????????????????? 0
?
?
?
??????????????????????????????? Variable?????????? Value??????? Reduced Cost
????????????????????????????????????? X1??????? 0.000000??????????? 0.000000
????????????????????????????????????? X2??????? 3.333333??????????? 0.000000
????????????????????????????????????? X3??????? 0.000000??????????? 2.333333
????????????????????????????????????? X4??????? 0.000000?????????? 0.3333333
?
???????????????????????????????????? Row??? Slack or Surplus????? Dual Price
?????????????????????????????????????? 1??????? 16.66667??????????? 1.000000
???????????????????????? ??????????????2??????? 0.000000??????????? 1.666667
?????????????????????????????????????? 3??????? 1.000000??????????? 0.000000
?????????????????????????????????????? 4??????? 0.000000??????????? 0.000000
?????????????????????????????????????? 5??????? 0.000000??????????? 1.000000
?
結果為14
?
四、實驗結果
線性規劃:
Excel:
MATLAB:
LINGO：
運輸問題:
Excel:
MATLAB:
LINGO：
?
0-1整數規劃:
Excel:
?
MATLAB:
LINGO：
?
五、分析與討論
這次實驗分別用excel、matlab和lingo求解線性規劃、運輸問題和0-1整數規劃問題，相比第一次實驗，這次實驗學習了lingo這個計算機軟件工具，用不同的工具去求解問題。? 線性規劃問題是使用linprog函數將目標函數求Max值轉化為求函數-S的最小值；運輸問題調用matlab中lingprog函數求出Min Cost的值；求解0-1整數問題時，在使用matlab時，使用了intlinprog函數。
本次實驗實踐過程較為輕松，首先要明確問題類型，分析題目，理解題目的約束條件、目標函數，熟悉Excel、matlab、lingo軟件的公式或函數，就能輕松把結果求解出來。
總結
以上是生活随笔為你收集整理的运筹与决策（三）求解线性规划、运输问题和0-1整数规划问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 浅析OC中的block
- 下一篇： BATJ互掐，哪家AI公司首先达到万亿美