运筹学课件2012-3

适用专业：信息管理授课教师：张凤玲运筹学课程回顾线性规划问题灵敏度分析1）CCN影响对应的某个非基变量检验数CB影响所有非基变量检验数2）b影响基变量取值最优基最优解本次授课内容增加一个变量增加一个约束技术系数A发生变化课程回顾1、单纯形法小结2、线性规划应用本次授课内容线性规划问题灵敏度分析——价值系数——资源常数课程回顾一、什么样的问题可以建立线性规划模型？一般讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划模型（1）要求解问题的目标函数能用数值指标来反映，且为线性函数；（2）存在着多种方案；（3）要求达到的目标是在一定的约束条件下实现的，这些约束条件可用线性等式或不等式来描述。二、建立模型的步骤（1）设变量（2）定目标（3）列约束课程回顾≤添加松弛变量，构造单位矩阵≥添加人工变量1）大M法人工变量——不能够影响目标函数，必须取0用M放大人工变量的影响2）两阶段法对人工变量构造新的目标函数，使人工变量的系数为-1迭代运算1、用非基变量替换基变量2、对主元素行（第l行）令bi/aik→bl;alj/alk→ajl3、对主元素列（第k列）令1→alk;0→其它元素4、表中其它行列元素令aij-ali/alk×aik→aijbi-bl/alk×aik→bi添加松弛变量、人工变量列出初始单纯形表计算非基变量各列的检验数δJ所有δJ≤0基变量中有非零的人工变量某非基变量检验数为零唯一最优解对任一δJ＞0有aik≤0令δK＝max{δJ}对所有aik＞0计算Θi＝bi/aik令Θl＝min{Θi}xl为换出变量aik为主元素无界解无可行解无穷多最优解是否否是否是是否第三章灵敏度分析3.1灵敏度分析的含义1、意义A代表企业的技术状况B代表企业的资源状况C代表企业产品市场状况决策者预先了解各因素变化时的反应在实际生产过程中，不断变化2、灵敏度分析的类型目标函数中价值系数C的变化（基变量价值系数变化；非基变量价值系数变化）右端资源常数b变化增加一个变量增加一个约束技术系数A发生变化第三章灵敏度分析3.2价值系数C发生改变1）当CN中某个Cj发生变化时，只影响xj的检验数，若cj的变化满足δj(cj-zj)≤0，则目前解还是最优；否则就不是最优，继续单纯形迭代就可以求得新的最优解。若不影响原最优解，分析Cj变化范围23300x1x2x3x4x510-14/3-1/3012-1/31/312x1x22300-1-5/3-1/3CBXBbδj(cj-zj)例：对于下例问题，讨论c3范围1、价值系数C发生改变2）当CB中某个Ci发生变化时，则会影响所有非基变量的检验数，若ci的变化满足δN≤0，则目前解还是最优；否则就不是最优，继续单纯形迭代就可以求得新的最优解。最优解不变的情况下，CB的变化范围23300x1x2x3x4x510-14/3-1/3012-1/31/312x1x22300-1-5/3-1/3CBXBbδj(cj-zj)例：对于下题中，讨论C1在什么范围内变化，问题的最优解不变23300x1x2x3x4x510-14/3-1/3012-1/31/312x1x22300c1-3CBXBbδj(cj-zj)3411c131cc1c1-1-5/3-1/3δ3’＝c1-3δ4’＝δ5’＝3411c131c≤0≤0≤0c1≤3C1≥3/4c1≤3∴当3/4≤c1≤3时，最优解不变。-1-5-300-11x54-1x4-12x301x21012x1x2x1cj-zj习题0,,37/33/41/311/33/11/3.32321321321321xxxxxxxxxstxxxMaxZ已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：试分析：(1)目标函数中变量x3的系数变为6，最优解是什么？(2)目标函数中变量x1和x2的系数在什么范围内变动时最优解不变？3.3右端资源常数b发生改变当b中某个分量bi发生改变时，将影响所在基变量的取值XB=B-1b。若bi的变化仍满足B-1b≥0，则目前基还是最优基。最优解为X＊=(B-1b,0)；否则，若bi的变化使B-1b中某些分量小于0，则目前基成了不可行基。可以用对偶单纯形法迭代求得新的最优解。例：在例1中，讨论b1改变的情况（b1在什么范围内变化时，当前最优基不变）23300x1x2x3x4x510-14/3-1/3012-1/31/312x1x22300-1-5/3-1/3CBXBbδj(cj-zj)23300x1x2x3x4x510-14/3-1/3012-1/31/312x1x22300-1-5/3-1/3CBXBbδj(cj-zj)1311341313131341b-33-b9b--bB0303131134bb解：设b变为(b1,9)T若B－1b≥0则解得9/4≤b1≤9习题0,,42-6.232121321321xxxxxxxxstxxxMaxZ已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：0-2-1-3001x511x411x313x210610x1x5x1cj-zj试说明分别发生下列变化时，最优解改变么？(a)目标函数变为maxZ=2x1+3x2+x3(b)约束条件右端项由(6,4)T变为(3,4)T课程小结线性规划问题合理配料问题灵敏度分析1）CCN影响对应的某个非基变量检验数CB影响所有非基变量检验数2）b影响基变量取值最优基最优解3.3增加一个变量若企业在计划期内，有新的产品可以生产，是否会影响原定生产计划？若企业在计划期内，有新的产品可以生产则在知道新产品的单位利润Cn+1，消耗量Pn+1=(a1n+1,a2n+1,…,amn+1)T时，可以在最优表中补充一列，可以由B-1Pn+1得到，而检验数行可以由δn+1=Cn+1-CBB-1Pn+1计算得到。若δn+1≤0，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则当δn+1＞0时，则应以xn+1进基，作单纯形迭代，从而找出新的最优解。例：在例1中，讨论增加产品D时的情况，假设产品D的单位利润为5（千元），工时消耗和材料消耗为（2,3）T23300x1x2x3x4x510-14/3-1/3012-1/31/312x1x22300-1-5/3-1/3CBXBbδj(cj-zj)解：31353131313461261632--PBaaδ6=c6-CBB-1P6=5-(2,3)=2/3＞031355x65/31/32/323300x1x2x3x4x510-14/3-1/3012-1/31/312x1x22300-1-5/3-1/3CBXBbδj(cj-zj)0x55/31/32/33/50-3/54/5-1/5-1/5111/5-3/52/53/59/5x6x25310-2/50-3/5-11/5-1/50[]-1-5-300-11x54-1x4-12x301x21012x1x2x1cj-zj习题0,,37/33/41/311/33/11/3.32321321321321xxxxxxxxxstxxxMaxZ7、已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：试说明分别发生下列变化时，新的最优解是什么？(3)约束条件右端项由(1,3)T变为(2,3)T(4)增加一个新的变量x6，P6=(1,1)T，C6=73.4增加约束条件外部环境变化生产原材料变化条件变化出现新的约束条件增加一个约束把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束条件对最优解不构成影响，即不影响最优生产计划的实施。若当前最优解不满足新增加的约束，则应把新的约束添加到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。例：在例1的问题中增加约束2x1+2x2+x3≤5，讨论最优解的情况23300x1x2x3x4x510-14/3-1/3012-1/31/312x1x22300-1-5/3-1/3CBXBbδj(cj-zj)解：将当前最优解X=(1,2,0)T代入约束条件中，得2×1+2×2+0＝65在新增加的约束条件中引入松弛变量得2x1+2x2+x3+x6=5加入最优表得2210010x6005x6023300x1x2x3x4x510-14/3-1/3012-1/31/312x1x223CBXBbδj(cj-zj)0x6002210015x60023-8/32/31300-1-201-100-1-5/3-1/30230x1x2x41/313/61/210-5/30-1/30113/601/32/3-1/600101/2-1/200-1/60-1/3-5/615/6[]企业某种工艺改进，原材料消耗发生变化生产计划如何调整3.5A中的元素发生变化N中Pj改变的情形：与增加一个变量时完全相同，只需要认为新增加一个产品，其利润与xj的利润相同为cj，而其消耗系数Pn+1等于变化后的Pj，则可以直接用处理增加一个变量的方法进行处理。例：对例1中的线性规划，若a23由7改变为5，试讨论其最优解的情况。-124/3-1/31001-1/31/3-1-5/300-1/312x1x223Cj-zjx3x4x1x2x530230XBCBb171011140139x4x5003023039/4θCj-zj初始单纯形表最终单纯形表解：虚拟一种产品D，其单位利润为c6=3，资源消耗为P6＝(1，5)T，则δ6＝C6-CBB-1P6＝-1/3＜0由此可知，最优解不变。试讨论a23在什么范围变化时最优解不变？23000x1x2x3x4x5000x3x4x58161214020410001000123000CBXBb203x3x24420010-21/21/41/2-1/80100-3/2-1/80初始单纯形表最终单纯形表问题一：若原计划生产产品I的工艺结构有了改进，这时有关它的技术系数向量变为P1‘＝(2,5,2)T，每件利润为4元。试分析对原计划有什么影响？问题二：若原计划生产产品I的工艺结构有了改进，这时有关它的技术系数向量变为P1‘＝(4,5,2)T，每件利润为4元。试问该厂应如何安排最优生产方案？8/32/14/5PB'118/3PBCc'11B'1'1解：把改进工艺的产品I看作产品I’，设x1’为其产量，计算在最终表中x1’对应的列向量B-1P1’和检验数δ1’。1005/41/23/80x1x1’3/881/12/74/5PB'118/21PBCc'11B'1'15/4-7/211/8-21/82、已知线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表如下所示，请将表中空白处数字填上。2-11000x1x2x3x4x5x6000x3x4x56010203111-1112-11000100012-1100002-1x4x1x2100-11/2-1/2-21/21/2习题CBXBbcj-zjcj-zj……习题0,,42-6.232121321321xxxxxxxxstxxxMaxZ6、已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：0-2-1-3001x511x411x313x210610x1x5x1cj-zj试说明分别发生下列变化时，新的最优解是什么？(a)目标函数变为maxZ=2x1+3x2+x3(b)约束条件右端项由(6,4)T变为(3,4)T(c)增添一个新的约束－x1+2x3≥2-1-5-300-11x54-1x4-12x301x21012x1x2x1cj-zj习题0,,37/33/41/311