运筹学作业标准答案 (教师用) 25

No.9 网络流问题

1、求下面网络s到t的最大流和最小截，从给定的可行流开始标号法。(要求每得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可行流，再进行标号法)

解：

v1(4,0)s(4,4)(3,0)v3+(s,9)v1(4,0)s(4,4)(3,0)v3(2,0)(3,0)v2(4,4)v4(8,4)t(3,0)s(s+,4)(4,0)v1+(2,0)(1,2)v4(3,0)(4,4)(3,3)v3v1(8,4)v2(4,4)(3,0)(6,3)(10,7)(s+, )(4+,2)t(9,0)(10,0)v5(3+,4)v4(8,4)t(3,0)(10,4)8(6,0)(4,0)(5+,4)8(s, )+

s(9,7)(4,4)v5v4(8,6)(2,0)(3,0)v2(4,4)(s+,2)(4,2)(2,2)(3,0)v2(4,4)8(s+, )(3+,3)(6,0)(4,4)(4,4)(3,3)v3(5+,3)8(3,0)t(9,4)(s+, )(9,7)(1+,2)(6,3)(10,7)(4,4)(5+,2)(s+,5)v1(2+,3)v5v4(8,6)

(3,0)t(10,9)(2+,2)v5(2,2)(3,2)v2(4,4)(6,5)(4,4)s(4,4)(s, )8+(3,3)(9,7)v3(4,4)

答：最大流为15，最小割截为 V?(s,v),V?(v,v,v,v,t)

31245(s+,2)v5

运筹学作业标准答案 (教师用) 26

习题课1

1、某工厂生产用2单位A和1单位B混合而成的成品出售，市场无限制。A和B可以在该工厂的3个车间中的任何车间生产，生产每单位的A和B在各车间消耗的工时如下表。

工时消耗 车间1 车间2 车间3 A 2 1 1.5 B 1 2 1.5 100 120 100 可用工时 试建立使成品数量最大的线性规划模型。

解：设车间1生产x1A单位A、生产x1B单位B；

设车间2生产x2A单位A、生产x2B单位B；

设车间3生产x3A单位A、生产x3B单位B；

则有生产安排最优化的模型如下：

maxf(x)?x1B?x2B?x3B2x1A?x1B?100??x2A?2x2B?120??s.t.?1.5x3A?1.5x3B?100?x1A?x2A?x3A?2(x1B?x2B?x3B)??xiA,xiB?0,i?1,2,3?

这是一个可分解的线性规划，这类问题

运筹学作业标准答案 (教师用) 27

就容易出现退化现象。

2、某饮料工厂按照一定的配方将A、B、C三种原料配成三种饮料出售。配方规定了这三种饮料中A和C的极限成分，具体见下表，

每升售需求量 价(元) 6.80 1500 甲 (1) A≥60％，C≤20％ 5.70 3000 乙 (2) A≥15％，C≤60％ 4.50 无限制 丙 (3) C≤50％ A、B、C三种原料每月的供应量和每升的价格如下表。

供应量价格(元/(升/月) 升) A 2000 7.00 B 2500 5.00 C 1200 4.00 饮料甲、乙、丙分别由不同比例的A、B、C调兑而成，设调兑后不同成分的体积不变，求最大收益的生产方案。

解：设x1A为饮料甲中A的总含量 (升)，饮料品种 规 格 运筹学作业标准答案 (教师用) 28

设x2A为饮料乙中A的总含量 (升)

设x1B为饮料甲中B的总含量 (升)，设x2B为饮料乙中B的总含量 (升)

设x1C为饮料甲中C的总含量 (升)，设x2C为饮料乙中C的总含量 (升)

设x3A为饮料丙中A的总含量 (升)， 设x3B为饮料丙中B的总含量 (升)

设x3C为饮料丙中C的总含量 (升) 则有模型如下：

maxf(x)?6.8(x1A?x1B?x1C)?5.7(x2A?x2B?x2C)?4.5(x3A?x3B?x3C)?7.0(x1A?x2A?x3A)?5.0(x1B?x2B?x3B)?4.0(x1C?x2C?x3C)??0.2x1A?1.8x1B?2.8x1C?1.3x2A?0.7x2B?1.7x2C?2.5x3A?0.5x3B?0.5x3Cx1A?x1B?x1C??x2A?x2B?x2C??x1A?x2A?x3A?x1B?x2B?x3B??x1C?x2C?x3C?s.t.??0.4x1A?0.6x1B?0.6x1C??0.2x1A?0.2x1B?0.8x1C???0.85x2A?0.15x2B?0.15x2C??0.6x?0.6x?0.4x2A2B2C???0.5x3A?0.5x3B?0.5x3C?xiA,xiB,xiC??1500?3000?2000?2500?1200?0?0?0?0乙配方约束?0丙配方约束?0, i?1,2,3甲配方约束资源约束需求约束

3、将下列线性规划化为标准形式

minf(x)?5x1?3x2?2x3? x1? x2? x3??10? 6x?3x?7x?15?123s.t. ??|10x1?12x2?x3|?19??x1?0, x2?0, x3?不限??2x'3?2x3??max[?f(x)]??5x1?3x2

?? x3??x3???x4?10? ?x1? x2???7x3??7x3?? ?15 6x1?3x2????x3??x3???x5?19s.t. ?10x1?12x2??10x?12x??x??x???x?1912336??,x3?,x3??,x4,x5,x6?0?? x1,x2