运筹学单纯形法的对偶问题.pptx

§1 线性规划的对偶问题 每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。例题1 某工厂在计划期内安排Ⅰ、Ⅱ两种产品，生产单位产品所需设备A、B、c台时如表所示 该工厂每生产一单位产品 可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少 产品和Ⅱ产品，才能使工厂获利最多？解：设 为产品 的计划产量， 为产品Ⅱ的计划产量，则有目标函数：Max z=50 + 100约束条件： §1 线性规划的对偶问题 现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、c，那么该厂的厂长应该如何来确定合理的租金呢？ 设 分别为设备A、B、c的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，生产单位 产品所需各设备的台时各总租金不应低于原利润50元，即 ，否则就不出租还是用于生产 产品以获利50元；同样生产一单位 产品 所需各设备的台时的总租金也不应当低于原利润100元， 即 ，否则这些设备台时就不出租，还是用于生产 产品以获利100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min，这样我们得到了该问题的数学模型： 目标函数： 约束条件： 这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。§1 线性规划的对偶问题 如果我们把求目标函数最大值的线性规划问题看成原问题，则把求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。 1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。 2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。 3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于对偶问题的目标函数中的第i个变量的系数。 4对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置 。 设 A=则 §1 线性规划的对偶问题如果我们用矩阵形式来表示，则有原问题： 其中A是 矩阵m×n，该问题有m个约束条件n个变量， , , 对偶问题： 其中 是A的转置， 是b的转置,是c的转置, y=现在我们用单纯形法求对偶问题的解。§1 线性规划的对偶问题 加上剩余变量 和人工变量 ，把此问题化成标准型如下：把上述数据填入单纯形表计算。§1 线性规划的对偶问题迭代变量基变量 b-300-400-25000-M 1-M1② 0 -1 0 15050/2-250 1 1 1 0 -1 0 100100/1-M-250-2M-250-250M250-M-50M-25000M-502M-1500-M-25002-4001/210-1/201/225-2501/2011/2-1-1/275-325-40075-287502500-75-250-M+753-300120-10150-2500-111-1-150-300-35050-275000-500-50-250-M+50§1 线性规划的对偶问题 由上表，最优解：=50， -f 的最大值为-27500，即目标函数f的最小值为f=27500元。 从上面可知租金：A设备为50元，B设备为0元，c设备为50元。这样把工厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目 标函数的最小值。 通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。 §1 线性规划的对偶问题 下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。