第二章线性规划.ppt
《第二章线性规划.ppt》由会员分享,可在线阅读,更多相关《第二章线性规划.ppt(41页珍藏版)》请在三一文库上搜索。
1、第二章 线性规划,第一节 线性规划问题及其数学模型 第二节 线性规划问题的图解法 第三节 单纯形法 第四节 线性规划的对偶问题 第五节 线性规划在卫生管理中的应用,第一节 线性规划问题及其数学模型,一、线性规划问题的特征和建模的步骤,二、线性规划问题的数学模型及一般形式,三、线性规划问题的标准形式,(一)线性规划问题的标准形式,(二)书写形式,(三)标准形式的转化,2、任务给定,如何合理地计划、统筹安排 以最少的资源完成它,1、资源给定,如何合理地计划、统筹安排 才能发挥最大的效益;,一、线性规划问题的特征和建模的步骤,(一) 线性规划研究的内容,(三)都有一个目标要求,并且这个目标可以表示为
2、决策变量的线性函数(称为目标函数)。,(一)可用一组变量(x1,x2 , xn)(称之为决策变量)来表示问题的方案,正常要求这组变量的取值是非负的,称为非负约束;,(二)存在某种限制条件,这些限制条件都可以用线性等式或不等式来表示。(这些等式或不等式称之为规划问题的约束条件方程式),(二) 线性规划问题的共同特征,(三) 建立模型的三个步骤, 确定一组变量(决策变量); 表示出一定的限制条件; 写出目标函数。,Max ( Min ) Z = c1 x1 + c2 x2 + + cn xn,约束条件:,目标函数:,二、线性规划问题的数学模型及一般形式,第二节 线性规划问题的图解法,一 、图解法解
3、极大化问题 二、 图解法求解极小化问题 三、 线性规划模型的解的各种情况 四、 解法的优点及局限性,一 、用图解法解极大化问题,例1MaxZ 60x 50y 2x 4y 80 3x 2y 60 x, y 0,(1) 以 x、y 作为坐标轴,建立平面直角坐标系,根据 x、y 非负的约束,可行解区域位于坐标图的第一象限(见图(a),1图示全部约束条件, 确定可行解区域,(2)用等式约束代替非等 式约束,画出直线 2x4y80 3x2y60 (见图(b),(3)根据不等式约束 2x4y 80 3x2y 60 确定可行解区域 (见图(c),( 1)等直线法:把目标函数 Z60x50y 看成是随着Z的取
4、值不同而产生的一族直线。令目标函数值分别为0、600、1200作平行线族(图(2),从图中可见,Z值越高,目标函数直线离原点越远。所以,寻找最优解问题可归结为:找出离原点最远的一条直线与可行解集的交点。,2从可行解中找出最优解,(1)等直线法 (2)试算法,(2)试算法:,(a)线性规划的可行域是凸多边形或凸集; (b)线性规划的最优解如果存在,必然在 可行解集的某个顶点上达到。,* 试算法是根据下面线性规划解的性质而得出的一种算法:,* 根据线性规划解的性质,先求出可行解集各顶点的坐标,然后试算目标函数之值,使目标函数达到极值的解,即为最优解,(见下面表13),表13 例1试算结果,最优解为
5、(x,y)(10,15) 最优值为 ZMax 1350,二、 图解法求解极小化问题,例 MinZ 50x 80y 4x + 10y 40 10x 5y 50 35x + 35y 245 x, y 0,解: 1、图示全部约束条件, 确定可行解区域,2可行解中找出最优解 (1)用等直线法求最优解。本例是极小值问题,因此目标函数值取离原点尽可能近的等直线的值(见图(4)。通过 p2 点的等直线离原点最近, p2 点的坐标既满足全部约束条件又能使目标函数取得最小值, 故为最优解。,(2)用试算法求最优解(见表14),表1-4 例2试算结果,最优解为(x,y)(5,2) 最优值为 ZMin 410,三、
6、线性规划模型的解的各种情况,例3,解:在本例中,由于目标函数(Z2x4y)的等直线与约束条件(x2y 8)的直线相平行,故最优解同时在两个顶点上达到。则在此两顶点连线上的任何一点都是最优解,即有无限多个最优解。,从图(6)可见,本 例的可行域无上界,目 标函数的值可趋于无穷 大。在这种情况下无法 确定最优解。,解:,例4,从图(7)可以看出, 本题的可行域是一个空集,因此无可行解。这是由于本题中包括了相互矛盾的约束条件的缘故。,解:,例5,线性规划问题解的几种情况,(1)有唯一的最优解。这时最优解一定在可行域的 某个顶点达到; (2)有最优解,但不唯一。这时最优解一定充满一个线段,此线段是可行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 线性规划
链接地址:https://www.31doc.com/p-3119967.html