《运筹学—线性规划》由会员分享，可在线阅读，更多相关《运筹学—线性规划（181页珍藏版）》请在金锄头文库上搜索。
1、改进单纯形法的步骤 （1） 根据给出的线性规划问题的标准型，确定初始基变量和初始可行基。求初始可行基B的逆阵-1，得初始基本可行解。 （2）计算单纯形乘子 ，得目标函数当前值 （3） 计算非基变量检验数 ，若N0，则当前解已是最优解，停止计算；否则转下一步。 （4） 根据 ，确定非基变量 为换入变量，计算 ,若 0，则问题没有有限最优解，停止计算， 否则转下一步。,（5） 根据 ，确定基变量 为换出变量。 （6） 用 替代 得新基1，由变换公式 计算新基的逆阵1-1，求出新的基本可行解 其中 为变换矩阵，构造方法是：从一个单位矩阵出发，把换出变量 在基B中的对应列的单位向量，替换成换入变量 对
2、应的系数列向量 ，并做如下变形，主元素 （应在主对角线上）取倒数，其它元素除以主元素并取相反数。重复（2）（6）直至求得最优解。,换入,无界解,换出,最优解,初始基,新基,例9、试用改进单纯形法求解解：（）观察法确定 ， 为基变量 为非基变量,（2）计算单纯行乘子 目标函数当前值（3）非基变量检验数,(4） 选择换入变量故 为换入变量。计算,()确定换出变量确定 为换出变量，主元素(6) 用 代替 得新可行基 为基变量，为非基变量，重复以上步骤，进入第二循环,(1)(2)(3),(4) 选择 换入变量(5)选择 换出变量,主元素(6) 用 代替 得新可行基 为基变量， 为非基变量，进入第三循环
3、.,(1)(2)(3)非基变量对应的检验数全部非正，故当前解 即为最优解，相应的目标函数最优值 。,六、单纯形法总结,1、Min型单纯形表与Max型的区别仅在于：令 k=minj 0的xk进基，当 0时最优。,2、解的几种情况及其在单纯形表上的体现（讨论Max型）,唯一 最优解,j 0, 非基0 但B-1Pk 0,无可行解,用大M法求解，最优基中含有X人,退化解,最优解中某基变量为0,第三节 对偶问题与灵敏度分析,一、对偶问题及其模型 例7：回顾例1,这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。,例7称为例1的对偶问题，记为（D），例1称为例7
4、的原问题,记为（P）。,对偶模型的一般式,以例7为例，原问题为,（P）,（D）,这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：,原问题（P） 对偶问题 （D）目标max型 目标min型有n个变量（非负） 有n个约束（大于等于）有m个约束 （小于等于） 有m个变量（非负）价格系数 资源向量 资源向量 价格系数技术系数矩阵 技术系数矩阵的转置,此外，还有一种情形,例8：写出下面线性规划的对偶规划模型：,例8：写出下面线性规划的对偶规划模型：,min Z= - CX s.T - AX- bX 0,对称性定理：对偶问题的对偶是原问题。,max W = -Yb s.T YA
5、 CY 0,二、对偶问题的性质,弱对偶原理：设 和 分别是问题（P）和（D）的可行解，则必有,推论：若 和 分别是问题（P）和（D）的可行解，则 是（D）的目标函数最小值的一个下界； 是（P）的目标函数最大值的一个上界。,对偶问题的性质,对偶问题的性质,推论：在一对对偶问题(P)和(D)中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。,推论：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题无界。,例1,试估计它们目标函数的界，并验证弱对偶性原理。,（P）,对偶问题的性质,解：,（D）,由观察可知： ， ，分
6、别是（P）和（D）的可行解。Z=10 ，W=40，故有 ，弱对偶定理成立。由推论可知，W 的最小值不能小于10，Z 的最大值不能超过40。,对偶问题的性质,考虑,4.对偶定理 若（P）有最优解，则（D）也有最优解， 且最优值相同。,证：对（P）增加松弛变量， 化为,设其最优基为B，终表为,其检验数为,问题：(1) 由对偶定理可知，对偶问题最优解的表达式 Y* =？,(2) 求Y*是否有必要重新求解（ D）？, CBB-1, 不必。可以从原问题（P）的单纯形终表获得。,请指出其对偶问题的最优解和最优值。,5.互补松弛定理,y1 yi ym ym+1 ym+j yn+m,x1 xj xn xn+1
7、xn+ixn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,xjym+j=0 yixn+i=0 (i=1,2,m; j=1,2,n) 在一对变量中，其中一个大于0，另一个一定等于0,直观上,定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi 增加一个单位时，所引起的目标函数最优值Z* 的改变量y*i称为第i个约束条件的影子价格，又称为边际价格。,影子价格,设：B是问题 P的最优基，由前式可知，Z*=CB B-1b = Y*b=y*1b1+ y*2b2+y*Ibi+y*mbm 当bi 变为bi+1 时（其余右端项不变，也不影响B）,影子价格,目标函
8、数最优值变为：Z*= y*1b1+ y*2b2+y*I （ bi+1 ）+y*mbm Z*= Z* Z* = y*i,也可以写成： 即y*i 表示Z*对 bi的变化率。,其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi 就是第 i 个约束条件的影子价格。 也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。 若第 i 种资源的单位市场价格为mi ，当yi mi 时，企业愿意购进这种资源，单位纯利为yimi ，则有利可图；如果yi mi ，则企业有偿转让这种资源，可获单位纯利为miyi ，否则企业无利可图，甚至亏损。,影
9、子价格,影子价格,多了 32/7,影子价格,多了 6/7,影子价格,6. 对偶问题的经济解释（1）对偶最优解的经济解释资源的影子价格（Shadow Price）,CBB-1 对偶问题的最优解 买主的最低出价； 原问题资源的影子价格 当该资源增加1单 位时引起的总收入的增量卖主的内控价格。,解：（1）煤、电、油的影子价格分别是0、1.36、0.52； 其经济意义是当煤、电、油分别增加1单位时可使总收入分别增加0 、1.36、0.52。,（2）由单纯形终表还可得到：原问题的最优生产计划、最大收入、资源剩余，对偶问题的最低购买价格、最少的购买费用等。,y1 y2ym,（2）对偶约束的经济解释产品的机
10、会成本 (Opportunity Cost),机会成本 表示减少一件产品所节省的资源可以增加的利润,增加单位资源可以增加的利润,减少一件产品可以节省的资源,机会成本,利润,差额成本,（3）对偶松弛变量的经济解释产品的差额成本（Reduced Cost）,差额成本=机会成本 利润,在利润最大化的生产计划中（1）影子价格大于0的资源没有剩余；（2）有剩余的资源影子价格等于0；（3）安排生产的产品机会成本等于利润；（4）机会成本大于利润的产品不安排生产。,（4）互补松弛关系的经济解释,对偶单纯形法,基本思想若保持对偶问题的解是基可行解，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也就得
11、到了最优解。这种方法的优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。 基本原理对于原问题,设B是一个基，不失一般性,令 ，它对应的基变量为 。当非基变量都为零时，可以得到 。若在 中至少有一个负分量，设 ，并且在单纯形表的检验数行中的检验数都非正，即对偶问题保持可行解，它的各分量是:对应基变量的检验数是对应非基变量的检验数是,每次迭代是将基变量中的负分量取出，去替换非基变量中的，经过基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近，当原问题得到可行解时，便得到了最优解。,计算步骤列出初始单纯形表，检查b列中的各分量，若都为非负，且检验数都为
12、非正，则已得到最优解。若b列中至少有一个负分量，检验数保持非正，进行以下计算。确定换出变量。按照法则 确定对应的基变量为换出变量。,确定换入变量。 若xj所在行有负系数，计算所对应的非基变量xk为换入变量。以 为主元素，按原单纯形法迭代运算，得新单纯形表。重复 的步骤，直至求得最优解。,例：试用对偶单纯形法求解如下线性规划问题,首先将该问题化为,初始单纯形表，如表2.4所示 表2.4,b列各行为负，进行迭代计算，确定换出变量,故X3为换出变量 。,故X1为换入变量。换入、换出变量所在列、行的交叉处“2”为主元项。进行迭代运算，得表2.5。,表2.5,从表2.5可看出，b列中仍有负分量，继续迭代
13、计算，重复上述步骤，得表2.6。 表2.6,在表2.6中，b列各分量全为非负，检验数全为非正，故问题的最优解为 ，其对偶问题的最优解为 。,三、灵敏度分析讨论模型的系数或变量发生小的变化时对解的影响 （如它们在何范围内变化时可使原最优解或最优基不变？）,我们主要讨论C、b和变量结构变化时对解的影响。,对解怎样影响？ 影响解的 - 最优性- 可行性,1. b变化时的分析,2. C变化时的分析,3.增加新变量时的分析主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产，数学意义是xn+1是否应进基。,经济意义：,市场价,影子价,例11：在例1（煤电油例）中，其单纯形终表如下：,（1）电的影子价格是多少？使最优基仍适用的电的变化范围为何？ （2）若有人愿以每度1元的价格向该厂供应25度电，是否值得接受？ （3）甲产品的价格在何范围内变化时，现最优解不变？ （4）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为6.5，问该产品是否可投产？,例11：在例1（煤电油例）中，其单纯形终表如下：,
