c13解目标规划的单纯形法及习题解答.ppt

1、2020/8/4,第4章 目标规划Goal Programming,李 健 北京化工大学经济管理学院,目标规划的数学模型 解目标规划的图解法 解目标规划的单纯形法,上节内容回顾,目标规划的数学模型 问题的提出 建立模型的有关概念 建模的一般步骤 解目标规划的图解法,重点,难点： 目标函数的确立,复杂的目标规划怎样求解？,本节内容提要,解目标规划的单纯形法 应用举例 小结 习题讲解,重点,解目标规划的单纯形法,GP模型与LP模型没有本质区别，可用单纯形法进行适当改进后求解。在组织、构造算法时，要考虑GP模型一些特点，作以下规定：,（3）,注：当不含绝对约束时，di-（i=1,2, ,K）构成了一

2、组基可行解。,解GP问题的单纯形法的计算步骤,建立初始单纯形表将表中检验数行按优先因子个数分别列成K行，置k=1。检验数计算方法同单纯形法。 检查当前行中是否存在负数，且对应的前k-1行系数为零。若有该类负数取其最小者对应的变量为换入变量，转3。若无，则转5； 按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量，转4； 按单纯形法进行基变换运算，建立新计算表，返回2； 当k K 时，计算结束。表中的解即为满意解。否则置k = k+1，返回2。,例4 试用单纯形法求解例2。,Min Z =P1d1+P2(d2-+d2+)+P3d3-,C,D,结

3、论：有无穷多最优解。C（2，4）D（10/3，10/3）,cj P1 P2 P2 P3 CB XB b X1 X2 X3 d1- d1+ d2- d2+ d3- d3+ 0 X3 11 2 1 1 0 0 0 0 0 0 0 d1- 0 1 -1 0 1 -1 0 0 0 0 P2 d2- 10 1 2 0 0 0 1 -1 0 0 P3 d3- 56 8 10 0 0 0 0 0 1 -1 0 0 0 0 1 0 0 0 0 -1 -2 0 0 0 0 2 0 0 -8 -10 0 0 0 0 0 0 1,P1,P2,P3,Cj-zj,建立初始单纯形表，将表中检验数行按优先因子个数分别列成

4、K 行，置k=1； 检查当前行中是否存在负数，且对应的前k-1行的系数为零。若有负数取其最小者对应的变量为换入变量，转3。若无负数，则转5；,cj P1 P2 P2 P3 CB XB b X1 X2 X3 d1- d1+ d2- d2+ d3- d3+ 0 X3 6 3/2 0 1 0 0 -1/2 1/2 0 0 0 d1- 5 3/2 0 0 1 -1 1/2 -1/2 0 0 0 X2 5 1/2 1 0 0 0 1/2 -1/2 0 0 P3 d3- 6 3 0 0 0 0 -5 5 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 -3 0 0 0 0

5、 5 -5 0 1,P1,P2,P3,Cj-zj,建立初始单纯形表，将表中检验数行按优先因子个数分别列成K行，置k=1。 检查当前行中是否存在负数，且对应的前k-1行的系数为零。若有负数取其最小者对应的变量为换入变量，转3。若无负数，则转5；,cj P1 P2 P2 P3 CB XB b x1 x2 x3 d-1 d+1 d-2 d+2 d-3 d+3 0 X3 3 0 0 1 0 0 2 -2 -1/2 1/2 0 d1- 2 0 0 0 1 -1 3 -3 -1/2 1/2 0 X2 4 0 1 0 0 0 4/3 -4/3 -1/6 1/6 0 X1 2 1 0 0 0 0 -5/3 5

6、/3 1/3 -1/3,表中所得解x*=(2 , 4)T相当 C 点，利润为56 非基变量d3+的检验数为零，还可以再做一步，d3+ d1-,可得 X=(10/3，10/3)T，对应于D点.,Cj-zj,P1,P2,P3,1,1,1,1,检查当前行中是否存在负数，且对应的前k-1行的系数为零。若无负数，则转5；,本节内容提要,解目标规划的单纯形法 应用举例 小结 习题讲解,课堂练习,某公司分厂用一条生产线生产两种产品A和B ，每周生产线运行时间为60小时，生产一台A产品需要4小时，生产一台B产品需要6小时根据市场预测，A、B产品平均销售量分别为每周9、8台，它们销售利润分别为12、18万元。在

7、制定生产计划时，经理考虑下述4项目标： 首先，产量不能超过市场预测的销售量； 其次，工人加班时间最少； 第三，希望总利润最大； 最后，要尽可能满足市场需求, 当不能满足时, 市场认为B产品的重要性是A产品的2倍 试建立这个问题的数学模型,本节内容提要,解目标规划的单纯形法 应用举例 小结 习题讲解,小结,解目标规划的单纯形法 如何确定检验数的正负性 应用举例,重点,作业,作业1：独立完成例6及例7，然后对照例题解答（不要求上交） 作业2：P112 / 4.3 (1)（要求上交）,本节内容提要,解目标规划的单纯形法 应用举例 小结 习题讲解,A,2020/8/4,例： 现要做100套钢架，每套用

8、长为2.9m，2.1m和1.5m各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。,0,1,0.9,0.1,方案,2,0,0.3,2020/8/4,例： 现要做100套钢架，每套用长为2.9m，2.1m和1.5m各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。,0,1,0.9,0.1,方案,2,0,0.3,例： 现要做100套钢架，每套用长为100m钢一根，40m钢二根和20m钢三根。已知原料长100m，问应如何下料，使用的原材料最省。 所有可能的下料方案的余料均为零！,2020/8/4,例： 现要做100套钢架，每套用长为2.9m，2.1m和1.5m各一根。已知原料长7.4m，问应如何下料，