管理运筹学线性规划详解

管理运筹学线性规划详解演示文稿第一页，共31页。优选管理运筹学线性规划第二页，共31页。

一、使用线性规划方法的典型情况。生产的组织与计划问题运输问题合理下料问题配料问题布局问题营销管理问题投资组合问题分派问题第三页，共31页。二、线性规划问题的提出及数学模型例1某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时和A、B两种原材料的消耗以及资源的限制情况，如表1-1所示：问工厂应分别生产多少个甲产品和乙产品才能使工厂获利最大？

第四页，共31页。甲乙资源限制设备128台时原料A4016千克原料B0412千克利润23表1-1

第五页，共31页。解：假设x1、x2分别表示在计划期内生产产品甲、乙的数量，则该计划问题可用如下数学模型表示为：目标函数Max

Z=2x1+3x2

约束条件第六页，共31页。例2

M&D公司生产两种产品A和B，基于对现有的存储水平和下一个月的市场潜力的分析，M&D公司管理层决定A和B的总产量至少要达到350千克，此外，公司的一个客户订了125千克的A产品必须首先满足。每千克A、B产品的制造时间分别为2小时和1小时，总工作时间为600小时。每千克A、B产品的原材料成本分别为2$和3$。确定在满足客户要求的前提下，成本最小的生产计划。

第七页，共31页。第八页，共31页。例3营养问题

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

第九页，共31页。第十页，共31页。第十一页，共31页。以这些例子可以看出,它们的共同特征是:每个问题都用一组决策变量(x1,x2,···,xn)表示某一方案,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。

(2)存在一定的限制条件(称为约束条件),这些条件都可以用关于决策变量的一组线性等式或不等式来表示。第十二页，共31页。(3)都有一个目标要求,并且这个目标可表示为这组决策变量的线性函数(称为目标函数),按研究问题的不同要求目标函数实现最大化或最小化。

满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为(1.1)和(1.2)形式。在该模型中,方程(1.1)称为目标函数(1.2)称为约束条件。第十三页，共31页。三、图解法

对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。

我们可以参考教材具体给出求解的方法。图解法简单直观，有助于了解线性规划问题求解的基本原理.第十四页，共31页。图解法求模型的解

可行解(FeasibleSolution)：满足所有约束条件的解为可行解。

可行域(Feasibleregion)：可行解所组成的区域称为可行域。

图解法步骤：

·画出满足每个约束条件的范围。

·确定可行域

·画出一条目标函数的直线

·平移目标函数直线，使其可行域在直线的一侧。

·确定最优解。

第十五页，共31页。第十六页，共31页。松弛变量(SlackVariable)

第十七页，共31页。当线性规划的所有约束条件都用等式来表达时，这种形式就称为标准型。

注释

在线性规划的标准型中，松弛变量的系数为零，这个零表示未使用的资源，不对目标函数产生任何影响，但在实际中，可以出售未使用的资源，以使公司获利，从这一角度看，松弛变量就变成了表示公司可以出售多少未使用的资源的决策变量。

第十八页，共31页。极点和最优解(ExtremePointandoptimal)

对于上述问题现在假设每生产一单位产品Ⅰ可获利1元，每生产一单位产品Ⅱ可获利5元，约束条件不变，显然约束条件不变，可行域就不变，此时目标函数的改变对最优解产生什么影响呢？

我们仍用图解法进行求解

第十九页，共31页。线性规划问题的最优解一定可以在可行域的一个极点上找到

练习：找可行域的极点，并通过计算和比较极点所对应的目标函数值来求最优解。

第二十页，共31页。一个简单的最小化问题

M&D公司生产两种产品----。第二十一页，共31页。用图解法进行求解

通过作图法我们找到了最小成本的解为：（250，100）最小成本为800。同时，我们也发现最优解仍然在极点出。

第二十二页，共31页。剩余变量(SurplusVariable)

通过对该公司的最优解的分析，我们知道最大生产量已经达到，需要的生产时间是小时，此外，A的产量已达到其最低要求，事实上，已经超过了A的最小限额250-125=125，多生产出来的这一部分产品就称为剩余。由于剩余不参与目标函数值的计算，因此剩余变量在目标函数中的系数为零，将该模型引入松弛变量和剩余变量后为：

第二十三页，共31页。第二十四页，共31页。特殊情况

无穷多最优解(Alternativeoptimalsolution)

第二十五页，共31页。最优解为:A(2,3),B(4,2)。而且在A、B两点之间的任何点也都是最优解，因为线段A、B及其内部的点都使得目标函数值最大。对于一个LP问题来讲，有无穷多最优解是一个好消息，有多种决策变量的组合可供选择。

第二十六页，共31页。无可行解(InfeasibilitySolution)

无可行解是指不存在满足全部约束条件的解。在图形中，无可行解是指可行域不存在。也就是说，没有任何一个点能够同时满足所有约束条件。

举例说明这一情况。在2.1中如果我们增加约束条件，生产Ⅰ、Ⅱ两种产品至少分别需要3千克。

第二十七页，共31页。现有的资源无法生产满足需要（3，3）的产品，此外，我们可以准确地告诉管理者要生产(3,3)换需要多少资源

第二十