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

1、第三章 线性规划问题的 计算机求解,如何求解？,“管理运筹学”的软件包,本章将介绍如何使用计算机软件包求解线性规划问题。 解决线性规划问题的软件包分两种，一种是大规模的软件包，它可以用来解决复杂的包含数千个决策变量和数千个约束条件的大型的线性规划的问题，重点掌握国内外常用软件：由芝加哥大学LinusESchrage开发的lindo6.1软件，此软件包可解决32000个变量(3200整型变量）16000个约束方程的运筹学问题。 另一种是用于微机的软件包，它们有很好的界面，使用方便，由科研机构和小软件公司为解决包含数百个决策变量的线性规划问题而开发的。本章介绍的是与本书配套的名为“管理运筹学”2.

2、0软件包就是属于这种软件，此软件包可解决100个变量50个约束方程的管理运筹学问题。 本章的重点放在如何读懂“管理运筹学”软件包的计算机输出结果关于线性规划问题的求解和灵敏度分析的信息，解决工商管理中的实际问题。,3.1“管理运筹学”软件的操作方法下面用运筹学软件2.0来解决例1的线性规划问题。,从开始程序管理运筹学2.0，这样就打开此软件，如下图：,然后就根据需要选择运筹学的各个分枝,1输入的系数可以是整数、小数， 但不能是分数，要把分数先化为小数再输入。 2输入前先要合并同类项。 3、此软件的一个最大缺点是变量只有一组X，不能有Y和Z等，而且下标不能是二维下标如：X12是错的（看作是一维）

3、。还有X1A等也是错误的，其次模型的修改比较麻烦。,注,意！,下面以第二章的例1为例说明此软件的用法,max Z=50 x1+100 x2， 约束条件：x1+x2300， 2 x1+x2400， x2250, x10, x20. 选择了线性规划后，就出现的界面，然后点新建。得到如下对话框：,然后新建清零，下面就可以输入模型了。,先输入变量个数、约束个数和MAX或Min，然后点确定后，才能输入模型。,输入目标函数系数,一般地变量的非负性不必修改。,在这输入约束条件，在输入约束条件时注意清0，还要注意不等号的方向。,输完模型后就可以选择要进行的操作，如：保存、解决（求解）等。下面是例1的输入结果。

4、,输完模型后，苦要修改模型点这里,样？,就,这,解决后得到如下结果。,如果选择保存，就弹出保存路径的对话框。,输入文件名，然后点保存即可，以后可以点打开调出模型。,从上面变量、最优解、相差值一栏中，知道例1的最优解为生产产品50单位；生产产品250单位。相差值的数值表示相应的决策变量的目标系数需要改进的数量，使得该决策变量有可能取正数值，一般地，当决策变量已取正数值时则相差值为零。如果决策变量取0值，则相差值可能不为0。对例1来说由于x1=50，x2=250，都是正值，所以它们的相差值都为零。如果x1的值为0；x1 的相差值为20；则就知道，只有当产品I 的利润再提高20元，即达到50+20=

5、70元时（这里的50是表示X1的利润，不是X1的最优解）， 产品I 才可能生产，即x1才可能大于零。对于目标函数求最小值的线性规划问题，那么所谓的改进就应该使其对应的决策变量的系数减少其相差值。这在以后还要说明。,如何读懂输出结果？,3.2软件输出信息分析,喂！相差值是什么意思？,我知道：如果决策变量取正数值，则相差值一般为零。则此时目标函数的系数无法再改变使目标函数值变得更好。 如果决策变量取0值，则相差值可能不为0（比如说相差值为正a，也有可能为0)。则此时目标函数的系数可以在原来基础上增加a（而当目标函数是求最小值时，减少a)，则可能才能使此决策变量变为非零（即生产该种产品），才有可能使

6、目标函数值变得更好。 也可以这样理解：在相差值内,价值系数增加就不会影响原来的最优基，但当价值系数增加大于等于相差值时,最优基就会发生变化。,满足约束条件：x1+x2300，（台时数） 2 x1+x2400，（原料A） x2250, （原料B） 在约束条件、松弛剩余变量、对偶价格这栏中，可知设备的台时数全部使用完，每个设备台时的对偶价格为50元，即增加了一个台时数就可使总利润增加50元；原料A还有50千克没有使用，原料A的对偶价格当然为零，即增加1千克A原料不会使总利润有所增加；原料B全部使用完，原料B的对偶价格为50元，即增加一千克原料B就可使总利润增加50元。,设备 原料A 原料B,在目标

7、函数系数范围一栏中，所谓的当前值是指在目标函数中决策变量的当前系数值。如x1的系数值为50，x2的系数值为100。所谓的上限与下限值是指目标函数的决策变量的系数（其它决策变量的系数固定在当前值）在此范围内变化时，其线性规划的最优解不变。例如当c1= 80时，因为080100，在x1的系数变化范围内，所以其最优解不变（此时要固定c2=100)，也即当x1=50，x2=250时，有最大利润。当然由于产品的单位利润由50变为80了，其最大利润也增加了(最优值变了)， 变为8050 +100250 =29000(元)。 但是如果c1=110元时，由于110100，所以原来的最优解就可能不再是最优解了。

8、 同样从上图可知，当c2 在50与之间变化时（此时要固定c1=50) ，原来的最优解依然是其最优解。,所谓当前值是指约束条件右边值的现在值，可知b1=300；b2=400，b3=250。所谓上限值与下限值是指当约束条件的右边值在此范围内变化时，则与其对应的约束条件的对偶价格不变，不能保证最优解不变。从可由对偶价格判断增加某约束条件的常数项值是否能使目标函数值变得更好（前提条件是其它常数项保持不变）。 当设备台时数在250325的范围内，其对偶价格都为50元，说明增加设备台时数可使目标函数值变大，每增加1个台时数可增加利润50元。当原料A的公斤数在350到+范围内，其对偶价格都为零；增加原料A对

9、目标函数值无影响。当原料B的千克数在200到300的范围内，其对偶价格都为50元。例如设备台时数和原料A的数量不变，即b1=300；b2=400，原料B变为280千克，由于200280300，原料B的对偶价格仍为50元，故新的最大利润值应为： 27500+(280-250)50=29000元。这里50是对偶价格。,设备 原料A 原料B,如果所有的右端常数项同时在变，对偶价格是否变啊？,以上关于目标函数系数及约束条件右边值的灵敏度分析都是基于这样一个重要假设：只有一个系数在变化，而其他的系数值保持不变。所有以上的目标函数系数及约束条件右边值的变化范围只适合于单个系数变化的情况。如果两个或更多或者

10、说所有约束条件右边常数项同时变动，就不能用上面方法来判断对偶价格是否变了。要用下面方法来判断。,百分之一百法则：,先以例1为例看一看如何用百分之一百法则对两个目标函数系数同时变化进行灵敏度分析。例1中原来每件产品和产品的利润分别为50元和100元，现在由于市场情况的变化每件产品和产品的利润分别变为74元和78元，最优解发生变化吗? 为了解决这个问题我们首先来定义“允许增加值”和“允许减少值”这两个术语，对一个目标函数的决策变量系数，所谓允许增加值是该系数在上限范围内的最大增加量，所谓的允许减少量是该系数在下限范围内的最大的减少量。,这样可以计算出C1的允许增加量百分比为： (74-50)50=

11、48；C2 的允许减少百分比为 (100-78)50=44，C1允许增加百分比与C2的允许减 少百分比之和为：48+44=92。,变量 下限 当前值 上限 x1 0 50 100 x2 50 100 无上限 从上面可知目标函数中X1的系数的上限为100，故C1允许增加量为： 上限-现在值=100-50=50；而X2的下限为50，故C2的允许减少量为： 现在值-下限=100-50=50。 定义Ci 的允许增加(减少)百分比为：Ci 的增加量(减少量)除以Ci 的允许增加量(允许减少量)的值。,目标函数决策变量系数的百分之一百法则：对于所有变化的目标函数决策变量系数，当其所有允许增加百分比和允许减

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

13、比的定义同Ci 的允许增加(减少)百分比一样：为bj 的增加量(减少量)除以bj的允许增加量(减少量)的值。,仍以例1为例来说明如何用约束条件右边常数值的百分之一百法则进行灵敏度分析。不妨设设备台时数从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=2

14、0， 原料B： (250-240)/(250-200)=10/50=20。,所以它们的允许增加百分比与允许减少百分比之和为60+20+20=100，从以上约束条件右边常数值的百分之一百法则可知此线性规划的对偶价格不变。因为设备台时数从300台时增加为315台时，而原料A从400千克减少到390千克，原料B从250千克减少到240千克，所以从对偶价格可知5015+0（-10）+50（-10）=250(元)，则最大利润增加了250元，为27750元。,在使用百分之一百的法则进行灵敏度分析时，要注意以下四点：,1)、当允许增加量(减少量)为无穷大时，则对于任一个增加量(减少量)，其允许增加(减少)百

15、分比都看成零。 例如，在表3- 4中，约束条件2的常数项变动范围为350至+, 如果原料A从400增加到410，则相当于 （410- 400）/（无穷大- 400)=0. 2)、当允许增加量(减少量)为0时， 则对于任一个增加量(减少量)，其 允许增加(减少)百分比都看成无穷 大（相当于该变量不能增加或减少）。,3)、百分之一百法则是判断最优解或对偶价格变不变的充分条件，但不是必要条件，也就是说当其允许增加和减少百分比之和不超过100时，其最优解或对偶价格不变，但是当其允许增加和减少百分比之和超过100时，我们并不知道其最优解或对偶价格变还是不变。 4)、百分之一百法则不能应用于目标函数决策变

16、量系数和约束条件右边常数值同时变化的情况，在这种情况下，只有重新求解。,下面把例2输入计算机来分析此线性规划的计算机输出，例2的数学模型如下：,目标函数：min 2x1+3x2 约束条件：x1+x2350， x1125， 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(万元)了。当然如果减少对原料A+原料B的下限，如把原料A+原料B的下限从350吨减少到349吨，那么总成本将得到改进，由800万元减少到800- 4=796万元了。 可知约束条件（加工时数）的对偶价格为1万元，也就是说如果把加工时数从600小时增加到601小时，则总成本将得到

18、改进(因为对偶价格为正值)，由800万元减少为800-1=799万元了。,目标函数系数范围： 变量 下限 当前值 上限 X1 无下限 2 3 X2 2 3 无上限,在目标函数系数范围这一栏中，知道当C2(目标函数中X2的系数)不变，C1（目标函数中X1的系数）在-到3范围内变化时，最优解不变；当C1不变时，C2在2到+范围内变化时，最优解不变。,常数项范围： 约束 下限 当前值 上限 1 300 350 475 2 无下限 125 250 3 475 600 700 在约束条件右边值范围一栏中，知道当约束条件的右边值（原料A和原料B的总量的下限）在300到475范围内变化，而其他约束条件的右边值不变时，则约束条件的对偶价格不变仍为 - 4。 当约束条件的右边值（原料A的需求量的下限）在0 到250范围内变化时，而其他约束条件的右边值