大学运筹学经典课件第六章—-单纯形法的灵敏度分析与对偶.ppt

* 加上剩余变量 和人工变量 ，把此问题化成标准型如下： 把上述数据填入单纯形表计算。 §2 线性规划的对偶问题 * 迭代变量 基变量 b -300 -400 -250 0 0 -M 1 -M 1 ② 0 -1 0 1 50 50/2 -250 1 1 1 0 -1 0 100 100/1 -M-250 -2M-250 -250 M 250 -M -50M-25000 M-250 2M-150 0 -M -250 0 2 -400 1/2 1 0 -1/2 0 1/2 25 -250 1/2 0 1 1/2 -1 -1/2 75 -325 -400 -250 75 250 -75 -28750 25 0 0 -75 -250 -M+75 3 -300 1 2 0 -1 0 1 50 -250 0 -1 1 1 -1 -1 50 -300 -350 -250 50 250 -50 -27500 0 -50 0 -50 -250 -M+50 §2 线性规划的对偶问题 由上表，最优解： =50， -f 的最大值为-27500，即目标函数f的最大值为f=27500元。 从上面可知租金：A设备为50元，B设备为0元，C设备为50元。这样把工 厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出 租设备的最小费用，因为这是目 标函数的最小值。 通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种 设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划 的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而 求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最 优值，因为这两个最优值相等。 * §2 线性规划的对偶问题 * 下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。 S.T. §2 线性规划的对偶问题 * 这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（-1），使不等号方向改变即可，得 这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有 显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的 两边都乘以（-1），得 §2 线性规划的对偶问题 * 通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题： s.t. §2 线性规划的对偶问题 * 这个求最大值的线性规划问题的约束条件都取小于等于号，我们马 上可以写出其对偶问题： s.t. §2 线性规划的对偶问题 * 这里 和 一样都是不同的决策变量，为了表示这两个 决策变量都来源于原问题的第三个约束条件，记为 。 因为在该对偶问题中 和 的系数只相差一个符号，我们可以把 上面的对偶问题化为： s.t. §2 线性规划的对偶问题 * 进一步，我们可以令 ，这时当 时， ，当 时， 。这也就是说，尽管