管理运筹学 第一章线性规划及单纯形法.ppt

-3 0 1 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 0 x4 4 1 1 1 1 0 0 0 -M x6 1 -2 1 -1 0 -1 1 0 -M x7 9 0 3 1 0 0 0 1 ?j 10M -2M-3 4M 1 0 -M 0 0 0 x4 3 3 0 2 1 1 -1 0 0 x2 1 -2 1 -1 0 -1 1 0 -M x7 6 6 0 4 0 3 -3 1 ?j 6M 6M-3 0 4M+1 0 3M -4M 0 0 x4 0 0 0 0 1 -1/2 1/2 -1/2 0 x2 3 0 1 1/3 0 0 0 1/3 -3 x1 1 1 0 2/3 0 1/2 -1/2 1/6 ?j 3 0 0 3 0 3/2 -M-3/2 -M+1/2 1 x3 3/2 3/2 0 1 0 3/4 -3/4 1/4 0 x4 0 0 0 0 1 -1/2 1/2 -1/2 0 x2 5/2 -1/2 1 0 0 -1/4 1/4 1/4 ?j -3/2 -9/2 0 0 0 -3/4 -M+3/4 -M-1/4 ? 4 1 3 1 1 9 3/2 例15：用单纯形法求解线性规划问题 添加人工变量，化成典式 2 3 0 0 -M CB XB b x1 x2 x3 x4 x5 0 x3 12 2 2 1 0 0 -M x5 14 1 2 0 -1 1 ?j 14M 2+M 3+2M 0 -M 0 3 x2 6 1 1 0.5 0 0 -M x5 2 -1 0 -1 -1 1 ?j 2M-18 -1-M 0 -1.5-M -M 0 所有的检验数都不大于零，人工变量X5 仍留在基变量中且不为零，故原问题无可行解。 ? 6 7 二. 两阶段法 第一阶段：寻找原问题的一个基可行解 第二阶段：求原问题的最优解 通过求解一个目标函数只含有人工变量的辅助问题实现。 原问题 辅助问题 第一阶段解的情况 1. 第一阶段人工变量取值为0，目标函数值也为0。此时得到原问题的第一个基可行解。结束第一阶段，去掉人工变量，进入第二阶段求原问题的最优解。 2. 第一阶段最优解的基变量中含有人工变量，表明原问题无可行解。 例16：用两阶段法求解下列线性规划问题 化标准型 第一阶段的线性规划问题为 第一阶段：用单纯形法求解辅助问题 0 0 0 0 0 -1 -1 CB XB b x1 x2 x3 x4 x5 x6 x7 0 x4 4 1 1 1 1 0 0 0 -1 x6 1 -2 1 -1 0 -1 1 0 -1 x7 9 0 3 1 0 0 0 1 ?j 10 -2 4 0 0 -1 0 0 0 x4 3 3 0 2 1 1 -1 0 0 x2 1 -2 1 -1 0 -1 1 0 -1 x7 6 6 0 4 0 3 -3 1 ?j 6 6 0 4 0 3 -4 0 0 x4 0 0 0 0 1 -1/2 1/2 -1/2 0 x2 3 0 1 1/3 0 0 0 1/3 0 x1 1 1 0 2/3 0 1/2 -1/2 1/6 ?j 0 0 0 0 0 0 -1 -1 得原问题的基可行解X=(1,3,0,0,0)T。 ? 4 1 3 1 1 第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数，从上表的最后一个单纯形表出发，继续计算。 -3 0 1 0 0 CB XB b x1 x2 x3 x4 x5 0 x4 0 0 0 0 1 -1/2 0 x2 3 0 1 1/3 0 0 -3 x1 1 1 0 2/3 0 1/2 ?j 3 0 0 3 0 3/2 0 x2 5/2 -1/2 1 0 0 -1/4 1 x3 3/2 3/2 0 1 0 3/4 0 x4 0 0 0 0 1 -1/2 ?j -3/2 -9/2 0 0 0 -3/4 得原问题的最优解X=（0，5/2，3/2，0，0）T，最优值是3/2。 ? 9 3/2 单纯形法计算小结 作业: P48 9（2） 10 第六节 线性规划应用案例分析 例17 [混合配料问题]　　某糖果厂用原料A,B,C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A,B,C的含量，原料成本，各种原料的每月限制用量，三种糖果的单位加工费如下表所示．问该厂每月生产这三种牌号的糖果各多少千克，才能获利最大？ 甲 乙 丙 原料成本 （元/kg） 每月限制用量（kg) A ? 60% ?30% 2.00 2000 B 1.50 2500 C ≤20% ≤50% ≤60% 1.00 1200 加工费(元/kg) 0.50 0.40 0.30 售价(元/kg) 3.40 2.85 2.25 解:　用i=1，2，3代