运筹学OR1-Ch3-LP对偶课件

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

2、得的收益不低于2元，同样，用于生产一件产品乙的各设备台时用于外加工所得的收益不低于3元，则将设备用于外加工（或租赁）；否则，就用于生产甲乙两种产品。根据以上分析和第一章例1-1的条件，我们得到关系式： *Page 2 of 28 3-1 对偶问题的提出从经济上提出从经济意义上提出对偶问题（续）则设备用于外加工的总收入为：设备台时价格越大，总收入就越大，我们当然希望总收入越大越好。但是，价格问题不是一个企业能完全确定的，它是一种社会价格。因此，我们希望知道最低的总收入是多少，或者说，最低的设备台时价格是多少时就和自己生产产品甲乙所得的收入是一样的。因此，这个问题的数学模型为：很显然，当时 ，决策

3、者认为设备用于外加工和用于生产产品甲乙这两种方案的效果是一样的。 *Page 3 of 28 3-1 对偶问题的提出从数学模型上提出从数学模型上提出对偶问题在上述矩阵表示的单纯形表中，若问题达到了最优解，则其检验数行均小于等于零，即：对其讨论如下：用 ，称之为单纯形乘子，对于最优解而言，显然有 。对于包含基变量在内的检验数，在最优解的情况下可以表示为：因为 在约束 的条件下无上界，所以它只存在最小值，它与常向量b的乘积也只存在最小值。记 作为： *Page 4 of 28 3-1 对偶问题的提出从数学模型上提出定义新的LP模型为原模型的对偶模型且注意到：原模型 在约束 条件下的最优解为： 所以

4、有：对偶模型*Page 5 of 28 3-2 写对偶问题将上一节中原问题与对偶问题的矩阵式展开：对偶式*Page 6 of 28 3-2 写对偶问题表格形式为便于叙述和记忆对偶问题，通常规定一个标准形式，一般规定原规划为“”约束，对偶规划为“”约束，变量均0的对偶问题为标准形式。把它们之间的关系用表格形式表示出来 ：*Page 7 of 28 3-2 写对偶问题非标准型的处理在实际问题中常常会有非标准形式，如有等式约束，或某变量无非负约束等等。如果某个约束为等式约束，可以把它变为两个不等式约束如下：等价变换写对偶*Page 8 of 28 3-2 写对偶问题对偶关系表注意：助记法：标准型应是

5、，应是，这是对于对偶变量0而言；若对偶变量0，则符号方向相反；等式对应无约束。 *Page 9 of 28 3-2 写对偶问题例题例3-1：写出下面线性规划问题的对偶问题。 解：根据对偶问题变换规则，其对偶问题如下： *Page 10 of 28 3-3 对偶问题的性质对称性：对偶问题的对偶是原问题。证明：设原问题是： 对偶问题是： 对偶再对偶此即原模型证闭*Page 11 of 28 3-3 对偶问题的性质弱对偶性弱对偶性若 是原问题的可行解， 是对偶问题的可行解，则存在 证明：设原规划问题是 若 又是其对偶问题的可行解， 用 左乘式两侧得： 是原问题的可行解，满足约束条件 用 右乘式两侧得

6、： 得到结论： 命题得证 *Page 12 of 28 3-3 对偶问题的性质等值最优性等值最优性设 是原问题的可行解， 是对偶问题的可行解，当时 ， 分别是原问题和对偶问题的最优解。 证明： 据性质2，有 （对偶问题的任一可行解不小于原问题的任一个可行解） 又 由 的任意性可知， 是对偶问题可行解中最小的一个，故是最优解。 同理， 由 的任意性可知， 是原问题可行解中最大的一个，故是最优解。 证毕*Page 13 of 28 3-3 对偶问题的性质对偶定理对偶定理若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。 证明：设 是原问题的最优解，则必有 即 这时的是对偶问题的可行解，所

7、以得到对偶问题的目标值 是原问题的最优解，它使目标函数取值为 由定理3的等值最优性可知， 是对偶问题的最优解。命题得证 *Page 14 of 28 3-3 对偶问题的性质互补松弛定理互补松弛定理（松紧定理）若 分别是原问题和对偶问题的可行解， 分别是原问题和对偶问题的松弛变量，那么，当且仅当 与 为最优解时，有关系式： 证明：设原问题和对偶问题的标准型分别为： 原问题中的目标函数中的系数向量 C 用 代替后得到： 将对偶问题的目标函数 b 中系数列向量用 代替后得到： 若 分别为原问题和对偶问题的最优解，将 代入、式得： *Page 15 of 28 3-3 对偶问题的性质互补松弛定理互补松

8、弛定理 (续)根据等值最优性定理有： 又 具有非负性 必有 同样，将可行解 代入、式，若有 ，则一定有 ，根据等值最优性定理， 必为原问题和对偶问题的最优解。 证毕 *Page 16 of 28 3-3 对偶问题的性质互补松弛定理例题例3-2 已知下面线性规划模型对偶问题的最优解 为 试用对偶理论找出原问题的最优解。解：先写出它的对偶模型*Page 17 of 28 3-3 对偶问题的性质互补松弛定理例题例3-2（续）设原问题的最优解为：对偶问题的最优解为：原问题加入松弛变量：对偶问题加入松弛变量：根据互补松弛定理有：变量的对应关系为：即原问题的两个约束均为等式约束。*Page 18 of 2

9、8 3-3 对偶问题的性质互补松弛定理例题例3-2（续）将Y*代入对偶问题约束，知道为严格不等式，则其对应的松弛变量 均不等于零。因此，原问题的约束变成为：求解此二元一次方程组得到：故原问题的最优解为：*Page 19 of 28 3-3 对偶问题的性质解与检验数原问题的检验数对应对偶问题的一个解。证明：设原问题为： 对偶问题为： 设B是原问题的一个可行基，则有： 原问题和对偶问题可以写成： 注：这里 ，其中 是对应于原问题中基变量 的剩余变量， 是对应于原问题中非基变量 的剩余变量。 *Page 20 of 28 3-3 对偶问题的性质解与检验数性质6（续）当求得了原问题的一个基本可行解 ，

10、并得到相应的检验数： 令 ，并代入到上述对偶问题的模型中得到： 即对偶问题的解： ，它们恰好是原问题基本可行解所对应的检验数的负值。 证毕 *Page 21 of 28 3-3 对偶问题的性质解与检验数性质6的讨论：由性质6可知，用单纯形表求解原问题的迭代过程中，在检验数行的各检验数对应于对偶问题的一个可行解，它们的关系是： 注：单纯形表中的检验数与对偶问题解之间仅差一个负号 由此可见，在求解原问题的单纯形表中，每迭代一次，得到原问题的一个基本可行解，所得的一组检验数，对应于对偶问题的一个解。要说明的是，若原问题未达最优，则检验数所对应的对偶问题的这个解是基本非可行解，当原问题达到最优解时，则

11、这个解是基本且可行解，而且也达到最优解；当原问题为无界解（无最优解）时，对偶问题无可行解。 *Page 22 of 28 3-4 对偶单纯形法对偶单纯形法思想对偶单纯形法并非将原问题写成对偶问题，再用单纯形表求解，而是利用对偶问题的性质求解线性规划模型，它提供了单纯形表的另一种用法。 在单纯形表中，b 列对应于原问题的一个基本可行解，而检验数行则对应其对偶问题的一个基本解。在前面我们进行单纯形表的迭代中，始终保持原问题为基本可行解（即 b 列大于等于零），而对偶问题为基本非可行解（即检验数行含有正值），一旦检验数行有基本非可行解变为基本可行解，则原问题和对偶问题同时达到最优解。 根据对偶问题的

12、对称性，单纯形表的迭代过程也可以反过来进行，即保持对偶问题始终是基本可行解（即保持 ），而使原问题从基本非可行解逐步迭代到基本可行解，从而使原问题和对偶问题同时得到最优解。这种单纯形表的应用方法称为对偶单纯形法。 *Page 23 of 28 3-4 对偶单纯形法对偶单纯形法流程对偶单纯形法流程*Page 24 of 28 3-4 对偶单纯形法例题例3-3：用对偶单纯形法求解下列线性规划模型。 解：首先将模型标准化。令 ，并加入松弛变量 得到标准模型： *Page 25 of 28 3-4 对偶单纯形法例题（续）列单纯形表如下 Cj 8 16 12 0 0 CBXB x1 x2 x3 x4 x5 b 0 0 x4 x5 1 4 0 1 0 2 0 4 0 1 2 3 cjzj 8 16 12 0 0 0 4 3 Cj 8 16 12 0 0 CBXB x1 x2 x3 x4 x5 b 012 x4 x3 1 4 0 1 0 1 /2 0 1 0 1 /4 2 3/4 cjzj 2 16 0 0 3 9 2 4 *Page 26 of 28 3-4 对偶单纯形法例题（续）最小化问题的最优解为 完 Cj 8 16 12 0 0 CBXB x1 x2 x3