第三题：
完整的数学模型：
Max f(n,1) S.t.
f(i,j),i? f(k,i)?j?Vk?V??1,2,?,n,
0<=f(i,j）<=Cij ,或者（Vi，Vj）?V f(n,1)=fv.
程序：
MODEL: SETS:
CHSH/1..12/;
LINKS(CHSH,CHSH)/11,1 11,10 1,2 1,4 1,3 10,4 10,3 2,5 2,4 4,5 4,7 4,8 4,6 4,9 3,6 5,7 5,8 5,9 6,8 6,9 7,12 8,12 9,12 12,11/:C,U,F; ENDSETS DATA:
U=35,18,20,15,0,6,12,10,10,10,10,5,6,0,12,7,3,10,8,10,17,16,20,54;
C=0,0,2,1.8,1.2,2.2,1.5,1.5,1,2,1.5,2,3,1,1.2,2,1,2,1,1,0,0,0,3;
ENDDATA
N=@SIZE(CHSH); F(12,11)=53;
MIN=@SUM(LINKS(I,J)|I#LT#N:C(I,J)*F(I,J)); @FOR(LINKS(I,J):F(I,J)<=U(I,J));
@FOR(CHSH(I):@SUM(LINKS(J,I):F(J,I))=@SUM(LINKS(I,J):F(I,J))); END
Global optimal solution found.
Objective value: 255.6000 Infeasibilities: 0.000000 Total solver iterations: 0
Variable Value Reduced Cost N 12.00000 0.000000 C( 11, 1) 0.000000 0.000000 C( 11, 10) 0.000000 0.000000 C( 1, 2) 2.000000 0.000000
C( 1, 4) 1.800000 0.000000 C( 1, 3) 1.200000 0.000000 C( 10, 4) 2.200000 0.000000 C( 10, 3) 1.500000 0.000000 C( 2, 5) 1.500000 0.000000 C( 2, 4) 1.000000 0.000000 C( 4, 5) 2.000000 0.000000 C( 4, 7) 1.500000 0.000000 C( 4, 8) 2.000000 0.000000 C( 4, 6) 3.000000 0.000000 C( 4, 9) 1.000000 0.000000 C( 3, 6) 1.200000 0.000000 C( 5, 7) 2.000000 0.000000 C( 5, 8) 1.000000 0.000000 C( 5, 9) 2.000000 0.000000 C( 6, 8) 1.000000 0.000000 C( 6, 9) 1.000000 0.000000 C( 7, 12) 0.000000 0.000000 C( 8, 12) 0.000000 0.000000 C( 9, 12) 0.000000 0.000000 C( 12, 11) 3.000000 0.000000 U( 11, 1) 35.00000 0.000000 U( 11, 10) 18.00000 0.000000 U( 1, 2) 20.00000 0.000000 U( 1, 4) 15.00000 0.000000 U( 1, 3) 0.000000 0.000000 U( 10, 4) 6.000000 0.000000 U( 10, 3) 12.00000 0.000000 U( 2, 5) 10.00000 0.000000 U( 2, 4) 10.00000 0.000000 U( 4, 5) 10.00000 0.000000 U( 4, 7) 10.00000 0.000000 U( 4, 8) 5.000000 0.000000 U( 4, 6) 6.000000 0.000000 U( 4, 9) 0.000000 0.000000 U( 3, 6) 12.00000 0.000000 U( 5, 7) 7.000000 0.000000 U( 5, 8) 3.000000 0.000000 U( 5, 9) 10.00000 0.000000 U( 6, 8) 8.000000 0.000000 U( 6, 9) 10.00000 0.000000 U( 7, 12) 17.00000 0.000000 U( 8, 12) 16.00000 0.000000 U( 9, 12) 20.00000 0.000000
U( 12, 11) 54.00000 0.000000 F( 11, 1) 35.00000 0.000000 F( 11, 10) 18.00000 0.000000 F( 1, 2) 20.00000 0.000000 F( 1, 4) 15.00000 0.000000 F( 1, 3) 0.000000 0.000000 F( 10, 4) 6.000000 0.000000 F( 10, 3) 12.00000 0.000000 F( 2, 5) 10.00000 0.000000 F( 2, 4) 10.00000 0.000000 F( 4, 5) 10.00000 0.000000 F( 4, 7) 10.00000 0.000000 F( 4, 8) 5.000000 0.000000 F( 4, 6) 6.000000 0.000000 F( 4, 9) 0.000000 0.000000 F( 3, 6) 12.00000 0.000000 F( 5, 7) 7.000000 0.000000 F( 5, 8) 3.000000 0.000000 F( 5, 9) 10.00000 0.000000 F( 6, 8) 8.000000 0.000000 F( 6, 9) 10.00000 0.000000 F( 7, 12) 17.00000 0.000000 F( 8, 12) 16.00000 0.000000 F( 9, 12) 20.00000 0.000000 F( 12, 11) 53.00000 0.000000
Row Slack or Surplus Dual Price 1 0.000000 0.000000
2 0.000000 -7.000000 3 0.000000 0.000000 4 0.000000 0.8000000 5 0.000000 0.000000 6 0.000000 1.200000 7 0.000000 1.100000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 1.500000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 2.500000 14 0.000000 2.000000 15 0.000000 0.000000 16 0.000000 3.000000 17 0.000000 2.500000
18 0.000000 0.000000 19 0.000000 1.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 0.000000 0.000000 25 0.000000 0.000000 26 1.000000 0.000000 27 0.000000 3.000000 28 0.000000 1.000000 29 0.000000 0.7000000 30 0.000000 0.000000 31 0.000000 -2.000000 32 0.000000 -3.000000 33 0.000000 -4.000000 34 0.000000 -4.000000 35 0.000000 -4.000000 36 0.000000 2.200000 37 0.000000 3.000000 38 0.000000 -4.000000 39 255.6000 -1.000000
第四题：
MODEL: SETS:
CHSH/1..12/;
LINKS(CHSH,CHSH)/11,1 11,10 1,2 1,4 1,3 10,4 10,3 2,5 2,4 4,5 4,7 4,8 4,6 4,9 3,6 5,7 5,8 5,9 6,8 6,9 7,12 8,12 9,12 12,11/:C,U,F; ENDSETS DATA:
U=37,16,20,15,2,6,10,10,10,10,10,5,6,0,12,7,3,10,8,10,17,16,20,54;
C=0,0,2,1.8,1.2,2.2,1.5,1.5,1,2,1.5,2,3,1,1.2,2,1,2,1,1,0,0,0,3;
ENDDATA
N=@SIZE(CHSH); F(12,11)=53;
MIN=@SUM(LINKS(I,J)|I#LT#N:C(I,J)*F(I,J)); @FOR(LINKS(I,J):F(I,J)<=U(I,J));
@FOR(CHSH(I):@SUM(LINKS(J,I):F(J,I))=@SUM(LINKS(I,J):F(I,J))); END
程序结果：
Global optimal solution found.
Objective value: 255.0000 Infeasibilities: 0.000000 Total solver iterations: 0
Variable Value Reduced Cost N 12.00000 0.000000 C( 11, 1) 0.000000 0.000000 C( 11, 10) 0.000000 0.000000 C( 1, 2) 2.000000 0.000000 C( 1, 4) 1.800000 0.000000 C( 1, 3) 1.200000 0.000000 C( 10, 4) 2.200000 0.000000 C( 10, 3) 1.500000 0.000000 C( 2, 5) 1.500000 0.000000 C( 2, 4) 1.000000 0.000000 C( 4, 5) 2.000000 0.000000 C( 4, 7) 1.500000 0.000000 C( 4, 8) 2.000000 0.000000 C( 4, 6) 3.000000 0.000000 C( 4, 9) 1.000000 0.000000
C( 3, 6) 1.200000 0.000000 C( 5, 7) 2.000000 0.000000 C( 5, 8) 1.000000 0.000000 C( 5, 9) 2.000000 0.000000 C( 6, 8) 1.000000 0.000000 C( 6, 9) 1.000000 0.000000 C( 7, 12) 0.000000 0.000000 C( 8, 12) 0.000000 0.000000 C( 9, 12) 0.000000 0.000000 C( 12, 11) 3.000000 0.000000 U( 11, 1) 37.00000 0.000000 U( 11, 10) 16.00000 0.000000 U( 1, 2) 20.00000 0.000000 U( 1, 4) 15.00000 0.000000 U( 1, 3) 2.000000 0.000000 U( 10, 4) 6.000000 0.000000 U( 10, 3) 10.00000 0.000000 U( 2, 5) 10.00000 0.000000 U( 2, 4) 10.00000 0.000000 U( 4, 5) 10.00000 0.000000 U( 4, 7) 10.00000 0.000000 U( 4, 8) 5.000000 0.000000 U( 4, 6) 6.000000 0.000000 U( 4, 9) 0.000000 0.000000 U( 3, 6) 12.00000 0.000000 U( 5, 7) 7.000000 0.000000 U( 5, 8) 3.000000 0.000000 U( 5, 9) 10.00000 0.000000 U( 6, 8) 8.000000 0.000000 U( 6, 9) 10.00000 0.000000 U( 7, 12) 17.00000 0.000000 U( 8, 12) 16.00000 0.000000 U( 9, 12) 20.00000 0.000000 U( 12, 11) 54.00000 0.000000 F( 11, 1) 37.00000 0.000000 F( 11, 10) 16.00000 0.000000 F( 1, 2) 20.00000 0.000000 F( 1, 4) 15.00000 0.000000 F( 1, 3) 2.000000 0.000000 F( 10, 4) 6.000000 0.000000 F( 10, 3) 10.00000 0.000000 F( 2, 5) 10.00000 0.000000 F( 2, 4) 10.00000 0.000000 F( 4, 5) 10.00000 0.000000
F( 4, 7) 10.00000 0.000000 F( 4, 8) 5.000000 0.000000 F( 4, 6) 6.000000 0.000000 F( 4, 9) 0.000000 0.000000 F( 3, 6) 12.00000 0.000000 F( 5, 7) 7.000000 0.000000 F( 5, 8) 3.000000 0.000000 F( 5, 9) 10.00000 0.000000 F( 6, 8) 8.000000 0.000000 F( 6, 9) 10.00000 0.000000 F( 7, 12) 17.00000 0.000000 F( 8, 12) 16.00000 0.000000 F( 9, 12) 20.00000 0.000000 F( 12, 11) 53.00000 0.000000
Row Slack or Surplus Dual Price 1 0.000000 0.000000
2 0.000000 -7.300000 3 0.000000 0.3000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 1.200000 7 0.000000 0.000000 8 0.000000 1.100000 9 0.000000 0.000000 10 0.000000 1.500000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 2.500000 14 0.000000 2.000000 15 0.000000 0.000000 16 0.000000 3.000000 17 0.000000 3.600000 18 0.000000 0.000000 19 0.000000 1.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 0.000000 0.000000 25 0.000000 0.000000 26 1.000000 0.000000 27 0.000000 5.000000 28 0.000000 3.000000
29 0.000000 3.800000 30 0.000000 2.000000 31 0.000000 0.000000 32 0.000000 -1.000000 33 0.000000 -2.000000 34 0.000000 -2.000000 35 0.000000 -2.000000 36 0.000000 5.300000 37 0.000000 5.300000 38 0.000000 -2.000000 39 255.0000 -1.000000