线性规划模型和图解法全.ppt

《线性规划模型和图解法全.ppt》由会员分享，可在线阅读，更多相关《线性规划模型和图解法全.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter2 线性规划线性规划模型和图解法模型和图解法 (Linear Programming-LP)LP方法应用的典型情况方法应用的典型情况 LP的数学模型的数学模型 LP模型的模型的图解法图解法 LP问题的计算机求解问题的计算机求解本章主要内容：本章主要内容：本章主要内容：本章主要内容：Chapter2 线性规划线性规划模型和图解法模型和图解法 本章本章本章本章教学目的、重点、难点教学目的、重点、难点教学目的、重点、难点教学目的、重点、难点：掌握线性规划问题数学模型建立和线性规划模型的特征；线性规划模型的一般形式及标准形式，解的相关概念；掌握两个变量线性规划问题的几何作图求解方法；掌握

2、两个变量线性规划模型可行域的特点及最优解存在的位置；熟悉计算机QM软件求解线性规划问题的步骤。Page 3 1.规划问题规划问题阐述阐述生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资

3、金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大.）LP方法应用的典型情况方法应用的典型情况Page 42 在管理中一些典型的线性规划应用LP方法应用的典型情况方法应用的典型情况（1）生产的组织与计划问题：合理利用现有的生产的组织与计划问题：合理利用现有的 人人 力、物力、财力做出最优产品生产计划。力、物力、财力做出最优产品生产计划。（2）运输问题：

4、根据生产单位的产量和销售单位的）运输问题：根据生产单位的产量和销售单位的 销量，制订产品调运方案，使得总运费最小。销量，制订产品调运方案，使得总运费最小。（3）合理下料问题：如何裁截下料，既满足生产需）合理下料问题：如何裁截下料，既满足生产需要，又使得所用的材料数量最少。要，又使得所用的材料数量最少。（4）配料问题：在原料供应量限制和保证产品成分配料问题：在原料供应量限制和保证产品成分含量的前提下，获取最优配料方案含量的前提下，获取最优配料方案Page 52 在管理中一些典型的线性规划应用LP方法应用的典型情况方法应用的典型情况（5）营销管理问题：要从几种媒体中选择一种组合，）营销管理问题：要

5、从几种媒体中选择一种组合，使其在广告费用预算条件下广告效益最好。使其在广告费用预算条件下广告效益最好。（6）投资组合问题：选择一组股票或证券进行投资，）投资组合问题：选择一组股票或证券进行投资，使得有最大的回报率。使得有最大的回报率。（7）人力资源管理问题：在不同的时间段需要不同数）人力资源管理问题：在不同的时间段需要不同数量的劳动力，如何安排劳动力才能用最少的劳动力来满量的劳动力，如何安排劳动力才能用最少的劳动力来满足工作的需要。足工作的需要。Page 6线性规划问题的数学模型线性规划问题的数学模型Page 7线性规划问题的数学模型线性规划问题的数学模型易拉罐的设计理念易拉罐的设计理念具体下

6、料具体下料-模型的建立模型的建立Page 8线性规划问题的数学模型线性规划问题的数学模型例例1.2 某企业计划生产甲、乙两种产品。这些产品分某企业计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？设设 备备产产 品品 A B C D利润（元）利润（元）甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效

7、 台台 时时 12 8 16 122 线性规划模型的建立线性规划模型的建立Page 9线性规划问题的数学模型线性规划问题的数学模型解：设解：设x x1 1、x x2 2分别为甲、乙两种产分别为甲、乙两种产品的产量，则数学模型为：品的产量，则数学模型为：max Z=2xmax Z=2x1 1+3x+3x2 2 x x1 1 0,x 0,x2 2 0 0s.t.s.t.2x2x1 1+2x+2x2 2 12 12 x x1 1+2x+2x2 2 8 8 4x 4x1 1 16 16 4x 4x2 2 12 12Page 10线性规划问题的数学模型线性规划问题的数学模型3 3 3 3.线性规划的数学

8、模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量 Decision variables Decision variables 目标函数目标函数目标函数目标函数 Objective functionObjective function约束条件约束条件约束条件约束条件 ConstraintsConstraints其特征是：其特征是：其特征是：其特征是：（1 1 1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性

9、线性线性函数，函数，函数，函数，通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；通常是求最大值或最小值；（2 2 2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性线性线性不不不不等式或等式。等式或等式。等式或等式。等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？模型建立练习：模型建立练习：P13Page 11线性规划问题的数学模型线性规划问题的数学模型目标函数：目标函数：

10、目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：4 4.线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：Page 12线性规划问题的数学模型线性规划问题的数学模型向量形式：向量形式：向量形式：向量形式：其中：其中：Page 13线性规划问题的数学模型线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：Page 14线性规划问题的数学模型线性规划问题的数学模型5.线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1)目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2

11、)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。Page 15线性规划问题的数学模型线性规划问题的数学模型6 6 6 6 如何化标准形式如何化标准形式如何化标准形式如何化标准形式 目标函数的转换目标函数的转换如果是求极小值即如果是求极小值即 则可将目标函数乘以则可将目标函数乘以(-1)(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：变量的变换变量的变换Page 16线性

12、规划问题的数学模型线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量 变量变量 的的变换变换 可令可令 ，显然显然Page 17线性规划问题的数学模型线性规划问题的数学模型例例1.3 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式解解:（）因为（）因为x3无符号要求无符号要求，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以 用用 替换替换 ，且且 ;Page 18线性规划问题的数学模型线性规划问题的数学模型(2)第一个约束条件是第一个约

13、束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(3)第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变量左端减去剩余变量x5，x50；(4)第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将右将右端常数项化为正数；端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;Page 19线性规划问题的数学模型线性规划问题的数学模型

14、标准形式如下：标准形式如下：Page 20 学习要点学习要点小结小结：1.1.线性规划模型在管理中的应用：生产组织，下料问题线性规划模型在管理中的应用：生产组织，下料问题等等2.2.线性规划模型的构成：目标函数、约束条件；线性规划模型的构成：目标函数、约束条件；3.3.将一般形式转化标准形式：目标函数求最大、最小时；将一般形式转化标准形式：目标函数求最大、最小时；约束条件变为不等号时；常数项为负时；决策变量无约束约束条件变为不等号时；常数项为负时；决策变量无约束时；时；小结小结Page 21作业作业作业：作业：课堂出题练习课堂出题练习思考：思考：建立模型后怎样进行求解？建立模型后怎样进行求解？

15、Page 22线性规划线性规划模型的图解法模型的图解法1 1.基本概念基本概念线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组的方程组中找出一个解，使目标函数中找出一个解，使目标函数(1)达到最大值。达到最大值。Page 23 可行解可行解：满足：满足约束条件约束条件（2 2）、(3)(3)的解为可行解。所有可的解为可行解。所有可行解的集合为可行域。行解的集合为可行域。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。最优值最优值：最优解带入目标函数所得的值称为线性规划的最最优解带入目标函数所得的值

16、称为线性规划的最优值。优值。凸集凸集：如果集合：如果集合C中任何两点连线上所有的点都是集合中任何两点连线上所有的点都是集合C中的点，则称该集合为凸集。中的点，则称该集合为凸集。线性规划线性规划模型的图解法模型的图解法Page 24线性规划线性规划模型的图解法模型的图解法凸集：如果集合凸集：如果集合C中任意两个点中任意两个点X1、X2，其连线上的所有点，其连线上的所有点也都是集合也都是集合C中的点，称中的点，称C为凸集。为凸集。凸集凸集凸集凸集不是凸集不是凸集顶顶 点点Page 25线性规划问题的求解方法线性规划问题的求解方法一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变

17、量、直角坐标两个变量、直角坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标准形式一般形式变成标准形式下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两个决策只有两个决策变量的线性规划问题，这时可以通过图解的方法来变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。性规划基本原理和几何意义等优点。线性规划线性规划模型的图解法模型的图解法Page 26线性规划模型图解法基本步骤：线性规划模型图解法基本步骤：Step1：建立坐标系；建立坐标系；Step2：图示约

18、束条件；图示约束条件；Step3：图示目标函数；图示目标函数；Step4：确定最优解；确定最优解；图解法简单直观，有助于领会线性规划的基本性质及一般求图解法简单直观，有助于领会线性规划的基本性质及一般求解方法的基本思想。解方法的基本思想。线性规划线性规划模型的图解法模型的图解法Page 27max Z=2X1+X2 X1+1.9X2 3.8 X1 -1.9X2 3.8s.t.X1+1.9X2 10.2 X1 -1.9X2 -3.8 X1 ，X2 0例例1.4 用图解法求解线性规划问题用图解法求解线性规划问题线性规划线性规划模型的图解法模型的图解法Page 28x1x2oX1-1.9X2=3.8

19、()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()4=2X1+X2 20=2X1+X2 17.2=2X1+X2 11=2X1+X2 Lo：0=2X1+X2（7.6，2）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域max Z=2X1+X2线性规划线性规划模型的图解法模型的图解法Page 29max Z=3X1+5.7X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()（7.6，2）DL0：0=3X1

20、+5.7X2 max Z34.2=3X1+5.7X2 蓝色线段上的所有点都是最蓝色线段上的所有点都是最优解这种情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=34.2是唯一的。是唯一的。可行域可行域线性规划线性规划模型的图解法模型的图解法Page 30min Z=5X1+4X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1+1.9X2=10.2()DL0：0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2（0，2）可行域可行域此点是唯一最优解此点是唯一最优解线性规划线性规划模型的图解法

21、模型的图解法Page 31246x1x2246无界解无界解(无最优解无最优解)max Z=x1+2x2例例1.5x1+x2=4()x1+3x2=6()3x1+x2=6()max Z min Z线性规划线性规划模型的图解法模型的图解法x1x2O10203040102030405050无可行解无可行解(即无最优解即无最优解)max Z=3x1+4x2例例1.6Page 33线性规划线性规划模型的图解法模型的图解法练习：练习：用图解法求解下面线性规划模型：用图解法求解下面线性规划模型：Page 34线性规划线性规划模型的图解法模型的图解法分析：分析：用图解法求解下面线性规划模型：用图解法求解下面线性

22、规划模型：图图1最大化线性规划模型的图解法最大化线性规划模型的图解法Page 35线性规划线性规划模型的图解法模型的图解法分析：分析：用图解法求解下面线性规划模型：用图解法求解下面线性规划模型：多边形区域多边形区域OABCDOABCD中的点就是线性规划问题的可行解（可行中的点就是线性规划问题的可行解（可行点），多边形区域点），多边形区域 OABCDOABCD称为线性规划问题的可行解区域。称为线性规划问题的可行解区域。显然它是一个凸区域。显然它是一个凸区域。可行域：可行域：目标函数：目标函数：我们将我们将 看作参数，则看作参数，则 表示坐标平面上的表示坐标平面上的一族平行线，直线一族平行线，直线

23、 上任意一点的坐标对应的上任意一点的坐标对应的目标函数值均为，我们称这样的直线为等值线（或等高线）目标函数值均为，我们称这样的直线为等值线（或等高线）。Page 36线性规划线性规划模型的图解法模型的图解法分析：分析：用图解法求解下面线性规划模型：用图解法求解下面线性规划模型：可得可得C C点坐标点坐标X1=4,X2=2X1=4,X2=2，对应的目标函数值为，对应的目标函数值为 Page 37线性规划模型有以下线性规划模型有以下4种情况：种情况：唯一唯一最优解：凸多边形的某个顶点；最优解：凸多边形的某个顶点；无穷多最优解：目标函数直线和可行域边界一条边无穷多最优解：目标函数直线和可行域边界一条

24、边重合；重合；无界解：如果线性规划模型的解无限的变大（变小），无界解：如果线性规划模型的解无限的变大（变小），却不违反任何约束条件；却不违反任何约束条件；无可行解：不存在在满足全部约束条件的解；无可行解：不存在在满足全部约束条件的解；线性规划线性规划模型的图解法模型的图解法Page 38计算机求解线性规规划问题计算机求解线性规规划问题Page 39下面下面介绍介绍QM软件的使用方法：软件的使用方法：Step1：双击：双击QM软件图标，运行该软件。软件图标，运行该软件。Step2：选择：选择“Module”按回车键，选择按回车键，选择“Linear Programming”按回车键。选择按回车键

25、。选择“New”按回车键按回车键,Step3：在出现的窗口中确定约束方程个数、变量个数，在出现的窗口中确定约束方程个数、变量个数，选择最大值、最小值。并按选择最大值、最小值。并按“OK”确认。确认。Step4：输入数据。：输入数据。Step5：选择：选择“Solve”按回车键运行。按回车键运行。Step6：在：在“Windows”窗口中查看结果。（最优解、最窗口中查看结果。（最优解、最优值、迭代过程、影子价格）。优值、迭代过程、影子价格）。线性规划线性规划模型的图解法模型的图解法Page 40线性规划线性规划模型的图解法模型的图解法2.使用使用QM软件求解线性规划模型软件求解线性规划模型 选择

26、线性规划模块选择线性规划模块（P12例题）例题），输入目标函数系数和约，输入目标函数系数和约束条件如图束条件如图1所示所示：图图 1 1Page 41线性规划线性规划模型的图解法模型的图解法点击点击“SLOVE”按钮，进行求解，结果如图按钮，进行求解，结果如图2所示。所示。图图 2 2Page 42学习要点学习要点小结小结：1.线性规划模型的构成、将一般形式转化标准形式线性规划模型的构成、将一般形式转化标准形式 2.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式 （唯一最优解；无穷多最优解；无界解；无可行解）（唯一最优解；无穷多最优解；无界解；无可行解）3.作图的关键有三点：作图的关键有三点：(1)可行解区域要画正确可行解区域要画正确(2)目标函数增加的方向不能画错目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动 4.计算机求解线性规划问题计算机求解线性规划问题小结小结Page 43作业作业课后作业：课后作业：P241、2、3、4思考：思考：求解松弛变量、剩余变量的意义？求解松弛变量、剩余变量的意义？如果模型中的决策变量大于两个时考虑用什么方法求解？如果模型中的决策变量大于两个时考虑用什么方法求解？