目标规划模型

线性规划处理问题时，将各个约束（也可看做目标）的地位看成同等重要，而在实际问题中，各个目标的重要性既有层次上的差别，也有在同一层次上不同权重的差别.为了克服线性规划的局限性，目标规划采用如下手段：

设置偏差变量：用偏差变量（Deviational Variables）来表示实际值与目标值之间的差异，令d⁺为超出目标的差值，称为正偏差变量；d^-为未达到目标的差值，称为负偏差变量.其中d⁺与d^-至少有一个为0.当实际值超过目标值时，有d^-=0，d⁺＞0；当实际值未达到目标值时，有d⁺=0，d^-＞0；当实际值与目标值一致时，有d^-=d⁺=0.

统一处理目标与决策：在目标规划中，约束有两类.一类是对资源有严格限制的，同线性规划的处理相同，用严格的等式或不等式约束来处理，构成刚性约束；另一类约束是可以不严格限制的，连同原线性规划的目标，构成柔性约束.分析可以得到，如果希望不等式保持大于等于，则极小化负偏差；如果希望不等式保持小于等于，则极小化正偏差；如果希望等式保持等式，则同时极小化正负偏差.

目标的优先级与权系数：在目标规划模型中，目标的优先级分成两个层次.第一个层次目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标.通常以P₁，P₂，…表示不同的因子，并规定P_kP_k+1，第二个层次目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，但用权系数的大小来表示目标重要性的差别.

目标规划的一般模型可以表示如下：设x_j（j=1，2，…，n）是目标规划的决策变量，共有m个约束是刚性约束，可能是等式约束，也可能是不等式约束.设有l个柔性目标约束，其目标规划约束的偏差为d⁺_i，d^-_i（i=1，2，…，l）.设有q个优先级别分别P₁，P₂，…，P_q.在同一个优先级P_k中，有不同的权重，分别记为w⁺_kj，w^-_kj（j=1，2，…，l）.因此目标规划的一般数学表达式为：

例5-8　笔记本电脑生产销售问题

某计算机公司生产三种型号的笔记本电脑A、B、C.这三种笔记本电脑需要在复杂的装配线上生产，生产1台A、B、C 型号的笔记本电脑分别需要5 h，8 h，12 h.公司装配线在正常的生产时间是每月1700 h.公司营业部门估计A、B、C 三种笔记本电脑的利润分别是1000元，1440元，2520元，而公司预计这个月生产的笔记本电脑能够全部售出.公司经理考虑以下目标：

第一目标：充分利用正常的生产能力，避免开工不足；第二目标：优先满足老顾客的需求，A、B、C 三种型号的电脑50台，50台，80台，同时根据三种电脑的纯利润分配不同的权因子；第三目标：限制装配线加班时间，不允许超过200 h；第四目标：满足各种型号电脑的销售目标，A、B、C 型号分别为100台，120台，100台，再根据三种电脑的纯利润分配不同的权重.第五目标：装配线的加班时间尽可能少.

【解题思路】

设生产A、B、C 型号的电脑为x₁，x₂，x₃，d^-_i为装配线正常生产时间未利用数，d⁺_i为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约束可以表述如下：

销售目标：优先满足老客户的需求，并根据三种电脑的纯利润分配不同的权因子，A，B，C 三种型号的电脑每小时的利润是，因此，老客户的销售目标约束可以表述如下：

再考虑一般销售，类似上面的讨论，得到如下约束表达式：

加班限制：首先是限制装配线加班时间，不允许超过200 h，因此得到

其次装配线的加班时间尽可能少，即

写出目标规划的数学模型：

目标规划问题可以通过贯序式算法进行求解，其主要的核心思想是将问题求解分解成多个步骤，每个步骤求解问题的某个目标，最后通过权重将这些步骤整合在一起.贯序式算法可以通过数学软件Lingo实现，这也给做题带来了极大的便利.下面将以实例介绍Lingo的解决方式.

目标规划的Lingo源程序如下所示：

model：

sets：

Level1..5：P，z，Goal；

Variable1..3：x；

S_Con_Num1..8：g，dplus，dminus；

S_Cons（S_Con_Num，Variable）：C；

Obj（Level，S_Con_Num）：Wplus，Wminus；

endsets

data：

P=？？？？？；

Goal=？，？，？，？，0；

g=1700 50 50 80 100 120 100 1900；

C=5 8 12 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 5 8 12；

Wplus=0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0；

Wminus=1 0 0 0 0 0 0 0 0 20 18 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 18 21 0 0 0 0 0 0 0 0 0；

enddata

min=@sum（Level∶P*z）；

@for（Level（i）：z（i）=@sum（S_Con_Num（j）：Wplus（I，j）*dplus（j））+@sum（S_Con _Num（j）：Wminus（I，j）*dminus（j）））；

@for（S_Con_Num（i）：@sum（Variable（j）：C（i，j）*x（j））+dminus（i）-dplus（i）=g（i）；）；

@for（Level（i）｜i#lt#@size（Level）：@bnd（0，z（i），Goal（i））；）；

end.

使用建模化语言Lingo进行编程，以Model标志程序的开始.首先定义集合段，在sets中定义了五种属性的集合，变量P，z，Goal是1×5的向量；g，dplus，dminus是1×8的向量，分别定义了约束条件以及偏差变量；x是1×3的向量，定义了需要求解的决策变量；C 是一个8×3的矩阵，定义了决策变量在约束条件中的系数矩阵；Wplus，Wminus是5×8的矩阵，定义了偏差变量的系数矩阵.然后在数据段中对变量进行赋初值，但是P，Goal的值是在程序运行中才能确定的，所以以“？”表示.最后以数学函数@sum，循环函数@for的形式给出问题的目标函数与约束条件.

由于在求解的过程中，需要确定权重，不同的权重会得到不同的答案，因此本例没有给出答案，大家可以在软件上自己实现.

例5-9　工厂生产销售问题

已知三个工厂生产的产品供应给四个用户，各工厂生产量、用户需求及从各工厂到用户的单位产品的运输费用如表5-8所示.由于总生产量小于总需求量，上级部门经研究后，制订了调配方案8项指标，并按重要性依次排序.

表5-8　供求关系表

第一目标：用户4为重要部门，需求量必须全部满足；

第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；

第三目标：每个用户的满足率不低于80％；

第四目标：应尽量满足各用户的需求；

第五目标：因道路限制，工厂2到用户4的线路应尽量避免运输任务；

第六目标：用户1和用户3的满足率应尽量保持平衡；

第七目标：力求减少总运费.

请列出相应的目标规划模型.

【解题思路】

设x_ij为工厂i调配给用户j的运量.

供应用户1的产品中，工厂3的商品不少于100个单位，可以得到如下表达式：

需求约束，各用户的满足率不低于80％，可以得到如下表达式：

应尽量满足各用户的需求，可以得到如下表达式：

工厂2到用户4的线路应尽量避免运输任务，即：x₂₄+d^-₁₀-d⁺₁₀=0.

用户1和用户3的满足率应尽可能保持平衡，可以得到如下表达式：

因此问题的目标函数可以表示为如下表达式：

目标规划的Lingo源程序如下所示：

model：

sets：

Level1..7：P，z，Goal；

S_Con_Num/1..12/：dplus，dminus；

Plant1..3：a；

Customer1..4：b；

Routes（Plant，Customer）：c，x；

Obj（Level，S_Con_Num）：Wplus，Wminus；

endsets

data：

P=？？？？？？？；

Goal=？？？？？？0；

a=300 200 400；

b=200 100 450 250；

c=5 2 6 7 3 5 4 6 4 5 2 3；

Wplus=0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0；

Wminus=0 0 0 0 0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 1 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0；

enddata

min=@sum（Level∶P*z）；

@for（Level（i）：z（i）=@sum（S_Con_Num（j）：Wplus（i，j）*dplus（j））+@sum（S_Con _Num（j）：Wminus（i，j）*dminus（j）））；

@for（Plant（i）：@sum（Customer（j）：x（i，j））＜=a（i））；

x（3，1）+dminus（1）-dplus（1）=100；

@for（Customer（j）：@sum（Plant（i）：x（i，j））+dminus（1+j）-dplus（1+j）=0.8*b（j）；

@sum（Plant（i）：x（i，j））+dminus（5+j）-dplus（5+j）=b（j）；）；

x（2，4）+dminus（10）-dplus（10）=0；

@sum（Plant（i）：x（i，1））-20/45*@sum（Plant（i）：x（i，3））+dminus（11）-dplus（11）=0；

@sum（Routes∶c*x）+dminus（12）-dplus（12）=2950；

@for（Level（i）｜i#lt#@size（Level）：@bnd（0，z（i），Goal（i）））；

end.

使用建模化语言Lingo进行编程，以Model标志程序开始.首先定义集合段，在sets中定义了六种属性的集合，变量P，z，Goal是1×7的向量；dplus，dminus是1×12的向量，分别定义了偏差变量；a是1×3的向量，定义了工厂的约束条件；b是1×4的向量，定义了用户的约束条件；c，x是3×4的向量，x 定义了需要求解的决策矩阵；Wplus，Wminus是7×12的矩阵，定义了偏差变量的系数矩阵.然后在数据段中对变量进行赋初值，但是P，Goal的值是在程序运行中才能确定的，所以以“？”表示.最后以数学函数@sum，循环函数@for的形式给出问题的目标函数与约束条件.

由于在求解的过程中，需要确定权重，不同的权重会得到不同的答案，因此本例没有给出答案.大家可以在软件上自己实现.