第二章 线性规划图解法

1、管理运筹学第二章第二章 线性规划图解法线性规划图解法第二章线性规划的图解法线性规划的图解法 线性规划是运筹学一个重要分支管理上的典型应用：典型线性规划应用典型线性规划应用应用场景应用场景合理利用线材问题用料最少配料问题获利最大投资问题投资回报最大的方案产品生产计划合理利用人力、物力、财力等使获利最大劳动力安排用最少的劳动力满足需要运输问题总运费最少第二章线性规划的图解法线性规划的图解法线性规划的组成：线性规划的组成1目标函数：MIN/MAX2约束条件：限制条件3决策变量：可控因素线性规划问题的提出线性规划的图解法图解法的灵敏度分析本章内容本章内容123 1线性规划问题的提出线性规划问题的提出例

2、1.1.某工厂在计划期内要安排、两种产品的生产，生产单位产品所需的设备台时及 A、B 两种原材料的消耗以及资源的限制，如下表所示。问：工厂应分别生产多少单位、产品才能使工厂获利最多？资源资源产品产品产品产品资源限制资源限制设备11300台时原料A21400kg原料B01250kg单位产品获利（元）50100 1线性规划问题的提出线性规划问题的提出约束条件：资源资源产品产品 产品产品资源限资源限制制设备11300台时原料A21400kg原料B01250kg单位产品获利（元）50100 1线性规划问题的提出线性规划问题的提出建模过程步骤步骤建立线性规划模型建立线性规划模型1在什么条件下追求什么目标

3、2定义决策变量表，每组 代表一个方案3用决策变量的线性函数形式写出目标函数4必须遵循的约束条件 1线性规划问题的提出线性规划问题的提出问题的提出图解法图解法的灵敏度分析本章内容本章内容123 2图解法图解法两个决策变量的线性问题，可以用图解法求解。 2图解法图解法每个约束条件都代表一个半平面。 2图解法图解法每个约束条件都代表一个半平面。 2图解法图解法把五个限制条件对应的五个半平面合并成一个图，各约束条件的公共部分即为可行域。 2图解法图解法得到最优解：B:x1=50,x2=250 最优目标值 z=27500 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1x2M ax Z=

4、2 x1 +3 x2 st . .1/3 x +1/3 x 1 1/3x +4/3 x 3 x ,x0 121212 （3，0）Z=6（9，0）（0，9/4）Z=0（0，3） 2图解法图解法重要结论 解的情况解的情况场景场景有最优解一定有一个可行域的顶点，对应一个最优点无穷多个最优解若将例一中的目标函数变为z=50 x1+50 x2，则线段BC上的所有点都代表最优解无可行解可行域为空域，不存在满足约束条件的解无界解可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小 2图解法图解法重要结论无界解（无最优解的情况）目标函数：max z = x1 + x2 ；约束条件：x1 - x2 1 -3

5、x1 +2 x2 6 x1 0， x2 0该问题可行域无界，目标函数值无穷大，无界解，即无最优解。 2图解法图解法例2 某公司由于生产需要，共需A,B两种原料至少350吨（A，B有一定替代性）限制条件具体如下：求目标函数最小化的线性规划问题试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买 A，B 两种原料，使得购进成本最低？资源需求资源需求加工时间加工时间（小时（小时/吨）吨）成本成本（万元（万元/吨）吨）A125吨22B无限制13总资源需求（A+B）需求350吨时间限制（小时）600 2图解法图解法得 B 点坐标（250，100）为最优解建立模型：问题的提出图解法图解法的灵敏度分

6、析本章内容本章内容123 3图解法的灵敏度分析图解法的灵敏度分析 3图解法的灵敏度分析图解法的灵敏度分析 3图解法的灵敏度分析图解法的灵敏度分析非标准形式的线性规划问题，通过变换转化为标准形式。标准形式的线性规划的四大特点线性规划标准线性规划标准形式的形式的四个特点四个特点1目标最大化2约束为等式3决策变量均非负4右端项非负 3图解法的灵敏度分析图解法的灵敏度分析极小化目标函数的标准化问题注意注意：以上两个问题的最优解相同，但最优值相差一个负号，即min f = max z 3图解法的灵敏度分析图解法的灵敏度分析约束条件不是等式的标准化问题引入一个非负变量s，令其等于等式左右两边的差值为了使约

7、束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量松弛变量”；当不等式为“大于等于”时称为“剩余变量剩余变量”。 3图解法的灵敏度分析图解法的灵敏度分析 3图解法的灵敏度分析图解法的灵敏度分析 3图解法的灵敏度分析图解法的灵敏度分析通过标准化得： 3图解法的灵敏度分析图解法的灵敏度分析* 变量无符号限制（自由变量）的标准化问题 3图解法的灵敏度分析图解法的灵敏度分析考虑例1 的情况，目标函数 z = 50 x1 + 100 x2 斜线在右图两条红线之间,-1 （-c1/c2） 0最优解不变，仍为B. 3图解法的灵敏度分析图解法的灵敏度分析等值线斜率在-1 （-c1/c2）

8、 0 范围内则最优值不变。 当某一线性规划问题在不考虑非负约束时（即可当某一线性规划问题在不考虑非负约束时（即可行域不一定限定在第一象限时），仅存在行域不一定限定在第一象限时），仅存在max(max(或或min)min)时，如果目标函数就是要求求解时，如果目标函数就是要求求解max(max(或或min)min)，此时该结论有效。如例此时该结论有效。如例1 1，习题，习题2 2（1 1），习题），习题6 6等。等。 当某一线性规划问题在不考虑非负约束时（即可当某一线性规划问题在不考虑非负约束时（即可行域不一定限定在第一象限时），既存在行域不一定限定在第一象限时），既存在maxmax也存也存在在minmin时，无论目标函数是要求求解时，无论目标函数是要求求解max(max(或或min)min)，此时该结论无效效。如此时该结论无效效。如P16P16的例的例2 2。 3图解法的灵敏度分析图解法的灵敏度分析 3图解法的灵敏度分析图解法的灵敏度分析结论结论：当某约束条件中的松弛（剩余）变量不为0时，其对偶价格一定为0，反之不成立。 3图解法的灵敏度分析图解法的灵敏度分析在一定范围内，当约束条件中常数项增加 1 个单位