第1章 线性规划-标准型和图解法

1第2章线性规划宁波大学商学院2线性规划应用的典型情况制造者希望建立一个生产时间表和库存计划以满足未来一段时间的市场需求，最理想的情况是：既满足市场上产品的需求、同时又使生产和库存的成本最低；金融分析员必须选择一种股票或证券进行投资，金融分析员希望使自己的投资有最大的回报率；营销经理希望能够从广播、电视、报纸、杂志这几种媒体中选择一种合适的组合，确定广告预算使自己的广告效益最好；公司的仓库分布于全美各地，现在有一些顾客订单，公司希望确定每个仓库的发货量使成本最低……3问题的提出例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品的资源消耗、单位产品利润等数据如表所示，问如何安排生产计划使企业利润最大？甲乙资源限制（公斤）A11300B21400C01250单位产品利润（元/件）50100产品资源单耗4解：设x、y分别代表甲、乙两种产品的生产数量（件），z表示公司总利润。则有maxz=50x+100ys.t.x+y≤3002x+y≤400y≤250x，y≥0规划问题的数学模型5线性规划应用的典型情况这类例子的共同特点：要求目标函数最大化或最小化；一定存在约束条件，而且这些约束条件会影响目标的实现。6基本概念1、给定有限资源，充分利用资源最大限度地实现目标2、给定目标，要求完成任务使用的资源最少目标函数：表示最大目标或是最小资源约束条件：表示资源的约束或是目标约束非负条件：往往实际问题中变量不允许为负，而问题不一定明确指出，需要自己判断。一般定义为≥07线性规划问题的数学模型规划问题的数学模型三要素决策变量：问题中要确定的未知量，用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制；目标函数：它是决策变量的函数，按优化目标分别在这个函数前加上max或min；约束条件：指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。8线性规划:是指约束条件和目标函数都是线性时的规划模型。实际问题中线性的含义：一是严格的比例性；二是可叠加性。非线性规划的例子:K－T条件、0.618法、梯度法、随机搜索法等。规划问题的数学模型9LP问题基本概念数学模型可行解、最优解实际问题LP问题解的概念基本解、基可行解提出基本最优解基本方法图解法原始单纯形法单纯形法大M法人工变量法对偶单纯形法两阶段法对偶理论进一步讨论灵敏度分析──参数规划*在经济管理领域内应用运输问题（转运问题）特殊的LP问题整数规划多目标LP问题*10线性规划数学模型目标函数约束条件决策变量11线性规划数学模型简写形式11max(min)(,)(1,,)..0(1,,)njjjnijjijjzcxaxbimstxjn或12线性规划数学模型向量形式111122212max(min)(,)..0(,,,);;;njjjjjnjnmmjzCXPxbstXaxbaxbCcccXPbxba或13线性规划数学模型用矩阵和向量形式111212122212max(min)(,)..0nnmmmnzCXAXbstXaaaaaaAaaa或14决策变量的取值变量xj的取值一般为非负，即xj≥0从数学意义上来说，可以有xj≤0xj的取值也可以是(－∞,+∞)，即xj取值不受约束或称xj无约束15maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………………………am1x1+am2x2+…+amnxn=bmx1,x2,…,xn≥0线性规划问题的标准形式目标函数极大化约束条件为等号变量非负右端常数项大于或等于零16简写形式矩阵形式11max..1,,01,,njjjnijjijjzcxstaxbimxjn0..maxXbAXtsCXz线性规划问题的标准形式17线性规划问题的标准形式若minf=CX，可令z=－f，则maxz=min–f；目标函数为minf=c1x1+c2x2++cnxn令z=－f，变为maxz=–c1x1–c2x2-–cnxn18线性规划问题的标准形式约束条件为“≤”时，则约束条件左式加上非负的松弛变量xn+i，将约束条件变为等式约束；约束条件为a11x1+a12x2++a1nxn≤b1加入非负变量xn+1，称为松弛变量，有a11x1+a12x2++a1nxn+xn+1=b119线性规划问题的标准形式约束条件为“≥”时，则约束条件左式减去非负的剩余变量xn+i，将约束条件变为等式约束；约束条件为a11x1+a12x2++a1nxn≥b1减去非负变量xn+1，称为剩余变量，有a11x1+a12x2++a1nxn－xn+1=b120线性规划问题的标准形式若xk无限制时，则令xk＝xk1－xk2，其中xk1、xk2≥0；若bi0时，则－bi0。21例化下列线性规划为标准形式maxz=2x1+2x2－4x3s.t.x1+3x2－3x3≥30x1+2x2－4x3≤80x1、x2≥0,x3无限制22解：该线性规划问题的标准形式为maxz=2x1+2x2－4x31+4x32x1+3x2－3x31+3x32－x4=30x1+2x2－4x31+4x32+x5=80x1、x2、x31、x32、x4、x5≥023例无约束y,x3x2yx.t.syxmax24解：令则0x,00x,xx当当0x,x0x,0x当当0y,00y,yy当当0y,y0y,0y当当xxxxxxyyyyyy加入松驰变量s,w，得到标准型如下：0w,s,y,y,x,x3wxx2syyxx.t.s)yy()xx(zmax25回顾：学校准备为学生添加营养餐，每个学生每月至少需要补充60单位的碳水化合物，40单位的蛋白质和35单位的脂肪。已知两种营养品每斤：AB含量碳水化合物52蛋白质32脂肪51单价1.50.7问题：买A和B分别多少斤既满足学生营养需要又省钱？目标函数：x+y取最小值约束条件：x+y≥60x+y≥40x+y≥35变量：xy非负条件：x≥0y≥026表达式minS(x,y)=1.5x+0.7ys.t.5x+2y≥603x+2y≥405x+y≥35x≥0y≥027图解法为了便于建立n维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。如果模型中只含有2个变量的线性规划问题，可以通过在平面上作图的方法求解。28图解法图解法求解的目的：一是判别线性规划问题的求解结局，二是在存在最优解的条件下，把问题的最优解找出来。29图解法求解下述线性规划问题1212121212max23221228416412,0zxxxxxxxxxx30图解法画出线性规划问题的可行域31图解法目标函数的几何意义：32图解法最优解的确定33第一建立坐标系，将约束条件在图上表示出来第二确立满足约束条件的解的范围；第三画出两条目标函数等值线；第四平行移动目标函数等值线，使目标函数在可行域范围内达到最优。线性规划图解法34图解法无穷多最优解的情况目标函数与某个约束条件恰好平行35图解法无界解（或无最优解）的情况可行域上方无界36图解法无解的情况约束条件不存在公共范围37例maxz=50x1+100x2s.t.x1+x2≤3002x1+x2≤400x1、x2≥0,x2≤250x2x2≤2502x1+x2≤400x1+x2≤300x1OABCD38x2≤250x1x22x1+x2≤400x1+x2≤300例maxz=50x1+50x2s.t.x1+x2≤3002x1+x2≤400x1、x2≥0x2≤250ABCDO39maxz=2x+2ys.t.x－y≥1－x+2y≤0x、y≥0－x+2y≤0x－y≥1XYOA1例40Y例Xmaxz=x+2ys.t.－x+2y≥1x+y≤－2x、y≥0－x+2y≥1x+y≤－2O41图解法的启示：1.求解线性规划问题时，解的情况有：唯一最优解，无穷多最优解，无界界，无可行解；2.若线性规划问题可行域存在，在可行域是一个凸集；3.若线性规划问题最优解存在，在最优解或最优解之一一定能够在可行域的某个顶点取得；4.解题思路是，先找凸集的任一顶点，计算其目标函数值。比较其相邻顶点函数值，若更优，则逐点转移，直到找到最优解。42练习maxS(x,y)=7x+12y9x+4y≤3604x+5y≤2003x+10y≤300x,y≥0F(0,90)G(0,40)A(0,30)D(40,0)H(50,0)E(100,0)BCO(0,0)9x+4y=3604x+5y=2003x+10y=300答案：最优解为B(20,24)。43练习：minS(x,y)=200x+160y6x+2y≥122x+2y≥84x+12y≥240≤x≤7，0≤y≤7246776426x+2y=122x+2y=84x+12y=24y=7x=7E(0,7)D(0,6)(0,4)(0,2)(0,0)(2,0)(4,0)A(6,0)G(7,0)F(7,7)C(1,3)B(3,1)答案：C为最优点。