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

第二章 线性规划问题的对偶理论;单纯形法的矩阵描述（1）;单纯形法的矩阵描述（2）;单纯形法的矩阵描述（3）;单纯形表的矩阵形式 注意：通过以上形式可以看出，单纯形表的计算可以转化为矩阵计算，其关键在于求得B-1;关于矩阵的逆阵（1）;关于矩阵的逆阵（1）;问题实例（1） 某工厂生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备A、B、C台时和产品的获利情况如下表所示： 该厂应如何安排生产，才能使获利最大？;;问题实例2 该厂厂长决定不进行生产了，要将设备A、B、C??租，问租金最低时多少？ 分析 （1）设y1,y2,y3分别表示设备A、B、C每个台时的租金，因此该问题的目标函数应为： （2）把生产单位产品Ⅰ的台时用于出租，不能低于它的利润，即 （3）把生产单位产品Ⅱ的台时用于出租，不能低于它的利润，即;;对偶问题的提出（3）;对偶问题的特征 如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数 最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的 关系。 （1）求目标函数最大值的线性规划问题中有n个变量、m个约束条件。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量、n个约束条件； （2）原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原向题的目标函数中的第j个变量的系数就等于对偶问题中的第j个 约束条件的右边常数项；(j=1,2,…,n) （3）原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系 数。并且原问题的第i个约束条件的右边常数项就等于对倪问题的日标函数中 的第i个变量的系数；(i=1,2,…,m) ;;对偶问题的种类 对称性对偶问题（见定义） 举例 注意：在第一章中，一直强调约束条件右端b要大于等于0，而在对偶问题的研究中b的取值可以任意。;;;;对偶问题的提出（5）;;给出性质讨论的前提条件 ;对偶问题的性质（1）;弱对偶性 ;;通过观察可知;无界性 若原问题（对偶问题）无界，则对偶问题（原问题）无可行解 注意：这个性质不可逆。 当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。;;;最优性判断性质 ;对偶定理 若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。 ;;互补松弛性 ;;实例;;;原问题单纯形表的检验数行对应其对偶问题的一个基解，当原问题达到最优解时，其检验数也是对偶问题的最优解。;;实例;;;;对偶单纯型法（1）;转化;计算步骤 （1）根据线性规划问题，列出初始单纯形表，检查b列数字，若都为非负，且检验数都为非正，则以达到最优解，停止计算 （2）确定出基变量。 （3）确定入基变量。 （4）进行矩阵初等变换，构造新的单纯形表，转（1）;;