第三章--线性规划问题的计算机求解优秀PPT.ppt

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

1、管管 理理 运运 筹筹 学学第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解1“管理运筹学”软件的操作方法2“管理运筹学”软件的输出信息分析1管管 理理 运运 筹筹 学学第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解 随书软件为“管理运筹学”2.0版（Window版），是1.0版（DOS版）的升级版。它包括：线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预料问题和层次分析法，共15个子模块。2管管 理理 运运 筹筹 学学例例3.1.目标

2、函数：Max z=50 x1+100 x2 约束条件：s.t.x1+x2 300 (A)2 x1+x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)3.13.1“管理运筹学管理运筹学”软件的操作方法软件的操作方法1.1.软件运用演示：（演示例软件运用演示：（演示例1 1）第一步：点击第一步：点击“起先起先”-“”-“程序程序”-“”-“管理运筹学管理运筹学2.0”2.0”，弹出主窗口。，弹出主窗口。3管管 理理 运运 筹筹 学学3.13.1“管理运筹学管理运筹学”软件的操作方法软件的操作方法其次步：选择所需子模块，点击主窗口中的相应按钮。本题中选用其次步：选择所需子模块，

3、点击主窗口中的相应按钮。本题中选用“线性规划线性规划”方方法。点击按钮弹出如下界面：法。点击按钮弹出如下界面：4管管 理理 运运 筹筹 学学3.13.1“管理运筹学管理运筹学”软件的操作方法软件的操作方法第三步：点击第三步：点击“新建新建”按钮，输入数据。本题中共有按钮，输入数据。本题中共有2个变量，个变量，4个约束条件，目标个约束条件，目标函函数取数取MAX。点击。点击“确定确定”后，在表中输入后，在表中输入Cj,bi和和aij等值，并确定变量的正负约束。等值，并确定变量的正负约束。输入数值后的界面如下。输入数值后的界面如下。5管管 理理 运运 筹筹 学学3.13.1“管理运筹学管理运筹学”

4、软件的操作方法软件的操作方法第四步：点击第四步：点击“解决解决”按钮，得出计算结果。本题的运行结果界面如下。按钮，得出计算结果。本题的运行结果界面如下。6管管 理理 运运 筹筹 学学3.23.2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析第五步：分析运行结果。本题中目标函数的最优值是27500，x1=50,x2=250。相差值表示相应的决策变量的目标系数须要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。松弛/剩余变量的数值表示还有多少资源没有被运用。假如为零，则表示与之相对应的资源已经全部用上。对偶价格表示其对应的资源每增加一个单位，将增加多少个单位的最优值

5、。目标函数系数范围表示最优解不变的状况下，目标函数的决策变量系数的变更范围。当前值是指当前的最优解中的系数取值。常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变更时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变更的基础上得出的！7管管 理理 运运 筹筹 学学3.23.2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析一、软件输出结果分析一、软件输出结果分析 1.最优值信息最优值信息 2.决策变量信息的分析决策变量信息的分析 1）给出最优解信息）

6、给出最优解信息 2）相差值供应的决策信息）相差值供应的决策信息 相差值的含义：指相应的决策变量的目标函数须要改进的数量，使得相差值的含义：指相应的决策变量的目标函数须要改进的数量，使得该决策变量有可能取正数值，当决策变量已取正数值时则相差值即为该决策变量有可能取正数值，当决策变量已取正数值时则相差值即为零。零。3.约束条件信息约束条件信息 1）松弛）松弛/剩余变量信息剩余变量信息 2）对偶价格信息）对偶价格信息 4.目标函数系数目标函数系数ci的信息的信息 给出了使最优解保持不变的决策变量系数给出了使最优解保持不变的决策变量系数ci的变更范围。的变更范围。5.常数项常数项bi的信息的信息 给出

7、了使约束条件的对偶价格保持不变的相应的给出了使约束条件的对偶价格保持不变的相应的bi的变更范围。的变更范围。8管管 理理 运运 筹筹 学学3.23.2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析 留意：留意：以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变更的基础上得出的！是在其他系数值不变，只有一个系数变更的基础上得出的！假如两个或两个系数同时发生变更，如何推断最优解或者对偶价格假如两个或两个系数同时发生变更，如何推断最优解或者对偶价格是否发生变更呢。下面我们介绍两个或更多系

8、数发生变更的灵敏度分是否发生变更呢。下面我们介绍两个或更多系数发生变更的灵敏度分析析百分之一百法则。百分之一百法则。9管管 理理 运运 筹筹 学学3.23.2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析二、多个系数变更时的灵敏度分析二、多个系数变更时的灵敏度分析 百分之一百法则：对于全部变更的目标函数决策系数（约束条百分之一百法则：对于全部变更的目标函数决策系数（约束条件右边常数值），当其全部允许增加的百分比与允许削减的百分比件右边常数值），当其全部允许增加的百分比与允许削减的百分比之和不超过之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原时，最优解不变（对偶价格不

9、变，最优解仍是原来几个线性方程的解）。来几个线性方程的解）。*允许增加量允许增加量=上限上限-现在值现在值 c1 的允许增加量为的允许增加量为 100-50=50 b1 的允许增加量为的允许增加量为 325-300=25 *允许削减量允许削减量=现在值现在值-下限下限 c2 的允许削减量为的允许削减量为 100-50=50 b3 的允许削减量为的允许削减量为 250-200=50 *允许增加的百分比允许增加的百分比=增加量增加量/允许增加量允许增加量 *允许削减的百分比允许削减的百分比=削减量削减量/允许削减量允许削减量 10管管 理理 运运 筹筹 学学3.23.2“管理运筹学管理运筹学”软件

10、的输出信息分软件的输出信息分析析 例例3.2：c1 变为变为 74,c2 变为变为 78,则则 (74-50)/50+(100-78)/50=92%，故最优解不，故最优解不变。变。b1 变为变为 315,b3 变为变为 240,则则 (315-50)/25+(250-240)/50=80%，故对偶价，故对偶价格不变（最优解仍是原来几个线性方程的解）。格不变（最优解仍是原来几个线性方程的解）。在运用百分之一百法则进行灵敏度分析时，要留意：在运用百分之一百法则进行灵敏度分析时，要留意：1）当允许增加量（允许削减量）为无穷大时，则对随意增加量（削减量），其允许增加（削减）百分比均看作）当允许增加量（

11、允许削减量）为无穷大时，则对随意增加量（削减量），其允许增加（削减）百分比均看作0；2）百分之一百法则是充分条件，但非必要条件；也就是说超过）百分之一百法则是充分条件，但非必要条件；也就是说超过100%并不确定变更；并不确定变更；3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变更的状况。这种状况下，只有重新求解。）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变更的状况。这种状况下，只有重新求解。11管管 理理 运运 筹筹 学学例3.3 目标函数：Min f=2x1+3 x2 s.t.x1+x2 350 x1 125 2 x1+x2 600 x1 ,

12、x2 0 从上图可知，当购进原材料A 250t，原料B 100t时，购进成本最低，为800万元。3.23.2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析12管管 理理 运运 筹筹 学学在松弛/剩余变量栏中，约束条件2的值为125，它表示对原料A的最低需求，即对A的剩余变量值为125；同理可知约束条件1的剩余变量值为0；约束条件3的松弛变量值为0。在对偶价格栏中，约束条件3的对偶价格为1万元，也就是说假如把加工时数从600小时增加到601小时，则总成本将得到改进，由800万削减到799万。也可知约束条件1的对偶条件为-4万元，也就是说假如把购进原料A和B的下限从350t增加到35

13、1t，那么总成本将加大，由800万增加到804万。当然假如削减对原料A和B的下限，那么总成本将得到改进。在常数项范围一栏中，知道当约束条件1的常数项在300475范围内变更，且其他约束条件不变时，约束条件1的对偶价格不变；当约束条件2的常数项在负无穷到250范围内变更，而其他约束条件的常数项不变时，约束条件2的对偶价格不变，仍为0；当约束条件3的常数项在475700内变更，而其他约束条件的常数项不变时，约束条件3的对偶价格不变，仍为1。3.23.2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析13管管 理理 运运 筹筹 学学例3.4 已知如下线性规划模型：用“管理运筹学”软件求解，得到如下结果（见下图1所示）。回答下列问题：（1）最优解及最优目标函数值是多少；（2）资源的对偶价格各为多少，并说明对偶价格的含义；（3）为了使目标函数值增加最多，让你选择一个约束条件，将它的常数项增加一个单位，你将选择哪一个约束条件？这时目标函数值将是多少？（4）对的目标函数系数进行灵敏度分析；（5）对第2个约束条件的右端项进行灵敏度分析；（6）结合本题的结果说明“相差值”的含义。3.23.2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析14管管 理理 运运 筹筹 学学3.23.2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析15