lingo及線性規(guī)劃

1、-. z.Lingo與線性規(guī)劃線性規(guī)劃的標(biāo)準(zhǔn)形式是(1)其中稱為目標(biāo)函數(shù)，自變量稱為決策變量,不等式組(1)稱為約束條件.滿足不等式組(1)的所有的集合稱為可行域，在可行域里面使得z取最小值的稱為最優(yōu)解，最優(yōu)解對(duì)應(yīng)的函數(shù)值稱為最優(yōu)值。求解優(yōu)化模型的主要軟件有Lingo、Matlab、E*cel等。其中Lingo是一款專業(yè)求解優(yōu)化模型的軟件，有其他軟件不可替代的方便功能。本文將簡要介紹其在線性規(guī)劃領(lǐng)域的應(yīng)用。一、根本規(guī)定1、目標(biāo)函數(shù)輸入格式ma*=函數(shù)解析式；或者 min=函數(shù)解析式；2、約束條件輸入格式利用：、=、與=沒有區(qū)別。Lingo軟件默認(rèn)所以自變量都大于等于0.3、運(yùn)算加(+),減(-

2、),乘(*),除(/),乘方(*a)，要注意乘號(hào)(*)不能省略。4、變量名不區(qū)分大小寫字母，不超過32個(gè)字符，必須以字母開頭。5、標(biāo)點(diǎn)符號(hào)每個(gè)語句以分號(hào)“；完畢，感慨號(hào)“！開場的是說明語句說明語句也需要以分號(hào)“;完畢。但是，model，sets，data以“：結(jié)尾。endsets，enddata，end尾部不加任何符號(hào)。6、命令不考慮先后次序7、MODEL語句一般程序必須先輸入MODEL：表示開場輸入模型，以“END完畢。對(duì)簡單的模型，這兩個(gè)語句也可以省略。8、改變變量的取值*圍bin(變量名)；限制該變量為0或1. bnd(a,變量名,b)；限制該變量介于a,b之間.free(變量名)；允許

3、該變量為負(fù)數(shù).gin(變量名)；限制該變量為整數(shù).例1 求目標(biāo)函數(shù)的最小值，約束條件為輸入Lingo程序：min = 2*1 + 3*2;*1 + *2 = 350;*1 = 100;2*1 + *2 = 600;有兩種運(yùn)行方式：1、點(diǎn)擊工具條上的按鈕即可。2、點(diǎn)擊菜單：LINGOSolve運(yùn)行結(jié)果如下：下面對(duì)其各個(gè)局部進(jìn)展說明：Global optimal solution found：表示已找到全局最優(yōu)解。Objective value：表示最優(yōu)值的大小。可見此題函數(shù)最小值800。Infeasibilities：矛盾約束的數(shù)目。Total solver iterations:迭代次數(shù)。Va

4、riable：變量。此題有兩個(gè)變量。Value：變量對(duì)應(yīng)的最優(yōu)解，即。Reduced Cost：變量在最優(yōu)解的根底上增加一個(gè)單位，目標(biāo)函數(shù)值的改變量。例如，一個(gè)變量的Reduced Cost值為8，則當(dāng)該變量增加一個(gè)單位，在最大化最小化問題中目標(biāo)函數(shù)值將減少增大8個(gè)單位。Slack or Surplus：表示接近等于的程度，即約束離相等還差多少。在約束條件是=中，不是過剩程度。如果約束條件是=，則Slack or Surplus為0，該約束是個(gè)緊約束(或有效約束)。如果一個(gè)約束是矛盾的，即模型無可行解則Slack or surplus的值是負(fù)數(shù)。知道Slack or Surplus的值，可以幫

5、助我們發(fā)現(xiàn)優(yōu)化模型中錯(cuò)誤的約束條件。在上例中第2和第4行松弛變量均為0,說明對(duì)于最優(yōu)解來講,兩個(gè)約束(第2和4行)均取等號(hào),即都是緊約束，第3行為150，即最優(yōu)解使得第3行過剩150.Dual Price ：對(duì)偶價(jià)格的值，它表示約束條件中的常數(shù)，每增加一個(gè)單位，目標(biāo)函數(shù)值改變的數(shù)量在最大化問題中目標(biāo)函數(shù)值是增加，在最小化問題中目標(biāo)函數(shù)值是減少。比方，在上一個(gè)Min模型中第四行的1，表示2*1 + *2 = 600增加一個(gè)單位到2*1 + *2 options-general solver-dual putations:prices & ranges-ok.第二步：菜單lingo-range2、

6、靈敏度報(bào)告中常見的詞匯Current coefficient：當(dāng)前目標(biāo)函數(shù)系數(shù)Allowable increase：允許增加量Allowable decrease：允許減少量Current RHS：當(dāng)前右邊常數(shù)項(xiàng)INFINITY：表示正無窮。例1 求解以下模型：ma* = 72*1+64*2;*1+*2 = 50;12*1+8*2 = 480;3*1 = 100;并做靈敏度分析。求解報(bào)告：靈敏度分析報(bào)告：靈敏度分析報(bào)告的解讀：*1的系數(shù)變化*圍是72-8，72+24=64，96；*2的系數(shù)變化*圍是64-16，64+8=48，72。注意：*1系數(shù)的允許*圍需要*2系數(shù)64不變，反之亦然。由于目

7、標(biāo)函數(shù)的費(fèi)用系數(shù)變化并不影響約束條件，因此此時(shí)最優(yōu)基不變可以保證最優(yōu)解也不變，但最優(yōu)值變化。右邊常數(shù)項(xiàng)中，第2行原來為50，當(dāng)它在50-6.67，50+10 = 43.33，60*圍變化時(shí)，最優(yōu)基保持不變。第3行可以類似解釋。對(duì)第4行，原來為100，當(dāng)它在100-40，100+ = 60，+*圍變化時(shí)，最優(yōu)基保持不變。不過由于此時(shí)約束發(fā)生變化，最優(yōu)基即使不變，最優(yōu)解、最優(yōu)值也會(huì)發(fā)生變化。三、數(shù)據(jù)輸入對(duì)于大型的優(yōu)化問題，即自變量比擬多的時(shí)候，還像上兩節(jié)那樣輸入目標(biāo)函數(shù)和約束條件就比擬麻煩了。一般輸入數(shù)據(jù)的方法有兩種：一、建立向量、矩陣輸入；二、調(diào)用外部數(shù)據(jù)。這里僅介紹第一種方法。1、建立向量命令

8、格式：集合名稱/集合維數(shù)/：向量名稱例如：sets：set1/1.9/:*;set2/1.5/:a,b;endsets表示建立了兩類集合。第一類集合set1，維數(shù)為9，*和y是向量名。向量*=*(1), *(9),其中*(i)是*的元素。第二類集合set2，維數(shù)為5，a和b都是向量名。向量a=a(1), a (5),其中a (i)是a的元素。向量b=b(1), b(5),其中b (i)是b的元素。2、建立矩陣命令格式：集合名稱集合1，集合2/：矩陣名稱例如：sets：set1/1.3/:*;set2/1.4/:a;link(set1, set2):A;endsets表示建立了一個(gè)矩陣類link

9、，其矩陣的階數(shù)為，A是具體的矩陣名。有兩個(gè)命令是比擬常見的：求和語句:sum(集合名(i):含集合名(i)的語句);循環(huán)語句:for(集合名(i):循環(huán)的語句);例3：求目標(biāo)函數(shù)的最小值，約束條件為輸入Lingo程序：model:sets:set1/1.2/:c,*;set2/1.3/:b;link(set2,set1):A;endsetsma*=sum(set1(i):c(i)*(i);for(set2(i):sum(link(i,j):A(i,j)*(j)=b(i);data:c=11 15;A=20 30 30 25 30 25;b=360 2000 300;enddataend運(yùn)行結(jié)果

10、報(bào)告：例4、*地區(qū)有三個(gè)蔬菜生產(chǎn)基地，估計(jì)每年可供給本地區(qū)的蔬菜量表為：生產(chǎn)基地ABC蔬菜生產(chǎn)量(噸)783有四個(gè)地市需要該類蔬菜，需求表為：地區(qū)甲乙丙丁蔬菜生產(chǎn)量(噸)6633如果從各蔬菜生產(chǎn)基地到各地市的每噸蔬菜的運(yùn)價(jià)表(單位：萬元/噸)為:地市生產(chǎn)基地甲乙丙丁A5879B49107C8429為了降低運(yùn)輸費(fèi)，需要合理調(diào)撥資源.根據(jù)以上資料表制訂一個(gè)使總的運(yùn)費(fèi)為最少的蔬菜調(diào)撥方案(2)如果有時(shí)機(jī)增加生產(chǎn)基地的產(chǎn)量1噸，問應(yīng)當(dāng)優(yōu)先增加那個(gè)基地的產(chǎn)量？ (3)如果將A到乙市的運(yùn)價(jià)減少為5萬元/噸，問這會(huì)影響最優(yōu)的調(diào)撥方案嗎？設(shè)：第i個(gè)蔬菜生產(chǎn)基地，分別對(duì)應(yīng)生產(chǎn)基地A，B，C；：第i個(gè)蔬菜需求地，

11、分別對(duì)應(yīng)蔬菜需求地市甲、乙、丙、?。唬嚎傔\(yùn)輸費(fèi)用；：表示的是從第i個(gè)生產(chǎn)基地向第j個(gè)地市運(yùn)輸?shù)氖卟藬?shù)量；：表示的是從第i個(gè)生產(chǎn)基地向第j個(gè)地市運(yùn)輸蔬菜的運(yùn)價(jià)；：第i個(gè)蔬菜生產(chǎn)基地的蔬菜產(chǎn)量；：第j個(gè)地市的蔬菜需求量；則有優(yōu)化模型：輸入Lingo程序求解模型：model:sets:set1/1.3/:b;set2/1.4/:q;link(set1,set2):c,*;endsetsmin=sum(link(i,j):c(i,j)*(i,j);for(set1(i):sum(link(i,j): *(i,j)=b(i);for(set2(j):sum(link(i,j): *(i,j)=q(j);

12、data:c=5,8,7,9 4,9,10,7 8,4,2,9;b=7,8,3;q=6,6,3,3;enddataend運(yùn)行結(jié)果如下：Global optimal solution found. Objective value: 100.0000 Infeasibilities: 0.000000 Total solver iterations: 6 Variable Value Reduced Cost B( 1) 7.000000 0.000000 B( 2) 8.000000 0.000000 B( 3) 3.000000 0.000000 Q( 1) 6.000000 0.000000

13、 Q( 2) 6.000000 0.000000 Q( 3) 3.000000 0.000000 Q( 4) 3.000000 0.000000 C( 1, 1) 5.000000 0.000000 C( 1, 2) 8.000000 0.000000 C( 1, 3) 7.000000 0.000000 C( 1, 4) 9.000000 0.000000 C( 2, 1) 4.000000 0.000000C( 2, 2) 9.000000 0.000000 C( 2, 3) 10.00000 0.000000 C( 2, 4) 7.000000 0.000000 C( 3, 1) 8.0

14、00000 0.000000 C( 3, 2) 4.000000 0.000000 C( 3, 3) 2.000000 0.000000 C( 3, 4) 9.000000 0.000000 *( 1, 1) 1.000000 0.000000 *( 1, 2) 6.000000 0.000000 *( 1, 3) 0.000000 1.000000 *( 1, 4) 0.000000 1.000000*( 2, 1) 5.000000 0.000000 *( 2, 2) 0.000000 2.000000 *( 2, 3) 0.000000 5.000000 *( 2, 4) 3.00000

15、0 0.000000 *( 3, 1) 0.000000 7.000000 *( 3, 2) 0.000000 0.000000 *( 3, 3) 3.000000 0.000000 *( 3, 4) 0.000000 5.000000 Row Slack or Surplus Dual Price1 100.0000 -1.000000 2 0.000000 0.000000 3 0.000000 1.000000 4 0.000000 4.000000 5 0.000000 -5.000000 6 0.000000 -8.000000 7 0.000000 -6.000000 8 0.00

16、0000 -8.000000從該報(bào)告可以得到：最優(yōu)的調(diào)撥方案為：地市生產(chǎn)基地甲乙丙丁A1600B5003C0030 2、從Dual Price來看生產(chǎn)基地A的供給量增加1個(gè)單位，費(fèi)用不變；生產(chǎn)基地B的供給量增加1個(gè)單位，費(fèi)用減少1；生產(chǎn)基地C的供給量增加1個(gè)單位，費(fèi)用減少4；城市甲的需求量增加1個(gè)單位，費(fèi)用減少-5，即增加5；城市乙的需求量增加1個(gè)單位，費(fèi)用減少-8，即增加8；城市丙的需求量增加1個(gè)單位，費(fèi)用減少-6，即增加6；城市丁的需求量增加1個(gè)單位，費(fèi)用減少-8，即增加8；3、從Slack or Surplus來看，所有的約束都是緊約束?？梢娒總€(gè)生產(chǎn)基地的蔬菜都全部運(yùn)完。然后做靈敏度分析

17、：Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease *( 1, 1) 5.000000 1.000000 1.000000 *( 1, 2) 8.000000 1.000000 4.000000 *( 1, 3) 7.000000 INFINITY 1.000000 *( 1, 4) 9.000000 INFINITY 1.000000 *( 2, 1) 4.000000 1

18、.000000 1.000000 *( 2, 2) 9.000000 INFINITY 2.000000 *( 2, 3) 10.00000 INFINITY 5.000000 *( 2, 4) 7.000000 1.000000 INFINITY *( 3, 1) 8.000000 INFINITY 7.000000 *( 3, 2) 4.000000 4.000000 1.000000 *( 3, 3) 2.000000 1.000000 INFINITY *( 3, 4) 9.000000 INFINITY 5.000000 Righthand Side Ranges Row Curre

19、nt Allowable Allowable RHS Increase Decrease 2 7.000000 INFINITY 0.0 3 8.000000 1.000000 0.0 4 3.000000 6.000000 0.0 5 6.000000 0.0 1.000000 6 6.000000 0.0 6.000000 7 3.000000 0.0 3.000000 8 3.000000 0.0 1.000000可以得到以下信息：1、運(yùn)價(jià)在下面的*圍內(nèi)最優(yōu)的調(diào)撥方案不變:地市生產(chǎn)基地甲乙丙丁A4,64,96, +8, +B3,57, +5, +0,8C1, +3,80,34, +2、生

20、產(chǎn)基地的產(chǎn)量在下面的*圍內(nèi)最優(yōu)基不變:生產(chǎn)基地ABC蔬菜生產(chǎn)量(噸)7, +8,96,93、四個(gè)地市的需求量在下面的*圍內(nèi)最優(yōu)基不變:地區(qū)甲乙丙丁蔬菜生產(chǎn)量(噸)5,60,60,32,3四、收集的一些問題1、福特在L.A. 和 Detroit生產(chǎn)汽車,在Atlanta有一倉庫,供給點(diǎn)為Houston 和 Tampa;城市間每輛汽車運(yùn)輸費(fèi)用見下表. L.A.的生產(chǎn)能力為1100輛, Detroit的生產(chǎn)能力為2900輛. Houston汽車需求量為2400輛, Tampa汽車需求量為1500輛,L.ADETROITATLANTAHOUSTONTAMPAL.A.014010090225DETROIT1450111110119ATLANTA105115011378HOUSTON891091210-TAMPA21011782-0如何確定運(yùn)輸和生產(chǎn)方案,才能滿足Houston 和 Tempa的需求且費(fèi)用最低.2、設(shè)有三個(gè)化肥廠供給四個(gè)地區(qū)的農(nóng)用化肥.假定等量的化肥在這些地區(qū)使用效果一樣.各化肥廠年產(chǎn)量,各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià)(萬元/萬噸)如下表所示.試求出總的運(yùn)費(fèi)最省的化肥調(diào)撥方案.需求地區(qū)化肥廠IIIIIIIV產(chǎn)量(萬噸)A1613221750B1413191560C192023制止50最低需求(萬噸)3070010最高需求(萬噸