运筹学实验报告(3)

Single cols= 6

Optimal solution found at step: 1 Objective value: 0.5999999

Variable Value Reduced Cost D1P 0.0000000 10000.00 D2P 0.0000000 99.00000 D3P 0.0000000 100.0000 D4P 0.0000000 100.0000 D5M 0.5999999 0.0000000 D6M 0.0000000 1.000000 X1 3.000000 0.0000000 X2 0.0000000 0.0000000 X3 7.500000 0.0000000 D1M 0.0000000 0.0000000 D2M 0.0000000 1.000000 D3M 6.000000 0.0000000 D4M 7.500000 0.0000000 D5P 0.0000000 1.000000 D6P 3.000000 0.0000000

Row Slack or Surplus Dual Price 1 0.5999999 1.000000 2 0.0000000 0.0000000 3 0.0000000 -1.000000 4 0.0000000 0.0000000 5 0.0000000 0.0000000 6 0.0000000 1.000000 7 0.0000000 0.0000000

七、整数规划

有一部货车每天沿着公路给4个零售店卸下6箱货物，如果各零售店出售该货物所得到的利润如下表所示，试求在各零售店卸下几箱货物，能够获得利润最大？其值是多少？ 零 利 售 店 润 数 1 2 3 4 箱 0 1 2 3 4

- 11 -

0 4 6 7 7 0 2 4 6 8 0 3 5 7 8 0 4 5 6 6

5 6 7 7 9 10 8 8 6 6 八、图论

设备更新问题

某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。我们用一个五年之内要更新某种设备的计划为例。若已知改种设备在各年年初的价格为： 第1年 第2年 第3年 第4年 第5年 11 11 12 12 13 还已知使用不同时间（年）的设备所需要的维修费用为： 使用年数 0-1 1-2 2-3 3-4 4-5 维修费用 5 6 8 11 18 解：

程序如下： data: n=6; enddata sets:

ci/1..n/:f; ro(ci,ci)/

1,2 1,3 1,4 1,5 1,6 2,3 2,4 2,5 2,6 3,4 3,5 3,6 4,5 4,6 5,6 /:d,p; endsets data:

d=16 22 30 41 59 16 22 30 41 17 23 31 17 23 18;

enddata f(n)=0;

@for(ci(i)|i#lt#n:

f(i)=@min(ro(i,j):d(i,j)+f(j)); );

@for(ro(i,j):

p(i,j)=@if(f(i)#eq#d(i,j)+f(j),1,0)

- 12 -

); end

求解结果：

Feasible solution found.

Total solver iterations: 0

Variable Value N 6.000000 F( 1) 53.00000 F( 2) 41.00000 F( 3) 31.00000 F( 4) 23.00000 F( 5) 18.00000 F( 6) 0.000000 D( 1, 2) 16.00000 D( 1, 3) 22.00000 D( 1, 4) 30.00000 D( 1, 5) 41.00000 D( 1, 6) 59.00000 D( 2, 3) 16.00000 D( 2, 4) 22.00000 D( 2, 5) 30.00000 D( 2, 6) 41.00000 D( 3, 4) 17.00000 D( 3, 5) 23.00000 D( 3, 6) 31.00000 D( 4, 5) 17.00000 D( 4, 6) 23.00000 D( 5, 6) 18.00000 P( 1, 2) 0.000000 P( 1, 3) 1.000000 P( 1, 4) 1.000000 P( 1, 5) 0.000000 P( 1, 6) 0.000000 P( 2, 3) 0.000000 P( 2, 4) 0.000000 P( 2, 5) 0.000000 P( 2, 6) 1.000000 P( 3, 4) 0.000000 P( 3, 5) 0.000000 P( 3, 6) 1.000000 P( 4, 5) 0.000000 P( 4, 6) 1.000000 P( 5, 6) 1.000000

- 13 -

Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 0.000000 13 0.000000 14 0.000000 15 0.000000 16 0.000000 17 0.000000 18 0.000000 19 0.000000 20 0.000000 21 0.000000

九、下图是一个电力输送网（单位：兆瓦）。现在要把电力从发电站Vs输送到地区Vt处，每条边上的数字表示每条输送线的最大输送能力。要求制定一个最优方案，将电力从Vs输送到Vt，使得输送电力达到最大。

V1 10 7 V3 8 5 5 V2 9 V4 9 8 10 Vs 12 Vt 7 8 V5 5 V6

- 14 -

解：设节点1到节点8表示电力输送网的8个节点，CAP,FLOW表示弧容量和弧流量 程序如下：

!maximum flow problem; model: SETS:

NODES/1..8/;

ARCS(NODES,NODES)/1,2 1,3 1,4 2,3 2,5 3,5 3,6 4,3 4,6 5,8 6,7 6,8 7,8 8,1/:CAP,FLOW; ENDSETS

MAX=FLOW(8,1);

@FOR(ARCS(I,J):FLOW(I,J)

@FOR(NODES(I):@SUM(ARCS(J,I):FLOW(J,I)) =@SUM(ARCS(I,J):FLOW(I,J))); DATA:

CAP=10,7,8,9,5,8,10,5,6,9,7,12,8,1000; ENDDATA END

Solution Report

Rows= 23 Vars= 14 No. integer vars= 0 ( all are linear) Nonzeros= 57 Constraint nonz= 42( 42 are +- 1) Density=0.165

Smallest and largest elements in abs value= 1.00000 1000.00

No. < : 14 No. =: 8 No. > : 0, Obj=MAX, GUBs <= 14 Single cols= 0

Optimal solution found at step: 4 Objective value: 25.00000

Variable Value Reduced Cost CAP( 1, 2) 10.00000 0.0000000 CAP( 1, 3) 7.000000 0.0000000 CAP( 1, 4) 8.000000 0.0000000 CAP( 2, 3) 9.000000 0.0000000 CAP( 2, 5) 5.000000 0.0000000 CAP( 3, 5) 8.000000 0.0000000 CAP( 3, 6) 10.00000 0.0000000 CAP( 4, 3) 5.000000 0.0000000 CAP( 4, 6) 6.000000 0.0000000 CAP( 5, 8) 9.000000 0.0000000 CAP( 6, 7) 7.000000 0.0000000 CAP( 6, 8) 12.00000 0.0000000

- 15 -

CAP( 7, 8) 8.000000 0.0000000 CAP( 8, 1) 1000.000 0.0000000 FLOW( 1, 2) 10.00000 0.0000000 FLOW( 1, 3) 7.000000 0.0000000 FLOW( 1, 4) 8.000000 0.0000000 FLOW( 2, 3) 9.000000 0.0000000 FLOW( 2, 5) 1.000000 0.0000000 FLOW( 3, 5) 8.000000 0.0000000 FLOW( 3, 6) 10.00000 0.0000000 FLOW( 4, 3) 2.000000 0.0000000 FLOW( 4, 6) 6.000000 0.0000000 FLOW( 5, 8) 9.000000 0.0000000 FLOW( 6, 7) 4.000000 0.0000000 FLOW( 6, 8) 12.00000 0.0000000 FLOW( 7, 8) 4.000000 0.0000000 FLOW( 8, 1) 25.00000 0.0000000

Row Slack or Surplus Dual Price 1 25.00000 1.000000 2 0.0000000 1.000000 3 0.0000000 1.000000 4 0.0000000 1.000000 5 0.0000000 0.0000000 6 4.000000 0.0000000 7 0.0000000 0.0000000 8 0.0000000 0.0000000 9 3.000000 0.0000000 10 0.0000000 0.0000000 11 0.0000000 0.0000000 12 3.000000 0.0000000 13 0.0000000 0.0000000 14 4.000000 0.0000000 15 975.0000 0.0000000 16 0.0000000 1.000000 17 0.0000000 0.0000000 18 0.0000000 0.0000000 19 0.0000000 0.0000000 20 0.0000000 0.0000000 21 0.0000000 0.0000000 22 0.0000000 0.0000000 23 0.0000000 0.0000000

- 16 -