（最新）运筹学单纯形法例题

（最新）运筹学单纯形法例题单纯形法例题:某工厂生产 I、II 两种商品,已知生产单位商品所需的设备台时、A、 B 两种原材料的消耗、设备使用台时限额以及原材料的限额如下表所示。该工厂每生产一件商品 I 可获利 3 元，每生产一件商品 II 可获利 4 元。写出使该工厂所获利润最大的线性规划模型, 并用单纯形法求解。产品 I 设备原材料 2 1 产品 II 1 3 限额 40 台时 30KG 解:设生产产品 I 的数量为 x1 ，生产产品 II 的数量为 x 2 ，所获利润为 z ，相应的模型为: max z = 3 x1 + ...

单纯形法例题:某工厂生产 I、II 两种商品,已知生产单位商品所需的设备台时、A、 B 两种原材料的消耗、设备使用台时限额以及原材料的限额如下表所示。该工厂每生产一件商品 I 可获利 3 元，每生产一件商品 II 可获利 4 元。写出使该工厂所获利润最大的线性规划模型, 并用单纯形法求解。产品 I 设备原材料 2 1 产品 II 1 3 限额 40 台时 30KG 解:设生产产品 I 的数量为 x1 ，生产产品 II 的数量为 x 2 ，所获利润为 z ，相应的模型为: max z = 3 x1 + 4 x2 ?2 x1 + x2 ? 40 ? ? x1 + 3 x2 ? 30 ?x , x ? 0 ? 1 2 MATCH_ word _1714045397573_0型 max z = 3 x1 + 4 x 2 ?2 x1 + x 2 + x3 = 40 ? ? x1 + 3x 2 + x 4 = 30 ?x , x , x , x ? 0 ? 1 2 3 4 用单纯形法求解。 (1)建立初始单纯行表，即将目标函数和约束条件填入表格中。 3 4 0 0 b 40 30 x1 2 1 x2 1 3 x3 1 0 x4 0 1 (2) 挑选单位阵为初始基。在本题中初始基 B1 = [ P3 , P4 ] ，相应的，基变矢 X B1 = [ x3 , x 4 ]T 。 (3)将初始基 B1 = [ P3 , P4 ] 对应的基变量填入单纯行表中。 3 4 0 0 XB b 40 30 x1 2 1 x2 1 3 x3 1 0 x4 0 1 x3 x4 这时，我们可以得到初始基 B1 = [ P3 , P4 ] 对应的基可行解。即令非基变量 x1 = 0, x 2 = 0 ，根据表中的约束条件可得 x3 = 40, x 4 = 30(这两个值正好是表中基变量对应的资源向量 b 对应的分量，为什么,) 第一个基可行解为 X 1 = [0,0,40,30]T 。 (4)找到了第一个基可行解，接下来的任务就是判断该基可行解是否为最优解，检验其是否为最优解的标准是:非基变量 x j 对应的检验数 σ j = c j ? C B ? B ?1 ? P j 是否 ? 0 。如果所有第 1 页共 9 页非基变量的检验数 σ j 均 ? 0 ，那么该基可行解为最优解，如果有一个或若干个非基变量的检验数 σ j > 0 ，那么该基可行解不是最优解，需要继续找另一个基可行解。因为我们选择的初始基 B1 = I ，所以其逆矩阵 B1?1 = I 。相应的，检验数 σ j = c j ? C B ? B ?1 ? P j ， ? σ j = c j ? C B ? P j 。在计算检验数时需要用到 C B (基变量在目标函数中的系数向量) ，将 C B 填入表格中。 3 4 0 0 CB 0 0 XB b 40 30 x1 2 1 x2 1 3 x3 1 0 x4 0 1 x3 x4 接下来就是计算非基变量的检验数(基变量的检验数均等于 0，为什么?) 3 4 0 0 CB 0 0 XB b 40 30 x1 2 1 x2 1 3 x3 1 0 0 x4 0 1 0 x3 x4 σ j (1) = c j ? C B ? Pj 这时，非基变量的检验数 σ 1 = 3, σ 2 = 4 均>0，所以该基可行解不是最优解。接下来，我们的任务就是找另一个基可行解。当然，我们希望接下来的这第二个基可行解 X 2 对应的目标函数值比第一个基可行解 X 1 。 (5)找另一个基可行解。由非基变量 ? 基变量的决策变量，我们称之为进基变量，挑选原则: max σ j σ j > 0 = σ k ，那么 x k 进基(即由非基变量变为基变量) 。由基变量 ? 非基变量的决策变量，我们称之为出基变量，挑选原则: { } ?b ? b 。 min ? i a ik > 0? = l ，那么原来的第 l 个基变量出基(即由基变量变为非基变量) ? aik ? a lk 我们称 a lk 为主元。题中，进基变量: max{σ 1 = 3, σ 2 = 4} = σ k = σ 2 ， x 2 进基成为基变量。即第 2 页共 9 页 ?b ? ?b b ? 30 ? 40 ? b 出基变量: min ? i aik > 0? = min ? 1 , 2 ? = min ? = 40, = 10? = 2 ，即第 2 个 3 ?1 ? a 22 ? a12 a 22 ? ? a ik ? 基变量出基，第 2 个基变量是 x 4 ，所以是 x 4 出基成为非基变量。主元为 a 22 。总结 : x 2 进基成为基变量， x 4 出基成为非基变量。也就是说 x 2 代替 x 4 成为基变量，即: 3 4 0 0 CB XB b x1 x2 x3 x4 bi aik 40 = 40 1 0 x3 x4 40 2 1 1 0 0 30 1 3 [3] 4 0 0 1 0 30 = 10 3 σ j (1) = c j ? C B ? Pj 0 4 x3 x2 这时的基变矢 X B 2 = [ x3 , x 2 ]T 。这两个基变量对应的系数列向量组成的矩阵即为 B2 。因为在计算非基变量的检验数的计算过程中会玫?B2 ?1 ,计算逆矩阵是一件麻烦事，我们当然不想干，怎么办呢,为了计算简便，我们期待 B2 = [ P3 , P 2 ] = I ，目前我们只是期待而已。 3 4 0 0 CB XB b x1 x2 x3 x4 bi aik 40 = 40 1 0 x3 x4 40 2 1 1 0 0 30 1 3 [3] 4 0 1 0 0 1 0 1 0 30 = 10 3 σ j (1) = c j ? C B ? Pj 0 4 x3 x2 第 3 页共 9 页 σ j ( 2) = c j ? C B ? Pj 先来看主元 a 22 所在的行。行的系数表示的是约束条件: 30 = x1 + 3x 2 + x 4 ?。我们期待的是:在这个约束条件中， x 2 的系数,1， x3 的系数,0。要做到这一点，只需在等式左右同除以 3(主元 a 22 本身) ，得 10 = 1 1 x1 + x 2 + x 4 ?’，式?’与式?等价。 3 3 接着看另一行。即第一行，该行的系数表示的是约束条件: 40 = 2 x1 + x 2 + x3 ?。我们期待的是:在这个约束条件中， x 2 的系数,0， x3 的系数,1。要做到这一点，需要将 ?, 1 × ?’ ? 30 = 5 1 x1 + x3 ? x 4 ?’，式?’与式?等价。 3 3 5 1 ? ?30 = 3 x1 + x3 ? 3 x 4 ?40 = 2 x1 + x 2 + x3 为实现我们的期待，将约束条件 ? 就等价的代换成 ? 1 1 ?30 = x1 + 3 x 2 + x 4 ?10 = x1 + x 2 + x 4 3 3 ? 将这些系数填入表格中。 3 4 0 0 CB XB b x1 x2 x3

                    本文档为【（最新）运筹学单纯形法例题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

（最新）运筹学单纯形法例题

你可能还喜欢