运筹学基础-目标规划(2)课件

上节小结：目标规划的基本概念1.目标值和正、负偏差变量

目标值是预先给定的某个目标的一个期望值。实现值是当决策变量x1、x2、…、xn选定以后目标函数的对应值。偏差变量：实现值和目标值之间的差异值，用d＋和d－表示。

d＋——超出目标的差值，称正偏差变量；

d－——未达到目标的差值，称负偏差变量；

2.绝对约束与目标约束

绝对约束又称系统约束，是指必须严格满足的等式和不等式约束。

目标约束：对那些不严格限定的约束，连同原线性规划建模时的目标函数转化为的约束，称为目标约束。

由此决策者可根据自己的要求构造一个使总偏差量为最小的目标函数，称为达成函数，记为

即达成函数是正、负偏变量的函数。有三种形式：

3．目标规划的目标函数－－达成函数实际值恰好等于目标值，即正、负偏变量尽可能地小，这时函数是：实际值大于目标值，即负偏变量尽可能地小，这时函数是：实际值小于目标值，即负偏变量尽可能地小，这时函数是：

在一个目标规划的模型中，如果两个不同目标重要程度相差悬殊，为达到某一目标可牺牲其它一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1，P2，…表示，并规定Pk＞＞Pk＋1，符号“＞＞”表示“远大于”，表示Pk与Pk＋1，不是同一各级别的量，即Pk比Pk＋1有更大的优先权。

对属于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。4.目标的优先级与权系数5.满意解

目标规划问题的求解是在不破坏上一级目标的前提下，实现下一级目标的最优。因此，这样最后求出的解就不是通常意义下的最优解，我们称它为满意解。§5.2应用举例[例1]某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间生产。已知除外购件外，生产一台录音机需甲车间加工2h，乙车间装配1h；生产一台电视机需甲车间加工1h，乙车间装配3h；两种产品需检验、销售环节，每台录音机检验销售费用需50元，每台电视机检验销售费用需30元。又甲车间每月可用工时为120h，车间管理为80元/h，乙车间每月可用工时为150h，车间管理为20元/h。估计每台录音机利润100元，每台电视机利润75元，又估计下一年度内平均每月可销售录音机50台，电视机80台。该厂的月度目标为

P1：检验销售费用每月不超过4600元；

P2：每月销售录音机不少于50台；

P3：甲、乙车间每月工时要充分利用（权数按每小时费用比例确定）；P4：甲车间加班不超过20h。P5：每月销售电视机不少于80台P6：两车间加班总时间要控制（权数按每小时管理费用比例确定）

解设录音机、电视机的产量分别为x1,x2；甲、乙工时比例为4：1，于是得到目标规划模型为检验销售费用每月不超过4600元，P1minZ=P1d1+x1+d2-

–d2+＝50x2+d3-

–d3+＝8050x1+30x2+d1-

–d1+＝

4600+P2d2-

+P5d3-d4++d6-

–d6+＝20每月销售录音机不少于50台，P2；每月销售电视机不少于80台，P52x1+x2+d4-

–d4+＝120

x1+3x2+d5-

–d5+＝150x1,x2，di-,di+

≥0

+P3(

4d4-+d5-)甲、乙车间每月工时要充分利用，P3甲车间加班不超过20h，P4

+P4d6+

+P6(4d4+＋d5+)两车间加班总时间要控制，P6最后得x1=50，x2=40，d1-

=900，

d4+=20，d5+=20，即每月生产录音机50台，电视机40台，利润额可达到8000元

[例2]某制药公司有甲、乙两个工厂，现要生产A、B两种药品均需在两个工厂生产．A药品在甲厂加工2h，然后送到乙厂检测包装2.5h才能成品，B药在甲厂加工4h，再到乙厂检测包装1.5h才能成品．A、B药在公司内的每月存贮费分别为8元和15元．甲厂有12台制造机器，每台每天工作8h，每月正常工作25天，乙厂有7台检测包装机，每天每台工作16h，每月正常工作25天，每台机器每小时运行成本：甲厂为18元，乙厂为15元，单位产品A销售利润为20元，B为23元，依市场预测次月A、B销售量估计分别为1500单位和1000单位．该公司依下列次序为目标的优先次序，以实现次月的生产与销售目标．P1：厂内的储存成本不超过23000元．P2：A销售量必须完成1500单位．P3：甲、乙两工厂的设备应全力运转，避免有空闲时间，两厂的单位运转成本当作它们的权系数．P4：甲厂的超过作业时间全月份不宜超过30h．P5：B药的销量必须完成1000单位．P6：两个工厂的超时工作时间总和要求限制，其限制的比率依各厂每小时运转成本为准．试确定A、B药各生产多少，使目标达到最好，建立目标规划模型并化成标准型§5.2目标规划的图解法和线性规划问题一样，图解法虽然只适用于两个决策变量的目标规划问题，但其操作简便，原理一目了然，并且有助于理解一般目标规划问题的求解原理和过程。

图解法解题的步骤为：1.确定各约束条件的可行域，即将所有约束条件(包括目标约束和绝对约束，暂不考虑正负偏差变量)在坐标平面上表示出来；

2.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；

3.求满足最高优先等级目标的解；4.转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；5.重复4，直到所有优先等级的目标都已审查完毕为止；6.确定最优解或满意解。下面通过例子来说明目标规划图解法的原理和步骤。例1用图解法求解目标规划问题：解

确定各个约束条件的可行域。在x1Ox2坐标平面上，暂不考虑每个约束方程中的正、负偏差变量，将上述每一个约束方程用一条直线表示出来，再用两个箭头分别表示上述目标约束方程中的正、负偏差变量。

4x1≤164x2≤122x1+3x2+d1-

–d1+=12x1－x2+d2-–d2+=02x1+2x2+d3-

–d3+=12

x1+2x2+d4-

–d4+=8x1,x2，di-,di+

≥0例1用图解法求解目标规划问题：

4x1≤164x2≤122x1+3x2+d1-

–d1+=123x1－4x2+d2-–d2+=02x1+2x2+d3-

–d3+=12

x1+2x2+d4-

–d4+=8x1,x2，di-,di+

≥01x1x2430215623456ABCd1+d1-d2-d2+d3-d3+d4+d4-EDF3x1-4x2=0x1+2x2=8得x1=3.2，x2=2.4例2用图解法求解目标规划问题：

10x1+12x2+d1-

–d1+＝62.5x1+2x2+d2-

–d2+=102x1+x2

≤8

x1,x2，d1-,d1+,d,2-,d2+

≥01x1x2430215623456d1-d1+d2+d2-D(0.625,4.6875)C(0,5.2083)于是，C,D两点及CD线段上的所有点(无穷多个)均是该问题的最优解。其中：C点对应的解为：x1=0，x2=5.2083；D点对应的解为：x1=0.6250，x2=4.6875；

例3、用图解法求解线性规划模型

30x1+12x2+d1-

–d1+＝25002x1+x2+d2-

–d2+=140

x1,x2，di-,di+

≥0

x1+d3-

–d3+＝60

x2+d4-

–d4+＝100

minZ=P1d1-

+P2(2.5d3++d4+)

+P3d2+于是，确定D点的坐标x1=60，x2=58.3为所求的满意解。即D(60,58.3)验算将x1=60，x2=58.3代入约束条件，有

以上验算表明，若A、B的计划生产量分别为60件和58.3件，所需甲种原料的数量超过了现有库存量。这就意味着，在现有资源条件下，求得的为非可行解。为了使这个解能成为可行解，工厂领导必须采取先进的技术手段和有效管理措施降低A、B产品对甲种原料的消耗量。显然，A、B产品每件所需甲种原料量应变为原有消耗量的78.5%(140/178.3=78.5%)，才能使求得的生产方案(x1=60，x2=58.3)成为可行方案。

30x1+12x2+d1-

–d1+＝25002x1+x2+d2-

–d2+=140

x1,x2，di-,di+

≥0

x1+d3-

–d3+＝60

x2+d4-

–d4+＝100

minZ=P1d1-

+P2(2.5d3++d4+)+P3d2+分析在上述两个例子中，前一个例子求得的结果为可行解，后一个例子求得的结果为非可行解。这就表明目标规划模型的求解结果可以是非可行解。而这正是目标规划模型与线性规划模型在求解思想上的差别，即线性规划立足于求满意解。目标规划模型的满意解虽然可能是非可行解，但它却有助于了解问题的薄弱环节以便有的放矢改进工作。练习：用图解法求解下列目标规划问题

(2)(3)(4)(1)CD结论：有无穷多最优解。C（2，4），D（10/3，10/3）2、用图解法解下列目标规划模型x1=400,x2=0,Z=80p3x2

1002003004005000x1100200300400最满意解为x1=400,x2=0§5.4目标有优先级的目标规划解法--加权法产品A产品B产品C条件利润（万元/吨）941总利润最大化耗用原料（吨/吨）425耗用原料总量不超过38吨排放污染（m3/吨）213排放污染总量不超过26m3销售价格（万元/吨）301020销售总额不低于100万元总产量（吨）111总产量不低于18吨如果以利润为目标函数，线性规划模型为：maxz=9x1+4x2+x3s.t.4x1+2x2+5x3≤38 （1）原料总量约束2x1+x2+3x3≤26 （2）排放污染约束30x1+10x2+20x3≥100 （3）销售总额约束x1+x2+x3≥18 （4）总产量约束x1,x2,x3≥0例：线性规划解得：x1=1,x2=17,x3

=0，maxZ=77目标规划如果利润期望值为77，将利润、耗用原料等五个因素作为目标，确定各目标的理想值以及偏差变量如下：目标产品A产品B产品C目标的理想值正偏差变量负偏差变量利润（万元/吨）94177d1+d1-耗用原料（吨/吨）42538d2+d2-排放污染（m3/吨）21326d3+d3-销售价格（万元/吨）301020100d4+d4-总产量（吨）11118d5+d5-如果目标大于理想值，正偏差变量大于0，小于理想值，负偏差变量大于0。因此，对第i个目标，有

如果各目标无优先级，要使所有的目标总偏差最小，即无优先级的目标规划模型为：同一个目标的正负偏差变量，不可能两个同时大于0。这一结果的实际意义也是很清楚的：任何一个目标，不可能既大于理想值，又小于理想值。

用单纯形法，得到目标规划的最优解、各目标的值以及偏差变量的值产品A产品B产品C目标的理想值正偏差变量负偏差变量产量（吨）0100RHSdi+di-达到的目标值利润（万元）4077037耗用原料（吨）3038018排放污染（m3）1026016销售价格（万元）10010000总产量（吨）101808最优解实现值偏差变量目标有优先级的目标规划产品A产品B产品C目标的理想值正偏差变量负偏差变量产量（吨）0100RHSdi+di-达到的目标值利润（万元）4077037耗用原料（吨）3038018排放污染（m3）1026016销售价格（万元）10010000总产量（吨）101808在上面的例子中，利润、耗用原料、排放污染、销售额、总产量等五个目标是一视同仁的，最优解是使偏离五个目标的总偏差之和最小。在实际问题中，这些目标往往是有轻重缓急的。

目标产品A产品B产品C优先级Pi目标的理想值正偏差变量负偏差变量利润（万元/吨）941177d1+d1-

耗用原料（吨/吨）425438d2+d2-排放污染（m3/吨）213326d3+d3-销售价格（万元/吨）3010205100d4+d4-总产量（吨）111218d5+d5-确定五个目标的优先级Pi（Pi=1，2，3，4，5），数字越小优先级越高目标规划的模型为：优先级Pi14352

目标产品A产品B产品C优先级权重理想值正偏差负偏差利润（万元/吨）941110000077d1+d1-耗用原料（吨/吨）425410038d2+d2-排放污染（m3/吨）2133100026d3+d3-销售价格（万元/吨）30102051