1、2.1 线性规划模型与图解法线性规划模型与图解法 线性规划的研究内容可归纳为线性规划的研究内容可归纳为两个方面两个方面：一是资源的数量：一是资源的数量已定，如何合理利用、调配，使任务完成的最多，才能更有效已定，如何合理利用、调配，使任务完成的最多，才能更有效地运用有限的资源以更高水平达到目标；二是系统的任务已定地运用有限的资源以更高水平达到目标；二是系统的任务已定，如何合理筹划，精细安排，用最少的资源，如何合理筹划，精细安排，用最少的资源(人力、物力和财人力、物力和财力力)去实现这个任务；去实现这个任务；2.1.1 问题的引入问题的引入 【例例2.1】（生产计划问题）某企业生产（生产计划问题）
2、某企业生产l、2和和3三种产品，三种产品，每种产品需经过三道工序，每件产品在每道工序中的工时定额每种产品需经过三道工序，每件产品在每道工序中的工时定额、每道工序在每周可利用的有效工时和每件产品的利润见下表、每道工序在每周可利用的有效工时和每件产品的利润见下表。问每种产品各生产多少。问每种产品各生产多少,可使这一周内生产的产品所获利润最可使这一周内生产的产品所获利润最大？大？2.1 线性规划模型与图解法线性规划模型与图解法 定额定额(工时工时/件件)产品型号产品型号每周可利用每周可利用的有效工时的有效工时123工序工序A1.21.01.15400B0.70.90.62800C0.90.81.03
3、600利润（元利润（元/件）件）101512生产计划资源表生产计划资源表 【分析分析】该问题主要是要把有限的工时资源合理地分配到三该问题主要是要把有限的工时资源合理地分配到三种产品的生产活动上去，以期望获得最多的利润。根据问题的种产品的生产活动上去，以期望获得最多的利润。根据问题的要求，旨在获得最大利润，也就是说，在资源约束的条件下，要求，旨在获得最大利润，也就是说，在资源约束的条件下，尽可能生产更多的产品，以获得最大的利润，实现工厂利润最尽可能生产更多的产品，以获得最大的利润，实现工厂利润最大化的目标，大化的目标，2.1 线性规划模型与图解法线性规划模型与图解法 首先引进首先引进决策变量决策
4、变量：设一周内企业各产品的生产件数为设一周内企业各产品的生产件数为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.1x3，它不应超过
5、工序它不应超过工序A在一周内所允许的在一周内所允许的工作时间工作时间5400工时，于是，得工序工时，于是，得工序A加工产品的约束条件：加工产品的约束条件：54001.10.12.1321xxx 同理，对工序同理，对工序B和和C有以下约束条件：有以下约束条件：28006.09.07.0321xxx36000.18.09.0321xxx2.1 线性规划模型与图解法线性规划模型与图解法 再者，还有一些变量本身的约束，再者，还有一些变量本身的约束，xj(j=1,2,3)只能取非负只能取非负值，故有下列非负约束条件：值，故有下列非负约束条件：0,0,0321xxx 最后确定产品生产的效益，若用最后确定产
6、品生产的效益，若用z表示工厂一周内生产三种表示工厂一周内生产三种产品所能获得的利润，则有：产品所能获得的利润，则有：321121510 xxxz 综上所述，得到生产计划问题的综上所述，得到生产计划问题的数学模型数学模型：3,2,1036000.18.09.028006.09.07.054001.10.11.1.121510max321321321321jxxxxxxxxxxtsxxxzj 其中其中s.t.是英文是英文“subject to”（受约束于）的缩写。（受约束于）的缩写。2.1 线性规划模型与图解法线性规划模型与图解法 【例例2.22.2】（营养配餐问题）假定一个成年人每天需要从（营养
7、配餐问题）假定一个成年人每天需要从食物中获取食物中获取30003000卡路里热量，卡路里热量，5555克蛋白质和克蛋白质和800800毫克钙。如果毫克钙。如果市场上只有四种食品可选，它们每千克所含热量和营养成份以市场上只有四种食品可选，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？购买食品的费用最小？食品的营养构成表食品的营养构成表序号序号 食品名称食品名称 热量热量(卡路里卡路里)蛋白质蛋白质(g)钙钙(mg)价格价格(元元)1猪肉猪肉100050400102鸡蛋鸡蛋8006020
8、063大米大米9002030034白菜白菜200105002 则相应的则相应的数学模型为：数学模型为：2.1 线性规划模型与图解法线性规划模型与图解法 解解 设设xj(j=1,2,3,4)为第为第 j 种食品每天的购买量，种食品每天的购买量，432123610minxxxxz.ts300020090080010004321xxxx55102060504321xxxx8005003002004004321xxxx0,0,0,04321xxxx2.1.2 线性规划模型线性规划模型 上面所建立的数学模型中目标函数和约束条件都是线性函上面所建立的数学模型中目标函数和约束条件都是线性函数，故称之为数，故
9、称之为线性规划线性规划，简记为，简记为LP。线性规划模型具有下列线性规划模型具有下列三三个要素个要素：l）决策变量决策变量 这些决策变量的一组定值代表所给问题的一个这些决策变量的一组定值代表所给问题的一个具体解决方案。一般来说，这些决策变量都是非负变量，如果在具体解决方案。一般来说，这些决策变量都是非负变量，如果在模型中变量与的符号不受限制，即变量取正值、取负值或取零都模型中变量与的符号不受限制，即变量取正值、取负值或取零都可以，把它称为自由变量，可以写入规划模型，也可省略。可以，把它称为自由变量，可以写入规划模型，也可省略。2.1 线性规划模型与图解法线性规划模型与图解法 2）约束条件约束条
10、件 这些约束条件都为线性等式或线性不等式。它这些约束条件都为线性等式或线性不等式。它们反映了所给问题对资源的客观限制及对所要完成的任务的各类们反映了所给问题对资源的客观限制及对所要完成的任务的各类要求，称为要求，称为系统约束系统约束；对决策变量的符号要求也属于约束条件，；对决策变量的符号要求也属于约束条件，称为称为符号约束符号约束。3）目标函数目标函数 它为决策变量的线性函数，亦称为它为决策变量的线性函数，亦称为评价函数评价函数。基于所给问题的不同，可要求目标函数实现最大值或最小值。基于所给问题的不同，可要求目标函数实现最大值或最小值。具体的，线性规划的数学模型的一般形式为：具体的，线性规划的
11、数学模型的一般形式为：mnmnmmnnnnnnbxaxaxabxaxaxabxaxaxatsxcxcxcz),(),(),(.)max(222122222221112122112211min或 A为为技术系数矩阵技术系数矩阵（也称为消（也称为消耗系数矩阵），简称为耗系数矩阵），简称为技术矩阵技术矩阵，2.1 线性规划模型与图解法线性规划模型与图解法 矩阵形式：矩阵形式：0XbAX),(.)max(mintsCXz或向量形式：向量形式：njxxtsCXzjjnj,2,10),(.min)max(1bPj或 其中：其中：C=(=(c1,c2,cn)是是n 维行向量维行向量，称为称为价值系数向量价值
12、系数向量，简称为简称为价值向量价值向量；b=(=(b1,b2,bm)T是是m 维列向量维列向量,称为称为资源向量资源向量；X=(=(x1,x2,xn)T称为称为决策向量决策向量；)(212222111211n21PPPAmnmmnnaaaaaaaaamiiiaaa21iP2.1 线性规划模型与图解法线性规划模型与图解法 2.1.3 线性规划模型的标准型线性规划模型的标准型 为了讨论线性规划问题解的方便，一般把目标函数最大化、为了讨论线性规划问题解的方便，一般把目标函数最大化、约束条件为等式、变量符号为非负的线性规划称为约束条件为等式、变量符号为非负的线性规划称为标准型标准型，即，即：0XbAX
13、CXzmax 线性规划的线性规划的标准型的特点标准型的特点：目标函目标函数是最大化类型；数是最大化类型；b0；约束条件均由约束条件均由等式组成；等式组成；决策变量均为非负。决策变量均为非负。对于各种非标准形式的线性规划都可以对于各种非标准形式的线性规划都可以通过适当的变换转化通过适当的变换转化为等价的标准型为等价的标准型问题，具体做法为：问题，具体做法为：l）目标函数的调整目标函数的调整 若线性规划目标函数为最小，通过改变目标函数的符号，若线性规划目标函数为最小，通过改变目标函数的符号，然后求最大。然后求最大。例如原问题例如原问题min z=3x1+5x2,可化为可化为max z=-(3x1+
14、5x2)。这样得到的新问题与原问题具有同样的可行城和最优解（若这样得到的新问题与原问题具有同样的可行城和最优解（若存在），只是最优值（若存在）相差一个符号而已。存在），只是最优值（若存在）相差一个符号而已。2.1 线性规划模型与图解法线性规划模型与图解法 2）约束条件为调整约束条件为调整 如果线性规划具有如果线性规划具有“”不等式的约束，这时可引入一个不等式的约束，这时可引入一个松弛变量松弛变量变为等式约束。变为等式约束。松弛变量表示在一个决策过程中松弛变量表示在一个决策过程中资源消耗的剩余量。若为正，表示有资源消耗的剩余量。若为正，表示有剩余；若为零，表示没有剩余，其结剩余；若为零，表示没有
15、剩余，其结果不影响收入，也不影响支出。因此，果不影响收入，也不影响支出。因此，松弛变量本身是零价格的，表现在目松弛变量本身是零价格的，表现在目标函数中，松弛变量的系数为零。标函数中，松弛变量的系数为零。例如对约束例如对约束4 4x1+2x214，加上松弛变量，加上松弛变量x3(0)，构成等式约束，构成等式约束4 4x1+2x2+x3=14 ，同时规定目标函数中，同时规定目标函数中的价值系数的价值系数c3 =0 ，不改变原问题的最优解。，不改变原问题的最优解。如果线性规划具有如果线性规划具有“”不等式的约束，这时可减去一不等式的约束，这时可减去一个个剩余变量剩余变量变为等式约束。变为等式约束。剩
16、余变量表示在一个经济决策中剩余变量表示在一个经济决策中超额满足最低需求的量。若为正，表超额满足最低需求的量。若为正，表示超额满足最低需求，若为负，表示示超额满足最低需求，若为负，表示没有满足最低需求，因此，剩余变量没有满足最低需求，因此，剩余变量本身也是零价格的。本身也是零价格的。例如对约束例如对约束4 4x1+2x214，减去剩余变，减去剩余变量量x3(0)，构成等式约束，构成等式约束4 4x1+2x2-x3=14 ，同时规定目标函数，同时规定目标函数中的价值系数中的价值系数c3 =0 。3）决策变量的调整决策变量的调整 若决策变量为若决策变量为xj0，引进新的非负变量，引进新的非负变量xj
17、，令令xj=-=-xj ，代入约束条件和目标函数中消去代入约束条件和目标函数中消去xj ，这样这样xj0就化成就化成xj0 。若若xj为自由变量，这时需引入两个新的非负变量为自由变量，这时需引入两个新的非负变量xj,xj”，令令xj=xj-xj”，代入约束条件和目标函数中消去，代入约束条件和目标函数中消去xj ，同时，同时，在约束条件中加入约束在约束条件中加入约束xj,xj”0 。2.1 线性规划模型与图解法线性规划模型与图解法 【例例2.3】将下列线性规划问题化成标准将下列线性规划问题化成标准型 无约束321321321321321,0,0632442392.32minxxxxxxxxxxx
18、xtsxxxz 解解 1）决策变量）决策变量 33311,xxxxx0,0,0,06)(3244)(239)(2.)(32min332133213132133213321xxxxxxxxxxxxxxxxtsxxxxz2.1 线性规划模型与图解法线性规划模型与图解法 2）第一个约束引入松弛变量）第一个约束引入松弛变量x4,第二个约束引入剩余变量第二个约束引入剩余变量x5;0,0,0,0,0,06)(3244)(239)(2.00)(32min543321332153132143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz 3）目标函数）目标函数min变为改变为变为
19、改变为max 0,0,0,0,0,06)(3244)(239)(2.00)(32max543321332153132143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz2.1 线性规划模型与图解法线性规划模型与图解法 4）由于在第三个约束中资源量为）由于在第三个约束中资源量为6,也可以从实际意义考也可以从实际意义考虑将第三个等式约束两边同乘以虑将第三个等式约束两边同乘以1,则该问题的标准形式为：则该问题的标准形式为：0,0,0,0,0,06)(3244)(239)(2.00)(32max543321332153132143321543321xxxxxxxxxxxx
20、xxxxxxxxtsxxxxxxz 【注注】求解所得最优值的相反数才是原问题的最优值，从求解所得最优值的相反数才是原问题的最优值，从而各种各样的线性规划问题都可转化为标准型。而各种各样的线性规划问题都可转化为标准型。2.1 线性规划模型与图解法线性规划模型与图解法 2.1.4 线性规划的图解法线性规划的图解法 对于只有两个变量的线性规划问题，可以直接使用图解法对于只有两个变量的线性规划问题，可以直接使用图解法求解。图解法简单直观，对一般线性规划问题的求解富有启发求解。图解法简单直观，对一般线性规划问题的求解富有启发作用。作用。图解法可分三步进行：图解法可分三步进行：1）在平面上建立直角坐标系；
21、在平面上建立直角坐标系；2）根据约束条件画出相应的半平面，由这些半平面共同确根据约束条件画出相应的半平面，由这些半平面共同确定的区域即为定的区域即为可行域可行域；3）画出目标函数的等值线，然后沿目标函数要求的方向平画出目标函数的等值线，然后沿目标函数要求的方向平移至与可行域边界相切的点，该点就是最优解，相应的坐标即为移至与可行域边界相切的点，该点就是最优解，相应的坐标即为最优解。最优解。2.1 线性规划模型与图解法线性规划模型与图解法 【例例2.42.4】求解线性规划问题求解线性规划问题 0,02426023302.5040max212212121xxxxxxxtsxxz 解解 应用图解法求解
22、线性规划，应用图解法求解线性规划，分下面三步求解。分下面三步求解。1）建立直角坐标系）建立直角坐标系 1x2xo 2）确定可行域）确定可行域 令令3个约束条件为等式，得到个约束条件为等式，得到3条直线，画条直线，画出第一象限的三个不等式区域，他们的交集出第一象限的三个不等式区域，他们的交集就是可行域，亦即区域就是可行域，亦即区域OABCD，其内部及，其内部及边界上的每一个点都是线性规划的解。边界上的每一个点都是线性规划的解。301530221 xx3020602321 xx122422xABCD 3）确定最优解）确定最优解 目标函数的等值线目标函数的等值线z=40 x1+50 x2(z z取定
23、某一取定某一个常值个常值)的法线方向的法线方向(40,50)(40,50)是函数值增加最是函数值增加最快的方向。沿着函数的梯度方向移动，函数快的方向。沿着函数的梯度方向移动，函数值会增大，当移动到点顶点值会增大，当移动到点顶点C(15,15/2)，再再继续移动就离开区域了。于是点继续移动就离开区域了。于是点C就是最优就是最优解，最优值为解，最优值为z=40z=4015+5015+5015/2=97515/2=975 2.1 线性规划模型与图解法线性规划模型与图解法 2.1 线性规划模型与图解法线性规划模型与图解法 【例例2.52.5】求解线性规划问题求解线性规划问题 0,02426023302
24、.8040max212212121xxxxxxxtsxxz 解解 该题将例该题将例2.4中的目标中的目标函数变为函数变为z=40 x1+80 x2 ,可行域不可行域不变。变。由于目标函数等直线由于目标函数等直线z=40 x1+80 x2与直线与直线x1+2x2=30平行，平行，当目标函数的等值线与直线当目标函数的等值线与直线x1+2x2=30重合时，重合时，1x2xo301530221 xx3020602321 xx122422xABCD 目标函数目标函数z=40 x1+80 x2达到最大值达到最大值1200，于是线段于是线段BC上的每上的每一个点均为该问题的最优解。一个点均为该问题的最优解。
25、特别地，线段特别地，线段BC的两个端点，即可的两个端点，即可行区域的两个顶点行区域的两个顶点B(6,12),C(15,15/2)，均是该线性规划问题的最，均是该线性规划问题的最优解。此时，最优解不唯一。优解。此时，最优解不唯一。2.1 线性规划模型与图解法线性规划模型与图解法 【例例2.62.6】求解线性规划问题求解线性规划问题 0,2282.42max21212121xxxxxxtsxxz 解解 由于由于可行域无界可行域无界,1x2xo88221 xx42221xx2 目目标函数标函数z=2x1+4x2沿着它的法线沿着它的法线方向方向(2,4)移动，移动，移动可以无移动可以无限制下去，而目标
26、函数值一限制下去，而目标函数值一直增加，直增加，所以该线性规划问所以该线性规划问题无有限最优解，有题无有限最优解，有无界解无界解，即该问题的目标函数无界。，即该问题的目标函数无界。2.1 线性规划模型与图解法线性规划模型与图解法 【例例2.72.7】求解线性规划问题求解线性规划问题 0,22.24max212121xxxxtsxxz 解解 约束条件互不相容，没有约束条件互不相容，没有公共交点，可行域是一个空集，不存在满足条件的公共交点，可行域是一个空集，不存在满足条件的解，说明线性规划问题无解，没有最优解，如图所示。解，说明线性规划问题无解，没有最优解，如图所示。1x2xo12221xx2 说
27、明说明：由例题的直观图形容易得到下面几个重要结论：由例题的直观图形容易得到下面几个重要结论：1）线性规划的可行域是若干个半平面的交集，它形成了一）线性规划的可行域是若干个半平面的交集，它形成了一个多面凸集（可能是空集个多面凸集（可能是空集）。）。2）对于给定的线性规划问题，如果它有最优解，最优解总）对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。这种情况下包含两种情况：可以在可行域的某个顶点上达到。这种情况下包含两种情况：有唯一解和有无穷多解。有唯一解和有无穷多解。3）如果可行域无界，线性规划问题的目标函数可能无界。）如果可行域无界，线性规划问题的目标函数可能无界。4）可行域为空集，无最优解。）可行域为空集，无最优解。
