运筹学单纯形法例题.pdf

第 1 页 共 9 页 单纯形法例题：某工厂生产 I、II 两种商品,已知生产单位商品所需的设备台时、A、B 两种 原材料的消耗、设备使用台时限额以及原材料的限额如下表所示。该工厂每生产一件商品 I 可获利 3 元，每生产一件商品 II 可获利 4 元。写出使该工厂所获利润最大的线性规划模型, 并用单纯形法求解。 产品 I产品 II限额 设备2140 台时 原材料1330KG 解：设生产产品 I 的数量为 1 x，生产产品 II 的数量为 2 x，所获利润为z，相应的模型为： + + += 0, 303 402 43max 21 21 21 21 xx xx xx xxz 标准型 =+ =+ += 0, 303 402 43max 4321 421 321 21 xxxx xxx xxx xxz 用单纯形法求解。 （1）建立初始单纯行表，即将目标函数和约束条件填入表格中。 3400 b 1 x 2 x 3 x 4 x 402110 301301 （2） 挑选单位阵为初始基。 在本题中初始基, 431 PPB=， 相应的， 基变矢 T B xxX, 431= 。 （3）将初始基, 431 PPB=对应的基变量填入单纯行表中。 3400 B Xb 1 x 2 x 3 x 4 x 3 x402110 4 x301301 这时，我们可以得到初始基, 431 PPB=对应的基可行解。 即令非基变量0, 0 21 =xx，根据表中的约束条件可得30,40 43 =xx（这两个值正好是表 中基变量对应的资源向量b对应的分量，为什么？） 第一个基可行解为 T X30,40, 0 , 0 1= 。 （4）找到了第一个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是 否为最优解的标准是：非基变量 j x对应的检验数 jBjj PBCc= 1 是否0。如果所有 第 2 页 共 9 页 非基变量的检验数 j 均0，那么该基可行解为最优解，如果有一个或若干个非基变量的 检验数 j 0，那么该基可行解不是最优解，需要继续找另一个基可行解。 因为我们选择的初始基IB= 1 ，所以其逆矩阵IB= 1 1 。 相应的，检验数 jBjj PBCc= 1 ， jBjj PCc=。 在计算检验数时需要用到 B C（基变量在目标函数中的系数向量） ，将 B C填入表格中。 3400 B C B Xb 1 x 2 x 3 x 4 x 0 3 x402110 0 4 x301301 接下来就是计算非基变量的检验数（基变量的检验数均等于 0，为什么?） 3400 B C B Xb 1 x 2 x 3 x 4 x 0 3 x402110 0 4 x301301 jBjj PCc= ) 1 ( 00 这时，非基变量的检验数4, 3 21 =均0，所以该基可行解不是最优解。 接下来， 我们的任务就是找另一个基可行解。 当然， 我们希望接下来的这第二个基可行解 2 X 对应的目标函数值比第一个基可行解 1 X。 （5）找另一个基可行解。 由非基变量基变量的决策变量，我们称之为进基变量，挑选原则：0max jj k =， 那么 k x进基（即由非基变量变为基变量） 。 由 基 变 量非 基 变 量 的 决 策 变 量 ， 我 们 称 之 为 出 基 变 量 ， 挑 选 原 则 ： 0min ik ik i a a b lk l a b =，那么原来的第l个基变量出基（即由基变量变为非基变量） 。 我们称 lk a为主元。 题中， 进基变量： 221 4, 3max= k ， 即 2 x进基成为基变量。 第 3 页 共 9 页 出基变量：= 0min ik ik i a a b 22 2 12 1 ,min a b a b =10 3 30 ,40 1 40 min 22 2 a b =，即第 2 个 基变量出基，第 2 个基变量是 4 x，所以是 4 x出基成为非基变量。主元为 22 a。 总结： 2 x进基成为基变量， 4 x出基成为非基变量。也就是说 2 x代替 4 x成为基变量，即： 3400 B C B Xb 1 x 2 x 3 x 4 x ik i a b 0 3 x402110 40 1 40 = 0 4 x30130110 3 30 = jBjj PCc= ) 1 ( 3400 0 3 x 4 2 x 这时的基变矢 T B xxX, 232 =。这两个基变量对应的系数列向量组成的矩阵即为 2 B。 因为在计算非基变量的检验数的计算过程中会用到 1 2 B,计算逆矩阵是一件麻烦事，我们当 然不想干，怎么办呢？为了计算简便，我们期待IPPB=, 232 ，目前我们只是期待而已。 3400 B C B Xb 1 x 2 x 3 x 4 x ik i a b 0 3 x402110 40 1 40 = 0 4 x30130110 3 30 = jBjj PCc= ) 1 ( 3400 0 3 x01 4 2 x10 第 4 页 共 9 页 jBjj PCc= )2( 先来看主元 22 a所在的行。行的系数表示的是约束条件： 421 330xxx+=。 我们期待的是：在这个约束条件中， 2 x的系数1， 3 x的系数0。要做到这一点，只需在 等式左右同除以 3（主元 22 a本身） ，得 421 3 1 3 1 10xxx+=，式与式等价。 接着看另一行。即第一行，该行的系数表示的是约束条件： 321 240xxx+=。 我们期待的是：在这个约束条件中， 2 x的系数0， 3 x的系数1。要做到这一点，需要将 1 431 3 1 3 5 30xxx+=，式与式等价。 为实现我们的期待，将约束条件 += += 421 321 330 240 xxx xxx 就等价的代换成 += += 421 431 3 1 3 1 10 3 1 3 5 30 xxx xxx 将这些系数填入表格中。 3400 B C B Xb 1 x 2 x 3 x 4 x ik i a b 0 3 x402110 40 1 40 = 0 4 x30130110 3 30 = jBjj PCc= ) 1 ( 3400 0 3 x30 3 5 01 3 1 4 2 x10 3 1 10 3 1 jBjj PCc= )2( 这时，我们可以得到基, 232 PPB=对应的基可行解。 即令非基变量0, 0 41 =xx，根据表中的约束条件可得10,30 23 =xx（这两个值正好是表 中基变量对应的资源向量b对应的分量） 第 5 页 共 9 页 那么，第 2 个基可行解为 T X 0 , 30,10, 0 2 =。 （6）找到了第 2 个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是 否为最优解的标准前面已经详细讲述，这里就不啰唆了。即转回到步骤（4） 。 3400 B C B Xb 1 x 2 x 3 x 4 x ik i a b 0 3 x402110 40 1 40 = 0 4 x30130110 3 30 = jBjj PCc= ) 1 ( 3400 0 3 x30 3 5 01 3 1 4 2 x10 3 1 10 3 1 jBjj PCc= )2( 3 5 00 3 4 这时，非基变量的检验数 3 4 , 3 5 41 =，其中0 1 ，所以该基可行解不是最优解。 （7）接下来，我们的任务就是找另一个基可行解。即转回到步骤（5） 。 选择进基变量： 11 3 5 max= = k ，即 1 x进基成为基变量。 出基变量： 21 2 11 1 ,min a b a b =30310,18 5 3 30min 11 1 a b =，即第 1 个基变量出基， 第 1 个基变量是 3 x，所以是 3 x出基成为非基变量。主元为 11 a。 总结： 1 x进基成为基变量， 3 x出基成为非基变量。也就是说 1 x代替 3 x成为基变量，即： 3400 B C B Xb 1 x 2 x 3 x 4 x ik i a b 0 3 x402110 40 1 40 = 0 4 x30130110 3 30 = 第 6 页 共 9 页 jBjj PCc= ) 1 ( 3400 0 3 x30 3 5 01 3 1 18 5 3 30= 4 2 x10 3 1 10 3 1 30310= jBjj PCc= )2( 3 5 00 3 4 3 1 x 4 2 x jBjj PCc= )3( 这时的基变矢 T B xxX, 213 =。这两个基变量对应的系数列向量组成的矩阵即为 3 B。 同样的，我们期待IPPB=, 213 。 3400 B C B Xb 1 x 2 x 3 x 4 x ik i a b 0 3 x402110 40 1 40 = 0 4 x30130110 3 30 = jBjj PCc= ) 1 ( 3400 0 3 x30 3 5 01 3 1 18 5 3 30= 4 2 x10 3 1 10 3 1 30310= jBjj PCc= )2( 3 5 00 3 4 3 1 x10 4 2 x01 jBjj PCc= )3( 第 7 页 共 9 页 先来看主元 11 a所在的行。行的系数表示的是约束条件： 431 3 1 3 5 30xxx+=。 我们期待的是：在约束条件中， 1 x的系数1， 2 x的系数0。要做到这一点，只需在等式 左右同除以 3 5 （主元 11 a本身） ，得 431 3 1 5 3 18xxx+=，式与式等价。 接着看另一行。即第二行，该行的系数表示的是约束条件： 421 3 1 3 1 10xxx+=。 我们期待的是：在约束条件中， 1 x的系数0， 2 x的系数1。 要做到这一点，需要将 3 1 432 5 2 5 1 4xxx+=，式与式 等价。 约束条件 += += 421 431 3 1 3 1 10 3 1 3 5 30 xxx xxx 就等价的代换成 += += 432 431 5 2 5 1 4 5 1 5 3 18 xxx xxx 将这些系数填入表格中。 3400 B C B Xb 1 x 2 x 3 x 4 x ik i a b 0 3 x402110 40 1 40 = 0 4 x30130110 3 30 = jBjj PCc= ) 1 ( 3400 0 3 x30 3 5 01 3 1 18 5 3 30= 4 2 x10 3 1 10 3 1 30310= jBjj PCc= )2( 3 5 00 3 4 3 1 x1810 5 3 5 1 4 2 x401 5 1 5 2 jBjj PCc= )3( 第 8 页 共 9 页 这时，我们可以得到基, 213 PPB=对应的基可行解。 即令非基变量0, 0 43 =xx，根据表中的约束条件可得4,18 21 =xx（这两个值正好是表 中基变量对应的资源向量b对应的分量） 那么，第 3 个基可行解为 T X0 , 0 , 4 ,18 3 =。 （8）找到了第 3 个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是 否为最优解的标准前面已经详细讲述，这里就不啰唆了。即转回到步骤（4） 。 3400 B C B Xb 1 x 2 x 3 x 4 x ik i a b 0 3 x402110 40 1 40 = 0 4 x30130110 3 30 = jBjj PCc= ) 1 ( 3400 0 3 x30 3 5 01 3 1 18 5 3 30= 4 2 x10 3 1 10 3 1 30310= jBjj PCc= )2( 3 5 00 3 4 3 1 x1810 5 3 5 1 4 2 x401 5 1 5 2 jBjj PCc= )3( 0011 这时，非基变量的检验数1, 1 43 =，均0，所以该基可行解就是最优解。 即 T X0 , 0 , 4 ,18= ，7044183=+= bCz B 。 练习题练习题 1 1 1 1、某工厂生产两种构件，甲构件每件占地 10 平方米，需要劳动力 150 个；乙构件 每