运筹学实例分析及lingo求解

1、运筹学实例分析及lingo求解一、线性规划某公司有6个仓库，库存货物总数分别为60、55、51、43、41、52，现有8个客户各要一批货，数量分别为35，37，22，32，41，32，43，38。各供货仓库到8个客户处的单位货物运输价见表V1V2V3V4V5V6V7V8W162674258W249538582W352197433W476739271W523957265W655228143试确定各仓库到各客户处的货物调运数量，使总的运输费用最小。解：设表示从第个仓库到第个客户的货物运量。表示从第个仓库到第个客户的单位货物运价，表示第个仓库的最大供货量，表示第个客户的订货量。目标函数是使总运输费用

2、最少，约束条件有三个：1、各仓库运出的货物总量不超过其库存数2、各客户收到的货物总量等于其订货数量3、非负约束数学模型为：编程如下：model:Sets:Wh/w1.w6/:ai;Vd/v1.v8/:dj;links(wh,vd):c,x;endsetsData: ai=60,55,51,43,41,52;dj=35,37,22,32,41,32,43,38;c=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(

3、i,j):c(i,j)*x(i,j);for(wh(i):sum(vd(j):x(i,j)<=ai(i);for(vd(j):sum(wh(i):x(i,j)=dj(j);end Global optimal solution found. Objective value: 664.0000 Total solver iterations: 0 Variable Value Reduced Cost AI( W1) 60.00000 0.000000 AI( W2) 55.00000 0.000000 AI( W3) 51.00000 0.000000 AI( W4) 43.00000

4、0.000000 AI( W5) 41.00000 0.000000 AI( W6) 52.00000 0.000000 DJ( V1) 35.00000 0.000000 DJ( V2) 37.00000 0.000000 DJ( V3) 22.00000 0.000000 DJ( V4) 32.00000 0.000000 DJ( V5) 41.00000 0.000000 DJ( V6) 32.00000 0.000000 DJ( V7) 43.00000 0.000000 DJ( V8) 38.00000 0.000000 C( W1, V1) 6.000000 0.000000 C(

5、 W1, V2) 2.000000 0.000000 C( W1, V3) 6.000000 0.000000 C( W1, V4) 7.000000 0.000000 C( W1, V5) 4.000000 0.000000 C( W1, V6) 2.000000 0.000000 C( W1, V7) 5.000000 0.000000 C( W1, V8) 9.000000 0.000000 C( W2, V1) 4.000000 0.000000 C( W2, V2) 9.000000 0.000000 C( W2, V3) 5.000000 0.000000 C( W2, V4) 3

6、.000000 0.000000 C( W2, V5) 8.000000 0.000000 C( W2, V6) 5.000000 0.000000 C( W2, V7) 8.000000 0.000000 C( W2, V8) 2.000000 0.000000 C( W3, V1) 5.000000 0.000000 C( W3, V2) 2.000000 0.000000 C( W3, V3) 1.000000 0.000000 C( W3, V4) 9.000000 0.000000 C( W3, V5) 7.000000 0.000000 C( W3, V6) 4.000000 0.

7、000000 C( W3, V7) 3.000000 0.000000 C( W3, V8) 3.000000 0.000000 C( W4, V1) 7.000000 0.000000 C( W4, V2) 6.000000 0.000000 C( W4, V3) 7.000000 0.000000 C( W4, V4) 3.000000 0.000000 C( W4, V5) 9.000000 0.000000 C( W4, V6) 2.000000 0.000000 C( W4, V7) 7.000000 0.000000 C( W4, V8) 1.000000 0.000000 C(

8、W5, V1) 2.000000 0.000000 C( W5, V2) 3.000000 0.000000 C( W5, V3) 9.000000 0.000000 C( W5, V4) 5.000000 0.000000 C( W5, V5) 7.000000 0.000000 C( W5, V6) 2.000000 0.000000 C( W5, V7) 6.000000 0.000000 C( W5, V8) 5.000000 0.000000 C( W6, V1) 5.000000 0.000000 C( W6, V2) 5.000000 0.000000 C( W6, V3) 2.

9、000000 0.000000 C( W6, V4) 2.000000 0.000000 C( W6, V5) 8.000000 0.000000 C( W6, V6) 1.000000 0.000000 C( W6, V7) 4.000000 0.000000 C( W6, V8) 3.000000 0.000000 X( W1, V1) 0.000000 5.000000 X( W1, V2) 19.00000 0.000000 X( W1, V3) 0.000000 5.000000 X( W1, V4) 0.000000 7.000000 X( W1, V5) 41.00000 0.0

10、00000 X( W1, V6) 0.000000 2.000000 X( W1, V7) 0.000000 2.000000 X( W1, V8) 0.000000 10.00000 X( W2, V1) 1.000000 0.000000 X( W2, V2) 0.000000 4.000000 X( W2, V3) 0.000000 1.000000 X( W2, V4) 32.00000 0.000000 X( W2, V5) 0.000000 1.000000 X( W2, V6) 0.000000 2.000000 X( W2, V7) 0.000000 2.000000 X( W

11、2, V8) 0.000000 0.000000 X( W3, V1) 0.000000 4.000000 X( W3, V2) 11.00000 0.000000 X( W3, V3) 0.000000 0.000000 X( W3, V4) 0.000000 9.000000 X( W3, V5) 0.000000 3.000000 X( W3, V6) 0.000000 4.000000 X( W3, V7) 40.00000 0.000000 X( W3, V8) 0.000000 4.000000 X( W4, V1) 0.000000 4.000000 X( W4, V2) 0.0

12、00000 2.000000 X( W4, V3) 0.000000 4.000000 X( W4, V4) 0.000000 1.000000 X( W4, V5) 0.000000 3.000000 X( W4, V6) 5.000000 0.000000 X( W4, V7) 0.000000 2.000000 X( W4, V8) 38.00000 0.000000 X( W5, V1) 34.00000 0.000000 X( W5, V2) 7.000000 0.000000 X( W5, V3) 0.000000 7.000000 X( W5, V4) 0.000000 4.00

13、0000 X( W5, V5) 0.000000 2.000000 X( W5, V6) 0.000000 1.000000 X( W5, V7) 0.000000 2.000000 X( W5, V8) 0.000000 5.000000 X( W6, V1) 0.000000 3.000000 X( W6, V2) 0.000000 2.000000 X( W6, V3) 22.00000 0.000000 X( W6, V4) 0.000000 1.000000 X( W6, V5) 0.000000 3.000000 X( W6, V6) 27.00000 0.000000 X( W6

14、, V7) 3.000000 0.000000 X( W6, V8) 0.000000 3.000000 Row Slack or Surplus Dual Price 1 664.0000 -1.000000 2 0.000000 3.000000 3 22.00000 0.000000 4 0.000000 3.000000 5 0.000000 1.000000 6 0.000000 2.000000 7 0.000000 2.000000 8 0.000000 -4.000000 9 0.000000 -5.000000 10 0.000000 -4.000000 11 0.00000

15、0 -3.000000 12 0.000000 -7.000000 13 0.000000 -3.000000 14 0.000000 -6.000000 15 0.000000 -2.000000由以上结果可以清楚的看到由各仓库到各客户处的货物调运数量，由此得出的符合条件的最佳运货方案，而使运费最低，最低为664。二、运输规划重庆有三家电子厂分别是新普,隆宇和恒华,生产的笔记本电脑将要运向北京,天津,广东,上海四个城市销售,其产量和销售量见下表：（单位：万台）表：1-1北京天津广东上海产量新普626730隆宇495325恒华881521销量15172212-问：哪种销售方案将会取得最少的运输

16、费用,费用为多少？针对该运输问题,为了方便计算,可以设新普（A1）,隆宇（A2）和恒华（A3）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为.建立以下模型：表：1-2B1B2B3B4产量A1626730A2495325A3881521销量15172212-目标（The objective）最少费用：约束条件：供应限制（The supply constrains） 指标约束（The damand constrains） LINGO模型：model:sets:origin/1.3/:a;sale/1.4/:b;routes(origin,sale):c,x;ends

17、etsdata:a=30,25,21;b=15,17,22,12;c=6,2,6,7,4,9,5,3,8,8,1,5;enddataOBJmin=sum(routes:c*x);for(origin(i):SUPsum(sale(j):x(i,j)<=a(i);for(sale(j):DEMsum(origin(i):x(i,j)=b(j);endlingo结果： Global optimal solution found. Objective value: 161.0000 Infeasibilities: 0.000000 Total solver iterations: 6 Var

18、iable Value Reduced Cost X( 1, 1) 2.000000 0.000000 X( 1, 2) 17.00000 0.000000 X( 1, 3) 1.000000 0.000000 X( 1, 4) 0.000000 2.000000 X( 2, 1) 13.00000 0.000000 X( 2, 2) 0.000000 9.000000 X( 2, 3) 0.000000 1.000000 X( 2, 4) 12.00000 0.000000 X( 3, 1) 0.000000 7.000000 X( 3, 2) 0.000000 11.00000 X( 3,

19、 3) 21.00000 0.000000 X( 3, 4) 0.000000 5.000000 Row Slack or Surplus Dual Price OBJ 161.0000 -1.000000 SUP( 1) 10.00000 0.000000 SUP( 2) 0.000000 2.000000 SUP( 3) 0.000000 5.000000 DEM( 1) 0.000000 -6.000000 DEM( 2) 0.000000 -2.000000 DEM( 3) 0.000000 -6.000000 DEM( 4) 0.000000 -5.000000从计算结果可以得出,新

20、普（A1）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为分别为2万台,17万台,1万台,0万台,剩余10万台；隆宇（A2）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为别为13万台,0万台,0万台,12万台,剩余0万台；恒华（A3）分别销往北京（B1）、天津（B2）、广东（B3）和上海（B4）四个城市销售量为分别为0万台,0万台,21万台,0万台,剩余0万台；总费用为161个单位.三、整数规划某公司打算向它的3个营业区增设6个销售店，每个营业区至少增设一个。从各区赚取的利润与增设的销售店个数有关，其数据如下表所示。试求各区应分配几

21、个增设的销售店，才能使总利润最大。销售点增加数01234A区利润/万元100200280330340B区利润/万元200210220225230C区利润/万元150160170180200 要设置集合zone/A,B,C/，表示三个地区。因为获得的利润与地区和各地的销售点增加数均相关，所以可以仿照运输模型，用number/1.4/表示每个地区可选的销售点增加数，然后用一个派生集links(zone,number):c,profit，定义profit(i,j)为在i地区新增j个销售点能获得的利润。可写出约束条件为：所求函数为max=sum(links:c*profit);Lingo程序如下：mo

22、del:sets:zone/A,B,C/; !A,B,C三个地区;number/1.4/; !各地区可选择新建的销售点数目，可选14中的一个数，通过links把zone和number联系起来;links(zone,number):c,profit; !若在i地区新建j个销售点，则c(i,j)=1,否则c(i,j)=0.profit(i,j)表示在i地区新建j个销售点的利润;endsetsdata:profit=200 280 330 340 210 220 225 230 160 170 180 200;enddatamax=sum(links:c*profit); for(zone(I):

23、sum(number(J):c(I,J)=1); !对于每一个地区，新建销售点的数目是一定的，c的和为1;sum(zone(I):sum(number(J):c(I,J)*J)=6; !三个地区新建的销售点总数为6;for(links(i,j):bin(c(i,j); !每一个c(i,j)只能取0或1;end 用Lingo求解，结果如下：Global optimal solution found. Objective value: 710.0000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduce

24、d Cost C( A, 1) 0.000000 -200.0000 C( A, 2) 0.000000 -280.0000 C( A, 3) 1.000000 -330.0000 C( A, 4) 0.000000 -340.0000 C( B, 1) 1.000000 -210.0000 C( B, 2) 0.000000 -220.0000 C( B, 3) 0.000000 -225.0000 C( B, 4) 0.000000 -230.0000 C( C, 1) 0.000000 -160.0000 C( C, 2) 1.000000 -170.0000 C( C, 3) 0.00

25、0000 -180.0000 C( C, 4) 0.000000 -200.0000则在A，B，C区域应分别新增3，1，2个销售点，可获得的最大利润为710万元。四、目标规划有11件任务（AK）分配到4个工作站（14），任务的优先次序如下图。每件任务所花费的时间如下表。(A)(B)(C)(F)(G)(K)(J)(I)(H)(E)(D) 任务ABCDEFGHIJK时间4511950151212121289解：用变量表示任务分配给工作站的情况，表示分配，表示不分配，表示完成各项任务所需时间，则目标函数为约束条件（1）：每项任务只能且必须分配至一个工作站来做，可以表示为：；约束条件（2）：各项任务间

26、如果有优先关系，则排在前面的任务对应的工作站（序号）应当小于（或等于）排在后面的任务所对应的工作站（序号），即对所有有顺序的任务：；约束条件（3）：。这是一个非线性规划（目标函数非线性），但可以化为线性规划，增加一个变量，再增加四个约束条件：，目标函数变为。LINGO程序为：model:sets: task/ A B C D E F G H I J K/:t; pred(task,task)/ A,B B,C C,F C,G F,J G,J J,K D,E E,H E,I H,J I,J /; station/1.4/; tsx(task, station):x;endsetsdata: T

27、= 45 11 9 50 15 12 12 12 12 8 9;enddata for(task(i): sum(station(k):x(i,k) = 1); for(pred(i,j): sum(station(k):k*x(j,k)-k*x(i,k)>= 0); for(station(k): sum(txs(i,k):t(i)*x(i,k)<=cyctime); min= cyctime; for(txs:bin(x);end计算的部分结果为 Global optimal solution found at iteration: 1255 Objective value:

28、50.00000 Variable Value Reduced Cost CYCTIME 50.00000 0.000000 X( A, 1) 1.000000 0.000000 X( A, 2) 0.000000 0.000000 X( A, 3) 0.000000 45.00000 X( A, 4) 0.000000 0.000000 X( B, 1) 0.000000 0.000000 X( B, 2) 0.000000 0.000000 X( B, 3) 1.000000 11.00000 X( B, 4) 0.000000 0.000000 X( C, 1) 0.000000 0.0

29、00000 X( C, 2) 0.000000 0.000000 X( C, 3) 0.000000 9.000000 X( C, 4) 1.000000 0.000000 X( D, 1) 0.000000 0.000000 X( D, 2) 1.000000 0.000000 X( D, 3) 0.000000 50.00000 X( D, 4) 0.000000 0.000000 X( E, 1) 0.000000 0.000000 X( E, 2) 0.000000 0.000000 X( E, 3) 1.000000 15.00000 X( E, 4) 0.000000 0.0000

30、00 X( F, 1) 0.000000 0.000000 X( F, 2) 0.000000 0.000000 X( F, 3) 0.000000 12.00000 X( F, 4) 1.000000 0.000000 X( G, 1) 0.000000 0.000000 X( G, 2) 0.000000 0.000000 X( G, 3) 0.000000 12.00000 X( G, 4) 1.000000 0.000000 X( H, 1) 0.000000 0.000000 X( H, 2) 0.000000 0.000000 X( H, 3) 1.000000 12.00000 X( H, 4) 0.000000 0.000000 X( I, 1) 0.000000 0.000000 X( I, 2) 0.000000 0.000000 X( I, 3) 1.000000 12.00000 X( I, 4) 0.000000 0.000000 X( J, 1) 0.000000 0.000000 X( J, 2) 0.000000 0.000000 X( J, 3) 0.0000