第3章 线性规划问题的计算机求解

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