《华南理工大学工商管理学院运筹学课件》由会员分享，可在线阅读，更多相关《华南理工大学工商管理学院运筹学课件（195页珍藏版）》请在金锄头文库上搜索。
1、对偶模型对偶性质对偶单纯形法作业第三章线性规划的对偶理论对偶模型对偶性质对偶单纯形法作业 对偶现象对偶现象对偶现象是一种广泛存在的现象。自然界 禽之双翅、人之双手、车之双轮、河之双岸等； 生死、昼夜、明暗、冷热、日月、上下、雄雌、离合。思想领域 周易：“乾道成男，坤道成女；乾知大始，坤作成物”； 老子：“有无相生，难易相成；长短相形，高下相倾”； 诗式：“夫对者，. 盖天地自然之数”； 哲学：对立统一 等。语言学领域 中国的对联对偶模型对偶性质对偶单纯形法作业 对偶现象对偶现象对偶现象是一种广泛存在的现象。自然界 禽之双翅、人之双手、车之双轮、河之双岸等； 生死、昼夜、明暗、冷热、日月、上下、
2、雄雌、离合。思想领域 周易：“乾道成男，坤道成女；乾知大始，坤作成物”； 老子：“有无相生，难易相成；长短相形，高下相倾”； 诗式：“夫对者，. 盖天地自然之数”； 哲学：对立统一 等。语言学领域 中国的对联对偶模型对偶性质对偶单纯形法作业 对偶现象对偶现象对偶现象是一种广泛存在的现象。自然界 禽之双翅、人之双手、车之双轮、河之双岸等； 生死、昼夜、明暗、冷热、日月、上下、雄雌、离合。思想领域 周易：“乾道成男，坤道成女；乾知大始，坤作成物”； 老子：“有无相生，难易相成；长短相形，高下相倾”； 诗式：“夫对者，. 盖天地自然之数”； 哲学：对立统一 等。语言学领域 中国的对联对偶模型对偶性质
3、对偶单纯形法作业 对偶现象对偶现象对偶现象是一种广泛存在的现象。自然界 禽之双翅、人之双手、车之双轮、河之双岸等； 生死、昼夜、明暗、冷热、日月、上下、雄雌、离合。思想领域 周易：“乾道成男，坤道成女；乾知大始，坤作成物”； 老子：“有无相生，难易相成；长短相形，高下相倾”； 诗式：“夫对者，. 盖天地自然之数”； 哲学：对立统一 等。语言学领域 中国的对联对偶模型对偶性质对偶单纯形法作业 对偶现象对偶现象对偶现象是一种广泛存在的现象。自然界 禽之双翅、人之双手、车之双轮、河之双岸等； 生死、昼夜、明暗、冷热、日月、上下、雄雌、离合。思想领域 周易：“乾道成男，坤道成女；乾知大始，坤作成物”；
4、 老子：“有无相生，难易相成；长短相形，高下相倾”； 诗式：“夫对者，. 盖天地自然之数”； 哲学：对立统一 等。语言学领域 中国的对联对偶模型对偶性质对偶单纯形法作业 对偶现象对偶现象在数学领域中，对偶现象也广泛存在。例如：在周长一定的四边形中，以正方形面积为最大；在面积一定的四边形中，以正方形的周长为最小。当两正数和一定时, 此二正数相等时其积为最大；当两正数积一定时, 此二正数相等时其和为最小。这些实际上都是同一个问题的两个方面。在数学领域，这种现象 非常常见。对偶模型对偶性质对偶单纯形法作业 对偶现象对偶现象在数学领域中，对偶现象也广泛存在。例如：在周长一定的四边形中，以正方形面积为最
5、大；在面积一定的四边形中，以正方形的周长为最小。当两正数和一定时, 此二正数相等时其积为最大；当两正数积一定时, 此二正数相等时其和为最小。这些实际上都是同一个问题的两个方面。在数学领域，这种现象 非常常见。对偶模型对偶性质对偶单纯形法作业 对偶现象对偶现象在数学领域中，对偶现象也广泛存在。例如：在周长一定的四边形中，以正方形面积为最大；在面积一定的四边形中，以正方形的周长为最小。当两正数和一定时, 此二正数相等时其积为最大；当两正数积一定时, 此二正数相等时其和为最小。这些实际上都是同一个问题的两个方面。在数学领域，这种现象 非常常见。对偶模型对偶性质对偶单纯形法作业 对偶现象在线性规划中，
6、同样存在对偶现象：每一个线性规划问题都有一个与其相应的线性 规划，这两个问题互为对偶问题。 在任何时候，用单纯形法求线性规划问题的解， 都可同时得到两个线性规划问题的解。对偶模型对偶性质对偶单纯形法作业引例对偶模型3.1 对偶线性规划模型对偶模型对偶性质对偶单纯形法作业引例对偶模型3.1.1 引例对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例.第一章例 1-1 的数学模型为：. . . . . . .maxZ = 5x1+ 4x2+ 2x3s.t.8x1+ 4x2+ 5x36 320 2x1+ 2x2+ x36 100x1,x2,x3 0(3-1)如果把这个 3 变量 2 约束的问题叫做
7、原问题，则其 对偶问题 是minW = 320y1+ 100y2 s.t.8y1+ 2y2 54y1+ 2y2 4 5y1+ y2 2y1 0, y2 0(3-2)其中，y1, y2叫做对偶变量。对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例.第一章例 1-1 的数学模型为：. . . . . . .maxZ = 5x1+ 4x2+ 2x3s.t.8x1+ 4x2+ 5x36 320 2x1+ 2x2+ x36 100x1,x2,x3 0(3-1)如果把这个 3 变量 2 约束的问题叫做 原问题，则其 对偶问题 是minW = 320y1+ 100y2 s.t.8y1+ 2y2 54y1+
8、 2y2 4 5y1+ y2 2y1 0, y2 0(3-2)其中，y1, y2叫做对偶变量。对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例.第一章例 1-1 的数学模型为：. . . . . . .maxZ = 5x1+ 4x2+ 2x3s.t.8x1+ 4x2+ 5x36 320 2x1+ 2x2+ x36 100x1,x2,x3 0(3-1)如果把这个 3 变量 2 约束的问题叫做 原问题，则其 对偶问题 是minW = 320y1+ 100y2 s.t.8y1+ 2y2 54y1+ 2y2 4 5y1+ y2 2y1 0, y2 0(3-2)其中，y1, y2叫做对偶变量。对偶模型
9、对偶性质对偶单纯形法作业引例对偶模型 引例.第一章例 1-1 的数学模型为：. . . . . . .maxZ = 5x1+ 4x2+ 2x3s.t.8x1+ 4x2+ 5x36 320 2x1+ 2x2+ x36 100x1,x2,x3 0(3-1)如果把这个 3 变量 2 约束的问题叫做 原问题，则其 对偶问题 是minW = 320y1+ 100y2 s.t.8y1+ 2y2 54y1+ 2y2 4 5y1+ y2 2y1 0, y2 0(3-2)其中，y1, y2叫做对偶变量。对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8
10、x1+ 4x2+ 5x36 3202x1+ 2x2+ x36 100 x1,x2,x3 0对偶问题：minW = 320y1+ 100y2 s.t.8y1+ 2y2 5 4y1+ 2y2 45y1+ y2 2 y1 0, y2 0对偶关系： 原问题的目标函数系数 (行) 向量是对偶问题约束条件 的常数 (列) 向量，原问题约 束条件的常数 (列) 向量是对 偶问题的目标函数系数 (行) 向量；对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8x1+ 4x2+ 5x36 3202x1+ 2x2+ x36 100 x1,x2,x3 0对偶
11、问题：minW = 320y1+ 100y2 s.t.8y1+ 2y2 5 4y1+ 2y2 45y1+ y2 2 y1 0, y2 0原问题与对偶问题约束条件 的不等号方向相反；对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8x1+ 4x2+ 5x36 3202x1+ 2x2+ x36 100 x1,x2,x3 0对偶问题：minW = 320y1+ 100y2 s.t.8y1+ 2y2 5 4y1+ 2y2 45y1+ y2 2 y1 0, y2 0原问题的目标函数是求最大 值，对偶问题的目标函数是 求最小值；对偶模型对偶性质对
12、偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8x1+ 4x2+ 5x36 3202x1+ 2x2+ 1x36 100 x1,x2,x3 0对偶问题：minW = 320y1+ 100y2 s.t.8y1+ 2y2 5 4y1+ 2y2 45y1+ 1y2 2 y1 0, y2 0约束条件系数矩阵互为转 置。因此，原问题的约束条 件的个数等于对偶问题变量 的个数，对偶问题约束条件 的个数等于原问题变量的个 数；对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8x1+ 4x2+ 5x36 32
13、02x1+ 2x2+ 1x36 100 x1,x2,x3 0对偶问题：minW = 320y1+ 100y2 s.t.8y1+ 2y2 5 4y1+ 2y2 45y1+ 1y2 2 y1 0, y2 0约束条件系数矩阵互为转 置。因此，原问题的约束条 件的个数等于对偶问题变量 的个数，对偶问题约束条件 的个数等于原问题变量的个 数；对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8x1+ 4x2+ 5x36 3202x1+ 2x2+ x36 100 x1,x2,x3 0对偶问题：minW = 320y1+ 100y2 s.t.8y1+
14、 2y2 5 4y1+ 2y2 45y1+ y2 2 y1 0, y2 0最后，对偶问题的对偶是原 问题。对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8x1+ 4x2+ 5x36 3202x1+ 2x2+ x36 100 x1,x2,x3 0对偶问题：minW = 320y1+ 100y2 s.t.8y1+ 2y2 5 4y1+ 2y2 45y1+ y2 2 y1 0, y2 0结合实际背景：原问题是分配两种有限资源 生产三种产品，求最大利润 的问题； 对偶问题可以理解为：将有 限资源转让出去，最少应有 多少利润才是合理的 生 产
15、单位某种产品所消耗资源 的转让收益不应低于生产所 带来的收益。对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8x1+ 4x2+ 5x36 3202x1+ 2x2+ x36 100 x1,x2,x3 0对偶问题：minW = 320y1+ 100y2 s.t.8y1+ 2y2 5 4y1+ 2y2 45y1+ y2 2 y1 0, y2 0结合实际背景： 原问题是分配两种有限资源 生产三种产品，求最大利润 的问题；对偶问题可以理解为：将有 限资源转让出去，最少应有 多少利润才是合理的 生 产单位某种产品所消耗资源 的转让收益不应低于生
16、产所 带来的收益。对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8x1+ 4x2+ 5x36 3202x1+ 2x2+ x36 100 x1,x2,x3 0对偶问题：minW = 320y1+ 100y2 s.t.8y1+ 2y2 5 4y1+ 2y2 45y1+ y2 2 y1 0, y2 0结合实际背景： 原问题是分配两种有限资源 生产三种产品，求最大利润 的问题； 对偶问题可以理解为：将有 限资源转让出去，最少应有 多少利润才是合理的 生 产单位某种产品所消耗资源 的转让收益不应低于生产所 带来的收益。对偶模型对偶性质对偶单纯形法作业引例对偶模型 引例原问题：maxZ = 5x1+ 4x2+ 2x3 s.t.8x1+ 4x2+ 5x36 3202x1+ 2x2+ x36 10
