第2章 线性规划的图解法

管理运筹学1第2章线性规划建模（最大最小问题）•线性规划最大化问题•例1：广州电器厂生产A、B两种电器需要用到原材料1和原材料2，有关的数据如下表1所示。•根据市场调查知道两种产品的市场需求状况可以确定，按当前的定价可确保所有产品均能销售出去。问第一个月内产品A与产品B各应生产多少，可使总利润最大？项目1件产品A1件产品B总量原材料1（单位/件）621800原材料2（单位/件）01350劳动时间（小时/件）241600利润（元/件）38管理运筹学22线性规划最大化问题•此问题中，目标是总利润最大化，所要决策的变量是产品的产量，而产品的产量则受到可提供的原材料与劳动时间的约束，因此该问题可以用目标函数、决策变量和约束条件三个因素加以描述。实际上，所有的线性规划问题都包含这三个因素。现对这三个因素简单说明如下：•1决策变量是指系统中有待确定的未知因素。例如决定企业经营目标的各产品的产量等。•2目标函数是指系统所追求的目标的数学描述。如最大利润、最小成本等。•3约束条件是指实现系统目标的限制因素，它限制了目标值所能达到的程度。例如原材料供应量、市场需求等。管理运筹学3例1.决策变量：X为第一个月产品A的产量（件）Y为第一个月产品B的产量（件）目标函数：Maxz=3x+8y约束条件：s.t.6x+2y≤1800(A)2x+4y≤1600(B)y≤350(C)x≥0(D)y≥0(E)得到最优解：x=100，y=350最优目标值z=31002图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：管理运筹学42图解法分别取决策变量x,y为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。yxy≥0y=0yxX≥0X=0管理运筹学52图解法xy4321012345678B：2x+4y=1600管理运筹学62图解法xy86420246810A：6x+2y≤1800管理运筹学72图解法x1x24321012345678Y=350管理运筹学82图解法（4）目标函数z=3x+8y，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，O是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=2400=3x+8y图2-2z=3100=3x+8yz=0=3x+8yz=1000=3x+8yCBADO管理运筹学9线性规划的标准化内容之一：——引入松驰变量（含义是资源的剩余量）•例1中引入s1，s2，s3模型化为目标函数：Maxz=3x+8y+0s1+0s2+0s3约束条件：s.t.6x+2y+s1=1800y+s2=3502x+4y+s3=1600x,y,s1,s2,s3≥0对于最优解x=100y=350，s1=500s2=0s3=0说明：松驰变量的值=右边的值-左边的值，即可提供的资源与实际消耗的资源之差，即闲置的那部分资源，可以算的原材料1有多余，称为非紧约束；原材料2、劳动时间没有多余，称为紧约束。管理运筹学10重要结论–如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；–无穷多个最优解。若将例1中的目标函数变为maxz=4x+8y，则线段BC上的所有点都代表了最优解；–无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。Max3x+8ys.t.x+y=350,x=0,y=0一般来说，这说明模型有错，忽略了一些必要的约束条件；–无可行解。若在例1的数学模型中约束条件为：当X=400，y=350，6x+2y=1800，2x+4y=1600，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。管理运筹学11最小化线性规划问题管理运筹学12最小化线性规划问题•可建立该最小化问题的线性规划问题如下：•o.b.min45X+10Y•s.t.•0.40X+0.25Y=600金属A的产量约束•0.42X+0.15Y=420金属B的需求约束•Y=800矿石2的使用量约束•X,Y=0非负约束管理运筹学13最小化线性规划问题•本问题的目标是最小化，所以应在可行域内选择使得费用达到最小值的解。作等费用直线族45X+10Y=k(k可取不同的常数)，对于等费用直线族来说，越靠近原点的等费用直线对应的费用越小。因此，最优解应是在可行域内的、最接近原点的那条等费用直线上的点。本问题中，既在可行域内的、又最接近原点的那条等费用直线上的点是A点，所有A点的坐标就是最优解。而A点直线①和②的交点。解此线性方程组，得到：X=333.3吨，Y=1866.7吨。相应的最优解为：45X+10Y=33666（元）。管理运筹学14最小化线性规划问题y=800xy5001000150025002000150010005000③ABC0.42x+0.15y=4200.40x+0.25y=60045X+10Y=k管理运筹学15剩余变量•在例2中，将X=333.3吨，Y=1866.7吨，代入约束条件：•0.40X+0.25Y=600=600金属A的产量约束①•0.42X+0.15Y=420=420金属B的需求约束②•Y=1867=800矿石2的使用量约束③•X,Y=0非负约束•约束①与②的左边等于右边称为紧的约束，约束③的左边大于右边，说明矿石2的使用量不仅能够满足所要求的最小使用量，而且有剩余，称为非紧约束。管理运筹学16•使上面的不等式变为等式，可写为如下的等式形式：•o.b.min45X+10Y•s.t.•0.40X+0.25Y+S1=600•0.42X+0.15Y-S2=420•Y-S3=800•X,Y,S1,S2,S3=0非负约束•上式模型称为标准型线性规划模型。变量S2,S3称为剩余变量（surplus），变量S1称为松弛变量（slack）。松弛变量的值等于“≤”不等式右边的值减去左边的值，剩余变量的值等于“≥”不等式左边的值减去右边的值，即超额或有剩余的那部分数量。管理运筹学17•在上例中，约束条件①的松弛变量为：•S1=600（右边的值）-600（左边的值）=0•约束条件②和③的剩余变量分别为：•S2=420（左边的值）-420（右边的值）=0•S3=1867（左边的值）-800（右边的值）=1067