运筹学 第2版 教学课件 作者 孔造杰OR1-Ch3-LP对偶.ppt

《运筹学 第2版 教学课件 作者 孔造杰OR1-Ch3-LP对偶.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性规划对偶理论§3-1对偶问题的提出§3-2写对偶问题§3-3对偶问题的性质§3-4对偶单纯形方法§3-1对偶问题的提出从经济意义上提出对偶问题仍以第一章的例1-1为例，假若企业的决策者除了生产产品甲、乙之外，还有其它可选方案来利用其设备资源。例如，承接外加工或租赁设备，作为决策者就要考虑设备台时定价的问题，即在何种台时价格的前提下接受外加工或租赁设备以取代生产甲乙两种产品。若以分别表示设备A、B、C每台时的价格（加工费或租金），这时就要与自己生产产品甲乙作一比较，因为每生产1件产品甲可得2元的利润，每

2、生产1件产品乙可得利润3元，那么，如果用于生产一件产品甲的各设备台时用于外加工所得的收益不低于2元，同样，用于生产一件产品乙的各设备台时用于外加工所得的收益不低于3元，则将设备用于外加工（或租赁）；否则，就用于生产甲乙两种产品。根据以上分析和第一章例1-1的条件，我们得到关系式：2021/9/52河北工业大学管理学院孔造杰制作§3-1对偶问题的提出——从经济上提出从经济意义上提出对偶问题（续）则设备用于外加工的总收入为：设备台时价格越大，总收入就越大，我们当然希望总收入越大越好。但是，价格问题不是一个企业能完全

3、确定的，它是一种社会价格。因此，我们希望知道最低的总收入是多少，或者说，最低的设备台时价格是多少时就和自己生产产品甲乙所得的收入是一样的。因此，这个问题的数学模型为：很显然，当时，决策者认为设备用于外加工和用于生产产品甲乙这两种方案的效果是一样的。2021/9/53河北工业大学管理学院孔造杰制作§3-1对偶问题的提出——从数学模型上提出从数学模型上提出对偶问题在上述矩阵表示的单纯形表中，若问题达到了最优解，则其检验数行均小于等于零，即：对其讨论如下：用，称之为单纯形乘子，对于最优解而言，显然有。对于包含基变量在

4、内的检验数，在最优解的情况下可以表示为：因为在约束的条件下无上界，所以它只存在最小值，它与常向量b的乘积也只存在最小值。记作为：2021/9/54河北工业大学管理学院孔造杰制作§3-1对偶问题的提出——从数学模型上提出定义新的LP模型为原模型的对偶模型且注意到：原模型在约束条件下的最优解为：所以有：对偶模型2021/9/55河北工业大学管理学院孔造杰制作§3-2写对偶问题将上一节中原问题与对偶问题的矩阵式展开：对偶式2021/9/56河北工业大学管理学院孔造杰制作§3-2写对偶问题——表格形式为便于叙述和记忆对

5、偶问题，通常规定一个标准形式，一般规定原规划为“≤”约束，对偶规划为“≥”约束，变量均≥0的对偶问题为标准形式。把它们之间的关系用表格形式表示出来：2021/9/57河北工业大学管理学院孔造杰制作§3-2写对偶问题——非标准型的处理在实际问题中常常会有非标准形式，如有等式约束，或某变量无非负约束等等。如果某个约束为等式约束，可以把它变为两个不等式约束如下：等价变换写对偶2021/9/58河北工业大学管理学院孔造杰制作§3-2写对偶问题——对偶关系表注意：助记法：标准型应是≤，应是≥，这是对于对偶变量≥0而言；若

6、对偶变量≤0，则符号方向相反；等式对应无约束。2021/9/59河北工业大学管理学院孔造杰制作§3-2写对偶问题——例题例3-1：写出下面线性规划问题的对偶问题。解：根据对偶问题变换规则，其对偶问题如下：2021/9/510河北工业大学管理学院孔造杰制作§3-3对偶问题的性质对称性：对偶问题的对偶是原问题。[证明]：设原问题是：对偶问题是：对偶再对偶此即原模型[证闭]2021/9/511河北工业大学管理学院孔造杰制作§3-3对偶问题的性质——弱对偶性弱对偶性若是原问题的可行解，是对偶问题的可行解，则存在[证明]

7、：设原规划问题是若又是其对偶问题的可行解，用左乘①式两侧得：∵是原问题的可行解，∴满足约束条件用右乘②式两侧得：∴得到结论：[命题得证]2021/9/512河北工业大学管理学院孔造杰制作§3-3对偶问题的性质——等值最优性等值最优性设是原问题的可行解，是对偶问题的可行解，当时，分别是原问题和对偶问题的最优解。[证明]：∵据性质2，有（对偶问题的任一可行解不小于原问题的任一个可行解）又∵由的任意性可知，是对偶问题可行解中最小的一个，故是最优解。同理，∵由的任意性可知，是原问题可行解中最大的一个，故是最优解。[证毕

8、]2021/9/513河北工业大学管理学院孔造杰制作§3-3对偶问题的性质——对偶定理对偶定理若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。[证明]：设是原问题的最优解，则必有即这时的是对偶问题的可行解，所以得到对偶问题的目标值∵是原问题的最优解，它使目标函数取值为由定理3的等值最优性可知，是对偶问题的最优解。[命题得证]2021/9/514河北工业大学管理学院孔造杰制作