页数：58页文件大小：523.7 KB来源： 运筹学ppt课件
本课件系统讲授线性规划：由生产计划与污水处理实例归纳模型特征与一般形式，说明标准型转化与图解法四种解的情形；进而展开单纯形法的基本概念、单纯形表、最优性检验与换基迭代、大M法与两阶段法，最后给出线材下料与连续投资等应用。
本章内容分为三大部分：
例：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划能使该厂获利最多？
| 资源 | 产品Ⅰ | 产品Ⅱ | 资源限量 |
|---|---|---|---|
| 设备 | 1台时 | 2台时 | 8台时 |
| 原料A | 4kg | 0kg | 16kg |
| 原料B | 0kg | 4kg | 12kg |
| 单位利润 | 2元 | 3元 | — |
设计划期内产品Ⅰ、Ⅱ的产量分别为 x1、x2，可获利润用 z 表示，则该问题的数学模型为：
例：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m³，两工厂之间有一条流量为每天200万m³的支流。已知条件如下：
问：两工厂各应处理多少污水才能使处理污水的总费用最低？
设工厂1和工厂2每天分别处理污水 x1 和 x2 万m³，则有：
式中 0.8 = 1 - 20%，为污水流经两厂之间的自然净化系数。
以上两例都具有以下共同特征：
满足上述三个条件的数学模型称为线性规划模型，其一般形式如下：
目标函数：max(min) z = c1x1 + c2x2 + … + cnxn
约束条件：a11x1 + a12x2 + … + a1nxn ≤ (=, ≥) b1；a21x1 + a22x2 + … + a2nxn ≤ (=, ≥) b2；…；am1x1 + am2x2 + … + amnxn ≤ (=, ≥) bm
非负约束：x1, x2, …, xn ≥ 0
线性规划问题的标准型要求目标函数求最大值、约束条件为等式、右端常数非负：
max z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … + a1nxn = b1；a21x1 + a22x2 + … + a2nxn = b2；…；am1x1 + am2x2 + … + amnxn = bm
x1, x2, …, xn ≥ 0，其中 bi ≥ 0（i = 1, 2, …, m）
不符合标准型的情形主要有以下四类，可分别转化：
例：max z = 2x1 + 3x2，约束 x1 + 2x2 ≤ 8、4x1 ≤ 16、4x2 ≤ 12、x1, x2 ≥ 0。用图解法可得到以下四种结果：
结论：线性规划问题如果有最优解，则最优解一定在可行域的边界上取得，特别地，一定可在可行域的顶点上取得。
一、基本概念：
例：指出下列线性规划问题的基、基变量、基本解、基本可行解、可行基。
max z = 2x1 + 3x2，约束：2x1 + 2x2 + x3 = 12、x1 + 2x2 + x4 = 8、4x1 + x5 = 16（xj ≥ 0，j = 1, …, 5）
取基 B = (p1 p4 p5)，这是一个满秩矩阵，所以 B 是一个基；相应的基变量是 x1、x4、x5。令非基变量 x2 = x3 = 0，代入约束方程得 x1 = 6，x4 = 2，x5 = 9，故 X = (6, 0, 0, 2, 9) 是一基本解，也是一基本可行解，B 是一可行基。
源文件该页为公式与矩阵排版，约束方程与解向量按上下文还原，变量取值建议对照原图核对。
二、基本原理：
定理4的证明（前半部分）：x 不是基本可行解 → x 不是可行域的顶点。
不失一般性设 x 的前 m 个分量为正，且对应的系数列向量线性相关，故存在不全为零的 δi 使 δ1P1 + δ2P2 + … + δmPm = 0。取 μ ≠ 0，构造 X(1) = (x1 + μδ1, …, xm + μδm, 0, …, 0)、X(2) = (x1 - μδ1, …, xm - μδm, 0, …, 0)，使 X = 1/2·X(1) + 1/2·X(2)，所以 x 不是顶点。
该页为数学推导排版，符号层次较密，建议对照原图阅读。
定理4的证明（续）：x 不是可行域的顶点 → x 不是基本可行解。
不失一般性，设 X = (x1, x2, …, xr, 0, …, 0) 不是顶点，因而可以找到另外两个可行解 Y 和 Z，有 X = αY + (1-α)Z（0 ≤ α ≤ 1），也可写成 xj = αyj + (1-α)zj。因 α ≥ 0、(1-α) ≥ 0，故当 xj = 0 时必有 yj = zj = 0，于是 ΣPjyj = ΣPjzj = b。以上两式相减得 Σ(yj - zj)Pj = 0，因 (yj - zj) 不全为零，故 P1, P2, …, Pr 线性相关，即 X 不是基本可行解。
该页为数学推导排版，符号层次较密，建议对照原图阅读。
要找到线性规划问题的最优解，只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个（不超过 C(n,m) 个），但当 m、n 较大时，用「穷举法」求出所有基本可行解是行不通的，必须寻求更有效的方法。
单纯形法的基本思路：从线性规划问题的一个基本可行解开始，转换到另一个使目标函数值增大的基本可行解，反复迭代，直到目标函数值达到最大时，就得到了最优解。
为便于单纯形法的实施，用单纯形表描述线性规划问题的一个基本可行解的情况。设 x1, x2, …, xm 组成一组基变量，用高斯消去法把等式约束和目标函数变形后，把其系数列成数据表即单纯形表。
源文件该页为矩阵式排版，具体数值建议对照原图核对。
按照单纯形法的思路求解线性规划问题，要解决三个技术问题：
已知线性规划问题 max z = Σcjxj，Σaijxj ≤ bi（i = 1, …, m），xj ≥ 0。
加入松弛变量 xsi 化为标准型：max z = Σcjxj + 0·Σxsi，Σaijxj + xsi = bi（i = 1, …, m），xj ≥ 0。此时约束方程的系数矩阵中含有一个 m 阶单位矩阵，X = (0, …, 0, b1, …, bm) 就是一个基本可行解。
源文件该页系数矩阵为排版格式，此处按公式语义还原，建议对照原图核对。
初始单纯形表按如下结构填制：
源文件该页为表格排版，数值建议对照原图核对。
将基本可行解 X(0) 与 X(1) 分别代入目标函数，由 θ > 0 可知，只要 cj - Σciaij > 0 就有 z(1) > z(0)，称 σj 为检验数。检验方法如下：
设初始基本可行解为 X(0) = (x1⁰, x2⁰, …, xm⁰, 0, …, 0)。因 P1, …, Pm 是一个基，其它向量可用这个基线性表示，即 Pj = ΣaijPi。由此可得另一点：
X(1) = (x1⁰ - θa1j, …, xm⁰ - θamj, 0, …, θ, …, 0)
要想使 X(1) 是一个基本可行解，因 θ > 0，应对所有 i 有 xi⁰ - θaij ≥ 0，令 θ = min{ xi⁰/aij | aij > 0 }，则 X(1) 中的正分量最多有 m 个，且 m 个向量 P1, …, Pl-1, Pl+1, …, Pm, Pj 线性无关，故 X(1) 是一新的基本可行解。
该页为数学推导排版，建议对照原图核对下标对应关系。
换入变量 xk 取代换出变量 xl 后，单纯形表按下述规则更新：
源文件该页为矩阵排版，具体数值建议对照原图核对。
基变换的三个步骤：
用单纯形法求解线性规划问题的具体步骤如下：
用单纯形法求解线性规划问题后，应回答下面几个问题：
例：max z = 2x1 + 3x2，约束 x1 + 2x2 ≤ 8、4x1 ≤ 16、4x2 ≤ 12，x1, x2 ≥ 0。
加入松弛变量 x3、x4、x5 化为标准型：
max z = 2x1 + 3x2，约束 x1 + 2x2 + x3 = 8、4x1 + x4 = 16、4x2 + x5 = 12，x1, x2, x3, x4, x5 ≥ 0
对于 max z = 2x1 + 3x2（约束同第29页标准型），依次以 x3、x4、x5 为初始基变量，经四次迭代后得到最终单纯形表，此问题的最优解为：
迭代中检验数依次由 (2, 3, 0, 0, 0) 变换，最终全部非基变量检验数 σj ≤ 0，故为唯一最优解。
源文件该页单纯形表数值排列错乱（如「x*=4,x*=2,x*=4,x*=x*=0」），此处按模型标准答案给出 x1=4、x2=2、x5=4、z*=14，建议对照原图核对表中各列数值。
例：min z = -3x1 + x2 + x3，约束 x1 - 2x2 + x3 ≤ 11、-4x1 + x2 + 2x3 ≥ 3、-2x2 + x3 = 1，x1, x2, x3 ≥ 0。
令 z′ = -z 化为 max z′ = 3x1 - x2 - x3，并加入松弛变量 x4、剩余变量 x5 与人工变量 x6、x7 后，标准型为：
max z′ = 3x1 - x2 - x3 - Mx6 - Mx7，约束 x1 - 2x2 + x3 + x4 = 11、-4x1 + x2 + 2x3 - x5 + x6 = 3、-2x1 + x3 + x7 = 1，x1, …, x7 ≥ 0
第三个约束源文件写作「-2x2 + x3 + x7 = 1」，而原式含 -2x2，标准型中按原式取 -2x2；两处表述不一致，建议对照原图确认。M 为充分大的正数。
对上页大M法算例，以 x4、x6、x7 为初始基变量，含 M 的检验数行按 cj - zj 计算，经三次迭代得到最终单纯形表。此问题的最优解为：
因人工变量 x6、x7 最终均为 0，故原问题有可行解。
源文件该页单纯形表数值排列错乱，此处按模型标准答案整理，表中各列系数建议对照原图核对。
记线性规划问题为 max z = cx，约束 Ax = b，X ≥ 0。其中 A = (aij)m×n = (B N)，价值向量 c = (cB, cN)，变量 X = (xB, xN)。
由 BX B + NX N = b 解出：X B = B⁻¹(b - NX N) = B⁻¹b - B⁻¹NX N。相应于 B 的基本可行解自然是 X B = B⁻¹b，X N = 0，得 z = cB B⁻¹b。
为判断该解是否为最优解，将其代入 Z 值：
z = cB B⁻¹b + (cN - cB B⁻¹N) X N
其中 cN - cB B⁻¹N 为非基变量的检验数。
矩阵形式的单纯形表结构如下：
当所有检验数都小于等于 0 时，此解为最优解；当有检验数大于 0 时，可继续迭代求解。
源文件该页为矩阵排版，具体栏目数值建议对照原图核对。
首先构造一个矩阵 H：在一个 m×m 的单位矩阵中抽掉第 l 列，换上另一列 (-a1k/alk, …, 1/alk, …, -amk/alk)ᵀ。
将 H 左乘迭代前的基的逆矩阵 B⁻¹old，就可以得到迭代后的基的逆矩阵 B⁻¹new = H · B⁻¹old。
源文件该页为矩阵排版，列向量元素建议对照原图核对。
例：max z = 4x1 + 2x2，约束 -x1 + 2x2 ≤ 6、x1 + x2 ≤ 9、3x1 - x2 ≤ 15，x1, x2 ≥ 0。
先化为标准形：max z = 4x1 + 2x2 + 0x3 + 0x4 + 0x5，约束 -x1 + 2x2 + x3 = 6、x1 + x2 + x4 = 9、3x1 - x2 + x5 = 15，x1, …, x5 ≥ 0。其中 b = (6, 9, 15)ᵀ，c = (cN, cB) = (4, 2, 0, 0, 0)。
源文件该页系数矩阵为排版形式，此处按语义还原，建议对照原图核对。
求解过程如下：
故本次迭代中的解 (x1, x2, x3, x4, x5) = (6, 3, 6, 0, 0) 即为问题的最优解。
源文件该页迭代矩阵数值排列密集且部分缺失，此处按标准答案整理，建议对照原图核对。
一、解的判别：
例：max z = 2x1 + 4x2，约束 2x1 + 2x2 ≤ 12、x1 + 2x2 ≤ 8、x1 + 3x2 ≤ 9（原文第三个约束写作 3x2 ≤ 9 一类形式），x1, x2 ≥ 0。
用单纯形法求解并得最终单纯形表：作为非基变量的 x3 的检验数为零，把 x3 换入基变量中，得到另一组基本可行解，且目标函数值不变，故该问题有无穷多最优解。
源文件该页约束与单纯形表数值排版不完整，此处仅保留结论性说明，具体数值建议对照原图核对。
用单纯形法求解时，如果存在某个 σj > 0，而且向量 pj 的所有元素 aij ≤ 0，则有无界解。
例：max z = 2x1 + 3x2，约束 x1 - x2 + x3 = 1、x1 + x4 = 2（xj ≥ 0，j = 1, …, 4）。表中 σj > 0 但 x2 列数字为 0，即 x2 的取值可无限增大而不受限制，由此目标函数值也可无限增大，说明问题的解无界。
源文件该页约束与表体数值排版不完整，建议对照原图核对。
前面讨论了约束条件为 Σaijxj ≤ bi 的线性规划问题求初始基本可行解的方法。当约束条件中有等式约束、而系数矩阵中又没有单位矩阵时，可添加人工变量来人为地在系数矩阵中构造一个单位矩阵，以它为初始可行基；若约束条件是「≥」型的不等式，则先减去剩余变量变成等式，再用人工变量法。
例：max z = -3x1 + x3，约束 x1 + x2 + x3 ≤ 4、-2x1 + x2 - x3 ≥ 1、3x2 + x3 = 9，xj ≥ 0（j = 1, 2, 3）。
变成标准形后，约束方程组的系数矩阵中没有 3 阶单位矩阵，因此在后两个约束的左边各加一个人工变量 x6、x7，约束变为：
x1 + x2 + x3 + x4 = 4；-2x1 + x2 - x3 - x5 + x6 = 1；3x2 + x3 + x7 = 9
目标函数变为 max z = -3x1 + x3 + 0x4 + 0x5 - Mx6 - Mx7，其中 M 代表一个充分大的数。由于人工变量在目标函数中的系数是 -M，它的取值若不为 0，目标函数就不能极大化。
对上页算例，以 x4、x6、x7 为初始基变量，按含 M 的检验数逐步迭代（依次换入 x2、x3、x1），得到最终单纯形表。最优解为：
源文件该页单纯形表数值排列密集，此处按标准答案整理，表中各列系数建议对照原图核对。
例：max z = 2x1 + 3x2，约束 2x1 + 2x2 ≤ 12、?x1 + 2x2 ≥ 14，xj ≥ 0（j = 1, 2）。
用图解法求解可知该问题无可行解。用大M法求解时，先变成标准形并添加人工变量 x5，再用单纯形法求解；最终表中人工变量 x5 仍保留在基中且取值不为零，据此判断原问题无可行解。
源文件该页第二个约束系数缺失（排版为「?x1 + 2x2 ≥ 14」），且表中数值不完整，建议对照原图补全。
例：max z = -3x1 + x3，约束 x1 + x2 + x3 ≤ 4、-2x1 + x2 - x3 ≥ 1、3x2 + x3 = 9，xj ≥ 0。
变成标准形并加入人工变量 x6、x7 后，第一阶段的模型为：
min z = x6 + x7，约束 x1 + x2 + x3 + x4 = 4、-2x1 + x2 - x3 - x5 + x6 = 1、3x2 + x3 + x7 = 9，xj ≥ 0（j = 1, …, 7）
用单纯形法求解第一阶段，得到最终单纯形表，由此得到原问题的一个可行基。
第二阶段：将上阶段中的人工变量除去，目标函数变为 max z = -3x1 + 0x2 + x3 + 0x4 + 0x5，再从第一阶段最终单纯形表出发，继续用单纯形法计算。
第一阶段最终表给出的可行解为 x1 = 0、x2 = 5/2、x3 = 3/2，第二阶段在其基础上迭代，得到原问题的最优解。
源文件该页表体数值排列不完整，建议对照原图核对。
关于线性规划问题的求解，有许多好的专业软件和商务软件。最简便易行的求解软件是 Excel，其使用方法如下：
例：现要做一百套钢管，每套要长为 2.9m、2.1m 和 1.5m 的钢管各一根。已知原料长 7.4m，问应如何下料，使用的原料最省。先列出可能的裁料方案：
| 裁料方案 | Ⅰ | Ⅱ | Ⅲ | Ⅳ | Ⅴ | Ⅵ | Ⅶ | Ⅷ |
|---|---|---|---|---|---|---|---|---|
| 2.9m 根数 | 2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2.1m 根数 | 0 | 2 | 1 | 0 | 3 | 2 | 1 | 0 |
| 1.5m 根数 | 1 | 0 | 1 | 3 | 0 | 2 | 3 | 4 |
| 料头（m） | 0.1 | 0.3 | 0.9 | 0 | 1.1 | 0.2 | 0.8 | 1.4 |
设用方案 Ⅰ, Ⅱ, …, Ⅷ 分别裁原料钢管 x1, x2, …, x8 根，则有：
min z = x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8
2x1 + x2 + x3 + x4 ≥ 100；2x2 + x3 + 3x5 + 2x6 + x7 ≥ 100；x1 + x3 + 3x4 + 2x6 + 3x7 + 4x8 ≥ 100；x1, …, x8 ≥ 0
源文件方案表按「Ⅷ…Ⅰ」倒序排列且数字连排，此处已按列对齐还原为「Ⅰ…Ⅷ」顺序，各方案料头由 7.4m 原料长度核算一致。
例：某工厂要用三种原材料 C、P、H 混合调配出三种不同规格的产品 A、B、D。已知产品的规格要求、单价和原料的供应量、单价如下：
| 产品名 | 规格要求 | 单价 |
|---|---|---|
| A | 原料C不少于50%，原料P不超过25% | 50元/kg |
| B | 原料C不少于25%，原料P不超过50% | 35元/kg |
| D | 不限 | 25元/kg |
| 原料名 | 每天最多供应量 | 单价 |
|---|---|---|
| C | 100kg | 65元/kg |
| P | 100kg | 25元/kg |
| H | 60kg | 35元/kg |
问：该厂应如何安排生产，能使利润最大？
记产品 A、B、D 中 C、P、H 的含量分别为 AC, AP, AH, BC, BP, BH, DC, DP, DH，令其为 x1, x2, …, x9，则有：
例：成批生产企业年度生产计划的按月分配。在年度计划按月分配时一般要考虑：
考虑以上条件，使设备负荷均衡并使利用率最大化。假定工厂有 m 类设备（用 i 表示），生产 n 种产品（用 j 表示），各产品的全年计划量用 dj 表示，aij 表示加工单位 j 种产品所需要的第 i 类设备的台时数，bik 表示 k 月份第 i 类设备的生产能力（台时）。再假定第 5、8 两种产品下半年投产，第 4 号产品要求二月初交货。
如要对全年 12 个月同时考虑，会使模型非常复杂，因此从 1 月到 12 月一个月一个月地分别建模计算。设 k 月份计划生产 j 种产品的数量为 xjk。
例：某厂计划期分为 n 个阶段，在第 j 个阶段生产上要用 rj 个专用工具。到阶段末，凡在这个阶段内使用过的工具都应送去修理后才能再使用。修理可分为两种方式进行：
设 xj 表示第 j 个阶段新购工具数，yj 表示第 j 个阶段末送去慢修的工具数，zj 表示第 j 个阶段末送去快修的工具数，sj 表示第 j 个阶段末工具的存储数。问应如何综合考虑使总的费用最小。
该问题的数学模型为：
源文件该页公式为连排排版，约束各阶段的下标区间（如 j = q+2, …, p+1 与 j = p+2, …, n）建议对照原图核对。
例：某单位有资金 10 万元，在今后 5 年内可考虑下列投资项目：
问：应如何安排每年的投资，使到 5 年末拥有的资金最多？
解：每年的投资额应不超过手中的资金。由于项目 D 每年都可投资、且当年末就可收回，所以该单位每年必然把资金全部投出去，即投资额等于手中的资金数。设第 i 年投资各项目的资金为 xiA、xiB、xiC、xiD，数学模型为：
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}