第二章单纯形方法

Linear programming model and application第 1章 线性规划问题的数学模型第 2章 单纯形方法第 3章 对偶线性规划问题第 4章 运输问题第 5章 整数规划2/47数学建模方法2-1 基本概念 2-2 单纯形方法的基本思路2-3 单纯形方法一、线性规划问题的标准形二、基本概念一、单纯形表及其结构二、单纯形方法的步骤3/47数学建模方法从两个变量线性规划问题的图解法可以看出：一、线性规划问题的标准形1.线性规划问题的可行解集是凸集 (连接任意两点的直线仍在可行解集中 )；2.线性规划问题若有最优解，则其最优解必可在其可行解集的顶点上达到。因此就为我们求其最优解带来了方便，产生了求解线性规划问题的有效方法 单纯形方法 。 本节对 单纯形方法 进行介绍。 4/47数学建模方法 线性规划问题的标准形 (特征 )(1)求目标函数的最大值；(2)所有约束条件都是等式约束，且右端常数项非负；(3)所有变量都有非负限制。5/47数学建模方法对于不符合标准形要求的 LP问题，一定可化成标准形。具体步骤如下 : 1.目标函数的改写 : 化求最小值为求最大值2.化不等式约束为等式约束 增加的变量称为 松弛变量 或剩余变量 ，以后将松弛变量和剩余变量统称为松弛变量 。6/47数学建模方法3.对于没有非负限制的化为有非负限制若 xk无非负限制，则引进 4.如果约束条件右端的常数项小于零，则用 -1乘以该式两端。7/47数学建模方法例 1 将下面线性规划问题化为标准形则原 LP的标准形为：解 :引入松弛变量 x40,x50,x30, x“30并令 x3=x3-x“38/47数学建模方法若记： 线性规划问题表示成 矩阵形式 ：或记 , 分别为 的系数列向量。 则线性规划问题可表示成 向量组合形式 ： 9/47数学建模方法设线性规划问题 (LP)： 二、基本概念可行解 : 我们称满足所有约束条件的 为线性规划问题的可行解。 最优解 : 使目标函数取到最大值的可行解 , 称为 (LP)的最优解。基 ：若系数矩阵 的秩为 m，称 A的任一 非奇异子矩阵 为线性规划问题 (LP)的一个基。 若 为 (LP)的 一个基 ， 与基向量对应变量 其余的称为 非基变量 。 称为 基变量 ，称为 基向量 ，N是 非基向量组成的矩阵 ，对应变量 组成的列向量记为 ； 分别是 基变量的系数 和 非基变量的系数 组成的行向量。 10/47数学建模方法记 ： 则 则线性规划问题的 目标函数 和 约束方程组 可以表示成：（ 2.1） 即 (2.2)因 B可逆 , 用 B-1左乘 (2.2)式两端得 (2.3) (2.3)是基变量用非基变量表示的表达式。称为对应于基 B的 基本解 。基可行解 ： 满足非负条件的基本解，称为 (LP)的 基可行解 。11/47数学建模方法可行基： B是 (LP)的一个基，若满足 ，这时 就是对应于基 B的一个可行解， 称为 (LP)的一个可行基。 基最优解： 使目标函数达到最大值的 基可行解 就是 基最优解 。理论上可以证明，只要 (LP)最优解存在，则一定有基最优解。 例 2 对于线性规划问题：引进松弛变量化成标准形 可以表示成矩阵形式： 12/47数学建模方法其中 很显然 A中任意 33的非奇异子矩阵都是 (LP)的一个基。 13/47数学建模方法是对应的基本解，它不是基可行解， B也不是可行基。 是 (LP)的一个基， 对应的 是基变量， 是非基变量。 如取 是 (LP)的一个基， 对应的 是基变量， 是非基变量。 14/47数学建模方法如取： 是 (LP)的一个基， 对应的 x3,x4,x5是基变量， x1,x2是非基变量。若令 x4=x5=0,得 X=(4,3,-2,0,0)T是对应的基本解 ,它也不是基可行解 .B1也不是可行基。 若令 x1=x2=0,得 X=(0,0,8,16,12)T是对应的基本解 ,它是基可行解 .B2是可行基。 15/47数学建模方法它的最优解一定在这些基可行解中求得。 线性规划问题的可行解、基本解和基可行解的关系如图 1-5所示。 通过以上介绍 ,大家可以熟悉线性规划问题的基本概念。 至多有 个可行基 ,至多有 对于该例中标准形的线性规划问题 ,它至多有 个基 ,个基可行解，基本解可行解基可行解图 1-516/47数学建模方法对例 2,实际上是求线性方程组 (2.4) 的非负解，且使 取到最大值。将目标函数改为为求 (2.4) 非负解 ,要求右端常数项非负 ,当自由未知量 (非基变量 )取0值时 , 基变量取值就是表达式右端常数项的值 , 得到基可行解 .由 (2.4)解得 基可行解 17/47数学建模方法从目标函数式 S=2x1+3x2可以看出 :若 x1,x2不取 0值 ,可使目标函数值增大 . 增大 x2的值 ,由 (2.4)式施行初等变换(2.5) 即 得对应基 的基可行解 18/47数学建模方法由 (2.5)式施行初等变换： 从目标函数式 可以看出 ,若 x1不取 0值 , 则可使目标函数值增大。即 (2.6) 的基可行解 . 19/47数学建模方法从目标函数式 可以看出 ,若 x5不取 0值, 则可使目标函数值增大。 由 (2.6)式施行初等变换： 即 (2.7) 的基可行解 . 即为 最优解 . 20/47数学建模方法以上四个步骤，就是单纯形方法的基本思想。每一步都是把基变量与目标函数表示成非基变量的表达式。 如果把上述步骤用一些表表示出来，其实就是单纯形表与单纯形方法。每一步都是把基变量与目标函数表示成非基变量的表达式： 对于 (2.4)式 表 2-1 基 B=(P3,P4,P5)所对应的单纯形表 对应的基可行解 21/47数学建模方法 对于 (2.5)式 表 2-2 基 B=(P3,P4,P2)所对应的单纯形表 对应的基可行解 对于 (2.6)式 表 2-3 基 B=(P1,P4,P2)所对应的单纯形表 对应的基可行解 22/47数学建模方法去掉松弛变量得到原问题的 最优解： 表 2-4 基 B=(P1,P5,P2)所对应的单纯形表 基 B =(P1,P5,P2)为最优基，对应的最优解为： 对于 (2.7)式这种以表格 (就是单纯形表 )计算的方法就是单纯形方法。23/47数学建模方法运行结果如下：Global optimal solution found.Objective value: 14.00000Total solver iterations: 1Variable Value Reduced CostX1 4.000000 0.000000X2 2.000000 0.000000Row Slack or Surplus Dual Price1 14.00000 1.0000002 0.000000 1.5000003 0.000000 0.12500004 4.000000 0.000000max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=12;用 LINGO10.0求解 ,程序：24/47数学建模方法设线性规划问题 (LP) 若 B是线性规划问题 (LP)一个基， 因 B可逆 ,则用 B-1左乘上式两端，得 一、单纯形表及其结构(2.8) 称为 (LP)对应于基 B的 基本解 . 25/47数学建模方法对应的基可行解 则有目标函数 则对应于 (LP)的基础解 的目标函数值为 则基 B为 (LP)的一个可行基，26/47数学建模方法故目标函数可改写成： 将其与约束条件写在一起，就可以得到单纯形表27/47数学建模方法若记： 则单纯形表的结构为：表 2-5 基 B=(Pj1,Pj2, ,Pjm)所对应的单纯形表 28/47数学建模方法若用解析式子表示，就是：特别是所给的线性规划问题中，其约束条件方程组的系数矩阵中含有一个单位矩阵，且右端的常数项非负时，这时以这个单位矩阵为基就是 (LP) 的一个明显的可行基，可以立即得到这个可行基所对应的单纯形表。29/47数学建模方法例如 ，对线性规划问题：可立即得到单纯形表如表 2