第六章 单纯形法的灵敏度分析与对偶

《第六章 单纯形法的灵敏度分析与对偶》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第六章单纯形法的灵敏度分析与对偶§1单纯形表的灵敏度分析§2线性规划的对偶问题§3对偶规划的基本性质2每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。例题1某工厂在计划期内安排Ⅰ、Ⅱ两种产品，生产单位产品所需设备A、B、c台时如表所示该工厂每生产一单位产品可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少产品和Ⅱ产品，才能使工厂获利最多？解：设为产品的计划产量，为产品Ⅱ的计划产量，则有目标函数：Maxz=50+100约束条件：§2线性规划的对偶问题和灵敏度分析3现在我们从另一个角度来考虑这个问题。假如

2、有另外一个工厂要求租用该厂的设备A、B、c，那么该厂的厂长应该如何来确定合理的租金呢？设分别为设备A、B、c的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，生产单位产品所需各设备的台时各总租金不应低于原利润50元，即，否则就不出租还是用于生产产品以获利50元；同样生产一单位产品所需各设备的台时的总租金也不应当低于原利润100元，即，否则这些设备台时就不出租，还是用于生产产品以获利100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min，这样我们得到了该问题的数学

3、模型：目标函数：约束条件：这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。§2线性规划的对偶问题资源价格问题两问题数学模型的对应关系(1)两个问题的系数矩阵互为转置。(2)一个问题变量的个数，等于另一个问题的约束条件的个数。MaxZ（X）=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0MinW(y）=300y1+400y2+250y3y1+2y2≥50y1+y2+y3≥100y1，y2，y3≥0y1x1x2y2y3(3)一个问题的右

4、端常数，是另一个问题的目标函数的系数。(4)若一个问题的目标为“max”，约束为“≤类型；则另一个问题的目标为“min”，约束为“≥”类型。这种关系称为对称型对偶关系。生产计划问题MaxZ（X）=4x1+5x2x1+x2≤452x1+x2≤80x1+3x2≤90x1，x2≥0例：生产计划问题资源价格问题MinW(y）=45y1+80y2+90y3y1+2y2+y3≥4y1+y2+3y3≥5y1，y2，y3≥0资源价格问题MaxZ（X）=4x1+5x2x1+x2≤452x1+x2≤80x1+3x2≤90x1，x2≥0MinW(y）=45y1+80y2+90y3y1+2y2

5、+y3≥4y1+y2+3y3≥5y1，y2，y3≥0生产计划问题7下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。s.t.§2线性规划的对偶问题8这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于等于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以-1，使不等号方向改变即可，得这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有显然，这两个约束条件与原来第三个约束条件是等价

6、的，我们再把其中的两边都乘以-1，得§2线性规划的对偶问题9通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：s.t.§2线性规划的对偶问题10这个求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题：s.t.§2线性规划的对偶问题11这里和一样都是不同的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为。因为在该对偶问题中和的系数只相差一个符号，我们可以把上面的对偶问题化为：s.t.§2线性规划的对偶问题12进一步，我们可以令，这时当时，，当时，。这也就是说，尽管但的取值可以为正，可以为0，可以为负，即没有非负限

7、制。这样我们把原规划的对偶问题化为s.t.没有非负限制。对照原线性规划问题，我们可以知道：当原线性规划问题的第i个约束条件取等号时，则其对偶问题的i个决策变量没有非负限制。如果当原线性规划问题中的第i个决策变量没有非负限制时，我们也可以用进行替换，这里，，用类似的方法知道其对偶问题中第i个约束条件取等号。§2线性规划的对偶问题例求对偶MaxZ（X）=2x2-5x3x1+x3≥22x1+x2+6x3≤6x1-x2+3x3=0x1，x2，x3≥0MaxZ（X）=2x2-5x3x1+x3≥22x1+x2+6x3≤6x1-x2+3x3=0x1，x