运筹学课件：第二章 线性规划问题的对偶理论

1、第二章 线性规划问题的对偶理论,单纯形法的矩阵描述（1,矩阵形式,单纯形法的矩阵描述（2,令,其中,单纯形法的矩阵描述（3,注意,单纯形表的矩阵形式 注意：通过以上形式可以看出，单纯形表的计算可以转化为矩阵计算，其关键在于求得B-1,单纯形法的矩阵描述（4,关于矩阵的逆阵（1,关于矩阵的逆阵（1,问题实例（1） 某工厂生产、两种产品，已知生产单位产品所需的设备A、B、C台时和产品的获利情况如下表所示： 该厂应如何安排生产，才能使获利最大,对偶问题的提出（1,建立模型 解：设产品的计划产量x1、产品的计划产量x2为决策变量，则问题可表示为,问题实例2 该厂厂长决定不进行生产了，要将设备A、B、C

2、出租，问租金最低时多少？ 分析 （1）设y1,y2,y3分别表示设备A、B、C每个台时的租金，因此该问题的目标函数应为： （2）把生产单位产品的台时用于出租，不能低于它的利润，即 （3）把生产单位产品的台时用于出租，不能低于它的利润，即,对偶问题的提出（2,建立模型 解：设y1,y2,y3为决策变量，分别表示设备A、B、C每个台时的租金，则问题可表示为,这样从两个不同的角度来考虑同一个工厂的最大利润(最小租金)的问题，所建立起来的两个线性规划模型就是一对对偶问题，其中任一个叫做原问题，而另外一个就叫对偶问题,对偶问题的提出（3,对偶问题的特征 如果我们把求目标函数最大值的线性规划问题看成原问题

3、，则求目标函数 最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的 关系。 （1）求目标函数最大值的线性规划问题中有n个变量、m个约束条件。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量、n个约束条件； （2）原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原向题的目标函数中的第j个变量的系数就等于对偶问题中的第j个 约束条件的右边常数项；(j=1,2,n) （3）原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系 数。并且原问题的第i个约束条件的右边常数项就等于对倪问题的日标函数中 的第i个变量的系数；(i=1,2,m,对偶问题的提出

4、（4,4）偶问题的约束条件的系数矩阵是原问题约束条件的系数矩阵的转置矩阵AT,对偶问题的种类 对称性对偶问题（见定义） 举例 注意：在第一章中，一直强调约束条件右端b要大于等于0，而在对偶问题的研究中b的取值可以任意,对偶问题的提出（5,非对称性对偶问题,实例,混合型对偶问题,对偶问题的提出（5,对偶问题的转换规则,给出性质讨论的前提条件,对偶问题的性质前提条件,P,D,对偶问题的性质（1,对称性 对偶问题的对偶是原问题 实例,弱对偶性,对偶问题的性质（2,实例,通过观察可知,无界性 若原问题（对偶问题）无界，则对偶问题（原问题）无可行解 注意：这个性质不可逆。 当原问题（对偶问题）无可行解时

5、，其对偶问题（原问题）或具有无界解或无可行解,对偶问题的性质（3,实例（1,试证明该线性规划问题无界,实例（2,最优性判断性质,对偶问题的性质（4,对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等,对偶问题的性质（5,总结 （1） （2）求解原问题最优解的同时也获得了其对偶问题的最优解,互补松弛性,对偶问题的性质（6,实例,原问题单纯形表的检验数行对应其对偶问题的一个基解，当原问题达到最优解时，其检验数也是对偶问题的最优解,对偶问题的性质（7,则,实例,由于 ，所以达到最优解，解为（7/2，3/2）； 最优目标函数值为17/2,对偶单纯型法（1,对偶单纯形法是求解线性规划的另一个基本方法，它是根据对偶原理和单纯形法的原理 而设计出来的，因此称为对偶单纯形法不要简单地将它理解为是求解对偶问题的单纯形法 实例,转化,计算步骤 （1）根据线性规划问题，列出初始单纯形表，检查b列数字