第4章目标2单纯型应用

第四章目标规划GoalProgramming4.1目标规划问题及其建模4.2目标规划的图解法4.3

目标规划的单纯形法4.4

目标规划应用第4章目标规划第2章单纯形法2求解下列目标规划问题第4章目标规划3求解线性规划的单纯形法的过程基本一致，只是在检验数处理时，需要考虑优先次序的影响。而且，目标规划的目标函数是求最小化，所以当检验数均为大于等于零时为满意解。例4-3用单纯形法求解例4-24.3目标规划的单纯形法第4章目标规划4Step(0):初始单纯形表Step(1):x2入基，d4-出基第4章目标规划5Step(2):d4+

入基，d1-出基Step(3):x1入基，d4+出基第4章目标规划6Step(4):d4-

入基，d3-出基Step(5):d1+

入基，d2-出基第第4章目标规划7这时，所有非基变量的检验数都大于零，所以有唯一最优解。X*=（13/2，5/4）Z*=9/4P3+3P4例：用单纯形法求解下列目标规划问题Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000

P3

5681000001－100

x3

11210000001σkjP1

0000100000P2

-10－1－20002000P3

-56－8－100000010Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

053/201－11/2-1/20000x251/21001/2-1/2000

P3

63000-551－100

x3

63/2000-1/21/2001σkjP1

0000100000P2

0000011000P3

-6－30005-5010θ=min｛10/3,10,6/3,12/3｝=2,故为换出变量。Cj

000P1

P2

P2P3

00CBXBbx1x2x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300

x3

300002-2-1/21/21σkjP1

0000100000P2

0000011000P3

0000000100最优解为x1＝2，x2＝4。但非基变量的检验数为零，故此题有无穷多最优解。θ=min｛4,24,－,6｝=4,故为换出变量。Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

04002-26-6-1100x210/301-1/31/31/3-1/30000x110/3102/3-2/31/3-1/30000

x3

100-1－1-11001σkjP1

0000100000P2

0000011000P3

000000100最优解为x1＝10/3,，x2=10/3。则这两个解得凸组合都是本例的满意解。目标规划的应用目标规划在人事管理中的应用

[例4]某研究所现有科研人员38名，定编人数42名，人员的工资级别与各级人员定编数如下表所示。级别年工资额(万元/人)现有人数定编人数Ⅳ.实习研究员Ⅲ.助理研究员Ⅱ.副研究员Ⅰ.研究员1.01.21.52.018107315158413.3

目标规划的应用现拟进行工资与人员调整,调整的原则与目标如下：（1）工资总额不超过50万元/年；（2）各级人员数不超过定编人数；（3）升入Ⅰ、Ⅱ、Ⅲ级的人数分别不低于各定编人数的20%,25%，40%；并且规定Ⅳ级人员的缺额由外调或招聘增补,其余各级人员应从原有次低级别的人员中晋升。已知Ⅰ、Ⅱ级人员即将离休各一人。应如何确定各级人员调整人数？

一、决策变量

设xj(j=1,2,3,4)为第j级人员增补数。

二、目标约束

(1)工资总额的目标约束

10(18-x3+x4)+12(10-x2+x3)+15(7-1-x1+x2)+20(3-1+x1)≤500化简得

5x1+3x2+2x3+10x4≤70故有

5x1+3x2+2x3+10x4+d1--

d1+=70

13.3

目标规划的应用z1

=d1+级别年工资额(万元/人)现有人数定编人数Ⅳ.实习研究员Ⅲ.助理研究员Ⅱ.副研究员Ⅰ.研究员1.01.21.52.0181073151584目标规划的应用(2)

各级定编人数的目标约束

Ⅳ级:18-x3+x4≤15

即x3-x4

≥3Ⅲ级:10-x2+x3≤15

即-x2+x3

≤5Ⅱ级:6-x1+x2≤8

即-x1+x2

≤2Ⅰ级:2+x1≤4

即x1≤2故有

x3

-x4

+d2--

d2+=3-x2

+x3

+d3--

d3+=5-x1

+x2

+d4--

d4+=2

x1+d5--

d5+=2z2

=d2-

+d3++

d4++d5+级别年工资额(万元/人)现有人数定编人数Ⅳ.实习研究员Ⅲ.助理研究员Ⅱ.副研究员Ⅰ.研究员1.01.21.52.0181073151584目标规划的应用(3)晋级人数的目标约束

晋入Ⅲ级:x3

≥15×0.40=6

晋入Ⅱ级:x2

≥8×0.25=2

晋入Ⅰ级:x1

≥4×0.20≈

1故有

x3+d6--

d6+=

6

x2+d7--

d7+=

2

x1+d8--

d8+=

1z3

=d6-

+d7-

+d8-级别年工资额(万元/人)现有人数定编人数Ⅳ.实习研究员Ⅲ.助理研究员Ⅱ.副研究员Ⅰ.研究员1.01.21.52.0181073151584目标规划的应用

三.目标函数

P1级：z1=d1+

P2级：z2=

d2-+d3++

d4++d5+

P3级：z3=d6-+d7-+d8-这样，本例的目标规划模型为

minz=P1d1++P2(d2-+d3++d4++d5+)+P3(d6-+d7-+d8-)5x1+3x2+2x3+10x4+d1--d1+=70

x3-x4+d2--d2+=3-x2+x3+

d3--d3+=5

-x1+x2+

d4--d4+=2

x1+

d5--d5+=2

x3+

d6--d6+=6

x2+

d7--d7+=2

x1+

d8--d8+=1

xj≥0整数，j=1,2,3,4

di-,di+

≥0,i=1,2,3,···，8s.t.目标规划在库存管理中的应用

[例5]

某副食品批发商店预测其经营的某种商品今后4个月购进与销出价格（万元/吨）如下表所示。目标规划的应用该店经营此种商品肯定能批发销售出去，但最大销量受到仓库容量的限制，而正常库容量为3吨，必要时还可占用机动库容量2吨。该店每月初批发销货，每月中旬采购进货，进货所需钱款完全依赖销售收入。月1234购价2.62.52.72.8销价2.92.73.13.3假设该店第1个月初库存量为2吨，其成本价格为2.5万元/吨，而且该月初无现金。该店预计今后4个月的经营目标如下：（1）每个月都使用正常库容量,尽量不要超贮;

（2）每月下旬都应储存1万元以备急用；

（3）力求今后4个月总盈利达到最大。应如何拟订购销计划？目标规划的应用目标规划的应用

一、决策变量

设

xj=第j月的采购量(吨)

，j=1,2,3,4yj

=第j月的销售量(吨)

二、约束条件

(1)各月销量的约束

y1≤2y2≤2-y1+x1y3≤2-y1+x1-y2+x2y4≤2-y1+x1-y2+x2-y3+x3

y1

+s1

=2y1+y2-x1

+s2

=2y1+y2+y3-x1-x2

+s3=2y1+y2+y3+y4

–x1

–x2–x3

+s4

=2(2)各月采购量的约束2.6x1

≤2.9y12.5x2

≤2.9y1-2.6x1+2.7y22.7x3

≤2.9y1-2.6x1+2.7y2-2.5x2+3.1y32.8x4

≤2.9y1-2.6x1+2.7y2-2.5x2+3.1y3-2.7x3+3.3y4目标规划的应用月1234购价2.62.52.72.8销价2.92.73.13.3目标规划的应用-2.9y1+2.6x1+s5=0-2.9y1-2.7y2

+2.6x1+2.5x2+s6=0-2.9y1-2.7y2-3.1y3

+2.6x1+2.5x2+2.7x3

+s7=0-2.9y1-2.7y2-3.1y3-3.3y4+2.6x1+2.5x2+2.7x3+2.8x4+s8=0(3)正常库容量的目标约束2-y1+x1≤3-y1

+x1+d1--d1+=1-y1-y2+x1+x2

+d2--d2+=1

-y1-y2-y3

+x1+x2+x3+d3--d3+

=1-y1-y2-y3-y4+x1+x2+x3+x4+d4--d4+=1-y1+x1≤1(2-y1+x1)-y2+x2≤3-y1+x1-y2+x2≤1目标规划的应用

(4)各月储备金的目标约束

2.9y1

-2.6x1

+d5--d5+

=1

2.9y1+2.7y2

-2.6x1-2.5x2

+d6--d6+

=1

2.9y1+2.7y2+3.1y3

-2.6x1-2.5x2-2.7x3

+d7--d7+

=1

2.9y1+2.7y2+3.1y3+3.3y4-2.6x1-2.5x2-2.7x3-2.8x4+d8--d8+

=1

(5)总盈利的目标约束

估计利润上界：(3.3-2.5)(3+2)×4

=16

第一月销售成本：2.5×2

=5

2.9y1

+2.7y2

+3.1y3

+3.3y4

-5

-2.6x1-2.5x2-2.7x3≥162.9y1+2.7y2+3.1y3+3.3y4-2.6x1-2.5x2-2.7x3+d9--d9+

=

21目标规划的应用

三、目标函数

P1级目标为不超过正常库容，故有

z1=d1++d2++d3++d4+

P2级目标为每月下旬至少储备1万元，故有

z2=d5-+d6-+d7-+d8-

P3级目标为4个月积累利润不低于16万元，故有

z3=d9-因此可得目标函数

minz=P1z1+P2z2+P3z3目标规划的应用目标规划在目标管理中的应用

[例]

一个生产能力为每天140工时的工厂生产甲、乙两种产品，每吨甲、乙产品分别消耗20工时，10工时，利润分别为5百元，2百元。由于产品需求量的限制，甲、乙产品每天最多只能生产6吨，10吨。

一、为获得最大利润，每天应生产甲、乙产品各多少吨？

设每天分别生产甲、乙产品

x1，x2

吨，总利润为z百元,则LP模型如下：

maxz=5x1+2x220x1+10x2≤140

x1≤6

x2≤10

x1，

x2≥0

目标规划的应用s.t.x1*

=6吨，x2*

=2吨，z*

=34百元若该厂提出以下经营目标：

P1:总利润不低于40百元；

P2

:充分利用生产能力,尽量不超过140工时.minz=P1d1-+P2(d2-+

d2+)

x1≤6

x2

≤10

5x1+

2x2+d1--

d1+=

40

20x1+

10x2+d2--

d2+=

140

x1,

x2

,

di-,

di+≥0目标规划的应用s.t.29目标规划的应用04422866810x1x2①②d1-d1+③d2-d2+④B(6,5)A(6,2)C(6,10)D(4,10)Eminz=P1d1-+P2(d2-+d2+)

x1≤6

x2≤105x1+2x2+d1--d1+=4020x1+10x2+d2--d2+=140

x1,x2,di-,di+≥0目标规划的应用

B点为次优解:x1=6

吨x2=5

吨由于该方案需要的生产能力为

20

×6+10

×5=170

工时而实际生产能力只有140

工时≈0.82

20

×0.82=16.4（工时/吨）

10

×0.82=8.2

（工时/吨）

16.4x1+8.2

x2+d2--d2+=14016.4

×6+8.2×5=139.4(工时)140170

LP解:

x1=6吨，x2

=2吨，设单位利润增加

△c1,△c2,成为c1´=5+△c1,c2´=2+△c2,则6c1´+2c2´=406(5+△c1)+2(2+△c2)=40即3△c1+△c2

=3

若保持c1´,

c2´仍为原比例,则△c1:△c2=5:2联立求解，得目标规划的应用

c1´=5.88,c2´=2.36,还可取线段AB上的任一点:(6,

x2),2

≤

x2≤

5类似可得:

13.3

目标规划的应用25-5x215+x2c1´=5+c2´

=2+25-5x215+x2单位利润单位消耗

28012+x2a1´=

14012+x2a2´=13.3

目标规划的应用生产管理部门会计部门生产部门厂长主管者2+5+2≤x2≤56403.综合方案10202.365.8826402.线性规划8.216.42556401.目标规划乙甲乙甲乙甲单耗(工时/吨)单位利润(百元/吨)日产量(吨)每天利润(百元)

目标方案25-5x215+x210-2x215+x228012+

x214012+

x2目标规划的应用厂长每天总利润4000元甲：500元/吨乙：200元/吨生产部门日产量产品甲：6吨

产品乙：5吨

生产管理部门应用工业工程提高生产效率降低消耗(工时/吨)：

产品甲由20降为16.4

产品乙由10降为8.2

每月核计成本核算利润：

产品甲：500元/吨

产品乙：200元/吨

会计部门例英特集团在大连和上海各设一个分公司，本年度拟在全国招聘170名优秀大学毕业生分别到生产、营销和财务部门工作。两家分公司各部门的人才需求如表1所示。目前集团经过前几轮面试，已选出180名候选人，根据每个人适合从事的部门以及希望工作的部门和城市，可以将这些候选人分为6个类别，如表2所示。集团确定人才录用与分配的原则及优先序如下：部门分公司生产营销财务大连203040上海252035表1各分公司的人才需求表

类别人数适合的部门希望工作部门希望工作城市130生产、营销生产大连230营销、财务营销大连330生产、财务生产上海430生产、财务财务上海530营销、财务财务大连630财务财务上海表2候选人类别与意愿

P1：集团恰好录用到需要并且适合从事各个部门工作的人才；P2：80%以上的录用员工分配到本人希望工作的部门；P3：80%以上的录用员工分配到本人希望工作的城市；请你帮助建立该问题的数学规划模型，并请回答：（1）你所建立的模型中有多少个决策变量？（2）你所建立的模型中有多少条约束条件（除变量取值约束之外）？企业计划生产甲、乙两种产品，这些产品需要使用两种原材料，要在两种不同的设备上加工，工艺资料如下表所示。企业应该如何安排生产计划，并尽可能的满足下列目标：例产品资源甲乙丙可用量（单位）材料I材料II设备A设备B

365435122355