线性规划图解法和单纯形法学习教案

1、会计学1线性规划线性规划(xin xn u hu)图解法和单图解法和单纯形法纯形法第一页，共87页。xa xxav 220 dxdv0)2()2()2(22 xaxxa6ax 第2页/共87页第二页，共87页。例1.2 某厂生产(shngchn)两种产品，下表给出了单位产品所需资源及单位产品利润 问：应如何(rh)安排生产计划，才能使总利润最大？ 解：1.决策变量：设产品I、II的产量 分别为 x1、x22.目标函数：设总利润为z，则有： max z = 2 x1 + x23.约束条件： 5x2 15 6x1+ 2x2 24 x1+ x2 5 x1， x20 x1=3.8, x2=1.2, z

2、=22.8第3页/共87页第三页，共87页。例1.3 已知资料如下表所示，问如何(rh)安排生产才能使利润最大？或如何(rh)考虑利润大，产品好销。 设设 备备产产 品品 A B C D利润利润（元）（元） 2 1 4 0 2 2 2 0 4 3 有有 效效 台台 时时12 8 16 12解：1.决策(juc)变量：设产品I、II的产量分别为 x1、x22.目标函数：设总利润为z，则有： max z = 2 x1 + x23.约束条件： x1 0 , x2 0 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12第4页/共87页第四页，共87页。例1.4 某厂生产三种药物

3、，这些药物可以从四种(s zhn)不同的原料中提取。下表给出了单位原料可提取的药物量 解：要求：生产A种药物至少160单位；B种药物恰好(qiho)200单位，C种药物不超过180单位，且使原料总成本最小。1.决策变量：设四种原料的使用 量分别为：x1、x2 、x3 、x42.目标函数：设总成本为z min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.约束条件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x4 0第5页/共87页第五页，共87页。 例1.5 某航运局现有

4、船只种类、数量以及计划(jhu)期内各条航线的货运量、货运成本如下表所示：航线号航线号船队船队类型类型编队形式编队形式货运成本货运成本（千元队）（千元队）货运量货运量（千吨）（千吨）拖轮拖轮A型型驳船驳船B型型驳船驳船1112362521436202322472404142720船只种类船只种类船只数船只数拖拖 轮轮30A型驳船型驳船34B型驳船型驳船52航线号航线号合同货运量合同货运量12002400问：应如何编队，才能既完成(wn chng)合同任务，又使总货运成本为最小？第6页/共87页第六页，共87页。解：设：xj为第j号类型船队的队数（j = 1，2，3，4）， z 为总货运(huy

5、n)成本则： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 5225x1+20 x2 200 40 x3+20 x4 400 xj 0 （ j = 1,2,3,4）第7页/共87页第七页，共87页。第8页/共87页第八页，共87页。第9页/共87页第九页，共87页。第10页/共87页第十页，共87页。1 12211 1122111 1221max (min) () () 00nnnnmmmnnmnzc xc xc xa xa xa xba xaxaxbxx )21(j 0

6、 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 简写为：第11页/共87页第十一页，共87页。) (21ncccC nxxX1 mjjjaaP1 mbbB1max (min) () 0 jjzCXP xBX 其中(qzhng)：第12页/共87页第十二页，共87页。 mnmnaaaaA1111 0 )( (min) maxXBAXCXZ其中(qzhng)：) (21ncccC nxxX1 mbbB1第13页/共87页第十三页，共87页。11max.1,2,0,1,2,njjjnijjijjZc xa xbstimxjn特点(tdin)：(1) 目标函数求最

7、大值（有时求最小值）(2) 约束条件都为等式方程，且右端常数项bi都大于或等于零(3) 决策变量xj为非负。第14页/共87页第十四页，共87页。 目标函数(hnsh)的转换 如果是求极小值即 ，则可将目标函数乘以(-1)，可化为求极大值问题。 jjxczmin也就是：令 ，可得到上式。zz jjxczzmax即 若存在取值无约束的变量 ，可令 其中：jxjjjxxx 0, jjxx 变量的变换第15页/共87页第十五页，共87页。 约束方程的转换(zhunhun)：由不等式转换(zhunhun)为等式。 ijijbxa0 iniinjijxbxxa称为(chn wi)松弛变量 ijijbxa

8、0 iniinjijxbxxa称为剩余变量 常量 bi0 的变换:约束方程两边乘以（1）第16页/共87页第十六页，共87页。例1.6 将下列(xili)线性规划问题化为标准形式 ,0,52324 7 532min321321321321321无无约约束束xxxxxxxxxxxxxxxZ用 替换(t hun) ，且 解:（）因为x3无符号要求 ，即x3取正值也可取负值，标准型中要求变量非负，所以33xx 3x0,33 xx第17页/共87页第十七页，共87页。(2) 第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3) 第二个约束条件是“”号，在“”左端减去剩余变量x5

9、，x50；(4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数(zhngsh)； (5) 目标函数是最小值，为了化为求最大值，令z=-z,得到max z=-z，即当z达到最小值时z达到最大值，反之亦然;第18页/共87页第十八页，共87页。 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准(biozhn)形式如下：第19页/共87页第十九页，共87页。 例1.7 将下列(xili)线性规划问题化为标准形式 ,0,52324 7 532min3213

10、21321321321xxxxxxxxxxxxxxxZ为无约束（无非(wfi)负限制）第20页/共87页第二十页，共87页。 解: 用 替换(t hun) ，且 ， 54xx 3x0,54 xx将第3个约束方程两边(lingbin)乘以（1）将极小值问题(wnt)反号，变为求极大值标准形式如下： 0,5 )(252 )( 7 )(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ76, xx引入变量第21页/共87页第二十一页，共87页。 12121212m in2385340 ,Zxxxxxxxx 无 约 束0 x

11、,x ,x ,x ,xx)x(xxx)x(xx)x(xxZaxm1111654364354343435832例1.8 将线性规划(xin xn u hu)问题化为标准型解：第22页/共87页第二十二页，共87页。 例1.9 将线性规划(xin xn u hu)问题化为标准型解：Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1 , x3 , x4 0； x2无约束 Max z = 3x15x2+5x2”

12、8x3 +7x4 s.t. 2x13x2+3x2”+5x3+6x4+x5= 28 4x1+2x2-2x2”+3x3-9x4-x6= 39 -6x2+6x2”-2x3-3x4-x7 = 58 x1 ,x2,x2”,x3 ,x4 ,x5 ,x6 ,x7 0 第23页/共87页第二十三页，共87页。11max(1)(1,2,)(2).0,1,2,(3)njjjnijjijjZc xa xbimstxjn线性规划(xin xn u hu)问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。第24页/共87页第二十四页，共87页。 可行解：满足约束条件

13、、的解为可行解。所有可行解的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子方阵（B0），称B是规划(guhu)问题的一个基。设：) (11111mmmmmppaaaaB 称 B中每个列向量Pj ( j = 1,2, , m) 为基向量。与基向量Pj 对应(duyng)的变量xj 为基变量。除基变量以外的变量为非基变量。第25页/共87页第二十五页，共87页。mnC非可行解可行解基解基可行解第26页/共87页第二十六页，共87页。 5 , 1, 0226103524max53214321321jxxxxxxxx

14、xxxxZj解: 约束方程的系数(xsh)矩阵为25矩阵 10261001115Ar(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即 100116010211120101015061111005261161015987654321BBBBBBBBB第27页/共87页第二十七页，共87页。一 般 有两种方法(fngf)图 解 法单纯形法两个(lin )变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观的优点，便于初学者窥探线性规划基本原理和几何意义。第28

15、页/共87页第二十八页，共87页。 解题(ji t)步骤4 将最优解代入目标(mbio)函数，求出最优值。1 在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为(chn wi)可行域，可行域中的点即为可行解。 2 标出目标函数值增加或者减小的方向。3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。第29页/共87页第二十九页，共87页。 -3.8 X1 ，X2 0例1.11 用图解法求解线性规划(xin xn u hu)问题第30页/共87页第三十页，共87页。x1x2oX1 - 1.9X2 = 3.8(

16、)X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此点是唯一(wi y)最优解，且最优目标函数值 max Z=17.2可行(kxng)域max Z = 2X1 + X2第31页/共87页第三十一页，共87页。max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X

17、2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数(hnsh)值max Z=34.2是唯一的。可行(kxng)域第32页/共87页第三十二页，共87页。x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行(kxng)域此点是唯一(wi y)最优解第33页/共87页第三十

18、三页，共87页。 006346321212121xxxxxxxx、246x1x2246无界解(无最优解)max Z=x1+2x2例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min Z第34页/共87页第三十四页，共87页。x1x2O10203040102030405050无可行(kxng)解(即无最优解)0,050305.140221212121 xxxxxxxxmax Z=3x1+4x2例1.7第35页/共87页第三十五页，共87页。 由图解法得到(d do)的几种情况 根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况： 1.可

19、行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2.可行域为封闭的无界区域 (c)有唯一的最优解； (d)有无穷多个最优解； (e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限(wxin)增大或无限(wxin)减少)，因而没有有限最优解。 3.可行域为空集 (f)没有可行解，原问题无最优解第36页/共87页第三十六页，共87页。 由图解法得到(d do)的启示(1) 线性规划问题解的情况：(2) 唯一(wi y)最优解；无穷多最优解；无界解；无可行解(2) 线性规划问题(wnt)的可行域是凸集（凸多边形）第37页/共87页第三十七页，共87页。x1x2oX

20、1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()17.2 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z可行(kxng)域max Z = 2X1 + X2 (3) 最优解一定是在凸集的某个(mu )顶点第38页/共87页第三十八页，共87页。 解题思路 先找出凸集的任一顶点，计算其目标(mbio)函数值，再与周围顶点的目标(mbio)函数值比较，如不是最大（或最小），继续比较，直到找出最大（或最小）为止。第39页/共87页第三十九页，共87页。学习要

21、点：1. 通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）2. 作图的关键有三点： (1) 可行解区域要画正确 (2) 目标函数增加的方向不能画错 (3) 目标函数的直线怎样(znyng)平行移动第40页/共87页第四十页，共87页。 连接几何形体中任意(rny)两点的线段仍完全在该几何形体之中。 有限个凸集的交集仍然是凸集。凸集第41页/共87页第四十一页，共87页。凸集：如果集合(jh)C中任意两个点X1、X2，其连线上的所有点也都是集合(jh)C中的点，称C为凸集。凸集凸集不是凸集2112, 0(11)CCaCaXXXa X有第42页/共87页第四十二页

22、，共87页。凸集凸集顶 点 顶点：如果凸集C中不存在任何两个(lin )不同的点X1，X2，使X成为这两个(lin )点连线上的一个点2112,11(0)XXXa XCCXaCa不存在第43页/共87页第四十三页，共87页。第44页/共87页第四十四页，共87页。1njjjP xb111121221222(,) ,(,)TTnnXxxxXxxx12,XC XC1211;(1.8)nnjjjjjjP xbP xb1212(1)(01)(1)(01,1, )(1.9)jjjXaXa Xaxaxa xajn第45页/共87页第四十五页，共87页。1211122111(1)nnjjjjjjjnnnjjjjjjjjjP xP axa xPaxP xPaxabbabb12(1)XaXa XC第46页/共87页第四十六页，共87页。n1) 当当k=m时，它们恰好构成一时，它们恰好构成一个个(y )基，从而相应的基可行基，从而相应的基可行解为解为n2) 当当k04010换出行(chxng)将3化为15/311801/301/3101-1/3 303005/30-4/3乘以1/3后得到103/5-1/51801-1/5 2/5400-1-1第78页/共87页第七十八页，共87页。 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：将数