工程优化第5章3

1、设 A 中不包含m阶单位矩阵引入人工变量得到(5)的一个基本可行解：显然(5)的系数矩阵中包含一个m阶单位矩阵，取做基矩阵，人工变量人为引入变量的个数变多了，线性规划的维数变大了把每个等式增加一个非负变量，得到如何排除人工变量，求出原线性规划的最优解呢？常用方法：两阶段法、大M法 时，(5)与原问题的约束等价第一页，共五十页。 两阶段法的第一阶段是用单纯形法消去人工变量(可以的话)，即把人工变量都变换成非基变量，求出原来问题的一个基本可行解。 消去人工变量的其中一种方法其中e是分量全为1的 m 维列向量，两阶段法的基本思想是解下列一个问题：第二页，共五十页。 两阶段法的基本思想设(6)的最优基

2、本可行解是 事实上，如果(LP)存在可行解 ，则 是(6)的可行解，对应(6)的目标函数值是矛盾！是(6)的最优解这时，m个基变量都是原来的变量， 是(6)的基本可行解，(i) 若 ，则标准的线性规划(LP)没有可行解；(ii) 若 ，且 xa 的分量都是非基变量。是(LP)的一个基本可行解。第三页，共五十页。 两阶段法的基本思想设(6)的最优基本可行解是 此时的最优值是0.这时，可用主元消去法，把原来变量中的非基变量引进基，替换出基变量中的人工变量，此时的最优值一直都保持是0，从而就 得到(LP)的一个基本可行解。第一阶段结束，得到原来线性规划的一个基本可行解。(iii) 若 ，且 xa 的

3、某些分量是基变量。可化为第(ii)种情况，第四页，共五十页。 两阶段法的第二阶段，就是从得到的基本可行解出发，用单纯形法求问题(LP)的最优解。第五页，共五十页。例1. 利用两阶段法求解如下的线性规划问题。 min -2x1-x2 s.t. x1 +x2 2 x1 -x2 1 x1 3 x1, x20min -2x1-x2 s.t. x1 +x2 - x3 = 2 x1 - x2 - x4 = 1 x1 + x5 = 3 xj 0 , j=1,2,5解： 1. 首先把问题化成标准形式：系数矩阵中不包含单位矩阵第六页，共五十页。min x6+ x7 s.t. x1 +x2 - x3 + x6 =

4、 2 x1 - x2 - x4 + x7 = 1 x1 + x5 = 3 xj 0 , j=1,2,7 2. 引进人工变量x6 ,x7构造单位矩阵，求解下面的问题 3. x6 , x7 , x 5对应的是单位矩阵，可选择作为基变量，建立单纯形表，利用主元消去法，进行迭代。min -2x1-x2 s.t. x1 +x2 - x3 = 2 x1 - x2 - x4 = 1 x1 + x5 = 3 xj 0 , j=1,2,5第七页，共五十页。xB x1 x2 x3 x4 x5 x6 x7 1 1 -1 0 0 1 01 -1 0 -1 0 0 11 0 0 0 1 0 0 x6x7x5 2 1 3

5、 2 0 -1 -1 0 0 00 2 -1 1 0 1 -11 -1 0 -1 0 0 10 1 0 1 1 0 -1x6x1x5 1 1 2 0 2 -1 1 0 0 -2cB110 2 1 3 1/2 - 2100 x2x1x50 1 -1/2 1/2 0 1/2 -1/21 0 -1/2 -1/2 0 1/2 1/20 0 1/2 1/2 1 -1/2 -1/2 1/2 3/2 3/2 0 0 0 0 0 -1 -1000c 0 0 0 0 0 1 1 min x6+ x7 s.t. x1 +x2 - x3 + x6 = 2 x1 - x2 - x4 + x7 = 1 x1 + x5

6、= 3 xj 0 , j=1,2,7第八页，共五十页。x2x1x50 1 -1/2 1/2 0 1/2 -1/21 0 -1/2 -1/2 0 1/2 1/20 0 1/2 1/2 1 -1/2 -1/2 1/2 3/2 3/2 0 0 0 0 0 -1 -1000 xB x1 x2 x3 x4 x5 x6 x7 cBc 0 0 0 0 0 1 1 4. 所有判别数 zj-cj0 ，因此达到最优解。 从表中看到：在一阶段问题的最优解中，人工变量x6 , x7都是非基变量。所以我们得到了原线性规划的基本可行解 :第九页，共五十页。xB x1 x2 x3 x4 x5 cB-1-2 00 1 -1/

7、2 1/2 0 1 0 -1/2 -1/2 0 0 0 1/2 -1/2 1 x2x1x5 1/2 3/2 3/2min -2x1-x2 s.t. x1 +x2 - x3 = 2 x1 - x2 - x4 = 1 x1 + x5 = 3 xj 0 , j=1,2,5 0 0 3/2 1/2 0c -2 -1 0 0 0 5. 第二阶段，修改最后的单纯形表。x2x1x50 1 -1/2 1/2 0 1/2 -1/21 0 -1/2 -1/2 0 1/2 1/20 0 1/2 1/2 1 -1/2 -1/2 1/2 3/2 3/2 0 0 0 0 0 -1 -1000 xB x1 x2 x3 x4

8、 x5 x6 x7 cBc 0 0 0 0 0 1 1 修改检验数和目标函数，去掉人工变量对应的列，其他不变。第十页，共五十页。xB x1 x2 x3 x4 x5 x2x1x3 2 3 3 0 0 0 -1 -3 cB-1-2 0 - - 3-1-2 00 1 -1/2 1/2 0 1 0 -1/2 -1/2 0 0 0 1/2 -1/2 1 x2x1x5 1/2 3/2 3/2 0 0 3/2 1/2 00 1 0 0 1 1 0 0 -1 1 0 0 1 -1 2 c -2 -1 0 0 0 6. 这时，检验数全部小于等于0，得到最优解： x = (3,2,3,0,0)T目标函数的最小值为

9、： f = -2*3-1*2=- 8第十一页，共五十页。例2. 利用两阶段法求解如下的线性规划问题。 min f = x1-x2 s.t. -x1+ 2x2 + x3 2 -4x1 +4x2 - x3 =4 x1 - x3 = 0 x1, x2, x3 0解： 1. 引入松弛变量x4，把上述问题转化为标准形式min f =x1- x2 s.t. -x1+ 2x2 + x3 + x4 = 2 -4x1 +4x2 - x3 =4 x1 - x3 = 0 x1, x2, x3 ,x40系数矩阵中不包含单位矩阵第十二页，共五十页。min f =x5+ x6 s.t. -x1+ 2x2 + x3 + x

10、4 = 2 -4x1 +4x2 - x3 + x5 =4 x1 - x3 + x6 = 0 x1, x2, x3 ,x4, x5, x6 0 3. x4 ，x5 ， x 6对应的是单位矩阵，可选择作为基变量，建立单纯形表，利用主元消去法，进行迭代。2. 引进人工变量 x5 , x6构造单位矩阵，用单纯形法求解下面的问题min f =x1- x2 s.t. -x1+ 2x2 + x3 + x4 = 2 -4x1 +4x2 - x3 =4 x1 - x3 = 0 x1, x2, x3 ,x40第十三页，共五十页。xB x1 x2 x3 x4 x5 x6 x4x5x6 2 4 0 -3 4 -2 0

11、 0 0 x2x5x6 1 0 0cB011 1 1 -011-1 2 1 1 0 0-4 4 -1 0 1 0 1 0 -1 0 0 1-1/2 1 -1/2 1/2 0 0-2 0 -3 -2 1 0 1 0 -1 0 0 1 -1 0 -4 -2 0 0 min f =x5+ x6 s.t. -x1+ 2x2 + x3 + x4 = 2 -4x1 +4x2 - x3 + x5 =4 x1 - x3 + x6 = 0 x1, x2, x3 ,x4, x5, x6 0c 0 0 0 0 1 14. 所有判别数 zj-cj0 ，达到最优解。在一阶段问题的最优解中，人工变量x5 ，x6 是基变量

12、并且都取0。用原来的变量（非人工变量）把人工变量从基变量中换出去。第十四页，共五十页。xB x1 x2 x3 x4 x5 x6 x2x5x6 1 0 0cB011-1/2 1 -1/2 1/2 0 0-2 0 -3 -2 1 0 1 0 -1 0 0 1 -1 0 -4 -2 0 0 c 0 0 0 0 1 1用原来变量(x1 , x2 , x3 , x4)中的非基变量x1 ，x3 和x4将人工变量x5 , x6 从基变量中换掉。 此时，判别数、价格系数和 都可略去。xB x1 x2 x3 x4 x5 x6 x2x5x1 1 0 00 1 0 1/2 0 1/20 0 -5 -2 1 21 0

13、 -1 0 0 1主元消去期间不会改变最优值0，最优解之间的变换。第十五页，共五十页。 用原来变量(x1 , x2 , x3 , x4)中的非基变量x1 ，x3 和x4将人工变量x5 , x6 从基变量中换掉。xB x1 x2 x3 x4 x5 x6 x2x5x1 1 0 00 1 0 1/2 0 1/20 0 -5 -2 1 21 0 -1 0 0 1主元消去xB x1 x2 x3 x4 x5 x6 x2x3x1 1 0 00 1 0 1/2 0 1/20 0 1 2/5 -1/5 -2/51 0 0 2/5 -1/5 3/55. 基变量均为原来的变量，得到原问题的一个基本可行解第十六页，共

14、五十页。6. 第二阶段，修改最后的单纯形表。加上检验数行，按照定义计算检验数和目标函数值。去掉人工变量对应的列。其他不变。 xB x1 x2 x3 x4 x5 x6 x2x3x1 1 0 00 1 0 1/2 0 1/20 0 1 2/5 -1/5 -2/51 0 0 2/5 -1/5 3/5xB x1 x2 x3 x4x2x3x1 1 0 00 1 0 1/20 0 1 2/51 0 0 2/5cBcmin f = x1-x2 s.t. -x1+ 2x2 + x3 2 -4x1 +4x2 - x3 =4 x1 - x3 = 0 x1, x2, x3 0 1 -1 0 0-1 0 10 0 0

15、 -1/10 7. 这时，检验数全部小于等于0，得到最优解： x = (0,1,0,0)T最优值为: f = 0*1- 1*1=-1第十七页，共五十页。大 M 法标准线性规划问题:A = ( aij)mn , b 0, 秩(A)= m . 如果 A 中不包含m阶单位矩阵，我们就不能明显得到线性规划的一个基本可行解 此时除了可以采用两阶段法之外，还可以利用大M法求解线性规划。第十八页，共五十页。大 M 法的基本思想在约束中添加人工变量 ，M0, e 为全1的m维列向量。(7)是可行的,基本可行解 由于大M是充分大的正数，在极小化目标函数的过程中，就会迫使人工变量离基。同时修改目标函数，加上惩罚项

16、通过求解(7)而获得(LP)的最优解第十九页，共五十页。 用单纯形法求解(7)，如果(7)存在有限最优解，设为(ii) 当 时，问题(LP)无可行解。(i) 当 时, x*是问题(LP)的最优解。 事实上，如果(LP)存在可行解 ，则 是(7)的可行解，对应(7)的目标函数值是M是充分大的正数是(7)的最优解矛盾！第二十页，共五十页。在单纯形表中如果(7)不存在有限最优解(i) 当 时，问题(LP)无界;(ii) 当 时，即 ，问题(LP)无可行解.第二十一页，共五十页。例3. 利用大M法求解如下的线性规划问题。 min x1+x2 -3x3 s.t. x1 -2x2 + x3 11 2x1

17、+ x2 - 4x3 3 x1 - 2x3 = 1 x1, x2 , x3 0解： 1. 将问题化成标准形式，引进松弛变量x4 ,剩余变量x5min x1+x2 -3x3 s.t. x1 -2x2 + x3 + x4 = 11 2x1 + x2 - 4x3 - x5 = 3 x1 - 2x3 = 1 xj0, j=1,2,5系数矩阵中不包含单位矩阵第二十二页，共五十页。2. 引进人工变量x6 ,x7 构造单位矩阵，用单纯形法求解下列问题min x1+x2 -3x3+ M(x6 +x7) s.t. x1 -2x2 + x3 + x4 = 11 2x1 + x2 - 4x3 - x5 + x 6

18、= 3 x1 - 2x3 + x 7 = 1 xj,0, j=1,2,73. x4 ，x6 ， x 7 对应的是单位矩阵，可选择作为基变量，建立单纯形表，利用主元消去法，进行迭代。第二十三页，共五十页。xB x1 x2 x3 x4 x5 x6 x7 x4x6x711 3 13M-1 M-1 -6M+3 0 -M 0 0 x4x6x1 10 1 1 0 M-1 1 0 -M 0 1-3McB0MM113/2 1 - 1 - 0M 1x4x2x1 12 1 1011c 1 1 -3 0 0 M M1 -2 1 1 0 0 02 1 -4 0 -1 1 01 0 -2 0 0 0 1min x1+x

19、2 -3x3+ M(x6 +x7) s.t. x1 -2x2 + x3 + x4 = 11 2x1 + x2 - 4x3 - x5 + x 6 = 3 x1 - 2x3 + x 7 = 1 xj,0, j=1,2,70 -2 3 1 0 0 -10 1 0 0 -1 1 -21 0 -2 0 0 0 10 0 3 1 -2 2 -50 1 0 0 -1 1 -21 0 -2 0 0 0 1 0 0 1 0 -1 1-M -1-M 4 - -第二十四页，共五十页。 0 0 0 -1/3 -1/3 1/3-M 2/3-M 4 1 9xB x1 x2 x3 x4 x5 x6 x7 cBx4x2x11

20、2 1 1011c 1 1 -3 0 0 M M0 0 3 1 -2 2 -50 1 0 0 -1 1 -21 0 -2 0 0 0 1 0 0 1 0 -1 1-M -1-M 4 - -x3x2x1-3 1 10 0 1 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -21 0 0 2/3 -4/3 4/3 -7/34. 检验数全部小于等于0，并且人工变量全取0， 于是得到最优解：最优值为： f = 9+1-3*4=- 2 x = (9,1,4)T第二十五页，共五十页。单纯性法小结M0不处理令z=- zmax z=-min z减去xs加入xa加入人工变量xa加松弛变量xs约束条

21、件两端同乘以-1不处理令 xj =- xj令xj = xj - xj xj 0 xj 0不处理单纯形法图解法、单纯形法求解 xaxs min zmax z=bi 0 bi 0 xj 0 xj无约束xj0三个以上两个新加变量系数极大或极小等式或不等式右 端 项取 值变量个数建立模型第二十六页，共五十页。作业 1. 用两阶段法或者大M法求解 P159 5.8 5.92. 利用大M法求解如下的线性规划问题。 min -2x1-x2 s.t. x1 +x2 2 x1 -x2 1 x1 3 x1, x20第二十七页，共五十页。线性规划的对偶理论与对偶单纯性法 线性规划早期发展过程中的最为重要的理论成果之

22、一就是线性规划的对偶问题及相关理论的提出。 线性规划的对偶理论是解释资源的影子价格、线性规划问题的灵敏度分析等的理论基础。主要内容 对偶问题定义-线性规划问题写出其对偶问题， 要掌握在对称形式和非对称情况下由原问题写出对偶问 题的方法。 对偶定理-原问题与对偶问题解的关系。 对偶单纯形法第二十八页，共五十页。线性规划的对偶模型 设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表 ：1216812设备可利用机时数(时) 34022乙 20412甲 产品利润（元件） DCBA 设备产品问：充分利用设备机时

23、，工厂应生产甲和乙型产品各多少件才能获得最大利润？1. 对偶问题的现实来源第二十九页，共五十页。解：设甲、乙型产品各生产x1及x2件，则数学模型为： 反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？线性规划的对偶模型第三十页，共五十页。 在市场竞争的时代，厂长的最佳决策显然应符合两条： （1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。 （2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。设A、B、C、D设备的机时价分别为y1、y2、y3、y4，由此原则，便构成了一些不等式约束条

24、件。则新的线性规划数学模型为：第三十一页，共五十页。 把同种问题的两种提法所获得的数学模型表示出来，将会发现一个有趣的现象。第三十二页，共五十页。2. 原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）第三十三页，共五十页。(1) 对称形式特点：目标函数求极小值，约束条件“”，变量非负; 目标函数求极大值，约束条件“”，变量非负; 对偶定义互为对偶第三十四页，共五十页。例 写出下面线性规划的 对偶问题第三十五页，共五十页。 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 方法一： 化成对称形式的线性规划，写出其对偶规划。(2) 非对称形式的对偶问题对偶定义第三十六页，共

25、五十页。例1：写出下列线性规划问题的对偶问题第三十七页，共五十页。第三十八页，共五十页。原问题对偶问题第三十九页，共五十页。例2： 标准形式的对偶问题对偶定义对偶问题第四十页，共五十页。变量数：n个第 j 个变量 0第 j 个变量 0第 j 个变量是自由变量 约束条件： m个第i个约束类型为“”第i个约束类型为“”第i个约束类型为“” 目标函数max对偶问题（原问题）约束条件：n个第 j 个约束类型为“”第 j 个约束类型为“”第 j 个约束类型为“” 变量数： m个第i个变量 0第i个变量 0第i个变量是自由变量 目标函数 min原问题（对偶问题）方法二：按照下面的对应关系直接给出其对偶规划:(2) 非对称形式的对偶问题第四十一页，共五十页。变量数：n个第 j 个变量 0第 j 个变量 0第 j 个变量是自由变量 约束条件： m个第i个约束类型为“”第i个约束类型为“”第i个约束类型为“” 目标函数max对偶问题（原问题）约束条件：n个第 j 个约束类型为“”第 j 个约束类型为“”第