运筹学25-27.ppt

在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数CN-CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是什么? 设B是｛max z=CX｜AX≤b，X≥0｝的最优基， 由-Yb= -CB B-1b可知 z*=CBB-1b=Y*b 。 对z求偏导数，得 yi*的值代表对第i种资源的估价-影子价格。 这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。 在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。 影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。 第6节???偶单纯形法 前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。 通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解。即原问题与对偶问题都是最优解。 设原问题max z=CXAX=bX≥0 又设B是一个基。不失一般性，令B=(P1，P2，…，Pm)，它对应的变量为 XB=(x1，x2，…,xm) 当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i＜0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是 每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。 对偶单纯形法的计算步骤如下：  (1) 根据线性规划问题，列出初始单纯形表。 检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。 若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。 例6 用对偶单纯形法求解  min ω=2x1+3x2+4x3 x1+2x2+x3≥3 2x1-x2+3x3≥4 x1，x2，x3≥0 解 先将此问题化成下列形式，以便得到对偶问题的初始可行基 max z=-2x1-3x2-4x3 -x1-2x2-x3+x4 =-3 -2x1+x2-3x3 +x5=-4 xj≥0，j=1,2,…,5 初始单纯形表，见表2-6。 表 2-8 [eg.8]用对偶单纯形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 ≥ 1 2x1 - x2 + 3x3 ≥ 4 x1,x2,x3 ≥ 0 从以上求解过程可以看到对偶单纯形法有以下优点： (1) 初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。 (2) 当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。 (3) 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。 练习2 用对偶单纯型求解 对偶单纯型法的单纯型表(min) 以前讨论线性规划问题时，假定αij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。 如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。 因此提出这样两个问题： (1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化； (2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。后一个问题将在第8节参数线性规划中讨论。 例1 已知下述问题的最优解及最优单纯形表, 最优单纯形表如下: 7.2 价值系数 cj 的灵敏度分析 cj 变动可能由于市场价格的波动，或生产成本的变动 cj 的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围?