第四章 目 标 规 划
前面的线性规划问题，研究的都是只有一个目标函数，若干个约束条件的最优决策问题．然而现实生活中，衡量一个方案的好坏标准往往不止一个，而且这些标准之间往往不协调，甚至是相互冲突的，标准的度量单位也常常各不相同．例如，在资源的最优利用问题中，除了考虑所得的利润最大，还要考虑使生产的产品质量好，劳动生产率高，对市场的适应性强等等．目标规划（g oal programming ）正是在线性规划的基础上为适应这种复杂的多目标最优决策的需要，而从20世纪60年代初逐步发展起来的．它对众多的目标分别确定一个希望实现的目标值，然后按目标的重要程度（级别）依次进行考虑与计算，以求得最接近各目标预定数值的方案．如果某些目标由于种种约束不能完全实现，它也能指出目标值不能实现的程度以及原因，以供决策者参考．
第一节 目标规划的基本概念与数学模型
一、问题的提出
例4-1 某生物药厂需在市场上采购某种原料，现市场上有甲、乙两个等级，单价分别为2千元/kg 和1千元/kg ，要求采购的总费用不得超过20万元，购得原料的总重量不少于100kg ，而甲级原料又不得少于50kg ，问如何确定最好的采购方案（即用最少的钱、采购最多数量的原料）．
分析：这是一个含有两个目标的数学规划问题． 设21,x x 分别为采购甲级、乙级原材料的数量（单位：kg ），1y 为花掉的资金，2y 为所购原料总量．则：
目标函数为：
11
2
212
M i n 2
(41)M a x (4
2)
y x x y x x =
+-=+-
约束条件有： 12121
2200 (43)
100 (44)
50 x x x x x +≤-+≥-≥12
(45),0 (46)x x ??
??-??≥-?
若只考虑花钱最少，则显然属于线性规划问题，由（4-1），（4-3）至（4-6）
构成它的数学模型；若只考虑采购数量最多，也是一个线性规划问题，由式（4-2）至（4-6）构成它的数学模型，但现在两者同时都要考虑．显然是一个多目标线性规划问题．
例4-2 某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如表4-1所示．试确定计划期内的生产计划，使利润最大，同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产，同时考虑这些问题，就形成多目标规划问题．
表4-1 产品的资源、技术消耗定额、单位利润表
甲（每件）
乙（每件）
现有资源 钢 材 （kg ） 9.2 4 3600 木 材 (m 3)
4 5 2000 设备负荷（台小时） 3 10 3000 单位产品利润 (元)
70
120
分析:设21,x x 分别是计划期内甲、乙产品的产量．则该问题的数学模型为
1122122M ax 70120M ax M in y x x y x y x
=+??
=??=?
12121
212
9.243600452000
s.t.
3103000,0x x x x x x x x +≤??
+≤??
+≤??≥? 对于这样的多目标问题，线性规划很难为其找到最优方案．极有可能出现：第一个方案使第一目标的结果优于第二方案，而对于第二目标，第二方案优于第一方案．就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的．实践中，人们转而采取“不求最好，但求满意”的策略，在线性规划的基础上建立一种新的数学规划方法——目标规划．
二、目标规划的基本概念
我们不难得出多目标规划问题的一般形式如下(简记为：GP1)
1111122112211222221122M ax M ax M ax n n n n m m m mn n m y c x c x c x C X
y c x c x c x C X
y c x c x c x C X
=+++???
=+++???
?
?=+++??
（4-7）
1111221121122222112212s.t
,,,0
n n n n k k kn n k
n a x a x a x b a x a x a x b a x c x c x b
x x x +++≤??
+++≤??
??+++≤?≥?? （4-8）
矩阵表示为：(GP1)
Max ??
?≥≤=0
:,X B
AX CX Y 约束条件
(4-9)
其他情况：如目标函数为y min , 约束条件为“≥”，都可作适当的变换，调整为（4-9）的形式．下面也称（4-9）式为目标规划的标准型．
定义4-1 设{}0≥≤=X B AX X R ,, 称R 为多目标线性规划问题（简记为GP1）的可行解集合或可行解域．
这个定义与线性规划问题中可行解集定义完全一样，因此，R 是一个凸集． 定义4-2 设问题（GP1）的可行解集合非空，R X ∈*，且对任意的R X ∈都有CX
CX
≥*
，则称*X 为问题（GP1）的最优可行解，简称最优解．
最优解实际上是使所有目标同时达到最优值，如图4—1所示
目标2
目标1
R
x 1
x 2
图4-1 目标规划解集示意图
但更多的情况是：由于多目标之间存在相互矛盾，最优解往往不可能存在，这就要求我们退而求其次，根据目标之间的相对重要程度，分等级和权重，求出相对最优解——有效解（满意解），为此引入以下概念，对目标函数和约束条件作适当处理．
（一）决策变量与偏差变量
决策变量也称控制变量，用x 1、x 2、…、x n 表示，如例4-1中的x 1、x 2等．
在多目标规划问题中，由于目标之间存在冲突或约束条件中有矛盾方程，我们可以设想降低目标要求、“放松”严格的约束条件，即从实际出发，根据经验、历史资料或市场的需求、上级部门的任务下达等来给每个目标确定一个希望达到的目标值e i , (i =1，2，…，m )．一般说来，这些值e i 的确定并不要求十分精确或严格，允许决策的实际值大于或小于e i ．我们称实际值与目标值的差距为偏差变量(deviation variable)．用-+i i d d 和表示．
+
i d ——第i 个目标的实际值超出目标值的部分，称为正偏差变量． -
i
d ——第i 个目标的实际值不足目标值的差距，称为负偏差变量．规定
-
+
i i d d 和≥0,
(i =1，2，…，m ) ．
实际操作中，当目标值确定时，所做的决策只可能出现以下三种情况：即由
-
+
i
i d d 和所构成的3种不同组合表示的含义：① 0=0>-+i i d d ,表示第i 个目标的
实际值超出目标值；②0,0>=-+i i d d 表示第i 个目标的实际值未达到目标值；③
0=0=-
+
i i d d ,表示第
i 个目标的实际值恰好等于目标值．并且无论发生哪种情况
均有：0=?-+i i d d ．
如在例4-2中，若提出目标y 1的期望值e 1= 45000元，y 2的期望值e 2=250件，y 3的期望值e 3=200件，则可引入偏差变量-+i i d d ,（i =1，2，3）, +1d 表示利润超过45000元的数量，-1d 则表示利润距45000元还差的数量，+2d 表示甲产品产量超过250件的部分，……．这样可得三个目标函数方程
???????≥=-+=-+=-+++
-+-+-+
-+
-+-0
,,,,,20025045000
120703322113322211121d d d d d d d d x d d x d d x x (4-10)
（二） 目标约束与绝对约束
前面通过确定各目标的目标值、引入偏差变量，把目标函数转化成约束方程，从而并入原约束条件中，我们称这类具有机动余地的约束为目标约束(goal restrictions)．如例4-2的目标函数转化为目标约束（4-10）．因它具有一定的弹性，
一般目标约束不会不满足，只是可能偏差要大一些，故也称为软约束．
绝对约束(absolute restrictions)是指必须严格满足的等式或不等式约束，也称为系统约束．它对应于线性规划中的约束条件（如资源、客观条件约束等），不能满足绝对约束的解即为不可行解，因此也称为硬约束．
在一个规划问题中，有时会因为资源的短缺等原因，在约束条件中出现互相矛盾的方程．此时，可行解集合是空集．应用一般的线性规划方法，只能得出无解的结论．而在实际的决策问题里，决策者需要采取一定的措施，或增加资源，或减少产量，综合平衡各方面的因素，寻求可行的方案．而要找出哪种资源短缺，哪个产量指标过高，仍是解决问题的前提，采取一般的线性规划单纯形法解决这个问题显得十分困难．而在目标规划中，将比较容易解决这个问题． 我们设想将约束条件“放松”，对约束方程也引入偏差变量，使矛盾的方程不再矛盾！然后通过适当的方法，找出问题的关键，即需要增加的资源品种与数量或需降低的产品产量等，就会获得较好的决策效果．这说明两种约束在一定条件下可以转换．
例如：在例4-2中，若再增加约束条件：甲、乙两产品总的生产件数大于510，即：510≥+21x x ，显然它与约束条件中的：4x 1+5x 2≤2000 矛盾！这样解空间成了空集．但若对新加入的约束条件引入正、负偏差变量0≥-7+7d d ,，可得约束方程
510
7721=-+++
-
d d x x
由于-7+7d d , 的作用，约束条件不再矛盾，可行解空间就非空了，我们便可应用后面介绍的方法求出相应的解，从而找出发生矛盾的关键因素及相应的数量，为进一步进行决策提供有力的依据．
当不易发现约束条件中是否有矛盾方程时，更一般的方法是对所有绝对约束都引入偏差变量，从而把约束条件全部变为等式．
（三）目标规划的目标函数
通过引入偏差变量，使原规划问题中的目标函数变成了目标约束，那么现在问题的目标是什么呢？我们知道：对于满足绝对约束和目标约束的所有解（即可行解），从决策者角度看，判断其优劣的依据是决策值与目标值的偏差越小越好．从而目标规划的目标函数就可由偏差变量构成．它有三种基本表现形式：
① 要求恰好达到目标值的，即正、负偏差变量都要尽可能小． 构造目标函数为：M in i i Z d d +-=+．② 要求不能超过目标值的，即允许达不到目标值，但即使超过，一定要越小越好．构造目标函数为：M in i Z d +=．③ 要求超过目标值的，即允许超过目标值，但即使不足，一定要使缺少量越少越好．构造目标函数为：M in i Z d -=．这样根据各个目标的不同要求，确定出总的目标函数
,M in ()
i
j i j
Z d
d +-
=
+∑．
如例4-2中的目标函数可表示为 123M i n Z d d d --
+
=++
．
其完整的目标规划模型为
123
M in Z d d d -
-
+
=++
12111222331212
12127012045000
250 200s.t.9.243600
452000
3103000,0,,0,(1,2,3)i i x x d d x d d x d d x x x x x x x x d d i -+-+
-+
-+
?++-=?+-=??+-=??
+≤??+≤?
?+≤?≥≥=??
（四）优先因子与权系数
目标规划中，当决策者要求实现多个目标时，这些目标的偏差可能相互替代或抵消，因为我们求的是所有偏差和最小，而实际问题中的目标之间也有主次、轻重、缓急之区别．决策者往往有一些最重要的，第一位要求达到的目标，我们赋予它优先因子(factor of priority )P 1，在它实现的前提下再去解决次要目标．依次把第二位达到的目标赋予优先因子P 2 ……，并规定P k ?P k+1，即不管P k+1乘以一个多大的正数M ，总成立P k >MP k+1,表示P k 比P k+1具有绝对的优先权．因此，不同的优先因子代表着不同的优先等级．在实现多个目标时，首先保证P 1级目标的实现，这时可不考虑其它级别目标，而P 2级目标是在保证P 1级目标满足的前提下考虑的．决不能因为要使P 2级目标更好地实现，而去降低P 1级目标的实现值．一般地在目标规划模型中，绝对约束相应的目标函数，其优先等级一定是P 1级．
若要进一步区别具有相同优先级的多个目标，则可分别赋予它们不同的权系数j ω(j ω可取一确定的非负实数)，根据目标的重要程度而给它们赋值，重要的目标，赋值较大，反之j ω值就小．如例4-2中，我们可把利润视作第一位重要，甲、乙产品的产量分配视作第二位，并且甲的产量越大越好，权重分别为10和2，则目标函数为：11223M in (102)Z P d P d d --+=++
由上面分析看到，目标规划比起线性规划来适应面要灵活得多．它可同时考虑多个目标，而且目标的计量单位也可以多种多样．目标规划的目标约束，给决策方案的选择带来很大的灵活性．并且由于目标规划中划分优先级和权系数的大小，使决策者可根据外界条件变化，通过调整目标优先级和权系数，求出不同方案以供选择．但是，用目标规划来处理问题也存在困难，主要表现在构造模型时需事先拟定目标值、优先级和权系数，而这些信息来自人的主观判断，往往带有模糊性，很难定出一个绝对的数值．
三、目标规划的数学模型
其实通过上面分析，目标规划问题的数学模型已经清析可见，如例4-2中问题的模型为
11223M in (102)
Z P d P d d -
-
+
=++
若把约束条件中的不等式全部化为等式约束，我们称之为“标准型”． 例4-2中问题的标准型为
11223M in (102)
Z P d P d d -
-
+
=++
12111222331212
12127012045000
250 200s.t.9.243600
452000
3103000,0,,0,(1,2,3)i i x x d d x d d x d d x x x x x x x x d d i -+-+
-+
-+
?++-=?+-=??+-=??
+≤??+≤?
?+≤?≥≥=??
s ．t
??
??
??
???????=≥≥=-++=-++=-++=-+=-+=-+++
-+-+
-+
-+
-+
-+-)6,,2,1(,0,,0,3000
103200054360042.9200 250 4500012070216
621552144213322211121 i d d x x d d x x d d x x d d x x d d x d d x d d x x i i
一般地，对于n 个决策变量，m 个目标约束，目标函数中有k 个优先级的目标规划问题，其数学模型的标准型如下：
1
1
M in ()
()s.t.,,0,(1,2,,)k
m i
ij
j
ij j i j i i i i
i i Z P d
d f X d d b X d d i n ω
ω-
-++
==-+
-+
=
+?+-=??
≥=??
∑∑
其中：P i 为优先等级；-ij ω, +ij ω为权系数．
综上所述，一个实际问题的目标规划模型的建立步骤为：
1） 根据问题所提出的各目标与条件，确定目标值（期望值），设定决策变量并列出目标约束与绝对约束；
2） 根据决策者的需要将某些或全部绝对约束，通过引入偏差变量转换为目标约束；
3） 给各级目标赋予相应的优先因子k P ，对同一优先级的各目标，按重要程度不同赋予相应的权系数kl ω；
4） 根据决策者的要求，各目标按三种情况取值：①恰好达到目标值，取
-
+
+i
i d d ；②允许超过目标值，取-i d ；③不允许超过目标值，取+i d ．然后构造一
个由优先因子、权系数与偏差变量组成的、要求最小化的目标函数．
最重要的目标、必须严格实现的目标及无法再增加的资源约束均应列入P 1级，其余按重要程度分别列入后面各级，并在同一级中确定权系数．一般地，如果问题的P 1级目标不能完全实现，则我们就认为该问题无不可行．
例4-3 某制药公司有甲、乙两个工厂，现要生产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单位．
该公司依下列次序为目标的优先次序，以实现次月的生产与销售目标． P 1：厂内的储存成本不超过23000元． P 2：A 销售量必须完成1500单位．
P 3：甲、乙两工厂的设备应全力运转，避免有空闲时间，两厂的单位运转成本当作它们的权系数．
P 4：甲厂的超过作业时间全月份不宜超过30h ． P 5：B 药的销量必须完成1000单位．
P 6：两个工厂的超时工作时间总和要求限制，其限制的比率依各厂每小时运转成本为准．
试确定A 、B 药各生产多少，使目标达到最好，建立目标规划模型并化成标准型．
解 设21x x ,分别表示次月份A 、B 药品的生产量，-+i i d d 和为相应目标约束的正、负偏差变量．
（1）甲、乙两厂设备运转时间约束： 甲的总时间为8×12×25=2400（h ），乙的总工作时间为16×7×25=2800（h ），则：
2800
=-+51+522400=-+4+2+
2-221+
1-
121d d x x d d x x ..,
（2）公司内储存成本约束：23000=-+15+8+3-321d d x x （3）销售目标约束：1000
=-+1500=-++
5-
52+4-41d d x d d x ,
（4）甲厂超时作业约束： 30=-++
11-11
+1d d d （5）目标函数：
132431241155612M in (65)(65)
Z P d P d P d d P d P d P d d +
-
-
-
+
-
+
+
=+++++++
其中：6:5=18:15为运转成本比率．
综合上述过程，可得该问题的目标规划模型：
13243124115561212111222123314425511111
M in (65)(65)
2424002.5 1.5 2800 8 15 23000s.t.
1500 1000Z P d P d P d d P d P d P d d x x d d x x d d x x d d x d d x d d d d d -
-
-
-
+
-
+
+
-+-+
-+
-+
-+
+-+=+++++++++-=++-=++-=+-=+-=+-=1230
,0,,0,(1,2,3,4,5,11)i i x x d d i -+
?????????
??
≥≥=??
第二节 目标规划的图解法
由于目标规划是在线性规划的基础上建立，并弥补了部分不足．所以两种规划模型结构没有本质区别，解法也非常类似．形式上的区别主要在于：①线性规划只能处理一个目标，而目标规划能统筹兼顾地处理多个目标关系，以求得切合实际需求的解；②线性规划是求满足所有约束条件的最优解，而目标规划是要在相互矛盾的目标或约束条件下找到尽量好的满意解；③线性规划的约束条件是不分主次地同等对待，而目标规划可根据实际需要给予轻重缓急的考虑．
比如关于最优解：线性规划是在可行解域内寻找某一点，使单个目标达到最优值（最大值或最小值）．而目标规划是在可行域内，首先寻找到一个使P 1级目标均满足的区域R 1，然后再在R 1中寻找一个使P 2级目标均满足或尽最大可能满足的区域R 2（?R 1），再在R 2中寻找一个满足P 3的各目标的区域R 3（?R 2?R 1），…,如此下去，直到寻找到一个区域R k (?R k -1?…?R 1)，满足P k 级的各目标，这个R k 即为所求的解域，如果某一个R i (1≤i ≤k )已退化为一点，则计算终止，这一点即为满意解，它只能满足P 1,…，P i 级目标，而无法进一步改进，当然，此时或许有低于P i 级目标被满足，这纯属巧合．
目标规划图解法的具体演算过程与线性规划图解法类似．
第1步：根据决策变量（当然不能多于2个）绘画所有（软、硬）约束条件的直线图形，偏差变量以移动（平移）直线的方法加以考虑．
第2步：对P 1级的各目标，确定解区域R 1．
第3步：对下一个优先级别P i 级各目标，确定它的最优解空间R i ，但必须是R i ?R i -1 ( i =2,3,…)．
第4步：在这个过程中，如果某解区域R i 减小到一点，则可结束这个过程，因为此时没有进一步改进的可能．
第5步：重复第3、4步过程，直到解区域R i 减少到一点或满足了所有k 个级别的目标为止，此时，R k 即为这个目标规划的最优解区域，其中的任何一点均为目标规划的满意解．
例4-4 求解下面目标规划:
112233
121121121222M in 51060
()2 0 ()s.t
4 4 36
Z P d P d P d x x l x x d d l x x d d -
+
-
-+
-+
=+++≤-+-=++-=31
233412
()68 48 (),0,,0,(1,2,3)
i i l x x d d l x x d d i -+
-+??????++-=??≥≥=? 解 将约束方程以直线形式画在图上，这里只使用决策变量（即21x x ,），偏差变量在画直线时被去掉，直线画好后，在该直线上标出目标函数中与该直线相关的偏差变量增大时直线的平移方向（用垂直于直线的箭头来反映）． 如图4-2．
图4-2 图解法示意图
按优先级高低，首先考虑P 1级目标，要求-1d min ，就在绝对约束的可行解域△OAB 中进一步缩小为△OAC ，记作R 1；再考虑P 2级目标，此时要求+2d min ，
因而解空间R 2为△OCD 区域；最后考虑P 3级，此时要求-3d min ，由图4-2可知R 3为四边形CDEF 区域，这个区域内的任一点均是该问题的满意解，可使目标函数0=z min ．
由于C 、D 、E 、F 坐标分别为（6，3）、（9，0），（8，0），（4．8, 2．4）， 故满意解可表示为：
)
.,.( ).,.(),(),(),(),(41432143212142+384+8+9+6=4284+08+09+36=ααααααααααx x
其中：),,,(,4321=0≥1=+++4321i i ααααα
这种满足目标函数中所有目标要求的情况，即：0=z min ，在实际中并不多见，很多目标规划问题只能满足前面几级目标要求．
例4-5 用图解法求解下面目标规划问题：
112233
12111122221233M in 10 ()
2 26
() 2 6
Z P d P d P d x x d d l x x d d l x x d d +
-
-
-+-+
-+
=++++-=++-=-++-=312 (),0,,0,(1,2,3)
i i l x x d d i -+??????
≥≥=? 解 作图4-3：
图4-3 图解法示意图
满足P 1级的区域为R 1，即△OAB, 现在其中考虑P 2级目标，由于直线l 2与R 1不相交，所以在R 1内无法使0=-2d ，因此在不退化P 1级目标时，不可能使P 2级目标完全满足．这样R 2就缩为一点，因为在R 1中，使-2d 达到最小的为C
点：x * = (10 ,0), 6=-2d ,
由于R 2仅含有一个点，所以对P 3级目标，我们已经无法进一步的选择与考虑，可求得16=-3d ，即目标函数为：3216+6=P P z min ．
此例中，之所以产生解域R 2退缩为一个点，从而无法使P 2，P 3级目标达成，是因为P 2级目标的期望值定得过高．如果将它的目标值从26降到14，则可考虑到P 3级目标，见图4-4． 满足P 1、P 2级目标的可行解域为△ACG ，进一步考察P 3级目标可得最优解区域△EFG ，对该区域中任意一点，均同时能使P 1，P 2，P 3级目标完全满足，这时问题的满意解不唯一．一般地，目标要求确定得越低，可供选择的解越多，目标定得太高，满意解的选择余地也越小，甚至一些低级别的目标无法实现．
另外值得一提的是，在目标规划中，考虑低级别目标时，不能破坏已经满足的高级别目标，这是基本原则．但它并不是说，当某一高级别目标不可能满足时，其后的低级别目标就一定不能满足．而是在有些目标规划中，当某一优先级的目标不能满足时，其后的某些低级别目标仍可能被满足．
第三节 目标规划的单纯形解法
由目标规划数学模型的标准型可看出，它实质上是最小化的线性规划，所以可用单纯形法求解．这时，我们应该把目标优先等级系数P i （i =1,2,…,k ）理解为一种特殊的正常数，且注意到各等级系数之间的关系：P 1 ?P 2?…?P k ．检验数就
是各优先因子P 1,P 2,…,P k 的线性组合，当所有检验数都满足最优性条件（0j j j C c z =-≥）时，从最终表上即可得出目标规划的解．
例4-6 用单纯形法求例4-4的解 解 引入松驰变量x 3,将它们化为标准型：
112233
1231
21112221233123
M in 510602 0s.t.4 4 36
68 48,,0,,0,(1,2,3)
i i Z P d P d P d x x x x x d d x x d d x x d d x x x d d i -
+
-
-+
-+
-+
-+=++++=??-+-=??++-=??++-=?
?≥≥=? 建立单纯形表，见表4-2，并把检验数j j j C c z =-用代数和表示，如：3
213+2+P P P 表示为：???
?
? ??321?????
?
??3
2
1
P P P ，其中“?”是一种运算符号，表示向量的数量积运算． 表4-2 单纯形表
计算步骤说明：
1．确定初始“基”（同线性规划单纯形法），计算检验数矩阵
()111
121913132351100,,0,60,:,.664P C P P P P P C C P ??
-???? ?
? ?
?=-=--=? ? ? ?
? ?
- ???????
同理可求出 2．最优性检验 目标规划的最优性检验是分优先级进行的，从P 1级开始依次到P k 级为止，具体检验P i 级目标时，可能有下述三种情况．
（1）若检验数矩阵的P i 行系数均≥0，则P i 级目标已达最优，应转入对P i+1级目标的寻优，直到i=k ，计算结束． 如本题中第二段检验数部分，P 1行各系数均≥0，故P 1目标已达最优：0==-1+1d d ．
（2）若检验数矩阵的P i 中有负系数，且负系数所在列的前i -1行优先因子的系数全为0，可判定该检验数为负，则选该系数（若此类负系数有多个，则可选绝对值最大者）所在列对应的非基变量为入基变量，继续进行基变换． 如本题中初始基确定后，从检验数可确定出x 1为入基变量，经变换后，再从检验数行看出，P 3行的系数有两个负数-20和-6，它们所对应列的前两行元素全为0，故选-20对应的变量x 2为入基变量，继续进行迭代变换．
（3）若检验数矩阵的P i 行中有负系数，但负系数所在列的前i -1行优先因子的系数有0，也有正数（没有负数），即整个检验数的值可判为正（因P i -1?P i ），故也应转入对P i +1级目标的寻优，否则会使高优先级别的目标函数值劣化．
3．基变换 ① 入基变量的确定：依步骤2可确定入基变量．② 出基变量的确定：按最小非负比值规则确定出基变量，同线性规划的单纯形法．③ 主元素的确定：出基变量与入基变量在系数矩阵中对应的交叉点上的元素即为主元素．④ 迭代变换：同线性规划的单纯形法．
4．从表中找到基本可行解和相应于各优先级的目标函数值 每个单纯形表中常数列b ，即为各基变量的相应取值．本题最后一个单纯形表已为最优，它对应的基本可行解：x 1=24/5, x 2=12/5, x 3=12, -2d =36/5，即为最优解．这与图解法得到结果一致．
值得一提的是：① 在最优单纯形表中非基变量+3+1d d 和的检验数都是零，故
知本题有多个最优解．如以+
d为入基变量继续迭代，可得单纯形表4-3，如以+3d
1
为入基变量继续迭代，可得单纯形表4-4．②目标规划可以用计算机进行数值逼近求解，只要适当注意优先因子与权系数的取值，就如同线性规划机器解一样，见第十三章．
表4-3 续单纯形表4-2
表4-4 续单纯形表4—2：
例4-7某公司生产A、B两种药品，这两种药品每小时的产量均为1000盒，该公司每天采用两班制生产，每周最大工作时间为80小时，按预测每周市场最大销量分别为70000盒和45000盒．A种药每盒的利润为2.5元，B种为1．5元．试确定公司每周A、B两种药品生产量x1和x2（单位：千盒），使公司的下列目标得以实现：
P1：避免每周80小时生产能力的过少使用．
P2：加班的时间限制在10小时以内．
P3：A、B两种药品的每周产量尽量分别达到70,000盒和45,000盒，但不得超出，其权系数依它们每盒的利润为准．
P4：尽量减少加班时间．
解 先建立这个问题的线性规划模型，依题意分别建立各项目标约束
??
???????321=0≥0≥45=+70
=+10=-+80=-+++-2
1-
32-
21+
11-11+
1+1-121)
,,(,,,, i d d x x d x d x d d d d d x x i i 权系数是指它们在目标函数中的重要程度，由2.5∶1.5=5∶3，故：目标函数为：
()11211323
4
1
M in 53Z P d P d P d d P d
-
+
-
-
+
=++++
建立单纯形表运算如下：
表4-5 单纯形表
至此，由于P 1 ?P 2? P 3?P 4 ，可知各检验数均非负，从而得最优解为：x 1=70，
x 2=20，0=-1d , 10=+1d , 0=-2d , 25=-
3d , 0=-11d ,0=+
11d
即生产A 种药品70 000盒，B 种药品20 000盒，P 1，P 2级目标可完全实现．因
10
=+
1d ，故每周需加班10小时，每周利润为：70000×2．5+20000×1．5=205000
（元）．
第四节 目标规划应用举例
目标规划是一种重要的多目标决策工具，有着广泛的实际应用，例如某高校有各类教职员工如下：助教、助研、讲师、教授助理、副教授、教授、兼职教师、专家及职工, 各类人员所承担的工作性质、工作量和工资各不相同，预计在下一学年要招收一定数量的本科生与研究生，现应用目标规划来确定聘用各类人员的人数，既要保持各类人员之间的适当比例，完成学校的各项工作，同时又要取得最好的经济效益．设聘用各类人员的人数如下：
x 1助研（可由研究生兼任） y 1教授助理（有博士学位） x 2助教（可由研究生兼任） y 2副教授（有博士学位） x 3讲师 y 3教授（有博士学位） x 4教授助理（无博士学位） y 4兼职教师（有博士学位） x 5副教授（无博士学位） y 5专家（有博士学位） x 6教授（无博士学位） w 1所有教职工的工资总基数
x 7兼职教师（无博士学位） w 2所有教职工的工资比上一年的总增加数 x 8专家（无博士学位） x 9职工
现各类人员承担的工作量，工资及所占比例见表4-6． 校方确定的各级决策目标为：
P 1：要求教师有一定的学术水平，即75%的教师是专职的，担任本科生教学
工作的教师中，至少有40%的人具有博士学位．担任研究生教学的至少有75%的人具有博士学位．
P 2：要求各类人员增加工资的总额不得超过176000美元，其中x 1，x 2和x 9增加的工资数为其原工资数的6%，而其它人员为8%．
P 3：要求能完成学校的各项教学工作，即学校计划招收本科生1820名、研究生100名．要求为本科生每周开课共910学时，研究生每周开课100学时，并要求本科生教师与学生人数比为1∶20，研究生教师与学生人数比为1∶10．
表4-6 各类人员工作量，工资及所占比例表
变 量 承担的教学工作量（学时/周） 所占教师的百分比（%） 年工资 （美元） 本科生 研究生 最大 最小 x 1 0 0 -- -- 3000 x 2 6 0 7 -- 3000 x 3 12 0 7 -- 8000 x 4 9 0 15 -- 13000 x 5 9 0 5 -- 15000 x 6 6 0 2 -- 17000 x 7 3 0 1 -- 2000 x 8 0 3 -- 1 30000 x 9 -- -- -- -- 4000 y 1 6 3 -- 21 13000 y 2 6 3 -- 14 15000 y 3 3 3 -- 23 17000 y 4 0 3 2 -- 2000 y 5
3
--
2
30000
P 4：要求各类教学人员之间有适当的比例，即x 2所占全体教师比例不超过7%，x 3不超过7%，x 4不超过15%，x 5不超过5%，x 6不超过2%，x 7不超过1%，x 8不低于1%，y 1不低于21%，y 2不低于14%，y 3不低于23%，y 4不超过2%，y 5不低于2%．
P 5：要求教师与行政管理职工x 9之比不超过4∶1 P 6：要求教师与助研x 1的比不超过5∶1． P 7：要求所有人员总工资基数尽可能地小． 如此可得如下各约束条件： （1） 75%的的教师是专职的:
0=-++
750-++
++
1-
15
1
=8
1
=53
1
=6
3
=8∑
∑∑
∑d d y x y y x x
i i i i i i i i
)(.
本科生教学中至少40%有博士学位：0
=-++
400-+
2-23
1
=72
=31
=∑
∑∑d d y x y i i i i i i )(.
研究生教学中至少75%有博士学位：0=-++
750-+
3-
35
1
=851
=∑
∑d d y x y i i i i )(.
（2） 教学任务
本科生：910=-+3+6+6+3+6+9+9+12+6+4-4321765432d d y y y x x x x x x 研究生：100=-+3+3+3+3+3+3+5-5543218d d y y y y y x
教师数：91=-+++6
-6
3
1
=7
2
=∑∑d d y x i i i i ， 10=-+++7-75
1
=8∑d d y x i i
（3） 教学人员比例：令T =∑∑5
1
=8
2
=+i i i i y x
=-+-0200=-+-0200=-+-2300=-+-1400=-+-2100
=-+-0100=-+-0100=-+-0200=-+-0500=-+-1500=-+-0700=-+-070+
19-195+
18-184+
17-173+
16-162+
15-151+14-148+13-
137+
12-
126+
11-
115+
10-
104+
9-
93+
8-82d d y T d d y T d d y T d d y T d d y T d d
x T d d x T d d x T d d x T d d x T d d x T d d x T ............
（4） 教师与职工（x 9）之比不超过4∶1 ： 0=-+4-+
20-20
9d d x T （5） 教师与助研（x 1）之比不超过5∶1 ： 0=-+5-+
21-21
1d d x T （6） 全体人员工资增加总额
=-+-30000+2000+17000+15000+13000+30000+2000+17000+15000+13000+8000080+4000++3000060+
22-222
54321876543921d d y y y y y x x x x x x x x x ω
)(.])([. 这里助研x 1,助教x 2和职工x 9的工资增长率为6%，其它人员的工资增长率
《管理运筹学》（第二版）课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0≥i b ，决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示：
课程学习 《管理运筹学基础》 判断正误 线性规划问题的一般模型中不能出现等式约束。 正确答案：说法错误 2.在线性规划模型的标准型中,b j（j=1，2，…m）一定是非负的。正确答案：说法正确 解答参考： 3. 判断正误 线性规划问题的基本解一定是基本可行解 正确答案：说法错误 解答参考： 5. 判断正误 同一问题的线性规划模型是唯一的。 正确答案：说法错误 解答参考： 12.第一个顶点和最后一个顶点相同的闭链叫回路。 正确答案：说法错误 解答参考： 14. 判断正误
Djisktra算法可求出非负赋权图中一顶点到任一顶点的最短距离。 正确答案：说法正确 解答参考： 15.简述编制统筹图的基本原则。 参考答案：统筹图是有向图，箭头一律向右；统筹图只有一个起始点。一个终点，没有缺口；两个节点之间只能有一个作业相连；统筹图中不能出现闭合回路。 17.简述西北角法、最小元素法、差值法确定运输问题初始基本可行解的过程并指出那种方法得出的解较优。 参考答案：西北角法：按照地图中的上北下南，左西右东的判断，对调运表中的最西北角上的空格优先满足最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。最小元素法：对调运表中的最小运价对应的空格优先没醉最大供应，之后划去一行或一列，重复这种做法，直至得到初始可行解。差值法：在运价表中，计算各行和各列的最小运价和次最小运价之差，选出最大者，它所在某行或某列中的最小运价对应的空格优先满足最大供应，重复这种做法，直至得到初始可行解。一般来讲，用差值法求出的初始可行解最接近最优解，也就是最优的。 2. 用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能找出最优解。 正确答案：说法正确 单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数的值增加更快。 正确答案：说法错误 解答参考： 6.若原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。 正确答案：说法正确 解答参考： 8.表上作业法中，任何一种确定初始基本可行解的方法都必须保证有（m + n -1）个变量。正确答案：说法正确 解答参考： 9.用分枝定界法求解一个极大化整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界 正确答案：说法正确
管理运筹学 ——管理科学方法谢家平 第一章 第一章 1. 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量（Decision Variable）是决策问题待 定的量值，取值一般为非负；约束条件（Constraint Conditions）是指决策变量取值时受到的各种资源条件的限制， 保障决策方案的可行性；目标函数（Objective Function）是决策者希望实现的目标，为决策变量的线性函数表达式， 有的目标要实现极大值，有的则要求极小值。 2.（1）设立决策变量； （2）确定极值化的单一线性目标函数； （3）线性的约束条件：考虑到能力制约，保证能力需求量不能突破有效供给量； （4）非负约束。 3.（1）唯一最优解：只有一个最优点 （2）多重最优解：无穷多个最优解 （3）无界解：可行域无界，目标值无限增大 （4）没有可行解：线性规划问题的可行域是空集 无界解和没有可行解时，可能是建模时有错。 4. 线性规划的标准形式为：目标函数极大化，约束条件为等式，右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 5. 可行解：满足约束条件AX =b,X≥0的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 6. 计算步骤： 第一步，确定初始基可行解。 第二步，最优性检验与解的判别。 第三步，进行基变换。 第四步，进行函数迭代。 判断方式： 唯一最优解：所有非基变量的检验数为负数，即σj< 0 无穷多最优解：若所有非基变量的检验数σj≤ 0 ，且存在某个非基变量xNk 的检验数σk= 0 ，让其进基，目标函数
练习4.9 连续投资问题 某公司现有资金10万元,拟在今后五年考虑用于下列项目的投资: 项目A:从第一年到第四年每年年初需要投资,并于次年收回本利115%,但要求第一年投资最低金额为4万元,第二.三.四年不限. 项目B:第三年初需要投资,到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为5万元. 项目C:第二年初需要投资,到第五年末能收回本利140%,但规定其投资金额或为2万元,或为4万元,或为6万元,或为8万元. 项目D:五年每年年初都可购买公债,于当年末归还,并获利6%,此项目投资金额不限. 试问该公司应图和确定这些项目的每年投资金额,使到第五年末拥有最大的资金收益. (1) x 为项目各年月初投入向量。 (2) ij x 为 i 种项目j 年的月初的投入。 (3) 向量c 中的元素 ij c 为i 年末j 种项目收回本例的百分比。 (4) 矩阵A 中元素 ij a 为约束条件中每个变量ij x 的系数。 (5) Z 为第5年末能拥有的资金本利最大总额。 因此目标函数为 4325max 1.15 1.28 1.40 1.06A B C D Z x x x x =+++ 束条件应是每年年初的投资额应等于该投资者年初所拥有的资金. 第1年年初该投资者拥有10万元资金,故有 11100000A D x x +=. 第2年年初该投资者手中拥有资金只有()116%D x +,故有 22211.06A C D D x x x x ++=. 第3年年初该投资者拥有资金为从D 项目收回的本金: 21.06D x ,及从项目A 中第1年投资收回的本金: 11.15A x ,故有 333121.15 1.06A B D A D x x x x x ++=+ 同理第4年、第5年有约束为 44231.15 1.06A D A D x x x x +=+, 5341.15 1.06D A D x x x =+
习题参考答案 习题一 1．设选用第1种、第2种、第3种、第4种、第5种饲料的量分别为12345,,,,x x x x x 。 Min 543218.03.07.04.02.0x x x x x Z ++++= 1234512345 1234512345326187000.50.220.530..0.50.220.8100,,,,0 x x x x x x x x x x s t x x x x x x x x x x ++++≥??++++≥?? ++++≥??≥? 2．设x ij 为生产第i 种食品所使用的第j 种原料数，i ＝1，2，3分别代表甲、乙、丙，j ＝1，2，3分别代表A 、B 、C 。其数学模型为： Max Z =) (0.1)(5.1)(2)(95.1)(45.2)(9.2332313322212312111333231232221131211x x x x x x x x x x x x x x x x x x ++?-++?-++?-++?+++?+++? s.t . ) 3,2,1,3,2,1(,05 .06 .015 .02 .06 .012002500200033 323133 23 222123 23 222121 13 121113 13 121111 332313322212312111==≥≤++≤++≥++≤++≥++≤++≤++≤++j i x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ij 3．将下列线性规划问题化为标准形式 （1）引入剩余变量1s ，松弛变量2 s
实验概述：实验二、灵敏度分析（操作型） 【实验目的及要求】 1、进一步掌握管理运筹学、LINDO和LINGO软件的基本入门知识，学习使用管理运筹学、LINDO和LINGO软件对线性规划问题进行灵敏度分析。 2、熟练掌握用单纯形法求解线性规划问题。 【实验原理】 单纯形法迭代原理及其基本步骤 【实验环境】（使用的软件） 管理运筹学软件、LINDO软件，信息中心6机房计算机 实验内容： 【实验方案设计】 1、分别打开管理运筹学、LIND软件； 2、在打开的软件中输入课本例题和习题数据，对线性规划问题进行灵敏度分析； 3、运行实验并保存实验结果。 【实验过程】 使用管理运筹学、LINDO软件分别对线性规划问题进行灵敏度分析。 1、使用管理运筹学软件对线性规划问题进行灵敏度分析： （1）打开管理运筹学软件，选择“线性规划”，单击“新建”菜单，输入P59-例题2.6.1的变量个数、约束条件个数并选择目标函数，点击“确定”。在目标函数中输入价值系数，再输入变量的约束条件数据，然后选择变量的正、负、无。选择“解决”得到线性规划结果，保存文件于指定文件夹。
（2）将例2.6.1中的右端向量b=(2 1)T变为b1=(-2 1)T，其他数据不变。 （3）在“线性规划”界面中，单击“新建”菜单，输入P77-习题20的变量个数、约束条件个数并选择目标函数，点击“确定”。在目标函数中输入价值系数，再输入变量的约束条件数据，然后选择变量的正、负、无。选择“解决”得到线性规划结果，保存文件于指定文件夹。 （4）将P77-习题20中的价值系数C1由1变为（-5/4）；C1由1变为（-5/4），C3由1变为2；b由(5 3)T变为b1=(-2 1)T；b=(5 3)T变为b1=(2 3)T。
管理运筹学第二版课后 习题参考答案 Document number【980KGB-6898YT-769T8CB-246UT-18GG08】
《管理运筹学》（第二版）课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0 i b ，决策变量满足非负性。
如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 5．用表格单纯形法求解如下线性规划。 . ??? ??≥≤++≤++0,,862383 21321321x x x x x x x x x 解：标准化 32124max x x x Z ++= . ?? ? ??≥=+++=+++0,,,,862385432153 214 321x x x x x x x x x x x x x 列出单纯形表
《管理运筹学》(第二版)课后习题参考答案 第１章 线性规划（复习思考题） 1.什么是线性规划？线性规划的三要素是什么？ 答：线性规划(Lin ｅar Programming ，LP ）是运筹学中最成熟的一个分支,并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量是决策问题待定的量值,取值一般为非负;约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值，有的则要求极小值。 2.求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误? 答：(1）唯一最优解:只有一个最优点； （2）多重最优解：无穷多个最优解; (３)无界解:可行域无界，目标值无限增大； （4)没有可行解:线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么? 答：线性规划的标准型是:目标函数极大化，约束条件为等式，右端常数项0≥i b ,决策变量满足非负性。 如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量;剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值,出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基,称为可行基。 最优解：使目标函数最优的可行解,称为最优解。 最优基:最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示:
最新管理运筹学(第二版)课后习题参考答案 第1章 线性规划（复习思考题） 1．什么是线性规划？线性规划的三要素是什么？ 答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？ 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？ 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0≥i b ，决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示： 5．用表格单纯形法求解如下线性规划。
管理运筹学课程 实验报告 实验名称：造纸厂目标规划问题 实验者：普丁玲 实验日期：2012年5月21日 专业年级：10级工程管理 指导教师：许娟
目的与要求实验目的： 通过实验掌握以及实际问题建立线性规划模型的方法，并熟练运用运筹学软件求解线性规划问题，以及根据求解结果进行灵敏度分析。 实验要求： （1）根据所给出的实际问题，建立其相应的数学模型，并利用软件进行求解。 （2）通过对求解结果的分析研究，回答相应的问题。 背景资料某造纸厂成产一般类型纸张的利润为300元/吨，每吨纸产生的工业废水的处理费用为30元；生产某种特种纸张的利润为500元/吨，每吨特种纸产生的工业废水的处理费用为40元。该纸张造纸厂近期目标如下： 目标1：纸张利润不少于15万元； 目标2：工业废水的处理费用不超过1万元。 （1）设目标1的优先权为p1,目标2的优先权为p2，建立目标规划模型并用图解法求解。 （2）若目标2的优先权为p1,建立目标规划模型并求解，所得的解是否与（1）中的相同？ （3）若目标2的罚数权重为5，目标1的罚数权重为2，建立目标规划模型求解
数学模型 求解结果step 1 目标函数值为: 0 变量解相差值 ------- -------- -------- x1 0 0 x2 300 0 d1- 0 1 d1+ 0 0 d2- 0 0 d2+ 12000 0
step 2 目标函数值为: 12000 变量解相差值 ------- -------- -------- x1 0 6 x2 300 0 d1- 0 0 d1+ 0 .08 d2- 0 1 d2+ 12000 0 step 1 目标函数值为: 0 变量解相差值 ------- -------- -------- x1 0 0 x2 0 0 d1- 150000 0 d1+ 0 0 d2- 0 0 d2+ 0 1 step 2 目标函数值为: 150000 变量解相差值 ------- -------- -------- x1 0 75 x2 0 100 d1- 150000 0 d1+ 0 1 d2- 0 12.5 d2+ 0 0
第七章目标规划 §1 目标规划的提出 线性规划问题是讨论一个给定的线性目标函数在一组线性约束条件下的最大值或最小值问题。对于一个实际问题，管理科学者根据管理层决策目标的要求，首先确定一个目标函数以衡量不同决策的优劣，且根据实际问题中的资源、资金和环境等因素对决策的限制提出相应的约束条件以建立线性规划模型；然后用计算机软件求出最优方案并作灵敏度分析以供管理层决策之用。而在一些问题中，决策目标往往不只一个，且模型中有可能存在一些互相矛盾的约束条件的情况，用已有的线性规划的理论和方法无法解决这些问题。因此，1961年美国学者查恩斯（A.Charnes）和库柏（W.W.Coopor）提出了目标规划的概念与数学模型，以解决经济管理中的多目标决策问题。 我们将通过几个例子来说明在实际应用中线性规划存在一系列的局限性。 例1某厂生产A、B两种产品每件所需的劳动力分别为4个人工和6个人工，所需设备的单位台时均为1。已知该厂有10个单位机器台时提供制造这两种产品，并且至少能提供70个人工。又，A、B产品的利润，每件分别为300元和500元。试问：该厂各应生产多少件A、B产品，才能使其利润值最大？ 解设该厂能生产A、B产品的数量分别为 ,x x件，则有 12
12 1212max 30050010..4670 0, 1,2.j z x x x x s t x x x j =+?+≤?+≥??≥=? 图解法求解如下： 由上图可得，满足约束条件的可行解集为?，即机时约束和人工约束之间产生矛盾，因而该问题无解。但在实际中，该厂要增加利润，不可能不生产A 、B 两种产品，而由线性规划模型无法为其找到一个合适的方案。 例2 某厂为进行生产需采购A 、B 两种原材料，单价分别为70元/公斤和50元/公斤。现要求购买资金不超过5000元，总购买量不少于80公斤，而A 原材料不少于20公斤。问如何确定最好的采购方案（即花掉的资金最少，购买的总量最大）？ 解 这是一个含有两个目标的数学规划问题。设12,x x 分别为购买两种 原材料的公斤数，()112,f x x 为花掉的资金，()212,f x x 为购买的总量。建 立该问题的数学模型形式如下：
习题 4-1对每题结论进行判断，如果结论错误请改正。 （1）正偏差变量大于等于零，负偏差变量小于等于零。 （2）系统约束中最多含有一个正或负的偏差变量。 （3）目标约束一定是等式约束。 （4）一对正负偏差变量至少一个大于零。 （5）一对正负偏差变量至少一个等于零。 （6）要求至少到达目标值的目标函数是maxZ=d +。 （7）要求不超过目标值的目标函数是minZ= d +。 （8）超出目标的差值称为正偏差。 （9）未到达目标的差值称为负偏差。 4-2 现有一船舶的舱容为3万立方米、载重量为2万吨，准备装运每件均为1立方米的三种货物A 、B 、C ，三种货物的每件重量和单位运费收入见下表：考虑以下几个方面： 1、总运费收入不低于350万元；2、总货物重量不低于1.25万吨；3、A 货物运量恰好为0.5万吨；4、B 货物运量不少于0.2万吨；5、C 货物运量不少于0.2万吨。请建立目标规划模型。 4-3用图解法求解以下目标规划模型 ???????=≥=-++-=-++=-++++=+-+-+-+-- -+3,2,1;0,,,6 226210min 21332122211121332211i d d x x d d x x d d x x d d x x d p d p d p z i i 4-4已知目标规划问题 ???????=≥=-+-=-+-≤++=+-+-+---+2,1;0,,,632226)(min 212221112112 2111i d d x x d d x x d d x x x d p d d p z i i 试用单纯形法求其满意解，若有多个满意解求出其中两个。
习题 6-1. 考虑下面的网络图，箭头上的数字代表相连两个节点之间的距离。 （1）用动态规划找出从节点1到节点10的最短路。 （2）从节点4到节点10的最短路呢？ 6-2. 从北京到上海的包机的剩余装载能力为2000kg ，某一运输公司现有4种货物需要从北京运输到上海。每种货物的单位、单位重量和单位运输费用如下表所示。 （1）用动态规划找出包机应该运输的每种货物的单位数。 （2）假设包机同意装载另一批货物，剩余装载能力降为1800kg ，计算结果会怎样变化？ 6-3. 假定有一个3阶段的过程，每一阶段的产量是需要做出决策的函数。使用数学符号，问题表述如下： Max ()()()332211d r d r d r ++ s.t. 1000321≤++d d d 每个阶段的决策变量和相应的返回值如下所示：
6-4. 某制造公司为一家汽车工厂提供发动机的部件，以下是3个月的生产计划的数据。 量是10单位，并且生产批量是10的倍数（例如，10,20或者30单位）。 6-5. 某物流公司雇佣了8名新员工，现决定如何把他们分配到4项作业上。公司给出了以下每项作业分配不同的作业人员的估计利润表。 (1) 用动态规划决定每项作业应该分配的新员工数目。 (2) 如果公司只雇佣了6名新员工，应该把这些员工分配给哪些作业？ 6-6. 一个锯木厂采购了一批20ft 长的原木，想要把这些原木切成更短的原木，然后把切后的小原木卖给制造公司。制造公司已经订购了一批4种尺寸的原木：l 1=3ft ，l 2=7ft ，l 3=11ft ，l 4=16ft 。锯木厂现在有2000个长度为20ft 的原木的库存，并希望有选择地裁截原木以最大化利润。假定锯木厂的订单是无限的，唯一的问题就是确定把现有原木裁成的类型以最大化利润。原木的利润如下表所示： 任何裁截类型的长度限制如下： 201173321≤++d d d 其中，i d 是长度为i l 的类型的裁截数目，4,3,2,1=i . （1）为这个问题建立动态规划模型，并使用模型解决问题。你需要设立哪些变量？状态变量有哪些？ （2）简要介绍如果总的长度l 被截成l 1，l 2，……l N 这样N 中长度的话，如果扩展现有模型以找到最优解？ 6-7. 一家港口公司建立了良好的管理训练计划，希望每一个员工完成一个4阶段的作业。但是在训练计划的每个阶段，员工都会被分配一系列艰难的作业。以下是训练计划的每个阶段员工可能被分派的作业和任务估计完成时间。 次级阶段的作业取决于其先前的作业。例如，在阶段1接受作业A 的员工在阶段2只能接受作业F 或者作业G ——即每一项作业都存在优先关系。
盛年不重来，一日难再晨。及时宜自勉，岁月不待人。 第七章目标规划 §1 目标规划的提出 线性规划问题是讨论一个给定的线性目标函数在一组线性约束条件下的最大值或最小值问题。对于一个实际问题，管理科学者根据管理层决策目标的要求，首先确定一个目标函数以衡量不同决策的优劣，且根据实际问题中的资源、资金和环境等因素对决策的限制提出相应的约束条件以建立线性规划模型；然后用计算机软件求出最优方案并作灵敏度分析以供管理层决策之用。而在一些问题中，决策目标往往不只一个，且模型中有可能存在一些互相矛盾的约束条件的情况，用已有的线性规划的理论和方法无法解决这些问题。因此，1961年美国学者查恩斯（A.Charnes）和库柏（W.W.Coopor）提出了目标规划的概念与数学模型，以解决经济管理中的多目标决策问题。 我们将通过几个例子来说明在实际应用中线性规划存在一系列的局限性。 例1某厂生产A、B两种产品每件所需的劳动力分别为4个人工和6个人工，所需设备的单位台时均为1。已知该厂有10个单位机器台时提供制造这两种产品，并且至少能提供70个人工。又，A、B产品的利润，每件分别为300元和500元。试问：该厂各应生产多少件A、B产品，才能使其利润值最大？ 解设该厂能生产A、B产品的数量分别为 ,x x件，则有 12
12 12 12 max300500 10 ..4670 0,1,2. j z x x x x s t x x x j =+ ?+≤ ? +≥ ? ?≥= ? 图解法求解如下： 由上图可得，满足约束条件的可行解集为?，即机时约束和人工约束之间产生矛盾，因而该问题无解。但在实际中，该厂要增加利润，不可能不生产A、B两种产品，而由线性规划模型无法为其找到一个合适的方案。 例2某厂为进行生产需采购A、B两种原材料，单价分别为70元/公斤和50元/公斤。现要求购买资金不超过5000元，总购买量不少于80公斤，而A原材料不少于20公斤。问如何确定最好的采购方案（即花掉的资金最少，购买的总量最大）？ 解这是一个含有两个目标的数学规划问题。设 12 ,x x分别为购买两种 原材料的公斤数，() 112 , f x x为花掉的资金，() 212 , f x x为购买的总量。建立该问题的数学模型形式如下：
《管理运筹学》(第二版)课后习题参考标准答案 -CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN
《管理运筹学》（第二版）课后习题参考答案 第1章线性规划（复习思考题） 1．什么是线性规划线性规划的三要素是什么 答：线性规划（Linear Programming，LP）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。 当无界解和没有可行解时，可能是建模时有错。 3．什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么 答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项 b，决策变量满足非负性。 ≥ i 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。 答：可行解：满足约束条件0 AX，的解，称为可行解。 b ≥ =X 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 它们的相互关系如右图所示：