运筹学第3章线性规划问题的计算机求解.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,广西大学数学与信息科学学院,管 理 运 筹 学,1,第三章 线性规划问题的计算机求解,1,“,管理运筹学,”,软件的操作方法,2,“,管理运筹学,”,软件的输出信息分析,2,第三章 线性规划问题的计算机求解,随书软件为“管理运筹学”,2.5,版（,Window,版），是,2.0,版（,DOS,版）的升级版。它包括：线性规划、运输问题、整数规划（,0-1,整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共,15,个子模块。,3,1,“,管理运筹学,”,软件的操作方法,【,例,1】,用,软件,求下列线性规划的最优解,1.,软件使用演示：,第一步：,点击,“,开始,”,-,“,程序,”,-,“,管理运筹学,2.0,”,，,弹出主窗口。,1,“,管理运筹学,”,软件的操作方法,4,本题选用“线性规划”,5,第二步：,选择所需子模块，点击主窗口中的相应按钮。本题中选用“线性规划”方法。点击按钮弹出如下界面：,点击“新建”按钮,6,输入变量个数,输入约束,条件个数,目标函数,点击“确定”,2,3,7,点击“解决”按钮,2,3,max,8,9,第五步：分析运行结果。,本题中目标函数的最优值是,27500,，,x,1,=50,x,2,=250,。,相差值表示相应,的决策变量的目,标系数需要改进,的数量，使得决,策变量为正值，,当决策变量已为,正数时，相差数,为零。,“,管理运筹学”软件的输出信息分析,10,松弛,/,剩余变量的数值表示还有多少资源没有被使用。,如果为零，则表示与之相对应的资源已经全部用上。,“,管理运筹学”软件的输出信息分析,11,对偶价格表示其对应的资源每增加一个单位，,将增加多少个单位的最优值。,“,管理运筹学”软件的输出信息分析,12,目标函数系数范围表示最优解不变的情况下，,目标函数的决策变量系数的变化范围。,当前值是指当前的最优解中的系数取值。,“,管理运筹学”软件的输出信息分析,13,常数项范围是指约束条件的右端常量。上限值和下限值是指当,约束条件的右端常量在此范围内变化时，与其对应的约束条件,的对偶价格不变。当前值是指现在的取值。,“,管理运筹学”软件的输出信息分析,14,“,管理运筹学”软件的输出信息分析,【,例,2】,用,软件,求下列线性规划的最优解,第一步：,点击,“,开始,”,-,“,程序,”,-,“,管理运筹学,2.0,”,，,弹出主窗口。,15,本题选用“线性规划”,16,第二步：,选择所需子模块，点击主窗口中的相应按钮。本题中选用“线性规划”方法。点击按钮弹出如下界面：,点击“新建”按钮,17,输入变量个数,输入约束,条件个数,目标函数,点击“确定”,2,3,min,18,19,“,管理运筹学,”,软件的输出信息分析,常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。,以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变化的基础上得出的！,“,管理运筹学”软件的输出信息分析,20,“,管理运筹学,”,软件的输出信息分析,2.,当有多个系数变化时，需要进一步讨论。,百分之一百法则：,对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过,100%,时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）。,“,管理运筹学”软件的输出信息分析,21,2,“,管理运筹学,”,软件的输出信息分析,*,允许增加量,=,上限,-,现在值,c,1,的允许增加量为,100-50=50,b,1,的允许增加量为,325-300=25,*,允许减少量,=,现在值,-,下限,c,2,的允许减少量为,100-50=50,b,3,的允许减少量为,250-200=50,*,“,管理运筹学”软件的输出信息分析,22,2,“,管理运筹学,”,软件的输出信息分析,允许增加的百分比,=,增加量,/,允许增加量,*允许减少的百分比,=,减少量,/,允许减少量例：,c,1,变为,74,c,2,变为,78,则,(74-50)/50+(100-78)/50=92%,，故最优解不变。,b,1,变为,315,b,3,变为,240,则,(315-300)/25+(250-240)/50=80%,，故,对偶价格不变（最优解仍是原来几个线性方程的解）,。,“,管理运筹学”软件的输出信息分析,23,2,“,管理运筹学,”,软件的输出信息分析,在使用百分之一百法则进行灵敏度分析时，要注意：,1,）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作,0,；,2,）百分之一百法则是充分条件，但非必要条件；也就是说超过,100并不一定变化；,3,）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。,“,管理运筹学”软件的输出信息分析,24,下面用“管理运筹学”软件来分析第二章的例,2,，其数学模型如下：,目标函数：,Min f=2x,1,+3 x,2,约束条件：,s.t.x,1,+x,2,350,x,1,125,2 x,1,+x,2,600,x,1,x,2,0,2,“,管理运筹学,”,软件的输出信息分析,“,管理运筹学”软件的输出信息分析,25,2,“,管理运筹学,”,软件的输出信息分析,从上图可知，当购进原材料,A 250t,，原料,B 100t,时，购进成本最低，为,800,万元。,“,管理运筹学”软件的输出信息分析,26,在松弛,/,剩余变量栏中，约束条件,2,的值为,125,，它表示对原料,A,的最低需求，即对,A,的剩余变量值为,125,；同理可知约束条件,1,的剩余变量值为,0,；约束条件,3,的松弛变量值为,0.,在对偶价格栏中，约束条件,3,的对偶价格为,1,万元，也就是说如果把加工时数从,600,小时增加到,601,小时，则总成本将得到改进，由,800,万减少到,799,万。也可知约束条件,1,的对偶条件为,-4,万元，也就是说如果把购进原料,A,的下限从,125t,增加到,126t,，那么总成本将加大，由,800,万增加到,804,万。当然如果减少对原料,A,的下限，那么总成本将得到改进。,2,“,管理运筹学,”,软件的输出信息分析,“,管理运筹学”软件的输出信息分析,27,2,“,管理运筹学,”,软件的输出信息分析,在常数项范围一栏中，知道当约束条件,1,的常数项在,300475,范围内变化，且其他约束条件不变时，约束条件,1,的对偶价格不变；,当约束条件,2,的常数项在负无穷到,250,范围内变化，而其他约束条件的常数项不变时，约束条件,2,的对偶价格不变，仍为,0,；,当约束条件,3,的常数项在,475700,内变化，而其他约束条件的常数项不变时，约束条件,3,的对偶价格不变，仍为,1,。,“,管理运筹学”软件的输出信息分析,28,注意：,当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称之为,影子价格,。,在求目标函数最大时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，所以影子价格等于对偶价格；,在求目标函数值最小时，改进的数量就是减少的数量，所以影子价格即为负的对偶价格。,2,“,管理运筹学,”,软件的输出信息分析,“,管理运筹学”软件的输出信息分析,29,2,“,管理运筹学,”,软件的输出信息分析,2.“,管理运筹学”软件可以解决含有,100,个变量,50,个约束方程的线性规划问题，可以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的,L.E.Schrage,开发的,Lindo,计算机软件包的微型计算机版本,Lindo/PC,。,“,管理运筹学”软件的输出信息分析,