运筹学线性规划问题的对偶理论推荐.pptVIP

运筹学课程 上海交通大学管理学院 人工变量法(1) 问题举例 人工变量 如果在线性规划模型的标准型中，不存在m*m阶单位阵，则可采用添加人工变量的方法来构建单位阵。 人工变量法(2) 大M法 在线性规划问题中添加人工变量后，令人工变量在目标函数中的系数为（-M）（M为任意大的正数），在目标函数实现得到最优解后，即变量中一定不包含人工变量，否则该问题无可行解。 上例问题，加入人工变量后变为 人工变量法(3) 两阶段法 第一阶段： 将原线性规划问题加入人工变量，并构造仅含人工变量、要求实现最小化的目标函数； 然后用单纯型法求解该模型，并进行判断： 若目标函数的最优值为0，则说明原问题存在基可行解，可以进行第二步计算； 否则，原问题无可行解停止计算。 第二阶段： 将第一阶段计算得到的最终表，除去人工变量，并将原问题目标函数中决策变量的系数带入表中，进行单纯型法的计算。 实例 第一阶段： 第二阶段 单纯型法小结（1） 标准型的转化总结 单纯型法小结（2） 第二章 线性规划问题的对偶理论 单纯形法的矩阵描述（1） 矩阵形式 单纯形法的矩阵描述（2） 单纯形法的矩阵描述（3） 对偶问题的提出（1） 问题实例（1） 某工厂生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备A、B、C台时和产品的获利情况如下表所示： 该厂应如何安排生产，才能使获利最大？ 建立模型 解：设产品Ⅰ的计划产量x1、产品Ⅱ的计划产量x2为决策变量，则问题可表示为 对偶问题的提出（2） 问题实例2 该厂厂长决定不进行生产了，要将设备A、B、C出租，问租金最低时多少？ 分析 （1）设y1,y2,y3分别表示设备A、B、C每个台时的租金，因此该问题的目标函数应为： （2）把生产单位产品Ⅰ的台时用于出租，不能低于它的利润，即 （3）把生产单位产品Ⅱ的台时用于出租，不能低于它的利润，即 建立模型 解：设y1,y2,y3为决策变量，分别表示设备A、B、C每个台时的租金，则问题可表示为： 对偶问题的提出（3） 对偶问题的特征 如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数 最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的 关系。 （1）求目标函数最大值的线性规划问题中有n个变量、m个约束条件。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量、n个约束条件； （2）原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原向题的目标函数中的第j个变量的系数就等于对偶问题中的第j个 约束条件的右边常数项；(j=1,2,…,n) （3）原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系 数。并且原问题的第i个约束条件的右边常数项就等于对倪问题的日标函数中 的第i个变量的系数；(i=1,2,…,m) （4）偶问题的约束条件的系数矩阵是原问题约束条件的系数矩阵的转置矩阵AT 对偶问题的提出（4） 对偶问题的转换规则 对偶问题的提出（5） 实例 作业中的问题 1、转化为标准型 无约束变量的转换 b值为负的情况 2、单纯型法求解过程 * Operation Research 第四讲 * ≤ 2.进行初等矩阵变换，得到单位基阵 令 其中 这样从两个不同的角度来考虑同一个工厂的最大利润(最小租金)的问题，所建立起来的两个线性规划模型就是一对对偶问题，其中任一个叫做原问题，而另外一个就叫对偶问题。 * Operation Research 第四讲