线性规划的对偶理论与灵敏度分析.pptVIP

*下面我们仍以第二章例1在最终单纯形表上对bj进行灵敏度分析。最终单纯形表如下所示：迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-50我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,01实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台02时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备03台时50元。04*第三章线性规划的对偶理论与灵敏度分析§1线性规划的对偶问题§2对偶规划的基本性质§3对偶单纯形法§4线性规划的灵敏度分析1线性规划的对偶问题*每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。例题1某工厂在计划期内安排Ⅰ、Ⅱ两种产品，生产单位产品所需设备A、B、C台时如表所示该工厂每生产一单位产品可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少产品和Ⅱ产品，才能使工厂获利最多？解：设为产品的计划产量，为产品Ⅱ的计划产量，则有目标函数：Maxz=50+100约束条件：，现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？设分别为设备A、B、C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，把生产单位产品所需各设备的台时各总租金不应低于原利润50元，即，否则就不出租还是用于生产产品以获利50元；同样把生产一单位产品所需各设备的台时的总租金也不应当低于原利润100元，即，否则这些设备台时就不出租，还是用于生产产品以获利100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min，这样我们得到了该问题的数学模型：目标函数：约束条件：这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。1求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。2原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。3原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。4对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。设A=则如果我们用矩阵形式来表示，则有原问题：其中A是矩阵m*n，该问题有m个约束条件n个变量，x=,b=,c=