Lindo解线性规划问题实例

《Lindo解线性规划问题实例》由会员分享，可在线阅读，更多相关《Lindo解线性规划问题实例（13页珍藏版）》请在装配图网上搜索。

1、标题：LINDO软件包介绍；副标题： Lindo 解线性规划问题实例导语：LINDO软件包首先由Linus Schrage开发，现在，美国的LINDO系 统公司（LINDO System Inc）拥有版权，是一种专门求解数学规划（优化问题） 的软件包。它能求解线性规划、（0， 1）规划、整数规划、二次规划等优化问题， 并能同时给出灵敏度分析、影子价格以及最优解的松弛分析，非常方便实用。1注意事项（ 1） 低版本的 LINDO 要求变量一律用大写字母表示；（2）求解一个问题，送入的程序必须以MIN或MAX开头，以END结 束；然后按Ctrl + S （或按工具栏中的执行快捷键）进行求解；（3）目

2、标函数与约束条件之间要用SUBJECT TO （或ST）分开，其 中字母全部大写；（4）LINDO已假定所有变量非负，若某变量，例如X5有可能取负值， 可在END命令下面一行用FREE X5命令取消X5的非负限制； LINDO 要求将取整数值的变量放在前面（即下标取小值），在 END下面一行用命令INTEGER K,表示前K个变量是（0,1） 变量；在END下面一行用命令GIN H表示前H个变量是整数变 量；（5）在LINDO中，“v”等价于“W” ，“”等价于“三”；（6）在LINDO的输出结果中有STATUS（状态栏），它的表出状态有： OPTIMAL （说明软件包求得的结果是最优解）、F

3、EASIBLE （说 明软件包求得的结果只是可行解）、INFEASIBLE （说明软件包 求得的结果是不可行解）。（7）在 LINDO 命令中，约束条件的右边只能是常数，不能有变量；（8）变量名不能超过 8 个字符；（9）LINDO对目标函数的要求，每项都要有变量，例如，LINDO不 认识 MIN 2000-X+Y，要改为 MIN X+Y；（10）LINDO 不认识 400 （X+Y）要改为 400X+400Y。2求解线性规划问题例6-1 求解下列线性规划问题：max f = 2 x + 3 y4x + 3 y 10s.t. 3x + 5y 0在 LINDO 中输入下列命令：MAX 2X+3Y

4、SUBJECT TO4X+3Y103X+5Y12ENDLINDO 输出下列结果：STATUS OPTIMALLP OPTIMUM FOUND AT STEP1OBJECTIVE FUNCTION VALUE1)7.454545VARIABLEVALUEREDUCED COSTX1.2727270.000000Y1.6363640.000000ROW SLACK OR SURPLUS DUAL PRICES2)0.0000000.0909093)0.0000000.545455NO. ITERATIONS= 1RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ

5、COEFFICIENT RANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFX2.000000Y3.000000INCREASE2.0000000.333333DECREASE0.2000001.500000ROWRIGHTHAND SIDE RANGESCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE210.0000006.0000002.800000312.0000004.6666674.500000这个结果说明：LINDO求解此线性规划问题（LP）只用一步迭代就得到最 优解 fmax = 7.454545, x =

6、 1.272727, y = 1.636364。两个松弛变量取 0 值，即， 这个最优解使得约束条件都取等号；其对偶问题的最优解（影子价格） DUAL PRICES为Y1=0.090909, Y2=0.545455。同时灵敏度分析告诉我们：在目标函数中，X的系数是2,允许下降0.2,允许增加2,即，X的系数在区间1.8, 4中 任意变化，最优基不变；在目标函数中，Y的系数是3,允许下降1.5,允许增 加0.333333，即，Y的系数在区间1.5, 3.333333中任意变化，最优基不变；约 束条件右边第一个常数是 10,允许下降 2.8,允许增加 6,即在区间7.2, 16中 任意变化，最优基

7、不变；约束条件右边第二个常数是12，允许下降4.5，允许增 加 4.666667，即在区间7.5， 16.666667中任意变化，最优基不变。例 6-2 求解下列线性规划问题：min f = x + y2x + 3 y 9s.t. x - 4y 0, yFREE在 LINDO 中输入以下命令：MIN X+YST2X+3Y9X-4Y11ENDFREE YLINDO运算后输出以下结果：STATUS OPTIMALLP OPTIMUM FOUND AT STEP1OBJECTIVE FUNCTION VALUE1) -2.750000REDUCED COST1.2500000.000000VARIA

8、BLEVALUEX0.000000Y-2.750000ROW SLACK OR SURPLUSDUAL PRICES2) 17.2500000.0000003) 0.0000000.250000NO. ITERATIONS=1RANGES IN WHICH THE BASIS IS UNCHANGED:VARIABLEOBJ COEFFICIENT RANGESCURRENTALLOWABLEROWRIGHTHAND SIDE RANGESCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE29.000000INFINITY17.250000311.0000

9、00INFINITY23.000000这个结果说明：LINDO求解此线性规划问题（LP）只用一步迭代就得到最 优解fmin = -2.75，x = 0, y = -2.75。第一个松弛变量取值17.25，第二个松弛变 量取 0值，即，这个最优解使得第二个约束条件取等号；其对偶问题的最优解（影 子价格）DUAL PRICES为Y=0, Y2=0.25。同时灵敏度分析告诉我们：在目标 函数中，X的系数是1,允许下降1.25,允许增加即, X的系数在区间-0.25, g中任意变化，最优基不变；在目标函数中，Y的系数是1,允许下降1,允许 增加即，Y的系数在区间0,-中任意变化，最优基不变；约束条件右

10、边 第一个常数是9,允许下降17.25,允许增加即在区间-8.25,-中任意变化, 最优基不变；约束条件右边第二个常数是11,允许下降23,允许增加即在 区间-12,中任意变化，最优基不变。ALLOWABLECOEFX1.000000Y1.000000INCREASEINFINITYINFINITYDECREASE1.2500001.000000例6-3求解下列线性规划问题（参见第5章例18）MAX 360X1+220X2+240X3+360X4+220X5+240X6STX1+X2+X3300X4+X5+X61200X1+X46000X2+X5500X3+X609X2-X50END得到结果如

11、下：LP OPTIMUM FOUND AT STEP3OBJECTIVE FUNCTION VALUE1）400000.0VARIABLEX1X2VALUE285.71429414.285714REDUCED COST0.0000000.000000X30.000000200.000000X471.4285740.000000X5128.5714260.000000X61000.0000000.0000000.000000400.0000000.000000200.0000005642.8569340.000000357.1428530.0000000.00000040.0000000.000

12、000-40.0000000.000000-20.000000ROW SLACK OR SURPLUS DUAL PRICES2)3)4)5)6)7)8)NO. ITERATIONS= 3RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLECOEFINCREASEDECREASEX1360.0000001750.000000174.999985X2220.000000175.0000001750.000000X3240.000000200.000000I

13、NFINITYX4360.0000007000.000000155.555542X5220.00000038.888885194.444427X6240.000000INFINITY40.000000RIGHTHAND SIDE RANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2300.000000499.999969277.77777131200.000000312.499969124.99999246000.000000INFINITY5642.8569345500.000000INFINITY357.14285361000.000

14、000124.999992312.49996970.000000277.777771499.99996980.0000002499.999756125.0000003.求解整数线性规划问题例 6-4 求解下列（ 0 ， 1 ）线性规划问题：max f = xll + x12 + 2x13 + 5x14 + 7x15 + x21 + 2x22 + 3x23 + 7x24 + 10x25+ x31 + 3x32 + 4x33 + 9x34 +10x35 + x41 + 4x42 + 5x43 +10x44 +10x45工 x = 1,1 i 4ijj=1s.t.x = 1,1 j 5iji=1x

15、= 0,1ij在 LINDO 中输入下列命令：MAX X11+X12+2X13+5X14+7X15+X21+2X22+3X23+7X24+10X25+X31+3X32+4X33+9X34+10X35+X41+4X42+5X43+10X44+10X45STX11+X12+X13+X14+X15=1X21+X22+X23+X24+X25=1X31+X32+X33+X34+X35=1X41+X42+X43+X44+X45=1X11+X21+X31+X41=1X12+X22+X32+X42=1X13+X23+X33+X43=1X14+X24+X34+X44=1X15+X25+X35+X45=1ENDI

16、NT 20LINDO运算后输出下列结果：STATUS INFEASIBLE （求不出最优解）若将问题变为5X5的问题，就能求出解来。max f = x11 + x12 + 2x13 + 5x14 + 7x15 + x21 + 2x22 + 3x23 + 7x24 +10x25 + x31 + 3x32 + 4x33 + 9x34 +10x35 + x41 + 4x42 + 5x43 +10x44 +10x45工 x = 1,1 i 4 ijj=1s.t. 工 x =1,1 j1.00000NEW INTEGER SOLUTION OF 25.0000000 AT BRANCH 0PIVOT 1

17、5BOUND ON OPTIMUM: 25.00000ENUMERATION COMPLETE. BRANCHES=0 PIVOTS=15LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUEVARIABLEVALUEREDUCED COSTX110.000000-1.000000X120.000000-1.000000X131.000000-2.000000X140.000000-5.000000X150.000000-7.000000X210.000000-1.

18、000000X220.000000-2.000000X230.000000-3.000000X240.000000-7.000000X251.000000-10.000000X310.000000-1.0000001)25.00000X320.000000-3.000000X330.000000-4.000000X341.000000-9.000000X350.000000-10.000000X410.000000-1.000000X421.000000-4.000000X430.000000-5.000000X440.000000-10.000000X450.000000-10.000000

19、X511.0000000.000000X520.0000000.000000X530.0000000.000000X540.0000000.000000X550.0000000.000000ROW)234567890.000000 0.00000010)11)0.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.000000SLACK OR SURPLUS DUAL PRIC

20、ESNO. ITERATIONS= 15BRANCHES= 0 DETERM.= 1.000E 0这个结果说明：LINDO求解此（0, 1）整数线性规划问题（LP）只15步 迭代得到最优解 fmax = 25，x13 = x25 = x34 = x42 = x51 =1，其它 xij = 0。松弛 变量都取0值,即,这个最优解使得约束条件都取等号；其对偶问题的最优解（影 子价格）DUAL PRICES都为0。例6-5求解下列整数线性规划问题（参见第5章例6）：max f = 20 x1 +10 y1x1 + x 2 + x3 = 30,y1 + y 2 + y3 = 20s.t.20x1 +1

21、0 y1 = 30x2 + 20y 2 = 25 x3 +15 y3 20x1 +10y1 20*30 +10*20 30x2 + 20y2 30*30 + 20*20 25x3 +15y3 0,int egersij在 LINDO 环境下，输入下列命令：MAX 20X1+10Y1STX1+X2+X3=30Y1+Y2+Y3=2020X1+10Y1=30X2+20Y230X2+20Y2=25X3+15Y320X1+10Y180030X2+20Y2130025X3+15Y3 0.000000E+00 DELETE Y2 AT LEVEL 1 RELEASE FIXED VARIABLESFIX A

22、LL VARS.( 1) WITH RC 0.000000E+00 DELETEY2 AT LEVEL1RELEASE FIXED VARIABLESFIX ALL VARS.( 1) WITH RC 0.000000E+00SETX3TO=2AT2,BND=348.3TWIN=-0.1000E+3118SETY2TO=3AT4,BND=347.5TWIN=-0.1000E+3120SETX3TO=4AT6,BND=346.7TWIN=-0.1000E+3123SETY2TO=5AT8,BND=345.8TWIN=-0.1000E+3126SETX3TO=6AT10,BND=345.0TWIN

23、=-0.1000E+3129SETY2TO=8AT11,BND=344.9TWIN=-0.1000E+3131SETX3TO=7AT13,BND=344.2TWIN=-0.1000E+3134SETY2TO=8AT15,BND=343.3TWIN=-0.1000E+3137SETY2TO=9AT17,BND=342.5TWIN=-0.1000E+3140SETY2TO=10AT19,BND=341.7TWIN=-0.1000E+3143SETY2TO=11AT21,BND=340.8TWIN=-0.1000E+3146SETY2TO=0AT22,BND=340.5TWIN=-0.1000E+3

24、147DELETEX2 AT LEVEL23DELETEY2 AT LEVEL22DELETEX2 AT LEVEL21DELETEY2 AT LEVEL20DELETEX2 AT LEVEL19DELETEY2 AT LEVEL18DELETEX2 AT LEVEL17DELETEY2 AT LEVEL16DELETEX2 AT LEVEL15DELETEY2 AT LEVEL14DELETEX2 AT LEVEL13DELETEX3 AT LEVEL12DELETEY2 AT LEVEL11DELETEX2 AT LEVEL10DELETEX3 AT LEVEL9DELETEX2 AT L

25、EVEL8DELETEY2 AT LEVEL7DELETEX2 AT LEVEL6DELETEX3 AT LEVEL5DELETEX2 AT LEVEL4DELETEY2 AT LEVEL3DELETEX2 AT LEVEL2DELETEX3 AT LEVEL1RELEASE FIXED VARIABLESSETY2TO=TWIN=-0.1000E+3162SETY2TO=TWIN=-0.1000E+3166SETY2TO=TWIN=-0.1000E+3172SETY2TO=TWIN=-0.1000E+3175SETX2 TO 10000s.t. 20000x 0, int egersj在 L

26、INDO 中输入下列命令：MIN X1+X2+X3+X4+X5+X6STX2+2X3+3X4+4X5+5X6100006X1+5X2+3X3+2X4+X520000ENDGIN 6LINDO运行后输出以下结果：STATUS： OPTIMALLP OPTIMUM FOUND AT STEP3OBJECTIVE VALUE =5200.00000FIX ALL VARS.( 4) WITH RC 0.400000E-01NEW INTEGER SOLUTION OF 5200.00000 AT BRANCH 0PIVOT 3BOUND ON OPTIMUM: 5200.000ENUMERATION

27、 COMPLETE. BRANCHES= 0 PIVOTS= 3LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUEVARIABLEVALUEREDUCED COSTX10.0000001.000000X24000.0000001.000000X30.0000001.000000X40.0000001.000000X50.0000001.000000X61200.0000001.0000001)5200.000ROWSLACK OR SURPLUSDUAL PRICES2)0.0000000.0000003)0.0000000.000000NO. ITERATIONS= 3BRANCHES= 0 DETERM.= 1.000E0这个结果说明：LINDO求解此线性规划问题（LP）共用3步迭代得到最优 解 fmin = 5200， x2 = 4000，x6 = 1200，其它xj = 0。松弛变量都取0值，即，这个最优解使得约束条件都取 等号；其对偶问题的最优解（影子价格）DUAL PRICES都为0。