§14利用LINDO求解線性規(guī)劃問(wèn)題

1、14.利用LINDO求解線性規(guī)劃問(wèn)題LINDO是一種專門用于求解數(shù)學(xué)規(guī)劃問(wèn)題的軟件包。由于LINDO執(zhí)行速度 很快、易于方便輸入、求解和分析數(shù)學(xué)規(guī)劃問(wèn)題。因此在數(shù)學(xué)、科研和工業(yè)界得 到廣泛應(yīng)用。LINDO主要用于解線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃和整數(shù)規(guī)劃 等問(wèn)題。也可以用于一些非線性和線性方程組的求解以及代數(shù)方程求根等。 LINDO中包含了一種建模語(yǔ)言和許多常用的數(shù)學(xué)函數(shù)（包括大量概論函數(shù)），可 供使用者建立規(guī)劃問(wèn)題時(shí)調(diào)用。一般用 LINDO（Linear Interactive and Discrete Optimizer）解決線性規(guī)劃（LP Linear Programming）o 整數(shù)規(guī)

2、劃（IPInteger Programming）問(wèn)題。其中 LINDO 6.1學(xué)生版至多可求解多達(dá)300個(gè)變量和150個(gè)約束的規(guī)劃問(wèn)題。其正式版（標(biāo) 準(zhǔn)版）則可求解的變量和約束在1量級(jí)以上。譬如，對(duì)于教材中第5章第1節(jié)的應(yīng)用實(shí)例，即農(nóng)場(chǎng)種植計(jì)劃問(wèn)題：某農(nóng)場(chǎng)I、II、III等耕地的面積分別為100 hm2、300 hm2和200 hm2，計(jì)劃種 植水稻、大豆和玉米，要求三種作物的最低收獲量分別為190000 kg、130000 kg 和350000kg。I、II、III等耕地種植三種作物的單產(chǎn)如表5.1.4所示。若三種作物 的售價(jià)分別為水稻1.20元kg，大豆1.50元/ kg，玉米0.80元/

3、kg。那么，（1）如 何制訂種植計(jì)劃，才能使總產(chǎn)量最大？ （2）如何制訂種植計(jì)劃，才能使總產(chǎn)值 最大？表5.1.4不同等級(jí)耕地種植不同作物的單產(chǎn)（單位g/ hm2）I等耕地II等耕地III等耕地水稻11 0009 5009 000大豆8 0006 8006 000玉米14 00012 00010 000對(duì)于上面的農(nóng)場(chǎng)種植計(jì)劃問(wèn)題，我們可以用線性規(guī)劃方法建立模型。根據(jù)題意，決策變量設(shè)置如表5.1.5所示，表中奇表示在第j等級(jí)的耕地上 種植第，種作物的面積。表5.1.5作物計(jì)劃種植面積（單位加勿I等耕地II等耕地III等耕地水稻xxx111213大豆xxx212223玉米x31x32x33三種作物

4、的產(chǎn)量可以用表5.1.6表示。表5.1.6三種作物的總產(chǎn)量（單位:kg）作物種類總產(chǎn)量水稻11000X + 9500X12 + 9000X13大豆8000 x21 + 6800X22 + 6000X23玉米14000X31 + 12000 x32 + 10000 x33根據(jù)題意，約束方程如下:X+ X+X=1 0 0II2131X+X+X=3 0 0122232X+X+X=2 0 0132333耕地面積約束:11000X + 9500X + 9000X 190000130000 最低收獲量約束：(1 + 12000X32 + 10000X33 350000非負(fù)約束：X0 Sl，2，jE，2,3

5、）（1）追求最大總產(chǎn)量的目標(biāo)函數(shù)為：maxZ = 11000 x + 9500 x + 9000 x+ 8000 x +6800 x +6000 x+ 14000 x3i + 12000 x32 + 10000 x33對(duì)于上述線性規(guī)劃問(wèn)題，用lindo進(jìn)行求解運(yùn)算，可以按照下述步驟進(jìn)行：首先運(yùn)行l(wèi)indo程序，在程序主界面下利用程序包自帶的文件編輯功能，編 輯程序文件（*.ltx），文件內(nèi)容如下：max11000 x11+9500 x12+9000 x13+8000 x21+6800 x22+6000 x23+14000 x31+12000 x32+10000 x33STx11+x21+x31

6、=100 x12+x22+x32=300 x13+x23+x33=20011000 x11+9500 x12+9000 x13=1900008000 x21+6800 x22+6000 x23x31+12000 x32+10000 x33=350000然后進(jìn)行求解運(yùn)行，可以得如下結(jié)果：LP OPTIMUM FOUND AT STEP 6OBJECTIVE FUNCTION VALUE1） 6892222.VARIABLEVALUEREDUCED COSTX110.0000001777.777832X120.0000001444.444458X1321.1111110.

7、000000X210.000000666.666687X220.000000666.666687X2321.6666660.000000X31100.0000000.000000X32300.0000000.000000X33157.2222290.000000ROW SLACK OR SURPLUSDUAL PRICES2)0.00000014000.0000003)0.00000012000.0000004)0.00000010000.0000005)0.000000-0.1111116)0.000000-0.6666677)6222222.0000000.000000NO. ITERAT

8、IONS= 6RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX1111000.0000001777.777710INFINITYX129500.0000001444.444458INFINITYX139000.0000001000.0000001368.421021X218000.000000666.666504INFINITYX226800.000000666.666504INFINITYX236000.0000

9、004000.000244499.999878X3114000.000000INFINITY666.666504X3212000.000000INFINITY666.666504X3310000.000000499.9998781000.000000RIGHTHAND SIDE RANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2100.000000INFINITY100.0000003300.000000INFINITY300.0000004200.000000INFINITY157.2222295190000.000000141500

10、0.000000190000.0000006130000.000000943333.375000130000.0000007350000.0000006222222.000000INFINITY其中，輸出內(nèi)容得含義為:“LP OPTIMUM FOUND AT STEP 6表示 LINDO 在（用單純形法）6 次迭 代或旋轉(zhuǎn)后得到最優(yōu)解?！癘BJECTIVE FUNCTION VALUE 1） 6892222 表示最優(yōu)目標(biāo)值為 6892222。“VALUE”給出最優(yōu)解中各變量的值?！?SLACK OR SURPLUS ”給出松弛變量的值?！癉UAL PRICE（對(duì)偶價(jià)格）列出最優(yōu)單純形表中判別數(shù)

11、所在行的松弛變 量的系數(shù)，表示當(dāng)對(duì)應(yīng)約束有微小變動(dòng)時(shí)，目標(biāo)函數(shù)的變化率，輸出結(jié)果中對(duì)應(yīng) 每一個(gè)約束有一個(gè)對(duì)偶價(jià)格。若其數(shù)值為X，表示對(duì)應(yīng)約束中不等式右端項(xiàng)若增 加一個(gè)單位，目標(biāo)函數(shù)將增加X(jué)個(gè)單位（max型問(wèn)題）?！癛ANGES IN WHICH THE BASIS IS UNCHANGED給出靈敏度分析：如 果做敏感性分析，則系統(tǒng)報(bào)告當(dāng)目標(biāo)函數(shù)的費(fèi)用系數(shù)和約束右端項(xiàng)在什么范圍變 化（此時(shí)假定其他系數(shù)保持不變）時(shí)，最優(yōu)基保持不變。報(bào)告中INFINITY表示 正無(wú)窮。其中，“OBJ COEFFICIENT RANGES”為目標(biāo)函數(shù)的系數(shù)可變范圍；“RIGHTHAND SIDE RANGES”為邊界

12、約束的可變范圍。（2）將目標(biāo)函數(shù)改為：追求最大總產(chǎn)值，即：maxZ = 1.20 x（11000 x + 9500 x + 9000 x ）+ 1.50 x（8000 x + 6800 x + 6000 x ）+ 0.80 x（14000 x + 12000 x + 10000 x ）=13200 x +1140Ox +10800 x+12000 x +10200 x +9000 x+ 11200 x31 + 9600 x32 + 8000 x33如果還是用lindo求解，那么編輯程序文件，文件內(nèi)容如下：max13200 x11+11400 x12+10800 x13+12000 x21+10

13、200 x22+9000 x23+11200 x31+9600 x32+8000 x33 STx11+x21+x31=100 x12+x22+x32=300 x13+x23+x33=20011000 x11+9500 x12+9000 x13=1900008000 x21+6800 x22+6000 x23x31+12000 x32+10000 x33=350000求解運(yùn)行，可以得如下結(jié)果:LP OPTIMUM FOUND AT STEP 4OBJECTIVE FUNCTION VALUE1)6830500.VARIABLEVALUEREDUCED COSTX1158

14、.7500000.000000X12300.0000000.000000X13200.0000000.000000X2116.2500000.000000X220.000000180.000000X230.000000900.000000X3125.0000000.000000X320.00000085.714287X330.0000001371.428589ROW SLACK OR SURPLUS DUAL PRICES2)0.00000013200.0000003)0.00000011400.0000004)0.00000010800.0000005)5106250.0000000.000

15、0006)0.000000-0.1500007)0.000000-0.142857NO. ITERATIONS= 4RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESALLOWABLEDECREASEVARIABLECURRENT ALLOWABLECOEFINCREASEX1113200.00000099.9999081200.000000X1211400.000000INFINITY85.714211X1310800.000000INFINITY899.999939X2112000.0000001200.0000002

16、11.764648X2210200.000000179.999954INFINITYX239000.000000899.999939INFINITYX3111200.0000002000.00012299.999908X329600.00000085.714211INFINITYX338000.0000001371.428467INFINITYRIGHTHAND SIDE RANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2100.000000INFINITY58.7500003300.000000INFINITY300.00000042

17、00.000000INFINITY200.0000005190000.0000005106250.000000INFINITY6130000.000000469999.968750129999.9921887350000.000000822500.000000350000.000000其中，輸出內(nèi)容得含義為：“LP OPTIMUM FOUND AT STEP 4”表示LINDO在（用單純形法）4次迭代或 旋轉(zhuǎn)后得到最優(yōu)解。“OBJECTIVE FUNCTION VALUE 1） 6830500 表示最優(yōu)目標(biāo)值為 6830500?！癡ALUE”給出最優(yōu)解中各變量的值。“SLACK OR SURPLUS”給出松弛變量的值?！癉UAL PRICE”（對(duì)偶價(jià)格）列出最優(yōu)單純形表中判別數(shù)所在行的松弛變量 的系數(shù)，表示當(dāng)對(duì)應(yīng)約束有微小變動(dòng)時(shí)，目標(biāo)函數(shù)的變化率，輸