运筹学单纯形法例题.pdf

单纯形法例题：某工厂生产I、II 两种商品,已知生产单位商品所需的设备台时、A、B两种 原材料的消耗、设备使用台时限额以及原材料的限额如下表所示。该工厂每生产一件商品I 可获利3元，每生产一件商品II 可获利4元。写出使该工厂所获利润最大的线性规划模型, 并用单纯形法求解。 产品I 产品II 限额 设备 2 1 40台时 原材料 1 3 30KG 解：设生产产品I的数量为 ，生产产品II 的数量为 ，所获利润为 ，相应的模型为： x1 x2 z maxz=3x + 4x maxz=3x + 4x 1 2 1 2 ⎧2x + x ≤ 40 ⎧2x + x + x = 40 ⎪ 1 2 标准型 ⎪ 1 2 3 ⎨x +3x ≤30 ⎨x + 3x + x =30 1 2 1 2 4 ⎪ ⎪ x,x ≥ 0 x ,x ,x ,x ≥ 0 ⎩ 1 2 ⎩ 1 2 3 4 用单纯形法求解。 （1）建立初始单纯行表，即将目标函数和约束条件填入表格中。 3 4 0 0 b x1 x2 x3 x4 40 2 1 1 0 30 1 3 0 1 T （2）挑选单位阵为初始基。在本题中初始基B =[P,P ]，相应的，基变矢X =[x ,x ] 。 1 3 4 B1 3 4 （3）将初始基B =[P,P]对应的基变量填入单纯行表中。 1 3 4 3 4 0 0 XB b x1 x2 x3 x4 x3 40 2 1 1 0 x4 30 1 3 0 1 这时，我们可以得到初始基B =[P,P ]对应的基可行解。 1 3 4 即令非基变量x = 0,x = 0，根据表中的约束条件可得x = 40,x =30（这两个值正好是表 1 2 3 4 中基变量对应的资源向量 对应的分量，为什么？） b 第一个基可行解为X =[0,0,40,30]T。 1 （4）找到了第一个基可行解，接下来的任务就是判断该基可行解是否为最优解，检