《《物流运筹学》郝海熊德国chap2线性规划课件.ppt》由会员分享，可在线阅读，更多相关《《物流运筹学》郝海熊德国chap2线性规划课件.ppt（18页珍藏版）》请在三一办公上搜索。
1、,2.1 线性规划模型与图解法,线性规划的研究内容可归纳为两个方面：一是资源的数量已定，如何合理利用、调配，使任务完成的最多，才能更有效地运用有限的资源以更高水平达到目标；二是系统的任务已定，如何合理筹划，精细安排，用最少的资源(人力、物力和财力)去实现这个任务；,2.1.1 问题的引入,【例2.1】（生产计划问题）某企业生产l、2和3三种产品，每种产品需经过三道工序，每件产品在每道工序中的工时定额、每道工序在每周可利用的有效工时和每件产品的利润见下表。问每种产品各生产多少,可使这一周内生产的产品所获利润最大？,2.1 线性规划模型与图解法,生产计划资源表,【分析】该问题主要是要把有限的工时资
2、源合理地分配到三种产品的生产活动上去，以期望获得最多的利润。根据问题的要求，旨在获得最大利润，也就是说，在资源约束的条件下，尽可能生产更多的产品，以获得最大的利润，实现工厂利润最大化的目标，,2.1 线性规划模型与图解法,首先引进决策变量：设一周内企业各产品的生产件数为xj(j=1,2,3),然后根据每件产品的工时定额以及各工序允许的有效工时的列出要求(约束条件)：,产品1每生产一件需A工序1.2工时，现生产x1件，故产品1耗费A工序的工时数1.2x1；,类似地，生产2和3产品耗费A工序的工时数分别为1.0 x2和1.1x3，,这样三种产品对A工序的总工时数为1.2x1+1.0 x2+1.1x
3、3，,它不应超过工序A在一周内所允许的工作时间5400工时，于是，得工序A加工产品的约束条件：,同理，对工序B和C有以下约束条件：,2.1 线性规划模型与图解法,再者，还有一些变量本身的约束，xj(j=1,2,3)只能取非负值，故有下列非负约束条件：,最后确定产品生产的效益，若用z表示工厂一周内生产三种产品所能获得的利润，则有：,综上所述，得到生产计划问题的数学模型：,其中s.t.是英文“subject to”（受约束于）的缩写。,2.1 线性规划模型与图解法,【例2.2】（营养配餐问题）假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可
4、选，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？,食品的营养构成表,则相应的数学模型为：,2.1 线性规划模型与图解法,解 设xj(j=1,2,3,4)为第 j 种食品每天的购买量，,2.1.2 线性规划模型,上面所建立的数学模型中目标函数和约束条件都是线性函数，故称之为线性规划，简记为LP。,线性规划模型具有下列三个要素：,l）决策变量 这些决策变量的一组定值代表所给问题的一个具体解决方案。一般来说，这些决策变量都是非负变量，如果在模型中变量与的符号不受限制，即变量取正值、取负值或取零都可以，把它称为自由变量，可以写入规划模型，也可
5、省略。,2.1 线性规划模型与图解法,2）约束条件 这些约束条件都为线性等式或线性不等式。它们反映了所给问题对资源的客观限制及对所要完成的任务的各类要求，称为系统约束；对决策变量的符号要求也属于约束条件，称为符号约束。,3）目标函数 它为决策变量的线性函数，亦称为评价函数。基于所给问题的不同，可要求目标函数实现最大值或最小值。,具体的，线性规划的数学模型的一般形式为：,A为技术系数矩阵（也称为消耗系数矩阵），简称为技术矩阵，,2.1 线性规划模型与图解法,矩阵形式：,向量形式：,其中：C=(c1,c2,cn)是n 维行向量，称为价值系数向量，简称为价值向量；,b=(b1,b2,bm)T是m 维
6、列向量,称为资源向量；,X=(x1,x2,xn)T称为决策向量；,2.1 线性规划模型与图解法,2.1.3 线性规划模型的标准型,为了讨论线性规划问题解的方便，一般把目标函数最大化、约束条件为等式、变量符号为非负的线性规划称为标准型，即：,线性规划的标准型的特点：目标函数是最大化类型；b0；约束条件均由等式组成；决策变量均为非负。,对于各种非标准形式的线性规划都可以通过适当的变换转化为等价的标准型问题，具体做法为：,l）目标函数的调整,若线性规划目标函数为最小，通过改变目标函数的符号，然后求最大。,例如原问题min z=3x1+5x2,可化为max z=-(3x1+5x2)。这样得到的新问题与
7、原问题具有同样的可行城和最优解（若存在），只是最优值（若存在）相差一个符号而已。,2.1 线性规划模型与图解法,2）约束条件为调整,如果线性规划具有“”不等式的约束，这时可引入一个松弛变量变为等式约束。,松弛变量表示在一个决策过程中资源消耗的剩余量。若为正，表示有剩余；若为零，表示没有剩余，其结果不影响收入，也不影响支出。因此，松弛变量本身是零价格的，表现在目标函数中，松弛变量的系数为零。,例如对约束4x1+2x214，加上松弛变量x3(0)，构成等式约束4x1+2x2+x3=14，同时规定目标函数中的价值系数c3=0，不改变原问题的最优解。,如果线性规划具有“”不等式的约束，这时可减去一个剩
8、余变量变为等式约束。,剩余变量表示在一个经济决策中超额满足最低需求的量。若为正，表示超额满足最低需求，若为负，表示没有满足最低需求，因此，剩余变量本身也是零价格的。,例如对约束4x1+2x214，减去剩余变量x3(0)，构成等式约束4x1+2x2-x3=14，同时规定目标函数中的价值系数c3=0。,3）决策变量的调整,若决策变量为xj0，引进新的非负变量xj，令xj=-xj，代入约束条件和目标函数中消去xj，这样xj0就化成xj0。,若xj为自由变量，这时需引入两个新的非负变量xj,xj”，令xj=xj-xj”，代入约束条件和目标函数中消去xj，同时，在约束条件中加入约束xj,xj”0。,2.
9、1 线性规划模型与图解法,【例2.3】将下列线性规划问题化成标准型,解 1）决策变量,2.1 线性规划模型与图解法,2）第一个约束引入松弛变量x4,第二个约束引入剩余变量x5;,3）目标函数min变为改变为max,2.1 线性规划模型与图解法,4）由于在第三个约束中资源量为6,也可以从实际意义考虑将第三个等式约束两边同乘以1,则该问题的标准形式为：,【注】求解所得最优值的相反数才是原问题的最优值，从而各种各样的线性规划问题都可转化为标准型。,2.1 线性规划模型与图解法,2.1.4 线性规划的图解法,对于只有两个变量的线性规划问题，可以直接使用图解法求解。图解法简单直观，对一般线性规划问题的求
10、解富有启发作用。,图解法可分三步进行：,1）在平面上建立直角坐标系；,2）根据约束条件画出相应的半平面，由这些半平面共同确定的区域即为可行域；,3）画出目标函数的等值线，然后沿目标函数要求的方向平移至与可行域边界相切的点，该点就是最优解，相应的坐标即为最优解。,2.1 线性规划模型与图解法,【例2.4】求解线性规划问题,解 应用图解法求解线性规划，分下面三步求解。,1）建立直角坐标系,2）确定可行域 令3个约束条件为等式，得到3条直线，画出第一象限的三个不等式区域，他们的交集就是可行域，亦即区域OABCD，其内部及边界上的每一个点都是线性规划的解。,3）确定最优解 目标函数的等值线z=40 x
11、1+50 x2(z取定某一个常值)的法线方向(40,50)是函数值增加最快的方向。沿着函数的梯度方向移动，函数值会增大，当移动到点顶点C(15,15/2)，再继续移动就离开区域了。于是点C就是最优解，最优值为z=4015+5015/2=975,2.1 线性规划模型与图解法,2.1 线性规划模型与图解法,【例2.5】求解线性规划问题,解 该题将例2.4中的目标函数变为z=40 x1+80 x2,可行域不变。,由于目标函数等直线z=40 x1+80 x2与直线x1+2x2=30平行，,当目标函数的等值线与直线x1+2x2=30重合时，,目标函数z=40 x1+80 x2达到最大值1200，,于是线
12、段BC上的每一个点均为该问题的最优解。,特别地，线段BC的两个端点，即可行区域的两个顶点B(6,12),C(15,15/2)，均是该线性规划问题的最优解。此时，最优解不唯一。,2.1 线性规划模型与图解法,【例2.6】求解线性规划问题,解 由于可行域无界,目标函数z=2x1+4x2沿着它的法线方向(2,4)移动，,移动可以无限制下去，而目标函数值一直增加，,所以该线性规划问题无有限最优解，有无界解，即该问题的目标函数无界。,2.1 线性规划模型与图解法,【例2.7】求解线性规划问题,解 约束条件互不相容，没有公共交点，可行域是一个空集，不存在满足条件的解，说明线性规划问题无解，没有最优解，如图所示。,说明：由例题的直观图形容易得到下面几个重要结论：,1）线性规划的可行域是若干个半平面的交集，它形成了一个多面凸集（可能是空集）。,2）对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。这种情况下包含两种情况：有唯一解和有无穷多解。,3）如果可行域无界，线性规划问题的目标函数可能无界。,4）可行域为空集，无最优解。,
