《管理运筹学》第2章线性规划

1、 本章学习的目的使学员掌握线性规划问本章学习的目的使学员掌握线性规划问题的一般定义和数学模型的特征。掌握两题的一般定义和数学模型的特征。掌握两个变量的线性规划问题的几何作图求解方个变量的线性规划问题的几何作图求解方法。重点是数学模型的建立和两个变量线法。重点是数学模型的建立和两个变量线性规划模型的可行域的特点及最优解存在性规划模型的可行域的特点及最优解存在的位置。同时理解最优解在极点达到这一的位置。同时理解最优解在极点达到这一结果对于一般线性规划也成立。熟悉计算结果对于一般线性规划也成立。熟悉计算机机QMQM软件求解软件求解LPLP问题的步骤。问题的步骤。第二章、线性规划第二章、线性规划LPL

2、P(Linear Programming) 线性规划是一种对问题进行求解的方法，线性规划是一种对问题进行求解的方法，可以帮组决策者制定决策可以帮组决策者制定决策.1947.1947年丹捷格年丹捷格( (G.B.G.B.DantzigDantzig) )提出一般线性规划问题的求提出一般线性规划问题的求解方法解方法单纯形法后，单纯形法后，LPLP在理论上趋向在理论上趋向成熟。成熟。在世界在世界500500家大公司中，有家大公司中，有85%85%使用使用LPLP方法。方法。一、使用线性规划方法的典型情况。一、使用线性规划方法的典型情况。生产的组织与计划问题运输问题合理下料问题配料问题布局问题营销管理

3、问题投资组合问题分派问题二、线性规划问题的提出及数学模型线性规划问题的提出及数学模型例例1 1 某工厂在计划期内要安排生产甲、某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要乙两种产品，已知生产单位产品所需要的设备台时和的设备台时和A A、B B两种原材料的消耗以两种原材料的消耗以及资源的限制情况，如表及资源的限制情况，如表1-11-1所示：所示： 问工厂应分别生产多少个甲产品和乙产问工厂应分别生产多少个甲产品和乙产品才能使工厂获利最大？品才能使工厂获利最大？甲乙资源限制设备128台时原料A4016千克原料B0412千克利润23表1-1解：假设 x1、x2分别表示在计划期内生产

4、产品甲、乙的数量，则该计划问题可用如下数学模型表示为： 目标函数 Max Z = 2x1 +3x2 约束条件0,12416482212121xxxxxx例例2 2 M&D公司生产两种产品A和B，基于对现有的存储水平和下一个月的市场潜力的分析，M&D公司管理层决定A和B的总产量至少要达到350千克，此外，公司的一个客户订了125千克的A产品必须首先满足。每千克A、B产品的制造时间分别为2小时和1小时，总工作时间为600小时。每千克A、B产品的原材料成本分别为2$和3$。确定在满足客户要求的前提下，成本最小的生产计划。解：设产品 A、B 的产量分别为y, x。则，数学模型为： 06

5、00235012532y, xyxyxxyxZmin 例例3 3 营养问题营养问题某公司饲养试验用的动物以供出售。已知这些动物的生长对饲料中的三种营养元素特别敏感，分别称为营养元素A、B、C。已求出这些动物每天至少需要700克营养元素A,30克可营养元素B，而营养元素C每天恰好为200克。现有五种饲料可供选择，各种饲料的营养元素及单价如下表2-2所示，为了避免过多使用某种元素，规定混合饲料中各种饲料的最高含量分别为：50、60、50、70、40克。求满足动物需要且费用最低的饲料配方。 1 2 3 4 5 需求 A 3 2 1 6 18 700 B 1 0.5 0.2 2 0.5 30 C 0.

6、5 1 0.2 2 0.8 200 价格 2 7 4 9 5 解：设54321 ,jxj为每天混合饲料内包含的第j种饲料的数量 （克） 。 则营养问题的数学模型为： ,j ,xx ,x ,x ,x ,xx.xx.xx.x.xx.x.xxxxxxxxxxxZminj5432104070506050200802205030502205070018623594725432154321543215432154321 以这些例子可以看出以这些例子可以看出, ,它们的共同特征是它们的共同特征是: :(1)(1)每个问题都用一组决策变量每个问题都用一组决策变量( (x x1 1 , , x x2 2 , ,

7、 , , x xn n) )表示某一方案表示某一方案 , ,这组未知数的值就代这组未知数的值就代 表一个具体的方案表一个具体的方案, ,通常要求通常要求这些未知数取这些未知数取值是非负的值是非负的。 (2) (2) 存在一定的限制条件存在一定的限制条件( (称为约束条件称为约束条件),),这这些条件都可以用关于决策变量的一组线性等式些条件都可以用关于决策变量的一组线性等式或不等式来表示。或不等式来表示。(3) (3) 都有一个目标要求都有一个目标要求, ,并且这个目标可表示为这并且这个目标可表示为这组决策组决策 变量的线性函数变量的线性函数( (称为目标函数称为目标函数),),按研按研究问题的

8、不同要求目标函数实现最大化或最小化究问题的不同要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为划数学模型。其一般形式为(1.1)(1.1)和和(1.2)(1.2)形式。形式。 在该模型中在该模型中, ,方程方程(1.1)(1.1)称为目标函数称为目标函数(1.2)(1.2)称为约称为约束条件。束条件。三、图解法 对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。 我们可以参考教材具体给出求解的方法。图解法简单直观，有助于了解线性规划问题求解的基本原理.图解法求模型的解图解法

9、求模型的解可行解可行解( (Feasible Solution)Feasible Solution)：满足所有约束条件的解为满足所有约束条件的解为可行解。可行解。可行域可行域( (Feasible region)Feasible region)：可行解所组成的区域称为可可行解所组成的区域称为可行域。行域。图解法步骤：图解法步骤：画出满足每个约束条件的范围。画出满足每个约束条件的范围。确定可行域确定可行域画出一条目标函数的直线画出一条目标函数的直线平移目标函数直线，使其可行域在直线的一侧。平移目标函数直线，使其可行域在直线的一侧。确定最优解。确定最优解。松弛变量(Slack Variable)

10、除了最优解和利润外，管理者还想知道再此最优解情况下，设备台时数和原材料的使用数量， 约束条件 需要的资源数量 资源限制 剩余资源 设备台时 14+22=8 8 0 原料 A 44=16 16 0 原料 B 42=8 12 4 这里原料 B 有声誉，为 4 千克，称为该资源的松弛。任何一个小于等于形式的约束条件中未使用的能力称为该种约束条件的松弛变量。 通常松弛变量加入到线性规划的方程中，表示该资源的空闲能力。未使用的资源对利润没有贡献；因此，在目标函数里松弛变量的系数为零。显然有多少种资源（约束条件）就有多少个松弛变量。对于上述例题增加 3 个松弛变量。 5, 2 , 1, 012 4 16

11、4 82 00032max524132154321ixxxxxxxxxxxxxzi当线性规划的所有约束条件都用等式来表达时，这种形式就称为标准型。注释在线性规划的标准型中，松弛变量的系数为零，这个零表示未使用的资源，不对目标函数产生任何影响，但在实际中，可以出售未使用的资源，以使公司获利，从这一角度看，松弛变量就变成了表示公司可以出售多少未使用的资源的决策变量。极点和最优解(Extreme Point and optimal)对于上述问题现在假设每生产一单位产品可获利1元，每生产一单位产品可获利5元，约束条件不变，显然约束条件不变，可行域就不变，此时目标函数的改变对最优解产生什么影响呢？我们仍

12、用图解法进行求解线性规划问题的最优解一定可以在可线性规划问题的最优解一定可以在可行域的一个极点上找到行域的一个极点上找到练习：找可行域的极点，并通过计算和比较极点所对应的目标函数值来求最优解。一个简单的最小化问题 M&D公司生产两种产品 -。0600235012532y, xyxyxxyxZmin用图解法进行求解通过作图法我们找到了最小成本的解为：（250，100）最小成本为800。同时，我们也发现最优解仍然在极点出。剩余变量(Surplus Variable) 通过对该公司的最优解的分析，我们知道最大通过对该公司的最优解的分析，我们知道最大生产量已经达到，需要的生产时间是小时，此外，

13、生产量已经达到，需要的生产时间是小时，此外，A A的产量已达到其最低要求，事实上，已经超过的产量已达到其最低要求，事实上，已经超过了了A A的最小限额的最小限额250-125=125250-125=125，多生产出来的这一，多生产出来的这一部分产品就称为剩余。由于剩余不参与目标函数部分产品就称为剩余。由于剩余不参与目标函数值的计算，因此剩余变量在目标函数中的系数为值的计算，因此剩余变量在目标函数中的系数为零，将该模型引入松弛变量和剩余变量后为：零，将该模型引入松弛变量和剩余变量后为：0,6001 12350 111125 11000321321321sssyxsyxsyxsxsss3y2xmi

14、nZ特殊情况无穷多最优解(Alternative optimal solution) 如将 2.1 中的目标函数改变为： 212minxxZ 其它约束条件不变，此时图解法求解为 最优解为最优解为: :A(2,3),B(4,2)A(2,3),B(4,2)。而且在而且在A A、B B两两点之间的任何点也都是最优解，因为线段点之间的任何点也都是最优解，因为线段A A、B B及其内部的点都使得目标函数值最大。对及其内部的点都使得目标函数值最大。对于一个于一个LPLP问题来讲，有无穷多最优解是一问题来讲，有无穷多最优解是一个好消息，有多种决策变量的组合可供选个好消息，有多种决策变量的组合可供选择。择。

15、无可行解(Infeasibility Solution) 无可行解是指不存在满足全部约束条件的解。在图形中，无可行解是指可行域不存在。也就是说，没有任何一个点能够同时满足所有约束条件。 举例说明这一情况。在2.1中如果我们增加约束条件，生产、两种产品至少分别需要3千克。现有的资源无法生产满足需要（3，3）的产品，此外，我们可以准确地告诉管理者要生产(3,3)换需要多少资源资源最少资源需求可用资源需增加的资源设备台时13+23=981原料A43=1216无原料B34=121200,)3.1(24221212121xxxxxxxxZMax无界解无界解Unbounded solution) 我们通过

16、画图可以知道该线性规划问题的可行解所在的范围是无界的,目标函数值可以增大到无穷大,称这种情况为无界解或无最优解,如下图所示: x2 Z 0 x1 进一步来看,是否可行解所在的范围无界就意味着解 无界无界, ,找不到最优解呢找不到最优解呢? ?那也不一定那也不一定, ,如在如在(1.3)(1.3)中中, ,将目将目标函数由标函数由 Max ZMax Z = = x x1 1 + + x x2 2 改为改为 Min ZMin Z = = x x1 1 + + x x2 2 , ,则可行解所在的范围虽然无界则可行解所在的范围虽然无界, ,但有最优解但有最优解 x x1 1 = = x x2 2 =

17、= 0 ,0 ,即即 (0,0) (0,0)点点. . 当求解结果出现当求解结果出现(2)(2)、(3)(3)两种两种情况时情况时, ,一般均说明线性规划问题的数学模型存在错误一般均说明线性规划问题的数学模型存在错误, ,前者缺乏必要的约束条件前者缺乏必要的约束条件, ,后者是存在矛盾的约束条后者是存在矛盾的约束条件件, ,在建立数学模型时，应当注意。在建立数学模型时，应当注意。 幻灯片 18可行域可行域D非空无界：求非空无界：求max（1）无界解。求无界解。求min （1）有唯一解、）有唯一解、 （2 2）有无穷多组最优解有无穷多组最优解可行域可行域D空：空：无可行解无可行解可行域可行域D非