线性规划及单纯形法.ppt

第一章 线性规划及单纯形法 1 学习目标 v了解线性规划问题的概念； v掌握线性规划问题的建模； v掌握两维线性规划问题的解法图解法； v掌握线性规划问题的算法单纯形法； v掌握线性规划问题解的概念。 2 第一节 数学模型及基本概念 3 一、引例 v例1：（生产计划问题）某企业利用三种原料 B1、B2、B3生产A1、A2 两种产品。三种原 料的月供应量（吨），生产一吨产品A1、A2 所需各种原料的数量以及单位产品的价格（ 万元/吨）如下表所示。那么该企业如何安排 生产计划，使总收益最大？ 4 A1 A2 原料月供应应量 （吨/月） B1 B2 B3 1 1 2 3 3 2 150 240 300 单单位产产品价格 2.4 1.8 产 品 原 料 单位产品消耗 5 v决策/方案：每月生产两种产品的数量 v目标：每月的收益最大化 v受制条件：每月的原料供应有限 v蕴含条件：每月的产量非负 6 v例1（生产计划）（模型） 7 v例2，（运输问题）某公司经销一种产品。它 下设三个生产点A1 、 A2、A3，每日的产量分 别为9吨、5吨、7吨。该公司把这些产品分别 运往四个销售点B1、B2、B3、B4，各销售点每 日销售量分别为3吨、8吨、4吨、6吨。每吨产 品从各生产点到各销售点的运价如下表。 问：该公司应如何调运产品，可在满足各销售 点需要量的前提下，使总运费最少？ 8 产产地 各地运价（千元/吨） 日产产量（吨） B1 B2 B3 B4 A1 A2 A3 2 9 10 7 1 3 4 2 8 4 2 5 9 5 7 日销销量 （吨） 3 8 4 621 9 v决策/方案：从各产地调往各销地的产品数量 v目标：总运费最小 v受制条件：从各产地调出的总量不超过可用总量 运入各销售点的数量不低于需求量 （由于总产量=总销量，所以都是等号） v蕴含条件：调运量非负 10 产产地 各地调调运量（吨） 日产产量（吨） B1 B2 B3 B4 A1 A2 A3 x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 9 5 7 日销销量 （吨） 3 8 4 621 11 v例2（运输问题）（模型） 12 v例3，美佳公司计划制造、两种家电产品 。已知各制造一件时分别占用的设备A、B的 台时、调试工序时间及每天可用能力，各售 出一件时的获利情况，见下表所示。 问：该公司应每天制造两种家电各多少件， 使获取的利润为最大。 13 项项目每天可用能力 设备设备 A（h） 设备设备 B（h） 调试调试 工序（ h） 0 6 1 5 2 1 15 24 5 利润润（千元 ） 21 14 v决策/方案：每月生产两种家电的数量 v目标：每天的利润最大化 v受制条件：每天的设备和调试时间可用时间 有限 v蕴含条件：每天的产量非负 15 v例3（美佳公司）（模型） 16 二、线性规划问题 v给定一定数量的人力、物力等资源，研究如何充分 利用，以发挥其最大效果； v给定计划任务，研究如何统筹安排，用最少的人力 和物力去完成。 1、规划问题：在生产和经营管理中如何合理安 排，使人力、物力等各种资源得到充分利用 ，获得最大的效益。 17 2、线性规划问题：要确定一组变量的值，使之 满足一组线性等式或线性不等式，并使一个 线性目标函数取得最小值（或最大值）。 18 3、（线性规划）数学模型的三要素 变量/决策变量； 目标函数（max/min）； 约束条件。 19 变量/决策变量：指决策者为实现规划目标采 取的方案、措施，是问题中要确定的未知量 ； 目标函数：指问题要达到的目的要求，表示 为决策变量的函数； 约束条件：指决策变量取值时受到的各种可 用资源的限制。 20 线性规划问题的数学模型： 目标函数（ Max/Min） 约束条件 非负约束 决策变量 21 说明 ： 非负约束：很多情况下蕴含了这一假设，不一定 需要明确指出。在实际中，有些决策变量允许取任 意实数，如温度变量等，不能强行限制其非负。 约束条件：等于（等式约束） 大于等于、小于等于（不等式约束） 目标函数：Max或Min 22 3、特点 决策变量x，表示要寻求的方案，每一组值 就是一个方案； 约束条件，是用等式或不等式表述的限制条 件； 一定有一个追求目标，或希望最大或最小； 所有函数都是线性的。 23 三、图解法（适用两个变量） 1、解法步骤P14-15 在平面上建立直角坐标系； 图示约束条件，找出可行域； 图示目标函数； 确定最优解。 24 2、例题 v例1（美佳公司） 25 x1 x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 o Q1 Q2 Q3Q4 唯一解 26 v说明： 图中凸多边形OQ1Q2Q3Q4所包含的区域是该 线性规划问题的可行域； 目标函数随f的变化而变化，f的斜率为（-2） 的一族平行直线，向P的方向逐渐增大； 最优解是可行域中使目标函数值达到最优的 点，因此当目标函数的直线与凸多边形相切 时，切点为最优解的点。 27 v例2：用图解法解线性规划问题。 28 x1 x2 x23 x1 + x2 6 x1 + 2x2 8 无穷多解 29 v例3：用图解法求解线性规划问题。 30 x1 x2 x1 - x2 1 x1 - 2x2 0 无最优解 31 v例4：用图解法求解线性规划问题。 32 x1 x2 x1 + x2 1 2x1 + 3x2 6 无可行解 33 3、结论（由上面的几个例子）P16-17 线性规划问题可能没有可行解； 当线性规划问题有可行解时，它可能不存在 最优解，也可能仅有唯一的最优解，还可能 有无穷多个最优解； 34 线性规划问题的可行解区域都是“凸区域”， 这一区域可能为封闭的有界，也可能为非封 闭的无界区域； 若线性规划问题存在最优解，则最优值必在 可行解区域的顶点上达到。 通过图解法为我们进行2维以上线性规划问题的 求解提供了思路。 35 第二节 线性规划问题解的性质 36 一、线性规划问题的标准式 1、线性规划问题的标准式P11-12 求目标函数的最大值； 所有变量xj均要求取非负值； 所有约束条件（变量非负约束除外）必须为 等式； 约束条件右端常数项bi全为非负值。 37 线性规划问题的标准形式： 38 2、标准形式的化法 目标函数为极小值，即 ； 令z=-f，化为 。 必须注意，尽管以上两个问题的最优解相同，但他们最优 解的目标函数值却相差一个符号，即 Minf=-Maxz 39 约束条件的右端项bi0时，只需将等式 或不等式两端同乘（-1），则等式右端项 必大于零。 40 约束条件为不等式 v“”：如6x1+2x224，令x3=24- 6x1+2x2 ， 得6x1+2x2+x3=24，显然x30，称为松弛变 量； v“”：如10x1+12x218，令x4 =10x1+12x2- 18 ，得10x1+12x2- x4 =18，显然x40，称 为剩余变量。 如果原问题中有若干个非等式约束，必须对各个约束引进 不同的松弛/剩余变量。 41 取值无约束的变量，x可正可负时，令 x=x-x” 其中x 0，x”0，将其代入线性规划模型即 可。 42 对x0的情况，令x=-x，显然x 0 。 43 例1：将线性规划问题化为标准形式 44 例2：将线性规划问题化为标准形式 45 二、线性规划问题的解 1、基本概念P13 可行解：满足所有约束条件的解； 可行域：所有可行解的集合； 最优解：使目标函数值达到最优的可行解； 最优值：最优解所对应的函数值。 46 2、基（本）解和基（本）可行解P13 v前提假设：设标准形式的线性规划问题的系 数矩阵A（ mn ）的秩为m，且mn。 行满秩，否则会去掉多余的约束条件 47 基：在线性规划问题中，系数矩阵A的一 个满秩（可逆）子矩阵B （mm）称为 问题的一个基。 R(A)=20，则问题有无穷多最优解； v当j0时，若所有的i 0（即aij 0 ），则 问题为无界解，计算结束，否则转入下一步。 思考题：这种情况下不会出现无解的情况？ 68 第五步：从当前基本可行解转换到相邻的目标 函数值更大的基本可行解，列出新的单纯形 表。 v确定换入基的变量，只要有检验数j0，对 应的变量xj就可以作为换入基的变量，当有 一个以上检验数大于零时，一般从中找出最 大一个k ， 出现相同的任取一个；其对应的 变量xk作为换入基的变量。 69 v确定换出基的变量 确定xl是换出基的变量。 70 v用换入变量xk替换基变量中的换出变量xl ， 得到一个新的基（p1,pl-1,pk,pl+1,pm）。 说明：在这个新的表中基仍应是单位矩阵，即 Pk应变换成单位向量，为此在新表中进行初 等行变换。 71 第六步：重复4、5两步，一直到计算结束为止 。 72 注意： 若问题的系数矩阵中不包含单位矩阵时，可 以添加人工变量的方法来人为构造一个单位 矩阵； 如果当所有j0 ，有人工变量仍留在基变量 中且不为零，则该问题无（可行）解。 73 三、例题 例1，用单纯形法求解线性规划问题 74 解：（1）上述问题的标准形式是 75 （2）构造初始单纯形表 cj 2 1 0 0 0 i cBxBb x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 15 24 5 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1 1 2 3 j=cj -zj 1 2 0 0 0 76 从表中看出，（P3、P4、P5）组成一个基， 令非基变量x1=x2=0，即得到一个初始基 本可行解： X=（0，0，15，24，5） 77 cj 2 1 0 0 0 i cBxBb x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 15 24 5 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1 - 4 5 j=cj -zj 2 1 0 0 0 确定换入变量1 =20， x1为换入变量 主元列 主元行 主元素 确定换出变量mini=2=4， x4为换出变量 78 列出新的单纯形表，用x1替换x4 cj 2 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 2 0 x3 x1 x5 15 24 5 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1 1 2 3 j=cj -zj 1 2 0 0 0 79 同时利用初等行变换，把主元列变为单位 列向量（主元素为1）。 cj 2 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 2 0 x3 x1 x5 15 4 5 0 5 1 0 0 1 1/3 0 1/6 0 1 1 0 0 1 1 2 3 j=cj -zj 1 2 0 0 0 80 cj 2 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 2 0 x3 x1 x5 15 4 1 0 5 1 0 0 1 1/3 0 1/6 0 0 2/3 0 -1/6 1 1 2 3 j=cj -zj 0 2 0 4 0 81 cj 2 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 2 0 x3 x1 x5 15 4 1 0 5 1 0 0 1 1/3 0 1/6 0 0 2/3 0 -1/6 1 3 12 3/2 j=cj -zj 0 1/3 0 -1/3 0 确定换入变量2 =1/30， x2为换入变量 确定换出变量mini=2=3/2， x5为换出变量 主元列 主元行 主元素 82 cj 2 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 2 1 x3 x1 x2 15 4 1 0 5 1 0 0 1 1/3 0 1/6 0 0 2/3 0 -1/6 1 3 12 3/2 j=cj -zj 0 1/3 0 -1/3 0 列出新的单纯性表，用x2替换x5 主元列 主元行 主元素 83 cj 2 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 2 1 x3 x1 x2 15 4 3/2 0 5 1 0 0 1 1/3 0 1/6 0 0 1 0 -1/4 3/2 j=cj -zj 同时利用初等行变换，把主元列变为单位 列向量（主元素为1）。 主元列 84 cj 2 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 2 1 x3 x1 x2 15/2 7/2 3/2 0 0 1 4/5 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 j=cj -zj 0 0 0 -1/4 -1/2 主元列 85 从上表中的检验行看到所有的j0，故表 中的基本可行解 X=（7/2，3/2，15/2，0，0）为最优解。 代入目标函数得maxf=17/2，解题结束。 86 例2，用单纯形法求解线性规划问题 87 解：上述问题的标准形式是 88 cj 4 6 0 0 0 0i cBxB b x1 x2 x3 x4 x5 x6 0 0 0 0 x3 x4 x5 x6 28 20 32 24 4 4 1 0 0 0 4 2 0 1 0 0 8 0 0 0 1 0 2 4 0 0 0 1 7 10 - 6 j=cj -zj 4 6 0 0 0 0 确定换入变量2 =60， x2为换入变量 确定换出变量mini=6=6， x6为换出变量 89 cj 4 6 0 0 0 0i cBxB b x1 x2 x3 x4 x5 x6 0 0 0 6 x3 x4 x5 x2 4 8 32 6 2 0 1 0 0 -1 3 0 0 1 0 -1/2 8 0 0 0 1 0 1/2 1 0 0 0 1/4 2 8/3 4 12 j=cj -zj 1 0 0 0 0 -3/2 列出新的单纯性表，用x2替换x6 同时利用初等行变换，把主元列变为单位列向量 （主元素为1）。 90 cj 4 6 0 0 0 0i cBxB b x1 x2 x3 x4 x5 x6 4 0 0 6 x1 x4 x5 x2 2 2 16 5 1 0 1/2 0 0 -1/2 0 0 -3/2 1 0 1 0 0 -4 0 1 4 0 1 -1/4 0 0 1/2 j=cj -zj 0 0 -1/2 0 0 -1 确定换入变量1 =10， x1为换入变量 确定换出变量mini=1=2， x3为换出变量 列出新的单纯性表，用x1替换x3 同时利用初等行变换，把主元列变为单位列向量 （主元素为1）。 91 表中的检验行中所有的j0 ，故表中的基 本可行解 X=（2，5，0，2，16，0）为最优解。 代入目标函数得maxf=38，解题结束 92 例3，用单纯形法求解线性规划问题 93 解：上述问题的标准形式是 94 构造初始单纯形表 cj 1 1 0 0 0 i cBxBb x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 6 8 3 1 1 1 0 0 1 2 0 1 0 0 1 0 0 1 6 4 3 j=cj -zj 1 1 0 0 0 确定换入变量2 =10， x2为换入变量 确定换出变量mini=2=3， x5为换出变量 95 cj 1 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 0 1 x3 x4 x2 3 2 3 1 0 1 0 -1 1 0 0 1 -2 0 1 0 0 1 3 2 - j=cj -zj 1 0 0 0 -1 列出新的单纯性表，用x2替换x5 同时利用初等行变换，把主元列变为单位列向量 （主元素为1）。 96 cj 1 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 0 1 x3 x4 x2 3 2 3 1 0 1 0 -1 1 0 0 1 -2 0 1 0 0 1 3 2 - j=cj -zj 1 0 0 0 -1 确定换入变量1 =10， x1为换入变量 确定换出变量mini=2=3， x4为换出变量 97 cj 1 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 1 1 x3 x1 x2 3 2 3 0 0 1 -1 1 1 0 0 1 -2 0 1 0 0 1 1 - 3 j=cj -zj 0 0 0 -1 1 列出新的单纯性表，用x1替换x4 同时利用初等行变换，把主元列变为单位列向量 （主元素为1）。 98 cj 1 1 0 0 0 i cBxB b x1 x2 x3 x4 x5 0 1 1 x5 x1 x2 1 4 2 0 0 1 -1 1 1 0 2 - 1 0 0 1 -1 1 0 j=cj -zj 0 0 -1 0 0 列出新的单纯性表，用x5替换x3 同时利用初等行变换，把主元列变为单位列向量 （主元素为1）。 99 表中的检验行所有的j0 ，且非基变量 x4=0，且可以找到0，所以该问题有无 穷多个最优解，其中 X=（4，2，0，0，1）为其中一个最优解。 代入目标函数得maxf=6，解题结束。 100 例4，用单纯形法求解线性规划问题 101 解：上述问题的标准形式是 102 构造初始单纯形表 cj 3 2 0 0 i cBxBb x1 x2 x3 x4 0 0 x3 x4 2 4 1 -1 1 0 -3 1 0 1 2 - j=cj -zj 3 2 0 0 103 cj 3 2 0 0 i cBxBb x1 x2 x3 x4 3 0 x1 x4 2 10 1 -1 1 0 0 -2 3 1 - - j=cj -zj 0 5 -3 0 104 表中的检验行中的20 ，且P2向量中所有 分量ai2 0 （i=1,2），所以该问题为无界 解，解题结束。 105 例5，用单纯形法求解线性规划问题 106 解：化为标准形式 107 系数矩阵A为： P1 P2 P3 P4 P5 108 系数矩阵A中不存在单位矩阵，为此在矩阵 中认为地添加两列单位向量P6、P7，使 之与P4构成单位矩阵 P1 P2 P3 P4 P5 P6 P7 109 例6，用单纯形法求解线性规划问题 110 表中的检验行中的j0 ，人工变量x5 仍 留在基变量中且不为零，故问题无可行 解。 111 课后作业 1、某化工厂生产的一种5000克重瓶装涂料， 由A、B两种原料混合而成。工艺规定每瓶涂 料含A种原料应在3000克3500克之间；含 B种原料至少1500克。已知原料A、B的价格 分别为0.4元/克和0.7元/克。那么每瓶涂料中 含A、B各多少可使成本最小，且符合工艺要 求。试写出此问题的数学模型。 112 2、图解法：p47 1.1(a) (b) 3、化标准形式：p48 1.6(a) 4、 p48 1.8 5、用单纯形法求解下列线形规划问题 （a） 113 （b） 114 cj 6 -3 3 0 0 0i cBxB b x1 x2 x3 x4 x5 x6 0 0 0 x4 x5 x6 8 14 18 2 1 0 1 0 0 -4 -2 3 0 1 0 1 -2 1 0 0 1 4 - 18 j=cj -zj 6 -3 3 0 0 0 115 cj 6 -3 3 0 0 0i cBxB b x1 x2 x