求解整数规划常用的方法有分枝定界法和割平面法

1、 求解整数规划常用的方法有分枝定界法和割平面求解整数规划常用的方法有分枝定界法和割平面 法。法。 这两种方法的共同特点：通过增加附加约束，使这两种方法的共同特点：通过增加附加约束，使 整数最优解最终成为线性规划的一个顶点，于是整整数最优解最终成为线性规划的一个顶点，于是整 个问题就可使用单纯形法找到这个整数最优解；它个问题就可使用单纯形法找到这个整数最优解；它 们的相异之处是附加约束条件的选取原则及方法不们的相异之处是附加约束条件的选取原则及方法不 同。同。 上周内容回顾上周内容回顾 基本思想基本思想 割平面法的基础仍然是用解线性规划的方法去解割平面法的基础仍然是用解线性规划的方法去解 整数规

2、划问题。首先不考虑变量为整数这一条件，但整数规划问题。首先不考虑变量为整数这一条件，但 增加线性约束条件（几何术语，称为增加线性约束条件（几何术语，称为割平面割平面），使得），使得 原可行解域中切掉一部分，这部分只包含非整数解，原可行解域中切掉一部分，这部分只包含非整数解， 但没切割掉任何整数可行解。切除的结果使整数解可但没切割掉任何整数可行解。切除的结果使整数解可 能成为顶点。能成为顶点。 关键：关键：如何找到割平面约束方程如何找到割平面约束方程，使切割后最终，使切割后最终 得到这样的可行解域，它的一个整数坐标的顶点恰好得到这样的可行解域，它的一个整数坐标的顶点恰好 是问题的最优解。是问题的

3、最优解。 整数线性规划模型的求解整数线性规划模型的求解割平面法割平面法 （1）由单纯形最终表得到决策变量非整数解方程，设）由单纯形最终表得到决策变量非整数解方程，设 为为 1 1i k k k i bxax 其中其中bi是基变量的非整数解。是基变量的非整数解。 （2）将）将aik和和bi分解为整数分解为整数n和正真分数和正真分数f 两部分之和两部分之和 2 biniiikikik fnb,fna 将（将（2）代入）代入(1)中中,然后将整数置于方程左边，分然后将整数置于方程左边，分 数置于方程右变，即数置于方程右变，即 kk kikbibikiki xffnxnx0 (3)得割平面方程得割平面

4、方程 k kikbi xff0 寻找割平面方程寻找割平面方程 基本思想基本思想 通过分枝枚举来寻找最优解。首先不考虑对变通过分枝枚举来寻找最优解。首先不考虑对变 量的整数要求，求解相应的线性规划模型，如求得量的整数要求，求解相应的线性规划模型，如求得 最优解不符合整数要求，则把原模型分解为两部分，最优解不符合整数要求，则把原模型分解为两部分， 每一部分都增加新的约束条件以减少相应线性规划每一部分都增加新的约束条件以减少相应线性规划 模型的可行域。通过不断分解，逐步逼近满足要求模型的可行域。通过不断分解，逐步逼近满足要求 的整数最优解，在这个过程中包括了的整数最优解，在这个过程中包括了“分枝分枝

5、”和和“定定 界界”两个关键步骤。两个关键步骤。 整数线性规划模型的求解整数线性规划模型的求解分枝定界法分枝定界法 （1）求解相应的线性规划模型，确定初始上、下界。）求解相应的线性规划模型，确定初始上、下界。 （a）lp无解，则无解，则ip无解，停止计算。无解，停止计算。 （b）lp的最优解满足整数要求，即为的最优解满足整数要求，即为ip的最优解，的最优解， 计算完毕。计算完毕。 （c） lp的最优解中有非整数分量，其目标函数值的最优解中有非整数分量，其目标函数值 是是 ip的初始上界。的初始上界。 （2）分枝并求解）分枝并求解 在非整数最优解中任选一个不满足整数约束条件在非整数最优解中任选一

6、个不满足整数约束条件 的变量的变量xj=bj，以，以bj表示不大于表示不大于bj的最大整数，构造两的最大整数，构造两 个约束条件个约束条件 xjbj，和，和xjbj+1 将这两个约束条件分别加到将这两个约束条件分别加到lp中，构成两个新的线性中，构成两个新的线性 规划分支，求解它们。规划分支，求解它们。 分枝定界法步骤：分枝定界法步骤： （3）定界）定界 上界：以每个后继问题为一分支，标明求解的结果，上界：以每个后继问题为一分支，标明求解的结果， 与其他问题解的结果比较，找出目标函数值最大者作与其他问题解的结果比较，找出目标函数值最大者作 为为ip新的上界新的上界z。 下界：从已符合整数条件的

7、分支中，找出目标函数最下界：从已符合整数条件的分支中，找出目标函数最 大者作为新的下界，若无符合条件者，则取大者作为新的下界，若无符合条件者，则取z =0。 （4）比较和剪枝）比较和剪枝 （a）该枝无可行解；）该枝无可行解； （b）该枝已得到整数最优解；）该枝已得到整数最优解； （c）该枝得到非整数最优解，且目标函数值小于）该枝得到非整数最优解，且目标函数值小于 z。 在求解的各分支的线性规划中，若其值大于在求解的各分支的线性规划中，若其值大于 z，即，即z* z但不符合整数条件则返回（但不符合整数条件则返回（2）继续分）继续分 枝直到枝直到z=z*= z。 有有n项任务，恰好项任务，恰好n个

8、人承担，第个人承担，第i 人完成第人完成第j 项任务项任务 的花费的花费(时间或费用等时间或费用等)为为cij，如何分派使总花费最省？如何分派使总花费最省？ 第第j项工作由一项工作由一 个人做个人做 第第i人做一项工人做一项工 作作 n i n j ijij xczmin 11 n),1,jn;,1,(i10 1 1 n), 1( 1 1 1 或或 ij n j ij n i ij x )n,i (x jx 0 1 ij x 分派第分派第i人做第人做第j项工作项工作 不分派第不分派第i人做第人做第j项工作项工作 8.6 指派问题（指派问题（assignment problem） 人员人员 工作

9、工作abcd 甲甲917167 乙乙1271416 丙丙8171417 丁丁79119 引入决策变量引入决策变量xij, 项项工工作作人人做做第第表表示示不不分分派派第第 项项工工作作人人做做第第表表示示分分派派第第 ji ji xij 0 1 【例【例8-78-7】有有4 4个工人，要分别指派他们完成个工人，要分别指派他们完成4 4项不同的项不同的 工作，每人做各项工作所消耗的时间如下表所示，问工作，每人做各项工作所消耗的时间如下表所示，问 应如何指派工作，才能使总的消耗时间为最少？应如何指派工作，才能使总的消耗时间为最少？ minz=9x11+17x12+16x13+7x14+12x21+

10、7x22+14x23+16x24+ 8x31+17x32+14x33+17x34+7x41 +9x42+11x43+9x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( a工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( b工作

11、只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( c工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( d工作只能一人干工作只能一人干) xij 为为0-1变量变量，i,j = 1,2,3,4 指派问题是指派问题是0-1规划问题。规划问题。 因每个人仅能承担一项任务，每项任务也只能分派因每个人仅能承担一项任务，每项任务也只能分派 给一个人，因此上述问题的线性规划模型也可写为：给一个人，因此上述问题的线性规划模型也可写为： 10 211 211 4 1 4 1 4 1 4 1 ,x m,jx m,ix . t . s xczmin ij i

12、ij j ij ij ijij 1000 0001 0100 0010 ij x 满足该约束条件的可满足该约束条件的可 行解可写成矩阵形式行解可写成矩阵形式 分派问题是线性规划，又是运输问题。分派问题是线性规划，又是运输问题。 定理：从定理：从(cij)矩阵的每行矩阵的每行(或每列或每列)减或加一个常数减或加一个常数 ui(vj)构成新矩阵构成新矩阵 ， ，则对应则对应 的的(xij) 最优解与原问题最优解与原问题(cij) 的最优解相同。的最优解相同。 jiijij vucc ij c ij c 41075 2763 3344 4663 -4 -2 -3 -3 0631 0541 0011

13、1330 -1 0621 0531 0001 1320 (cij) 例如：例如： (cij) 利用这一性质，可以使原系数矩阵利用这一性质，可以使原系数矩阵(cij)变换成含有变换成含有 很多很多0元素的新系数矩阵元素的新系数矩阵 ，而最优解保持不变。，而最优解保持不变。 ij c 匈牙利法是针对匈牙利法是针对目标要求极小化问题目标要求极小化问题提出的提出的 基本原理：为了实现目标极小，在系数矩阵基本原理：为了实现目标极小，在系数矩阵 元素元素c cij ij 0 0条件下，如果能使矩阵具有一组处于条件下，如果能使矩阵具有一组处于 不同行不同列的零元素不同行不同列的零元素c cij ij 0 0

14、，画上圈符号，画上圈符号 “”，表示对应该元素的决策变量，表示对应该元素的决策变量x xij ij=1 =1，未画，未画 圈元素对应的决策变量圈元素对应的决策变量x xij ij 0 0，那么目标的数值，那么目标的数值z z 0 0为最小，这样的组合解为最小，这样的组合解x x就是最优解。所以匈就是最优解。所以匈 牙利法又称画圈法。牙利法又称画圈法。 画圈法的关键是如何实现系数矩阵具有一组画圈法的关键是如何实现系数矩阵具有一组 处于处于不同行又不同列的不同行又不同列的0 0元素元素（独立零独立零），并保），并保 证所画的圈的个数等于矩阵的阶数。证所画的圈的个数等于矩阵的阶数。 【例【例8-88

15、-8】用匈牙利算法求解下面的指派问题，使得用匈牙利算法求解下面的指派问题，使得 总的费用最小。总的费用最小。 41075 2763 3344 4663 匈牙利算法的步骤：匈牙利算法的步骤： （1）变换系数矩阵，使其每行每列都出现）变换系数矩阵，使其每行每列都出现0元素。首元素。首 先每行减去该行最小数，再每列减去该列最小数。先每行减去该行最小数，再每列减去该列最小数。 (2)进行试分派，寻求最优解。进行试分派，寻求最优解。 经第（经第（1）步变换后，系数矩阵每行每列都已有了）步变换后，系数矩阵每行每列都已有了 0元素，但需找出元素，但需找出n个独立的个独立的0元素，为此，按下列的元素，为此，按

16、下列的 步骤进行。步骤进行。 41075 2763 3344 4663 -4 -2 -3 -3 0631 0541 0011 1330 -1 0621 0531 0001 1320 从只有一个从只有一个0元素的行（列）的元素的行（列）的0元素开始，给这元素开始，给这 个个0元素加圈，即作，这表示对这行所代表的人元素加圈，即作，这表示对这行所代表的人 ，只，只 有一种任务可分派。然后划去所在列（行）的其它有一种任务可分派。然后划去所在列（行）的其它0 元素元素 ，记作，记作 ，这表示这列所代表的任务已分派完，这表示这列所代表的任务已分派完， 不必再考虑别人了。不必再考虑别人了。 给只有一个给只有

17、一个0元素的列元素的列(行行)的元素加圈，记作；的元素加圈，记作； 然后划去所在的行的其它然后划去所在的行的其它0元素，即作元素，即作 。 0621 0531 0001 1320 0621 0531 0001 1320 0621 0531 0001 1320 若仍有没有圈出或划掉的若仍有没有圈出或划掉的0元素，且同行（列）的元素，且同行（列）的 0元素至少有元素至少有2个，则找出个，则找出0元素的闭回路，任选一个元素的闭回路，任选一个0 元素加圈，破闭回路，直到所有元素加圈，破闭回路，直到所有0元素都已圈出和划掉元素都已圈出和划掉 为止。列如：为止。列如： 反复进行、反复进行、 两步，直到所有

18、两步，直到所有0元素都被圈出元素都被圈出 或划掉为止。转第步。或划掉为止。转第步。 636 40089 57510 80032 9025 若元素的数目等于矩阵的阶数，那末，这分派若元素的数目等于矩阵的阶数，那末，这分派 问题的最优解已经得到，否则转第（问题的最优解已经得到，否则转第（3）步。）步。 （3）作最少的直线覆盖所有的）作最少的直线覆盖所有的0元素，以确定该系数元素，以确定该系数 矩阵能找到最多的独立矩阵能找到最多的独立0元素。为此按以下步骤进行：元素。为此按以下步骤进行： 对没有的行打对没有的行打号；号； 对已打对已打的行中所有的行中所有0元素所对应的列打元素所对应的列打号；号； 再

19、对打有再对打有的列中元素所对应的行打的列中元素所对应的行打号；号； 重复、重复、 ，直到得不出新的打，直到得不出新的打号的行、列号的行、列 为止。为止。 对没有打对没有打号的行画一横线，有打号的行画一横线，有打号的列画一号的列画一 纵线，这就得到覆盖所有的纵线，这就得到覆盖所有的0元素的最少直线数。元素的最少直线数。 做最少直线做最少直线 （4） 在未被直线覆盖的部分中找出最小元素，在未被直线覆盖的部分中找出最小元素， 然后在打然后在打行各元素中都减去这最小元素，而在打行各元素中都减去这最小元素，而在打 列的各元素都加上这最小元素。这样得到新的系数列的各元素都加上这最小元素。这样得到新的系数

20、矩阵（它的最优解和原问题相同）。矩阵（它的最优解和原问题相同）。 0510 0420 1001 2320 0621 0531 0001 1320 0621 0531 0001 1320 0510 0420 1001 2320 0510 0420 1001 2320 0510 0420 1001 2320 0510 0420 1001 2320 0510 0420 1001 2320 0400 0310 2002 2210 调整后，再试指派调整后，再试指派 0400 0310 2002 2210 0400 0310 2002 2210 0400 0310 2002 2210 0400 0310

21、2002 2210 指派结果：指派结果： 第第1个人做第个人做第3个工作；第个工作；第2个人做第个人做第1个工作个工作 第第3个人做第个人做第2个工作；第个工作；第4个人做第个人做第4个工作个工作 调整后，调整后， 再试指派再试指派 0400 0310 2002 2210 【例【例8-9】6个人完成个人完成4项任务，由于个人的技术专长项任务，由于个人的技术专长 不同，他们完成不同，他们完成4项任务所获得的收益如表所示，且项任务所获得的收益如表所示，且 规定每人只能做一项工作，一项工作只能由一个人规定每人只能做一项工作，一项工作只能由一个人 来完成，试求总收益最大的分配方案。来完成，试求总收益最

22、大的分配方案。 abcd 13545 26768 389810 41010911 512111012 613121113 运用匈牙利法求解分派问题有以下三个条件：运用匈牙利法求解分派问题有以下三个条件： （1）目标函数为求极小值型；）目标函数为求极小值型； （2）目标系数矩阵为方阵；）目标系数矩阵为方阵； （3）目标系数矩阵）目标系数矩阵 0 nn ij cc 对于不属于上述三个条件的分派问题，可以先将对于不属于上述三个条件的分派问题，可以先将 条件进行转化，再求解。条件进行转化，再求解。 abcdef 1354500 2676800 38981000 4101091100 512111012

23、00 61312111300 非平衡的指派问题，设两项虚任务，其收益为非平衡的指派问题，设两项虚任务，其收益为0， 化为平衡指派问题。化为平衡指派问题。 用匈牙利法求解用匈牙利法求解 354500 676800 8981000 () 101091100 1211101200 1312111300 ij c 求最大值问题转化为求最小值问题，利用下式求最大值问题转化为求最小值问题，利用下式 zminzmax 即即 ij n i n j ij xczmin 11 354500 676800 8981000 () 101091100 1211101200 1312111300 ij c -(-5) -

24、(-8) -(-10) -(-11) -(-12) -(-13) 201055 212088 21201010 11201111 01201212 01201313 200000 211033 211055 111066 011077 011088 200000 211033 211055 111066 011077 011088 200000 211033 211055 111066 011077 011088 200000 211033 211055 111066 011077 011088 300100 200022 200044 100055 000066 000077 300100

25、200022 200044 100055 000066 000077 522300 200022 200022 100033 000044 000055 300100 200022 200044 100055 000066 000077 最优解：第最优解：第3个人做个人做d工作工作 第第4个人做个人做c工作工作 第第5个人做个人做b工作工作 第第6个人做个人做a工作工作 最大收益为：最大收益为： 10+9+11+13=43 第第9 9章章 目标规划目标规划 9.1 9.1 目标规划问题的提出及其数学模型目标规划问题的提出及其数学模型 9.2 9.2 线性目标规划的基本概念及其数学模线性目标规划

26、的基本概念及其数学模 型型 9.3 9.3 目标规划的图解法目标规划的图解法 9.4 9.4 目标规划的单纯形法目标规划的单纯形法 9.5 9.5 目标规划应用举例目标规划应用举例 目标规划问题的提出目标规划问题的提出 （1 1）线性规划只研究在满足一定条件下）线性规划只研究在满足一定条件下, ,单一目标函单一目标函 数取得最优解数取得最优解, ,而在企业管理中而在企业管理中, ,经常遇到多目标决经常遇到多目标决 策问题策问题, ,如拟订生产计划时如拟订生产计划时, ,不仅考虑总产值不仅考虑总产值, ,同时要同时要 考虑利润考虑利润, ,产品质量和设备利用率等。这些指标之间产品质量和设备利用率

27、等。这些指标之间 的重要程度的重要程度( (即优先顺序即优先顺序) )也不相同也不相同, ,有些目标之间往有些目标之间往 往相互发生矛盾；往相互发生矛盾； （2 2）线性规划最优解存在的前提条件是可行域为非）线性规划最优解存在的前提条件是可行域为非 空集空集, ,否则否则, ,线性规划无解。然而实际问题中线性规划无解。然而实际问题中, ,有时可有时可 能出现资源条件满足不了管理目标的要求的情况能出现资源条件满足不了管理目标的要求的情况, ,此此 时时, ,仅做无解的结论是没有意义的；仅做无解的结论是没有意义的； 9.1 9.1 目标规划问题的提出及其数学模型目标规划问题的提出及其数学模型 （3

28、 3）线性规划问题中的约束条件是不分主次）线性规划问题中的约束条件是不分主次, ,同等对待同等对待 的的, ,是一律要满足的是一律要满足的“硬约束硬约束”,”,而在实际问题中而在实际问题中, ,多多 个目标和多个约束条件并不一定是同等重要的个目标和多个约束条件并不一定是同等重要的, ,而是而是 有轻重缓急和主次之分的；有轻重缓急和主次之分的； （4 4）线性规划的最优解可以说是绝对意义下的最优）线性规划的最优解可以说是绝对意义下的最优, , 但很多实际只需但很多实际只需( (或只能或只能) )找出满意解就可以。找出满意解就可以。 目标规划是解决多目标决策问题的方法之一。目标规划是解决多目标决策

29、问题的方法之一。 是针对线性规划单目标、单一最优解的局限性以及是针对线性规划单目标、单一最优解的局限性以及 刚性约束而发展起来的。刚性约束而发展起来的。 【例题例题】某公司分厂用一条生产线生产两种产品某公司分厂用一条生产线生产两种产品a a 和和b b，每周生产线运行时间为每周生产线运行时间为6060小时，生产一台小时，生产一台a a产产 品需要品需要4 4小时，生产一台小时，生产一台b b产品需要产品需要6 6小时。根据市小时。根据市 场预测场预测,a,a、b b产品平均销售量分别为每周产品平均销售量分别为每周9 9、8 8台台, ,它它 们销售利润分别为们销售利润分别为1212、1818万

30、元。在制定生产计划时万元。在制定生产计划时 经理考虑下述经理考虑下述4 4项目标：项目标： 首先，产量不能超过市场预测的销售量；首先，产量不能超过市场预测的销售量； 其次，工人加班时间最少；其次，工人加班时间最少； 第三，希望总利润最大；第三，希望总利润最大； 最后，要尽可能满足市场需求最后，要尽可能满足市场需求, ,当不能满足时当不能满足时, ,市场市场 认为认为b b产品的重要性是产品的重要性是a a产品的产品的2 2倍。倍。 建立这个问题的数学模型建立这个问题的数学模型 若把总利润最大看作目标，而把产量不能超过若把总利润最大看作目标，而把产量不能超过 市场预测的销售量、工人加班时间最少和

31、要尽可能市场预测的销售量、工人加班时间最少和要尽可能 满足市场需求的目标看作约束，则可建立一个单目满足市场需求的目标看作约束，则可建立一个单目 标线性规划模型。标线性规划模型。 12 12 1 2 12 max1218 4660 9a . 8b ,0 zxx xx x st x xx （设设备备台台时时） （ 产产品品销销售售量量） （ 产产品品销销售售量量） 设决策变量设决策变量 x x1 1，x x2 2 分别为产品 分别为产品a a，b b的产量的产量 容易求得上述线性规划的最优解为容易求得上述线性规划的最优解为(9,4)(9,4)t t 到到 (3,8)(3,8)t t 所在线段上的点

32、，最优目标值为所在线段上的点，最优目标值为z z* * = 180, = 180, 即可选方案有多种。即可选方案有多种。 在实际上，这个结果并非完全符合决策者的要在实际上，这个结果并非完全符合决策者的要 求，它只实现了经理的第一、二、三条目标，而没求，它只实现了经理的第一、二、三条目标，而没 有达到最后的一个目标。有达到最后的一个目标。 第四个目标为第四个目标为: : x1 9，x2 8；要尽可能满足要尽可能满足 市场需求市场需求, , 当不能满足时当不能满足时, , 市场认为市场认为b b产品的重要产品的重要 性是性是a a产品的产品的2 2倍。倍。 第三个目标为第三个目标为: : 希望总利

33、润最大，要表示成希望总利润最大，要表示成 不等式需要找到一个目标下界，这里可以估计为不等式需要找到一个目标下界，这里可以估计为 252252（=12=12 9+189+18 8 8），于是有：），于是有：12x1 + 18x2 252； 第二个目标为第二个目标为: : 4x1 + 6x2 60 （工人加班时（工人加班时 间最少）；间最少）； 如果把第如果把第4 4个目标表示为不等式，仍设决策变量个目标表示为不等式，仍设决策变量 x x1 1，x x2 2 分别为产品 分别为产品a a，b b的产量，则的产量，则 第一个目标为第一个目标为: : x1 9 ，x2 8（产量不能超过（产量不能超过

34、市场预测的销售量）；市场预测的销售量）； 要实现全体目标是不可能的。要实现全体目标是不可能的。 线性目标规划和线性规划比较，具有下面的特点线性目标规划和线性规划比较，具有下面的特点 （1 1）线性规划只讨论单目标线性函数在一组线性约）线性规划只讨论单目标线性函数在一组线性约 束条件下的最优值问题，而目标规划能统筹兼顾处束条件下的最优值问题，而目标规划能统筹兼顾处 理实际问题中出现的多目标关系，求得切合实际的理实际问题中出现的多目标关系，求得切合实际的 最优解。最优解。 （2 2）线性规划是求最优解，而目标规划是求满意解。）线性规划是求最优解，而目标规划是求满意解。 （3 3）线性规划将约束条件

35、看出同等重要，而目标规）线性规划将约束条件看出同等重要，而目标规 划将依实际情况将约束条件主次有别地进行求解。划将依实际情况将约束条件主次有别地进行求解。 【例例9-3】某工厂生产某工厂生产甲甲、 乙乙两种产品，已知两种产品，已知 有关数据如下表：试求获利最大的生产方案有关数据如下表：试求获利最大的生产方案. 甲甲乙乙拥有量拥有量 原材料原材料(kg)2111 设备设备(k1)1210 利润利润/千元千元810 用图解法求得最优决策为用图解法求得最优决策为: x1*=4,x2*=3,z=62 解：设解：设x1，x2分别表示分别表示生产生产a、 b两种产品的生产量，两种产品的生产量， 则则数学模

36、型为：数学模型为： 0 102 112 108 21 21 21 21 x,x xx xx xxzmax 9.2 线性目标规划的基本概念及其数学模型线性目标规划的基本概念及其数学模型 实际上工厂正在作决策时要考虑市场等一系列实际上工厂正在作决策时要考虑市场等一系列 其他条件，如：其他条件，如： 1. 根据市场信息产品根据市场信息产品a的销售量有下降的趋势，故的销售量有下降的趋势，故 考虑产品考虑产品a的产量不大于产品的产量不大于产品b； 2. 超过计划供应的原材料时，需要高价采购，使超过计划供应的原材料时，需要高价采购，使 成本增加；成本增加； 3. 应尽可能充分利用设备，但不希望加班；应尽可

37、能充分利用设备，但不希望加班； 4. 应尽可能达到并超过计划利润指标应尽可能达到并超过计划利润指标56千千元。元。 产品决策时，为多目标决策。产品决策时，为多目标决策。 仍设决策变量仍设决策变量 x x1 1， x x2 2 分别为产品 分别为产品a a，b b的产的产 量，则该厂决策者考虑量，则该厂决策者考虑4 4个目标，用数学表达式表个目标，用数学表达式表 示为：示为： 12 12 12 12 0 211 210 81056 xx xx xx xx 下面引入与建立目标规划数学模型有关的概念下面引入与建立目标规划数学模型有关的概念 产品产品a的产量不大于产品的产量不大于产品b 不超过计划供应

38、的原材料不超过计划供应的原材料 充分利用设备充分利用设备 达到并超过计划利润指标达到并超过计划利润指标56元元 （1）目标值（理想值）目标值（理想值） 预先给定的某个目标函数的期望值，如：预先给定的某个目标函数的期望值，如： 右端值是对右端值是对 目标所赋予目标所赋予 的期望值的期望值 （2）正、负偏差量正、负偏差量 实际值与目标值之间的差异。实际值与目标值之间的差异。 设设x1,x2为决策变量，为决策变量，d+、d-为正、负偏差变量。为正、负偏差变量。 d+ ：实际值超过目标值部分；：实际值超过目标值部分； d-：实际值未达到目标值部分；：实际值未达到目标值部分； 恒有恒有d+ d-=0 5

39、6108 1121 ddxx 12 12 12 12 0 211 210 81056 xx xx xx xx 目标约束：目标约束：目标规划特有的，当目标规划特有的，当把约束右端项看作要把约束右端项看作要 努力追求的目标值，但允许发生正式负偏差，用在约努力追求的目标值，但允许发生正式负偏差，用在约 束中加入正负偏差变量来表示，于是称它们是软约束束中加入正负偏差变量来表示，于是称它们是软约束 （3）目标约束）目标约束和绝对约束和绝对约束 绝对约束：必须严格满足的等式约束和不等式约束绝对约束：必须严格满足的等式约束和不等式约束 如在线性规划问题中考虑的约束条件，不能满足这如在线性规划问题中考虑的约束

40、条件，不能满足这 些约束条件的解称为非可行解，所以它们是硬约束些约束条件的解称为非可行解，所以它们是硬约束 如生产甲，乙产品所需原材料数量有限制，如果无如生产甲，乙产品所需原材料数量有限制，如果无 法从其它渠道予以补充，则构成绝对约束。法从其它渠道予以补充，则构成绝对约束。 21 108xxz56108 1121 ddxx 12 210 xx 1222 210 xxdd （4）优先因子（优先等级）与权系数。）优先因子（优先等级）与权系数。 目标的主次。要求第一位达到的目标赋予优先目标的主次。要求第一位达到的目标赋予优先 因子因子p1，次位的目标赋予优先因子，次位的目标赋予优先因子p2, 规定规

41、定 prpr+1，r=1,2, ,k. 首先保证首先保证p1级目标的实级目标的实 现，这时可不考虑次级现，这时可不考虑次级 目标。目标。 p2级目标的实现是在实级目标的实现是在实 现现p1 级目标的基础上级目标的基础上 若要区别具有相同优先因子的两个目标的差别，若要区别具有相同优先因子的两个目标的差别， 决策者可根据具体情况分别赋予它们不同的权系数决策者可根据具体情况分别赋予它们不同的权系数wj。 权系数由决策者按具体情况而定。权系数由决策者按具体情况而定。 比如比如【例例9-39-3】, ,决策者考虑的首先是甲产品的产量不决策者考虑的首先是甲产品的产量不 能超过乙产品的产量；赋予优先级为能超

42、过乙产品的产量；赋予优先级为p p1 1, , 其次是充分其次是充分 利用设备有效机时，不加班；利用设备有效机时，不加班；赋予优先级为赋予优先级为p p2 2。 （5）目标规划的目标函数。）目标规划的目标函数。 目标规划的目标函数（准则函数）是按各自目标目标规划的目标函数（准则函数）是按各自目标 约束的正、负偏差变量和赋予相应的优先因子而构造约束的正、负偏差变量和赋予相应的优先因子而构造 的。每当一目标值确定后，决策者的要求是的。每当一目标值确定后，决策者的要求是尽可能缩尽可能缩 小偏离目标值小偏离目标值，因此目标规划的目标函数只能是，因此目标规划的目标函数只能是 minz=f(d+,d-)其基本形式有三种：其基本形式有三种： 要求恰好达到目标值，即正、负偏差变量都要要求恰好达到目标值，即正、负偏差变量都要 尽可能地小，这时，尽可能地小，这时， minz=d+d- 要求不超过目标值，即允许达不到目标值，就是要求不超过目标值，即允许达不到目标值，就是 正偏差变量要尽可能地小，这时，正偏差变量要尽可能地小，这时，minz=d+ 要求超过目标值，即超过量不限，就是负偏差要求超过目标值，即超过量不限，就是负偏差 变量要尽可能地小，这时，变量要尽可能地小，这时，minz=d- 对每一个具体目标规划问题，可根据决策者的要求对每一个具体目标规划问题