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