《管理运筹学（第五版）》-目标整数及零壹

目标规划问题及其数学模型1.问题的提出： 目标规划是在线性规划的基础上，逐步发展起来的一个分支。 目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，分析如何达到规定目标或从总体上离规定目标的差距为最小。目标规划问题及其数学模型例1:某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。ABCD单件利润甲11402乙22043最大负荷1281612问该企业应如何安排计划，使得计划期内的总利润收入为最大？目标规划问题及其数学模型解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：其最优解为x1＝4，x2＝2，z＊＝14元目标规划问题及其数学模型但企业的经营目标不仅仅是利润，而且要考虑多个方面，如：力求使利润指标不低于12元；考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例；C和D为贵重设备，严格禁止超时使用；设备B必要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽可能不加班。要考虑上述多方面的目标，需要借助目标规划的方法。目标规划问题及其数学模型线性规划模型存在的局限性：1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。目标规划问题及其数学模型目标规划怎样解决上述线性规划模型建模中的局限性？1.设置偏差变量，用来表明实际值同目标值之间的差异偏差变量用下列符号表示：d+——超出目标的偏差，称正偏差变量d-——未达到目标的偏差，称负偏差变量正负偏差变量两者必有一个为0。当实际值超出目标值时：d+>0,d-=0;

当实际值未达到目标值时：d+=0,d->0;

当实际值同目标值恰好一致时：d+=0,d-=0;故恒有d+×d-=0目标规划问题及其数学模型2.统一处理目标和约束

对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如C和D设备的使用限制。

对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。1）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为：x1=x2。由于这个比例允许有偏差，当x1<x2时，出现负偏差d-，即：x1+d-

=x2或x1－x2+d-

=0当x1>x2时，出现正偏差d+，即：x1-d+

=x2或x1－x2-d+

=0目标规划问题及其数学模型∵正负偏差不可能同时出现，故总有：x1－x2+d--d+

=0

若希望甲的产量不低于乙的产量，即不希望d->0,用目标约束可表为:

若希望甲的产量低于乙的产量，即不希望d＋>0,用目标约束可表为:

若希望甲的产量恰好等于乙的产量，即不希望d＋>0,也不希望d->0用目标约束可表为:目标规划问题及其数学模型3）设备B必要时可加班及加班时间要控制，目标约束表示为：2）力求使利润指标不低于12元，目标约束表示为：4）设备A既要求充分利用，又尽可能不加班，目标约束表示为：目标规划问题及其数学模型3.目标的优先级与权系数

在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,…表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。现假定：

第1优先级P1——企业利润；第2优先级P2——甲乙产品的产量保持1:1的比例第3优先级P3——设备A,B尽量不超负荷工作。其中设备A的重要性比设备B大三倍。目标规划问题及其数学模型上述目标规划模型可以表示为：目标规划问题及其数学模型5.目标规划的目标函数从决策者的要求来分析，总希望得到的结果与规定的指标值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小化的目标函数，minZ=f（d+，d-）其基本形式有三种：4.满意解前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。目标规划问题及其数学模型（1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小。构造的目标函数是

minZ=f（d++d-

）

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

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

minZ=f（d-）目标规划问题及其数学模型

建模的步骤1.根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；4.对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。3.给各目标赋予相应的优先因子Pi（i=1.2…L）。2.可根据决策者的需要，将某些或全部绝对约束转化为目标约束。目标规划问题及其数学模型目标规划数学模型的一般形式达成函数目标约束其中：gk为第k个目标约束的预期目标值，和为pl优先因子对应各目标的权系数。目标规划问题及其数学模型用目标规划求解问题的过程：明确问题，列出目标的优先级和权系数构造目标规划模型求出满意解满意否？分析各项目标完成情况据此制定出决策方案NY目标规划问题及其数学模型例2:某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的生产方案？ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810

在此基础上考虑：

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

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

3.利润不小于56

元。解:分析第二目标P2

：第三目标P3

：第一目标P1:

目标规划问题及其数学模型ⅠⅡ拥有量原材料2111设备(台时)1210单件利润8101、产品Ⅱ的产量不低于产品Ⅰ的产量；

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

3、利润不小于56元。2x1+x2≤11

（在绝对约束基础上进行目标规划）

x1-x2+d1--d1+=0

(要求：d1+

尽可能小，最好是0才能满足≤)

x1+2x2+d2--d2+=10

（要求：d2-

和d2+

都尽可能小，最好等于0）

8x1+10x2+d3--d3+=56

（要求：d3-

尽可能小，最好是0才能满足≥）

x1,x2,di-,di+≥0目标规划问题及其数学模型规划模型：目标规划的图解法目标规划的图解法：

适用两个变量的目标规划问题，图解法解题步骤：1.将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。2.确定系统约束的可行域。3.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向目标规划的图解法3.求满足最高优先等级目标的解4.转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解5.重复4，直到所有优先等级的目标都已审查完毕为止6.确定最优解和满意解。目标规划的图解分析法例4.3用图解法求解下列目标规划问题目标规划的图解分析法(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解(3,3)046834622目标规划的单纯形法（一）、一般形式：Cj

c1c2cn+2mCBXBb

x1x2xn+2m

cj1xj1bo1e11e12e1n+2mcj2xj2bo2e21e22e2n+2mcjmxjm

bomem1em2emn+2mσkjP1

α1σ11σ12σ1n+2mP2

α2σ21σ22σ2n+2mPK

αK

σm1σm2σmn+2m目标规划的单纯形法一、特点1.目标函数：min2.最优性判断：σj≥0

时为最优3.非基变量检验数的特殊性：含有不同等级的优先因子P1,P2,…,Pk;又因P1>>P2

>>P3>>…>>Pk

，所以检验数的正负首先取决于P1

的系数的正负，若P1

的系数为0，再由P2

的系数的正负决定检验数的正负，然后依次类推。目标规划的单纯形法

(1)建立初始单纯形表．在表中将检验数行按优先因子个数分别列成K行。初始的检验数需根据初始可行解计算出来，方法同基本单纯形法。当不含绝对约束时，di-

（i=1,2,…,K）构成了一组基本可行解，这时只需利用相应单位向量把各级目标行中对应di-

（i=1,2,…,K）的量消成0即可得到初始单纯形表。置k＝1；解目标规划问题的单纯形法的计算步骤(2)检查当前第k行中是否存在大于0，且对应的前k-1行的同列检验数为零的检验数。若有取其中最大者对应的变量为换入变量，转(3)。若无这样的检验数，则转(5)；目标规划的单纯形法(4)按单纯形法进行基变换运算，建立新的单纯形表，（注意：要对所有的行进行转轴运算）返回(2)；

(5)当k＝K

时，计算结束。表中的解即为满意解。否则置k=k+1，返回（2）。

(3)按单纯形法中的最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量，转（4）；

目标规划的单纯形法例4.6：用单纯形法求解下列目标规划问题解：将上述目标规划问题化为标准型：目标规划的单纯形法建立初始单纯形表：目标规划的单纯形法θ=min｛－，10/2，56/10，11/1｝=5进基变量x2Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000

P3

5681000001－100

x3

11210000001σjP1

000100000P2

－1－20002000P3

－8－100000010换出变量d2-目标规划的单纯形法Cj

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,进基变量x1换出变量d3-目标规划的单纯形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

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

300002-2-1/21/21σjP1

000100000P2

000011000P3

000000100最优解为x1＝2，x2＝4。但非基变量d3+的检验数为零，故此题有无穷多最优解。目标规划的单纯形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

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

300002-2-1/21/21σjP1

000100000P2

000011000P3

000000100θ=min｛4,24,－,6｝=4进基变量d3+换出变量d1-目标规划的单纯形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

04002-26-6-1100x210/301-1/31/31/3-1/30000x110/3102/3-2/31/3-1/30000x3

100-1－1-11001σjP1

000100000P2

000011000P3

000000100最优解为x1＝10/3，x2＝10/3。目标规划应用举例例8:已知一个生产计划的线性规划模型如下，其中目标函数为总利润，x1,x2

为产品A、B产量。现有下列目标：1.要求总利润必须超过2500元；2.考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件；3.由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。目标规划应用举例解：以产品A,B的单件利润比2.5:1为权系数，模型如下：目标规划应用举例0x2

0⑴x11401201008060402020406080100⑵⑶⑷ABCDC(60,58.3)为所求的满意解。(24,26)目标规划应用举例例9:某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。

该厂经营目标如下：1、利润指标为每月16000元，争取超额完成；2、充分利用现有生产能力；3、可以适当加班，但加班时间不得超过24小时；4、产量以预计销售量为准。试建立目标规划模型。目标规划应用举例已知条件如表所示工序型号每周最大加工能力ABⅠ（小时/台）Ⅱ（小时/台）436215070利润（元/台）300450如果工厂经营目标的期望值和优先等级如下：p1:每周总利润不得低于10000元；p2:因合同要求，A型机每周至少生产10台，B型机每周至少生产15台；p3:希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。目标规划应用举例这个问题的目标规划模型为：目标规划问题及其数学模型小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xsxa

xixsxad约束条件绝对约束目标约束、绝对约束解最优最满意Chapter5整数规划

(IntegerProgramming)整数规划的特点及应用分支定界法0－1整数规划指派问题本章主要内容：

在很多场合，我们建立最优化模型时，实际问题要求决策变量只能取整数值而非连续取值。此时，这类最优化模型就称为整数规划（离散最优化）模型。

整数规划的求解往往比线性规划求解困难得多，而且，一般来说不能简单地将相应的线性规划的解取整来获得。整数规划的特点及应用整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：整数规划的特点及应用整数线性规划问题的种类：

纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。

0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。整数规划的特点及应用整数规划的典型例子例5.1工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量350400300150工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。整数规划的特点及应用解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：整数规划的特点及应用混合整数规划问题整数规划的特点及应用例5.2现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定;项目3和4中至少选择一个；项目5,6,7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。整数规划的特点及应用解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令xj表示第j个项目的决策选择，记为：投资问题可以表示为：整数规划的特点及应用例5.3指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。

工作人员ABCD甲85927390乙95877895丙82837990丁86908088整数规划的特点及应用设数学模型如下：要求每人做一项工作，约束条件为：整数规划的特点及应用每项工作只能安排一人，约束条件为：变量约束：整数规划的特点及应用整数规划问题解的特征：

整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。整数规划的特点及应用例5.3设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。整数规划的特点及应用用图解法求出最优解为：x1＝3/2,x2=10/3，且有Z=29/6

现求整数解(最优解):如用舍入取整法可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。x1x2⑴⑵33(3/2,10/3)

按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。其中(2,2),(3,1)点的目标函数值最大，即为Z=4。整数规划的特点及应用整数规划问题的求解方法：

分支定界法和割平面法匈牙利法（指派问题）分支定界法1）求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步；2）分支与定界： 任意选一个非整数解的变量xi，在松弛问题中加上约束：xi≤[xi]和xi≥[xi]+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。分支定界法的解题步骤：分支定界法例5.4用分枝定界法求解整数规划问题解：首先去掉整数约束，变成一般线性规划问题(原整数规划问题的松驰问题)LPIP分支定界法用图解法求松弛问题的最优解，如图所示。x1x2⑴⑵3(18/11,40/11)⑶21123x1＝18/11,x2=40/11Z=－218/11≈(－19.8)即Z也是IP最小值的下限。对于x1＝18/11≈1.64，取值x1≤1，x1≥2对于x2=40/11≈3.64，取值x2≤3，x2≥4先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2分支定界法分支：分别求出（LP1）和（LP2）的最优解。分支定界法先求LP1,如图所示。此时在B点取得最优解。x1＝1,x2=3,Z(1)＝－16找到整数解，问题已探明，此枝停止计算。x1x2⑴⑵33(18/11,40/11)⑶11BAC同理求LP2,如图所示。在C

点取得最优解。即:x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z(2)<Z(1)＝－16∴原问题有比－16更小的最优解，但x2

不是整数，故继续分支。分支定界法在IP2中分别再加入条件：x2≤3,x2≥4得下式两支：分别求出LP21和LP22的最优解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACD先求LP21,如图所示。此时D在点取得最优解。即x1＝12/5≈2.4,x2=3,Z(21)＝-87/5≈-17.4<Z(1)=-16但x1＝12/5不是整数，可继续分枝。即3≤x1≤2。求LP22，如图所示。无可行解，故不再分枝。分支定界法

在（LP21）的基础上继续分枝。加入条件3≤x1≤2有下式：分别求出（LP211）和（LP212）的最优解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACDEF先求（LP211）,如图所示。此时在E点取得最优解。即x1＝2,x2=3,Z(211)＝－17找到整数解，问题已探明，此枝停止计算。求（LP212），如图所示。此时F在点取得最优解。即x1＝3,x2=2.5,Z(212)＝－31/2≈－15.5>Z(211)

如对LP212继续分解，其最小值也不会低于－15.5，问题探明,剪枝。分支定界法原整数规划问题的最优解为:x1=2,x2=3,Z*=－17以上的求解过程可以用一个树形图表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP21x1=12/5,x2=3Z(21)

＝－17.4LP22无可行解LP211x1=2,x2=3Z(211)

＝－17LP212x1=3,x2=5/2Z(212)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃小结学习要点：掌握一般整数规划问题概念及模型结构掌握分支定界法原理能够用分支定界法求解一般整数规划问题课后练习：一、0－1变量及其应用

0－1变量常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。例如:0－1整数规划当问题有多项要素，每项要素皆有两种选择时，可用一组0－1变量来描述。设问题有有限项要素E1，E2，┉，En,其中每项Ej有两种选择Aj和不选择Aj（j=1,2,┉,n）,则令在应用中，有时会遇到变量可以取多个整数值的问题。如果用0－1变量来表示，也可以用一组0－1变量来取代。如x取0－9之间的任意整数时。

x=20x0+

21x1+

22x2+

23x390－1整数规划（1）两个约束中，只有一个起作用。例：a11x1+a12x2<B1a21x1+a22x2<B2

例5.7含有相互排斥的约束条件的问题解：引入0-1变量Y1,Y2和足够大的正数M，则a11x1+a12x2<B1+M1Y1a21x1+a22x2<B2+M2Y2Y1+Y2=10－1整数规划（2）互相排斥的多个约束中，只有一个起作用ai1x1+ai2x2+…+ainxn

bi(i=1,…,m)互相排斥m个约束，只有一个起作用:ai1x1+…+ainxn

bi+yiM

(i=1,…,m)y1+…+ym=m-1yi为0或1M>0（3）若a个约束条件中只能有b个起作用。则令0－1变量之和为a-b。注意：可用统一M，但M的取值必须足够的大。0－1整数规划例5.8固定费用问题解：设Xj是第j种产品的产量。Yj是0－1变量，表示是（Yj=1）否（Yj=0）生产第j种产品。

单耗量产品资源IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价810120－1整数规划maxZ=4X1+5X2+6X3–100Y1

–150Y2

–200Y32X1+4X2+8X35002X1+3X2+4X3300X1+2X2+3X3100X1

M1Y1X2

M2Y2X3

M3

Y3X1,

X2,

X30整数Y1,Y2,Y3为0－1变量。

s.t.0－1整数规划用4台机床加工3件产品。各产品的机床加工顺序，以及产品I在机床j上加工工时aij见表。例5.9工件排序问题

由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。产品1产品2产品3a11机床1a21机床1a13机床3a22机床2a23机床2a33机床3a14机床4a24机床40－1整数规划机床1：x11+a11

x21+

My1

及x21+a21

x11+

M(1-y1)机床2：

x22+a22

x32+

My2及x32+a32

x22+

M(1-y2)机床3：

x13+a13

x33+

My3及x33+a33

x13+

M(1-y3)机床4：

x14+a14

x24+

My4及x24+a24

x14+

M(1-y4)解：设产品i在机床j上开始加工的时间为xij（1）同一件产品在不同机床上的加工顺序约束（2）每一台机床对不同产品上的加工顺序约束产品1：x11+a11

x13

及x13+a13

x14产品2：

x21+a21

x22及x22+a22

x24产品3：

x32+a32

x330－1整数规划（4）目标函数的建立x24+a24-x21

d（3）产品2的加工时间总约束w

x14+a14w

x24+a24w

x33+a33minz=wminz=max(x14+a14,

x24+a24,

x33+a33)0－1整数规划0－1整数规划隐枚举法(max)原则：1、用试探法，求出一个可行解，以它的目标值作为当前最好值Z02、增加过滤条件Z

Z03、将xi按ci由小大排列（min

大小）

0－1

整数规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1，一般的解法为隐枚举法。0－1整数规划例5.10：maxZ=3x1-2x2+5x3x1+2x2-

x3

2①x1+4x2+x3

4②x1+x2

3③4x2+x3

6④x1,x2,x3为0或1解：观察得解(x1,x2,x3)=(1,0,0)Z0=3过滤条件：3x1-2x2+5x33将(x1，x2

，x3)

(x2

，x1，x3)0－1整数规划解(x2x1x3)目标值

Z0①②③④当前最好值

(0,0,0)0<3(0,0,1)5>√√√√5(0,1,0)3<(0,1,1)8>√√√√8(1,0,0)-2<(1,0,1)3<(1,1,0)1<(1,1,1)6<最优解x=(1,0,1)TZ=8指派问题一、指派问题的数学模型的标准形式：

设n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的效率（时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？设决策变量指派问题的数学模型为：指派问题克尼格定理

:

如果从分配问题效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵[bij]，则以[bij]为效率矩阵的分配问题与以[aij]为效率矩阵的分配问题具有相同的最优解。指派问题二、匈牙利法指派问题的匈牙利法求解步骤：1)变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列中都出现0元素，即从(cij)的每行元素都减去该行的最小元素；再从所得新系数矩阵的每列元素中减去该列的最小元素。2)进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。指派问题找独立0元素，常用的步骤为：

从只有一个0元素的行开始，给该行中的0元素加圈，记作◎。然后划去◎所在列的其它0元素，记作Ø

；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。从只有一个0元素的列开始（画Ø的不计在内），给该列中的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Ø

，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比较这行各0元素所在列中0元素的数目，选择0元素少这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。指派问题

若◎元素的数目m等于矩阵的阶数n（即：m＝n），那么这指派问题的最优解已得到。若m<n,则转入下一步。3)用最少的直线通过所有0元素。其方法：

对没有◎的行打“√”；对已打“√”的行中所有含Ø元素的列打“√”；再对打有“√”的列中含◎元素的行打“√”；重复①、②直到得不出新的打√号的行、列为止；对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数l。注：l应等于m，若不相等，说明试指派过程有误，回到第2步，另行试指派；若l＝m<n，表示还不能确定最优指派方案，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第4步。指派问题4)变换矩阵(bij)以增加0元素

在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。指派问题例5.6有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁5982匈牙利法解：1）变换系数矩阵，增加0元素。－52）试指派（找独立0元素）◎◎◎ØØ

找到3个独立零元素但m=3<n=

4匈牙利法3）作最少的直线覆盖所有0元素

◎◎◎ØØ√√√独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；4）没有被直线通过的元素中选择最小值为1，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派匈牙利法000000◎◎◎ØØ◎得到4个独立零元素，所以最优解矩阵为：即完成4个任务的总时间最少为：2＋4＋1+8=15匈牙利法例4.7已知四人分别完成四项工作所需时间如下表，求最优分配方案。

任务