管理数学课件4

第六章线性规划导论线性规划问题及其数学模型线性规划模型的图解法120世纪30年代，前苏联数学家康托洛维奇在生产组织与运输问题研究中，为线性规划做出了开拓性的工作。1947年，美国数学家G.B.Dantzig提出了线性规划问题的一般性解法即单纯形方法，奠定了线性规划的基础20世纪50年代后，随着电子计算机的迅速介入，线性规划得到了广泛的应用，在生产管理、资源配置等领域发挥着重要的作用2制造商希望建立一个生产时间表和库存计划，以满足未来一段时间的市场需求。最理想的情况是，既满足市场需求，同时又使生产和库存的成本最低财务分析师必须选择若干支股票和债券进行投资组合，使其所作的投资组合的回报最大营销经理希望将固定的广告预算在广播、电视、报纸、杂志等广告媒体中进行最好的分配，使广告效果最好某公司的仓库遍布全国，希望确定每个仓库到每个顾客的发货量，使总的运输成本最低3共同的特点：要求使某个量最大化或最小化－目标存在某些限制条件－约束条件4第一节

线性规划问题及其数学模型线性规划研究的问题可以归纳为以下两个方面：

◎在现有的资源条件下，如何充分利用资源，使任务或目标完成得更好◎在给定的目标或任务下，如何以最少的资源消耗，去实现该目标或任务线性规划就是求条件极值问题

5一、线性规划问题

例1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关数据如下表。试拟订使总收入最大的生产方案。

6资源单耗产品资源甲乙资源限量煤电油9445310360200300单位产品价格7127目标函数：总收入，记为z,则z=7x1+12x2，用Max来表示使函数极大化；决策变量：甲、乙产品的计划产量，记为；约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为解：设安排甲、乙产量分别为,总收入为，则模型为：8线性规划模型的三要素：◎决策变量：需决策的量，即待求的未知数◎目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示◎约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示9线性规划模型的一个基本特点：目标和约束均为变量的线性表达式如果模型中出现如的非线性表达式，则属于非线性规划。10

例2

某企业生产500克瓶装涂料，由A、B两种原料混合而成。工艺要求规定，A种原料最多不能超过350克，B种原料不能少于200克。已知A原料的购进价格为4元/克，B原料7元/克。假定两种原料的市场供应没有限制，不计工艺过程中的损耗，试问：每瓶涂料中两种原料各使用多少才能使加工成本最小。11解：设原料A、B的使用量分别为,总成本为w，则模型为：12二、线性规划模型的一般形与标准形

1.线性规划模型的一般形式：132.线性规划模型的标准形式：141）目标函数约定为求极大值2）所有约束方程都取等号3）变量取值满足非负性3.线性规划模型的标准化处理◎将极小化目标函数转化为极大化问题

◎把约束方程中的不等式转化为等式◎将变量中的非正限制或无限制转化为非负限制1516例217例3将下列线性规划模型变成标准形1819第二节

线性规划模型的图解法图解法是用画图的方式求解线性规划的一种方法只能用于解两个变量的线性规划问题主要作用在于能够直观地说明线性规划解的一些重要性质20一、图解法的基本步骤

1.做约束的图形

◎非负约束的图形

21以例1为例，其约束为

22◎资源约束的图形

23各约束的公共部分即模型的约束，称可行域。煤油电2.做目标的图形24对于目标函数任给二不同的值，便可做出相应的二直线，用虚线表示。分别令做出相应的利润线，便可看出增大的方向。利润线253.求出最优解

将目标直线向使目标优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点即最优解。如在例1中，是可行域的一个角点，经求解交出的二约束直线联立的方程可解得26◎由图解法的结果得到例1的最优解◎代入目标函数求得相应的最优目标值

◎经济含义：当甲生产20个单位，乙生产24个单位时，可获得最大的收入428约束条件最优方案所需资源可用资源未用资源煤27636084电2002000油300300027◎除了最优生产方案和与之相关的最大收入，可以将最优值带入约束条件来获得生产所需要的资源信息28约束条件松弛变量的值煤84电0油029◎对于该问题的标准形来说，对最优解，松弛变量的值是30最优解受电和油的约束，所以这个方案需要全部这两种资源，即他们没有松弛变量。另一方面，因为煤没有对最优解形成约束，所以有松弛或闲置资源存在煤电油练习：用图解法求解下面的线性规划3132

二、线性规划解的特性1.线性规划的约束集（即可行域）是凸多面体33

凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：凸集中的“极点”，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。2.线性规划的最优解（若存在的话）必能在可行域的角点获得34◎由图解法可知，只有当目标直线平移到边界时，才能使目标z达到最大限度的优化。◎使得在可行域中寻优的工作由“无限”上升为“有限”，从而为线性规划的算法设计提供了重要基础。3.

线性规划解的几种情形35①

唯一最优解②

多重最优解③

无解④

无有限最优解（无界解）问题：某公司生产高尔夫器材，它决定进入中等和高等价位的高尔夫球袋市场。具体生产信息如下：

36资源单耗产品工序标准袋高级袋工时切割与印染缝合成型检查与包装7/1011/25/61