Lindo解線性規(guī)劃問(wèn)題實(shí)例

1、標(biāo)題：LINDO軟件包介紹；副標(biāo)題：Lindo解線性規(guī)劃問(wèn)題實(shí)例導(dǎo)語(yǔ)：LINDO軟件包首先由Linus Schrage開發(fā)，現(xiàn)在，美國(guó)的 LINDO系統(tǒng)公司(LINDO System Inc.)擁有版權(quán)，是一種專門求解數(shù)學(xué)規(guī)劃(優(yōu)化問(wèn)題) 的軟件包。它能求解線性規(guī)劃、(0，1)規(guī)劃、整數(shù)規(guī)劃、二次規(guī)劃等優(yōu)化問(wèn)題， 并能同時(shí)給出靈敏度分析、影子價(jià)格以及最優(yōu)解的松弛分析，非常方便實(shí)用。1. 注意事項(xiàng)(1) 低版本的LINDO要求變量一律用大寫字母表示；(2) 求解一個(gè)問(wèn)題，送入的程序必須以MIN或MAX開頭，以END結(jié) 束；然后按Ctrl + S (或按工具欄中的執(zhí)行快捷鍵)進(jìn)行求解；(3) 目標(biāo)

2、函數(shù)與約束條件之間要用 SUBJECT TO (或ST)分開，其 中字母全部大寫；(4) LINDO已假定所有變量非負(fù)，若某變量，例如X5有可能取負(fù)值， 可在END命令下面一行用FREE X5命令取消X5的非負(fù)限制； LINDO 要求將取整數(shù)值的變量放在前面(即下標(biāo)取小值)，在 END下面一行用命令I(lǐng)NTEGER K，表示前K個(gè)變量是(0,1) 變量；在END下面一行用命令GIN H表示前H個(gè)變量是整數(shù)變 1量;(5) 在LINDO中，“<”等價(jià)于“W”，“”等價(jià)于；(6) 在LINDO的輸出結(jié)果中有 STATUS(狀態(tài)欄)，它的表出狀態(tài)有： OPTIMAL (說(shuō)明軟件包求得的結(jié)果是最優(yōu)

3、解)、FEASIBLE (說(shuō) 明軟件包求得的結(jié)果只是可行解)、INFEASIBLE (說(shuō)明軟件包 求得的結(jié)果是不可行解)。(7) 在LINDO命令中，約束條件的右邊只能是常數(shù)，不能有變量；(8) 變量名不能超過(guò)8個(gè)字符；(9) LINDO對(duì)目標(biāo)函數(shù)的要求，每項(xiàng)都要有變量，例如， LINDO不 認(rèn)識(shí) MIN 2000-X+Y，要改為 MIN -(+Y ；(10) LINDO 不認(rèn)識(shí) 400 (X+Y )要改為 400X+400Y。2. 求解線性規(guī)劃問(wèn)題例6-1求解下列線性規(guī)劃問(wèn)題：max f =2x 3y4x 3y 豈10s.t.« 3x + 5y 蘭 12.x, y在LINDO中輸入

4、下列命令：MAX 2X+3YSUBJECT TO4X+3Y<103X+5Y<12 ENDLINDO 輸出下列結(jié)果：STATUS OPTIMALLP OPTIMUM FOUND AT STEP1OBJECTIVE FUNCTION V ALUE1)7.454545VARIABLEXYVALUEREDUCEDCOST1.2727270.0000001.6363640.000000ROW2)3)SLACK OR SURPLUSDUAL PRICES0.0000000.0909090.0000000.545455NO. ITERATIONS= 1RANGES IN WHICH THE BA

5、SIS IS UNCHANGED:VARIABLEALLOWABLEOBJ COEFFICIENT RANGESCURRENTALLOWABLECOEFINCREASEDECREASEXY2.0000002.0000000.2000003.0000000.3333331.500000ROWALLOWABLERIGHTHAND SIDE RANGESCURRENTALLOWABLERHSINCREASEDECREASE2310.0000006.0000002.80000012.0000004.6666674.500000這個(gè)結(jié)果說(shuō)明： LINDO求解此線性規(guī)劃問(wèn)題（LP）只用一步迭代就得到最優(yōu)解

6、 fmax = 7.454545，x = 1.272727, y = 1.636364。兩個(gè)松弛變量取 0 值，即， 這個(gè)最優(yōu)解使得約束條件都取等號(hào)；其對(duì)偶問(wèn)題的最優(yōu)解（影子價(jià)格） DUALPRICES為Yi=0.090909, 丫2=0.545455同時(shí)靈敏度分析告訴我們：在目標(biāo)函數(shù)中，X的系數(shù)是2,允許下降0.2,允許增加2,即，X的系數(shù)在區(qū)間1.8, 4中 任意變化，最優(yōu)基不變；在目標(biāo)函數(shù)中，丫的系數(shù)是3,允許下降1.5,允許增加0.333333,即，丫的系數(shù)在區(qū)間1.5, 3.333333中任意變化，最優(yōu)基不變；約 束條件右邊第一個(gè)常數(shù)是10,允許下降2.8,允許增加6,即在區(qū)間7.2

7、, 16中 任意變化，最優(yōu)基不變；約束條件右邊第二個(gè)常數(shù)是12,允許下降4.5,允許增加4.666667,即在區(qū)間7.5, 16.666667沖任意變化，最優(yōu)基不變。例6-2求解下列線性規(guī)劃問(wèn)題：min f = x y'2x+3y 蘭9s.t.x 4y 蘭 11x >0, yFREE 在LINDO中輸入以下命令：MIN X+YST2X+3Y 9 X-4Y 11ENDFREE YLINDO 運(yùn)算后輸出以下結(jié)果：STATUS OPTIMALLP OPTIMUM FOUND AT STEP1OBJECTIVE FUNCTION V ALUE1)-2.750000VARIABLEVALU

8、EREDUCED COSTX0.0000001.250000Y-2.7500000.000000ROW SLACK OR SURPLUS DUAL PRICES2) 17.2500000.0000003) 0.0000000.250000NO. ITERATIONS=1RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLECURRENTALLOWABLEALLOWABLEINCREASEINFINITYINFINITYDECREASE1.2500001.000000COEFX1.000000Y1.000000R

9、IGHTHAND SIDE RANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE29.000000INFINITY17.250000311.000000INFINITY23.000000這個(gè)結(jié)果說(shuō)明：LINDO求解此線性規(guī)劃問(wèn)題（LP）只用一步迭代就得到最 優(yōu)解 fmin = -2.75，x = 0, y = -2.75 。第一個(gè)松弛變量取值 17.25，第二個(gè)松弛變 量取 0值，即，這個(gè)最優(yōu)解使得第二個(gè)約束條件取等號(hào)； 其對(duì)偶問(wèn)題的最優(yōu)解（影 子價(jià)格）DUAL PRICES為丫1=0, 丫2=0.25。同時(shí)靈敏度分析告訴我們：在目標(biāo) 函數(shù)

10、中，X的系數(shù)是1,允許下降1.25,允許增加,即，X的系數(shù)在區(qū)間-0.25, X中任意變化，最優(yōu)基不變；在目標(biāo)函數(shù)中，丫的系數(shù)是1,允許下降1,允許增加,即，丫的系數(shù)在區(qū)間0, x中任意變化，最優(yōu)基不變；約束條件右邊 第一個(gè)常數(shù)是9,允許下降17.25,允許增加,即在區(qū)間-8.25, x中任意變化， 最優(yōu)基不變；約束條件右邊第二個(gè)常數(shù)是11,允許下降23,允許增加,即在區(qū)間-12, x中任意變化，最優(yōu)基不變。例6-3求解下列線性規(guī)劃問(wèn)題（ 參見第 5章例 18）： MAX 360X1+220X2+240X3+360X4+220X5+240X6 STX1+X2+X3<300 X4+X5+X

11、6<1200 X1+X4<6000 X2+X5<500 X3+X6<1000 X1-4X4>0 9X2-X5>0END得到結(jié)果如下：LP OPTIMUM FOUND AT STEP3OBJECTIVE FUNCTION V ALUE1) 400000.0VARIABLEX1X2VALUE285.71429414.285714REDUCED COST0.0000000.000000X30.000000 200.000000X4 71.428574 0.000000X5 128.571426 0.000000X6 1000.000000 0.000000ROW

12、SLACK OR SURPLUS DUAL PRICES2)0.000000400.0000003)0.000000200.0000004)5642.8569340.0000005)357.1428530.0000006)0.00000040.0000007)0.000000-40.0000008)0.000000-20.000000NO. ITERATIONS= 3RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX

13、1360.0000001750.000000174.999985X2220.000000175.0000001750.000000X3240.000000200.000000INFINITYX4360.0000007000.000000155.555542X5220.00000038.888885194.444427X6240.000000INFINITY40.000000RIGHTHAND SIDE RANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2300.000000499.999969277.77777131200.0000003

14、12.499969124.99999246000.000000INFINITY5642.8569345500.000000INFINITY357000000124.999992312.49996970.000000277.777771499.99996980.0000002499.999756125.0000003. 求解整數(shù)線性規(guī)劃問(wèn)題例6-4求解下列（0, 1）線性規(guī)劃問(wèn)題：max f = x11 x12 2x13 5x14 7x15 x21 2x22 3x23 7x24 10x25x31 3x32 4x33 9x34 10x35 x41 4x42 5x43 10

15、x44 10x45L 5Z n = 1,1 蘭 i 蘭 4j 二4st.« E $ =1,1 乞 j 蘭5Xj =0,1在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+X4 仁1X12+X22+X32+X42

16、=1X13+X23+X33+X43=1X14+X24+X34+X44=1X15+X25+X35+X45=1ENDINT 20 LINDO運(yùn)算后輸出下列結(jié)果：STATUS INFEASIBLE （求不出最優(yōu)解）。若 將問(wèn)題變?yōu)?X5的問(wèn)題，就能求出解來(lái)。max f =x11 x12 2x13 5x14 7x15 x21 2x22 3x23 7x24 10x25x31 3x32 4x33 9x34 10x35 x41 4x42 5x43 10x44 10x45'5送 xj =1,1 Wi W4j丑5st.« 瓦 xj =1,1 蘭 j 蘭 5xij =0,1在LINDO中輸入下列

17、命令：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=1X51+X52+X53+X54+X55=1X11+X21+X31+X41+X51=1X12+X22+X32+X42+X52=1X13+X23+X33+X43+X53=1X14+X24+X34+X44+X54=1X15+

18、X25+X35+X45+X55=1ENDINT 25LINDO 運(yùn)算后輸出下列結(jié)果： STATUS OPTIMALLP OPTIMUM FOUND AT STEP15OBJECTIVE V ALUE = 25.0000000FIX ALL V ARS.( 11) WITH RC > 1.00000015NEW INTEGER SOLUTION OF 25.0000000 AT BRANCH PIVOT 15BOUND ON OPTIMUM: 25.00000ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS=LAST INTEGER SOLUTION IS

19、THE BEST FOUND RE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION V ALUE1) 25.00000VARIABLEVALUEREDUCED COSTX110.000000-1.000000X120.000000-1.000000X131.000000-2.000000X140.000000-5.000000X150.000000-7.000000X210.000000-1.000000X220.000000-2.000000X230.000000-3.000000X240.000000-7.000000X251.000000-10.0

20、00000X310.000000-1.000000X320.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.000000X511.0000000.000000X520.0000000.000000X530.0000000.000000X540.0000000.000000X55 0.000000 0.0

21、000002)0.0000000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.0000006)0.0000000.0000007)0.0000000.0000008)0.0000000.0000009)0.0000000.00000010)0.0000000.00000011)0.0000000.000000NO. ITERATIONS=15BRANCHES=0 DETERM.=1.000E 0ROWSLACK OR SURPLUS這個(gè)結(jié)果說(shuō)明：LINDO求解此（0,1）整數(shù)線性規(guī)劃問(wèn)題（LP）只15步 迭代得到最優(yōu)解 fmax

22、= 25， x13 = x25 = x34 = x42 = x51 =1，其它 xij = 0 。松弛 變量都取 0 值,即,這個(gè)最優(yōu)解使得約束條件都取等號(hào)； 其對(duì)偶問(wèn)題的最優(yōu)解（影 子價(jià)格） DUAL PRICES 都為 0。DUAL PRICES例6-5求解下列整數(shù)線性規(guī)劃問(wèn)題（ 參見第 5章例 6）：max f = 20x110 y1x1 +x2 + x3 = 30,y1 +y2 +y3 =2020x1 +10y1 =30x2 + 20y2 =25x3+15y3s.t”20x1 +10y1 玄20* 30 + 10* 2030x2 +20y2 蘭30*30 +20* 20 25x3 +1

23、5y3 蘭25* 30 +15* 20 xi, yj > 0,int egers在LINDO環(huán)境下，輸入下列命令：MAX 20X1+10Y1STX1+X2+X3=30Y1+Y2+Y3=2020X1+10Y1=30X2+20Y230X2+20Y2=25X3+15Y320X1+10Y1V80030X2+20Y2V130025X3+15Y3V1050ENDGIN 6LINDO 運(yùn)行后，輸出以下結(jié)果：STATUS: OPTIMALLP OPTIMUM FOUND AT STEP5OBJECTIVE V ALUE =350.000000FIX ALL V ARS.( 2) WITH RC >

24、0.000000E+00DELETEY2 AT LEVEL 1RELEASE FIXED V ARIABLESFIX ALL V ARS.( 1) WITH RC >0.000000E+00DELETEY2 AT LEVEL 1FIX ALL V ARS.(1)WITH RC >SETX3TOV=TWIN=-0.1000E+3117SETX2TO>=TWIN=-0.1000E+3118SETY2TOV=TWIN=-0.1000E+3119SETX2TO>=TWIN=-0.1000E+3120SETX3TOV=TWIN=-0.1000E+3122RELEASE FIXED

25、 V ARIABLES0.000000E+001,BND=348.711AT2AT2,BND=348.314AT3,BND=348.13AT4,BND=347.59AT5,BND=347.0SETX2TO>=4AT6,BND=346.7TWIN=-0.1000E+3123SETY2TO<=11AT7,BND=346.5TWIN=-0.1000E+3125SETX2TO>=5AT8,BND=345.8TWIN=-0.1000E+3126SETX3TO<=7AT9,BND=345.2TWIN=-0.1000E+3128SETX2TO>=6AT10,BND=345.0T

26、WIN=-0.1000E+3129SETY2TO<=8AT11,BND=344.9TWIN=-0.1000E+3131SETX3TO<=6AT12,BND=344.3TWIN=-0.1000E+3133SETX2TO>=7AT13,BND=344.2TWIN=-0.1000E+3134SETY2TO<=6AT14,BND=343.8TWIN=-0.1000E+3136SETX2TO>=8AT15,BND=343.3TWIN=-0.1000E+3137SETY2TO<=5AT16,BND=343.2TWIN=-0.1000E+3139SETX2TO>=9

27、AT17,BND=342.5TWIN=-0.1000E+3140SETY2TO<=3AT18,BND=342.2TWIN=-0.1000E+3142SETX2TO>=10AT19,BND=341.7TWIN=-0.1000E+3143SETY2TO<=2AT20,BND=341.6TWIN=-0.1000E+3145SETX2TO>=11AT21,BND=340.8TWIN=-0.1000E+3146SETY2TO<=0AT22,BND=340.5TWIN=-0.1000E+31 47DELETEX2 AT LEVEL23DELETEY2 AT LEVEL22DE

28、LETEX2 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 LEVEL8DELETEY2 AT LEVEL7DELETEX2 AT LEVEL6DE

29、LETEX3 AT LEVEL5DELETEX2 AT LEVEL4DELETEY2 AT LEVEL3DELETEX2 AT LEVEL2DELETEX3 AT LEVEL1340.000000AT BRANCH33BOUND ON OPTIMUM: 349.1667DELETEX2 AT LEVEL8DELETEY2 AT LEVEL7DELETEX2 AT LEVEL6DELETEY2 AT LEVEL5DELETEX2 AT LEVEL4DELETEY2 AT LEVEL3DELETEX2 AT LEVEL2DELETEY2 AT LEVEL1ENUMERATION COMPLETE.

30、 BRANCHES=NEW INTEGER SOLUTION OFPIVOT 7733 PIVOTS=77RELEASE FIXED V ARIABLESSETY2TO<=15AT1,BND=347.8TWIN=-0.1000E+3159SETX2TO>=2AT2,BND=347.5TWIN=-0.1000E+3162SETY2TO<=14AT3,BND=347.3TWIN=-0.1000E+3164SETX2TO>=3AT4,BND=346.7TWIN=-0.1000E+3166SETY2TO<=12AT5,BND=346.2TWIN=-0.1000E+3170

31、SETX2TO>=4AT6,BND=345.8TWIN=-0.1000E+3172SETY2TO<=11AT7,BND=345.7TWIN=-0.1000E+3175SET X2 TO <=4 AT8, BND=340.0TWIN=345.077LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION V ALUE1)340.0000VARIABLEVALUEREDUCED COSTX113.000000-20.000000Y18.000000 -10.0000

32、00X24.0000000.000000X313.0000000.000000Y211.0000000.000000Y31.0000000.000000ROWSLACK OR SURPLUSDUAL PRICES2)0.0000000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.0000006)460.0000000.0000007)960.0000000.0000008)710.0000000.000000NO. ITERATIONS=77BRANCHES=33 DETERM.= 1.000E0這個(gè)結(jié)果說(shuō)明：LINDO求解此線性規(guī)劃問(wèn)題（LP）共用77步迭代得到最 優(yōu)解 fmax = 340, x1 = 13，x2 = 4，x3 = 13，y 1= 8， y2