Lingo與線性規(guī)劃.docx

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

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

3、變量名)； 允許該變量為負數(shù).gin(變量名)； 限制該變量為整數(shù).例1 求目標函數(shù)的最小值，約束條件為輸入Lingo程序：min = 2*x1 + 3*x2;x1 + x2 = 350;x1 = 100;2*x1 + x2 = 600;有兩種運行方式：1、點擊工具條上的按鈕 即可。2、點擊菜單：LINGOSolve運行結(jié)果如下：下面對其各個部分進行說明：Global optimal solution found：表示已找到全局最優(yōu)解。Objective value：表示最優(yōu)值的大小?？梢姳绢}函數(shù)最小值800。 Infeasibilities：矛盾約束的數(shù)目。Total solver iter

4、ations:迭代次數(shù)。 Variable：變量。本題有兩個變量。 Value：變量對應(yīng)的最優(yōu)解，即。Reduced Cost：變量在最優(yōu)解的基礎(chǔ)上增加一個單位，目標函數(shù)值的改變量。例如，一個變量的Reduced Cost值為8，那么當該變量增加一個單位，在最大化（最小化）問題中目標函數(shù)值將減少（增大）8個單位。Slack or Surplus：表示接近等于的程度，即約束離相等還差多少。在約束條件是=中，不是過剩程度。如果約束條件是=，則Slack or Surplus為0，該約束是個緊約束(或有效約束)。如果一個約束是矛盾的，即模型無可行解則Slack or surplus的值是負數(shù)。知道S

5、lack or Surplus的值，可以幫助我們發(fā)現(xiàn)優(yōu)化模型中錯誤的約束條件。在上例中第2和第4行松弛變量均為0,說明對于最優(yōu)解來講,兩個約束(第2和4行)均取等號,即都是緊約束，第3行為150，即最優(yōu)解使得第3行過剩150.Dual Price ：對偶價格的值，它表示約束條件中的常數(shù)，每增加一個單位，目標函數(shù)值改變的數(shù)量（在最大化問題中目標函數(shù)值是增加，在最小化問題中目標函數(shù)值是減少）。比如，在上一個Min模型中第四行的1，表示2*x1 + x2 = 600增加一個單位到2*x1 + x2 options-general solver-dual computations:prices & r

6、anges-ok.第二步：菜單lingo-range2、靈敏度報告中常見的詞匯Current coefficient：當前目標函數(shù)系數(shù)Allowable increase：允許增加量Allowable decrease：允許減少量Current RHS：當前右邊常數(shù)項INFINITY：表示正無窮。例1 求解下列模型：max = 72*x1+64*x2;x1+x2 = 50;12*x1+8*x2 = 480;3*x1 = 100;并做靈敏度分析。求解報告：靈敏度分析報告：靈敏度分析報告的解讀：x1的系數(shù)變化范圍是（72-8，72+24）=（64，96）；x2的系數(shù)變化范圍是（64-16，64+8

7、）=（48，72）。注意：x1系數(shù)的允許范圍需要x2系數(shù)64不變，反之亦然。由于目標函數(shù)的費用系數(shù)變化并不影響約束條件，因此此時最優(yōu)基不變可以保證最優(yōu)解也不變，但最優(yōu)值變化。右邊常數(shù)項中，第2行原來為50，當它在50-6.67，50+10 = 43.33，60范圍變化時，最優(yōu)基保持不變。第3行可以類似解釋。對第4行，原來為100，當它在100-40，100+ = 60，+范圍變化時，最優(yōu)基保持不變。不過由于此時約束發(fā)生變化，最優(yōu)基即使不變，最優(yōu)解、最優(yōu)值也會發(fā)生變化。 三、數(shù)據(jù)輸入對于大型的優(yōu)化問題，即自變量比較多的時候，還像上兩節(jié)那樣輸入目標函數(shù)和約束條件就比較麻煩了。一般輸入數(shù)據(jù)的方法有兩

8、種：一、建立向量、矩陣輸入；二、調(diào)用外部數(shù)據(jù)。這里僅介紹第一種方法。1、建立向量命令格式：集合名稱/集合維數(shù)/：向量名稱例如：sets：set1/1.9/:x;set2/1.5/:a,b;endsets表示建立了兩類集合。第一類集合set1，維數(shù)為9，x和y是向量名。向量x=（x(1), x(9)）,其中x(i)是x的元素。第二類集合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/:x;se

9、t2/1.4/:a;link(set1, set2):A;endsets表示建立了一個矩陣類link，其矩陣的階數(shù)為，A是具體的矩陣名。有兩個命令是比較常見的：求和語句:sum(集合名(i):含集合名(i)的語句);循環(huán)語句:for(集合名(i):循環(huán)的語句);例3：求目標函數(shù)的最小值，約束條件為輸入Lingo程序：model:sets:set1/1.2/:c,x;set2/1.3/:b;link(set2,set1):A;endsetsmax=sum(set1(i):c(i)*x(i);for(set2(i):sum(link(i,j):A(i,j)*x(j)=b(i);data:c=11

10、15;A=20 30 30 25 30 25;b=360 2000 300;enddataend運行結(jié)果報告：例4、某地區(qū)有三個蔬菜生產(chǎn)基地，估計每年可供應(yīng)本地區(qū)的蔬菜量表為：生產(chǎn)基地ABC蔬菜生產(chǎn)量(噸)783有四個地市需要該類蔬菜，需求表為：地區(qū)甲乙丙丁蔬菜生產(chǎn)量(噸)6633如果從各蔬菜生產(chǎn)基地到各地市的每噸蔬菜的運價表(單位：萬元/噸)為: 地市生產(chǎn)基地甲乙丙丁A5879B49107C8429為了降低運輸費，需要合理調(diào)撥資源.(1) 根據(jù)以上資料表制訂一個使總的運費為最少的蔬菜調(diào)撥方案(2)如果有機會增加生產(chǎn)基地的產(chǎn)量1噸，問應(yīng)當優(yōu)先增加那個基地的產(chǎn)量？ (3)如果將A到乙市的運價減少

11、為5萬元/噸，問這會影響最優(yōu)的調(diào)撥方案嗎？設(shè)：第i個蔬菜生產(chǎn)基地，分別對應(yīng)生產(chǎn)基地A，B，C；：第i個蔬菜需求地，分別對應(yīng)蔬菜需求地市甲、乙、丙、?。唬嚎傔\輸費用；：表示的是從第i個生產(chǎn)基地向第j個地市運輸?shù)氖卟藬?shù)量；：表示的是從第i個生產(chǎn)基地向第j個地市運輸蔬菜的運價；：第i個蔬菜生產(chǎn)基地的蔬菜產(chǎn)量；：第j個地市的蔬菜需求量；那么有優(yōu)化模型：輸入Lingo程序求解模型：model:sets:set1/1.3/:b;set2/1.4/:q;link(set1,set2):c,x;endsetsmin=sum(link(i,j):c(i,j)*x(i,j);for(set1(i):sum(lin

12、k(i,j): x(i,j)=b(i);for(set2(j):sum(link(i,j): x(i,j)=q(j);data:c=5,8,7,9 4,9,10,7 8,4,2,9;b=7,8,3;q=6,6,3,3;enddataend運行結(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.0000

13、00 0.000000 B( 3) 3.000000 0.000000 Q( 1) 6.000000 0.000000 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.000000 C( 2, 2) 9.000000 0.000000 C( 2,

14、3) 10.00000 0.000000 C( 2, 4) 7.000000 0.000000 C( 3, 1) 8.000000 0.000000 C( 3, 2) 4.000000 0.000000 C( 3, 3) 2.000000 0.000000 C( 3, 4) 9.000000 0.000000 X( 1, 1) 1.000000 0.000000 X( 1, 2) 6.000000 0.000000 X( 1, 3) 0.000000 1.000000 X( 1, 4) 0.000000 1.000000 X( 2, 1) 5.000000 0.000000 X( 2, 2)

15、0.000000 2.000000 X( 2, 3) 0.000000 5.000000 X( 2, 4) 3.000000 0.000000 X( 3, 1) 0.000000 7.000000 X( 3, 2) 0.000000 0.000000 X( 3, 3) 3.000000 0.000000 X( 3, 4) 0.000000 5.000000 Row Slack or Surplus Dual Price 1 100.0000 -1.000000 2 0.000000 0.000000 3 0.000000 1.000000 4 0.000000 4.000000 5 0.000

16、000 -5.000000 6 0.000000 -8.000000 7 0.000000 -6.000000 8 0.000000 -8.000000從該報告可以得到：1、 最優(yōu)的調(diào)撥方案為： 地市生產(chǎn)基地甲乙丙丁A1600B5003C0030 2、從Dual Price來看 生產(chǎn)基地A的供應(yīng)量增加1個單位，費用不變；生產(chǎn)基地B的供應(yīng)量增加1個單位，費用減少1；生產(chǎn)基地C的供應(yīng)量增加1個單位，費用減少4；城市甲的需求量增加1個單位，費用減少-5，即增加5；城市乙的需求量增加1個單位，費用減少-8，即增加8；城市丙的需求量增加1個單位，費用減少-6，即增加6；城市丁的需求量增加1個單位，費用減

17、少-8，即增加8；3、從Slack or Surplus來看，所有的約束都是緊約束?？梢娒總€生產(chǎn)基地的蔬菜都全部運完。然后做靈敏度分析：Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X( 1, 1) 5.000000 1.000000 1.000000 X( 1, 2) 8.000000 1.000000 4.000000 X( 1, 3) 7.000000 INFINI

18、TY 1.000000 X( 1, 4) 9.000000 INFINITY 1.000000 X( 2, 1) 4.000000 1.000000 1.000000 X( 2, 2) 9.000000 INFINITY 2.000000 X( 2, 3) 10.00000 INFINITY 5.000000 X( 2, 4) 7.000000 1.000000 INFINITY X( 3, 1) 8.000000 INFINITY 7.000000 X( 3, 2) 4.000000 4.000000 1.000000 X( 3, 3) 2.000000 1.000000 INFINITY

19、X( 3, 4) 9.000000 INFINITY 5.000000 Righthand Side Ranges Row Current 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、運價在下面的范圍內(nèi)最

20、優(yōu)的調(diào)撥方案不變: 地市生產(chǎn)基地甲乙丙丁A4,64,96, +8, +B3,57, +5, +0,8C1, +3,80,34, +2、生產(chǎn)基地的產(chǎn)量在下面的范圍內(nèi)最優(yōu)基不變:生產(chǎn)基地ABC蔬菜生產(chǎn)量(噸)7, +8,96,93、四個地市的需求量在下面的范圍內(nèi)最優(yōu)基不變:地區(qū)甲乙丙丁蔬菜生產(chǎn)量(噸)5,60,60,32,3四、收集的一些問題1、福特在L.A. 和 Detroit生產(chǎn)汽車,在Atlanta有一倉庫,供應(yīng)點為Houston 和 Tampa;城市間每輛汽車運輸費用見下表. L.A.的生產(chǎn)能力為1100輛, Detroit的生產(chǎn)能力為2900輛. Houston汽車需求量為2400輛,

21、Tampa汽車需求量為1500輛,L.ADETROITATLANTAHOUSTONTAMPAL.A.014010090225DETROIT1450111110119ATLANTA105115011378HOUSTON891091210-TAMPA21011782-0如何確定運輸和生產(chǎn)方案,才能滿足Houston 和 Tempa的需求且費用最低.2、設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥.假定等量的化肥在這些地區(qū)使用效果相同.各化肥廠年產(chǎn)量,各地區(qū)年需要量及從各化肥廠到各地區(qū)運送單位化肥的運價(萬元/萬噸)如下表所示.試求出總的運費最省的化肥調(diào)撥方案. 需求地區(qū)化肥廠IIIIIIIV產(chǎn)量(萬噸)A1613221750B1413191560C192023禁止50最低需求(萬噸)3070010最高需求(萬噸