第二章线性规划－程－2次课

第一章 线性规划程斌 Email:本章主要内容n 线性规划问题及其建模n 线性规划问题几何求解与解情况分析n 线性规划标准型n 线性规划问题求解 单纯形法n 灵敏度分析n 运输问题n 计算机求解一、线性规划问题的提出n 在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。n 线性规划是由丹捷格（ G.B.Dantzig）在 1947提出的，并提出了求解线性规划的单纯形法，成为运筹学的标志性成就，被誉为线性规划之父。n 1939年前苏联学者康托洛维奇在解决工业生产组织和规划问题时，已提出类似线性规划的模型，并给出 “解乘数法 ”的求解方法。 1960年再次发表 最佳资源利用的经济计算 ,获经济学诺贝尔奖。例题 1：生产计划问题引例 某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？产 品 A 产 品 B 资 源限量劳动 力设 备原材料9434510360200300利 润 元 /kg 70 120解题步骤：1、确定决策变量：设生产 A产品 X1kg,B产品 X2kg2、确定目标函数： maxZ=70X1+120X23、确定约束条件： 人力约束 9X1+4X2360设备约束 4X1+5X2200原材料约束 3X1+10X2 300 非负性约束 X10 X20综上所述，该问题的数学模型表示为：问题一 ： 任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件 .假定这两台车床的可用台时数分别为 800和 900，三种工件的数量分别为 400、 600和 500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表 .问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？例题例题 2：车床加工安排问题：车床加工安排问题解题步骤：1、确定决策变量：在甲车床上加工工件 1、 2、 3的数量分别为 x1、 x2、 x3，在乙车床上加工工件 1、 2、 3的数量分别为x4、 x5、 x62、确定目标函数： minz=13x1+9x2+10x3+11x4+12x5+8x63、确定约束条件：工件 1、 2、 3约束 X1+X4=400甲车床台时数约束 0.4X1+1.1X2+x3800乙车床台时数约束 0.5X1+1.2X2+1.3x3900非负性约束 Xi0 i=16综上所述，该问题的数学模型表示为：目标函数：Max(Min)z = c1x1 + c2x2 + + cnxn 约束条件： a11x1+a12x2+a1nxn( =, ) b1a21x1+a22x2+ a2nxn( =, ) b2 . . am1x1+am2x2 + amnxn( =, ) bmx1 ， x2 ， ， xn 0线性规划的一般形式 二 .线性规划问题的图解法n 若有线性规划问题：n n n 注：此方法只使用于两个决策变量的情况 1 2 3 412344x1=164x2=12x1+2x2=8Q1Q2Q3Q4可行域可行域与等值线1 2 3 412344x1=164x2=12x1+2x2=8Q1Q2(4,2)Q3Q4可行域n 可行域： 阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称 可行解 ），此区域是线性规划问题的解的集合，称为 可行域 。等值线最优 方案，最大利润为 14元x1x2最优解个数情况1.无穷多最优解n 上例中求解得到问题 最优解是唯一 的，但对一般线性规划问题，求解结果可能出现以下几种情况：n 1、无穷多最优解（多重最优解）n 若将上例中的目标函数变为 maxz=2x1+4x2，目标函数中以参数 z的这族等值线与约束条件x1+2x28的 边界线平行 。当 z值由小变大时，将与线段 Q2Q3重合。线段 Q2Q3上 任意一点都使 z取得相同的最大值，故这个线性规划问题有无穷多最优解（多重最优解）。（ 4,2）（ 4,0）（ 0,0）（ 2,3） 用图解法解下面的例子 Max z=2X1+4X 2 X1+2X2 8 (1) 4X1 16 （ 2） 4X2 12 （ 3） X1， X2 0 （ 4）无穷多最优解注意：多重解产生的原因，是因为目标函数线与第（ 1）条约束条件边界线的斜率相等。(1)(2)(3)(8,0)(0,4)2、无界解Max z= x1+x2 -2x1+x2 4 （ 1） x1 x2 2 （ 2） x1,x2 0 （ 3） （ 2， 0）（ 0， 4）（ 0， 0）无界解 （不等于无可行解）在这里需要注意的是，可行域无界不等于问题无界，这要看目标函数的情况。如 把把该问题中目标函数该问题中目标函数 x1的系数的系数由原来的由原来的 1改为改为 3/2时时 ， 该问题有最优解 Z(0,4) 4。3、无可行解Max z=2x1+3x2x1+2x2 8 (1)4x1 16 (2)4x2 12 (3)-2x1+x2 4 (4)x1,x2 0 (5)（ -2， 0）（ 0， 4）（ 4， 0）（ 4， 2）无可行解（约束条件无共同区域）图解法总结l 从 图解法中直观地见到，当线性规划问题的可行域 非空 时，它是 有界区域 或 无界凸多边形区域 。若线性规划问题存在唯一最优解，它一定在有界可行域的 某个顶点 得到；若能在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，此时就有 无穷多最优解 ；可行域 为空时 则无最优解可行域的一般情况 线性规划的可行域是凸集 线性规划的最优解在极点上凸集 凸集 不是凸集可行域和最优解的几种情况1、可行域封闭唯一最优解2、可行域封闭多个最优解3、可行域开放唯一最优解4、可行域开放多个最优解 5、可行域开放 目标函数无界 6、无可行解多个（ 2）决策变量时可行域的情况n 三个决策变量，最优解在棱角处取到，用图解法无法求解。n 三个以上决策变量时可行域就为超平面，最优解在相应的棱角处取到。用图解法无法求解。三 .线性规划问题的标准形式在 标准形式中规定各约束条件的 右端项 bi0 ，若否则在等式两端同乘以 “ -1” 即可。线性规划问题的标准形式矩阵表示A 约束条件的 mn 维系数矩阵，一般 mnb 资源向量C 价值向量X 决策变量向量实际碰到各种线性规划问题的数学模型都应变换为 标准型式后求解 。标准型的特点n 标准型的特点：n 1、目标函数 求极大 n 2、约束方程全为 等式n 3、变量全为 非负 n 4、约束条件右端常数项 bi 0 （ I=1,2,m ）n 如何变换为标准型的问题。化标准形式的一般步骤n 化标准形式的一般步骤n 1、目标函数若为极小化 “ 极大化 ”n 2、约束条件的右端项 bi0 “ bi0” n 3、 约束条件为不等式 或 “ =”n 4、取值无约束（自由）变量 “ 非负变量 ”n 5、取值非正变量 “ 非负变量 ”B. 约束条件标准化约束条件标准化(2) 约束条件是约束条件是 类型类型如何将一般问题化为标准型：如何将一般问题化为标准型：A. 目标函数标准化目标函数标准化 左边左边 加加 非负松弛变量非负松弛变量 (1) 右端常数右端常数 bi 0 等式两边乘以（等式两边乘以（ -1）(4) 变量符号无约束变量符号无约束(5) 变量变量 xi 0 引入新变量引入新变量(3) 约束条件是约束条件是 类型类型 左边左边 减减 非负剩余变量非负剩余变量 例例 1 将下述规划模型化为标准型将下述规划模型化为标准型 :解：解：红色字部分红色字部分是不符合标是不符合标准