第二章 对偶理论和灵敏度

1、1 第二章 对偶理论和灵敏度分析 2 第一节 单纯形法的矩阵描述 设线性规划的标准型为： max . 0 zCX AX st X b 5210 3 22 1 2max 543 542 41 5421 ,jx xxx xxx xx s.t xxxxz j 1 B XB b 1 BNN ZC B bX 1 NNB CC B N 1 B CC B A 4 1 1 1 min0 i j i j i B b B P B P 第二节 改进单纯形法 w改进单纯形法的出发点改进单纯形法的出发点：由于单纯形法的迭代 过程中基矩阵的逆矩阵求出后，单纯形表上的 其它行和列的数字也随着可确定，不必要计算 很多与下一步

2、迭代无关的数字，提高计算效率， 减少计算机求解所需的存储单元。 5 改进单纯形法的计算步骤 6 7 例1 用改进单纯形法求解 12345 123 14 25 12345 max23000 28 416 . 412 ,0 zxxxxx xxx xx st xx x x x x x 1 B XB b 1 BNN ZC B bX 1 NNB CC B N 1 B CC B A 1 1 1 min0 i j i j i B b B P B P 8 习题2.1 9 123 123 13 123 max623 222 .44 ,0 zxxx xxx st xx x x x 123 1234 135 123

3、45 max623 222 .44 ,0 zxxx xxxx st xxx x x x x x 第三节第三节 对偶问题的提出对偶问题的提出 10 例例1：某工厂在计划期内安排生产：某工厂在计划期内安排生产 、两种产品两种产品，已知生产单位已知生产单位 产品所需的设备台时、产品所需的设备台时、A、B两种两种 原材料的消耗如下表所示：原材料的消耗如下表所示： 该工厂每生产一件产品该工厂每生产一件产品可获利可获利2 元，每元，每生产一件产品生产一件产品可获利可获利3元，元， 问应如何安排计划使该工厂获利问应如何安排计划使该工厂获利 最多？最多？ 资源限制资源限制 设设 备备128 台时台时 原料原料

4、 A4016 千克千克 原料原料 B0412 千克千克 单位产品获利单位产品获利2 元元3 元元 现在从另一角度来 讨论这个问题。假 设该工厂的决策者 决定不生产产品， 而将所有资源出租 或外售。这时工厂 的决策者就要考虑 给每种资源如何定 价的问题。 原问题与对偶问题的关系 非对称形式线性规划问题的处理 w若原问题的第i个约束条件是等式约束， 则对偶问题中相应于它的变量无非负要 求；反之，若原问题的第i个变量无非负 要求，则对偶问题中相应于它的约束条 件是等式约束。 12 13 12 12 12 12 max23 215 .4320 ,0 zxx xx stxx x x 0 2034 152

5、 . 32max 1 21 21 21 x xx xx ts xxz 0, 2034 152 . 32max 21 21 21 21 xx xx xx ts xxz 0, 0 2034 152 . 32max 21 21 21 21 xx xx xx ts xxz 14 例 求下述线性规划问题的对偶问题 无约束,0,0, 2099912 85376 53 . 432max 4321 4321 4321 4321 4321 xxxx xxxx xxxx xxxx ts xxxxz 例3 试求下述线性规划问题的对偶问题 1234 1234 134 234 1234 min235 35 224 .

6、6 0;,0; zxxxx xxxx xxx st xxx xx xx 无约束 2.3 17 0, 564 373 2532 . 422min 321 321 321 321 321 xxx xxx xxx xxx ts xxxz 原问题与对偶问题对应关系的一般形式 0 . max X bAX ts CXz 0, . min 21 2211 22222112 11221111 2211 m nmmnnn mm mm mm yyy cyayaya cyayaya cyayaya ts ybybybw 0 . min Y CYA ts Ybw 0, . max 21 2211 22222121 1

7、1212111 2211 n mnmnmm nn nn nn xxx bxaxaxa bxaxaxa bxaxaxa ts xcxcxcz 4.2 对偶问题的基本性质 1.对称性对称性对偶问题的对偶是原问题对偶问题的对偶是原问题 2.弱对偶性弱对偶性若若是原问题的可行是原问题的可行 解，解，是对偶问题的可行解，则存是对偶问题的可行解，则存 在在 X Y bYXC 3.无界性无界性若原问题（对偶问题）为若原问题（对偶问题）为 无界解，则其对偶问题（原问题）无界解，则其对偶问题（原问题） 无可行解。无可行解。 此问题的性质不存在逆。此问题的性质不存在逆。 0, 1 1 . min 21 21 21

8、 21 xx xx xx ts xxw 0, 1 1 . max 21 21 21 21 yy yy yy ts yyz 4.可行解是最优解时的性质可行解是最优解时的性质 设设是原问题的可行解，是原问题的可行解，是对偶问是对偶问 题的可行解，当题的可行解，当时，时，是最是最 优解。优解。 X Y bYXC YX , 5.对偶定理对偶定理若原问题有最优解，若原问题有最优解， 那么对偶问题也有最优解，且目标那么对偶问题也有最优解，且目标 函数值相等。函数值相等。 例4 已知线性规划问题 12 123 123 123 max 2 21 ,0 zxx xxx xxx x xx 试用对偶理论证明上述线性

9、规划问题无 最优解。 6.互补松弛定理互补松弛定理若若分别是原问题分别是原问题 和对偶问题的可行解，那么和对偶问题的可行解，那么和和 ，当且仅当，当且仅当为最优解。为最优解。 YX , 0 S XY 0Y X S YX , max ,0 S S zCX AXXb X X min ,0 S S wYb YA YC Y Y 原问题与对偶问题对应关系的一般形式 0 . max X bAX ts CXz 0, . min 21 2211 22222112 11221111 2211 m nmmnnn mm mm mm yyy cyayaya cyayaya cyayaya ts ybybybw 0 .

10、 min Y CYA ts Ybw 0, . max 21 2211 22222121 11212111 2211 n mnmnmm nn nn nn xxx bxaxaxa bxaxaxa bxaxaxa ts xcxcxcz 例5 已知线性规划问题 12345 12345 12345 min23523 234 233 0,1,2,5 j wxxxxx xxxxx xxxxx xj 已知其对偶问题的最优解为 * 12 4/5,3/5,5yyz 试用对偶理论找出原问题的最优解。 7.原问题单纯形表的检验数行对应原问题单纯形表的检验数行对应 其对偶问题的一个基解，对应关系其对偶问题的一个基解，对

11、应关系 见下表。见下表。 27 max ,0 S S zCX AXXb X X min ,0 S S wYb YA YC Y Y 补充例题 123 123 123 123 max61413 1 224 2 2460 ,0 zxxx xxx xxx x x x 该线性规划问题的 最终单纯形表如下， 求对偶问题的最优 解。 第五节第五节 对偶问题对偶问题 的经济解释的经济解释 对偶问题的解的经济意义：在其它条件不对偶问题的解的经济意义：在其它条件不 变的情况下，单位资源变化所引起的目标函变的情况下，单位资源变化所引起的目标函 数的最优值的变化。数的最优值的变化。 对偶问题的经济解释对偶问题的经济解

12、释 某工厂在计划期内要 安排、两种产品 的生产，已知生产单 位产品所需的设备台 时及A、B两种原材 料的消耗以及资源的 限制，如下表： 问题：如何安排生产 才能使工厂获利最多？ 30 资源限制资源限制 设设 备备128 台时台时 原料原料 A4016 千克千克 原料原料 B0412 千克千克 单位产品获利单位产品获利2 元元3 元元 0, 124 164 82 . 32max 21 2 1 21 21 xx x x xx ts xxz 0, 342 24 . 12168min 321 31 21 321 yyy yy yy ts yyyw 31 3 4 8 4 0 x2 x1 B(4.25,1

13、.875)Z=14.125 A(4,2)Z=14 C(4,2.5)Z=15.5 C AB 0 124 164 82 32max 21 2 1 21 21 ,xx x x xx s.t xxz 的值代表对第的值代表对第种资源的估价。种资源的估价。 这种估价是针对具体工厂的具体产品而存这种估价是针对具体工厂的具体产品而存 在的一种特殊价格，称它为在的一种特殊价格，称它为“影子价影子价 格格”(ShadowpriceorDualprice)。 i yi 影子价格的性质 u影子价格越小，说明这种资源相对不紧缺 u影子价格越大，说明这种资源越是相对紧缺 u如果最优生产计划下某种资源有剩余，这种资 源的影

14、子价格一定等于0 34 影子价格对市场有调节作用。在完全影子价格对市场有调节作用。在完全 市场经济的条件下，当某种资源的市场市场经济的条件下，当某种资源的市场 价格低于企业影子价格时，企业应买进价格低于企业影子价格时，企业应买进 该资源用于扩大生产；而当某种资源的该资源用于扩大生产；而当某种资源的 市场价格高于企业影子价格时，则企业市场价格高于企业影子价格时，则企业 的决策者应把已有资源卖掉。的决策者应把已有资源卖掉。 第六节 对偶单纯形法 对偶单纯形法的基本思想：保持对偶问题 的解是可行解，原问题在非可行解的基础上， 通过逐步迭代达到基可行解，最终得到最优解 。 在单纯形表中进行迭代时，在

15、b 列中得到 的是原问题的可行解，而在检验数行得到的是 对偶问题的基解。通过逐步迭代，当在检验数 行得到对偶问题的解也是基可行解时，对偶问 题得到最优解。 例题 12 12 12 12 max 22 .1 ,0 zxx xx stxx x x 123 124 12 22 .1 ,0 xxx stxxx x x 例6 用对偶单纯形法求解 123 123 123 123 min234 23 234 ,0 wxxx xxx xxx x xx 对偶单纯形法的计算步骤 目标函数求极大值目标函数求极大值 w初始单纯形表：检验数非初始单纯形表：检验数非 正，常数项若非负，已是正，常数项若非负，已是 最优解，

16、若常数项有负分最优解，若常数项有负分 量，转入下一步。量，转入下一步。 w换出变量：值为负的变量换出变量：值为负的变量 w换入变量：检查出基变量换入变量：检查出基变量 所在行的系数，若都为非所在行的系数，若都为非 负，则无可行解。若存在负，则无可行解。若存在 系数小于零，计算检验数系数小于零，计算检验数 与系数的比值，取最小值与系数的比值，取最小值 对应的系数为主元素。对应的系数为主元素。 w迭代，重复上述步骤。迭代，重复上述步骤。 目标函数求极小值目标函数求极小值 w初始单纯形表：检验数初始单纯形表：检验数非非 负负，常数项若非负，已是，常数项若非负，已是 最优解，若常数项有负分最优解，若常

17、数项有负分 量，转入下一步。量，转入下一步。 w换出变量：值为负的变量换出变量：值为负的变量 w换入变量：检查出基变量换入变量：检查出基变量 所在行的系数，若都为非所在行的系数，若都为非 负，则无可行解。若存在负，则无可行解。若存在 系数小于零，计算检验数系数小于零，计算检验数 与系数的比值，取与系数的比值，取绝对值绝对值 的最小值对应的系数为主的最小值对应的系数为主 元素。元素。 w迭代，重复上述步骤。迭代，重复上述步骤。 对偶单纯形法的优点与局限 优点优点 w初始解可以是非可行解，当检验数都为负数时，就 可以进行基的变换，这时不需要加入人工变量，因 此可以简化计算。 w在灵敏度分析及求解整

18、数规划的割平面法中，有时 需要对偶单纯形法，这样可使问题的处理简化。 局限：局限： 对大多数线性规划问题，很难找到一个初始可 行基，因而这种方法在求解线性规划问题时很少单 独应用。 第七节 灵敏度分析 w当线性规划的系数有一个或几个发生变化时， 已求得的线性规划问题最优解会有什么变化； w或者这些系数在什么范围内变化时，线性规划 问题的最优解或最优基保持不变。 42 43 原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤 可行解可行解 可行解可行解表中的解仍为最优解表中的解仍为最优解 可行解可行解 非可行解非可行解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解 非可行

19、解非可行解 可行解可行解用对偶单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解 非可行解非可行解 非可行解非可行解引进人工变量，编制新的单纯形表，求最优解引进人工变量，编制新的单纯形表，求最优解 7.1 资源数量变化的分析 44 第一章例1中，求使最优基保持不变的第二个 约束条件b2的变化范围 b2。 。 资资 源源 限限 制制 设设 备备 128台台 时时 原原 料料A 4016千千 克克 原原 料料B0412千千 克克 单单 位位 产产 品品 获获 利利 2元元 3元元 0, 124 164 82 . 32max 21 2 1 21 21 xx x x xx ts xxz 45 例7

20、 46 从例1的最优单纯形表，每设备台时的影子价 格为1.5元。若该厂又从其它处抽调4台时用 于生产产品和 。求这时该厂生产产品 和的最优方案。 资资 源源 限限 制制 设设 备备 128台台 时时 原原 料料A 4016千千 克克 原原 料料B0412千千 克克 单单 位位 产产 品品 获获 利利 2元元 3元元 0, 124 164 82 . 32max 21 2 1 21 21 xx x x xx ts xxz 47 -4 4 4 48 -4 4 4 7.2 目标函数中价值系数的变化分析 w非基变量的价值系数变化分析 w基变量的价值系数变化分析 49 例8 以例1的最优表为例。设基变量

21、的系数变化 ，在原最优解不变的条件下，确定 的变 化范围。 50 2 x 2 c 2 c 3+ 2 c 3+ 2 c 7.3 技术系数的变化 例例9分析在原计划中是否应该安排一种新产品。以例1 为例，设该厂除了生产产品1和2 外，现有一种新产品 3，每件需消耗原材料A,B各为6kg, 3kg，使用设备2台 时，每件可获利5元。问该厂是否应该生产该产品和 生产多少？ 51 52 例 10 分析原计划生产产品的工艺结构发生变化 。仍以例1为例，若原计划生产产品1的工艺结 构有了改进，这时有关它的技术系数向量变为 ，每件利润为4元，分析对原最优 计划有什么影响？ 53 T P)2 , 5 , 2(

22、1 54 例 11 假设例10的新产品1的技术系数向量为 ，而每件获利仍为4元。试问该厂应如何安排最 优生产方案？ 55 T P)2 , 5 , 4( 1 56 57 58 补充：增加约束条件分析 u一般将原最优解代入新增约束，若满足，则最 优解保持不变。 u否则，将新约束条件加入到原单纯形表中，调 整求解。 59 例题 60 0, 4 2 92 . 4max 321 321 321 321 321 xxx xxx xxx xxx ts xxxz 最优单纯形表如下： 增加新约束： 1763 321 xxx 61 62 资源数量的变化分析 63 1 1 1 1 1 (bb) (bb)0 B(bb) (bb) B B B B B XB CC B A XB XB XB 会发生变化 不变 若，则最优基保持不变， 依然是 。最优解变成了。 若中有负的分量，则最优基 发生变化，需要继续用对偶单纯形法迭代， 求出新的最优解。 价值系数的变化分析 64 1 1 1 1 1 b 0 b B B B B B XB CCB A CCB A XB CCB A 不变 会发生变化 若，