第一章线性规划及单纯形法

第一章 线性规划及单纯形法Linear Programming and Simplex Method北京物资学院运筹学教学课件北京物资学院信息学院 李珍萍2013年 9月 第一节 线性规划问题的数学模型第二节 两变量线性规划问题的图解法第三节 线性规划问题的基本定理第四节 单纯形法第五节 单纯形法的进一步讨论第六节 线性规划应用案例分析本章内容第一节 线性规划问题的数学模型线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支，它是一种合理利用和调配有限资源的数学方法。线性规划研究的问题 ：极大化问题：面对一定的资源，要求充分利用，以获得最大的经济效益。极小化问题：给定一项任务，要求统筹安排，尽量做到用最少的人力、物力资源去完成这一任务 。一、引例：生产安排问题原料配比问题运输问题二、线性规划问题的结构特征三、线性规划问题的数学模型线性规划问题的一般形式线性规划问题的标准形式一般形式向标准形式的转化本节内容安排一、引例例 1 生产安排问题 某企业使用 A、 B、 C三台机器生产甲、乙两种产品。已知未来两周内 A、 B、 C三台机器的使用时间分别不得超过 80， 60， 45小时，生产每单位产品所需要各台机器的加工时间及每单位产品的利润如下表所示，问企业如何安排未来两周的生产，才能使总利润达到最大？产 品机器甲 乙 可利用的机 时（小 时 ）A 2 4 80B 3 2 60C 3 0 45单 位 产 品的利 润 （元）50 60可控因素：生产两种产品的数量，设分别为 x1 , x2， 目标是生产利润最大，设生产利润为 z. 利润函数为：限制条件：三台设备的使用时间不超过可利用机时设备 A: 2x1+4x280设备 B: 3x1+2x260设备 C: 3x1 45蕴涵约束：产量为非负x10, x2 0目标函数约束条件设生产甲乙两种产品的数量分别为 x1,x2单位 ， 总利润为 z.例 2 原料配比问题 某企业使用三种原料 B1,B2,B3配置某种食品，要求食品中蛋白质、脂肪、糖、维生素的含量分别不低于 15、 20、 25、 30单位。 以上三种原料的单价以及每单位原料所含各种成分的数量如下表所示，问应如何配置食品，才能使成本最低？原料营 养成分B1 B2 B3食品中 营 养成分的需要量蛋白 质 5 6 8 15脂肪 3 4 6 20糖 8 5 4 25维 生素 10 12 8 30原料 单 价（元） 20 25 30设 x1,x2,x3分别表示原料 B1,B2,B3的用量， z表示食品成本。该问题的数学模型为： 例 3 运输问题 设要从甲地调出物资 2000吨，从乙地调出物资 600吨，从丙地调出物资 500吨，分别供应给 A地 1700吨、 B地1100吨、 C地 200吨、 D地 100吨。已知每吨运费如下表所示。假定运费与运量成正比例，问怎样才能找到一个总运费最省的调拨计划？丙 1726384315375151 乙1572521 甲DCBA 销地产地单位：元 / 吨x22x11 x12 x13x21 x23x31 x32 x33x14x24x34用 （ i=1,2,3; j=1,2,3,4） 分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。则该问题的数学模型为简化表达式二、线性规划问题的结构特征：（ 1）都有一组决策变量。（ 2）都有一组线性的约束条件，它们是线性等式或不等式。（ 3）都有一个确定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题 。所以称为线性规划 linear programming (LP)1. 线性规划问题的一般形式s.t（ 1）（ 2）（ 3）一般形式的简化表达三、线性规划问题的数学模型：规范形式极大化问题 极小化问题2. 线性规划的标准形式s.t.s.t（ 1）（ 2）（ 3）标准形式的简化表达标准形式的矩阵表达标准形式的向量表达标准形式的特点 ：(1).目标函数极大化(2).约束条件全部是等式(3).所有的变量都是非负的(4).约束条件右端常数为非负的3.一般形式向标准形式的转化 ：(1) 目标函数极大化对于极小化的目标函数 可以等价地转化成求的极大化 。(2) 不等式约束化等式约束对于 形的不等式，可以在不等式的左边加上（减去）一个非负的变量使不等式化成等式。这样的变量称为松弛（剩余）变量。 例如：(3) 自由变量化非负变量的 差自由变量可以用两个非负变量的差代替，例如对于一个符号无限制的变量 ，可以引进两个非负变量并设(4) 约束条件右端的负常数化为正常数对于右端常数为负数的约束，可以两端同时乘以 -1。取值小于等于 0的变量，可以用一个非负变量的相反数表示。例 将下列 LP问题化成标准形式s.t. s.t.课堂练习：将下列 LP问题化成标准形式作业： P46页习题 1-4题第二节 两变量线性规划问题的图解法一、 几个概念二、 两变量线性规划问题的图解法三、 两变量线性规划问题解的性质可行解 ：任何一组满足所有约束条件的决策变量值 称为 LP问题的一个可行解。最优解 ：使目标函数达到 最大（小 ）值的可行解。最优值 ：最优解对应的目标函数值。可行域 ：所有可行解的集合称为可行域。一、几个概念 ：二、两变量 LP问题的图解法图解法是根据平面直角坐标系和二元一次方程（不等式）的特点设计的。1. 图解法的一般步骤 ：（ 1） 建立直角坐标系，以 为横轴， 为纵轴。（ 2） 将约束条件在直角坐标系中表示，并找出可行域 。（ 3）作出目标函数的等值线簇，找出目标函数值的增加（或减小）方向，用箭头表示。（ 4）确定出问题的最优解。若为极大（小）化问题，目标函数沿增加（减小）方向平移，与可行域的最后一个交点即为最优解。例 1 用图解法解下列线性规划问题最优解 x*=(10,15)T, 最优值 z*=5010+6015