目标规划02-图解法、单纯形法

1、1目标规划目标规划 Goal Programming（GP）第2节 目标规划的图解法 如何求解多目标线性规划问题，其方法与求解线性规划问如何求解多目标线性规划问题，其方法与求解线性规划问题的方法相似题的方法相似目标线性规划目标线性规划单纯形法单纯形法。但是，对于只有。但是，对于只有两两个决策变量个决策变量的的目标线性规划问题同样可以采用目标线性规划问题同样可以采用图解的方法图解的方法来揭来揭示问题的解的某种特征。示问题的解的某种特征。 在用图解法解目标规划时，首先必须满足所有绝对约束条在用图解法解目标规划时，首先必须满足所有绝对约束条件。在此基础上，再按照目标优先级别从高到低的顺序，逐个件。在

2、此基础上，再按照目标优先级别从高到低的顺序，逐个地考虑各个目标约束条件。地考虑各个目标约束条件。2目标规划目标规划 Goal Programming（GP）王老板的目标规划问题图解：王老板的目标规划问题图解：min Z = P1 d1+ P2（ d2-+ d2+）+ P3 d3- s.t. 2x1+ x2 11 x1 - x2 + d1- - d1+= 0 x1 + 2x2 + d2- - d2+= 10 8x1 +10 x2 + d3- - d3+= 56 x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 08x1 +10 x2 = 56 x1 - x2 = 0 x1 + 2

3、x2 = 102x1+ x2 =11 绝对约束域绝对约束域d2+ d3+ d3- d2- d1- d1+ （10/3，10/3）（2，4）3目标规划目标规划 Goal Programming（GP）案例案例 电视机厂装配彩色和黑白两种电视机，每装配一台电视机需占电视机厂装配彩色和黑白两种电视机，每装配一台电视机需占用装配线用装配线1 1小时，装配线每周计划开动小时，装配线每周计划开动40小时。预计市场每周彩色小时。预计市场每周彩色电视机的销量是电视机的销量是24台，每台可获利台，每台可获利80元；元；每周黑白电视机的销量是每周黑白电视机的销量是30台，每台可获利台，每台可获利40元。决策者的目

4、标为：元。决策者的目标为： 第一优先级目标：第一优先级目标：充分利用充分利用装配线每周计划开动的装配线每周计划开动的40小时；小时； 第二优先级目标：第二优先级目标：允许允许装配线装配线加班；但加班时间加班；但加班时间每周尽量不超过每周尽量不超过10小时；小时； 第三优先级目标：第三优先级目标：装配电视机的数量尽量满足市场需求。因为彩装配电视机的数量尽量满足市场需求。因为彩色电视机的利润更高（是黑白电视机利润的色电视机的利润更高（是黑白电视机利润的2倍），取其市场需求倍），取其市场需求满足权系数为满足权系数为2。4目标规划目标规划 Goal Programming（GP）解：解：建立目标规划模

5、型：建立目标规划模型： x1 彩色彩色电视机的生产量电视机的生产量 x2 黑白黑白电视机的生产量电视机的生产量x1 + x2 + d1- - d1+= 40 x1 + x2 + d2- - d2+= 40+10=50 x1 + d3- - d3+= 24 x2 + d4- - d4+= 30 x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- 0 min Z = P1 d1-+ P2 d2+ P3（2d3- +d4-）s.t.5目标规划目标规划 Goal Programming（GP）利用利用图解图解法求解法求解：d3- d1- d3+ d4+ d2+ d1+

6、d4- d2- x2x1x1 + x2 = 40 x1 + x2 = 50 x1 = 24x2 = 30 满意解（满意解（24，26）6目标规划目标规划 Goal Programming（GP）第3节 目标规划的单纯形法 目标规划的模型实际上是求目标规划的模型实际上是求 min 型的线性规划，因此，也型的线性规划，因此，也可以采用可以采用单纯形法单纯形法求解。求解。 在采用单纯形法求解目标规划时，检验数是各优先因子的在采用单纯形法求解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，关键是要线性组合。因此，在判别各检验数的正负及大小时，关键是要注意到优先因子的级别。

7、当检验数按优先级别从高到低已满足注意到优先因子的级别。当检验数按优先级别从高到低已满足最优性条件时，且无法进一步优化时，从单纯形表上就可以得最优性条件时，且无法进一步优化时，从单纯形表上就可以得到目标规划的最优解或满意解。到目标规划的最优解或满意解。7目标规划目标规划 Goal Programming（GP）例：例：现有如下目标规划问题现有如下目标规划问题Min Z = P1d1- +P2d2+ +P3d3- 5x1 + 10 x2 + x3 = 60 x1 2x2 + d1- d1+ = 0 4x1 + 4x2 + d2- d2+ = 36 6x1 + 8x2 + d3- d3+ = 48

8、xj ， di- ，di+ 0当前基变量：当前基变量： x3 ，d1- ， d2- ， d3- 。8目标规划目标规划 Goal Programming（GP）目标规划问题的单纯形表：目标规划问题的单纯形表：cj000P100P2P30CB基基解解x1x2x3d1-d1+d2-d2+d3-d3+0 x3605101000000P1d1-01-201-100000d2-36440001-100P3d3-4868000001-1 j P11P21P31P1-121P3-6-819目标规划目标规划 Goal Programming（GP）cj000P100P2P30CB基基解解x1x2x3d1-d1+

9、d2-d2+d3-d3+0 x3605101000000P1d1-01-201-100000d2-36440001-100P3d3-4868000001-1 j P1-121P21P3-6-81cj000P100P2P30CB基基解解x1x2x3d1-d1+d2-d2+d3-d3+0 x3600201-5500000 x101-201-100000d2-360120-441-100P3d3-480200-66001-1 j P11P21P3-206-6110目标规划目标规划 Goal Programming（GP）cj000P100P2P30CB基基解解x1x2x3d1-d1+d2-d2+d3

10、-d3+0 x3600201-5500000 x101-201-100000d2-360120-441-100P3d3-480200-66001-1 j P11P21P3-206-61cj000P100P2P30CB基基解解x1x2x3d1-d1+d2-d2+d3-d3+0 x3120011-100-110 x124/51002/5-2/5001/10-1/100d2-36/5000-2/52/51-1-3/53/50 x212/5010-3/103/10001/20-1/20 j P11P21P3111目标规划目标规划 Goal Programming（GP）第第5 5节节 目标规划应用问题

11、目标规划应用问题 例6： 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：(1) 不超过年工资总额60000元；(2) 每级的人数不超过定编规定的人数；(3) ，级的升级面尽可能达到现有人数的20%，且无越级 提升；(4) 级不足编制的人数可录用新职工，又级的职工中有 10%要退休。 有关资料汇总于表有关资料汇总于表4-84-8中，问该领导应如何拟订一个满中，问该领导应如何拟订一个满意的方案。意的方案。12表4-8：13解解：设x1、x2、x3分别表示提升到、级和录用到级的新职工人数。对各目标确定的优先因子为：nP1不超过年工资总额60000元；nP2每级的人数不超过定编规定的人

12、数；nP3、级的升级面尽可能达到现有人数的20%。先分别建立各目标约束：（具体如下页所示）（具体如下页所示）14P1：年工资总额不超过年工资总额不超过60000元元 2000(10-100.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1-d1+ =60000P P2 2：每级的人数不超过定编规定的人数每级的人数不超过定编规定的人数 对级有 10(1-0.1)+x1+d2-d2+=12 对级有 12-x1+x2+d3-d3+=15 对级有 15-x2+x3+d4-d4+=15P P3 3：，级的升级面不大于现有人数的级的升级面不大于现有人数的20%20%，但尽可能，但尽可能多提多