《运筹第一章线性规划》由会员分享，可在线阅读，更多相关《运筹第一章线性规划（117页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划及单纯形法Linear Programming (LP),北京物资学院运筹学教学课件,北京物资学院信息学院,第一节 线性规划问题的数学模型 第二节 两变量线性规划问题的图解法 第三节 单纯形法的原理 第四节 单纯形法的计算步骤 第五节 单纯形法的进一步讨论 第六节 线性规划应用举例,本章内容,第一节 线性规划问题的数学模型,线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支，它是一种合理利用和调配有限资源的数学方法。,线性规划研究的问题：,极大化问题：面对一定的资源，要求充分利用，以获得最大的经济效益。,极小化问题：给定一项任务，要求统筹安排，尽量做到用最少的人
2、力、物力资源去完成这一任务。,一、实例：生产安排问题运输问题 二、线性规划问题的结构特征线性规划问题的特征线性规划问题的一般形式线性规划问题的标准形式一般形式向标准形式的转化,本节内容安排,一、实例,例1 生产安排问题,某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产 品。每件产品在生产中需要占用的设备机时数，每件产品 可以获得的利润以及三种设备可利用的时数如下表所示：,问题：工厂应如何安排生产可获得最大的总利润？,可控因素：生产两种产品的数量，设分别为x1 , x2， 目标: 生产利润最大，设生产利润为z.,利润函数为：,限制条件：三台设备的使用时间不超过设备能力的限制 设备A: 3x1
3、+2x265 设备B: 2x1+ x240 设备C: 3x275,蕴涵约束：产量为非负x10, x2 0,目标函数 约束条件,设生产甲乙两种产品的数量分别为x1,x2件，总利润为z.,在处理产、供、销的经济活动中，会经常遇到物资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产地调运到若干个销售地。问题是，怎样制定合理的调运方案才能使总运输费用最少？这类问题称为运输问题,例2 运输问题,设要从甲地调出物资2000吨，从乙地调出物资600吨，从丙地调出物资500吨，分别供应给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如下表所示。,假定运费与运量
4、成正比例，问怎样才能找到一个总运费最省的调拨计划？,丙,17,26,38,43,15,37,51,51,乙,15,7,25,21,甲,D,C,B,A,销地 产地,单位：元 / t,问题分析： 可控因素：从三个产地到四个销地的运输量；目标： 总运费最省；限制条件：各个产地的产量和销地的需求量的限制 。,用 （i=1,2,3; j=1,2,3,4）分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。,则该问题的数学模型为,简化表达式,二、线性规划问题的结构特征：,1. 线性规划问题的特征； （1）都有一组决策变量。 （2）都有一组线性的约束条件，它们是线性等式或不等式。 （3）都有一个确
5、定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。,线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题。 所以称为线性规划 linear programming (LP),2. 线性规划问题的一般形式,一般形式的简化表达,规范形式,极大化问题,极小化问题,3. 线性规划的标准形式,标准形式的简化表达,标准形式的矩阵表达,标准形式的向量表达,标准形式的特点：,(1).目标函数极大化,(2).约束条件全部是等式,(3).所有的变量都是非负的,(4).约束条件右端常数为非负的,4. 一般形式向标准形式的转化：,(1) 目标函数极大化,
6、(2) 不等式约束化等式约束,对于 形的不等式，可以在不等式的左边加上（减去）一个非负的变量使不等式化成等式。这样的变量称为松弛（剩余）变量，它们在目标函数中的生系数均为零。,例如：,(3) 无约束的变量（自由变量）化非负变量的差,自由变量可以用两个非负变量的差代替，例如对于一个符号无限制的变量 ，可以引进两个非负变量并设,(4) 约束条件右端的负常数化为正常数,对于右端常数为负数的约束，可以两端同时乘以-1。,取值小于等于0的变量，可以用一个非负变量的相反数表示。,例 将下列LP问题化成标准形式,s.t.,课堂练习：将下列LP问题化成标准形式,作业：,见公共邮箱,第二节 两变量线性规划问题的
7、图解法,一、几个概念 二、两变量LP问题的图解法,可行解：任何一组满足所有约束条件的决策变量值 称为LP问题的一个可行解。,最优解：使目标函数达到最大（小）值的可行解。 最优值：最优解对应的目标函数值。,可行域：所有可行解的集合称为可行域。,一、几个概念：,二、两变量LP问题的图解法,图解法是根据平面直角坐标系和二元一次方程（不等式）的特点设计的。,1. 图解法的一般步骤：,（1） 建立直角坐标系，以 为横轴， 为纵轴。,（2） 将约束条件在直角坐标系中表示，并找出可行域。,（3）作出目标函数的等值线簇，找出目标函数值的增加（或减小）方向，用箭头表示。,（4）确定出问题的最优解。若为极大（小）
8、化问题，目标函数沿增加（减小）方向平移，与可行域的最后一个交点即为最优解。,例1 用图解法解下列线性规划问题,最优解 x*=(10,15)T, 最优值 z*=6010+5015=1350.,0,1 0 20 30 4 0,1 0 2 0 3 0,x2,x1,(1),(2),(10,15),可行域有界,有唯一最优解,课堂练习：用图解法求解下列LP问题,最优解为X=(5，25)T，最优值 70000。,例2、,无穷多最优解,x1,x2,例3、,无有限 最优解,x1,x2,可行域无界, 有唯一最优解,x1,x2,例4、,x1,x2,可行域为空, 无可行解,例5、,0,1 2 3 4 5 6 7 8,
9、1 2 3 4 5 6,x2,x1,(4 2),课堂练习:用图解法求解,可行域是空集。 可行域存在，则一定是一个凸多边形.,无有限最优解（可行域一定无界）。 最优解存在且唯一，则一定在顶点上达到。 最优解存在且不唯一，一定存在一个顶点是最优解。,2. 图解法求解两变量LP问题时可能出现的情况：,3. 两变量线性规划问题解的性质,1. 两变量线性规划问题的可行域是若干个半平面的交集，它是一个有界或无界的凸多边形，并且有有限个顶点。,2. 对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。,第三节 单纯形法的原理,一、可行区域的几何结构 二、基可行解及线性规划的基本定理
10、 三、单纯形法的原理,单纯形方法（Simplex Method）是G.B.Dantzing 在1947年提出的。,一、可行区域的几何结构,1. 基本假设 2. 凸集及其性质 3. 可行域的凸性 4. 问题,1. 基本假设,凸集：设S是n维欧氏空间的一个点集，若任意两点X(1)S, X(2)S 的连线上的一切点 X(1)+ (1- )X(2)S, (0 1); 则称S为一个凸集。,性质：任意多个凸集的交集仍然是凸集。,2. 凸集及性质,顶点：设S是凸集，XS；若对任何X(1)S和 X(2)S， X(1) X(2)，以及任何0 m)，其秩为m，B是A中的一个m阶满秩子方阵，称B是线性规划问题的一个
11、基。 B中每一个列向量称为一个基向量，与基向量对应的变量称为基变量。其余变量称为非基变量。,不失一般性，设,则Pj（j=1，2m）是基向量，xj（ j=1，2m ）是基变量。 xj（ j=m+1，n ）是非基变量。,基解：在约束方程组中令所有的非基变量 xm+1=x m+2=x n=0，得,此方程组有唯一解XB=(x1，x2，xm)T，将这个解加上非基变量取0的值有X=(x1，x2，xm,0,0)T,称X为线性规划问题的基解。,显然，基解中取非零值的变量个数不超过m，基解的总数不超过Cnm个。,基可行解：满足非负约束的基解称为基可行解。 可行基：对应于基可行解的基。,基可行解,用矩阵形式表示的
12、基解,考虑标准形式的线性规划问题：,例如LP问题,是它的两个基，对应的基解分别为,可见X1是基可行解，故B1是可行基。而X2不是基可行解，故B2不是可行基。,根据以上定义,2. 线性规划的基本定理,引理：LP问题的可行解X是基可行解的充要条件是它的正分量所对应的A中的列向量线性无关。,定理2：线性规划问题的基可行解对应可行域的顶点。（X是基可行解X是可行域的顶点）（基可行解个数有限）,定理3：一个LP问题，若有最优解，则一定存在一个基可行解是最优解。,3. 问题,如何得到第一个基可行解？ 如何判别一个基可行解是否最优？ 如果当前的基可行解不是最优，如何从一个基可行解转化到另一个基可行解？,三、
13、单纯形法原理,确定初始基可行解 最优性检验和解的判别 基可行解的改进,情况1 约束条件全部是“”型不等式且右端常数非负（化成标准形后，约束条件系数矩阵含有单位子矩阵）,加上松弛变量，化为标准形式：,1. 确定初始基可行解,其约束条件系数矩阵为,令其中的单位矩阵作为基，可得初始基可行解,考虑标准形式的LP问题,假设可行域非空， A为一 mn实矩阵，r(A)=mn 。,情况2 化成标准形式后，约束条件系数矩阵不含单位子矩阵,关键：找一个可行基，将约束条件化成系数矩阵含有单位矩阵的形式。,假设B是一个可行基，不妨设B是由A的前m个列向量组成的，即A=(B,N)，则线性规划问题的等式约束AX=b 可以化成：,目标函数 Z=CX 可以化成,线性规划问题的典式（典则形式）,典式的特点：（1）约束条件系数矩阵中含有一个单位矩阵；（2）目标函数中不含有基变量。,此时：,有了典式，就很容易写出线性规划问题的基解,
