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

《运筹学——第3章-线性规划问题的计算机求解ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学——第3章-线性规划问题的计算机求解ppt课件.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第三章第三章 线性规划问题的线性规划问题的 计算机求解计算机求解“管理运筹学管理运筹学”的软件包的软件包 3.1“管理运筹学管理运筹学”软件的操作方法软件的操作方法下面用运筹学软件下面用运筹学软件2.0来解决例来解决例1的线性规划问题。的线性规划问题。 从开始从开始程序程序管理运筹学管理运筹学2.0，这样就打开此软件，如下，这样就打开此软件，如下图：图： 注意！下面以第二章的例下面以第二章的例1为例说明为例说明此软件的用法此软件的用法 max Z=50 x1+100 x2， 约束条件：约束条件：x1+x2300， 2 x1+x2400， x2250, x10, x20.选择了线性规划后，就出

2、现的界面，然后点选择了线性规划后，就出现的界面，然后点新建。得到如下对话框：新建。得到如下对话框：样？就这 从上面变量、最优解、相差值一栏中，知道例从上面变量、最优解、相差值一栏中，知道例1的最优解为生的最优解为生产产产品产品50单位；生产单位；生产产品产品250单位。单位。对例对例1来说由于来说由于x1=50，x2=250，都是正值，所以它们的相差值都为零。如果都是正值，所以它们的相差值都为零。如果x1的值为的值为0；x1 的相差值为的相差值为20；则就知道，只有当产品；则就知道，只有当产品I 的利润再提高的利润再提高20元，即元，即达到达到50+20=70元时（这里的元时（这里的50是表示

3、是表示X1的利润，不是的利润，不是X1的最优的最优解），解）， 产品产品I 才可能生产，即才可能生产，即x1才可能大于零。才可能大于零。3.2软件输出信息分析软件输出信息分析 满足约束条件：满足约束条件：x1+x2300，（，（台时数）台时数） 2 x1+x2400，（，（原料原料A） x2250, （原料原料B） 在约束条件、松弛剩余变量、对偶价格这栏中，可在约束条件、松弛剩余变量、对偶价格这栏中，可知设备的台时数全部使用完，每个设备台时的对偶价格知设备的台时数全部使用完，每个设备台时的对偶价格为为50元，即增加了一个台时数就可使总利润增加元，即增加了一个台时数就可使总利润增加50元；元；原

4、料原料A还有还有50千克没有使用，原料千克没有使用，原料A的对偶价格当然为零，的对偶价格当然为零，即增加即增加1千克千克A原料不会使总利润有所增加；原料原料不会使总利润有所增加；原料B全部全部使用完，原料使用完，原料B的对偶价格为的对偶价格为50元，即增加一千克原料元，即增加一千克原料B就可使总利润增加就可使总利润增加50元。元。 在目标函数系数范围一栏中，在目标函数系数范围一栏中，例如当例如当c1= 80时，因为时，因为080100，在，在x1的系数变化范的系数变化范围内，所以其最优解不变（此时要固定围内，所以其最优解不变（此时要固定c2=100)，也即当也即当x1=50，x2=250时，有

5、最大利润。当然由于产品时，有最大利润。当然由于产品的单位利润由的单位利润由50变为变为80了，其最大利润也增加了了，其最大利润也增加了(最优值变了最优值变了)， 变为变为8050 +100250 =29000(元元)。 但是如果但是如果c1=110元时，由于元时，由于110100，所以原来的最优解就可，所以原来的最优解就可能不再是最优解了。能不再是最优解了。 同样从上图可知，当同样从上图可知，当c2 在在50与与之间变化时（此时要固定之间变化时（此时要固定c1=50) ，原来的最优解依然是其最优解。，原来的最优解依然是其最优解。 所谓当前值是指约束条件右边值的现在值，可知所谓当前值是指约束条件

6、右边值的现在值，可知b1=300；b2=400，b3=250。从可由对偶价格判断增加某约束条件的常数项值是否从可由对偶价格判断增加某约束条件的常数项值是否能使目标函数值变得更好能使目标函数值变得更好（前提条件是其它常数项保持不变）（前提条件是其它常数项保持不变）。 当设备台时数在当设备台时数在250325的范围内，其对偶价格都为的范围内，其对偶价格都为50元，说元，说明增加设备台时数可使目标函数值变大，每增加明增加设备台时数可使目标函数值变大，每增加1个台时数可增加个台时数可增加利润利润50元。当原料元。当原料A的公斤数在的公斤数在350到到+范围内，其对偶价格都为范围内，其对偶价格都为零；增

7、加原料零；增加原料A对目标函数值无影响。当原料对目标函数值无影响。当原料B的千克数在的千克数在200到到300的范围内，其对偶价格都为的范围内，其对偶价格都为50元。例如设备台时数和原料元。例如设备台时数和原料A的的数量不变，即数量不变，即b1=300；b2=400，原料，原料B变为变为280千克，由于千克，由于200280300，原料，原料B的对偶价格仍为的对偶价格仍为50元，故新的最大利润值应元，故新的最大利润值应为：为： 27500+(280-250)50=29000元。这里元。这里50是对偶价格。是对偶价格。 先以例先以例1为例看一看如何用百分之一百法为例看一看如何用百分之一百法则对两

8、个目标函数系数同时变化进行灵敏度则对两个目标函数系数同时变化进行灵敏度分析。例分析。例1中原来每件中原来每件产品和产品和产品的利润产品的利润分别为分别为50元和元和100元，现在由于市场情况的变元，现在由于市场情况的变化每件化每件产品和产品和产品的利润分别变为产品的利润分别变为74元元和和78元，最优解发生变化吗元，最优解发生变化吗? 为了解决这个问题我们首先来定义为了解决这个问题我们首先来定义“允许允许增加值增加值”和和“允许减少值允许减少值”这两个术语，对这两个术语，对一个目标函数的决策变量系数，一个目标函数的决策变量系数，。 在上题中在上题中C1 的允许增加百分比与的允许增加百分比与C2

9、 的允许减的允许减少百分比之和为少百分比之和为92不超过不超过100，所以当每件产，所以当每件产品品利润从利润从50元增加到元增加到74元，每件产品元，每件产品利润从利润从100元减少到元减少到78元时，此线性规划最优解仍然为元时，此线性规划最优解仍然为产品生产产品生产50件，件， 产品生产产品生产250件件(即即x1= 50，x2=250)，此时有最大利润为，此时有最大利润为: 74 50+78 250=370019500=23200(元元)。 注意最大利润已变。注意最大利润已变。 同样有约束条件右边常数值的百分之一百法同样有约束条件右边常数值的百分之一百法则：对于所有变化的约束条件右边常数

10、值，当其则：对于所有变化的约束条件右边常数值，当其所有允许增加百分比和允许减少百分比之和不超所有允许增加百分比和允许减少百分比之和不超过百分之一百时，则其对偶价格不变。过百分之一百时，则其对偶价格不变。 其中其中bj 的允许增加的允许增加(减少减少)百分比的定义同百分比的定义同Ci 的允许的允许增加增加(减少减少)百分比一样：百分比一样：为为bj 的增加量的增加量(减少量减少量)除以除以bj的允许增加量的允许增加量(减少量减少量)的值。的值。并不难 仍以例仍以例1为例来说明如何用约束条件右边常数值的为例来说明如何用约束条件右边常数值的百分之一百法则进行灵敏度分析。不妨设设备台时百分之一百法则进

11、行灵敏度分析。不妨设设备台时数从数从300台时增加为台时增加为315台时，而原料台时，而原料A从从400千克减千克减少到少到390千克，原料千克，原料B从从250千克减少到千克减少到240千克，这千克，这样可以得到它们的允许增加样可以得到它们的允许增加(减少减少)百分比。因为：百分比。因为：约束约束 下限下限 当前值当前值 上限上限 1 250 300 325 2 350 400 无上限无上限 3 200 250 300设备台时数：设备台时数： (315-300)/(325-300)=15/25=60，原料原料A： (400-390)/(400-350)=10/50=20，原料原料B： (25

12、0-240)/(250-200)=10/50=20。 所以它们的允许增加百分比与允许减少所以它们的允许增加百分比与允许减少百分比之和为百分比之和为60+20+20=100，从，从以上约束条件右边常数值的百分之一百法则以上约束条件右边常数值的百分之一百法则可知此线性规划的对偶价格不变。因为设备可知此线性规划的对偶价格不变。因为设备台时数从台时数从300台时增加为台时增加为315台时，而原料台时，而原料A从从400千克减少到千克减少到390千克，原料千克，原料B从从250千千克减少到克减少到240千克，所以从对偶价格可知千克，所以从对偶价格可知5015+0（-10）+50（-10）=250(元元)

13、，则最大利润增加了则最大利润增加了250元，为元，为27750元。元。 在使用百分之一百的法则进行灵敏度分在使用百分之一百的法则进行灵敏度分析时，要注意以下四点：析时，要注意以下四点： 1)、当允许增加量、当允许增加量(减少量减少量)为无穷大时，则对于任一为无穷大时，则对于任一个增加量个增加量(减少量减少量)，其允许增加，其允许增加(减少减少)百分比都看成零。百分比都看成零。 例如，在表例如，在表3- 4中，约束条件中，约束条件2的常数项变动范围为的常数项变动范围为350至至+, 如果原料如果原料A从从400增加到增加到410，则相当于，则相当于 （410- 400）/（无穷大（无穷大- 40

14、0)=0. 2)、当允许增加量、当允许增加量(减少量减少量)为为0时，时，则对于任一个增加量则对于任一个增加量(减少量减少量)，其，其允许增加允许增加(减少减少)百分比都看成无穷百分比都看成无穷大（相当于该变量不能增加或减少）。大（相当于该变量不能增加或减少）。 要打开思路!3)、百分之一百法则是判断最优解或对偶价、百分之一百法则是判断最优解或对偶价格变不变的格变不变的充分条件充分条件，但，但不是必要条件不是必要条件，也，也就是说当其允许增加和减少百分比之和不超就是说当其允许增加和减少百分比之和不超过过100时，其最优解或对偶价格不变，但时，其最优解或对偶价格不变，但是当其允许增加和减少百分比

15、之和超过是当其允许增加和减少百分比之和超过100时，我们并不知道其最优解或对偶价格变时，我们并不知道其最优解或对偶价格变还是不变。还是不变。 4)、百分之一百法则不能应用于目标函数、百分之一百法则不能应用于目标函数决决策变量系数策变量系数和约束条件和约束条件右边常数值右边常数值同时变化同时变化的情况，在这种情况下，只有重新求解。的情况，在这种情况下，只有重新求解。 下面把例下面把例2输入计算机来分析此线性规划的输入计算机来分析此线性规划的计算机输出，例计算机输出，例2的数学模型如下：的数学模型如下： 目标函数：目标函数：min 2x1+3x2 约束条件：约束条件：x1+x2350， x1125

16、， 2x1+x2600 x10， x20上机计算得到如下结果：上机计算得到如下结果： 从上面结果知道，当购进从上面结果知道，当购进A原料原料250吨吨(X1=250)，B原料原料100吨吨(X2=100)时，使得购进成本最低为时，使得购进成本最低为800万万元。在松弛剩余栏中，约束条件的值为元。在松弛剩余栏中，约束条件的值为125，约，约束条件表示对原料束条件表示对原料A的最低需求，由于此约束为大的最低需求，由于此约束为大于等于，这样可知原料于等于，这样可知原料A的剩余变量值为的剩余变量值为125（因为（因为x1=250）。）。同样可知约束条件（对所有原料的总需同样可知约束条件（对所有原料的总

17、需要量）的剩余变量值为零，约束条件（加工时数的要量）的剩余变量值为零，约束条件（加工时数的限制）的松弛变量值为零。限制）的松弛变量值为零。约束约束 松弛剩余变量松弛剩余变量 对偶价格对偶价格 1 0 - 4 2 125 0 3 0 1 在对偶价格一栏中，可知约束条件的对偶价格为在对偶价格一栏中，可知约束条件的对偶价格为- 4万元，也就是说如果把购进原料万元，也就是说如果把购进原料A+原料原料B的下限从的下限从350吨增加到吨增加到351吨，那么总成本将加大（因为对偶价格为吨，那么总成本将加大（因为对偶价格为负值），由负值），由800万元增加到万元增加到800+4=804(万元万元)了。当然如了

18、。当然如果减少对原料果减少对原料A+原料原料B的下限，如把原料的下限，如把原料A+原料原料B的下的下限从限从350吨减少到吨减少到349吨，那么总成本将得到改进，由吨，那么总成本将得到改进，由800万元减少到万元减少到800- 4=796万元了。万元了。 可知约束条件（加工时数）的对偶价格为可知约束条件（加工时数）的对偶价格为1万元，万元，也就是说如果把加工时数从也就是说如果把加工时数从600小时增加到小时增加到601小时，则小时，则总成本将得到改进总成本将得到改进(因为对偶价格为正值因为对偶价格为正值)，由，由800万元万元减少为减少为800-1=799万元了。万元了。 目标函数系数范围：目

19、标函数系数范围： 变量变量 下限下限 当前值当前值 上限上限 X1 无下限无下限 2 3 X2 2 3 无上限无上限 在目标函数系数范围这一栏中，知道当在目标函数系数范围这一栏中，知道当C2(目标函数中目标函数中X2的系数的系数)不变，不变，C1（目标函目标函数中数中X1的系数）在的系数）在-到到3范围内变化时，最范围内变化时，最优解不变；当优解不变；当C1不变时，不变时，C2在在2到到+范围内范围内变化时，最优解不变。变化时，最优解不变。 常数项范围：常数项范围： 约束约束 下限下限 当前值当前值 上限上限 1 300 350 475 2 无下限无下限 125 250 3 475 600 7

20、00 在约束条件右边值范围一栏中，知道当约束条件在约束条件右边值范围一栏中，知道当约束条件的右边值（原料的右边值（原料A和原料和原料B的总量的下限）在的总量的下限）在300到到475范围内变化，而其他约束条件的右边值不变时，范围内变化，而其他约束条件的右边值不变时，则约束条件的对偶价格不变仍为则约束条件的对偶价格不变仍为 - 4。 当约束条件的右边值（原料当约束条件的右边值（原料A的需求量的下限）的需求量的下限）在在0 到到250范围内变化时，而其他约束条件的右边值不范围内变化时，而其他约束条件的右边值不变时，则约束条件的对偶价格不变，仍为变时，则约束条件的对偶价格不变，仍为0。当约。当约束条

21、件的右边值（加工时数的上限）在束条件的右边值（加工时数的上限）在475到到700范范围内变化，而其他约束条件的右边值不变时，则约束围内变化，而其他约束条件的右边值不变时，则约束条件的对偶价格不变仍为条件的对偶价格不变仍为1。练习练习 P37 ,4 有些书上常常使用有些书上常常使用影子价格影子价格这个术语，当约束这个术语，当约束条件右边值增加一个单位时最优目标函数值增加条件右边值增加一个单位时最优目标函数值增加的数量称之为的数量称之为影子价格影子价格，对照对偶价格的定义：，对照对偶价格的定义：当约束条件右边值增加一个单位时最优目标函数当约束条件右边值增加一个单位时最优目标函数值改进的数量。可知当求目标函数的值改进的数量。可知当求目标函数的最大值时最大值时，增加的数量就是改进的数量，所以增加的数量就是改进的数量，所以影子价格就等影子价格就等于对偶价格于对偶价格。而当求目标函数的。而当求目标函数的最小值时最小值时，改进，改进的数量应该是减少的数量。所以的数量应该是减少的数量。所以影子价格即为负影子价格即为负的对偶价格的对偶价格。