物流運籌學(xué)課件：用Lingo求解整數(shù)規(guī)劃模型

用Lingo求解整數(shù)規(guī)劃模型變量定界函數(shù):@bin(x):限制x為0或1.@gin(x):限制x為整數(shù).例

1用Lingo軟件求解0-1規(guī)劃問題max=2*x1+5*x2+3*x3+4*x4;-4*x1+x2+x3+x4>=0;-2*x1+4*x2+2*x3+4*x4>=1;x1+x2-x3+x4>=1;@bin(x1);@bin(x2);@bin(x3);@bin(x4);Lingo程序:一、用Lingo求解規(guī)劃問題例

2用Lingo軟件求解整數(shù)規(guī)劃問題min=2*x1+5*x2+3*x3;-4*x1-x2+x3>=0;-2*x1+4*x2-2*x3>=2;x1-x2+x3>=2;@gin(x1);@gin(x2);@gin(x3);Lingo程序:例3：6人指派問題人工作1工作2工作3工作4工作5工作61201516547217153312863912181630134128112719145-7102110326---611136個人做6項工作的收益情況說明：其中“-”表示某人無法做某項工作。，否則，，否則，model:!AssignmentProblemModel;sets:Flight/1..6/;Assign(Flight,Flight):c,x;endsets!Hereisincomematrix;data:c=20151654717153312869121816301312811271914-99710211032-99-99-9961113;enddata!Maximizevalueofassignments;max=@sum(Assign:c*x);@for(Flight(i):!Eachimustbeassignedtosomej;@sum(Flight(j):x(i,j))=1;!Eachimustreceiveanassignment;@sum(Flight(j):x(j,i))=1;);end補充知識：Lingo循環(huán)編程語句(1)集合的定義包括如下參數(shù):1)集合的名稱.命名規(guī)則:以字母開頭,后面是字母或下劃線.字母不區(qū)分大小寫.2)集合包含的元素(可選).3)集合中元素的所有屬性(可選).例4Math,English,totalsets:endsetsstudentsJohn,Jill,Rose,Mikesets:students/John,Jill,Rose,Mike/:Math,English,total;endsets(2)數(shù)據(jù)賦值例4data:enddatadata:Math=80,85,90,70;English=75,80,72,60;enddata格式:(1)集合的定義例4sets:students/John,Jill,Rose,Mike/:Math,English,total;endsets(3)集合的循環(huán)函數(shù)集合的循環(huán)函數(shù)可以使所有的元素重復(fù)完成一些操作.函數(shù)函數(shù)功能@for形成集合所有元素需滿足的約束條件@sum計算集合中元素所在表達式的和@min計算集合中元素所在表達式的最小值@max計算集合中元素所在表達式的最大值maxM=@max(students(i):Math);maxE=@max(students(i):English);averageM=@sum(students(i):Math)/4;@for(students(i):total(i)=Math(i)+English(i));例4!數(shù)學(xué)的最高分;!英語的最高分;!數(shù)學(xué)的平均分;!每個學(xué)生數(shù)學(xué)與英語分?jǐn)?shù)之和.(4)衍生集合的定義.包括如下參數(shù):1)衍生集合的名稱.3)衍生集合包含的元素(可選).4)集合中元素的所有屬性(可選).例5link2)衍生集合的父集合名稱.sets:ren/A,B,C,D/:rent;job/1..5/:jobt;link(ren,job):time;endsetsrenjobtime注:若沒有指明元素列表,LINGO將用父集合元素的所有組合作為衍生集合的元素.(A,1),(A,2),(A,3),(A,4)(A,5)(B,1),(B,2),(B,3),(B,4)(B,5)(C,1),(C,2),(C,3),(C,4)(C,5)(D,1),(D,2),(D,3),(D,4)(D,5)補充知識：集合的基本用法和LINGO模型的基本要素

理解LINGO建模語言最重要的是理解集合（Set）及其屬性（Attribute）的概念。例SAILCO公司需要決定下四個季度的帆船生產(chǎn)量。下四個季度的帆船需求量分別是40條，60條，75條，25條，這些需求必須按時滿足。每個季度正常的生產(chǎn)能力是40條帆船，每條船的生產(chǎn)費用為400美元。如果加班生產(chǎn)，每條船的生產(chǎn)費用為450美元。每個季度末，每條船的庫存費用為20美元。假定生產(chǎn)提前期為0，初始庫存為10條船。如何安排生產(chǎn)可使總費用最小？DEM,RP,OP,INV對每個季度都應(yīng)該有一個對應(yīng)的值，也就說他們都應(yīng)該是一個由4個元素組成的數(shù)組，其中DEM是已知的，而RP,OP,INV是未知數(shù)。

第一季度第二季度第三季度第四季度DEM:需求量(為已知)40607525RP:正常生產(chǎn)的產(chǎn)量OP:加班生產(chǎn)的產(chǎn)量INV:庫存量總費用：四個季度的（生產(chǎn)費用+加班費用+庫存費用）設(shè)問題的模型(可以看出是LP模型)目標(biāo)函數(shù)是所有費用的和

約束條件主要有兩個：1）能力限制：2）產(chǎn)品數(shù)量的平衡方程：加上變量的非負(fù)約束正常生產(chǎn)的產(chǎn)量加班產(chǎn)量庫存量注：LINDO中沒有數(shù)組，只能對每個季度分別定義變量，如正常產(chǎn)量就要有RP1，RP2，RP3，RP44個變量等。寫起來就比較麻煩，尤其是更多(如1000個季度)的時候。記四個季度組成的集合QUARTERS={1，2，3，4}，它們就是上面數(shù)組的下標(biāo)集合，而數(shù)組DEM,RP,OP,INV對集合QUARTERS中的每個元素1，2，3，4分別對應(yīng)于一個值。LINGO正是充分利用了這種數(shù)組及其下標(biāo)的關(guān)系，引入了“集合”及其“屬性”的概念，把QUARTERS={1，2，3，4}稱為集合，把DEM,RP,OP,INV稱為該集合的屬性(即定義在該集合上的屬性)。QUARTERS集合的屬性DEMRPOPINVQUARTERS集合2341

集合及其屬性集合元素及集合的屬性確定的所有變量集合QUARTERS的元素1234定義在集合QUARTERS上的屬性DEMDEM(1)DEM(2)DEM(3)DEM(4)RPRP(1)RP(2)RP(3)RP(4)OPOP(1)OP(2)OP(3)OP(4)INVINV(1)INV(2)INV(3)INV(4)LINGO中定義集合及其屬性LP模型在LINGO中的一個典型輸入方式以“MODEL：”開始以“END”結(jié)束集合定義部分從(“SETS：”到“ENDSETS”)：定義集合及其屬性集合定義部分從(“DATA：”到“ENDDATA”)給出優(yōu)化目標(biāo)和約束目標(biāo)函數(shù)的定義方式對語句中冒號“：”后面的表達式，按照“：”前面的集合指定的下標(biāo)（元素）進行求和。本例中目標(biāo)函數(shù)也可以等價地寫成@SUM(QUARTERS(i):400*RP(i)+450*OP(i)+20*INV(i))，“@SUM”相當(dāng)于求和符號“∑”，由于本例中目標(biāo)函數(shù)對集合QUARTERS的所有元素(下標(biāo))都要求和，所以可以將下標(biāo)i省去。min=@sum(Quarters:400*RP+450*OP+20*INV);@SUM(集合（下標(biāo)）：關(guān)于集合的屬性的表達式)約束的定義方式循環(huán)函數(shù)@FOR(集合(下標(biāo))：關(guān)于集合的屬性的約束關(guān)系式)對冒號“：”前面的集合的每個元素（下標(biāo)），冒號“：”后面的約束關(guān)系式都要成立本例中，每個季度正常的生產(chǎn)能力是40條帆船，這正是語句“@FOR(QUARTERS(I):RP(I)<40);”的含義。這個語句可以簡化成“@FOR(QUARTERS:RP<40);”。@for(quarters(I):RP(I)<40);@For(Quarters(I)|I#GT#1:INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););對下標(biāo)集合的元素（下標(biāo)i）增加了一個邏輯關(guān)系式“i#GT#1”（這個限制條件與集合之間有一個豎線“|”分開，稱為過濾條件）。限制條件“I#GT#1”是一個邏輯表達式，意思就是I>1；“#GT#”是邏輯運算符號，意思是“大于（GreaterThan的字首字母縮寫）”。約束的定義方式問題的求解：運行菜單命令“LINGO|Solve”全局最優(yōu)解RP=(40,40,40,25),OP=(0,10,35,0)最小成本=78450Lingo模型的基本結(jié)構(gòu)（1）集合段（SETS）：

sets:Quarters/1,2,3,4/:DEM,RP,OP,INV,I;endsets或者sets:Quarters/1..4/:DEM,RP,OP,INV,I;endsets（2）目標(biāo)與約束段：

min=@sum(Quarters:400*RP+450*OP+20*INV);@For(quarters(I):RP(I)<40);@For(Quarters(I)|I#GT#1:INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););INV(1)=10+RP(1)+OP(1)-DEM(1);（3）數(shù)據(jù)段(DATA)：DATA:DEM=40,60,75,25;（或?qū)懗蒁EM=40607525；）Enddata（4）初始段(INIT)：以“INIT:”開始，“ENDINIT”結(jié)束，對集合的屬性(數(shù)組)定義初值(因為求解算法一般是迭代算法，所以用戶如果能給出一個比較好的迭代初值，對提高算法的計算效果是有益的)。如果有一個接近最優(yōu)解的初值，對LINGO求解模型是有幫助的。定義初值的格式為：“attribute（屬性）=value_list（常數(shù)列表）；”這與數(shù)據(jù)段中的用法是類似的。上例中沒有初始化部分，我們將在下一個例子中舉例說明。（5）計算段(CALC)：以“CALC:”開始，“ENDCALC”結(jié)束，對一些原始數(shù)據(jù)進行計算處理。在實際問題中，輸入的數(shù)據(jù)通常是原始數(shù)據(jù)，不一定能在模型中直接使用，可以在這個段對這些原始數(shù)據(jù)進行一定的“預(yù)處理”，得到模型中真正需要的數(shù)據(jù)。例如上例，如果希望得到全年的總需求和季度平均需求，可以增加這個段：CALC:T_DEM=@SUM(quarters:DEM);!總需求;A_DEM=T_DEM/@size(quarters);!平均需求;ENDCALC在計算段中也可以使用集合函數(shù)（其中函數(shù)@size(quarters)表示集合quarters的元素個數(shù)，這里也就是4）。這時，變量T_DEM的值就是總需求，A_DEM的值就是平均需求（如果需要的話，這兩個變量就可以在程序的其它地方作為常數(shù)使用了）。注：上面的兩個語句不能交換順序，因為計算A_DEM必須要用到T_DEM的值。此外，在計算段中只能直接使用賦值語句，而不能包含需要經(jīng)過解方程或經(jīng)過求解優(yōu)化問題以后才能決定的變量。例4現(xiàn)有五名工人甲,乙,丙,丁,戊,完成五項工作A,B,C,D,E,所需時間列表如下

工作時間(小時)工人ABCDE甲10.521.754乙2131.53.5丙1.751.52.513丁2.521.50.54戊11.5223例5：人員選拔問題3571.92隊員號碼身高/m1位置1.881.851.80中鋒前鋒前鋒后衛(wèi)4681.90隊員號碼身高/m2位置1.861.831.78中鋒前鋒后衛(wèi)后衛(wèi)同時,要求出場陣容必須滿足以下條件:中鋒只能有一個上場;(2)至少有一名后衛(wèi);(3)如果1號隊員和4號隊員都上場,則6號隊員不能上場;(4)2號隊員和6號隊員必須至少保留一個不出場.如何確定符合要求的出場陣容?作業(yè)題

某城市的巡邏大隊要求每天的各個時間段都有一定數(shù)量的警員值班,以便隨時處理突發(fā)事件,每人連續(xù)工作6h,中間不休息.如表所示是一天8個班次所需值班警員的人數(shù)情況統(tǒng)計:現(xiàn)在在不考慮時間段中警員上班和下班的情況下,巡邏大隊至少需要多少警員才能滿足值班需要?人員安排問題班次時間段人數(shù)班次時間段人數(shù)16:00～9:0070518:00～21:008029:00～12:0080621:00～24:00100312:00～15:0065724:00～3:00120415:00～18: