09 运筹学习题.pptx

第1页：习题1.2 图解法求解

习题 1.2：用图解法求解下列线性规划问题。

• （1）min z = 2x1 + 3x2，满足 4x1 + 6x2 ≥ 6，2x1 + 2x2 ≥ 4，x1、x2 ≥ 0
• （2）max z = 3x1 + 2x2，满足 2x1 + x2 ≤ 2，3x1 + 4x2 ≥ 12，x1、x2 ≥ 0
• （3）max z = x1 + x2，满足 6x1 + 10x2 ≤ 120，5 ≤ x1 ≤ 10，3 ≤ x2 ≤ 8
• （4）max z = 5x1 + 6x2，满足 2x1 - x2 ≥ 2，-2x1 + 3x2 ≤ 2，x1、x2 ≥ 0

第2页：习题1.5 图解与单纯形对照

习题 1.5：分别用图解法和单纯形法求解下列各题，并对照指出单纯形表中的各基本可行解对应图解法中可行解域的哪一顶点。

已知 max z = 10x1 + 5x2，满足 3x1 + 4x2 ≤ 9，5x1 + 2x2 ≤ 8，x1、x2 ≥ 0，将其变为标准形：

max z = 10x1 + 5x2 + 0x3 + 0x4，满足 3x1 + 4x2 + x3 = 9，5x1 + 2x2 + x4 = 8，x1、x2、x3、x4 ≥ 0。

第3页：习题1.5 求解过程（一）

用单纯形法求解，迭代过程依次得到各基本可行解：

• 初始解 (x1, x2) = (0, 0)
• a 点 (0, 9/4)
• b 点 (8/5, 0)
• c 点 (1, 3/2)，即最优解 x* = (1, 3/2)

表中依次出现 [5]、[14/5] 等主元素，迭代至所有非基变量检验数 σj ≤ 0 时停止。

源文件该页单纯形表为矩阵式连排数字，行列对应无法安全切分，未作表格还原，建议对照原图核对。

第4页：习题1.5 求解过程（二）

（2）max z = 2x1 + x2，满足 5x2 ≤ 15，6x1 + 2x2 ≤ 24，x1 + x2 ≤ 5，x1、x2 ≥ 0，化为标准形后引入 x3、x4、x5。

• 可行域顶点：a 点 (0, 3)、b 点 (2, 3)、c 点 (7/2, 3/2)、d 点 (4, 0)
• 第一轮迭代主元素为 [6]，得基变量 x1 与 x3
• 第二轮迭代主元素为 [2/3]，得最优解，对应 c 点附近的基本可行解

源文件该页单纯形表为连排数字，主元素与检验数所在行难以逐格还原，建议对照原图核对。

第5页：习题1.8 填空

习题 1.8：下表为用单纯形法求解某线性规划问题时的一步，要求填出表中标 (a) 至 (t) 各空格处的数值，并填出各列的检验数 cj - zj 行。

表中基变量为 x4、x5，非基变量为 x1、x2、x3，已知 cj 行含 2、-1、1 等系数。

源文件该页为单纯形表的填空版式，各空格标注字母而数值位置被打散，无法逐格还原，建议对照原图核对。

第6页：作业：单纯形表填空

作业：填出下列单纯形表中各空格处的数值，并写出 cj - zj 行。

表中含基变量 x1、x2、x4、x5、x6 及其所在行（如 8/3、2/3、14/3、29/3 等右端项），要求据此判断当前基本可行解是否最优。

源文件该页数字为连排排布，基变量与右端项的对应关系难以确认，建议对照原图核对。

第7页：习题1.9 仓库租借模型

习题 1.9：某厂在今后四个月内需租用仓库堆放物资，已知各月所需仓库面积和租金，租借时每月初都可办理，租期越长折扣越大，试建立一个使总租金最小的数学模型。

源文件该页数据为连排数字，面积与租金的月份对应关系按原文出现顺序整理，建议对照原图核对。

第8页：产品与设备数据表

某厂生产甲、乙、丙三种产品，有关数据如下：原料费分别为 0.25、0.35、0.50 元/件，售价分别为 1.25、2.00、2.80 元/件。

源文件该页各产品在各设备上的工时消耗数字被打散连排，未能完整还原，建议对照原图核对后补充该部分数据。

第9页：习题2.2 写出对偶问题

习题 2.2：写出下列线性规划的对偶问题。

• （1）min z = 2x1 + 2x2 + 4x3，满足 2x1 + x2 + 3x3 ≤ 3，x1 + 3x2 + 4x3 ≥ 2，x1 + 4x2 + 3x3 = 5，x1、x2 ≥ 0，x3 无约束
• （2）max z = 5x1 + 6x2 + 3x3，满足 x1 + 2x2 + 2x3 = 5，-x1 + 5x2 - x3 ≥ 3，4x1 + 7x2 + 3x3 ≤ 8，x1 无约束，x2 ≥ 0，x3 ≤ 0
• （3）含 m1 个等号约束与 n1 个无约束变量的一般形式：min z = Σ Σ cij xij，约束按 i ≤ m1 取等号、i > m1 取不等式，变量按 j ≤ n1 无约束、j > n1 非负
• （4）max z = Σ cj xj 的一般形式

第10页：习题2.4 与 2.5

习题 2.4：已知线性规划问题 max z = x1 + x2，满足 -x1 + x2 + x3 ≤ 2，-2x1 + x2 - x3 ≤ 1，xj ≥ 0，试用对偶理论证明此问题有可行解而无最优解。

习题 2.5：已知线性规划问题 max z = 2x1 + 4x2 + x3 + x4，满足 x1 + 3x2 + x4 ≤ 8，2x1 + x2 ≤ 6，x2 + x3 + x4 ≤ 6，x1 + x2 + x3 ≤ 9，xj ≥ 0。

1. 写出对偶问题
2. 已知原问题的最优解为 X* = (2, 2, 4, 0)，试根据对偶理论直接求出对偶问题的最优解

第11页：习题2.6 展开并写对偶

习题 2.6：分别把 A、B 两个线性规划问题展开，并写出其对偶问题。

原问题 max z = c1x1 + c2x2 + … + cnxn，满足三个约束（第一个取等号、第二个取 ≤、第三个取等号），xj ≥ 0；

其对偶问题为 min w = b1y1 + b2y2 + b3y3，满足 a11y1 + a21y2 + a31y3 ≥ c1，a12y1 + a22y2 + a32y3 ≥ c2，……，a1ny1 + a2ny2 + a3ny3 ≥ cn，其中 y1、y3 无约束，y2 ≥ 0。

作变量代换 y1 = 5ŷ1 + 3ŷ3，y2 = (1/5)ŷ2，y3 = ŷ3 后，可得与原问题等价的形式及相应的对偶问题。

源文件该页公式被打散连排，部分系数与下标的对应关系建议对照原图核对。

第12页：习题2.7 对偶单纯形法

习题 2.7：利用对偶单纯形法求解下列线性规划问题。

• （1）min z = 4x1 + 12x2 + 18x3，满足 x1 + 3x3 ≥ 3，2x2 + 2x3 ≥ 5，xj ≥ 0（j = 1, …, 5）
• （2）变成标准形得 max z = -4x1 - 12x2 - 18x3，满足 -x1 - 3x3 + x4 = -3，-2x2 - 2x3 + x5 = -5，xj ≥ 0

求解过程中依次以 [-2]、[-3] 等为主元素作对偶单纯形迭代，直到右端项全部非负且检验数均符合条件。

源文件该页单纯形表为连排数字，主元素与各行对应无法安全切分，建议对照原图核对。

第13页：习题2.8 灵敏度分析要求

习题 2.8：已知线性规划问题 max z = 2x1 - x2 + x3，满足 x1 + x2 + x3 ≤ 6，-x1 + 2x2 ≤ 4，xj ≥ 0。

要求先用单纯形法求最优解，再分析在下列条件单独变化时最优解的变化：

1. 目标函数变为 max z = 2x1 + 3x2 + x3
2. 第一个约束条件右端项由 6 变为 3
3. 增加一个约束条件 -x1 + 2x3 ≥ 2

第14页：习题2.8 求解过程

用单纯形法求得最终单纯形表后：

• （1）将 c 值的变化直接反映到最终单纯形表中，重新计算检验数，得 X1 = 8/3、X2 = 10/3、Z = 56/3；原问题最优解为 X1 = 6、Z = 12
• （2）Δb 由 B⁻¹·Δb 计算：B⁻¹·[6, -3] 一类运算得 x* = (3, 0, 0, 0, 7)，z = 6
• （3）把 x1 = 6 代入新约束 -x1 + 2x3 = -6 < 2，说明新约束起作用，将其加入最终单纯形表后迭代得 X1 = 10/3、X3 = 8/3、Z = 28/3

源文件该页矩阵与单纯形表数字连排，B⁻¹ 的具体元素与各行对应无法确认，建议对照原图核对。

第15页：应用对偶理论证明上界

已知线性规划问题 max z = 4x1 + 3x2 + 2x3，满足 x1 + 2x2 + x3 ≤ 10，2x1 + 3x2 + 3x3 ≤ 10，x1、x2、x3 ≥ 0，应用对偶理论证明该问题最优解的目标函数值不大于 25。

其对偶问题为 min w = 10y1 + 10y2，满足 y1 + 2y2 ≥ 4，y1 + 3y2 ≥ 2，2y1 + 3y2 ≥ 3，y1、y2 ≥ 0；取对偶可行解 Y = (1, 1.5) 代入即得 w = 25，由弱对偶性可知原问题最优值不超过 25。

第16页：对偶理论综合题

考虑如下线性规划问题：min z = 60x1 + 40x2 + 80x3，满足 3x1 + 2x2 + x3 ≥ 2，4x1 + x2 + 3x3 ≥ 4，2x1 + 2x2 + 2x3 ≥ 3，x1、x2、x3 ≥ 0。

1. (a) 写出其对偶问题：max w = 2y1 + 4y2 + 3y3，满足 3y1 + 4y2 + 2y3 ≤ 60，2y1 + y2 + 2y3 ≤ 40，y1 + 3y2 + 2y3 ≤ 80，y1、y2、y3 ≥ 0
2. (b) 用对偶单纯形法求解原问题
3. (c) 用单纯形法求解其对偶问题
4. (d) 对比 (b)、(c) 中每步计算得到的结果

第17页：对偶理论综合题求解

原问题侧：依次以 [-4]、[-3/2] 等为主元素迭代，最终得 x1 = 5/6、x2 = 2/3 一类基本可行解，检验数行全部满足条件时得到最优解。

对偶问题侧：以 [4]、[3/2] 等为主元素迭代，得 y2 = 20/3、y3 = 50/3 一类结果，两侧每步的目标函数值与检验数可逐步对照。

源文件该页两组单纯形表均为连排数字，行列归属难以逐格确认，未作表格还原，建议对照原图核对。

第18页：习题2.9 灵敏度分析

习题 2.9：已知线性规划问题 max z = 3x1 + 2x2，满足 x1 + 2x2 ≤ 6，-x1 + x2 ≤ 1，2x1 + x2 ≤ 8，x2 ≤ 2，x1、x2 ≥ 0，用单纯形法求得最优解的最终单纯形表如下。

1. 第 ①、② 个约束条件的右端项分别由 6 变为 7、由 8 变为 4
2. 目标函数变为 max z = 2x1 + 5x2
3. 增加一个变量 x3，其在目标函数中的系数 c3 = 4，系数列向量 P3 = (1, 2, 3, 2)
4. 问题中 x2 的系数列向量变为 (3, 2, 1, 2)，c2 = 4
5. 增加一个新的约束条件 x4 ≤ 4

表中基变量行含 x1 = 10/3、x2 = 4/3、x5 = 2/3、x6 = 0 等取值。

第19页：习题2.10 参数线性规划

习题 2.10：min z = x1 + x2 - λx3 + 2λx4，满足 x1 + x3 + 2x4 = 2，2x1 + x2 + 3x4 = 5，xj ≥ 0。变量的系数矩阵为 [1 0 1 2；2 1 0 3]。

令 λ = 0 求得初始最优基（x2、x3 为基变量），再把含 λ 的检验数行一并计算，按检验数 ≤ 0 的条件讨论参数取值范围：

• λ ≤ 1/2 时，Z = 2
• 1/2 ≤ λ ≤ 1 时，Z = 2λ + 2
• λ ≥ 1 时，Z = -2λ + 1

将 λ 的值代入即得相应的最优解与最优值。

源文件该页分段结论的数字为连排排布，区间端点按原文给出的 1/2 与 1 整理，建议对照原图核对。

第20页：习题2.11 生产计划灵敏度分析

习题 2.11：某厂生产 A、B、C 三种产品，其所需劳动力、材料等有关数据见表（产品利润分别为 3、1、4 元/件；劳动力消耗 6、3、5；材料消耗 3、4、5；劳动力可用量 45，材料可用量 30）。

1. 设生产 A、B、C 产品的数量分别为 x1、x2、x3 件，建立使获利最大的数学模型并求解：max z = 3x1 + x2 + 4x3，满足 6x1 + 3x2 + 5x3 ≤ 45，3x1 + 4x2 + 5x3 ≤ 30，xj ≥ 0
2. 产品 A 的利润在什么范围内变化时最优解不变：把 c1 = λ 代入最终单纯形表，要使最优解不变应所有 σ ≤ 0，即 1 + λ/3 - 4 ≤ 0，-λ/3 + 4/5 ≤ 0，-λ/3 - 8/5 ≤ 0，解得 12/5 ≤ λ ≤ 24/5
3. 若设计一种新产品 D，其 P = (8, 2)、c = 3，问是否值得生产：σ = 3 - (1/5, 3/5)·(8, 2) = 1/5 > 0，值得生产
4. 劳动力数量不变而材料不足时可市场购买，每单位 0.4 元，问是否购进、购进多少：因 Y2 = 0.6 > 0.4，可以购买，由基变量非负条件解得 λ ≤ 15

第21页：习题3.1 运输表

习题 3.1：已知运输问题的产销平衡表与单位运价表（三个产地 A1、A2、A3 与四个销地 B1、B2、B3、B4），表中含运价系数 5、11、0、12、1、2、10、9、7、18、16、14 等，求最优调运方案。

源文件该页运价数字被打散连排，产地与销地的行列对应无法安全切分，未作表格还原，建议对照原图核对。

第22页：习题3.2 运价变化分析

习题 3.2：试分析当分别发生下述变化时，最优解的变化。

• (1) 单位运价表中第 r 行的每个 cij 都加上一个常数 k：位势变为 u′i = ui + k（i = r）、u′i = ui（i ≠ r），v′j = vj，最优解不变，最优值 z′ = z + k·ar（ar 为该行调运量）
• (2) 单位运价表中第 p 列的每个 cij 都加上一个常数 k：v′p = vp + k，最优解不变，最优值 z′ = z + k·bp
• (3) 单位运价表中所有 cij 都乘上一个常数 k：k > 0 时最优解不变；k < 0 时最优解一般情况下要变化

第23页：习题3.3 运价范围分析

习题 3.3：在下列产销平衡与单位运价表（产地 A1、A2、A3，销地 B1、B2、B3、B4，产量 15、25、5，销量 5、15、15、10 一类）中：

• C22 在什么范围内变化时最优解不变：由非基变量检验数 ≤ 0 解得 3 ≤ C22 ≤ 10
• C24 为何值时该问题有无穷多个最优调运方案，并列出两个方案：当 C24 = 17 时该空格检验数为零，问题有无穷多最优调运方案

源文件该页运输表数字为连排排布，产量与销量的行归属按原文顺序整理，建议对照原图核对。

第24页：习题3.4 生产储存问题

习题 3.4：某厂在三年内需满足各年需要量，可于第 1、2、3 年正常生产或加班生产，多余产品可于第 3 年末储存，各年的期初储存、正常生产、加班生产与需要量构成下表（单位：台一类）。

源文件该页数字为连排排布，各成本系数与行列归属无法安全切分，表格仅按可辨识项整理，建议对照原图核对。

第25页：习题4.2 0-1变量建模

习题 4.2：试用 0-1 变量对下列各题分别表示成一般线性约束条件。

• (1) x1 + x2 ≤ 2 或 2x1 + 3x2 ≥ 5：写成 x1 + x2 ≤ 2 + (1 - y1)M，2x1 + 3x2 ≥ 5 - (1 - y2)M，y1 + y2 = 1，y1、y2 = 0 或 1
• (2) 变量 x 只能取 0、3、5、7 中的一个值：写成 x = 3y1 + 5y2 + 7y3，y1 + y2 + y3 ≤ 1，yi = 0 或 1
• (3) 若 x1 ≤ 2，则 x2 ≥ 1；否则 x2 ≤ 4：写成 x1 ≤ 2 + (1 - y1)M，x2 ≥ 1 - (1 - y1)M，x1 ≥ 2 - (1 - y2)M，x2 ≤ 4 + (1 - y2)M，y1 + y2 = 1
• (4) 以下四个约束条件中至少满足两个（x1 + x2 ≤ 5、x1 ≤ 2、x3 ≥ 2、x3 + x4 ≥ 6）：各加 (1 - yi)M 松弛项，并令 y1 + y2 + y3 + y4 ≥ 2

第26页：习题4.6 匈牙利法求解

习题 4.6：已知分配问题的效率矩阵如下，试用匈牙利法求最优解。

题目给出三组效率矩阵（阶数分别为 4 阶与 5 阶），矩阵元素含 4、2、4、1、0、3、8、9、6、2、0、7、5 等，求解过程须先作行、列归约（各行减最小元素、各列减最小元素），再以最少的直线覆盖所有零元素并调整，直至得到 n 个独立零元素。

源文件该页三个效率矩阵的元素被打散连排，行列归属无法安全切分，未作表格还原，建议对照原图核对。

第27页：习题4.8 四人五项任务分配

习题 4.8：今有甲、乙、丙、丁四个人去完成 A、B、C、D、E 五项任务，每个人完成各项任务的时间如下。由于人数少于任务数，故规定其中一个人可完成两项任务，其他人每人完成一项。确定总花费时间最少的分配方案。

建模提示：增加一个虚拟人（或把允许完成两项任务的人拆成两个「人」）使之化为标准指派问题，再用匈牙利法求解。

源文件该页数值为连排数字，各人员与任务的行列归属按原文顺序（E、D、C、B、A）整理，建议对照原图核对。

第28页：习题5.3 目标规划建模

习题 5.3：三种产品 A、B、C 在同一生产线上完成，消耗工时分别为 6、8、10 h，可用工时 200 h；每件产品可获利 500、650、800 元；每月销量预计 12、10、6 件。该厂经营目标如下：

• P1：利润指标为每月 16000 元
• P2：充分利用生产能力
• P3：加班不超过 24 h
• P4：产量以销量为准

建模：500x1 + 650x2 + 800x3 + d1⁻ - d1⁺ = 16000；6x1 + 8x2 + 10x3 + d2⁻ - d2⁺ = 200；d2⁺ + d3⁻ - d3⁺ = 24；x1 + d4⁻ - d4⁺ = 12；x2 + d5⁻ - d5⁺ = 10；x3 + d6⁻ - d6⁺ = 6；min z = P1d1⁻ + P2d2⁻ + P3d3⁺ + P4(d4⁻ + d5⁻ + d6⁻) 一类。

第29页：习题5.4 调运目标规划建模

习题 5.4：某公司的三个煤矿 A1、A2、A3 每天的产量为 12、10、10 t，供应 B1、B2、B3、B4 四个工厂，需求量为 6、8、6、10 t。

调运优先级如下：

• P1：A1 尽量全部调出
• P2：B4 需求最好由 A3 供应
• P3：满足各销地需求
• P4：调运总费用控制在 85 元以下

建模要点：x11 + x12 + x13 + x14 + d1⁻ = 12；x31 + d2⁻ - d2⁺ = 10（B4 由 A3 供应）；各销地列和分别加偏差变量满足 6、8、6、10；Σ Σ cij xij + d7⁻ - d7⁺ = 85；min z = P1d1⁻ + P2d2⁻ + P3(d3⁻ + d4⁻ + d5⁻ + d6⁻) + P4d7⁺。

源文件该页单位运价表的数字被打散连排，运价系数建议对照原图核对。

第30页：习题5.5 图解分析法（一）

习题 5.5：用图解分析法求满意解。

(1) min z = P1d1⁺ + P2d2⁺ + P3d3⁺，满足 -x1 + 2x2 + d1⁻ - d1⁺ = 4，x1 - 2x2 + d2⁻ - d2⁺ = 4，x1 + 2x2 + d3⁻ - d3⁺ = 8，x1、x2 ≥ 0，di⁻、di⁺ ≥ 0（i = 1, 2, 3）。

图中标出 a、b、c、d 等顶点，按优先级 P1、P2、P3 逐层缩小可行域，最后落在满意解所在的点。

第31页：习题5.5 图解分析法（二）

(3) min z = P1d1⁺ + P2d2⁻ + P3(d3⁻ + d3⁺)，满足 6x1 + 2x2 + d1⁻ - d1⁺ = 24，x1 + x2 + d2⁻ - d2⁺ = 5，5x1 + d3⁻ - d3⁺ = 15，x1、x2 ≥ 0，di⁻、di⁺ ≥ 0（i = 1, 2, 3）。

按 P1 → P2 → P3 的顺序逐层缩小可行域，最终得到满意解所在区域（图中给出点 (0, 12) 等参考坐标）。

第32页：习题5.6 单纯形法（一）

习题 5.6：(1) min z = P1d1⁺ + P2d2⁺ + P3(d3⁻ + d3⁺)，满足 3x1 + x2 + x3 + d1⁻ - d1⁺ = 60，x1 - x2 + 2x3 + d2⁻ - d2⁺ = 10，x1 + x2 - x3 + d3⁻ - d3⁺ = 20，xi ≥ 0，di⁻、di⁺ ≥ 0。

初始单纯形表以 d1⁻、d2⁻、d3⁻ 为基变量，右端项分别为 60、10、20，检验数行按 P1、P2、P3 分层列出。

源文件该页单纯形表为矩阵式连排数字，各偏差变量列与检验数行的对应无法安全切分，建议对照原图核对。

第33页：习题5.6 单纯形法（二）

第一次迭代：以 d1⁻、d2⁻、x3 一类为基变量，表中出现 15、1/2、3/2 等元素，检验数行按 P1、P2、P3 三行分别计算（如 P1 行 0、0、0、0、1、0、0；P2 行 0、0、0、1、-1、-1、0；P3 行 0、1、0、0、0、1、0 一类）。

源文件该页为单纯形表连排数字，各行检验数与偏差变量的归属难以确认，未作表格还原，建议对照原图核对。

第34页：习题5.6 单纯形法（三）

继续迭代至最终单纯形表，基变量为 x1、x2、x3，各偏差变量列的元素含 1/2、-1/4、3/4、1、0 等；检验数行按 P1、P2、P3 分层，当各优先级行均满足最优性条件时停止，由此得到该目标规划问题的满意解。

源文件该页纯粹由连排数字构成，行列归属无法安全切分，故不作表格还原，建议对照原图核对。

第35页：习题6.2 标出各点位置

习题 6.2：某人从 A 出发，途经 J、N、H、K、G、B、M、I、E、P、F、C、L、D、O、C、G、N、H、K、O、D、L、P、E、I、F、B、J、A，最后到达 M，请在图上标明各点的位置。

本题答案依赖原课件中的图形，源文件未提取到图形坐标，建议对照原图完成标注。

第36页：习题6.3 关联关系表

习题 6.3：表中给出 A、B、C、D、E、F 六个对象与 1 至 10 共十项之间的对应关系（表中以星号标记）。

源文件该页关联表被打散为字符序列，星号与行列位置的对应无法安全切分，未作表格还原，建议对照原图核对。

第37页：习题6.4 网络权值数据

习题 6.4：图中各弧的权值为 2、1、2、7、8、7、3、5、1、3、2、4、3、4、4、6、6、5、2、2、3、2、2、3、1、3、4、2、2、2、2、5 一类，要求据此求解图上相应的优化问题。

源文件该页权值数字连排且与弧的对应关系未提取成功，未作表格还原，建议对照原图核对。

第38页：习题6.5 最短路数据

习题 6.5：图中给出以 v1 为起点的有向网络，各弧权值为 2、15、11、6、21、0、5、7、5、4、5、6、30、20、7、10、4、30、10、v1、20、4、20、19、8、5、8、2、7、3、4、3、10、7 一类，要求求出各点间的最短路线。

源文件该页数字连排，弧与权值的对应关系未提取成功，未作表格还原，建议对照原图核对。

第39页：习题6.7 网络流数据

习题 6.7：容量网络上各弧以（容量, 流量）形式标注，如 a—s、s—b、s—c 等弧分别为 (3,2)、(5,5)、(3,3)、(2,2)、(4,4)、(3,3)、(6,6)、(2,0)、(2,0) 一类，要求判断当前流是否为最大流并求出最大流量与最小截集。

源文件该页（容量, 流量）数对被打散连排，各弧与数对的对应无法安全切分，建议对照原图核对。

第40页：图与网络数据

图中给出 A、B、C、D、E 各点之间的距离与费用数据（含 12、20、30、80、17、40、60、40、30、20、40、10、14、0、B3、50、C3、10、60、30、30、D2、40、30、30 一类），要求据此完成相应的图上计算。

源文件该页数字连排，点号与数值的对应关系未提取成功，未作表格还原，建议对照原图核对。

第41页：综合题1 单纯形表判读

某一求目标函数极大值的线性规划问题，用单纯形法求解得到某一步的单纯形表如下，问表中 a1、a2、a3、c、d 各为何值以及变量 xk 属于哪一类性质的变量时：

• (a) 现有解为唯一最优解
• (b) 现有解为最优解，但最优解有无穷多个
• (c) 存在可行解，但目标函数无界
• (d) 无可行解

表中基变量行为 x3（0、1、0、1、3、-1、4）、x4（1、0、0、a1、1、-4、a1）、x5（0、0、1、a2、-2、c、d），检验数行含 1、3、-1、4 等。

第42页：综合题2 化标准型

将下列线性规划问题变成标准型，并列出初始单纯形表：

min z = 2x1 - x2 + 2x3，满足 -x1 + x2 + x3 = 4，-x1 + x2 - x3 ≤ 6，x1 ≤ 0，x2 ≥ 0，x3 无约束。

处理要点：令 x1′ = -x1 ≥ 0，令 x3 = x3′ - x3″（x3′、x3″ ≥ 0），不等式约束加松弛变量，目标函数化为 max(-z) 后列出初始单纯形表。

第43页：综合题3 求表中待定值

下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 max z = 5x1 + 3x2，约束为小于等于号，x3、x4 为松弛变量，表中解代入目标函数得 z = 10。

表中含 x1 行（1/5、1、0）、x3 行（c、e、d、a、1）与 x1 行（f、-1、b）等元素。

1. 求 a 至 g 各值
2. 表中解是否为最优解

源文件该页表格元素为连排字母与数字，位置对应难以确认，建议对照原图核对。

第44页：综合题4 对偶问题

已知线性规划问题：max z = 5x1 + 3x2 + 6x3，满足 x1 + 2x2 + x3 ≤ 18，2x1 + x2 + 3x3 = 16，x1 + x2 + x3 = 10，x1、x2 ≥ 0，x3 无约束。

1. 写出对偶问题
2. 已知原问题用两阶段法求得最终单纯形表，写出对偶问题的最优解

终表中基变量行含 x4（0、1、0、0、1、0、8）、x1（5、0、1、-1、1、0、4）、x3″（-6、0、0、0、-1、1、0）与检验数行 -6、0、0、0、0、1 一类。

第45页：综合题5 运输问题的对偶

某一实际的运输问题可以叙述如下：有 n 个地区需要某种物资，需要量分别为 bj（j = 1, …, n）。这些物资均由某公司分设在 m 个地区的工厂供应，各工厂的产量分别为 ai（i = 1, …, m）。已知从第 i 个地区工厂至第 j 个需求地区单位物资的运价为 cij，这是个产销平衡问题。

试阐述其对偶问题，并解释对偶变量的经济意义：对偶变量 ui、vj 可理解为各地物资的「影子价格」或位势，其经济含义是某地产量（或某地需求量）增加一个单位所引起的总运费变化量。

第46页：综合题6 最优调拨方案

已知某运输问题的产销平衡表与单位运价表（产地与销地 A、B、C、D、E，产量 50、40、20、20、15 一类，销量 25、115、60、30、70 一类，运价 11、30、30、15、40、20、23、15、50、25、55、40、35 一类）。

1. 求最优调拨方案
2. 如产地 3 的产量变为 130，又 B 地区需要的 115 单位必须满足，试重新确定最优调拨方案

源文件该页运价与产销数字被打散连排，行列归属无法安全切分，未作表格还原，建议对照原图核对。

第47页：综合题7 求参数k

已知线性规划问题 min z = 2x1 - x2 + 2x3，满足 -x1 + x2 + x3 = 4，-x1 + x2 - kx3 ≤ 6，x1 ≤ 0，x2 ≥ 0，x3 无约束，其最优解为 x1 = -5、x2 = 0、x3 = -1。

1. 求 k 的值
2. 求对偶问题的最优解

第48页：综合题8 对偶最优解

已知线性规划问题 min z = 15x1 + 33x2，满足 3x1 + 2x2 - x3 = 6，6x1 + x2 - x4 = 6，x2 - x5 = 1，xj ≥ 0。

1. 写出其对偶问题
2. 已知原问题用两阶段法求解时得到的最终单纯形表，试写出对偶问题的最优解

终表中基变量行为 x4（3、1、-2、0、0、0）、x1（2/3、0、-1/3、0、1、0）、x2（4/3、-1、0、0、1、0）与检验数行 1、-2、3、0、-5、0；系数行 -33、-15、0、0、0。

第49页：综合题9 灵敏度分析

线性规划问题 max z = 2x1 - x2 + x3，满足 x1 + x2 + x3 ≤ 6，-x1 + 2x2 ≤ 4，xj ≥ 0，用单纯形法求解得最终单纯形表（基变量 x1 = 6、x3 = 1、x5 = 1，检验数行 -3、-1、-2、0、0）。试说明分别发生下列变化时，新的最终解是什么：

1. 目标函数变为 max z = 2x1 + 3x2 + x3
2. 第一个约束条件右端项由 6 变为 3
3. 增加一个新的约束 -x1 + 2x3 ≥ 2

第50页：综合题10 带储存费的运输问题

如表所示的运输问题：若产地 I 有一个单位物资未运出，则将发生储存费用，假定 1、2、3 产地单位物资储存费用分别为 5、4、3；又假定产地 2 的物资至少运出 38 个单位，产地 3 的物资至少运出 27 个单位，试求此运输问题的最优解。

源文件该页数字被打散连排，各产地与销地的运价、产量、销量对应按原文顺序整理，建议对照原图核对。

第51页：综合题11 加班生产目标规划

某企业生产两种产品：产品 1 售出后每件可获利 10 元，产品 2 售出后每件可获利 8 元。生产每件产品 1 需 3 小时的装配时间，生产每件产品 2 需 2 小时的装配时间。可用的装配时间共计为每周 120 小时，但允许加班。在加班时间内生产两种产品时，每件的获利分别降低 1 元；加班时间限定每周不超过 40 小时，企业希望总获利最大。

试凭自己的经验确定优先结构，并建立该问题的目标规划模型（设正常生产产量为 x1、x2，加班产量为 x1′、x2′，偏差变量按各级目标分别设置）。

第52页：综合题12 调运目标规划

某公司下属三个小型煤矿 A1、A2、A3，每天煤炭的生产量分别为 12 t、10 t、10 t，供应 B1、B2、B3、B4 四个工厂，需求量分别为 6 t、8 t、6 t、10 t。公司调运时依次考虑的目标优先级为：

• P1：A1 产地因库存限制，应尽量全部调出
• P2：因煤质要求，B4 最好由 A3 供应
• P3：满足各地需求
• P4：调运总费用尽可能少

源文件该页运价数字为连排排布，各行与销地的对应按原文顺序（B4、B3、B2、B1）整理，建议对照原图核对。

第53页：综合题13 匈牙利法求解

用匈牙利法求解下列指派问题，其效率矩阵元素为 3、7、10、9、2、2、8、7、3、8、5、5、7、3、2、2、4、4、6、8、10、9、6、10 一类（5 阶方阵）。

源文件该页效率矩阵的元素被打散连排，行列归属无法安全切分，未作表格还原，建议对照原图核对。

第54页：综合题14 动态规划基本方程

写出下题的动态规划基本方程：

max z = 5x1 - x1² + 9x2 - x2² 一类，满足 x1 + x2 ≤ 5，x1、x2 ≥ 0。

提示：以资源剩余量 sk 为状态、以 xi 的取值为决策，状态转移 sk+1 = sk - xk，基本方程写成 fk(sk) = max{ gk(xk) + fk+1(sk - xk) }，并给出边界条件 f3(s3) = 0。

源文件该页目标函数被打散连排（如 x1、x2 的平方项），具体形式建议对照原图核对。

第55页：综合题15 运输问题的动态规划模型

考虑一个有 m 个产地和 n 个销地的运输问题：设 ai 为产地 i 可发运的物资数，bj 为销地 j 需要的物资数，又从产地 i 至销地 j 运送 xij 单位物资的单价为 hij(xij)（即为运量的函数）。试将此问题建立为动态规划模型。

建模提示：以产地为阶段 k = 1, …, m，以剩余可发运物资量为状态，以分配给各销地的运量为决策，按基本方程递推求解。

第56页：第16题（题面待补充）

本页源文件仅提取到题号「16」，未提取到题目正文，仅有图片或竖排文字。

源文件该页文字缺失，建议对照原课件图片补充第 16 题的题面与配图说明。

第57页：模拟题 一、填空

模拟题 一、填空（10 分）

1. 线性规划问题中任何 m 个线性无关的列就构成了线性规划问题的一个基，该基对应的决策变量称为基变量
2. 最优解是指满足约束条件且使目标函数取最优值的可行解
3. 凡不是基本变量的变量叫做非基变量
4. 基变量的值为非负时的基本解称为基本可行解
5. 当大 M 法单纯形表在最终表仍有人工变量时，则原问题无可行解
6. 如果原问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数的最优值相等
7. 如果运输问题中的行与列相等，并供需量都是 1，这样的运输问题就是指派问题
8. x2 是一线性规划问题的决策变量，若 x2 是该单纯形表中的基变量，则它的检验数为0；若它的检验数大于零，则 x2 是换入变量
9. 当线性规划问题是求极大值时，人工变量在目标函数中的系数为-M，这样做法的目的是：人工变量的值若不为0，目标函数就求不到极大值

第58页：模拟题 二、单项选择

模拟题 二、单项选择（每空 3 分）

1. 下列哪一个结论是不正确的：A 解决分派问题可以用匈牙利法；B 分派问题是一种特殊的运输问题；C 匈牙利法是由匈牙利数学家 D. Konig 提出来的；D 分派问题不能用单纯形法求解（D 不正确）
2. 在求极小值线性规划问题中，正确的是：A 所有约束在求初始单纯形表中都要加入人工变量；B 初始单纯形表中不一定有人工变量；C 所有检验数都大于或等于零，必有最优解（B 正确）
3. 在有 m 个产地、n 个销地的产销平衡运输问题中，下述结论错误的是：A 空格有 mn - m - n + 1 个；B 基变量的个数就是数字格的个数；C 每一个空格都有一闭回路；D 运输问题就是线性规划问题

第59页：模拟题 选择续

已知线性规划问题 max z = 3x1 + 5x2，满足 x1 ≤ 4，2x2 ≤ 12，3x1 + 2x2 ≤ 18，x1、x2 ≥ 0，其最优解为 X = (2, 6)，则其对偶问题最优解为：

• A、Y = (3, 2, 0)
• B、Y = (0, 3/2, 1)
• E、Y = (3/2, 1, 1)
• H、Y = (3, 1, 2/3)

5、在调整某运输方案时，尽可能使空格处的运量增加的最大值为要减少的数字格的最小值，主要原因是：

• A 保证总运输费用的某种节俭得以实现
• B 保证不减少某个需求点的需要量
• C 保证任何一个有数字的格的运量不出现负数
• D 使这个运输方案不是最优的

源文件该页题干与选项被打散连排，选项字母与内容的对应按原文顺序整理，建议对照原图核对。

第60页：模拟题 三、四题

三、每题 5 分

1. 将下列线性规划问题化成标准型：max z = -x1 + 5x2 - 3x3，满足 x1 + 3x2 + x3 ≤ 2，x1 + 4x2 - 5x3 ≤ 30，x1 ≥ 0，x2 ≤ 0，x3 无约束
2. 写出下列线性规划的对偶问题：max z = -2x1 + 3x2 + 7x3，满足 4x1 - 5x2 + 4x3 = 20，x1 + x2 + x3 ≤ 30，x1、x2 ≥ 0，x3 无约束

四、用单纯形法求解下列线性规划问题（10 分）：max z = 2x1 + 3x2，满足 x1 + 2x2 ≤ 8，4x1 ≤ 16，4x2 ≤ 12，x1、x2 ≥ 0。

第61页：模拟题 第五题

五（10 分）：已知最终单纯形表（基变量行 x1 为 -1、4、0、6、1；x3 为 3、1/2、-1、1、1、0；右端项为 6、14、13 一类），检验数行为 -14、-9、0 等。

根据以上资料回答：

1. 写出最优解和最优函数值
2. 写出最优解不变的 c1 的变化范围

源文件该页单纯形表数字为连排排布，基变量与右端项的对应难以确认，建议对照原图核对。

第62页：模拟题 第六题

六、已知一产销平衡表和单位运价表：产地 A1、A2、A3，销地 B1、B2、B3、B4，产量分别为 7、4、9，销量分别为 3、6、5、6；运价表为 A1（3、11、3、10）、A2（1、9、2、8）、A3（7、4、10、5）。

用最小元素法得初始调运方案如下，上述调运方案是否为最优方案？若不是，进行一次调整（10 分）。

源文件该页数字为连排排布，运价与产销量的行列归属按教材常见数据整理，建议对照原图核对。

第63页：模拟题 第七题

七、某工厂准备安装三台机器（A、B、C），安装位置有四个（1、2、3、4），机器 B 不能安装在位置 3，其余没有限制。由于各处对这些机器的需要程度、离开某中心的远近不同，单位时间所需的原料运费也不同，估计运输成本如下。求最低运输成本的安装方案（10 分）。

表中给出位置 4、3、2、1 与机器 A、B、C、D 对应的运输成本（含 15、18、16、0、12、13、10、12、17、0、16、11、18、0 一类）。

源文件该页成本数字被打散连排，机器与位置的行列归属无法安全切分，未作表格还原，建议对照原图核对。

第64页：模拟题 第八、九题

八、1、1、1、2、3 能不能是某个简单图的次的序列，为什么？（5 分）

答：不能。因为简单图中各点的次之和必为偶数（等于边数的 2 倍），而 1 + 1 + 1 + 2 + 3 = 8 虽为偶数，但按 Havel-Hakimi 判定，删去次为 3 的点后剩余序列需由其他点各减 1，得到的序列中将出现负值与超出剩余点数的次，故不能构成简单图。

九、下图为一容量网络：(1) 试加一组可行流；(2) 判断其是否为网络最大流（10 分）。

图中各弧的容量为 s—a：2、s—b：3、s—c：3、a—b：2、a—d：3、b—d：4、c—d：4、c—e：3、d—t：2、e—t：3、2、3 一类。

源文件该页网络图的弧编号与容量数字为连排排布，弧的连接关系未提取成功，建议对照原图核对。

第65页：模拟题 第十题

十、用图解法求下列目标规划问题（10 分）：

min z = P1d1⁺ + P2d2⁻ + P3(d3⁻ + d3⁺)，满足 6x1 + 2x2 + d1⁻ - d1⁺ = 24，x1 + x2 + d2⁻ - d2⁺ = 5，5x1 + d3⁻ - d3⁺ = 15，x1、x2 ≥ 0，di⁻、di⁺ ≥ 0（i = 1, 2, 3）。

提示：先在平面上画出三条约束线，再按 P1、P2、P3 的顺序逐层缩小可行域，最后得到满意解所在的点或区域。