单纯形法例题8页

第 1 页 共 9 页 单纯形法例题：某工厂生产 I、II两种商品,已知生产单位商品所需的设备台时、A、B两种 原 材料 关于××同志的政审材料调查表环保先进个人材料国家普通话测试材料农民专业合作社注销四查四问剖析材料 的消耗、设备使用台时限额以及原材料的限额如下 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 所示。该工厂每生产一件商品 I 可获利 3元，每生产一件商品 II可获利 4元。写出使该工厂所获利润最大的线性规划模型 , 并用单纯形法求解。 产品 I 产品 II 限额 设备 2 1 40台时 原材料 1 3 30KG 解：设生产产品 I的数量为 1x ，生产产品 II的数量为 2x ，所获利润为 z，相应的模型为： ⎪ ⎩ ⎪ ⎨ ⎧ ≥ ≤+ ≤+ += 0, 303 402 43max 21 21 21 21 xx xx xx xxz 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 型 ⎪ ⎩ ⎪ ⎨ ⎧ ≥ =++ =++ += 0,,, 303 402 43max 4321 421 321 21 xxxx xxx xxx xxz 用单纯形法求解。 （1）建立初始单纯行表，即将目标函数和约束条件填入表格中。 3 4 0 0 b 1x 2x 3x 4x 40 2 1 1 0 30 1 3 0 1 （2）挑选单位阵为初始基。在本题中初始基 ],[ 431 PPB = ，相应的，基变矢 T B xxX ],[ 431 = 。 （3）将初始基 ],[ 431 PPB = 对应的基变量填入单纯行表中。 3 4 0 0 B X b 1x 2x 3x 4x 3x 40 2 1 1 0 4x 30 1 3 0 1 这时，我们可以得到初始基 ],[ 431 PPB = 对应的基可行解。 即令非基变量 0,0 21 == xx ，根据表中的约束条件可得 30,40 43 == xx （这两个值正好是表 中基变量对应的资源向量 b 对应的分量，为什么？） 第一个基可行解为 T X ]30,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 填入表格中。 3 4 0 0 B C B X b 1x 2x 3x 4x 0 3x 40 2 1 1 0 0 4x 30 1 3 0 1 接下来就是计算非基变量的检验数（基变量的检验数均等于 0，为什么?） 3 4 0 0 B C B X b 1x 2x 3x 4x 0 3x 40 2 1 1 0 0 4x 30 1 3 0 1 jBjj PCc ⋅−=)1(σ 0 0 这时，非基变量的检验数 4,3 21 == σσ 均>0，所以该基可行解不是最优解。 接下来，我们的任务就是找另一个基可行解。当然，我们希望接下来的这第二个基可行解 2X 对应的目标函数值比第一个基可行解 1X 。 （5）找另一个基可行解。 由非基变量→基变量的决策变量，我们称之为进基变量，挑选原则： { }0max > jj σσ k σ= ， 那么 k x 进基（即由非基变量变为基变量）。 由 基 变 量 → 非 基 变 量 的 决 策 变 量 ， 我 们 称 之 为 出 基 变 量 ， 挑 选 原 则 ： ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ > 0min ik ik i a a b lk l a b = ，那么原来的第 l个基变量出基（即由基变量变为非基变量）。 我们称 lk a 为主元。题中，进基变量： { } 221 4,3max σσσσ ==== k ，即 2x 进基成为基变量。 第 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个基变量是 4x ，所以是 4x 出基成为非基变量。主元为 22a 。 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ： 2x 进基成为基变量， 4x 出基成为非基变量。也就是说 2x 代替 4x 成为基变量，即： 3 4 0 0 B C B X b 1x 2x 3x 4x ik i a b 0 3x 40 2 1 1 0 40 1 40 = 0 4x 30 1 [3] 0 1 103 30 = jBjj PCc ⋅−=)1(σ 3 4 0 0 0 3x 4 2x 这时的基变矢 T B xxX ],[ 232 = 。这两个基变量对应的系数列向量组成的矩阵即为 2B 。 因为在计算非基变量的检验数的计算过程中会用到 12 − B ,计算逆矩阵是一件麻烦事，我们当 然不想干，怎么办呢？为了计算简便，我们期待 IPPB == ],[ 232 ，目前我们只是期待而已。 3 4 0 0 B C B X b 1x 2x 3x 4x ik i a b 0 3x 40 2 1 1 0 40 1 40 = 0 4x 30 1 [3] 0 1 103 30 = jBjj PCc ⋅−=)1(σ 3 4 0 0 0 3x 0 1 4 2x 1 0 第 4 页 共 9 页 jBjj PCc ⋅−=)2(σ 先来看主元 22a 所在的行。行的系数表示的是约束条件： 421 330 xxx ++= ②。 我们期待的是：在这个约束条件中， 2x 的系数＝1， 3x 的系数＝0。要做到这一点，只需在 等式左右同除以 3（主元 22a 本身），得 421 3 1 3 1 10 xxx ++= ②’，式②’与式②等价。 接着看另一行。即第一行，该行的系数表示的是约束条件： 321240 xxx ++= ①。 我们期待的是：在这个约束条件中， 2x 的系数＝0， 3x 的系数＝1。要做到这一点，需要将 ①－ ×1 ②’ 431 3 1 3 5 30 xxx −+=⇒ ①’，式①’与式①等价。 为实现我们的期待，将约束条件 ⎩ ⎨ ⎧ ++= ++= 421 321 330 240 xxx xxx 就等价的代换成 ⎪ ⎩ ⎪ ⎨ ⎧ ++= −+= 421 431 3 1 3 1 10 3 1 3 5 30 xxx xxx 将这些系数填入表格中。 3 4 0 0 B C B X b 1x 2x 3x 4x ik i a b 0 3x 40 2 1 1 0 40 1 40 = 0 4x 30 1 [3] 0 1 103 30 = jBjj PCc ⋅−=)1(σ 3 4 0 0 0 3x 30 3 5 0 1 3 1 − 4 2x 10 3 1 1 0 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）。 3 4 0 0 B C B X b 1x 2x 3x 4x ik i a b 0 3x 40 2 1 1 0 40 1 40 = 0 4x 30 1 [3] 0 1 103 30 = jBjj PCc ⋅−=)1(σ 3 4 0 0 0 3x 30 3 5 0 1 3 1 − 4 2x 10 3 1 1 0 3 1 jBjj PCc ⋅−=)2(σ 3 5 0 0 3 4 − 这时，非基变量的检验数 3 4 , 3 5 41 −== σσ ，其中 01 >σ ，所以该基可行解不是最优解。 （7）接下来，我们的任务就是找另一个基可行解。即转回到步骤（5）。 选择进基变量： 11 3 5 max σσσ == ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ = k ，即 1x 进基成为基变量。 出基变量： ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ 21 2 11 1 ,min a b a b ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ =×=×= 30310,18 5 3 30min 11 1 a b = ，即第 1个基变量出基，第 1个基变量是 3x ，所以是 3x 出基成为非基变量。主元为 11a 。 总结： 1x 进基成为基变量， 3x 出基成为非基变量。也就是说 1x 代替 3x 成为基变量，即： 3 4 0 0 B C B X b 1x 2x 3x 4x ik i a b 0 3x 40 2 1 1 0 40 1 40 = 0 4x 30 1 [3] 0 1 103 30 = 第 6 页 共 9 页 jBjj PCc ⋅−=)1(σ 3 4 0 0 0 3x 30 [ 3 5 ] 0 1 3 1 − 18 5 3 30 =× 4 2x 10 3 1 1 0 3 1 30310 =× jBjj PCc ⋅−=)2(σ 3 5 0 0 3 4 − 3 1x 4 2x jBjj PCc ⋅−=)3(σ 这时的基变矢 T B xxX ],[ 213 = 。这两个基变量对应的系数列向量组成的矩阵即为 3B 。 同样的，我们期待 IPPB == ],[ 213 。 3 4 0 0 B C B X b 1x 2x 3x 4x ik i a b 0 3x 40 2 1 1 0 40 1 40 = 0 4x 30 1 [3] 0 1 103 30 = jBjj PCc ⋅−=)1(σ 3 4 0 0 0 3x 30 [ 3 5 ] 0 1 3 1 − 18 5 3 30 =× 4 2x 10 3 1 1 0 3 1 30310 =× jBjj PCc ⋅−=)2(σ 3 5 0 0 3 4 − 3 1x 1 0 4 2x 0 1 jBjj PCc ⋅−=)3(σ 第 7 页 共 9 页 先来看主元 11a 所在的行。行的系数表示的是约束条件： 431 3 1 3 5 30 xxx −+= ①’。 我们期待的是：在约束条件中， 1x 的系数＝1， 2x 的系数＝0。要做到这一点，只需在等式 左右同除以 3 5（主元 11a 本身），得 431 3 1 5 3 18 xxx −+= ①’’，式①’’与式①’等价。 接着看另一行。即第二行，该行的系数表示的是约束条件： 421 3 1 3 1 10 xxx ++= ②’。 我们期待的是：在约束条件中， 1x 的系数＝0， 2x 的系数＝1。 要做到这一点，需要将②’－ × 3 1 ①’’ 432 5 2 5 1 4 xxx +−=⇒ ②’’，式②’’与式②’ 等价。 约束条件 ⎪ ⎩ ⎪ ⎨ ⎧ ++= −+= 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 将这些系数填入表格中。 3 4 0 0 B C B X b 1x 2x 3x 4x ik i a b 0 3x 40 2 1 1 0 40 1 40 = 0 4x 30 1 [3] 0 1 103 30 = jBjj PCc ⋅−=)1(σ 3 4 0 0 0 3x 30 [ 3 5 ] 0 1 3 1 − 18 5 3 30 =× 4 2x 10 3 1 1 0 3 1 30310 =× jBjj PCc ⋅−=)2(σ 3 5 0 0 3 4 − 3 1x 18 1 0 5 3 5 1 − 4 2x 4 0 1 5 1 − 5 2 jBjj PCc ⋅−=)3(σ 第 8 页 共 9 页 这时，我们可以得到基 ],[ 213 PPB = 对应的基可行解。 即令非基变量 0,0 43 == xx ，根据表中的约束条件可得 4,18 21 == xx （这两个值正好是表 中基变量对应的资源向量 b 对应的分量） 那么，第 3个基可行解为 T X ]0,0,4,18[3 = 。 （8）找到了第 3个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是 否为最优解的标准前面已经详细讲述，这里就不啰唆了。即转回到步骤（4）。 3 4 0 0 B C B X b 1x 2x 3x 4x ik i a b 0 3x 40 2 1 1 0 40 1 40 = 0 4x 30 1 [3] 0 1 103 30 = jBjj PCc ⋅−=)1(σ 3 4 0 0 0 3x 30 [ 3 5 ] 0 1 3 1 − 18 5 3 30 =× 4 2x 10 3 1 1 0 3 1 30310 =× jBjj PCc ⋅−=)2(σ 3 5 0 0 3 4 − 3 1x 18 1 0 5 3 5 1 − 4 2x 4 0 1 5 1 − 5 2 jBjj PCc ⋅−=)3(σ 0 0 1− 1− 这时，非基变量的检验数 1,1 43 −=−= σσ ，均<0，所以该基可行解就是最优解。 即 T X ]0,0,4,18[=∗ ， 7044183 =×+×=⋅=∗ bCz B 。 练习题 1111、某工厂生产两种构件，甲构件每件占地 10平方米，需要劳动力 150个；乙构件 每件占地 2平方米，需要劳动力 25个。该厂共有生产用地 720平方米，每月劳动力 10000 个。同时，因为受到其他设备限制，每月最多能生产甲构件 50件，乙构件 200件。若每个 第 9 页 共 9 页 甲构件能获利 250元，每个乙构件能获利 50元，要想获得最大的利润，每月应该生产甲、 乙构件各多少件？ 练习题 2222、求解下面线性规划问题。 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≤+− ≤+ ≤+− ++= − 0 204 10 50533 .. 1020max 31 321 31 321 321 x xxx xx xxx ts xxxz