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

《《管理运筹学》第2章线性规划》由会员分享，可在线阅读，更多相关《《管理运筹学》第2章线性规划（36页珍藏版）》请在文档大全上搜索。

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)称为约称为约束条件。束条件。三、图解法 对于简单的线性规划问题(只有两个决策变量的线性规划问题),我们通过图解法可以对它进行求解。 我们可以参考教材具体给出求解的方法。图解法简单直观，有助于了解线性规划问题求解的基本原理.图解法求模型的解图解法