刘萌萌-关于数学规划图解法的探究1

1、刘萌萌关于数学规划图解法的探究1淮北师范大学2022届学士学位论文关于数学规划图解法的探究学院、专业数学科学学院数学与应用数学研究方向 运筹学学生姓名学号指导教师姓名指导教师职称2012年4月12日关于数学规划图解法的探究刘萌萌(淮北师范大学数学科学学院，淮北，235000)摘要数学规划(mathematical programming)是运筹学的重要分支，包括线 性规划，非线性规划，整数规划，二次规划，多目标规划等等广泛应用于 各领域，特别是金融领域线性规划理论和非线性规划理论是数学规划的两 个主要分支图解法就是利用坐标图去解数学规划问题的方法该方法不是 线性规划的主要方法，只是用于说明线性

2、规划的性质和特点此方法简单直 观，有助于我们从几何图形上了解数学规划问题的一些基本概念、理论及解 的原理.本文首先论述了数学规划问题图解法的有关概念，包括可行域、基本解、 基可行解、凸集、极点等，及数学规划图解法的适用范围、理论依据、解题 步骤；然后给出数学规划图解法几种模型；最后给出几个关于数学规划图 解法的实际应用.关键词 线性规划非线性规划线性规划模型可行域 图解法解法 探讨求解过程最优值目录引言？一、数学规划图解法理论说明?1（一）主要概念?1（-）数学规划图解法的适用范围、解题步骤?2（三）数学规划图解法理论依据?4（四）数学规划图解问题解决方法？?6二、数学规划图解法几种模型？?1

3、2（一）两个变量线性规划图解法模型？?13（二）多个变量线性规划图解法模型？?14（三）非线性规划图解法模型?16三、数学规划图解法的应用?18（一）数学规划图解法的理论应用?18（二）数学规划图解法的实际应用?20结论?22 参考文献？22 致谢？24引言朴素的运筹学作为一门现代科学，是在第二次世界大战期间首先在英 美两国发展起来的，它的思想可追溯到公元前400隹至第二次世界大战前 夕？.运1筹学的特点是1.运筹学已被广泛应用于工商企业、军事部门、民政事 业等研究组织内的统筹协调问题，故其应用不受行业、部门之限制；2运 筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题, 它具

4、有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效； 3它以整体最优为冃标，从系统的观点出发，力图以整个系统最佳的方式 来解决该系统各部门之间的利害冲突对所研究的问题求岀最优解，寻求最 佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题 的优化方法然而图解法是运筹学的形思维的启蒙，也是打开运筹学基本原 理的一把钥匙，该方法简单、直观、具体数学规划作为运筹学的重要分支， 可想而知图解法在数学规划中的作用也是不可替代的我们从几何图形上 了解数学规划问题的一些基本概念、理论、及解的原理，并使我们能得心应 手地解决数学规划问题木文就图解法的基木理论和基木解题方法及其应 用展开思

5、考.一、数学规划图解法理论说明(-)主耍概念定义1对数学规划问题min z?cjxjns.t ?aijxj?bi ?i?l,2,.zm?xj?o?j?l,2z.zn?价值向量c?(cl,c2,.,cn)?a?11系数矩阵a?aml?aln? ?amn?tt资源向量 b?决策向量 x? (bl, b2, ?, bm) (xl,?,xn)称d?x/ax?b,o?x?为数学规划(lp)的可行域若x?d,则称x为(lp)的可彳亍解若x*?d jgl对任意x?d有cx*?cx,则称x*为(lp)的最优解,ex*为 最优值.定义2对上述数学规划问题，设a为约朿方程组的m?n阶系数矩阵， (设n?m),秩为

6、mzb是矩阵a中一个m?m阶的满秩子矩阵，称b是数学规 划问题的?all?alm? 一个基阵或简称基不失一般性，设b?al/a2,.zam?b 是每一?a?ml?amn?个列向量aj(j?l,2?.zm)称为基向量，与基向量aj对应的变量xj成为基 变量.数学规划中基变量以外的变量成为非基变量在约束方程中，令所有非基 变量xm?l?xm?2?.?xn?0,因为不是满秩矩阵，有cramer法则,可以从方程组 ax?b 得到基变量的唯一解 xb?(xl,x2/./xm)t?b?lb,称 x?(xl,x2/.,xm,0/.0)t 为数学规划问题的基解显然，基解的总数不超过cnm个当基解x满足x?0

7、时称为基可行解?2?.定义3如果集合c中任意两个点xl,x2,其连线上的所有点也都是集合 c中的点，称c为凸集在多维空间中，用数学解析式课表示为对任何 xl?c,x2?c有?xl?(l?)x2?c(0?l)z则称c为凸集若c中的点x不能用 xl?c,x2?c的凸组合?xl?(l?)x2?c(0?l)表示，则称x为凸集c的极点.(-)数学规划图解法的适用范围、解题步骤1、适应范围数学规划图解法主要是通过等值线在极点的值,平移到另一个极点的 等值线的值进行比较，然后求出最优解即先画出有约束条件决定的区域，然 后作冃标函数的平行直线（或平面）族（冃标函数视为参数），让直线族在 区域上移动，移动至区域

8、顶点停止或不能在顶点停止而决定最优解在顶点 确定或最优解不存在其主要适用于有两个变量的线性规划问题，一个二维 的线性规划,可以在平面图上求解，三维的则耍在立体图形上求解，维数再高 的就不能图试了但对于多个变量的来说，只要在标准型中有m个独立方程, n个未知数，且mm=2即仅有两个独立变量也可以用图解法解决问题.2、解题步骤数学规划问题图解法的基本步骤大体上可分为两步，第一是可行域的 确定,即在坐标系下用图形表示约束条件不等式（也就是约束条件的解域）; 第二是最优解的确定，即画目标函数图,由零等值线逐步得到最优解但在处 理实际问题时，得到解的结果会是怎样，我们一起来分析下面例题例 有一批钢管，长

9、度都是4000mm,要截成500mm和600mm两种 毛坯，且这两种毛坯数量比大于配套，怎样截最合理？ 32分析 先设出未知数，建立约束条件和目标函数后，再按求最优解是 整数解的方法去求.解 设截500mm的x根，600mm的y根，根据题意，得?5x?6y?40,?y?3x,?且 x,y?z. ?x?0,?y?0.作出可行域，如下图中阴影部分.目标函数为z?x?y,作一组平行直线x?y?t,经过可行域内的点且和原点距离最远的直线为过b(0,8)的直线，这时x?y?&由x, y为正整数，知(0,8)不是最优解.在可行域内找整点，使x?y?7可知点(2,5), (3,4), (4,3),

10、(5,2), (6j)均为最优伤军答 每根钢管截500mm的2根,600mm的5根，或截500mm的3根， 600mm的4根或截500mm的4根，600mm的3根或截500mm的5根, 600mm的2根或截500mm的6根，600mm的1根最合理.说明 本题易出现如下错解 设截500mm的x根，600mm的y根，则,?500x?600y?4000?5x?6y?40,?xl?y?3x,?,即？ ?y3?x?0z?x?0,?y?0.?y?0 其中x、y均为整数.作出可行域，如下图所示中阴影部分.目标函数 为z?x?y,作一组平行直线x?y?t,经过可行域内的点且和原点相距最远的 直线3为过a点的直

11、线.先求a点的坐标，40?x?y?3x?23 解？得？,120?5x?6y?40?y?23?40120?故 a?,即 x?y?7,调整为 x?2, y?5.?2323?经检验满足条件，所以每根截500mm的2根，600mm的5根最合 理.本题解法错误主要是在作一组平行直线x?y?t时没能准确作出，而得 到经过可行域内的点且和原点距离最远的直线为过a点的直线.此错误可检验如下如果直线x?y?t通过a点，它是经过可行域内的点且到原点距离最远 的直线，40120175?t,即x?y?7.由于x, y为整数,所以点a5)不是最 优那么723232323解但在可行域内除a点外，不可能再有其他点满足x?y

12、?7, 只能在可行域内找满足x?y?6的点.如果还没有整数点，则只能在可行域 内找满足x?y?5的整数点但我们知道x?2, y?5满足题意，这样，就出现 了矛盾，从而判断解法错误，即x?y?t通过a点的直线并不是通过可行域 内的点但和原点距离最远的直线.(三) 、数学规划图解法理论依据1、基本理论依据定理1若线性规划问题存在可行域，则可行域一定是凸集.',“证 设e(xl',x2则ef)/f(xl,x2)是可行域内任意的两点，连接 e、f,如 xl'?xl"'x2?x2 所在的直线方程是 x2?x?n'(

13、xl?xl')z?0zl?,对 应线段e,f上的任意一点xl?xl'2"'"g 的坐标为?xl'?l?xlz?x2?l?x2,不失一般性，设 e,f 两点的坐标满足?？''""约束条件 axl?bx2?c 则 axl?bx2?c,axl?bx2?c&#39'“'',h?a?c?l?c?c?xl?l?xl?b?x2?l?x2?axl?bx2?l?axl?bx2?即点g的坐标也满足约束条件 axl?bx2?c

14、,同样也可以证明点g的坐标也满足其”它约束条件，因点g也是可行域的点.如xl'?xl则ef上任意一点'''?l?x?2,同样也可以证明点h也是可行域的点即线段ef上的任意一 h?xl'z?x2点都属于可行域,?可行域是凸集.定理2线性规划问题的基可行解对应可行域的顶点.定理3若线性规划问题有可行解,则至少有一个基本可行解.''t证 设x'= (xl,.zxn)是线行规划问题的任一可行解，则有 ax'?b,0?x'不妨设x'的非零分量为前

15、k个，即有x'j?oj?b,k; xl'?0j?k?l,.,n.r 如果约束4矩阵a的前k个列向量a1,.,ak线性无关,则可知x'是基本可行解; 否则存在着不全为零的数?jj?l,k使得?iaj?o,令?l=o?k?bn得到n 维向量j?lk?lz./?k?k?l,./?n?/冇 a?jaj?j?ltkl?k?l由于 x?a?o,iin?oj?l,.,k,我们可取适当小的正数?，使得0?x'j?j,j?bkk?l,n易知a?x'?ax'?a?b.所以 x'?”x'?

16、均是问题的可 行解在满足不等式0?x'j?j 0?x'j?j,j?l/./k 的同时，可以选择?0,是上述诸式 中至少有一个取等号.这样就得到一个可行解x'?或x'?,它的非零分量至少比 x'少一个如果这个解还不是基本可行解，那么上述过程还可继续下去, 由于当可行解只有一个非零分量时，该非零分量所对应的列向量一定是线 性无关的,所以原线性规划问题必存在基本可行解.定理4?若线性规划问题有有限个最优值,则一定存在一个基本可行解 是最优3解.2、图解法与单纯性法等价的证明线性规划的可行解集是一个凸多面体,若非空，在有界

17、的情况下,它一定 有最优解，单纯形法是仅涉及可行解集极点的方法，迭代法的极点,沿着凸 多面体的一条棱走到相邻的一个极点，然后求得最优解或判断无最优解图 解法是通过等值线在极点的值，平移到另一个极点的等值线的值进行比较， 然后求出最优解，用图解法求解，线性规划不需要化成标准型。这两种方法 的连续求解过程,其实是等价的，这样我们就搭起了这两种解法的桥梁，圆满 地解释了这两种解法的共同本质.定义1若又连续映射fgx-s；其屮f为单纯形法,g为图解法;x为原问 题可行解集,s为其标准型可行解集.定义2若f,g: x-s连续，存在h xx |->y连续/吏得h?x,o?=f?x?,h?x,l?=g

18、?x?,称f同伦于目记为f?g定理?？单纯形法与图解法是同伦的.4h要想证明图解法与单纯性法等价关系，只要在上述定理的基础上证明 在某个集合上，同伦就是等价关系，这样我们就可证得了.下面我们来证明图解法与单纯性法等价的在集合s中，同伦f?g是个 等价关系.证明（1）反身性 设f:x-s是映射，则由h?x,t?= f?x?z x?x,t?b定义的同 伦是从f到f得同伦.（2）对称性 若f?g x-*s,则可定义同伦xxis为?x,t?=hxhh?x,l?t?, x?x,t?l则h是从g到f的同伦.5（3）传递性 若f?g,g?h,定义h xxi-s为 hh?g(x/2t?l),l/2?t?l?h

19、(x/t)?x?x如图所示则 h 连续，且 h?x,o?=f?x?7h?x,l?=h?x?,x?x,故得 f?h证毕单纯形法与图解法的传递性，对称性，使我们可将单纯形的理论用图解 法直观地表述出來,图解法过极点的等值线对应单纯形法过极点的一条棱, 其平移过程对应迭代过程必然得到图解法的最优解对应单纯形法的最优 解.(四) 数学规划图解问题解决方法线性规划问题的可行域是n维向量空间rn中的多血凸集，英最优值 如果存在必在该凸集的某顶点处达到,顶点所对应的可行解称为基本可行 解对可行域(可行解集)的确定和对冃标函数等值线平移方向的确定方法不 一，掌握不当易出差错下就介绍几种常见的方法1、判定可行域

20、的方法直接判定法对于ax?by?c?o或ax?by?c?o所表示的区域的情况冇如下结论'详见 表1与表2.表1 ax?by?c?o或ax?by?c?o (bho)所表示的区域情况h表2 ax?by?c?o或ax?by?c?o (b=0)所表示的区域情况6必须注意不等式中的符号“？” 、“？”或“？” 、“？” ,它们的唯一的区别就是前者表示的区域包括边界，后者表示的区域不包括边 界.点判定法二元一次不等式ax?by?c?o或ax?by?c?o表示在直角坐标系屮直线 ax?by?c?o某一侧的平曲区域的所有点?x,y?.那么，任取区域中一点，若该点 的坐标满足约束条件ax?by?c?o或

21、ax?by?c?o,则该约束条件表示的区域就 是以直线ax?by?c?o分隔且包含该点的一侧半平面，否则就表示另一侧半平 面为了方便'一般来说都是取原点来判定ax?by?c?o或ax?by?c?o所表示在 直线ax?by?c?o某一侧的平面区域的当c?0时，因原点已在直线ax?by?c?o 上'故不能通过原点来判定.例1根据表1、表2我们可以直接判定约束条件2x?y?6?0表示直线 2x?y?6?0下方区域;约束条件x?3y?2?0表示直线x?3y?2?0上方区域；约束 条件2x?3?0表示直线2x?3?0右方区域;约束条件?3x?2?0表示直线?3x?2?0 左方区域，例2画

22、出不等式2x?3y?6?0所表示的平曲区域.解 先画出直线2x?3y?6?0 （画成虚线），取原点?0,0?,代入 2x?3y?6?0 中，因为 6?0,所以，原点在不等式2x?3y?6?0所表示的平面区域内，不等式 2x?3y?6?0所表示的平面区域如图11所示.由于对在直线ax?by?c?0同一侧的所有点?x, y?来说，把它的坐标?x, y?代入ax?by?c所得到实数的符号都相同，所以只需在此直线的某一侧取 一个特殊点?xy?,从ax?by0,00?c?0的正负即可判断ax?by?c?0表示直线哪 一侧的0平面区域，特殊地，当ch0时，常把原点作为此特殊点这里强调了 这样的一个重要的事

23、实在直线一侧所有的点都使ax?by?c同号，另外， 由于原点的代入，数值计算相对来说较简单，故当c?0时，取原点作为特 殊点来判断ax+by+c的符号，那应该是最方便的，当c?0时，因原点己在 直线ax?by?c?o上，故不能7通过原点来判断ax?by?c的符号，此时其值恒为0.2、确定最优点的方法1、顶点比较法由于简单线性规划的可行域的边界类似于多边形的边界或部分边界， 我们类似于多边形那样给可行域边界予边或顶点等概念顶点比较法就是 先求出可行域边界的所有顶点,再分别计算目标函数在各个顶点的值进行 比较确定最优解的方法.2、斜率比较法由于目标函数z?ax?by?c（a,b 不同时为 0）可变

24、形为aaczy?x?（不妨设bh0）,故将z视作常数时,表示斜率为?（称为目标斜bbbb率）的直线斜率比较法是指当直线ax+by二0平移后难以判定最优解为 a,b等顶点时，将与a,b等顶点相连的可行域的边的斜率求出来，并从小到大 排列，观察a目标斜率?于哪两个斜率之间，求岀和这两个斜率表示的边都相 连的顶点确定最b 优解.?x?y?4.8?例 正数x,y满足?3x?10y?30 求冃标函数z?10x?12y的最大 值.?4x?5y?20?解作出如图的可行域，作直线10x?12y?0并平移后可知只有当直线z?10x?12y过可行域的右上边界时才可能取最大值；而右上边界的边的斜率由小到大排列为54

25、3?l?z冃标斜率为位于65104?区间?lz?之间，故直线x?y?4.8 5?与 4x?5y?20 的交点，即 b?4,4.8?为最优解，此时z的值为49.6.83、平移找解法作出可行域后，先打网格，描出整点，然后平移直线i,直线i最先经 过或最后经过的那个整点便是整点最优解.例1、某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3,第二种有56m3,假设生产每种产品都需耍用两种木料，生产一只圆桌和一个衣柜分别 所需木料如下表所示每生产一只圆桌可获利6元，生产一个衣柜可获利10元.木器厂在现有木料条件下，圆桌和衣柜各生产多少,才使获得利润最多？解 设生产圆桌x只，生产衣柜y个，利

26、?0.18x?0.09y?72?0.08x?0.28y?56?润总额为 z 元'那么？x?0?y?0?而 z?6x?10y.如图所示/乍出以上不等式组所表示的平面区域，即可行域.作直线l:6x?10y?0,即l:3x?5y?0,把直线i向右上方平移至ii的位置时,直线经过可行域上点且与原点距离最大，此时z?6x?10y取最大值解方程组?0.18x?0.09y?72 解方程组?，得 m 点坐标?350,100?.?008x?028y?56答 应生产圆桌350只，生产衣柜100个，能使利润总额达到最大.点评 本题的最优点恰为直线0.18x?0.28y?72和0.08x?o.28y?56的交

27、点m.4、整点调整法先按“平移找解法”求出非整点最优解及最优值，再借助不定方程的 知识调整最优值，最后筛选岀整点最优解.例3已知xy满足不等式组?2x?y?3?0?2x?3y?6?0?3x?5y?15?0?求使取最大值x?y的整数x和y.9解 不等式组的解集为三直线11: 2x?y?3?0, 12 :2x?3y?6?0,i3:3x?5y?15?0所围成的三角形内部（不含边界）,设ii与12, ii与13,12 与 1312?153?75交点分别为ab, c则a,b,c坐标分别为a?, ?b?0,?3?c?,?4?9?8?19作一组平行线i x?y?t平行于10 x?y?0,当i往10右上方移动

28、时，t随之增大，当i过c点时x?y最大为乂由 0?x?63,但不是整数解，1975知x可取1,2,3 19当x?l时，代入原不等式组得y?2,x?y?l；当 x?2 时,得 y?0 或?1,/.x?y?2 或 1； 当 x?3 时，?x?2?x?3故x?y的最大整数解为?或?.y?0y?l?5、目标参与法冃标参与法是指在冃标函数z?ax?by?c屮将x或y用乙y或乙x表示， 代入约束条件，再作出关于zy型或乙x型可行域，确定的最值点后求出对应 的关于x,y的最优解.例耍将两种大小不同的钢板截成a,b,c3种规格的小钢板，每张钢板 可同问各截这两种钢板多少张可得到所需三种规格成品，且使所用钢板面

29、 积最小.解 设分别截第一种，第二种钢板各为x,y张，所用钢板面积为乙则?x?y?12?z二x+2y,且x,y为非负整数，同时满足?2x?y?15?x?3y?27?z?y?12?2z?3y?15?由z=x+2y得x=z-2y代入约束条件得:?z?y?27?z?2y?0?y?0,z?010z作出关于乙y型可行域如图，处z（即纵坐标）取最小值，由z-y和z+y二27联立方程组得z=19.5,y即点m 不是最优整数解'此时z将直线z=19.5平移，当z=20时,7?y?8;所以当x=6,y二7或x=4,y=8时取得最小值z取6张、7张或4张、8张时，需3种规格成品，且使所用钢板面积最小.注最

30、优化方法是近几十年形成的，它主要运用数学方法研究各种系 统的优化途径及方案，为决策者提供科学决策的依据最优化方法的主要研 究对象是各种有组织系统的管理问题及其生产经营活动最优化方法的目 的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方 案，发挥和提高系统的效能及效益，最终达到系统的最优冃标实践表明, 随着科学技术的日益进步和牛产经营的日益发展，最优化方法已成为现代 管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管 理、经济管理、国防等各个领域，发挥着越来越重要的作用本章将介绍最 优化方法的研究对象、特点，以及最优化方法模型的建立和模型的分析、 求解、应用主耍是线

31、性规划问题的模型、求解（线性规划问题的单纯形解 法）及其应用一一运输问题；以及动态规划的模型、求解、应用一一资源 分配问题从数学意义上说，最优化方法是一种求极值的方法，即在一组约 朿为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最 小值从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济 效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下， 使投入的人力、物力和财力等资源为最少.3、确定等值线增减方向的方法？?命题 设直线z=ax?by （a,b,z是常 数），矢量r?ai?bj是使z增大的平移方向.证明设平面数量场u=u（a,b）在点m （a,b）处的梯度为

32、?u?u?gradu?i?j?ai?bj ?a?b由梯度定义,gradu的方向是点m出u值变化最大方向，而gradu?o, u值的变化?时增加的.ai?bj是常矢量，与点m无关，所以ai?bj是场中任意处u值增大最快的方向.?为使用方便，根据适量的平移性，记矢量r?om?ai?bj,再令 u(a,b)二乙得?z=ax?by,是场中等值线所以r=ax?by是等值线z=ax?by的z增大最快的 平移方向,也就是z增大的平移方向？注1 r的方向取决于等值线z=ax?by 的常数容易有图决定.注2该定理除了确定等值线z=ax?by的增大减小方向，另外一个应用就 是可以确定ax?by?(?)c表示的平面

33、区域.因为直线:z=ax?by把平血分为两部分，一部分是ax?by?c的区域，另一部?分是ax?by?c的区域，而矢量r=ax?by的方向是ax?by增大的方向，反 之,r的?负向是ax?by减小的方向，由r的方向就可定出区域.?方法是作 直线 ax?by=c 定出点 mo(a,b)引矢量 omo,以直线 ax?by=c 为? 界,omo方向就是ax?by?c表示的区域.omo的负向是ax?by?c的区域.例 mins?xl?x?2xl?x2?2?x?2x?212?xl?x2?5?x?x?l?12?xl?0/x2?0 解 如图？向，即？r方向10?20由应用一方法确定目标函数等值线:s?xl?

34、x2: 减小的平移方向r?i?j的反30由图知等直线平移在b点达最小值故问题最优解为xl?4,x2?l最优值mins?3注:对三变量的线性规划问题，其约朿条件及目标函数式的图形与等值 面有关，也可用上述方法进行图解，但空间图形不易画也不直观，求解不易、 意义不大.二、数学规划图解法几种模型数学规划的一般模型具备以下三个要素决策变量 决策问题待定的量值称为决策变量；决策变量的取值要求非负.2、约束条件 任何问题都是限定在一定的条件下求解,把各种限制条 件表示为一组等式或不等式，称之为约束条件；约束条件是决策方案可行的保障；lp的约束条件,都是决策变量的线性函数.123、目标函数衡量决策方案优劣的

35、准则，如时间最省、利润最大、成 本最低；目标函数是决策变量的线性函数；有的目标要实现极大，有的则要求极小.(-)两个变量线性规划图解法模型1、基本步骤(1) 可行域的确定满足所有约束条件的解的集合,称之为可行域即所有约束条件共同围 城的区域.例maxz= 3xl?5x2?xl?8?2x?12?2?3xl?4x2?36?xl?0,x2?0五边形oabcd内（含边界）的任意一点（xl,x2）都是满足所有约束条件 的一个解，称之可行解xl（2）最优解的确定目标函数z=3xl?5x2代表以z为参数的一族平行线.0等值线 位于同一直线上的点的目标函数值相同.最优解可行解中使目标函数最优（极大或极小）的解

36、.2、几点说明由线性不等式组成的可行域是凸集（凸集的定义是 集合内部任意两点 连线上xl13的点都属于这个集合）.可行域有有限个顶点设规划问题有n个变量,m个约束，则顶点的个数 不多于5m个? cn目标函数最优值一定在可行域的边界达到，而不可能在其内部.3、解的可能性唯一最优解只有一个最优点.多重最优解无穷多个最优解若在两个顶点同时得到最优解,则它们 连线上的每一点都是最优解.例 maxz?3xl?4x2?xl?8?2x?12?2 3x?4x?362?l?xl?0zx2?0=36 1无界解 线性规划问题的可行域无界，使目标函数无限增大而无界.（缺 乏必耍的约束条件）（二）多个变量线性规划图解法

37、模型图解法在一般情况下只适用于二维的线性规划问题求解，有一定的局 限性但利用对偶线性规划及其最优解互补松弛条件来解决含有两个约朿 的多个变量的线性规划的求解问题，突破图解法只能用于二维线性规划求 解的框框对于多变量的线性规划问题，利用图解法求解思路是应用线性规划的对偶规划原理，先用图解法解含有两个约束的多变量 线性规划的对偶线性规划，含有两个变量多个约束的线性规划问题再根据 图中哪个约束条件起作用,哪个不起作用，由对偶线性规划的最优解互补 松弛条件确定对偶规划中不起作用的约束所对应的原规划中的相应变量 为零.这样就将原线性规划变成了含有两个变量的线性规划问题从而可 以再用一次图解法确定最优解及

38、目标14 函数的最优值?？6对于多变量的线性规划问题的图解法除了应上述对偶方法外,三个决 策变量的还可以在立体图形中画岀可行域，进而应图解法解决线性规划问 题.其图解问题一般要在三维空间中讨论，在问题中一个约束条件决定了一 个平面及其切出的半个空间，这n个半空间的交就是线性规划问题的可行 域可行域一般是一个凸多面体.设有三个决策变量的线性规划问题maxz?clxl?c2x2?c3x3?allxl?al2x2?al3x3?bl?ax?ax?ax?b2112222332?t?ax?ax?ax?bn22n33n?nll?xl,x2,x3?0特殊情况下，可行域无界则可能导致线性规划问题无最优解，或n个

39、半 空间的交为空集，则线性规划问题无解.另一种特殊情况是约束条件中有一等式，这时问题可转化为二维问题.事实上，不妨设第i个约束条件为等式，贝!j ail?ai2?ai3?bi,其中ail,ai2,ai3不 全为零，不妨1设ai3?0,则x3?(bi?ailxl?ai2x2)把该式代入目标函数和约朿条件中的 其余不ai3等式中去，则问题变为一个只有两个决策变量xl,x2的线性规划问题.全部约束条件都是不等式的时候,在平面clxl?c2x2?c3x3?c上,目标函 数的值恒等于常数c,故称这样的平面为等值平面线性规划问题在空间的 可行域与等值平面的交便是使目标函数的值c的可行解平移该等值平面， 使

40、常数项c的值逐渐变大并且保持与可行域的交不空，则c值达到最大的那 个等值平血与可行域的交便是线性规划问题的最优解，这时等值平烦的c 值便是目标函数的最大值,最优解还可以从另一个角度去理解/乍一个特殊 的等值平面clxl?c2x2?c3x3?0,该平面过原点'而最优解可以理解为在可行 域上到等值平面距离最远的点.例maxz?2xl?3x2?x3ll?lx?x?31323x3?l? 47?ls.t?xl?x2?x3?333?3?xl,x2,x3?0?15解 首先建立空间直角坐标系，如下图.再在坐标系中画出可行域则 如图可行域为凸五面体oabcde,粗虚线所围平面为目标函数等值面，平移 目标

41、函数等值面得最优点为b点b点对应着该线性规划的最优解x*=(l,2,0)t 即 xl=l x2=2x3=0 此时有 maxz=8介绍了.对于三个决策变量的线性规划问题还可以用画迹线的方法 解决，这里就不做从上面用图解法求解例子过程中明显感觉到对具有三个决策变量的 线性规划进行图解就麻烦得多了因此，尽管图解法具有简单、直观的优点, 但它的使用是有局限性的，对仅含有两个至多不超过三个决策变量的线性 规划才适于使用图解法,大多数情况下仅对含有两个决策变量的线性规划才使用图解法求?6注 线性规划模型的局限性（1）英要求问题的求解必须满足全部约朿，但实际问题中并非所有 约束都需要严格满足，对某些约束有一

42、定程度的违背是允许的；（2）只能处理单冃标的优化问题，故线性规划模型屮人为的将一些 次要目标转化为约束，而实际问题中目标和约束可以互相转化，处理时候 不一定要严格区分；（3）线性规划中各个约朿条件（实际可看成目标）都处于同等重要 的地位，但实际问题中各目标的重要性有层次上的差别，同一层次中又可 以有权重上的区别；（4）线性规划寻求最优解，但很多实际问题中只需要找到满意解即 可.（三）非线性规划图解法模型非线性规划是具冇非线性约束条件或目标函数的数学规划，是运筹学 的一个重要分支非线性规划的理论是在线性规划的基础上发展起来 的.1951年，库恩（h.w.kuhn）和塔克（a.w.tucker）等

43、人提出了非线性规划 的最优性条件，为它的16发展奠定了基础?以后随着电子计算机的普遍使用，非线性规划的理 论和方法有7了很大的发展，非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具.一般來说，解非线性规划问题要比求解线性规划问题困难得多，而口也 不像线性规划那样有统一的数学模型及如单纯形法这一通用解法非线性 规划的各种算法大都有自己特定的适用范围都有一定的局限性，如线性规 划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的 顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行 域的任意一点达到到目前为止还没有适合于各种非线性

44、规划问题的一般 算法这正是需要人们进一步研究的课题.一般非线性规划的数学模型可表示为minf?x?s.t gi?x?ohj?x?0,?j?l,2,?,l?式中 x?xlzx2,?,xn?rn 是 n 维向量朮gi?i?12?,m?,hj?j?12?都是rn?rl的映射（即自变量是n维向量，因变量是实数的函数关系），且其 中至少存t?j则称?为可行域因此上述模型可简记为minf?x?s.t x?当只有两个口变量时，非线性规划也可象线性规划那样，具有鲜明的几何解释,并但可象征地 把这种解释推广到多维中去.对非线性规划问题17min(xl?2)2?(x2?l)2)2?xl?x2?5x2?0?t?xl

45、?x2?5?0s.?x,x?0?12首先画出目标函数f(x*)?(3?2)2?(2?l)2的等值线2然后画出等式约朿xl?x2?5x2?0的图形它是一条抛物线最后画出不等式约束所代表的区域(带斜线区域).2由图看岀，可行解集是抛物线xl?x2?5x2?0上的曲线段abcd,即抛物 线被限制在带斜线区域中的部分不难分析，当动点从a出发沿抛物线abcd 移动时，在ab段日标函数值下降;过了 b点，在bc段上升，过了 c点,在cd段下 降d点是可行解集上使目标函数值获得最小值的点,因此是最优点，其坐标不 难由下面方?xl?x2?5?0t*x?4,lfx?4.程组得出？ 最后的,?2?xl?x2?5x

46、2?0三、数学规划图解法的应用 线性规划研究的是线性目标函数在线性约束条件下的最大值或最小 值的问题，线性规划实质上是“数形结合”思想的一种体现，即将最值问题直 观、简便地寻找出來，是一种较为简捷的求最值的方法图解法?？8(-)数学规划图解法的理论应用用二元一次不等式表示平面区域，是简单的线性规划问题的基础下面 就介绍几种利用线性规划图解法来解决数学问题的方法1、在方程中的应 用例1过直线2x+y+8=0和直线x+y+3=0的交点作一条直线，使它 夹在两条平行直线xy5=0和xy2=0之间的线段长为，求该直线的方程.18解析?2x?y?8?0 由？交点 m?5,2?x?y?3?0设所求直线i与

47、11、12分别交于b、a两点，由已知ab?,又1112间距离ac?在 rtaabc 中，bc?1.23,2设ii至ijl的角为？，则tan?acbc?3.设直线i的斜率为k,由夹角公式得k?l ?3?k?2或k?2.1?k 所求直线的方程为2x?y?8?0或x?2y?l?0注意:解题关键是“构造”与“转化”，即由所给出的根的范围列出条 件不等式组，再将英转换成线性规划问题.2、求斜率范围的应用例2已知两点a?3,4?, b?3,2?,过点p?2,?l?的直线i与线段ab有 公共点.(1) 求直线i的斜率的取值范围.(2)求直线i的倾斜角的取值范围.分析如图1,为使直线i与线段ab有公共点，则直

48、线i的倾斜角应介 于直线pa的倾斜角与直线pa的倾斜角之间，所以，当i的倾斜角小于90° 时，有k?kpb ；当i的倾斜角大于90。时，则有k?kpa结合线性规划知 识，根据直线于线段相交求直线斜率的取值范围解如图1,冇分析知19kpa?4?(?l)2?(?l)?l, kpb?3?3?23?23?. 4?(l)k?l 或 k?3z(2)arctg3?3、在概率中的应用?1?例3将长为1的棒任意地折成三段，求三段的长度都不超过 a?a?l?的?3?概率.解 设第一段的长度为x,第二段的长度为y,第三段的长度为l?x?y,则基本事件组所対应的几何区域可表示为 l?xyo?x?bo?y?b

49、o?x?y?l?,此区域面积为.2?1?事件“三段的长度都不超过a?a?l?”所对应的几何区域可表示 为?3?a?x,y?x,y?,x?a,y?a？x?y?a?即图中六边形区域，此区域面积 当?a?时，322?3a?l?为，此时事件“三段的长度都不超过2?3a?l?21?； a?a?l? 的概率为p?3?113?l?a?2当？a?l时，为?.此时事件“三段的222?1?长度都不超过a?a?l?v的概率为p?l?3?l?a?2. ?3?(二)数学规划图解法的实际应用解线性规划应用问题的基本步骤(1)转化设元，写出约束条件和目标函数，从而将实际问题转化为数学上的线性规划问题.求解解这个纯数学的线性规划问题.线性规划在解决实际问题中的应用，常通过二元