運籌學 1

1、線性規(guī)劃建模舉例與lingo軟件求解,感受lingo！,例如：,求解此問題的lingo代碼：,max=2*x1+3*x2;x1+2*x2<=8;4*x1<=16;4*x2<=12;,點擊,求解。首先出現(xiàn)求解狀態(tài)框。,變量,約束,非零變量,解的狀態(tài),解狀態(tài)擴展,消耗時間,占用基本內(nèi)存,Global optimal solution found at iteration: 5 Object

2、ive value: 14.00000 Variable Value Reduced Cost X1 4.000000 0.000000 X

3、2 2.000000 0.000000 Row Slack or Surplus Dual Price 1 14.00000 1.000000 2 0.0000

4、00 1.500000 3 0.000000 0.1250000 4 4.000000 0.000000,再次感受！,Lingo代碼？,Min=-3*x1+x2+x3;X1-2*x2+x3=3;-2*x1+x3=1;,Glo

5、bal optimal solution found at iteration: 0 Objective value: -2.000000 Variable Value Reduced Cost X1

6、 4.000000 0.000000 X2 1.000000 0.000000 X3 9.000000 0.000000 Row Slack or Surplu

7、s Dual Price 1 -2.000000 -1.000000 2 0.000000 0.3333333 3 0.000000 -0.333333

8、3 4 0.000000 -0.6666667,例1 工件加工任務(wù)分配問題,某車間有兩臺機床甲和乙，可用于加工三種工件。假定這兩臺機床的可用臺時數(shù)分別是700和800，三種工件的數(shù)量分別是300、500和400，且已知用不同機床加工單位數(shù)量的不同工件所需要的臺時數(shù)和加工費用（入下表），問：怎樣分配機床的加工任務(wù)，才能既滿足加工任務(wù)的要求，又使得總

9、加工費用最低？,三種工件的數(shù)量分別是300、500和400,模型,Lingo代碼：,min=13*x1+9*x2+10*x3+11*x4+12*x5+8*x6;x1+x4=300;x2+x5=500;x3+x6=400;0.4*x1+1.1*x2+x3<=700;0.5*x4+1.2*x5+1.3*x6<=800;,線性規(guī)劃問題建模的步驟,1、分析實際問題，弄清需要確定的未知量，在此基礎(chǔ)上假定自變量（決策變量）。

10、2、認清決策者想要達到的主要目標，據(jù)此列出目標函數(shù)。3、分析并匯總問題的限制條件，寫出約束條件。4、寫出完整的線性規(guī)劃數(shù)學模型。,例2、廠址選擇問題,考慮A、B、C三地，每地都有一定數(shù)量的原料，也消耗一定數(shù)量的產(chǎn)品。已知制成每噸產(chǎn)品需3噸原材料，各地之間的距離為：A-B：150km，A-C：100km,B-C：200km。假定每萬噸原材料運輸1km的運價是5000元,產(chǎn)品的運價為6000元。由于地區(qū)差異，在不同地方設(shè)廠的生產(chǎn)費用也不

11、同。問究竟在哪些地方設(shè)廠，規(guī)模多大，才能使總費用最小？另外，由于其他條件的限制，在B處建廠的規(guī)模不能超過5萬噸。,制成每萬噸產(chǎn)品需3萬噸原料；各地之間的距離：AB:150km;AC:100km;BC:200km;每萬噸運價：原料：5000元/km;產(chǎn)品：6000元/km。B處設(shè)廠規(guī)模小于5萬噸。,模型,Lingo代碼,min=75*x12+75*x21+50*x13+50*x31+100*x23+100*x32+150*y11+2

12、40*y12+210*y21+120*y22+160*y31+220*y32;x11+x12+x13<=20;x21+x22+x23<=16;x31+x32+x33<=24;y11+y21+y31=7;y12+y22+y32=13;x11+x21+x31=3*(y11+y12);x12+x22+x32=3*(y21+y22);x13+x23+x33=3*(y31+y32);y21+y22<=5;

13、,Global optimal solution found at iteration: 0 Objective value: 3485.000 Variable Value Reduced Cost X12

14、 0.000000 150.0000 X21 1.000000 0.000000 X13 0.000000 53.33333 X31 0.000000

15、 46.66667 X23 0.000000 28.33333 X32 0.000000 171.6667 Y11 7.000000 0.00

16、0000 Y12 0.000000 30.00000 Y21 0.000000 150.0000 Y22 5.000000 0.000000

17、 Y31 0.000000 0.000000 Y32 8.000000 0.000000 X11 20.00000 0.000000

18、 X22 15.00000 0.000000 X33 24.00000 0.000000,例3：連續(xù)投資問題,某部門在今后五年內(nèi)考慮給下列項目投資，已知：項目A:從第一年到第四每年年初需要投資，并于次年末收回本利115%；項目B：第三年初需要投資，到第五年末能收回本利125%，但最大投資額不超過4萬元；項

19、目C：第二年初需要投資，到第五年末能收回本利140%，但規(guī)定最大投資額部超過3萬元。項目D，五年內(nèi)每一年初可購買公債，于當年末歸還，并加利息6%。該部門現(xiàn)有資金10萬元，問應(yīng)如何投資使第五年末擁有的資金本利最多？,Lingo代碼,max=1.15*x4a+1.4*x2c+1.25*x3b+1.06*x5d;x1a+x1d=100000;x2a+x2c+x2d=1.06*x1d;x3a+x3b+x3d=1.15*x1a+1.06

20、*x2d;x4a+x4d=1.15*x2a+1.06*x3d;x5d=1.15*x3a+1.06*x4d;x2c<=30000;x3b<=40000;,Global optimal solution found at iteration: 0 Objective value: 143750.0

21、 Variable Value Reduced Cost X4A 45000.00 0.000000 X2C 30000.00 0.000000 X3

22、B 40000.00 0.000000 X5D 0.000000 0.000000 X1A 71698.11 0.000000 X1D 28301.8

23、9 0.000000 X2A 0.000000 0.000000 X2D 0.000000 0.3036000E-01 X3A 0.000000

24、 0.000000 X3D 42452.83 0.000000 X4D 0.000000 0.2640000E-01,復(fù)雜一點的線性規(guī)劃問題,假設(shè)某公司有6個貨棧向8個銷售商供應(yīng)小裝飾品，每一個貨棧的供應(yīng)量都是有限的，每一個銷售商的需求量必須得到滿足。該公司

25、要決定如何調(diào)運貨棧的裝飾品滿足銷售商以使總運輸成本最少。,數(shù)據(jù)：,貨棧： 1 2 3 4 5 6可供量： 60 55 51 43 41 52銷售商 1 2 3 4 5 6 7 8需求量 35 37 22 32 41 32 43

26、 38運輸成本： 1 2 3 4 5 6 7 8 1 6 2 6 7 4 2 5 9 2 4 9 5 3 8 5 8 2 3 5 2 1 9 7 4 3 3 4 7

27、 6 7 3 9 2 7 1 5 2 3 9 5 7 2 6 5 6 5 5 2 2 8 1 4 3;,模型,Matlab求解此線性規(guī)劃（代碼）：,f=[6;2;6;7;4;2;5;9;4;9;5;3;8;5;8;2;5;2;1;9;7;4;3;3;... 7;6;

28、7;3;9;2;7;1;2;3;9;5;7;2;6;5;5;5;2;2;8;1;4;3];A=[1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

29、,0,0,0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0

30、,0,0 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1];b=[60;55;51;4

31、3;41;52];Aeq=[1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0 0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0 0,0,1

32、,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0 0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0 0,0,0,0,1,0,0,0,0,0,0,0,1

33、,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0 0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0 0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1

34、,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1];beq=[35,37,22,32,41,32,43,38];lb=zeros(48,1);[x,fval]=linprog(f,A

35、,b,Aeq,beq,lb),利用lingo編程求解：,在lingo中怎么輸入？！如果按初等的輸入方法，怎么樣？煩?。。。。。。。。。。∮斜匾M新的方法：Lingo 的特點：集語言！,1、lingo中的集,在lingo中引進集的概念及定義的主要目的是為了實現(xiàn)程序的循環(huán)功能。 集：由一些對象組成的全體。 集成員的屬性：集成員可能有一個或多個與之有關(guān)聯(lián)的特征，我們把這些特征稱為屬性。例如雇員集中的每位雇員可以有一個薪水

36、屬性，也可以有一個生日屬性等等。,1、lingo中的集,Lingo中集的定義語法：setname/member_list/:attribute_list; 說明： setname為集的名稱； /member_list/為成員列表； attribute_list為屬性列表。,1、lingo中的集,集定義的例子：sets: students/John Jill, Rose Mike/: s

37、ex, age;endsets 注意：集部分以關(guān)鍵字“sets:”開始，以“endsets”結(jié)束。一個集及其屬性在模型約束中被引用之前必須定義了它們。,把上面的代碼在lingo中運行，可得到下面的結(jié)果：,Variable Value SEX( JOHN) 1.234568

38、 SEX( JILL) 1.234568 SEX( ROSE) 1.234568 SEX( MIKE) 1.234568 AGE( JOHN)

39、 1.234568 AGE( JILL) 1.234568 AGE( ROSE) 1.234568 AGE( MIKE) 1.234568,1、

40、lingo中的集,sets:w/1..6/:capacity;endsets 也定義了一個集。注意該集合成員列表時所使用方法。,把上面的代碼在lingo中運行，可得到下面的結(jié)果：,Variable Value CAPACITY( 1) 1.234568

41、 CAPACITY( 2) 1.234568 CAPACITY( 3) 1.234568 CAPACITY( 4) 1.234568 CAPACITY( 5

42、) 1.234568 CAPACITY( 6) 1.234568,1、lingo中的集,派生集（高維數(shù)組）的定義方法：setname(parent_set_list)/member_list/:attribute_list; 例如：sets: product/A B/; machine/M N/; week/1..2

43、/; allowed(product,machine,week):x;endsets,把上面的代碼在lingo中運行，可得到下面的結(jié)果：,Variable Value X( A, M, 1) 1.234568 X( A, M, 2)

44、1.234568 X( A, N, 1) 1.234568 X( A, N, 2) 1.234568 X( B, M, 1) 1.234568

45、 X( B, M, 2) 1.234568 X( B, N, 1) 1.234568 X( B, N, 2) 1.234568,2、數(shù)據(jù)部分,集合中對象的每一個屬性都是一個變量，ling

46、o程序運行完畢后所有的變量都會有一個值，變量取值的確定有兩種方法：第一，對變量進行賦值（數(shù)據(jù)部分就是解決這個問題）。 第二，沒有賦值的變量，就是決策變量。,數(shù)據(jù)部分定義方法：,數(shù)據(jù)部分以關(guān)鍵字“data:”開始，以關(guān)鍵字“enddata”結(jié)束。在這里，可以指定集成員、集的屬性。其語法如下： object_list = value_list;,例如：,sets: set1/A,B,C/: X,Y;endsets

47、data: X=1,2,3; Y=4,5,6;enddata,也可以寫成下面的形式：,sets: set1/A,B,C/: X,Y;endsetsdata: X,Y=1 4 2 5 3 6;enddata 注意：LINGO在為對象指定值時，首先在n個對象的第1個索引處依次分配數(shù)值列中的前n個對象，然后在n個對象的第2個索引處依次分配數(shù)值列中緊接著的n個對象，……

48、，以此類推。,把上面的代碼在lingo中運行，可得到下面的結(jié)果：,Variable Value X( A) 1.000000 X( B) 2.000000

49、 X( C) 3.000000 Y( A) 4.000000 Y( B) 5.000000 Y(

50、 C) 6.000000,3、初始部分,在初始部分中，可以輸入初始聲明（initialization statement），和數(shù)據(jù)部分中的數(shù)據(jù)聲明相同。對實際問題的建模時，初始部分并不起到描述模型的作用，在初始部分輸入的值僅被LINGO求解器當作初始點來用，并且僅僅對非線性模型有用。和數(shù)據(jù)部分指定變量的值不同，LINGO求解器可以自由改變初始部分初始化的變量的值。,初始部分的定義方法：,一個初始部分以“init:”開始，以

51、“endinit”結(jié)束。初始部分的初始聲明規(guī)則和數(shù)據(jù)部分的數(shù)據(jù)聲明規(guī)則相同。例如（在lingo中所有變量是不分大小寫的）： init: X, Y = 2,0.1;endinitmax=x+y;Y=@log(X);X^2+Y^2<=1;,函數(shù)： 函數(shù)運算前必須加@號,循環(huán)： @FOR(集名 [ (循環(huán)字母) [ | 循環(huán)條件]]: 表達式列表)最大： @MAX(集名 [ (循環(huán)字母) [ | 循環(huán)條件]]:

52、表達式) 最?。?@MIN(集名 [ (循環(huán)字母) [ | 循環(huán)條件]]: 表達式) 取和： @SUM(集名 [ (循環(huán)字母) [ | 循環(huán)條件]]: 表達式),運輸問題的lingo程序,sets: w/1..6/:capacity; v/1..8/:demand; links(w,v):cost,volume;endsetsdata: capacity=60 55 51 43 41 52; demand=35 3

53、7 22 32 41 32 43 38; cost=6 2 6 7 4 2 5 9 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3;enddatamin=@sum(links(i,j):cost(i,j)*volume(i,j));@for