《模型与图解法》PPT课件.ppt
第一节第一节 线性规划的模型与图解法线性规划的模型与图解法一、线性规划问题及其数学模型一、线性规划问题及其数学模型 在生产管理和经营活动中经常需要解决：如何在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。合理地利用有限的资源，以得到最大的效益。例例1 1 某工厂可生产甲、乙两种产品，需消耗煤、某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。试拟订使总收入最大的生产方案。资源单耗资源单耗 产品产品资源资源甲甲 乙乙资源限量资源限量煤煤电电油油9 44 5 3 10360200300单位产品价格单位产品价格 7 12线性规划模型的三要素线性规划模型的三要素3.3.约束条件：约束条件：为实现优化目标需受到的限制，用为实现优化目标需受到的限制，用 决策变量的等式或不决策变量的等式或不 等式表示；等式表示；1.1.决策变量：决策变量：需决策的量，即待求的未知数；需决策的量，即待求的未知数；2.2.目标函数：目标函数：需优化的量，即欲达的目标，用决需优化的量，即欲达的目标，用决 策变量的表达式表示；策变量的表达式表示；目标函数：总收入，记为目标函数：总收入，记为Z,Z,则则z z=7=7X1+121+12X2 2，为体现对其，为体现对其 追求极大化，在追求极大化，在Z Z 的前面冠以极大号的前面冠以极大号MaxMax；决策变量：甲、乙产品的计划产量，记为决策变量：甲、乙产品的计划产量，记为 ；在本例中在本例中约束条件：分别来自资源煤、电、油限量的约束，和产约束条件：分别来自资源煤、电、油限量的约束，和产 量非负的约束，表示为量非负的约束，表示为:解：解：设安排甲、乙产量分别设安排甲、乙产量分别 为为 ,总收入为总收入为 ，则模型为：则模型为：线性规划模型的一个基本特点：线性规划模型的一个基本特点：目标和约束均为变量的线性表达式目标和约束均为变量的线性表达式如果模型中出现如如果模型中出现如的非线性表达式，则属于非线性规划。的非线性表达式，则属于非线性规划。例例2 2 某市今年要兴建大量住宅某市今年要兴建大量住宅,已知有三种住宅体系可以已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最要求在充分利用各种资源条件下使建造住宅的总面积为最大大(即求安排各住宅多少即求安排各住宅多少m2)，求建造方案。，求建造方案。水泥水泥(公斤公斤/m2)4000(千工日千工日)147000(千块千块)150000(吨吨)20000(吨吨)110000(千元千元)资源限量资源限量3.518025120大模住宅大模住宅3.019030135壁板住宅壁板住宅4.521011012105砖混住宅砖混住宅人工人工(工日工日/m2)砖砖(块块/m2)钢材钢材(公斤公斤/m2)造价造价(元元/m2)资源资源住宅体系住宅体系 解解:设今年计划修建砖混、壁板、大模住宅各为设今年计划修建砖混、壁板、大模住宅各为 x1,x2,x3 m2,z为总面积为总面积,则本问题的数学模型为则本问题的数学模型为:前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，个变量，10个约束条件。个约束条件。练习：练习：某畜牧厂每日要为牲畜购买饲料以使其获取某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上四种养分。市场上可选择的饲料有可选择的饲料有M、N两种。有关数据如下：两种。有关数据如下：试决定买试决定买M与与N二种饲料各多少公斤而使支出的总费用为最少？二种饲料各多少公斤而使支出的总费用为最少？410售价售价 0.4 0.6 2.0 1.7牲畜每日每头需要量牲畜每日每头需要量 0 0.1 0.2 0.1N 0.1 0 0.1 0.2 M每公斤含营养成分每公斤含营养成分 A B C D饲料饲料解：设购买解：设购买M、N饲料各为饲料各为 ，则，则 线性规划模型的一般形式：线性规划模型的一般形式：（以（以MAX型、型、约束为例）约束为例）决策变量：决策变量：目标函数：目标函数：约束条件：约束条件：则模型可表示为则模型可表示为:模型一般式的矩阵形式模型一般式的矩阵形式:记记回顾例回顾例1 1的模型的模型其中其中 表示决策变量的向量；表示决策变量的向量；表示产品的价格向量；表示产品的价格向量；表示资源限制向量；表示资源限制向量；表示产品对资源的单耗系数矩阵。表示产品对资源的单耗系数矩阵。一般地一般地中中 称为决策变量向量，称为决策变量向量，称为价格系数向量称为价格系数向量,称为技术系数矩阵称为技术系数矩阵,称为资源限制向量。称为资源限制向量。问题：问题：为什么为什么 A A 称为技术系数矩阵？称为技术系数矩阵？二、线性规划模型的图解法二、线性规划模型的图解法n图解法是用画图的方式求解线性规划的一种图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些是在于能够直观地说明线性规划解的一些重要性质。重要性质。1.1.图解法的步骤图解法的步骤（1）做约束的图形）做约束的图形 先做非负约束的图形；先做非负约束的图形；再做资源约束的图形。再做资源约束的图形。以例以例1 1为例，其约束为为例，其约束为 问题：问题：不等式的几何意义是什么？怎样作图？不等式的几何意义是什么？怎样作图？（1）做约束的图形）做约束的图形 先做非负约束的图形；先做非负约束的图形；再做资源约束的图形。再做资源约束的图形。以例以例1 1为例，其约束为为例，其约束为 各约束的公共部分即各约束的公共部分即模型的约束，称可行域。模型的约束，称可行域。1.1.图解法的步骤图解法的步骤（2）做目标的图形）做目标的图形对于目标函数对于目标函数任给任给 两个不同的值，便可做出两个不同的值，便可做出相应的两条直线，用虚线表示。相应的两条直线，用虚线表示。以例以例1 1为例，其目标为为例，其目标为 ，分别令，分别令 ，做出，做出相应的二直线，便可看出相应的二直线，便可看出 增大的方向。增大的方向。（3 3）求出最优解）求出最优解 将目标直线向使目将目标直线向使目标标 优化的方向移，直优化的方向移，直至可行域的边界为止，至可行域的边界为止，这时其与可行域的这时其与可行域的“切切”点点 即最优解。即最优解。如在例如在例1 1中，中，是可行域的一个角点，是可行域的一个角点，经求解交出经求解交出 的的二约束直线联立的方程二约束直线联立的方程可解得可解得 由图解法的结果得到例由图解法的结果得到例1 1的最优解的最优解 ，还可将其代入目标函数求得相应的最优目标值还可将其代入目标函数求得相应的最优目标值 。说说明明当当甲甲产产量量安安排排 20 20 个个单单位位，乙乙产产量量安安排排 24 24 个个单单位位时时，可可获获得得最大的收入最大的收入 428428。练习：练习：用图解法求解用图解法求解下面的线性规划。下面的线性规划。问题：问题：在上两例中在上两例中 多边形，而且是多边形，而且是“凸凸”形的多边形。形的多边形。最优解在什么位置获得？最优解在什么位置获得？在边界，而且是在某个角点获得。在边界，而且是在某个角点获得。线性规划的可行域是一个什么形状？线性规划的可行域是一个什么形状？2.由图解法得到线性规划解的一些特性由图解法得到线性规划解的一些特性（1）线性规划的约束集（即可行域）是一个凸多）线性规划的约束集（即可行域）是一个凸多 面体。面体。凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：此集。试判断下面的图形是否凸集：凸集中的凸集中的“极点极点”，又称顶点或角点，是指它属于凸集，但不能表，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。示成集中某二点连线的内点。如多边形的顶点。（2 2）线性规划的最优解（若存在的话）必能在）线性规划的最优解（若存在的话）必能在可行域的角点获得。可行域的角点获得。因为，由图解法可知，只有当目标直线平移到边界时，才能使目标因为，由图解法可知，只有当目标直线平移到边界时，才能使目标 z z 达到最大限度达到最大限度的优化。的优化。问题：问题：本性质有何重要意义？本性质有何重要意义？它使得在可行域中寻优的工作由它使得在可行域中寻优的工作由“无限无限”上升为上升为“有有 限限”，从而为线性规划的算法设计提供了重要基础。，从而为线性规划的算法设计提供了重要基础。（3 3）线性规划解的几种情形）线性规划解的几种情形 唯一最优解唯一最优解 多重最优解多重最优解 无解无解 无有限最优解无有限最优解（无界解）（无界解）
