用单纯形法求解目标规划.ppt

由目标规划数学模型的标准型可看出， 它实质上是最小化的线性规划，所以可用单纯形法求解． 这时，我们应该把目标优先等级系数Pi（i = 1, 2, …, k）理解为一种特殊的正常数，且注意到各等级系数之间的关系：P1?P2 ?…?Pk． 而检验数就是各优先因子P1, P2 ,…, Pk的线性组合。 解：引入松驰变量 x3 , 将它们化为标准型： 4．从表中找到基本可行解和相应于各优先级的目标函数每个单纯形表中常数列b，即为各基变量的相应取值． 本题最后一个单纯形表已为最优，它对应的基本可行解：x1=24/5, x2=12/5, x3=12, d2-=36/5，即为最优解． 这与图解法得到结果一致． 结果分析：计算结果表明，工厂应生产A产品60件， B产品175/3件，2500元的利润目标刚好达到。 d4- ＝125/3，表明产品B比最高限额少125/3件，满足要求。 d2+＝115/3 表明甲资源超过库存115/3公斤，该目标没有达到。 从表中还可以看到，P3 的检验数还有负数， 但其高等级的检验数却是正数， 要保证 P1目标实现，P3等级目标则无法实现。 所以，按现有消耗水平和资源库存量，无法实现2500元的利润目标。 可考虑如下措施： 降低A、B产品对甲资源的消耗量， 以满足现有甲资源库存量的目标； 或改变P3等级目标的指标值，增加甲资源115/3公斤。 若很难实现上述措施，则需改变现有目标的优先等级， 以取得可行的满意结果。 满意解 x1 ＝60， x2 ＝175/3， d2+＝115/3， d4- ＝125/3。 1、要求总利润必须超过 2500 元； 2、考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3、由于甲资源供应比较紧张，不要超过现有量140。 简述 * * 目标规划求解问题过程 明确问题，列出(或修改) 目标的优先级和权系数 构造目标 规划的模型 求出 满意解 满意否？ 分析各项目 表完成情况 据此制定出 决策方案 是 否 当所有检验数都满足最优性条件（ ）时，从最终表上即可得出目标规划的解． ci - zj = ∑αkj Pk ,j=1,2,…,n ; k=1,2,…,K Pk是指不同数量的很大的数 d-是松弛变量 d+是剩余变量 PkMPk+1 (M是任意大的正数） 例: 用单纯形法求解下面目标规划问题: 1 0 0 0 -6 6 0 -20 0 P3 0 0 1 0 0 0 0 0 0 P2 0 0 0 0 0 1 0 0 0 P1 -1 1 0 0 6 -6 0 [20] 0 48 P3 0 0 -1 1 4 -4 0 12 0 36 0 0 0 0 0 -1 1 0 -2 1 0 x1 0 0 0 0 0 5 -5 1 20 0 60 x3 0 1 0 0 0 0 0 0 -8 -6 P3 0 0 1 0 0 0 0 0 0 P2 0 0 0 0 1 0 0 2 -1 P1 -1 1 0 0 0 0 0 8 6 48 P3 0 0 -1 1 0 0 0 4 4 36 0 0 0 0 0 -1 1 0 -2 [1] 0 P1 0 0 0 0 0 0 1 10 5 60 x3 0 x3 x2 x1 b XB CB 0 P3 P2 0 0 P1 0 0 0 cj 　　单纯形表1 0 1 0 0 0 0 0 0 0 P3 0 0 1 0 0 0 0 0 0 P2 0 0 0 0 0 1 0 0 0 P1 -1/20 1/20 0 0 3/10 -3/10 0 1 0 12/5 x2 0 3/5 -3/5 -1 1 2/5 -2/5