第四章目标规划课件

目标规划(Goalprogramming)目标规划的图解法目标规划的单纯形法目标规划应用举例目标规划问题及其数学模型7/22/20231目标规划的方法是在1961年由查恩斯(A.Charnes)和库伯(W.W.Cooper)提出的它是在线性规划的基础上，适应企业经营管理中多目标决策的需要而逐步发展起来的。目标规划是在企业决策者所规定的若干指标值及要求实现这些指标的先后顺序后，并在给定有限资源条件下，求得总的偏离指标值为最小的方案，称这方案为满意方案。目标规划7/22/20232目标规划与线性规划相比，有以下优点：线性规划只能处理一个目标，而现实问题往往要处理多种目标。目标规划能统筹兼顾地处理多种目标的关系，求得更切合实际要求的解。线性规划立足于满足所有约束条件的可行解，而在实际问题中可能存在相互矛盾的约束条件。目标规划可以在相互矛盾的约束条件下找到满意解，即满意方案。目标规划找到的最优解是指尽可能地达到或接近一个或若干个已给定的指标值。线性规划的约束条件是同等重要的，而目标规划可根据实际需要给予轻重缓急或主次之分的考虑。7/22/20233

可以认为目标规划更能确切地描述和解决经营管理中的许多实际问题一种简单、实用的处理多目标决策问题的方法。在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。7/22/20234一、目标规划问题及其数学模型（一）目标规划问题的提出单一目标问题例1

解：可用线性规划的模型来描述产品ⅠⅡ限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）687/22/20235

目标函数：maxz=6x1+8x2约束条件：5x1+10x2≤604x1+4x2≤40x1，x2≥0

最优解：x1=8件，x2=2件，maxz=64元

7/22/20236

（二）目标规划的数学模型实际上工厂在做决策时，要考虑市场等其他条件：1、根据市场信息，产品Ⅱ的销售量已有下降的趋势，故考虑产品Ⅱ的产量最好不大于产品Ⅰ的一半；2、由于原材料严重短缺，生产中应避免过量消耗；3、最好能节约设备工时（4h）；4、应尽可能达到并超过预计利润指标（48元）。工厂现在的生产、经营问题——多目标决策问题。引入与建立目标规划数学模型有关的概念：7/22/20237

1、引入一种新的变量——正、负偏差变量d+、d-，

d+:可能实现值超过规定目标值的偏差量，d+≥0。

d-:可能实现值未达到规定目标值的偏差量，d-≥0d+•d-=02、约束条件—绝对（硬）约束、目标（软）约束3、优先因子（优先等级）P1，P2，…，规定Pl>>Pl+1，l=1，2，…。表示Pl比Pl+1有更大的优先权。这意味着当目标与目标之间发生冲突时应按其优先等级来实现。具有相同优先因子的目标，其重要程度用不同的权系数表示4、目标规划的目标函数7/22/20238

当完成或超额完成规定的指标则表示：d＋≥0,d－＝0

当未完成规定的指标则表示：d＋＝0,d－≥0

当恰好完成指标时则表示：d＋＝0,d－＝0∴d＋×d－

＝0成立。在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0,d－≥01、引入一种新的变量——正、负偏差变量d+、d-7/22/20239

引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。

目标约束是目标规划中特有的，是软约束。2、约束条件—绝对（硬）约束、目标（软）约束

绝对约束是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。7/22/202310

由各目标约束的正、负偏差变量及相应的优先因子和权系数构成。从决策者的要求来分析，总希望得到的结果与规定的指标值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小化的目标函数，minZ=f（d+，d-）

其基本形式有三种：4、目标规划的目标函数7/22/202311

（1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小。构造的目标函数是

minZ=f（d++d-

）

（2）要求不超过目标值，但允许达不到目标值，即只有使正偏差量要尽可能地小（实现最少或为零）

minZ=f（d+）（3）要求超过目标值，即超过量不限。要求超额完成规定目标，要实现负偏差量为零或为最小

minZ=f（d-）7/22/202312

对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。

5、满意解

7/22/202313

归纳上面的分析：由于原材料严重短缺，生产中应避免过量消耗受到严格限制的基础上按顺序考虑其他目标的实现目标优先等级：1、P1—产品Ⅱ的产量最好不大于产品Ⅰ的一半2、P2—最好能节约设备工时4h。3、P3—总利润尽可能达到并超过48元。

由此，可以如下建立该问题的最优化模型

——7/22/202314

决策变量：

x1——产品Ⅰ的产量，x2——产品Ⅱ的产量。偏差变量：

P1等级：正、负偏差变量——d1+、d1-

P2等级：正、负偏差变量——d2+、d2-

P3等级：正、负偏差变量——d3+、d3-

x1

、x2

、d1+、d1-、d2+、d2-、d3+、d3-≥07/22/202315

约束条件：绝对约束：

5x1+10x2≤60

目标约束：

x1-2x2+d1--d1+=0（P1

）

4x1+4x2+d2--d2+=36（P2

）

6x1+8x2+d3--d3+=48（P3

）目标函数：

minZ=P1d1-+P2

d2++P3d3-7/22/202316某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的生产方案？ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810在此基础上考虑：

1、产品Ⅱ的产量不低于产品Ⅰ的产量；

2、充分利用设备有效台时，不加班；

3、利润不小于56元。解:分析第一目标：即产品Ⅰ的产量不大于Ⅱ的产量。第二目标：例2：7/22/202317第三目标：规划模型：7/22/202318目标规划数学模型的一般形式

7/22/202319

建模的步骤

1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；

4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。

3、给各目标赋予相应的优先因子Pl（l=1.2…L）。

2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。7/22/202320

5、根据决策者的要求，按下列情况之一：

⑴恰好达到目标值，取。⑵允许超过目标值，取。⑶不允许超过目标值，取。构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数。7/22/202321

小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,

xs

xa

xi

xs

xa

d约束条件绝对约束目标约束、绝对约束解最优最满意7/22/202322

图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。

图解法解题步骤如下：

1、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来；

2、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；二、目标规划的图解法7/22/202323

3、求满足最高优先等级目标的解；

4、转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；

5、重复4，直到所有优先等级的目标都已审查完毕为止；

6、确定最优解和满意解。例3：用图解法解例1的目标规划模型7/22/202324

minZ=P1d1-+P2d2++P3d3-s.t.5x1+10x2≤60x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48x1

、x2

、di-、di+、≥0i=1,2,34x1+4x2=36

x1-2x2=0

5x1+10x2=606x1+8x2=48

d3-d2+d1-AFCDE

Bo7/22/202325

例4电视机厂装配彩色和黑白两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；每周黑白电视机的销量是30台，每台可获利40元。决策者的目标为：第一优先级目标：充分利用装配线每周计划开动的40小时；第二优先级目标：允许装配线加班；但加班时间每周尽量不超过10小时；第三优先级目标：装配电视机的数量尽量满足市场需求。因为彩色电视机的利润更高（是黑白电视机利润的2倍），取其市场需求满足权系数为2。7/22/202326

模型：x1、x2——彩色、黑白电视机的生产量

minZ=P1d1-+P2

d2++P3（2d3-+1d4-）

x1+x2+d1--d1+=40x1+x2+d2--d2+=40+10=50x1+d3--d3+=24x2+d4--d4+=30x1

、x2

、di-

、di+-≥0

i=1,2,3,47/22/202327

d3-

d1-

d3+

d4+

d2+

d1+

d4-

d2-

x2x1x1+x2=40x1+x2=50

x1=24x2=30

满意解（24，26）minZ=P1d1-+P2

d2++P3（2d3-+1d4-）s.t.x1+x2+d1--d1+=40x1+x2+d2--d2+=40+10=50x1+d3--d3+=24x2+d4--d4+=30

x1

、x2

、di-、di+-≥0

i=1,2,3,47/22/202328例5、用图解法求解目标规划问题7/22/202329012345678123456⑴⑵⑶Ax2

x1BC

B(0.6250,4.6875)C(0,5.2083)，B、C

线段上的所有点均是该问题的解（无穷多最优解）。7/22/202330例6、已知一个生产计划的线性规划模型为其中目标函数为总利润，x1,x2

为产品A、B产量。现有下列目标：

1、要求总利润必须超过2500元；

2、考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件；

3、由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。7/22/202331解：以产品A、B的单件利润比2.5：1为权系数，模型如下：7/22/2023320x2

0⑴x11401201008060402020406080100⑵⑶⑷ABCD结论：C(60,58.3)为所求的满意解。作图：7/22/202333检验：将上述结果带入模型，因＝＝0；

＝＝0；

＝0，存在；＝0，存在。所以，有下式：minZ=P3

将x1＝60，x2

＝58.3带入约束条件，得30×60＋12×58.3＝2499.6≈2500；2×60+58.3=178.3>140；1×60＝601×58.3＝58.3<100由上可知：若A、B的计划产量为60件和58.3件时，所需甲资源数量将超过现有库存。在现有条件下，此解为非可行解。为此，企业必须采取措施降低A、B产品对甲资源的消耗量，由原来的100％降至78.5％（140÷178.3＝0.785），才能使生产方案（60，58.3）成为可行方案。7/22/202334用图解法求解下列目标规划问题7/22/202335⑴⑵⑶⑷CD结论：有无穷多最优解

C（2，4）D（10/3，10/3）7/22/202336例：用单纯形法求解下列目标规划问题三、目标规划的单纯形法7/22/202337Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000

P3

5681000001－100

x3

11210000001σjP1

000100000P2

－1－20002000P3

－8－100000010θ=min｛－，10/2，56/10，11/1｝=5换出变量进基变量7/22/202338Cj

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σjP1

000100000P2

000011000P3

－30005-5010θ=min｛10/3,10,6/3,12/3｝=2,进基变量换出变量7/22/202339Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

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

x3

300002-2-1/21/21σjP1

000100000P2

000011000P3

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

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σjP1

000100000P2

000011000P3

000000100最优解为x1＝10/3,，x2=10/3。7/22/202341例：某车间计划生产A、B两种产品。决策者首先考虑要充分利用供电部门分配的电量限额指标62.5kw/日，然后考虑完成与超额完成利润指标10元/日。每日可给车间供应所需原料8t。其他有关数据汇总于下表。应当如何确定产品A、B的产量。产品耗电量（kw/单位产品）材料消耗（t/单位产品）利润（元/单位产品）AB10122112试用单纯形法求解。

7/22/202342

解：目标规划问题的数学模型

minZ=P1(d1-+d1+)+P2

d2-

10x1+12x2+d1--d1+=62.5x1+2x2+d2--d2+=102x1+

x2≤8x1

,x2

,≥0,d1-,d1+,

d2-,d2+≥07/22/202343(1)确定初始解，建立初始计算表初始基变量：d1-,

d2-,x3minZ=P1(d1-+d1+)+P2

d2-

10x1+12x2+d1--d1+=62.5x1+2x2+d2--d2+=102x1+

x2+x3=8x1

,x2

,x3≥0,d1-,d1+,

d2-,d2+≥07/22/202344

cj000P1P1P20θCBxBbx1x2x3d1-d1+d2-d2+P1P20d1-d2-x362.510810121221001100-1000100-10cj-zjP1P2检验数σj=cj–zj

σ1=0

–10×P1–1×P2–0×2=–10P1–P2-10-1-12-221……

7/22/202345

cj000P1P1P20θCBxBbx1x2x3d1-d1+d2-d2+P1P20d1-d2-x362.510810121221001100-1000100-10cj-zjP1P2-10-1-12-221(2)先从检验数P1行中，选择

min(σj＜0）=min(-10,-12)=-12

进基变量：x262.5/1210/28/1出基变量：d2-再按θ=min(8/1,10/2,62.5/12)=57/22/202346

cj000P1P1P20θCBxBbx1x2x3d1-d1+d2-d2+P100d1-x2x32.55341/2-3/2010001100100-61/2-1/26-1/21/2cj-zjP1P2

-4261-6(3)用x2替换基变量d2-，进行迭代运算，得到下表：(4)重复(1)的工作7/22/202347

cj000P1P1P20θCBxBbx1x2x3d1-d1+d2-d2+P100d1-x2x32.55341/2-3/2010001100100-61/2-1/26-1/21/2cj-zjP1P2-4

261-62.5/63/0.5(5)重复(2)的工作

检查P1行所有系数，P1行还有负数，选d2+—进基变量，计算θ得d1-—出基变量7/22/202348用d2+替换基变量d1-，进行迭代运算，得到下表cj000P1P1P20θCBxBbx1x2x3d1-d1+d2-d2+000d2+x2x35/12125/2467/242/35/67/60100011/61/12-1/12-1/6-1/121/12-100100cj-zjP1P2

111检验数都为正，得满意解：

x1=0，x2=5.208，x3=2.79，d2+=0.4177/22/202349

cj000P1P1P20θCBxBbx1x2x3d1-d1+d2-d2+000d2+x2x35/12125/2467/242/35/67/60100011/61/12-1/12-1/6-1/121/12-100100cj-zjP1P2

1115/8125/2067/28

非基变量x1

的检验数是零,用x1替换基变量d2+，进行迭代运算，得下表表示有多重解。7/22/202350

cj000P1P1P20θCBxBbx1x2x3d1-d1+d2-d2+000x1x2x35/8225/4833/161000100011/4-1/8-3/8-1/41/83/8-3/25/47/43/2-5/4-7/4cj-zjP1P2

111另一个满意解：x1=0.625，x2=4.6375，x3=2.06257/22/202351例、用单纯形法求解下列目标规划问题

7/22/202352Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σjP1

－30－1201000000P2

00000002.501P3

0000010000θ=min｛2500/30,140/2,60/1｝=60,故为换出变量。7/22/202353Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σjP1

0－12010030－3000P2

00000002.501P3

0000010000θ=min｛700/30,20/2,－,－｝=10,故为换出变量。7/22/202354Cj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σjP1

030115-150000P2

0-5/400-5/45/45/2001P3

0000010000θ=min｛400/15,－,－,－｝=10,故为换出变量。7/22/202355Cj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σjP1

0010000000P2

0-1-1/121/12002/5001P3

01/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75,故为换出变量。7/22/202356Cj

00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000125/300-1/121/12005/2-5/21－1σjP1

0010000000P2

00000005/201P3

00-1/121/12101/2-1/200

P3优先等级目标没有实现，但已无法改进，得到满意解

x1

＝60，x2

＝175/3，＝115/3，＝125/37/22/202357

结果分析：计算结果表明，工厂应生产A产品60件，B产品175/3件，2500元的利润目标刚好达到。＝125/3，表明产品比最高限额少125/3件，满足要求。＝115/3表明甲资源超过库存115/3公斤，该目标没有达到。从表中还可以看到，P3的检验数还有负数，但其高等级的检验数却是正数，要保证P1目标实现，P3等级目标则无法实现。所以，按现有消耗水平和资源库存量，无法实现2500元的利润目标。可考虑如下措施：降低A、B产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变P3等级目标的指标值，增加甲资源115/3公斤。若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意解果。7/22/202358目标规划建模

1、某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。该厂经营目标如下：1、利润指标为每月16000元，争取超额完成；2、充分利用现有生产能力；3、可以适当加班，但加班时间不得超过24小时；4、产量以预计销售量为准。试建立目标规划模型。

7/22/2023597/22/2023602.已知条件如表所示工序型号每周最大加工能力ABⅠ（小时/台）Ⅱ（小时/台）436215070利润（元/台）300450如果工厂经营目标的期望值和优先等级如下：p1:每周总利润不得低于10000元；p2:因合同要求，A型机每周至少生产10台，B型机每周至少生产15台；p3:希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。试建立这个问题的目标规划模型。

7/22/2023617/22/202362

3.在上题中，如果工序Ⅱ在加班时间内生产出来的产品，每台A型机减少利润10元，每台B型机减少利润25元，并且工序Ⅱ的加班时间每周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划模型。7/22/202363设x1,x2分别为在正常时间和加班时间生产A型机台数，x3,x4分别为在正常时间和加班时间生产B型机台数，目标规划数学模型为：7/22/202364

4某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：

(1)不超过年工资总额60000元；

(2)每级的人数不超过定编规定的人数；

(3)Ⅱ，Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升；

(4)Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工中有10%要退休。有关资料汇总于下表中，问该领导应如何拟订一个满意的方案。7/22/202365解

设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工人数。对各目标确定的优先因子为：P1——不超过年工资总额60000元；P2——每级的人数不超过定编规定的人数；P3——Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。7/22/202366

先分别建立各目标约束。

年工资总额不超过60000元

2000(10-10×0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1—-d1+

=600007/22/202367每级的人数不超过定编规定的人数：对Ⅰ级有10(1-0.1)+x1+d2-—d2+=12对Ⅱ级有12-x1+x2+d3-—d3+=15对Ⅲ级有15-x2+x3+d4-—d4+=15Ⅱ，Ⅲ级的升级面不大于现有人数的20%，但尽可能多提；对Ⅱ级有x1+d5-—d5+=12×0.2对Ⅲ级有x2+d6-—d6+=15×0.2目标函数：minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)7/22/2023685已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见下表。有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应的优先等级：

P1——B4是重点保证单位，必须全部满足其需要；P2——A3向B1提供的产量不少于100；P3——每个销地的供应量不小于其需要量的80%；P4——所定调运方案的总运费不超过最小运费调运方案的10%；