第二章线性规划.ppt

1、本章学习的目的使学员掌握线性规划问题的一般定义和数学模型的特征。掌握两个变量的线性规划问题的几何作图求解方法。重点是数学模型的建立和两个变量线性规划模型的可行域的特点及最优解存在的位置。同时理解最优解在极点达到这一结果对于一般线性规划也成立。熟悉计算机QM软件求解LP问题的步骤。,第二章、线性规划LP(Linear Programming) 线性规划是一种对问题进行求解的方法，可以帮组决策者制定决策.1947年丹捷格(G.B.Dantzig)提出一般线性规划问题的求解方法单纯形法后，LP在理论上趋向成熟。在世界500家大公司中，有85%使用LP方法。,一、使用线性规划方法的典型情况。,生产的组

2、织与计划问题 运输问题 合理下料问题 配料问题 布局问题 营销管理问题 投资组合问题 分派问题,二、线性规划问题的提出及数学模型,例1 某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时和A、B两种原材料的消耗以及资源的限制情况，如表1-1所示： 问工厂应分别生产多少个甲产品和乙产品才能使工厂获利最大？,表1-1,解：假设 x1、x2分别表示在计划期内生产产品甲、乙的数量，则该计划问题可用如下数学模型表示为： 目标函数 Max Z = 2x1 +3x2 约束条件,例2 M&D公司生产两种产品A和B，基于对现有的存储水平和下一个月的市场潜力的分析，M&D公司管理层决定A和

3、B的总产量至少要达到350千克，此外，公司的一个客户订了125千克的A产品必须首先满足。每千克A、B产品的制造时间分别为2小时和1小时，总工作时间为600小时。每千克A、B产品的原材料成本分别为2$和3$。确定在满足客户要求的前提下，成本最小的生产计划。,例3 营养问题某公司饲养试验用的动物以供出售。已知这些动物的生长对饲料中的三种营养元素特别敏感，分别称为营养元素A、B、C。已求出这些动物每天至少需要700克营养元素A,30克营养元素B，而营养元素C每天恰好为200克。现有五种饲料可供选择，各种饲料的营养元素及单价如下表2-2所示，为了避免过多使用某种饲料，规定混合饲料中各种饲料的最高含量分

4、别为：50、60、50、70、40克。求满足动物需要且费用最低的饲料配方。,例4 某昼夜服务的公交线路每天每个时间段内所需司机和乘务人员数如下：,假设司机和乘务人员分别在各时间段一经上班，就连续工作八小时。问该公司怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员。,解：设 表示第 班次时开始上班的司机和乘务人员数，在第 班工作的人数应包括第 班才开始上班的人数和第 -1班次开始上班的还需继续工作的人数。 这样建立的数学模型为：,以这些例子可以看出,它们的共同特征是: 每个问题都用一组决策变量(x1 , x2 , , xn)表示某一方案 ,这组未知数的值在满足限制条件下，就代表

5、一个具体的方案,通常要求这些未知数取值是非负的。,(2) 存在一定的限制条件(称为约束条件),这 些条件都可以用关于决策变量的一组线性等式 或不等式来表示。,(3) 都有一个目标要求,并且这个目标可表示为这组决策变量的线性函数(称为目标函数),按研究问题的不同要求目标函数实现最大化或最小化。,满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为(1.1)和(1.2)形式。 在该模型中,方程(1.1)称为目标函数(1.2)称为约束条件。,三、图解法 对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。 我们可以参考教材具体给出求解的方法。图解法简单直

6、观，有助于了解线性规划问题求解的基本原理.,图解法求模型的解可行解(Feasible Solution)：满足所有约束条件的解为可行解。可行域(Feasible region)：可行解所组成的区域称为可行域。图解法步骤：画出满足每个约束条件的范围。确定可行域画出一条目标函数的直线平移目标函数直线，使其可行域在直线的一侧。确定最优解。,松弛变量(Slack Variable),当线性规划的所有约束条件都用等式来表达时，这种形式就称为标准型。注释在线性规划的标准型中，松弛变量的系数为零，这个零表示未使用的资源，不对目标函数产生任何影响，但在实际中，可以出售未使用的资源，以使公司获利，从这一角度看，

7、松弛变量就变成了表示公司可以出售多少未使用的资源的决策变量。,极点和最优解(Extreme Point and optimal)对于上述问题现在假设每生产一单位产品可获利1元，每生产一单位产品可获利5元，约束条件不变，显然约束条件不变，可行域就不变，此时目标函数的改变对最优解产生什么影响呢？我们仍用图解法进行求解,线性规划问题的最优解一定可以在可行域的一个极点上找到练习：找可行域的极点，并通过计算和比较极点所对应的目标函数值来求最优解。,一个简单的最小化问题 M&D公司生产两种产品 -。,用图解法进行求解通过作图法我们找到了最小成本的解为：（250，100）最小成本为800。同时，我们也发现最

8、优解仍然在极点出。,剩余变量(Surplus Variable) 通过对该公司的最优解的分析，我们知道最大生产量已经达到，需要的生产时间是600小时，此外，A的产量已达到其最低要求，事实上，已经超过了A的最小限额250-125=125，多生产出来的这一部分产品就称为剩余。由于剩余不参与目标函数值的计算，因此剩余变量在目标函数中的系数为零，将该模型引入松弛变量和剩余变量后为：,特殊情况无穷多最优解(Alternative optimal solution),最优解为:A(2,3),B(4,2)。而且在A、B两点之间的任何点也都是最优解，因为线段A、B及其内部的点都使得目标函数值最大。对于一个LP

9、问题来讲，有无穷多最优解是一个好消息，有多种决策变量的组合可供选择。,无可行解(Infeasibility Solution) 无可行解是指不存在满足全部约束条件的解。在图形中，无可行解是指可行域不存在。也就是说，没有任何一个点能够同时满足所有约束条件。 举例说明这一情况。在2.1中如果我们增加约束条件，生产、两种产品至少分别需要3千克。,现有的资源无法生产满足需要（3，3）的产品，此外，我们可以准确地告诉管理者要生产(3,3)换需要多少资源,无界解Unbounded solution),我们通过画图可以知道该线性规划问题的可行解所在 的范围是无界的,目标函数值可以增大到无穷大,称这种 情况为

10、无界解或无最优解,如下图所示: x2 Z 0 x1 进一步来看,是否可行解所在的范围无界就意味着解,无界,找不到最优解呢?那也不一定,如在(1.3)中,将目标函数由 Max Z = x1 + x2 改为 Min Z = x1 + x2 ,则可行解所在的范围虽然无界,但有最优解 x1 = x2 = 0 ,即 (0,0)点. 当求解结果出现(2)、(3)两种情况时,一般均说明线性规划问题的数学模型存在错误,前者缺乏必要的约束条件,后者是存在矛盾的约束条件,在建立数学模型时，应当注意。,幻灯片 18,可行域D非空无界：求max（1）无界解。求min （1）有唯一解、 （2）有无穷多组最优解,可行域D空：无可行解,可行域D非空有界：（1）有唯一解、（2）有无穷多最优解,从图解法中可直观地看到: