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