第三章 线性规划的对偶理论.ppt

1 第三章对偶理论 DualityTheory 线性规划对偶问题的提出 线性规划的矩阵表示 对偶问题的性质 对偶单纯形法 灵敏度分析 应用实例 2 第一节对偶规划问题 一 对偶问题的基本概念1 对偶现象 事物的两面性 例如 1 在周长一定的四边形中 以正方形的面积最大 2 在面积一定的四边形中 以正方形的周长最小 这是一个现象的两个提法 我们称这两种情况互为对偶 其中一个问题为原问题 另外一个问题为原问题的对偶问题 3 例1 1某制药厂用甲 乙两台机器生产A B两种药物 每种药物要经过两道工序 在甲机器上搅拌 在乙机器上包装 已知在未来两周内 甲 乙两台机器的使用时间分别不得超过40小时和30小时 生产每公斤药物A的利润是30元 B是25元 生产每公斤药物所需的加工时间如表所示 试问 如何安排这两周的生产 能使工厂利润最大 2 对偶问题 Maxz 30 x1 25x2s t 2x1 4x2 403x1 2x2 30 x1 x2 0 A x1公斤 B x2公斤 4 设y1 y2分别为出租资源设备甲 乙每工时收取的费用 Minw 40y1 30y2 租金额最小 s t 2y1 3y2 30 药物A的租金不少于药物A的利润 4y1 2y2 25 药物B的租金不少于药物B的利润 y1 y2 0 若第二章例1中制药厂的设备都用于外协加工 即该厂的决策者不是考虑自己生产甲 乙两种产品 而是将厂里的现有资源用于接受外来加工任务 工厂只收取加工费 试问 设备甲 乙每工时各应如何收费才最有竞争力 下面从另一个角度来讨论这个问题 分析问题 1 每种资源收回的费用不能低于自己生产时的可获利润 2 定价又不能太高 要使对方能够接受 5 Maxz 30 x1 25x2s t 2x1 4x2 403x1 2x2 30原问题x1 x2 0Minw 40y1 30y2s t 2y1 3y2 304y1 2y2 25对偶问题y1 y2 0 线性规划的对偶 每一个线性规划 LP 必然有与之相伴而生的另一个线性规划问题 其中的一个问题叫 原问题 记为 LP 另一个称为 对偶问题 记为 DP 6 3 影子价格在上例中 对偶问题的最优解为原问题约束条件的影子价格 解yi称为第i种资源 设备 的影子价格 影子价格并非市场上的真实价格 而是企业根据本企业的具体生产过程 为使药物A B实现最大利润而得到的一种估计价格 为了与市场价格相区别 我们称它为影子价格 影子价格是厂家对所拥有的资源的稀缺程度的一种度量 是相对于具体厂家而言的 影子价格提供了一个价格的标准 如果市场上某种资源的价格低于影子价格 那么应当购进这种资源 增加生产 提高利润 反之就应该售出这种资源 求得更高的利润 7 对称形式 互为对偶 LP Maxz cx DP Minf bTys t Ax bs t ATy cTx 0y 0 Max Min 二 对称形式的对偶线性规划 8 一对对称形式的对偶规划之间具有下面的对应关系 1 若一个模型为目标求 极大 约束为 小于等于 的不等式 则它的对偶模型为目标求 极小 约束是 大于等于 的不等式 即 max 和 min 相对应 2 从约束系数矩阵看 一个模型中为 则另一个模型中为AT 一个模型是m个约束 n个变量 则它的对偶模型为n个约束 m个变量 3 从数据b C的位置看 在两个规划模型中 b和C的位置对换 4 两个规划模型中的变量皆非负 9 1对偶规划问题P 44任一L P 问题 都有一个与之密切相关的L P 问题 叫对偶问题 给定一个L P 问题 如何引出其对偶问题 见P 52 表3 1 x1x2 xn原关系Min y1a11a12 a1n b1y2a21a22 a2n b2 ymam1am2 amn bm对偶关系 X 0 Y 0 MaxZc1c2 横向组合得原问题 MaxZ c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmX 0 纵向组合得对偶问题 Min b1y1 b2y2 bmyma11y1 a21y2 am1ym c1a12y1 a22y2 am2ym c2 a1ny1 a2ny2 amnym cnY 0 若写成矩阵形式 可得 原问题 对偶问题 MaxZ CXMin bTYAX bATY CTX 0Y 0注意 其中C是行向量 X Y与b是列向量 Amn为aij所构成的矩阵 2 3 4 1 10 其矩阵形式为 对偶 原 问题为 以下举例说明对偶问题的作法 见P 52例2原 对偶 问题 MinZ 2x1 5x2y1x1 4y2x2 3y3x1 2x2 8x1 x2 0 x1x2 101012 y1y2y3 对偶 原 问题为 MaxW 4y1 3y2 8y3y1 y3 2x1y2 2y3 5x2y1 0 y2 0 y3 0 25 100112 438 y1y2y3 X o Y o MaxW 4 3 8 原 对偶 问题 MinZ 2 5 11 写出下面线性规划的对偶规划 1 maxz 2x1 3x22x1 2x2 12x1 2x2 8s t 4x1 164x2 12x1 x2 0 2 12 Minw 12y1 8y2 16y2 12y2 s t 2y1 y2 4y3 2 2y1 2y2 4y4 3 y1 y2 y3 y4 0 解 2 首先将原式变形 对偶问题 解 1 13 三 非对称的对偶线性规划对于对称形式的线性规划可按上述规则写出其对偶规划 但是经常遇到的是非对称形式的线性规划问题 dualofanonnormalLP 这时可将其转化为等价的 满足对称形式条件的线性规划问题 然后再按照对称形式的原问题与对偶问题的对应关系表 构造其对偶问题 在非对称形式向对称形式转化的过程中 若原问题是求目标函数极大 约束条件不等式为 可在不等式两端乘以 1 将 化为 若决策变量xj或yi 0 则令xj xj或yi yi 将决策变量化为非负值 对于约束条件是等式的标准型形式的原问题 可由下述方法导出其对偶规划问题 例如 对约束条件是等式的LP问题maxz CXs t AX bX 0 14 s t AX bX 0由于AX bAX b即 AX b AX b AX b AX b 所以 原问题可化为maxz CXs t AX b AX bX 0 AbX A b 15 设Y AX b的对偶变量 行向量 Y AX b的对偶变量 行向量 按对称形式的对偶关系可得出原问题的对偶问题如下 minw Y b Y b Y Y b Yb bTYT s tY A Y A C YA ATYT Y 0 Y 0令Y Y Y 则对偶问题为minw Ybs tYA CY符号不限结论 原问题中约束条件为等式 对应的对偶变量无非负要求 反过来同样成立 16 求下列原问题的对偶问题 maxz 4x1 5x2s t 3x1 2x2 204x1 3x2 10 x1 x2 5x1 0 x2符号不限 解 首先将原问题化成对称形式 令x2 x3 x4 x3 0 x4 0 原问题化为 maxz 4x1 5x3 5x4s t 3x1 2x3 2x4 20 4x1 3x3 3x4 10 x1 x3 x4 5 x1 x3 x4 5x1 x3 x4 0 将对称形式线性规划问题化为对偶问题如下 17 MinW 20w1 10w2 5w3 5w4s t 3w1 4w2 w3 w4 42w1 3w2 w3 w4 5 2w1 3w2 w3 w4 5 w1 w2 w3 w4 0 1 得2w1 3w2 w3 w4 5令y1 w1 y2 w2 y3 w3 w4 得MinW 20y1 10y2 5y3s t 3y1 4y2 y3 42y1 3y2 y3 5y1 y2 0 y3符号不限 18 原规划与对偶规划的线性关系 56表3 3 19 对于非对称形式的规划 可以按照下面的对应关系直接给出其对偶规划 1 对原问题模型为 max 约束条件为 或 min 约束条件为 的形式 对应的对偶规划的变量大于0 反之 若原问题模型为 max 或 min 的形式 对应的对偶规划的变量小于0 2 原问题线性规划的决策变量大于0 则对偶问题的模型为 max 约束条件为 或 min 约束条件为 的形式 若原问题线性规划的决策变量小于0 则对偶问题的模型为 max 或 min 的形式 非对称形式的对偶规划 3 若原规划的某个约束条件为等式约束 则在对偶规划中与此约束对应的那个变量取值没有非负限制 4 若原规划的某个变量的值没有非负限制 则在对偶问题中与此变量对应的那个约束为等式 20 maxz 4x1 5x2s t 3x1 2x2 204x1 3x2 10 x1 x2 5x1 0 x2符号不限MinW 20y1 10y2 5y3s t 3y1 4y2 y3 42y1 3y2 y3 5y1 0 y2 0 y3符号不限MinW 20y1 10y2 5y3s t 3y1 4y2 y3 42y1 3y2 y3 5y1 y2 0 y3符号不限 21 例写出下面线性规划的对偶规划模型 解 先将约束条件变形为如下形式 22 再根据非对称形式的对应关系 直接写出对偶规划 maxz x1 x2 5x3 7x4 23 求下列原问题的对偶问题 1 maxz 2x1 3x2s t 2x1 x2 154x1 3x2 20 x1 x2 0 2 maxz 3x1 6x2 5x3 4x4s t x1 2x2 3x3 4x4 53x1 x2 x3 7x4 14 4x1 5x2 3x3 2x4 3x1 x2 0 x3 x4符号不限 24 解答 1MinW 15y1 20y2s t 2y1 4y2 4y1 3y2 3y1符号不限 y2 02MinW 5y1 14y2 3y3s t Y1 3y2 4y3 32y1 y2 5y3 6 3y1 y2 3y3 5 y1 7y2 2y3 4y2 0 y3 0 y1符号不限 25 练习 26 答案 27 作业题 课后习题二第1题 P79 80页 28 四 线性规划的矩阵表示 29 30 31 XB Xj 请分别指出 B 1 B 1 CN CBB 1N CI CBB 1 32 习题 一个极大化 目标函数为maxZ 的线性规划问题 有三个非负变量x1 x2 x3 两个 型约束条件 x4 x5是松弛变量 用单纯形法计算时得到的初始单纯型表及最终单纯型表如下 最优单纯型表中 x1 x5为基变量 请将表中空白处数字填上 1 0 0 1 1 3 6 10 1 1 0 3 1 2 0 33 性质一 对称性定理 对偶问题的对偶是原问题 第二节对偶问题的性质 34 其他形式问题的对偶 原问题与对偶问题互为对偶 任意一个原问题经过两次对偶形式的转换后 必定等价于原问题 35 性质二弱对偶性若X 为原问题 最大化 的可行解 Y 为对偶问题 最小化 的可行解 则CX Y b Maxz 30 x1 25x2 CX s t 2x1 4x2 403x1 2x2 30原问题x1 x2 0Minw 40y1 30y2 Y bs t 2y1 3y2 304y1 2y2 25对偶问题y1 y2 0 36 z 30 x1 25x2 w 40y1 30y2 LP Maxz cx DP Minf ybs t Ax bs t yA cx 0y 0 Max Min yAx ybyAx cx由上面两个不等式 yb cx 弱对偶定理说明 如果原问题是最大化问题 则它的任一可行解对应的目标函数值不大与其对偶问题 最小化问题 的可行解对应的目标函数值 37 性质三 最优性判定定理 可行解是最优解时的性质当X 是原问题 Max 的可行解 Y 是其对偶问题 Min 的可行解时 若CX Y b 则X 与Y 是各自问题的最优解 证明 设X 是原问题的任意一个可行解 由性质2即弱对偶定理可知 CX Y b 又由CX Y b知 CX Y b CX 就是说 X 使目标函数所达到的值比其它任何可行解使目标函数所达到的值不会小 所以X 是最优解 同理 设Y b CX Y b Y 是其对偶问题的最优解 证毕 38 性质四 强对偶定理 若原问题有最优解 则对偶问题也有最优解 且目标函数最优值相等 证明设原问题的形式为 MaxZ CX AX b X 0 于是AX XS b 即 A I b 其中A为mxn矩阵 I为m阶单位矩阵 XS为m维列向量 既知有最优解 必有最优基变量对应的矩阵 记之为B 那么 在最终单纯形表中 检验数所形成的行向量为 C CBB 1A CBB 1 0 于是C CBB 1A 0 即CBB 1A C YA C 令Y CBB 1 又 CBB 1 0 即CBB 1 0 可得Y CBB 1 0 则YA C Y 是对偶问题 MinW Yb YA C Y 0 的可行解 而W Y b CBB 1b 因为B是最优基变量对应的矩阵 所以Zmax CX CBB 1b Y b 由性质3 定理获证 XXS 对偶性质4 39 性质五 52页 互补松驰定理若X 与Y 分别为原问题和对偶问题的可行解 那么Y XS 0和YSX 0的充分必要条件是X Y 为最优解 XS与YS分别为原问题和对偶问题的松弛变量和剩余变量 MaxZ CXAX XS bX 0 MinW YbYA YS CY 0 证明必要性 设原问题和对偶问题的标准形式分别为 和于是C YA YS b AX XS 所以Z X CX YA YS X YAX YSX 而W Y Yb Y AX XS YAX YXS可见 若Y XS YSX 0 则Z X Y AX W Y 由性质3知X Y 为最优解 必要性获证 以下证充分性 若X 与Y 分别为原问题和对偶问题的最优解 由性质4可知Z X Y AX YSX Y AX Y XS W Y 又由于X 与Y 为可行解 存在X Y XS YS 0 则必有YSX 0 Y XS 0 于是由上式知Y XS YSX 0 充分性获证 完 40 原始问题和对偶问题最优解之间的互补松弛关系 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 互补松弛关系 41 设有L P 问题MaxZ x1 2x2 3x3 4x4x1 x2 2x3 3x4 202x1 x2 3x3 2x4 20 xj 0 1 j 4已知其对偶问题的最优解为 y1 1 2 y2 0 2 相应的目标函数值W 28 试用对偶理论求原问题的解 解 其对偶问题为 MinW 20y1 20y2y1 2y2 12y1 y2 22y1 3y2 33y1 2y2 4y1 y2 0 x1x2x3x4 42 MaxZ x1 2x2 3x3 4x4x1 x2 2x3 3x4 u1 202x1 x2 3x3 2x4 u2 20 MinW 20y1 20y2y1 2y2 v1 12y1 y2 v2 22y1 3y2 v3 33y1 2y2 v4 4y1 y2 0 x1x2x3x4 将y1 1 2 y2 0 2代入对偶问题的约束条件 得 1 2 为严格不等式 所以v1 0 v2 0 由互补松弛性得x1 v1 x2 v2 0 所以x1 x2 0 又因为 y1 0 y2 0 所以u1 u2 0 即原问题的两个约束条件为等式约束 故得方程组 2x3 3x4 203x3 2x4 20 解之得x3 x4 4 而W Z 28 故原问题的最优解为 X 0 0 4 4 T W 28 1 2 3 4 43 练习题 设有L P 问题 已知原问题的最优解为X 0 0 4 Z 12试求对偶问题的最优解 解 其对偶问题为 将X 0 0 4 代入原问题中 有下式 44 1 2 3 将X 0 0 4 代入原问题中 有下式 所以 根据互补松弛条件y1 xs1 y2 xs2 0 必有y1 y2 0 代入对偶问题 3 式 y3 3 因此 对偶问题的最优解为Y 0 0 3 W 12 45 性质六 62页 原问题的检验数对应于对偶问题的一个基本解 MaxZ CXAX XS b X 0 MinW YbYA YS CY 0 A B N C CB CN Y B N CB CN Y 0或YB Ys1 CB YN Ys2 CN Y 0 Ys1 0 Ys2 0 Ys1 Ys2分别对应原问题基变量和非基变量的检验数 假设原问题找到了一个基本可行解 XB 0 对应的检验数 0 CN CBB 1N CI CBB 1 分别令检验数的相反数为 Ys1 0Ys2 CN CBB 1N Y CBB 1将其带入约束条件式 满足上式 则说明原问题的检验数的相反数是其对偶问题的一个解 得证 46 设原问题为 MaxZ CX AX XS b 0 X 0 XS 0 对偶问题为 MinW Yb YA YS C Y 0 YS 0 则原问题单纯形表的检验数行 对应于其对偶问题的一个基解 性质6的意思究竟是什么 先列出原问题的单纯形表 表中给出了对偶问题的变量与原问题各检验数的对应关系 当给出了原问题的一个基后 算出各检验数 反号之后 就得到对偶问题的一个基本解 X Xs 中的 基变量 非基变量分别对应于 Ys Y 中的 非基变量 基变量 性质6 x1x2 xnxs1xs2 xsma11a12 a1n10 0a21a22 a2n01 0 am1am2 amn00 1 1 2 n n 1 n 2 n mys1ys2 ysny1y2 ym 47 结论 由性质6可知 在用单纯形法求解原问题的过程中 每迭代一次 得到原问题的一个基本可行解 其检验数的相反数则是对偶问题的一个基本解 当找到最优解时 对应的检验数都是非正的 其相反数则是对偶问题的一个基本可行解 Y CBB 1是对偶问题的最优解 原问题约束条件的影子价格 48 以第二章第三节的例7为例 表2 3 2 4 2 5给出了单纯形法的迭代过程 试分别对这三个表指出其对偶问题的解 XB Xj 49 解 由性质6 原问题的检验数的相反数对应于对偶问题的基本解 可得到表2 3对偶问题的基本解为 0 0 30 25 表2 4对偶问题的基本解为 0 10 0 5 表2 5对偶问题的最优解为 15 8 35 4 0 0 50 XB Xj 诊疗问题 教材第37页 试分别对这三个表指出其对偶问题的解 51 解 由性质6 原问题的检验数的相反数对应于对偶问题的基本解 可得到表1对偶问题的基本解为 0 0 0 10 4 表2对偶问题的基本解为 0 20 3 0 0 2 3 表3对偶问题的最优解为 0 6 1 0 0 52 作业题 P80页 掌握对偶问题的7个性质 习题二第2题 第2题分别用性质5和性质6求对偶问题的最优解 习题二第3题 习题二第5题 1 2 53 其他性质无界性若原问题 对偶问题 为无界解 则其对偶问题 原问题 为无可行解 证明 若原问题为最大化问题 由题意CX 所以若对偶问题 最小化 有可行解Y 根据性质2 CX Y b 于是CX 将有上界 与CX 无界矛盾 证毕 若原问题为最小化问题 由题意Y b 所以若对偶问题 最大化 有可行解X 根据性质2 CX Y b 于是Y b将有下界 与Y b无界矛盾 证毕 注意 本性质的逆不成立 当原问题 对偶问题 无可行解时 其对偶问题 原问题 可以没有可行解 见下例 也可以是无界解 但决没有最优解 54 原问题与对偶问题均无可行解原 对偶 问题 对偶 原 问题 MinZ x1 x2MaxW y1 y2s t x1 x2 1s t y1 y2 1 x1 x2 1 y1 y2 1x1 x2 0y1 0 y2 0 综上所述 互为对偶的线性规划原问题与对偶问题 它们之间解的对应关系仅仅存在下面的三种可能 1 两个问题都有可行解 则他们都存在最优解 且他们的最优解的目标函数值相等 2 一个问题有无界可行解 而另一个问题无可行解 3 两个问题均无可行解 55 习题判断下列说法是否正确 为什么 1 如线性规划的原问题存在可行解 则其对偶规划问题也一定存在可行解 2 如线性规划的对偶问题无可行解 则原问题也一定无可行解 错 当原问题有无界解时 此时当然有可行解 其对偶问题无可行解 2 答 1 答 错 原问题可以有无界解时 此时当然有可行解 也可以无可行解 56 资源影子价格 对偶问题是资源定价问题 对偶问题的最优解y1 y2 ym称为m种资源的影子价格 ShadowPrice 影子价格越大 说明这种资源越是相对紧缺 影子价格越小 说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余 这种资源的影子价格一定等于0 互补松弛定理 资源效益分析和影子价格 原始和对偶问题都取得最优解时 最大利润maxz minw 57 如果某种资源的影子价格yi 0 则增加该种资源的供给量可获得更多的收益 那么从企业的经营角度是否应增加这种资源的供给呢 此时要视获取该种资源的成本也即市场价格而定 设该资源的市场价格为yi0 企业增加资源投入量 bi后利润的增加量 bi yi yi0 所以影子价格提供了一个价格的标准 如果市场上某种资源的价格低于影子价格 当yi00 那么应当购进这种资源 增加生产 提高利润 反之 当yi0 yi 时 利润增量 0 则不宜去扩大生产 可适当出售或出租 求得更高的利润 58 表3 13放射科3项检查资源需求 资源限制及利润 A医院放射科目前可以开展X线平片检查 CT检查和磁共振检查业务 经过资料收集和信息处理 A医院估计今后放射科如果开展此3项业务 在现有放射科医务人员力量和病人需求的情况下 每月此3项业务的最多提供量为1800人次 平均每人次检查时间 每月机器实际可使用时间 平均每人次检查利润如表3 13 应用实例 教材第75 79页 59 XB Xj 模型 maxZ 20 x1 60 x2 10 x3 x1 x2 x3 0 s t 0 1x1 3000 25x2 1200 5x3 120 x1 x2 x3 1800 每月业务量X线 x1次 CT x2次 磁共振 x3次 问题 1 A医院从放射科收益的角度考虑 如何开展最优业务量 2 在最优业务安排情况下 A医院如何利用影子价格进行决策 60 1 该线性规划模型的最优解X 1320 480 0 168 0 120 0 T 最优值Z 55200 则A医院从放射科收益的角度考虑 在每月X线平片检查和CT检查业务量各为1320人次和480人次 且不开展磁共振检查业务时 放射科利润最大 达55200元 2 该对偶规划的最优解为Y 0 160 0 20 即对应于原问题资源约束的影子价格 X线y1 0 xs1 x4 168CT检查y2 160 xs2 x5 0磁共振机y3 0 xs3 x6 120放射科服务量y4 20 xs4 x7 0 61 一 对偶单纯形法的基本思想设有标准型的线性规划模型MaxZ CX AX b X 0 上一章讨论的单纯形法基本思想是从某一基本可行解出发 B 1b 0 在初始单纯形表中 检验数C CBB 1A 0不一定成立 在保持B 1b 0成立的条件下 经过逐步换基迭代 使检验数C CBB 1A 0成立 从而得到最优解或判断无最优解 如果求解线性规划时 是否可以这样来进行 某个初始基本解使得检验数C CBB 1A 0一定成立 B 1b 0不成立 我们能否对约束等式和目标函数进行适当的行初等变换使条件C CBB 1A 0始终成立 直至B 1b 0成立 从而求得最优解或判断无最优解 这就是对偶单纯形法的基本思想 对偶单纯形法的基本思想 求解一般的线性规划问题时 由满足C CBB 1A 0的对偶可行解出发 逐次换基迭代 但始终保持对偶可行性成立 也即C CBB 1A 0成立 直至B 1b 0成立 从而求得最优解或判断无最优解 第三节对偶单纯形法 62 1 将线性规划问题化为标准型 建立初始对偶单纯形表 检查b列的数字 若都有非负数 检验数均为非正 则已得到最优解 停止计算 若b列的数字中至少有一个负分量 且所有检验数保持非正 那么转入下一步 2 确定出基变量 取b列中最负的值对应的变量为出基变量 min bi 0 bl 该行称为主元行 3 确定入基变量 在单纯形表中检查主元行的各系数 若所有alj 0 则原问题无可行解 停止计算 否则 若有alj 0则选 min j alj alj 0 k alk 那么 在换出变量那一行 用检验数除以同列具有负值的系数 取最小商数对应的变量为换入变量 相应列为主元列 如果换出变量那一行无负值的系数 则原问题无可行解 二 对偶单纯形法求解线性规划问题的一般步骤和过程 63 4 求出最优解或判断问题无解 当出基变量与入基变量选定后 则主元alk 也就确定 以alk 为转轴元 按原单纯形法在表中进行迭代运算 即作矩阵行变换 使其主元位置元素变为1 该列其他元素变为0 转1 重复计算 直至求出最优解或判断问题无解 如果得到的基本解的分量皆非负则该基本解为最优解 也就是说 对偶单纯形法在迭代过程中始终保持对偶解的可行性 即检验数非正 使原规划的基本解由不可行逐步变为可行 当同时得到对偶规划与原规划的可行解时 便得到原规划的最优解 三 对偶单纯形法求解线性规划问题的一般步骤和过程 64 三单纯形法与对偶单纯形法计算步骤的对比 65 用对偶单纯形法求解下列线性规划问题MinW 1600 x1 2500 x2 400 x3s t 2x1 5x2 x3 42x1 2 5x2 3x1 x2 x3 0 令Z W 将原问题化为标准形式MaxZ 1600 x1 2500 x2 400 x3s t 2x1 5x2 x3 x4 42x1 2 5x2 x5 3x1 x2 x3 x4 x5 0 四 表解形式对偶单纯形法求解实例 初始可行基 大M法 66 将约束条件等式的两边都乘以 1 得到MaxZ 1600 x1 2500 x2 400 x3s t x1 5x2 x3 x4 4 2x1 2 5x2 x5 3x1 x2 x3 x4 x5 0 四 表解形式对偶单纯形法求解实例 XB Xj 对偶问题的初始可行基 建立此问题的初始单纯形表如下 800 500 400 67 XB Xj 400 200 200 400 68 XB Xj 原问题的最优解为 1 0 4 0 0 0 最优值为2600 对偶问题的最优解为 200 600 0 0 200 最优值为2600 最优解 69 五 对偶单纯形法的优缺点及用途 对偶单纯形法的优点 1 初始解可以是非可行解 避免加入人工变量 简化运算 2 对变量多于约束条件时的LP问题 直接用对偶单纯形法求解 对变量少于约束条件的LP问题 可先将其转化为对偶问题 再用对偶单纯形法运算求解 可减少迭代次数 简化计算 3 在灵敏度分析中 有时需要用对偶单纯形法处理简化 对偶单纯形法缺点 在初始单纯形表中对偶问题是基可行解 这点对多数线性规划问题很难做到 70 习题 求解线性规划问题 并指出其对偶问题的最优解和对偶松弛向量 课后P80页第4题 1 对偶单纯形法 71 对偶单纯形法 72 1 4 3 8 5 73 Y 8 5 1 5 Ys 0 0 9 5 X 11 5 2 5 0 0 0 Z 28 5 74 作业题 P80页 阅读P75页第五节的应用举例 习题二第4题 75 习题二第2题 P68页 解答 3111 10110 12 1 B 1 B 1 1 1 201 21 20 1 21 2 B 1P3 1 1 201 21 20 1 21 2 11 2 3 2 10155 已知线性规划问题用单纯形法计算时得到的初始单纯型表及最终单纯型表如表3 18 请将表中空白处数字填上 76 0 1 0 0 10 15 1 1 2 0 0 3 2 0 3 2 0 1 5 3 2 1 2 77 灵敏度分析的目的在于 当求解L P 问题 且已获最优解之后 再假定原问题中某参数如bi或cj或aij发生变化 或增加一个变量 或增加一个约束条件后 于是得到一个新的L P 问题 这样一个新的L P 问题对原L P 问题的最优解和最优值产生什么样的影响 希望从原来的最终单纯形表出发 经少量运算而获得新问题的最终 优 单纯形表 或确定参数的变化范围 使原L P 问题的最优解或最优基变量不变 既然参数发生变化 或增加一个变量 或增加一个约束条件后 当然可以重新从头求解 灵敏度分析 第四节线性规划的灵敏度分析 78 79 其中C CBB 1A 0 B 1b 0从上表可以看出 1 价值系数Cj发生变化可能引起C CBB 1A的改变 2 资源常数bi发生变化可能引起B 1b的改变 3 技术系数aij发生变化可能引起C CBB 1A和B 1b的改变 4 价值系数Cj 资源常数bi 技术系数aij发生变化都可能导致最优值CBB 1b的改变 80 第四节灵敏度分析 关于灵敏度分析 我们讨论如下五种情况 1 目标函数系数cj的灵敏度分析 2 约束条件的常数项bi的灵敏度分析 3 分析参数aij的变化 4 增加新变量xij的灵敏度分析 5 添加一个新的约束条件的灵敏度分析 81 一 目标函数中价值系数Cj发生变化的分析 1 若cj不是基变量的系数 这种情形最为容易 由检验数的计算公式 由 j cj CBB 1Pj知 若cj变为cj cj 则 j变为cj cj CBB 1Pj 若cj cj CBB 1Pj 0 1 j n cj j那么原最优解不变 否则须从原最终单纯形表出发继续迭代 至新的 j 0 82 2 若cj是基变量Xj的系数 这种情形较为复杂 因cj CB 设cj为CB的第s个分量 故当cj变为cj cj时 CB将变为CB CB cj变化后最终单纯形表中检验数那一行将变为 C CB CB B 1A C CBB 1A CBB 1A C CBB 1A 0 0 cj 0 0 B 1A C CBB 1A cj as1 as2 asn cj变化前最终单纯形表中的第S行 即新的检验数行等于原来检验数行减去 cj乘原来最终单纯形表的第S行 Xj的检验数除外 应全为0 以下举例说明 第S个 83 例9 某制药公司在计划期内要安排生产A1 A2 A3三种药品 已知生产一盒药品所需消耗的D E两种原材料的数量 单位 kg 以及单位药品的利润如表3 8所示 表3 8药品生产的资源消耗 资源限制及利润 问应如何安排生产使制药公司获利最多 产品 原料 84 1 若第3种药品的单位利润c3发生变化 那么 c3在什么范围内变化时 原问题的最优解不变 2 基本变量x1的系数c1 5有改变量 那么 c1在什么范围内变化时 原问题的最优解不变 表3 9初始单纯形表和最终单纯形表 85 1 非基变量x3的系数c3 6改变仅会影响到该列检验数 3 2 则 c3 3 2C3 8 2 C CBB 1A CBB 1A j CBPj 0即 2 2 c1 0 3 c1 0得 1 c1 3原问题的最优值变为z 84 4 c1 解 86 XB Xj 表3 10基本变量x1的系数c1 5改变 c1对最优解影响 87 1 若非基变量c4有改变量 c4 那么 c4在何范围内变化时 问题的最优解不变 2 若基变量c2有改变量 c2 那么 c2在何范围内变化时 问题的最优解不变 最优值为多少 88 1 非基变量c4 0的改变仅会影响到检验数C4 1 则 c4 C4 12 C CBB 1A CBB 1A Cj CBPj 即 1 c2 0 3 2 c2 0得 3 2 c2 1z 215 10 c2 解 89 二 右端项b发生变化 b 第i个分量 灵敏度分析 第四节灵敏度分析 假定bi发生变化 设分量bi获得增量 bi而变为bi bi 则b将获得增量 b 根据单纯形法矩阵表示式的讨论 最优解的基本变量xB B 1b B 1b将获得增量B 1 b而变为B 1b B 1 b 即基本变量保持不变 只有最优值的变化 否则 需要利用对偶单纯形法继续计算 只要B 1b B 1 b 0 则在原最终单纯形表中只要用B 1b B 1 b代替B 1b这一列 就可获得新最终单纯形表 此处 0 0 bi0 0 90 例10 以例9为例 1 若b1 12有改变 为使最优基本变量x1 x2地位不变 求 b1的变化范围 2 若b1的变化超出了所允许的范围 如 b1 9 试求取新的最优解 由表3 9最后二列 因最终单纯形表之最后二列x4 x5构成单位矩阵 知B 1 而 b 易见由B 1b B 1 b 知 2 b1 8 当 b1在此范围内变化时 只须修改表3 9的B 1b列即可获得新问题的最终单纯形表 2 1 11 b10 48 00 4 2 b18 b1 2 1 11 b10 91 XB Xj 若b1的变化超出了所允许的范围 如 b1 9 最优解的基本变量发生变化 此时检验数不变 需用对偶单纯形法求出新的最优解 表3 11b1改变量 b1 9时对最优解影响 2 2 0 0 4 Z 100 5 92 三 技术系数aij的变化 1 非基变量的系数列向量Pj的改变假设改变量为 Pj 即Pj Pj PjPj的改变将影响到检验数所谓改变 即Cj cj CBB 1Pj cj CBB 1 Pj Pj Cj CBB 1 Pj最优基本解不变 应有Cj CBB 1 Pj 0或Cj CBB 1 Pj2 基变量的系数列向量Pj的改变这种改变将影响到B B 1的改变 影响到单纯型表的每一列 一般需重新迭代求解 93 增加一个变量增加变量xn 1则有相应的系数列向量pn 1和目标函数系数cn 1 那么计算出B 1pn 1 检验数 n 1 cn 1 CBB 1pn 1填入最优单纯形表 若 n 1 0则最优解不变 否则 继续用单纯形法求解 四 决策变量增减的灵敏度分析 94 增加一个约束增加约束一个之后 应把最优解带入新的约束 若满足则最优解不变 否则填入最优单纯形表作为新的一行 引入一个新的非负变量 原约束若是小于等于形式可引入非负松弛变量 否则引入非负人工变量 并通过矩阵行变换把对应基变量的元素变为0 进一步用单纯形法或对偶单纯形法求解 五 约束条件增减的灵敏度分析 95 XB Xj 0 0 2 2 3 Z 84 Z 80 0 0 10 3 0 11 3 0 2 3 2 3 96 灵敏度分析的步骤 综上所述 灵敏度分析的步骤可归纳如下 1 将某些变化后的参数代入最优单纯形表 2 检查修正后的最优单纯形表 主要考察最优解的两点变化 1 解的可行性变化 检查表中基变量值B 1b是否依旧非负 2 解的最优性变化 检查表中所有检验数是否非负 极大化 3 将修正后的最优表作为初始单纯形表 重新使用单纯形法 或对偶单纯形法 迭代求解 97 习题二第5题 给出线性规划问题及其最优单纯型表如下 maxz 6x1 2x2 12x3s t 4x1 x2 3x3 242x1 6x2 3x3 30 xj 0 j 1 2 3 1 试求出最优解不变的c3变化范围 2 试求出最优基变量不变的b2变化范围 3 在原线性规划的约束条件上 增加下面的约束条件 x1 2x2 2x3 12 其最优解是否变化 如变化 试求出最优解 98 2 B 1 而 b 易见由B 1b B 1 b 知6 b2 0 当 b2 6 b2 24时 只须修改表的B 1b列即可获得新问题的最终单纯形表 1 30 11 0 b2 86 86 b2 1 若是最优解不变 则必须满足下式 6 4c3 3 02 c3 3 0 c3 3 0 1 2 3 c3 9 2c3 6c3 0 c3 6 0 b2 解 99 3 在原线性规划的约束条件上 增加下面的约束条件x1 2x2 2x3 12 原最终单纯形表新增一行和一列 此时原最终单纯形表中的x3和x5的系数不再是单位向量了 所以继续进行行变换 保持原基变量不变 在行变换后得到的新单纯形表中 检验数均小于等于零 但右端项出现负值 所以可用对偶单纯形法继续运算 最后得最优解X 12 5 0 24 5 0 54 5 0 T 最优值Z 72 100 作业题 课后习题二第5题 P81页 课后习题二第6题 P81页 101 习题 对上述最大化的线性规划问题 已知其初始和最优单纯形表 1 请填写最优表中空白处的数字 2 写出原线性规划问题 3 写出其对偶规划及其最优解 4 当b变为b b b 1 1 0 T 问 在何范围内变化 原最优性不变 5 目标函数x2的系数c2从 1变为 2 原最优性是否改变 求出c2 2时最优解的最优目标函数值 102 1 请填写最优表中空白处的数字 0 1 2 0 0 1 0 0 0 0 1 0 0 3 2 1 3 2 1 2 3 2 1 4 5 30 5 2 c2 0 b1 60 b2 10 b3 20 103 1 解 将y 1 4 5 y 2 3 5代入对偶问题的约束条件 得 2 3 4 为严格不等式 所以ys2 0 ys3 0 ys4 0 由互补松弛性得x 2ys2 x 3ys3 x 4ys4 0所以x 2 x 3 x 4 0 又因为 y 1 0 y 2 0 所以x s1 x s2 0 即原问题的两个约束条件为等式约束 故得方程组 x 1 3x 5 42x 1 x 5 3解之得x 1 x 5 1 而W Z 5 故原问题的最优解为 X 1