运筹学课件2012

1、适用专业：信息管理 授课教师：张凤玲,运 筹 学,课程回顾,线性规划问题灵敏度分析,1）C CN 影响对应的某个非基变量检验数 CB 影响所有非基变量检验数 2）b 影响基变量取值 最优基 最优解,本次授课内容,增加一个变量 增加一个约束 技术系数A发生变化,课程回顾,1、单纯形法小结 2、线性规划应用,本次授课内容,线性规划问题灵敏度分析 价值系数 资源常数,课程回顾,一、什么样的问题可以建立线性规划模型？,一般讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划模型 （1）要求解问题的目标函数能用数值指标来反映，且为线性函数； （2）存在着多种方案； （3）要求达到的目标是在一定的约束

2、条件下实现的，这些约束条件可用线性等式或不等式来描述。,二、建立模型的步骤,（1）设变量 （2）定目标 （3）列约束,课程回顾,添加松弛变量，构造单位矩阵 添加人工变量 1）大M法人工变量不能够影响目标函数，必须取0 用M放大人工变量的影响 2）两阶段法 对人工变量构造新的目标函数，使人工变量的系数为-1,迭 代 运 算 1、用非基变量替换基变量 2、对主元素行（第l行） 令bi/ aikbl;alj/alk ajl 3、对主元素列（第k列） 令1 alk;0 其它元素 4、表中其它行列元素 令aij-ali/alkaik aij bi-bl/alkaik bi,添加松弛变量、人工变量 列出初

3、始单纯形表,计算非基变量 各列的检验数J,所有J0,基变量中有非 零的人工变量,某非基变量 检验数为零,唯一 最优解,对任一J 0 有aik0,令KmaxJ ,对所有aik 0计算 ibi/ aik 令lmini xl为换出变量 aik为主元素,无界解,无可行解,无穷多最优解,是,否,否,是,否,是,是,否,第三章灵敏度分析,3.1灵敏度分析的含义 1、意义 A代表企业的技术状况 B代表企业的资源状况 C代表企业产品市场状况 决策者 预先了解各因素变化时的反应,在实际生产过程中，不断变化,2、灵敏度分析的类型,目标函数中价值系数C的变化（基变量价值系数变化；非基变量价值系数变化） 右端资源常数

4、b变化 增加一个变量 增加一个约束 技术系数A发生变化,第三章 灵敏度分析,3.2 价值系数C发生改变,1）当CN中某个Cj发生变化时，只影响xj的检验数，若cj的变化满足j(cj-zj)0，则目前解还是最优；否则就不是最优，继续单纯形迭代就可以求得新的最优解。 若不影响原最优解，分析Cj变化范围,例：对于下例问题，讨论c3范围,1、价值系数C发生改变,2）当CB中某个Ci发生变化时，则会影响所有非基变量的检验数，若ci的变化满足N0，则目前解还是最优；否则就不是最优，继续单纯形迭代就可以求得新的最优解。 最优解不变的情况下，CB的变化范围,例：对于下题中，讨论C1在什么范围内变化，问题的最优

5、解不变,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,0,0,c1-3,CB,XB,b,j(cj-zj),c1,c1,-1,-5/3,-1/3,3c1-3,4,5,0,0,0,c13,C13/4,c13,当3/4c13时，最优解不变。,习题,已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：,试分析： (1)目标函数中变量x3的系数变为6，最优解是什么？ (2)目标函数中变量x1和x2的系数在什么范围内变动时最优解不变？,3.3 右端资源常数b发生改变,当b中某个分量bi发生改变时，将影响

6、所在基变量的取值XB=B-1b。若bi的变化仍满足B-1b0，则目前基还是最优基。最优解为X=(B-1b,0)；否则，若bi的变化使B-1b中某些分量小于0，则目前基成了不可行基。可以用对偶单纯形法迭代求得新的最优解。,例：在例1中，讨论b1改变的情况（b1在什么范围内变化时，当前最优基不变）,解：设b变为(b1,9)T,若B1b0则,解得9/4b19,习题,已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：,0,-2,-1,-3,0,0 1,x5,1 1,x4,1 1,x3,1 3,x2,1 0,6 10,x1 x5,x1,cj-zj,试说明分别发生下列变化时，最优解改变么？ (

7、a)目标函数变为maxZ=2x1+3x2+x3 (b)约束条件右端项由(6,4)T变为(3,4)T,课程小结,线性规划问题合理配料问题 灵敏度分析 1）C CN 影响对应的某个非基变量检验数 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计算得到。

8、若n+10，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则当n+10时，则应以xn+1进基，作单纯形迭代，从而找出新的最优解。,例：在例1中，讨论增加产品D时的情况，假设产品D的单位利润为5（千元），工时消耗和材料消耗为（2,3）T,解：,6=c6-CBB-1P6=5-(2,3) =2/30,5,x6,5/3,1/3,2/3,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,0,0,-1,-5/3,-1/3,CB,XB,b,j(cj-zj),0,x5,5/3,1/3,2/3,3/5,0,-3/

9、5,4/5,-1/5,-1/5,1,11/5,-3/5,2/5,3/5,9/5,x6,x2,5,3,1,0,-2/5,0,-3/5,-11/5,-1/5,0, ,习题,7、已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：,试说明分别发生下列变化时，新的最优解是什么？ (3)约束条件右端项由(1,3)T变为(2,3)T (4)增加一个新的变量x6，P6= (1,1)T，C6=7,3.4 增加约束条件,外部环境变化 生产原材料变化 条件变化 出现新的约束条件,增加一个约束,把目前的最优解代入新增加的约束， 能满足约束条件，则说明该增加的约束条件对最优解不构成影响，即不影响最优生产计划

10、的实施。 若当前最优解不满足新增加的约束，则应把新的约束添加到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。,例：在例1的问题中增加约束2x1+2x2+x35，讨论最优解的情况,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,0,0,-1,-5/3,-1/3,CB,XB,b,j(cj-zj),解：将当前最优解X=(1,2,0)T代入约束条件中，得 21+22+065,在新增加的约束条件中引入松弛变量得2x1+2x2+x3+x6=5 加入最优表得,2,2,1,0,0,1,0,x

11、6,0,0,5,x6,0,2,3,3,0,0,x1,x2,x3,x4,x5,1,0,-1,4/3,-1/3,0,1,2,-1/3,1/3,1,2,x1,x2,2,3,CB,XB,b,j(cj-zj),0,x6,0,0,2,2,1,0,0,1,5,x6,0,0,2,3,-8/3,2/3,1,3,0,0,-1,-2,0,1,-1,0,0,-1,-5/3,-1/3,0,2,3,0,x1,x2,x4,1/3,13/6,1/2,1,0,-5/3,0,-1/3,0,1,13/6,0,1/3,2/3,-1/6,0,0,1,0,1/2,-1/2,0,0,-1/6,0,-1/3,-5/6,1,5/6, ,企业某

12、种工艺改进，原材料消耗发生变化 生产计划如何调整,3.5 A中的元素发生变化,N中Pj改变的情形：与增加一个变量时完全相同，只需要认为新增加一个产品，其利润与xj的利润相同为cj，而其消耗系数Pn+1等于变化后的Pj，则可以直接用处理增加一个变量的方法进行处理。,例：对例1中的线性规划，若a23由7改变为5，试讨论其最优解的情况。,-1,2,4/3,-1/3,1,0,0,1,-1/3,1/3,-1,-5/3,0,0,-1/3,1,2,x1,x2,2,3,Cj-zj,XB,CB,b,x4,x5,0,0,3,0,2,3,0,3,9/4,Cj-zj,初始单纯形表,最终单纯形表,解：虚拟一种产品D，其

13、单位利润为c6=3，资源消耗为P6(1，5)T，则,6C6-CBB-1P6-1/30,由此可知，最优解不变。,试讨论a23在什么范围变化时最优解不变？,CB,XB,b,初始单纯形表,最终单纯形表,问题一：若原计划生产产品I的工艺结构有了改进，这时有关它的技术系数向量变为P1(2,5,2)T，每件利润为4元。试分析对原计划有什么影响？,问题二：若原计划生产产品I的工艺结构有了改进，这时有关它的技术系数向量变为P1(4,5,2)T，每件利润为4元。试问该厂应如何安排最优生产方案？,解：把改进工艺的产品I看作产品I，设x1为其产量，计算在最终表中x1对应的列向量B-1P1和检验数1。,1 0 0,5

14、/4 1/2 3/8,0,x1,x1,3/8,5/4 -7/2 11/8,-21/8,2、已知线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表如下所示，请将表中空白处数字填上。,习题,CB,XB,b,cj-zj,cj-zj,习题,6、已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：,0,-2,-1,-3,0,0 1,x5,1 1,x4,1 1,x3,1 3,x2,1 0,6 10,x1 x5,x1,cj-zj,试说明分别发生下列变化时，新的最优解是什么？ (a)目标函数变为maxZ=2x1+3x2+x3 (b)约束条件右端项由(6,4)T变为(3,4)T (c)增添一

15、个新的约束x1+2x32,习题,7、已知右侧的线性规划问题用单纯形法求解得最终单纯形表如下表所示：,试说明分别发生下列变化时，新的最优解是什么？ (1)目标函数中变量x3的系数变为6； (2)目标函数中变量x1和x2的系数在什么范围内变动时最优解不变？ (3)约束条件右端项由(1,3)T变为(2,3)T (4)增加一个新的变量x6，P6= (1,1)T，C6=7 (5)增添一个新的约束x1+2x2 +x34,例1.某工厂在计划期内要安排生产、三种产品，已知生产单位产品所需的A、B两种原材料的消耗，如表1-1所示。,该工厂每生产一件产品可获利2元，每生产一件产品、可获利3元，问应如何安排计划使该工厂获利最多？,表1-1,XB,CB,b,x4,x5,0,0,3,0,2,3,0,-3/4,7/4,1,0,3/4,1/4,0,1,-1/4,1/4,-9/4,0,5/4,0,-3/4,3/4,9/4,x4,x2,0,3,-1,2,4/3,-1/3,1,0,0,1,-1/3,1/3,-1,-5/3,0,0,-1/3,1,2,x1,x2,2,3,3,9/4, ,1,9, ,Cj-zj,Cj-zj,Cj-zj,用单纯形法求解下列问题,