第1节 线性规划 模型和图解法.

第二章线性规划（LinearProgramming）第一节线性规划的模型与图解法第二节单纯形法第三节对偶问题与灵敏度分析第四节运输问题第五节线性整数规划第一节线性规划的模型与图解法一、线性规划问题及其数学模型在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。例1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。资源单耗产品资源甲乙资源限量煤电油9445310360200300单位产品价格7121.决策变量：需决策的量，即待求的未知数；2.目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；3.约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示；线性规划模型的三要素约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为12,712zzxx目标函数：总收入，记为则=为体现对其追求极大化，在z的前面冠以极大号max；在本例中12  ,xx决策变量：甲、乙产品的计划产量，记为解：设安排甲、乙产量分别为,总收入为，则模型为：21,xxz12max712zxx0,3001032005436049..21212121xxxxxxxxts线性规划模型的一个基本特点：如果模型中出现如32211ln2xxx的非线性表达式，则属于非线性规划。目标和约束均为变量的线性表达式例2某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。水泥(公斤/m2)4000(千工日)147000(千块)150000(吨)20000(吨)110000(千元)资源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105砖混住宅人工(工日/m2)砖(块/m2)钢材(公斤/m2)造价(元/m2)资源住宅体系解:设今年计划修建砖混、壁板、大模住宅各为,为总面积,则本问题的数学模型为:0,,40000035.0003.00045.0147000210.0150000180.0190.0110.020000025.0030.0012.0110000120.0135.0105.0.3213211321321321xxxxxxxxxxxxxxxxts123maxzxxx前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。123,,xxxz练习：某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有M、N两种。有关数据如下：试决定买M与N二种饲料各多少公斤而使支出的总费用为最少？饲料售价每公斤含营养成分ABCDM100.100.10.2N400.10.20.1牲畜每日每头需要量0.40.62.01.7解：设购买M、N饲料各为，则12min104zxx0,7.11.02.00.22.01.06.01.004.001.0..2121212121xxxxxxxxxxts21,xx线性规划模型的一般形式：（以MAX型、≤约束为例）决策变量：目标函数：约束条件：0,,..11111111nmnmnmnnxxbxaxabxaxatsnxx,,111maxnnzcxcx则模型可表示为模型一般式的矩阵形式记1(,,)TnXxxmax..0zCXAXbstX()ijmnAa1(,,)nCcc1(,,)TmbbbC是行向量回顾例1的模型其中表示决策变量的向量：表示产品的价格向量：示资源限制向量：表示产品对资源的单耗系数矩阵。TxxX),(21)12,7(CTb)300,200,360(1035449A一般地中称为决策变量向量，称为价格系数向量,称为技术系数矩阵,称为资源限制向量。max..0zCXAXbstXXCAb问题：为什么称为技术系数矩阵？A二、线性规划模型的图解法图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。1.图解法的步骤（1）做约束的图形先做非负约束的图形；再做资源约束的图形。以例1为例，其约束为0,3001032005436049.21212121xxxxxxxxts01x2x问题：不等式的几何意义是什么？怎样做图？1294360xx再确定不等式表示上述直线的哪半平面，可用代入点的方法:1294360,xx先做直线用两点连线方法:12129436094360xxxx如，它表示以为边界的一个半平面。因此，它的做图方法是：12210,90,0,40,090400xxxx令则再令则于是该直线过点（，）、（，）；00原点所如把原点（，）代入不等式，满足，说明的半平面即该不等式在所表示的区域。01x2x9040（1）做约束的图形先做非负约束的图形；再做资源约束的图形。以例1为例，其约束为0,3001032005436049.21212121xxxxxxxxts01x2x9040501003040各约束的公共部分即模型的约束，称可行域。1.图解法的步骤（2）做目标的图形01x2x对于目标函数任给z二不同的值，便可做出相应的二直线，用虚线表示。nnxcxcz117121424（3）求出最优解将目标直线向使目标Z优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点X*即最优解。01x2x9040501003040*X如在例1中，X*是可行域的一个角点，经求解交出X*的二约束直线联立的方程可解得X*=(20,24)T说明当甲产量安排20个单位，乙产量安排24个单位时，可获得最大的收入428。由图解法的结果得到例1的最优解X*=(20,24)T，还可将其代入目标函数求得相应的最优目标值Z*=428。练习：用图解法求解下面的线性规划。12121212min6421..341.5,0zxxxxstxxxx01x2x15.0375.05.11*X3,)0,5.0(**zXT问题：在上两例中——多边形，而且是“凸”形的多边形。最优解在什么位置获得？——在边界，而且是在某个顶点获得。线性规划的可行域是一个什么形状？2.由图解法得到线性规划解的一些特性（1）线性规划的约束集（即可行域）是一个凸多面体。凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：凸集中的“极点”，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。必能在可行域的角点获得。因为，由图解法可知，只有当目标直线平移到边界时，才能使目标z达到最大限度的优化。问题：本性质有何重要意义？——它使得在可行域中寻优的工作由“无限”上升为“有限”，从而为线性规划的算法设计提供了重要基础。（2）线性规划的最优解（若存在的话）（3）线性规划解的几种情形①唯一最优解②多重最优解③无可行解④无有限最优解（无界解）