本章学习的目的使学员掌握线性规划问题的一般定义和数学模型的特征。掌握两个变量的线性规划问题的几何作图求解方法。重点是数学模型的建立和两个变量线性规划模型的可行域的特点及最优解存在的位置。同时理解最优解在极点达到这一结果对于一般线性规划也成立。熟悉计算机QM软件求解LP问题的步骤。第二章、线性规划LP(LinearProgramming)线性规划是一种对问题进行求解的方法，可以帮组决策者制定决策.1947年丹捷格(G.B.Dantzig)提出一般线性规划问题的求解方法——单纯形法后，LP在理论上趋向成熟。在世界500家大公司中，有85%使用LP方法。一、使用线性规划方法的典型情况。二、线性规划问题的提出及数学模型解：假设x1、x2分别表示在计划期内生产产品甲、乙的数量，则该计划问题可用如下数学模型表示为：目标函数MaxZ=2x1+3x2约束条件例2M&D公司生产两种产品A和B，基于对现有的存储水平和下一个月的市场潜力的分析，M&D公司管理层决定A和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所示，为了避免过多使用某种饲料，规定混合饲料中各种饲料的最高含量分别为：50、60、50、70、40克。求满足动物需要且费用最低的饲料配方。例4某昼夜服务的公交线路每天每个时间段内所需司机和乘务人员数如下：假设司机和乘务人员分别在各时间段一经上班，就连续工作八小时。问该公司怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员。解：设表示第班次时开始上班的司机和乘务人员数，在第班工作的人数应包括——第班才开始上班的人数和第-1班次开始上班的还需继续工作的人数。这样建立的数学模型为：以这些例子可以看出,它们的共同特征是:每个问题都用一组决策变量(x1,x2,···,xn)表示某一方案,这组未知数的值在满足限制条件下，就代表一个具体的方案,通常要求这些未知数取值是非负的。(3)都有一个目标要求,并且这个目标可表示为这组决策变量的线性函数(称为目标函数),按研究问题的不同要求目标函数实现最大化或最小化。三、图解法对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。我们可以参考教材具体给出求解的方法。图解法简单直观，有助于了解线性规划问题求解的基本原理.图解法求模型的解可行解(FeasibleSolution)：满足所有约束条件的解为可行解。可行域(Feasibleregion)：可行解所组成的区域称为可行域。图解法步骤：·画出满足每个约束条件的范围。·确定可行域·画出一条目标函数的直线·平移目标函数直线，使其可行域在直线的一侧。·确定最优解。松弛变量(SlackVariable)当线性规划的所有约束条件都用等式来表达时，这种形式就称为标准型。注释在线性规划的标准型中，松弛变量的系数为零，这个零表示未使用的资源，不对目标函数产生任何影响，但在实际中，可以出售未使用的资源，以使公司获利，从这一角度看，松弛变量就变成了表示公司可以出售多少未使用的资源的决策变量。极点和最优解(ExtremePointandoptimal)对于上述问题现在假设每生产一单位产品Ⅰ可获利1元，每生产一单位产品Ⅱ可获利5元，约束条件不变，显然约束条件不变，可行域就不变，此时目标函数的改变对最优解产生什么影响呢？我们仍用图解法进行求解线性规划问题的最优解一定可以在可行域的一个极点上找到练习：找可行域的极点，并通过计算和比较极点所对应的目标函数值来求最优解。一个简单的最小化问题M&D公司生产两种产品----。用图解法进行求解通过作图法我们找到了最小成本的解为：（250，100）最小成本为800。同时，我们也发现最优解仍然在极点出。剩余变量(SurplusVariable)通过对该公司的最优解的分析，我们知道最大生产量已经达到，需要的生产时间是600小时，此外，A的产量已达到其最低要求，事实上，已经超过了A的最小限额250-125=125，多生产出来的这一部分产品就称为剩余。由于剩余不参与目标函数值的计算，因此剩余变量在目标函数中的系数为零，将该模型引入松弛变量和剩余变量后为：特殊情况无穷多最优解(Alternativeoptimalsolu