第一章--线性规划及图解法

运筹学OperationsResearch第一章线性规划及图解法第一章线性规划及单纯形法线性规划（LinearProgramming，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。1947年G.B.Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。§1线性规划问题及其数学模型e.g.1资源的合理利用问题问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？表1产品资源甲乙库存量A1360B1140单件利润1525某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。第一章线性规划及单纯形法maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0解：设x1，x2为下一个生产周期产品甲和乙的产量；约束条件：Subjecttox1+3x2≤60x1+x2≤40x1，x2≥0目标函数：z=15x1+25x2表1产品资源甲乙库存量A1360B1140单件利润1525决策变量§1线性规划问题及其数学模型e.g.2营养问题假定在市场上可买到B1,B2,…Bnn种食品，第i种食品的单价是ci,另外有m种营养A1,A2,…Am。设Bj内含有Ai种营养数量为aij(i=1~m,j=1~n)，又知人们每天对Ai营养的最少需要量为bi。见表2：表2食品最少营养B1B2…Bn需要量A1a11a12…a1nb1A2a21a22…a2nb2………………Amam1am2…amnbm单价c1c2…cn试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。第一章线性规划及单纯形法表2食品最少营养B1B2…Bn需要量A1a11a12…a1nb1A2a21a22…a2nb2………………Amam1am2…amnbm单价c1c2…cn解：设xj为购买食品Bj的数量(j=1,2,…,n)（i=1,2,…,m）xj≥0（j=1,2,…,n）0≤xj≤lj1minnjjjzcx1..nijjijstaxb§1线性规划问题及其数学模型三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成n个子系统处理。1、决策变量xj≥02、约束条件——一组决策变量的线性等式或不等式3、目标函数——决策变量的线性函数第一章线性规划及单纯形法max（min）z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1a21x1+a22x2+…+a2nxn≤（或=，≥）b2……am1x1+am2x2+…+amnxn≤（或=，≥）bmxj≥0（j=1,2,…,n）其中aij、bi、cj（i=1,2,…,m；j=1,2,…,n）为已知常数线性规划问题的一般形式：§1线性规划问题及其数学模型线性规划问题的标准形式：maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmxj≥0（j=1,2,…,n）bi≥0（i=1,2,…,m）特点：1、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负。第一章线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为：。njjjxcz1minnjjjxcz1'max因为求minz等价于求max(-z)，令z’=-z，即化为：2、约束条件为不等式，njinjijbxxa11njijijbxa1njijijbxa1xn+1≥0松弛变量如何处理？§1线性规划问题及其数学模型３、右端项bi0时，只需将等式两端同乘（-1）则右端项必大于零4、决策变量无非负约束设xj没有非负约束，若xj≤0，可令xj=-xj’，则xj’≥0；又若xj为自由变量，即xj可为任意实数，可令xj=xj’-xj’’，且xj’,xj’’≥0第一章线性规划及单纯形法e.g.3试将LP问题minz=-x1+2x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0化为标准形式。解：令x3=x4-x5其中x4、x5≥0；对第一个约束条件加上松弛变量x6；对第二个约束条件减去松弛变量x7；对第三个约束条件两边乘以“-1”；令z’=-z把求minz改为求maxz’maxz’=x1-2x2+3x4-3x5s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0§1线性规划问题及其数学模型LP的几种表示形式：),,2,1(0),,2,1(..max11njxmibxatsxczjinjjijnjjj12,,,ncccc价值向量max(1)..(2)0(3)zcxstAxbx1max..0njjjzcxstpxbx决策向量Tnxxxx,,,21右端向量0,,,,21iTmbbbbb列向量的第为jAaaapTmjjjj,,,21系数矩阵mnmmnnaaaaaaaaaA212222111211§2线性规划问题的图解法定义1在LP问题中，凡满足约束条件(2)、(3)的解x=(x1,x2,…,xn)T称为LP问题的可行解，所有可行解的集合称为可行解集（或可行域）。记作D={x|Ax=b,x≥0}。定义2设LP问题的可行域为D，若存在x*∈D，使得对任意的x∈D都有cx*≥cx，则称x*为LP问题的最优解，相应的目标函数值称为最优值，记作z*=cx*。max(1)..(2)0(3)zcxstAxbx§2线性规划问题的图解法maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0(40,0)(0,0)BC(30,10)12360xx1240xxO(0,20)AL1L2Z=250目标函数变形：x2=-3/5x1+z/25x2x1最优解：x1=30x2=10最优值：zmax=700B点是使z达到最大的唯一可行点第一章线性规划及单纯形法LP问题图解法的基本步骤：1、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；4、寻找最优解。§2线性规划问题的图解法maxz=3x1+5.7x2s.t.x1+1.9x2≥3.8x1-1.9x2≤3.8x1+1.9x2≤11.4x1-1.9x2≥-3.8x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1+5.7x2maxZminZ（3.8,4）34.2=3x1+5.7x2可行域x1-1.9x2=-3.8(0,2)(3.8,0)绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.2第一章线性规划及单纯形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4x1，x2≥01222xx1244xxOA(１,0)x1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。可行域为无界区域一定无最优解吗？§2线性规划问题的图解法由以上两例分析可得如下重要结论：1、LP问题从解的角度可分为：⑴有可行解⑵无可行解a.有唯一最优解b.有无穷多最优解C.无最优解2、LP问题若有最优解，必在可行域的某个顶点上取到；若有两个顶点上同时取到，则这两点的连线上任一点都是最优解。§2线性规划问题的图解法图解法优点：直观、易掌握。有助于了解解的结构。图解法缺点：只能解决低维问题，对高维无能为力。