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

《运筹学——第3章-线性规划问题的计算机求解课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、有一组X，不能有Y和Z等，而且下标不能是二维下标如：X12是错的（看作是一维）。还有X1A等也是错误的，其次模型的修改比较麻烦。注意！下面以第二章的例1为例说明此软件的用法maxZ=50x1+100x2，约束条件：x1+x2≤300，2x1+x2≤400，x2≤250,x1≥0,x2≥0.选择了线性规划后，就出现的界面，然后点新建。得到如下对话框：然后新建清零，下面就可以输入模型了。先输入变量个数、约束个数和MAX或Min，然后点确定后，才能输入模型。输入目标函数系数一般地变量的非负性不必修改。在这输入约束条件，在输入约束条件时注意清0，还要注意不等

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

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

6、可能为0)。则此时目标函数的系数可以在原来基础上增加a（而当目标函数是求最小值时，减少a)，则可能才能使此决策变量变为非零（即生产该种产品），才有可能使目标函数值变得更好。也可以这样理解：在相差值内,价值系数增加就不会影响原来的最优基，但当价值系数增加大于等于相差值时,最优基就会发生变化。满足约束条件：x1+x2≤300，（台时数）2x1+x2≤400，（原料A）x2≤250,（原料B）在约束条件、松弛／剩余变量、对偶价格这栏中，可知设备的台时数全部使用完，每个设备台时的对偶价格为50元，即增加了一个台时数就可使总利润增加50元；原料A还有50千克没

7、有使用，原料A的对偶价格当然为零，即增加1千克A原料不会使总利润有所增加；原料B全部使用完，原料B的对偶价格为50元，即增加一千克原料B就可使总利润增加50元。设备原料A原料B在目标函数系数范围一栏中，所谓的当前值是指在目标函数中决策变量的当前系数值。如x1的系数值为50，x2的系数值为100。所谓的上限与下限值是指目标函数的决策变量的系数（其它决策变量的系数固定在当前值）在此范围内变化时，其线性规划的最优解不变。例如当c1=80时，因为0≤80≤100，在x1的系数变化范围内，所以其最优解不变（此时要固定c2=100)，也即当x1=50，x2=25

8、0时，有最大利润。当然由于产品Ⅰ的单位利润由50变为80了，其最大利润也增加了(最优值变了)，变为80×50