运筹学单纯形法例题.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)找到了第一个基可行解,接下来的任务就是判断该基可行解是否为最优解,检
显示全部