运筹学习题4(名校讲义)

《管理运筹学》第四版课后习题解析第4章线性规划在工商管理中的应用1．解：为了用最少的原材料得到10台锅炉，需要混合使用14种下料方案。

设14种方案下料时得到的原材料根数分别为x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11，x12，x13，x14，如表4-1所示。

表4-1 各种下料方式1234567891011121314s.t. 2x1＋x2＋x3＋x4≥80x2＋3x5＋2x6＋2x7＋x8＋x9＋x10≥350x3＋x6＋2x8＋x9＋3x11＋2x12＋x13≥420x4＋x7＋x9＋2x10＋x12＋2x13＋3x14≥10x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11，x12，x13，x14≥0通过管理运筹学软件，我们可以求得此问题的解为：x1=40，x2=0，x3=0，x4=0，x5=116.667，x6=0，x7=0，x8=0，x9=0，x10=0，x11=140，x12=0，x13=0，x14=3.333最优值为300。

2．解：（1）将上午11时至下午10时分成11个班次，设x i表示第i班次新上岗的临时工人数，建立如下模型。

min f=16(x1＋x 2＋x3＋x4＋x5＋x6＋x7＋x8＋x9＋x10＋x11)s.t．x1＋1≥9x1＋x2＋1≥9x1＋x2＋x3＋2≥9x1＋x2＋x3＋x4＋2≥3x2＋x3＋x4＋x5＋1≥3x3＋x4＋x5＋x6＋2≥3x4＋x5＋x6＋x7＋1≥6x5＋x6＋x7＋x8＋2≥12x6＋x7＋x8＋x9＋2≥12x7＋x8＋x9＋x10＋1≥7x8＋x9＋x10＋x11＋1≥7x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11≥0通过管理运筹学软件，我们可以求得此问题的解如下：x1=8，x2=0，x3=1，x4=1，x5=0，x6=4，x7=0，x8=6，x9=0，x10=0，x11=0，最优值为320。

问题是：
求出达到最 大运输总量 的最优运输 方案。
(+120) 70v1 •
50 • y1 (-180)
x1 •
70
v2
•
40 150
100
(-200)
• y2
130
(+240)x•2
150
• 120
v3
图 5-31
§1 网络流 （3）
②有关术语
i) 运输网络 给定有向图G＝(V，E)，对每条边都给出相应的非
②有关定理
定理1设f和 K (S，S )分别为图G中任一流和任一割，则必存
在：V(f)=f+(s)－f－(s) ， 其中，f (s)
f (e)，f (s) f (e)
e(S，S )
e(S，S )
即图G中任一截面之净流值V(f)，必是任何一个横截面的输出量
减去输入量（亦即代数和）。
1) 根据图5-38所给出的初始流，为图G所有点标号，标号
过程示于表5-11中。
§3 最大流算法 （3）
表5-11
检查点
x v2 v2
v3
v5
v5
v4
新生点
x v2 v3 v5 v4 v1 v6
y
新生点标号 +∞ +6 －6 +2 +1 +2 +1 +1
v1
从表5-11中得知，Qy=xv2 v3 v4y，14,14
0 f(e) c(e)，eE（约束条件）
§1 网络流 （4）
f+(v) = f－(v)， vI（守恒条件） 则称f为G的一个网络流或流。 f(e)称为f在边e上的流量。任一网络G，至少存在一个流，若每 条边的f(e)=0，则称为零流。 2．单源和单汇运输网络 实际问题往往存在多源多汇网络（例如图5-31便是双源双汇网 络）。为了计算的规格化，可将多源多汇网络G化成单源单汇 网络G’。

2010/03
或为： f(xj) = kjyj+cjxj xj≤yjM yj≤xjM xj≥0, yj=0或1
--15--
--第4章 整数规划--
三、隐枚举法 步骤：
① 化标准形(隐枚举法)： 1) 目标函数极小化；2) 约束条件化成≥ ； 3) 使目标函数系数皆为非负, 若xj系数为负值, 则令xj=1-xj′；4) 使 目标函数按变量系数由小→大顺序排列，约束条件变量排列的顺 序要与之对应。 ② 令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约 束条件，若满足，即为最优解；否则，分枝计算。 ③ 分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值， 然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。 ④ 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a) 对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b) >zmin分枝，剪掉； (c) 能判断出为无可行解的分枝，剪掉； (d) 非上述情况，继续分枝。
2010/03
--12--
--第4章 整数规划--
（a）当x8=1 当x8=0 ∴ x8 ≤ x6
x6=1，x6≠0 x6=1，x6=0
（b）当x5 =1 当x5 =0 ∴ x5 + x3 ≤ 1
x3=0， x3 ≠1 x3=0， x3 =1
（c） x2 + x4 ≥ 1 （d） x8 = x7 （e） x1 + x4 + x6 + x9 ≤ 2
EXCEL求解：
2010/03
--8--
--第4章 整数规划--
4.2 0-1规划问题及模型
一、0-1规划问题的概念 • 在整数规划问题中，若变量取值为0或者1，则为0-1 规划问题。

2．存在可行解，但找不到最优解，例如规划 x1－x2=0 x1，x2≥0
－2 x1=min 显然，令x1=x2=λ,λ为任意非负值都是可行解， 当λ→+∞，则目标函数－2 x1→∞，故找不出使目标函数 取极小值的具体解X。
§1 初步分析线性规划解的几 种可能性 （3）
3．存在最优解，但不是唯一的。例如规划
i1
m
yi bi max
i 1
(j 1,2,, n) (7) (8)
§3 对偶性质及平衡定理 （4）
则平衡定理阐述如下：若xj(j=1,2…，n)和yi（i=1,2,…，m）分 别是原问题和对偶问题之可行解，必存在下述关系：
m
n
①
yibi c j x j
（即弱对偶性）
图1-2中，阴影部分为可行域，若要求出最优点，必须作出目标 函数的等值线，然后令等值线向最小值方向（即最优方向）移 动，直到离开可行域的瞬间为止，此时的交点即为最优点。
图中直线L1，L2，L3即为目标值分别为12，9及6的等值线，L3与 可行域的顶点B（x1＝2，x2＝0），L3再向左下方移动，必离开 可行域，于是该点即为线性规划之最优解，即：X ＝（x1，x2，
§3 对偶性质及平衡定理 （2）
2．强对偶性（对偶最优性）
若

X

，Y
分别是原问题与对偶问题可行解，且
CT

X


YT
b，
则

X

，Y
必分别是原问题及对偶问题的最优解。
证明：设X是原向题任一可行解，则从弱对偶性知，


CT X YT b CT X
，可见

X