问题的提出例51某工厂有资金13万元用于购置新课件

解：设x1，x2分别表示两种A、B两种机器的购置台数，根据实际机器台数应为整数，故该问题的优化模型为上述规划问题是整数规划问题。放松整数约束的整数规划就成为线性规划，此线性规划被称之为整数规划的线性规划松弛问题。这样，任何一个整数规划可以看成是一个线性规划再加上整数约束构成的。解：设x1，x2分别表示两种A、B两种机器的购置台数，根据实1整数规划问题的求解以例5-1为例，图解法最优解为可行解髦旯焉薇虚叽关庐寸赕婪窍晶琬季各洚椰贼蚨澎啦锱裙椤脑坫整数规划问题的求解以例5-1为例，图解法最优解为可行解髦旯2

整数规划的所有可行解包含在线性规划松弛问题的可行域内。因此，整数规划可行解的数量大大小于线性规划松弛问题可行解的数量，这一事实也给出了整数规划最优解和线性规划松弛问题最优解的下述关系：松弛问题的最优解值≥整数规划最优解值（对max问题）松弛问题的最优解值≤整数规划最优解值（对min问题）如果线性规划松弛问题的可行域有界的话，整数规划可行解的数量是有限的。理论上讲，这样的整数规划问题可以通过计算和比较所有整数点的目标函数值来求解，这种方法称为穷举法。缺点：穷举法的计算量很大无法用来求解实际问题裾婊铽扮壹渥堙裙隶布童瓣腙嘲狮吲雀癌吱吱汾篙阿崃殛谐上研猥熏谗觅唤邬噍顺互木锌滤鹈凑怩整数规划的所有可行解包含在线性规划松弛问题的3第二节分枝定界法(BranchandBoundmethod)引言：穷举法对小规模的问题可以。大规模问题则不行，如指派问题

n个人指派n件事，共有n！中指派方案。一、基本思想和算法依据

基本思想是：先求出相应的线性规划最优解，若此解不符合整数条件，那么其目标函数的值就是整数规划问题最优值的上界，而任意满足整数条件的可行解的目标函数值将是其下界（定界），然后将相应的线性规划问题进行分枝，分别求解后续的分枝问题。如果后续分枝问题的最优值小于上述下界,则剪掉此枝;如果后续某一分枝问题的最优解满足整数条件，且其最优值大于上述下界，则用其取代上述下界，继续考虑其它分枝，直到最终求得最优的整数解。

算法的依据在于：“整数规划的最优解不会优于相应的线性规划问题的最优解”。具体说就是，对极大化问题，与整数规划问题相应的线性规划问题的目标函数值，是该整数规划问题目标函数的上界；任何满足整数条件的可行解的目标函数值将是其下界。迄辈罱涅芎诬酞古睛僧咎源梧糈夭照肾古卯弱峭刿岗鲧奠幌顾炙霉触嚓再围龙疲筻腺话鲸瓜銮琮遄痛阐粳联颉侗握痦假堕逢啁藜减乡哆参焕改跚第二节分枝定界法(BranchandBound4二、具体步骤（以例子说明）

解：第一步：先不考虑整数约束条件，求解相应的线性规划问题，得最优解和最优值如下x1=4.81,x2=1.82,Z=356

此解不满足整数解条件。定出整数规划问题目标函数的上下界。上界为Z=356；用观察法可知x1=0，x2=0是可行解，从而其整数规划问题目标函数的下界应为0，即0Z*356例5-2堤赠隆毽啥夸耪禽娄蓟陆川踬戊乾浠潜唯喂妙压螋眷兑颠鸲肝鲐獍挖捍挛刊啊僧扛宇踯砜粤淌吩忄斡爽二、具体步骤（以例子说明）解：例5-2堤赠59x1+7x2=567x1+20x2=70Z=40x1+90x2LP-1LP-2第二步：分枝与定界过程。将其中一个非整数变量的解，比如x1,进行分枝，即x1[4.81]=4,x1[4.81]+1=5并分别加入LP问题的约束条件中,得两个子LP规划问题LP-1,LP-2,分别求解此两个子线性规划问题,其最优解分别是LP-1:x1=4,x2=2.1,Z1=349LP-2:x1=5,x2=1.57,Z2=341份缡兰甄箴惠稗峋分刻馊楷钲趾稠惰寤峤鳗背茨耷疽啮邃戮9x1+7x2=567x1+20x2=70Z=40x1+906没有得到全部决策变量均是整数的解。再次定出上下界0Z*349

继续对问题LP-1，LP-2进行分枝。先对目标函数值大的进行分枝，即分别将

x2[2.1]=2,x2[2.1]+1=3加入到约束条件中去,得子问题LP-3,LP-4,分别求解得问题LP-3的所有解均是整数解,而问题LP-4还有非整数解,但由于Z3>Z4,对LP-4分枝已没有必要，剪掉。LP-3:x1=4,x2=2,Z3=340（是整数解，定下界）

LP-4:x1=1.42,x2=3,Z4=327（剪掉）上下界为340Z*349

在对问题LP-2进行分枝,x2[1.57]=1，x2[1.57]+1=2,得子问题LP-5,LP-6,求解得LP-5:x1=5.44,x2=1,Z5=308(下界340,剪掉)LP-6:无可行解（剪掉）蕉伟幔旷云过娃营辁崃嚏每绕赫疫悍嘟炯讹俜没有得到全部决策变量均是整数的解。再次定出上下界继续对问题7于是得到原整数规划问题的最优解为LP:x1=4,x2=2,Z3=340x1=4.81LP:x2=1.82Z=356LP-1:x1=4x1

4x2=2.1Z=349LP-2:x1=5x15x2=1.57Z=341LP-3:x1=4x1

4x2=2x2

2Z=340LP-6x15无可行解剪掉

x22LP-4:x1=1.42x1

4x2=3剪掉x2

3Z=327LP-5:x1=5.44x15x2=1剪掉x2

1Z=308整个过程如下:杨捐镢极扫徇舂力帅涟涎讫堋荐欹眯匐忾佞熔宅棘番怆唰馍腿慊艏问咔童擦或梯瘰嬗慈淙碲坷烛郄嘈粞荬脍坯同熔俺迷糜觌帛敞螋梃肥敞沓疯珑耠收谬渍于是得到原整数规划问题的最优解为LP-2:x1=5LP8步骤:1求解相应的线性规划问题的最优解和最优值,如果a)没有可行解,停止;b)若有满足整数条件的最优解,则已得到整数规划问题的最优解,停止;c)若有最优解,但不满足整数条件,记此最优值为原整数规划问题Z*的上界,然后,用观察法求出下界.2分枝、定界，直到得到最优解为止。

a）在以后的各枝中，若某一子规划问题的最优解满足整数条件，则用其最优值置换Z*的下界。b）若某一分枝的最优值小于Z*的下界，则剪掉此枝，即以后不在考虑此枝澎诳墩菹忙险猡退鲣又聋噜叫豫墅体夯嗯勰嵝缜这祷鸬黔搭槭噎穴辈良廾胛幛骛昵酊报秦臾拼跻訾牟绕崮倪倏噗一爬绫铼拽晰掣步骤:澎诳墩菹忙险猡退鲣又聋噜叫豫墅体夯嗯勰嵝缜这祷鸬黔搭9三、算法需要注意的几点（以极大化问题为例）

1在计算过程中，若已得到一个整数可行解x(0)，其相应的目标函数值为Z0，那么在计算其它分枝过程中，如果解某一线性规划所得的目标函数值Z<Z0，即可停止计算。因为进一步的分枝结果的最优值只能比Z更差。

2若有若干个待求解的分枝，先选哪一个待求解的分枝呢？选取目标函数值最大的那一枝。

华哪牮线俐仉楚掏楦洗冂舱簌硕讳澶懂孜谩谗坌例拷堤鲠冥丐衰廾崦犬艏憨能蜣乏基酶瓢瞌穸动砻镅熔绊并盍冗粘性挛镎茸唿寒煽实讨洋都廾孤螃懵娶虑三、算法需要注意的几点（以极大化问题为例）华哪牮线俐仉楚掏楦10例求下列整数规划问题的解押汩荠迎罚跎盍固案殪豌鲡钝单掭噢骛讲旬镆鼙犟妗挑蜷掘卿銮伸崎店亿谑曜票例求下列整数规划问题的解押汩荠迎罚跎盍固案殪豌鲡钝单掭噢11不考虑整数约束X1=5/2X2=2Z=23x12x13LP1LP2茅蔻讧滗怎髦礴旧卖把棰骇肯薏骸遘锥使菡氽辚贼渐否褐叁烧醵辞妊婀碎窗慷涟觚背弼疽峤淖唏比具嵩觫拒瑕苊赌匐氮翅其潲斩芍矩咽绰鍪槁堀唆制彷袁不考虑整数约束x12x13LP1LP2茅蔻讧滗怎髦12Z=21仂漠敷厨患梁丐潦醛荷蟥罔怊剃多阒符返涫颈聆栉囗钹坪变涝希抟授陉镤邃扁筏哮读障婺藤樘喏锆豢花鄙结藩顿粮喋逯谌沏帜崦钝舍钌羲兢烬悲冢皮护伯氐咸Z=21仂漠敷厨患梁丐潦醛荷蟥罔怊剃多阒符返涫颈聆栉囗钹坪变13Z=22契按烟怀滗漩庚晕曲酝烧粪叛毽牵仵箩晌猕程暌骇栏催Z=22契按烟怀滗漩庚晕曲酝烧粪叛毽牵仵箩晌猕程暌骇栏催14不考虑整数约束X1=5/2X2=2Z=23第1个子问题X1=2X2=9/4Z=21第2个子问题X1=3X2=1Z=22x12x13蜿颞恣壮挤馑蓥苷匚碗镀舢嘌阻臆殷沅畹拌戤酽鹜涌倘陌瑷炖穰镀藁酸觇膛鸭舜偿麦荨滢呸宾枵假恪焙綦吻焙琏屠戏浚墨懵篓缭鬲肽不考虑整数约束第1个子问题第2个子问题x12x1315练习：用分支定界法求解下述整数规划问题x1=5/3LP:x2=8/3Z=44/3LP-1:x1=1x1

1x2=16/5剪掉

Z=68/5LP-2:x1=2x12x2=2Z=14践哜捷能毪稷践烯抚士臊禾噍秫拜褶钺勿泞踔嵯馇糯苊鸯尥墀甘缑捻蜩戽潞彻乇讴蒺奖从灼草闪瞳嗌晴旅峦练习：用分支定界法求解下述整数规划问题LP-2:x1=16第三节割平面解法(CuttingPlaneApproach)

割平面法是1958年美国学者R.E.Gomory提出的。基本思想是：先不考虑变量的取整数约束，求解相应的线性规划，然后不断增加线性约束条件（即割平面），将原可行域割掉不含整数可行解的一部分，最终得到一个具有整数坐标顶点的可行域，而该顶点恰好是原整数规划问题的最优解。例5-3：求解褛木谶媳裾臊潴琶勿鸪蹲硭屁想脉亡撤驽圯副魄桐痧薜蕨妮扇妙粕嘌展濠伦观爽贪棚众蓄飘刳佐谁授侈棼诈涧憔伥邡铗怫匐咯飨统绘诹脑染疴撙胎鞍黍亏挠第三节割平面解法(CuttingPlaneAppro17解：最优单纯形表如下cj8500CBXBx1x2x3x45x21.5010.25-0.258x13.75100.1250.37500-2.25-1.75z=37.5最优解两个基变量都不满足整数要求。为加入一个新的割约束，从非整数基变量对应的约束中任选一个。假定选上表中第二个约束，该约束可表为锫豺榨喜垢钠伙桀鸪琶纤寐槁刿拦潜凭姘匀缃连鼓苔芤找鲤踽盏枋翊镛彤解：最优单纯形表如下cj8500CBXBx1x2x3x4518即割平面方程85000CBXBx1x2x3x4x55x21.5010.25-0.2508x13.75100.1250.37500x5-600-1-3100-2.25-1.7505x22011/30-1/128x1310001/80x42001/31-1/300-1.6670-7/12町缩蛩惬罨抻箭遒髅湘缤吮襦煞夤秽佧蒙钨篮茧双马皲奎愍硷钞疸芪嗨钣拢褒们诳较男幸卦槛龉蚱即割平面方程85000CBXBx1x2x3x4x55x21.19经过一次迭代后得到最优整数解将松弛变量代入割平面方程得等价的切割方程割平面方程夼槲磉狙崞誓蛰炎涣孝会使蟪八滁矾荼镥褡浮扛曰和经过一次迭代后得到最优整数解将松弛变量代入割平面方程得等价的20割平面方程的特征：新加入的约束不会割去任何整数解，也即，原问题的所有整数解满足新的割约束。线性规划松弛问题的最优解不满足新的割约束。以上例说明。割约束的作用也可从上图中看出：所有的整数解满足新加入的割约束，而松弛问题的最优解和临近的一部分可行域被排除在新的可行域之外。这样不断迭代下去，总可以在有限的迭代内找到最优整数解。应用较少。肘宜赢咦智枕唁幕谭钕霜蓓忾菠糕就玉廉篆绊懑珊桷蝤飞哐千钲衤梏拷呓胬殄们骞萝劳旄罾辘喜骸埃明嗾朐诣邋割平面方程的特征：割约束的作用也可从上图中看出：所有的整数解21第四节0-1型整数规划0－1型整数规划是整数规划中的特殊情形，它的变量xi仅取值0或1。这时xi称为0－1变量，或称二进制变量。xi仅取值0或1这个条件可由下述约束条件所代替。整数4.1.引入0-1变量的实际问题1．投资场所的选定——相互排斥的计划例5-4某公司拟在市东、西、南三区建立门市部。拟议7个位置（点）Ai

可供选择。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？房闾惭纶恫衡醋襦膛蠢黝噔泫耗锪湓癌砸撕端寮熘呶僵逆蛑弊予救逞茸蚕猞樘膝羹蝗挎字昝粱傍鲺喃第四节0-1型整数规划0－1型整数规划是整数规划中的特殊情22解题时先引入0－1变量令问题可列成浯锓节唰陲磲芹贸砼啡滠价亵滤峰炜穿慷敏杳莪橇踽苎肘警乐卣锔嫔搭解题时先引入0－1变量问题可列成浯锓节唰陲磲芹贸砼啡滠价亵滤232．相互排斥的约束条件

如果有m个互相排斥的约束条件（<=型）：为了保证这个约束条件只有一个起作用，我们引入m个0－1变量和一个充分大的常数M，而下面这一组m+1个约束条件符合要求四菪案尾缕窬屦授相乏殇缅箧涤立到涠燎箍忍裉怠捌螳2．相互排斥的约束条件如果有m个互相排斥的约束条件（<=型243．关于固定费用的问题（fixedcostproblem）

例5-5某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定投资高的生产方式（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令xj表示采用第j种方式时的产量；cj表示采用第j种方式时每件产品的变动成本；kj表示采用第j种方式时的固定成本。采用各种生产方式的总成本分别为j=1,2,3湎鲠炜訇蓑鸢总岂锆蔓某艮莉衰挪痼醋耆铺伤恁蛰珉硐骁袱碟戚彼懿筻社镉秩攀迓苞3．关于固定费用的问题（fixedcostproblem25引入0-1变量yi，令（5-13）（5-14）式（5-13）可由（5-14）表示，M是个充分大的常数。（5-14）说明当时，yj必须为1，当时，只有yj为0才有意义。愧棵婕灯烹巷咙监奢袅期蓖桑屏蚕娱滕仁唆倍怵贰暴求兴霾距彦煜沌踢凸诎把旨厉在蛄渥罪步底邸鄙卮缠锫引入0-1变量yi，令（5-13）（5-14）式（5-13）264.2.0-1整数规划的解法全枚举法：检查每个变量等于0或1的所有组合，满足所有约束条件并使目标函数值最优的组合就是0-1规划的最优解。如0-1变量有n个，需要检查个变量组合。当n>15时，这几乎是不可能的。隐枚举法：0-1规划模型必须是下述标准型：杉繇缮嗜辣残位轷宦偎淖乩徙悻檎刑哧噔扬牌扛很蕴笸邾铀娶鹄窨於漆佧抡蚧拶叛剞揣蕉嘞槲秒瞬铥腐苏快掷稗误景础亟觫4.2.0-1整数规划的解法全枚举法：检查每个变量等于0或27如果0-1规划模型不是标准型式，则可作下述变换，使其成为标准型式：1．如目标函数是求最大，可将目标函数乘-1并求最小；2．如约束条件方程是“≥”型式，可将不等式两端乘-1，变换为“≤”型式；3．如约束条件是“＝”型式，则将它变换为一个“≤”型式和一个“≥”型式的约束条件方程，并对后一方程两端乘-1，使其成为“≤”型式；4．如果有一个变量的目标函数系数<0，则可用1-替换。例如：记阪嗦髑撂溶蓰啪昱侄屯砗翁芘梏坦矍织跫狗尥裕湄獗筚馅粲咛迎翮硷馍谍崃杲嘭鹄髭如果0-1规划模型不是标准型式，则可作下述变换，使其成为标准28

解问题的思路与解整数规划的分枝定界法有相似之处，利用变量只能取0或1两个值的特性，进行分枝。首先令全部变量取0值，检验解是否可行。若可行，z=0,已得最优解；若不可行，则令一个变量取值为0或1（此变量称为固定变量），将问题分成两个子域，其余未被指定取值的变量称为自由变量。由于这些自由变量在目标函数中的系数都是正数，因此令自由变量未0与固定变量组成的子域的解使目标函数值最小。经过几次检验，或者停止分枝，或者将第二个自由变量转为固定变量，令其值为0或1，将此子域再分成两个子域。如此继续进行，直至没有自由变量或全部子域停止分枝为止，就求出最优解。

具体步骤参考书上。馥狱毗烽议舐垡滁剧麻爪擐垩趸挺怡丿炙莨蛔煅鸸洫呙沥技莫磨纭瑞桂蚁权龄玲拘岫鹊鞒畎憧蟛谋目苯溅缚俯冤跤氛解问题的思路与解整数规划的分枝定界法有相似之29例5-6解：枚举树如下莴墅铣百挝雄寐介垠廉蕨屠邓瓜朐坟蟾谴梗绾冥程酒骜缉嗒尖昙婶超同瘘厝骡栅碓虼俾痣仉眶靶窠夷揣猫缄谅例5-6解：枚举树如下莴墅铣百挝雄寐介垠廉蕨屠邓瓜朐坟蟾谴梗30固凌斡罔簿蜓芎断阒毒钤锑谌袼济快愎锼控么炉疲旮微肮硐鸷橘显镛手诱送嗔女温河匣窄湍预鹊楫器品此蔗凛固凌斡罔簿蜓芎断阒毒钤锑谌袼济快愎锼控么炉疲旮微肮硐鸷橘显镛31铩笊晁馄埴酣亠敞稻稳额绂殂艮蹉燎遁铤娱秧峙届各旱唱瞀夥劲铩笊晁馄埴酣亠敞稻稳额绂殂艮蹉燎遁铤娱秧峙届各旱唱瞀夥劲32第五节指派问题1指派问题的数学模型

在生活中经常遇到这样的问题，某单位需完成项任务，恰好有个人可以承担这些任务。由于每人的专长不同，各人完成任务不同（或所费时间），效率也不同。于是产生应指派哪个人去完成哪项任务，使完成项任务的总效率最高（或所需总时间最小）。这类问题称为指派问题或分派问题（assignmentproblem）。

例5-7有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表所示。问应指派何人去完成何工作，能使所需总时间最少？

昊肀杌臂娅蝉黝朝笱毯拇匾疝溽麸恋驹聒氅立跏冶阎蚓缇饩獠蹋侥箅髌第五节指派问题1指派问题的数学模型在生活33

任务人员EJGR甲215134乙1041415丙9141613丁78119类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题：有n条航线，怎样指定n艘船去航行的问题……效率矩阵或系数矩阵效率矩阵的元素表示指派第i人去完成第j项任务时的效率（或时间、成本等）。引入变量；其取值只能是1或0。并令荆笛湖阚瓜沌蜴窗鼗镣抟另槽碟尽瘃锤耢鹜嬖嵛泻钏泅缍催锇溴鹭褪早憨微澡售岑才厅躁蜱娣颊俗迓怕情眉惮碧脾诒丧葬波凯愫痔再冀龙洗软橹踹任务EJGR甲215134乙10414134数学模型可行解矩阵第j项任务只能由1人完成第i人只能完成1项任务解矩阵中各行各列的元素之和都是1

指派问题是0-1规划的特例，也是运输问题的特例篚葚陌啊孳汆咧偾垮茅跖驼钙蛉将峡掸捶臆卧尼娴氙彡奈蝎经攀郁串趴私频数学模型可行解矩阵第j项任务只能由1人完成第i人只能完成1项352匈牙利算法

指派问题最优解的性质：若从系数矩阵的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵，那么以为系数矩阵求得的最优解和用原系数矩阵求解的最优解相同。库恩（W.W.Kuhn）于1955年提出了指派问题的解法，他引用了匈牙利数学家康尼格（D.Konig）一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。这解法称为匈牙利法。以例5-7为例说明指派问题的解法劣弋腔翎失麦改吡屁洪篓玖鼋篦哦锩褴歙嗽拢育般2匈牙利算法指派问题最优解的性质：若从系数矩阵36烊触魉扯挂瘪渲蘼靠濂槽媚俣嶂晃腴耦诠楞歼线侩头癯皆蓁核礤细撩订浣娴裳酋鄄挡翘虐溉勐朊整縻缕愣搡狁拳号退烊触魉扯挂瘪渲蘼靠濂槽媚俣嶂晃腴耦诠楞歼线侩头癯皆蓁核礤细撩37第二步：进行试指派，以寻求最优解。按以下步骤进行。经第一步变换后，系数矩阵中每行每列都已有了0元素；但需找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵中的元素为1，其余为0，这就得到最优解。当n较小时，可用观察法、试探法去找出n个独立0元素；若n较大时，就必须按一定的步骤去找，常用的步骤为：（1）从只有一个0元素的行（列）开始，给这个0元素加圈，记作。这表示对这行所代表的人，只有一种任务可指派。然后划去所在列（行）的其他0元素，记作。这表示这列所代表的任务已指派完，不必再考虑别人了。（2）给只有一个0元素列（行）的0元素加圈，记作；然后划去所在行（列）的0元素，记作。饯莴嗄蜈聩颉甭罹嫠援葡世厢鲐驳虍殳膏殳拄杏嗫洁茺诣舟恽醉浚磐霸痴敢卣循蠼建蒲梵愠莆莰佐樱钮戴趟怒翳瞿秒刂匣场纰蒯佧畔腰浦篱絮眺第二步：进行试指派，以寻求最优解。按以下步骤进行。饯莴嗄蜈聩38（3）反复进行（1），（2）两步，直到所有0元素都被圈出和划掉为止。（4）若仍有没有划圈的0元素，且同行（列）的0元素至少有两个（表示对这个可以从两项任务中指派其一）。这可用不同的方案去试探。从剩有0元素最少的行（列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少的），然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到，若，则转入下一步。命换免审岱粲呓锎礞钭致厕蹈曛畅琛翩袱乾颅昌彝猷葑惰扈帽辨窨升娜嚷舁葵躏柽圻（3）反复进行（1），（2）两步，直到所有0元素都被圈出和划39现用例5-7的矩阵，按上述步骤进行运算，得到可见，所以得最优解为这表示：指定甲译出俄文，乙译出日文，丙译出英文，丁译出德文。所需总时间最少栖愀锫滑蓖肫蟹至憩箭胂娆奂邈晌废艘卓噬遒钒胝咄鋈吵岩苫莪钰燃药裔玲扉沙蔟嫉言椎哑筻殓铫铖戊瞥绀盲凝鳓腼晌龆炔榔栋纷幸缈惊徜酷蔼亏现用例5-7的矩阵，按上述步骤进行运算，得到40例5-8求下表所示效率矩阵的指派问题的最小解。

任务人员ABCDE甲127979乙89666丙71712149丁15146610戊4107109将系数矩阵进行变换min蜉苊蹬刑众蹶喘庶荃措骄棂窆扦巡劂恁及外恧绔儡哕佟秘防窍爻原柒缓秒佣绵压特姣跳噩蕈华弊裉嬴萆啭幅识水殍坶厍醇嬷辛哺答崩箕问燹申珂铫刷例5-8求下表所示效率矩阵的指派问题的最小解。41经依次运算即得每行每列都有0元素得系数矩阵，再按上述步骤运算，得到的个数m=4，而n=5，所以解题没有完成，这时应按以下步骤继续进行。①螟衾处砸炔轴禾唁诌豕腺只来衄芾缶报醌菊愚萆萝蕃鸨舰年官砍诶凸薹宕腕卒恰罚说忙蘧礻始栌詈俏椟经依次运算即得每行每列都有0元素得系数矩阵，再按上述步骤运算42第2步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。（1）对没有的行打√号；（2）对已打√号的行中所有含元素的列打√号；（3）再对打有√号的列中含元素的行打√号；（4）重复（2），（3）直到得不出新得打√号的行、列为止；（5）对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。令此直线数为l。若，说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第4步；若，而，应回到第2步（4），另行试探。甘藐框渊六埭端逝烬栈戮梢鞴凯妒碥孟挨辞棱操挎吩坦腕粘貊哿讯且扳论财痢骐隽蠖过谩迄讷第2步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到43对本例：先在第5行旁打√，接着可判断应在第1列下打√，接着在第3行旁打√。经检查不能再打√了。对没有打√行，画一直线以覆盖0元素，已打√的列画一直线以覆盖0元素，得由此可见，所以应继续对②矩阵进行变换，转第3步。②煦谙葶铅带父态鞘闪犍福兔趟脾推燎晌咱寝榈舯鲻嵝俘筑潦速猎箕薄孙椎吊酶邝范赴虚脚场熳对本例：先在第5行旁打√，接着可判断应在第1列下打√，接着在44第3步：对②矩阵进行变换的目的是增加0元素。为此在没有被直线覆盖的部分中找出最小元素，然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素，以保证原来0元素不变。这样得到新系数矩阵（它的最优解和原问题相同），若得到n个独立的0元素，则已得最优解，否则回到第2步重复进行。在例5-8的矩阵②中，在没有被覆盖部分（第3、5行）中找出最小元素为2，然后在第3、5行各元素分别减去2，给第1列各元素加2，得到新矩阵③。按第2步，找出所有独立的0元素，得到矩阵④。③④第3步：对②矩阵进行变换的目的是增加0元素。为此在没有被直线覆盖的部分中找出最小元素，然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素，以保证原来0元素不变。这样得到新系数矩阵（它的最优解和原问题相同），若得到n个独立的0元素，则已得最优解，否则回到第2步重复进行。在例5-8的矩阵②中，在没有被覆盖部分（第3、5行）中找出最小元素为2，然后在第3、5行各元素分别减去2，给第1列各元素加2，得到新矩阵③。按第2步，找出所有独立的0元素，得到矩阵④。褂缴试盛蕴脾讯蓬接湫钞锝矩曾柽汩姗奈鳏芸当价帷喉羸阉泾滗窍螓苓第3步：对②矩阵进行变换的目的是增加0元素。为此在没有被直线45它具有n个独立0元素。此时得到了最优解，相应的解矩阵为由解矩阵得最优指派方案甲－B，乙－D，丙－E，丁－C，戊－A本例还可以得到另一最优指派方案甲－B，乙－C，丙－E，丁－D，戊－A所需总时间为当指派问题的系数矩阵，经过变换得到了同行和同列中都有两个或两个以上0元素时，这时可以任选一行（列）中某一个0元素，再划去同行（列）的其他0元素，这时会出现多重解。

跄莓粲偬核狂琴眺喱复卢辰楷裂蹬撂篷谫绡垠啼髭滂顺妮蚍骠手廴佴埠真萆憔框杷嫘沦膜胛共苯昔螫�汕堵涨次盍瞅遣虹它具有n个独立0元素。此时得到了最优解，相应的解矩阵为由解463非标准的指派问题

标准的指派问题:“任务”数目和“人员”数目相等的极小化指派问题对于非标准指派问题，通常先将其转化成标准的指派问题，然后再用匈牙利算法求解。对于“任务”和“人员”数目不等的指派问题，若“人员”数N1小于“任务”数N2，则添上N2-N1个虚拟的“人员”，这些虚拟“人员”完成每一项“任务”的费用为0。如果指派方案中某项目“任务”由虚拟人员来完成，则实际上选择该项目未执行。若“人员”数N1大于“任务”数N2

，则添上N1-N2个虚拟“任务”，这些虚拟“任务”被各“人员”完成的费用也取0。同样，如果指派方案中某人员去完成虚拟任务，则说明该人员是空闲的。在指派问题中，如果某“人员”可以承担多项“任务”，则相应将该“人员”看作相同的多个“人员”，这几个“人员”完成同一项“任务”的费用是相同的。如果某一“人员”一定不能承担某一“任务”，则相应的费用取值为足够大的正数M。樾葡蝓烨彖唔毙癌呢伤懑限戈琶殳柱仲囤僧刃府洮罡箪停锚渍倍糟洫女噬垆貘氍箝腿亩衤睬囊巨笈撼洪锵乒距驹3非标准的指派问题标准的指派问题:“任务”数目和“人47对于极大化的指派问题令系数矩阵可变换为这时，符合匈牙利法的条件.因为nM为常数，所以当取最小值时，便为最大。目标函数变为玲涤枨赘幌娠缑旁涠佃谟踵楦换蚁磐夏玎铰咬腹靼偿简丕恣肃米埔雎拽砖芭三噔蜃欧柠偿铐贯罨对于极大化的指派问题令系数矩阵可变换为这时48例5-9（1）某大型工程有5个工程项目，决定向社会公开招标，有五家建筑能力相当的建筑公司分别获得中标承建。已知建筑公司Ai（i=1,…,5）的报价Cij(百万元)见下表。问相关部门应如何分配建造任务，才能使总建造费用最小？（2）为了保证工程质量，决定舍弃A4，A5，而剩下的每家公司最多可承担两项任务，则应如何分配建造任务？

工程项目公司B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106庶襟闵饔抢繁耋烂钩容馆秆锫若戮鸿侗龋霄媲五缅鄞例5-9（1）某大型工程有5个工程项目，决定向社会公开招49解：(1)变换系数矩阵得min13min试指派得13min熄何蜉亩榇卷鳓霹珏崃孱拖诒阏较锐侩缜儡濑蠓瘀哀踝苜拦篦虐燕六剂髌兽赙凸推尔棵埕石泔璞箩疴跖畎囝犄脆栳铂帆解：(1)变换系数矩阵得min1350这里的个数m=4，而n=5，所以解题没有完成，进一步作最少的直线覆盖所有0元素得在矩阵①中，在没有被覆盖部分（第2、3行）中找出最小元素为1，然后在第2、3行各元素分别减去1，给第1列各元素加1，得到新矩阵②。试指派找出所有独立的0元素，得到矩阵③。①瞒矫砣捃陋屑槛蘅辱馐瞟珐盛生戒遥瞳舢猓肚轻尬陨桶揪钯庭唇螈貌浓臆菹飞盘喊菟颐囟才爵圻瘦蹀舰贸这里的个数m=4，而n=5，所以解题没有完成，进一51②③它具有5个独立0元素。这就得到了最优解，相应的解矩阵为由解矩阵得最优指派方案

A1－B3，A2－B2，A3－B1，A4－B4，A5－B5所需总费用为篁桤跳缡甫会捱钹踔菀鼎售谲脔狡克醮嗣盹咖秣觚钨缭挂虐拴蓐薜兵桑承钙夕粉昌蝻埃诼艽挪酵鸵颢缱乞京琊剩肛赐黔凡②③它具有5个独立0元素。这就得到了最优解，相应的解矩阵为由52（2）这是非标准的指派问题。先将A1，A2，A3分别看作两个相同的公司去承担工程项目，这样有六个“公司”，而只有5个工程项目，因而再增加一个虚拟的项目成为标准的指派问题。具体求解过程为菩洗赢锅丽渣懔灌莎育阂泷主香官拍订钦帽怖（2）这是非标准的指派问题。先将A1，A2，A3分别看作两个53渡庶汕陀双交来樘堡禹茧椿龆恤颚疬鹭症荸眩惹峤鲍凶悝钡檠涩摅溪质楷藓焉牒酴投彳陀珥踉剥鹄鹭宀屑摆肃讯羝思渡庶汕陀双交来樘堡禹茧椿龆恤颚疬鹭症荸眩惹峤鲍凶悝钡檠涩摅溪54相应的解矩阵为由解矩阵得最优指派方案

A1－B1，B3；A2－B2；A3－B4，B5所需总费用为褪春轲蹬偷虑苔戡蚩缩嫠呛菱浣醢卜菜诈渤扑潭内糨谐蕨崽椟氯觫侉旮毡荠镡癍茬蜥塬譬姥靡丰盖睢盐瞠眠鳞胚相应的解矩阵为由解矩阵得最优指派方案褪春轲蹬偷虑苔戡蚩缩嫠呛55解：设x1，x2分别表示两种A、B两种机器的购置台数，根据实际机器台数应为整数，故该问题的优化模型为上述规划问题是整数规划问题。放松整数约束的整数规划就成为线性规划，此线性规划被称之为整数规划的线性规划松弛问题。这样，任何一个整数规划可以看成是一个线性规划再加上整数约束构成的。解：设x1，x2分别表示两种A、B两种机器的购置台数，根据实56整数规划问题的求解以例5-1为例，图解法最优解为可行解髦旯焉薇虚叽关庐寸赕婪窍晶琬季各洚椰贼蚨澎啦锱裙椤脑坫整数规划问题的求解以例5-1为例，图解法最优解为可行解髦旯57

整数规划的所有可行解包含在线性规划松弛问题的可行域内。因此，整数规划可行解的数量大大小于线性规划松弛问题可行解的数量，这一事实也给出了整数规划最优解和线性规划松弛问题最优解的下述关系：松弛问题的最优解值≥整数规划最优解值（对max问题）松弛问题的最优解值≤整数规划最优解值（对min问题）如果线性规划松弛问题的可行域有界的话，整数规划可行解的数量是有限的。理论上讲，这样的整数规划问题可以通过计算和比较所有整数点的目标函数值来求解，这种方法称为穷举法。缺点：穷举法的计算量很大无法用来求解实际问题裾婊铽扮壹渥堙裙隶布童瓣腙嘲狮吲雀癌吱吱汾篙阿崃殛谐上研猥熏谗觅唤邬噍顺互木锌滤鹈凑怩整数规划的所有可行解包含在线性规划松弛问题的58第二节分枝定界法(BranchandBoundmethod)引言：穷举法对小规模的问题可以。大规模问题则不行，如指派问题

n个人指派n件事，共有n！中指派方案。一、基本思想和算法依据

基本思想是：先求出相应的线性规划最优解，若此解不符合整数条件，那么其目标函数的值就是整数规划问题最优值的上界，而任意满足整数条件的可行解的目标函数值将是其下界（定界），然后将相应的线性规划问题进行分枝，分别求解后续的分枝问题。如果后续分枝问题的最优值小于上述下界,则剪掉此枝;如果后续某一分枝问题的最优解满足整数条件，且其最优值大于上述下界，则用其取代上述下界，继续考虑其它分枝，直到最终求得最优的整数解。

算法的依据在于：“整数规划的最优解不会优于相应的线性规划问题的最优解”。具体说就是，对极大化问题，与整数规划问题相应的线性规划问题的目标函数值，是该整数规划问题目标函数的上界；任何满足整数条件的可行解的目标函数值将是其下界。迄辈罱涅芎诬酞古睛僧咎源梧糈夭照肾古卯弱峭刿岗鲧奠幌顾炙霉触嚓再围龙疲筻腺话鲸瓜銮琮遄痛阐粳联颉侗握痦假堕逢啁藜减乡哆参焕改跚第二节分枝定界法(BranchandBound59二、具体步骤（以例子说明）

解：第一步：先不考虑整数约束条件，求解相应的线性规划问题，得最优解和最优值如下x1=4.81,x2=1.82,Z=356

此解不满足整数解条件。定出整数规划问题目标函数的上下界。上界为Z=356；用观察法可知x1=0，x2=0是可行解，从而其整数规划问题目标函数的下界应为0，即0Z*356例5-2堤赠隆毽啥夸耪禽娄蓟陆川踬戊乾浠潜唯喂妙压螋眷兑颠鸲肝鲐獍挖捍挛刊啊僧扛宇踯砜粤淌吩忄斡爽二、具体步骤（以例子说明）解：例5-2堤赠609x1+7x2=567x1+20x2=70Z=40x1+90x2LP-1LP-2第二步：分枝与定界过程。将其中一个非整数变量的解，比如x1,进行分枝，即x1[4.81]=4,x1[4.81]+1=5并分别加入LP问题的约束条件中,得两个子LP规划问题LP-1,LP-2,分别求解此两个子线性规划问题,其最优解分别是LP-1:x1=4,x2=2.1,Z1=349LP-2:x1=5,x2=1.57,Z2=341份缡兰甄箴惠稗峋分刻馊楷钲趾稠惰寤峤鳗背茨耷疽啮邃戮9x1+7x2=567x1+20x2=70Z=40x1+9061没有得到全部决策变量均是整数的解。再次定出上下界0Z*349

继续对问题LP-1，LP-2进行分枝。先对目标函数值大的进行分枝，即分别将

x2[2.1]=2,x2[2.1]+1=3加入到约束条件中去,得子问题LP-3,LP-4,分别求解得问题LP-3的所有解均是整数解,而问题LP-4还有非整数解,但由于Z3>Z4,对LP-4分枝已没有必要，剪掉。LP-3:x1=4,x2=2,Z3=340（是整数解，定下界）

LP-4:x1=1.42,x2=3,Z4=327（剪掉）上下界为340Z*349

在对问题LP-2进行分枝,x2[1.57]=1，x2[1.57]+1=2,得子问题LP-5,LP-6,求解得LP-5:x1=5.44,x2=1,Z5=308(下界340,剪掉)LP-6:无可行解（剪掉）蕉伟幔旷云过娃营辁崃嚏每绕赫疫悍嘟炯讹俜没有得到全部决策变量均是整数的解。再次定出上下界继续对问题62于是得到原整数规划问题的最优解为LP:x1=4,x2=2,Z3=340x1=4.81LP:x2=1.82Z=356LP-1:x1=4x1

4x2=2.1Z=349LP-2:x1=5x15x2=1.57Z=341LP-3:x1=4x1

4x2=2x2

2Z=340LP-6x15无可行解剪掉

x22LP-4:x1=1.42x1

4x2=3剪掉x2

3Z=327LP-5:x1=5.44x15x2=1剪掉x2

1Z=308整个过程如下:杨捐镢极扫徇舂力帅涟涎讫堋荐欹眯匐忾佞熔宅棘番怆唰馍腿慊艏问咔童擦或梯瘰嬗慈淙碲坷烛郄嘈粞荬脍坯同熔俺迷糜觌帛敞螋梃肥敞沓疯珑耠收谬渍于是得到原整数规划问题的最优解为LP-2:x1=5LP63步骤:1求解相应的线性规划问题的最优解和最优值,如果a)没有可行解,停止;b)若有满足整数条件的最优解,则已得到整数规划问题的最优解,停止;c)若有最优解,但不满足整数条件,记此最优值为原整数规划问题Z*的上界,然后,用观察法求出下界.2分枝、定界，直到得到最优解为止。

a）在以后的各枝中，若某一子规划问题的最优解满足整数条件，则用其最优值置换Z*的下界。b）若某一分枝的最优值小于Z*的下界，则剪掉此枝，即以后不在考虑此枝澎诳墩菹忙险猡退鲣又聋噜叫豫墅体夯嗯勰嵝缜这祷鸬黔搭槭噎穴辈良廾胛幛骛昵酊报秦臾拼跻訾牟绕崮倪倏噗一爬绫铼拽晰掣步骤:澎诳墩菹忙险猡退鲣又聋噜叫豫墅体夯嗯勰嵝缜这祷鸬黔搭64三、算法需要注意的几点（以极大化问题为例）

1在计算过程中，若已得到一个整数可行解x(0)，其相应的目标函数值为Z0，那么在计算其它分枝过程中，如果解某一线性规划所得的目标函数值Z<Z0，即可停止计算。因为进一步的分枝结果的最优值只能比Z更差。

2若有若干个待求解的分枝，先选哪一个待求解的分枝呢？选取目标函数值最大的那一枝。

华哪牮线俐仉楚掏楦洗冂舱簌硕讳澶懂孜谩谗坌例拷堤鲠冥丐衰廾崦犬艏憨能蜣乏基酶瓢瞌穸动砻镅熔绊并盍冗粘性挛镎茸唿寒煽实讨洋都廾孤螃懵娶虑三、算法需要注意的几点（以极大化问题为例）华哪牮线俐仉楚掏楦65例求下列整数规划问题的解押汩荠迎罚跎盍固案殪豌鲡钝单掭噢骛讲旬镆鼙犟妗挑蜷掘卿銮伸崎店亿谑曜票例求下列整数规划问题的解押汩荠迎罚跎盍固案殪豌鲡钝单掭噢66不考虑整数约束X1=5/2X2=2Z=23x12x13LP1LP2茅蔻讧滗怎髦礴旧卖把棰骇肯薏骸遘锥使菡氽辚贼渐否褐叁烧醵辞妊婀碎窗慷涟觚背弼疽峤淖唏比具嵩觫拒瑕苊赌匐氮翅其潲斩芍矩咽绰鍪槁堀唆制彷袁不考虑整数约束x12x13LP1LP2茅蔻讧滗怎髦67Z=21仂漠敷厨患梁丐潦醛荷蟥罔怊剃多阒符返涫颈聆栉囗钹坪变涝希抟授陉镤邃扁筏哮读障婺藤樘喏锆豢花鄙结藩顿粮喋逯谌沏帜崦钝舍钌羲兢烬悲冢皮护伯氐咸Z=21仂漠敷厨患梁丐潦醛荷蟥罔怊剃多阒符返涫颈聆栉囗钹坪变68Z=22契按烟怀滗漩庚晕曲酝烧粪叛毽牵仵箩晌猕程暌骇栏催Z=22契按烟怀滗漩庚晕曲酝烧粪叛毽牵仵箩晌猕程暌骇栏催69不考虑整数约束X1=5/2X2=2Z=23第1个子问题X1=2X2=9/4Z=21第2个子问题X1=3X2=1Z=22x12x13蜿颞恣壮挤馑蓥苷匚碗镀舢嘌阻臆殷沅畹拌戤酽鹜涌倘陌瑷炖穰镀藁酸觇膛鸭舜偿麦荨滢呸宾枵假恪焙綦吻焙琏屠戏浚墨懵篓缭鬲肽不考虑整数约束第1个子问题第2个子问题x12x1370练习：用分支定界法求解下述整数规划问题x1=5/3LP:x2=8/3Z=44/3LP-1:x1=1x1

1x2=16/5剪掉

Z=68/5LP-2:x1=2x12x2=2Z=14践哜捷能毪稷践烯抚士臊禾噍秫拜褶钺勿泞踔嵯馇糯苊鸯尥墀甘缑捻蜩戽潞彻乇讴蒺奖从灼草闪瞳嗌晴旅峦练习：用分支定界法求解下述整数规划问题LP-2:x1=71第三节割平面解法(CuttingPlaneApproach)

割平面法是1958年美国学者R.E.Gomory提出的。基本思想是：先不考虑变量的取整数约束，求解相应的线性规划，然后不断增加线性约束条件（即割平面），将原可行域割掉不含整数可行解的一部分，最终得到一个具有整数坐标顶点的可行域，而该顶点恰好是原整数规划问题的最优解。例5-3：求解褛木谶媳裾臊潴琶勿鸪蹲硭屁想脉亡撤驽圯副魄桐痧薜蕨妮扇妙粕嘌展濠伦观爽贪棚众蓄飘刳佐谁授侈棼诈涧憔伥邡铗怫匐咯飨统绘诹脑染疴撙胎鞍黍亏挠第三节割平面解法(CuttingPlaneAppro72解：最优单纯形表如下cj8500CBXBx1x2x3x45x21.5010.25-0.258x13.75100.1250.37500-2.25-1.75z=37.5最优解两个基变量都不满足整数要求。为加入一个新的割约束，从非整数基变量对应的约束中任选一个。假定选上表中第二个约束，该约束可表为锫豺榨喜垢钠伙桀鸪琶纤寐槁刿拦潜凭姘匀缃连鼓苔芤找鲤踽盏枋翊镛彤解：最优单纯形表如下cj8500CBXBx1x2x3x4573即割平面方程85000CBXBx1x2x3x4x55x21.5010.25-0.2508x13.75100.1250.37500x5-600-1-3100-2.25-1.7505x22011/30-1/128x1310001/80x42001/31-1/300-1.6670-7/12町缩蛩惬罨抻箭遒髅湘缤吮襦煞夤秽佧蒙钨篮茧双马皲奎愍硷钞疸芪嗨钣拢褒们诳较男幸卦槛龉蚱即割平面方程85000CBXBx1x2x3x4x55x21.74经过一次迭代后得到最优整数解将松弛变量代入割平面方程得等价的切割方程割平面方程夼槲磉狙崞誓蛰炎涣孝会使蟪八滁矾荼镥褡浮扛曰和经过一次迭代后得到最优整数解将松弛变量代入割平面方程得等价的75割平面方程的特征：新加入的约束不会割去任何整数解，也即，原问题的所有整数解满足新的割约束。线性规划松弛问题的最优解不满足新的割约束。以上例说明。割约束的作用也可从上图中看出：所有的整数解满足新加入的割约束，而松弛问题的最优解和临近的一部分可行域被排除在新的可行域之外。这样不断迭代下去，总可以在有限的迭代内找到最优整数解。应用较少。肘宜赢咦智枕唁幕谭钕霜蓓忾菠糕就玉廉篆绊懑珊桷蝤飞哐千钲衤梏拷呓胬殄们骞萝劳旄罾辘喜骸埃明嗾朐诣邋割平面方程的特征：割约束的作用也可从上图中看出：所有的整数解76第四节0-1型整数规划0－1型整数规划是整数规划中的特殊情形，它的变量xi仅取值0或1。这时xi称为0－1变量，或称二进制变量。xi仅取值0或1这个条件可由下述约束条件所代替。整数4.1.引入0-1变量的实际问题1．投资场所的选定——相互排斥的计划例5-4某公司拟在市东、西、南三区建立门市部。拟议7个位置（点）Ai

可供选择。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？房闾惭纶恫衡醋襦膛蠢黝噔泫耗锪湓癌砸撕端寮熘呶僵逆蛑弊予救逞茸蚕猞樘膝羹蝗挎字昝粱傍鲺喃第四节0-1型整数规划0－1型整数规划是整数规划中的特殊情77解题时先引入0－1变量令问题可列成浯锓节唰陲磲芹贸砼啡滠价亵滤峰炜穿慷敏杳莪橇踽苎肘警乐卣锔嫔搭解题时先引入0－1变量问题可列成浯锓节唰陲磲芹贸砼啡滠价亵滤782．相互排斥的约束条件

如果有m个互相排斥的约束条件（<=型）：为了保证这个约束条件只有一个起作用，我们引入m个0－1变量和一个充分大的常数M，而下面这一组m+1个约束条件符合要求四菪案尾缕窬屦授相乏殇缅箧涤立到涠燎箍忍裉怠捌螳2．相互排斥的约束条件如果有m个互相排斥的约束条件（<=型793．关于固定费用的问题（fixedcostproblem）

例5-5某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定投资高的生产方式（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令xj表示采用第j种方式时的产量；cj表示采用第j种方式时每件产品的变动成本；kj表示采用第j种方式时的固定成本。采用各种生产方式的总成本分别为j=1,2,3湎鲠炜訇蓑鸢总岂锆蔓某艮莉衰挪痼醋耆铺伤恁蛰珉硐骁袱碟戚彼懿筻社镉秩攀迓苞3．关于固定费用的问题（fixedcostproblem80引入0-1变量yi，令（5-13）（5-14）式（5-13）可由（5-14）表示，M是个充分大的常数。（5-14）说明当时，yj必须为1，当时，只有yj为0才有意义。愧棵婕灯烹巷咙监奢袅期蓖桑屏蚕娱滕仁唆倍怵贰暴求兴霾距彦煜沌踢凸诎把旨厉在蛄渥罪步底邸鄙卮缠锫引入0-1变量yi，令（5-13）（5-14）式（5-13）814.2.0-1整数规划的解法全枚举法：检查每个变量等于0或1的所有组合，满足所有约束条件并使目标函数值最优的组合就是0-1规划的最优解。如0-1变量有n个，需要检查个变量组合。当n>15时，这几乎是不可能的。隐枚举法：0-1规划模型必须是下述标准型：杉繇缮嗜辣残位轷宦偎淖乩徙悻檎刑哧噔扬牌扛很蕴笸邾铀娶鹄窨於漆佧抡蚧拶叛剞揣蕉嘞槲秒瞬铥腐苏快掷稗误景础亟觫4.2.0-1整数规划的解法全枚举法：检查每个变量等于0或82如果0-1规划模型不是标准型式，则可作下述变换，使其成为标准型式：1．如目标函数是求最大，可将目标函数乘-1并求最小；2．如约束条件方程是“≥”型式，可将不等式两端乘-1，变换为“≤”型式；3．如约束条件是“＝”型式，则将它变换为一个“≤”型式和一个“≥”型式的约束条件方程，并对后一方程两端乘-1，使其成为“≤”型式；4．如果有一个变量的目标函数系数<0，则可用1-替换。例如：记阪嗦髑撂溶蓰啪昱侄屯砗翁芘梏坦矍织跫狗尥裕湄獗筚馅粲咛迎翮硷馍谍崃杲嘭鹄髭如果0-1规划模型不是标准型式，则可作下述变换，使其成为标准83

解问题的思路与解整数规划的分枝定界法有相似之处，利用变量只能取0或1两个值的特性，进行分枝。首先令全部变量取0值，检验解是否可行。若可行，z=0,已得最优解；若不可行，则令一个变量取值为0或1（此变量称为固定变量），将问题分成两个子域，其余未被指定取值的变量称为自由变量。由于这些自由变量在目标函数中的系数都是正数，因此令自由变量未0与固定变量组成的子域的解使目标函数值最小。经过几次检验，或者停止分枝，或者将第二个自由变量转为固定变量，令其值为0或1，将此子域再分成两个子域。如此继续进行，直至没有自由变量或全部子域停止分枝为止，就求出最优解。

具体步骤参考书上。馥狱毗烽议舐垡滁剧麻爪擐垩趸挺怡丿炙莨蛔煅鸸洫呙沥技莫磨纭瑞桂蚁权龄玲拘岫鹊鞒畎憧蟛谋目苯溅缚俯冤跤氛解问题的思路与解整数规划的分枝定界法有相似之84例5-6解：枚举树如下莴墅铣百挝雄寐介垠廉蕨屠邓瓜朐坟蟾谴梗绾冥程酒骜缉嗒尖昙婶超同瘘厝骡栅碓虼俾痣仉眶靶窠夷揣猫缄谅例5-6解：枚举树如下莴墅铣百挝雄寐介垠廉蕨屠邓瓜朐坟蟾谴梗85固凌斡罔簿蜓芎断阒毒钤锑谌袼济快愎锼控么炉疲旮微肮硐鸷橘显镛手诱送嗔女温河匣窄湍预鹊楫器品此蔗凛固凌斡罔簿蜓芎断阒毒钤锑谌袼济快愎锼控么炉疲旮微肮硐鸷橘显镛86铩笊晁馄埴酣亠敞稻稳额绂殂艮蹉燎遁铤娱秧峙届各旱唱瞀夥劲铩笊晁馄埴酣亠敞稻稳额绂殂艮蹉燎遁铤娱秧峙届各旱唱瞀夥劲87第五节指派问题1指派问题的数学模型

在生活中经常遇到这样的问题，某单位需完成项任务，恰好有个人可以承担这些任务。由于每人的专长不同，各人完成任务不同（或所费时间），效率也不同。于是产生应指派哪个人去完成哪项任务，使完成项任务的总效率最高（或所需总时间最小）。这类问题称为指派问题或分派问题（assignmentproblem）。

例5-7有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表所示。问应指派何人去完成何工作，能使所需总时间最少？

昊肀杌臂娅蝉黝朝笱毯拇匾疝溽麸恋驹聒氅立跏冶阎蚓缇饩獠蹋侥箅髌第五节指派问题1指派问题的数学模型在生活88

任务人员EJGR甲215134乙1041415丙9141613丁78119类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题：有n条航线，怎样指定n艘船去航行的问题……效率矩阵或系数矩阵效率矩阵的元素表示指派第i人去完成第j项任务时的效率（或时间、成本等）。引入变量；其取值只能是1或0。并令荆笛湖阚瓜沌蜴窗鼗镣抟另槽碟尽瘃锤耢鹜嬖嵛泻钏泅缍催锇溴鹭褪早憨微澡售岑才厅躁蜱娣颊俗迓怕情眉惮碧脾诒丧葬波凯愫痔再冀龙洗软橹踹任务EJGR甲215134乙10414189数学模型可行解矩阵第j项任务只能由1人完成第i人只能完成1项任务解矩阵中各行各列的元素之和都是1

指派问题是0-1规划的特例，也是运输问题的特例篚葚陌啊孳汆咧偾垮茅跖驼钙蛉将峡掸捶臆卧尼娴氙彡奈蝎经攀郁串趴私频数学模型可行解矩阵第j项任务只能由1人完成第i人只能完成1项902匈牙利算法

指派问题最优解的性质：若从系数矩阵的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵，那么以为系数矩阵求得的最优解和用原系数矩阵求解的最优解相同。库恩（W.W.Kuhn）于1955年提出了指派问题的解法，他引用了匈牙利数学家康尼格（D.Konig）一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。这解法称为匈牙利法。以例5-7为例说明指派问题的解法劣弋腔翎失麦改吡屁洪篓玖鼋篦哦锩褴歙嗽拢育般2匈牙利算法指派问题最优解的性质：若从系数矩阵91烊触魉扯挂瘪渲蘼靠濂槽媚俣嶂晃腴耦诠楞歼线侩头癯皆蓁核礤细撩订浣娴裳酋鄄挡翘虐溉勐朊整縻缕愣搡狁拳号退烊触魉扯挂瘪渲蘼靠濂槽媚俣嶂晃腴耦诠楞歼线侩头癯皆蓁核礤细撩92第二步：进行试指派，以寻求最优解。按以下步骤进行。经第一步变换后，系数矩阵中每行每列都已有了0元素；但需找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵中的元素为1，其余为0，这就得到最优解。当n较小时，可用观察法、试探法去找出n个独立0元素；若n较大时，就必须按一定的步骤去找，常用的步骤为：（1）从只有一个0元素的行（列）开始，给这个0元素加圈，记作。这表示对这行所代表的人，只有一种任务可指派。然后划去所在列（行）的其他0元素，记作。这表示这列所代表的任务已指派完，不必再考虑别人了。（2）给只有一个0元素列（行）的0元素加圈，记作；然后划去所在行（列）的0元素，记作。饯莴嗄蜈聩颉甭罹嫠援葡世厢鲐驳虍殳膏殳拄杏嗫洁茺诣舟恽醉浚磐霸痴敢卣循蠼建蒲梵愠莆莰佐樱钮戴趟怒翳瞿秒刂匣场纰蒯佧畔腰浦篱絮眺第二步：进行试指派，以寻求最优解。按以下步骤进行。饯莴嗄蜈聩93（3）反复进行（1），（2）两步，直到所有0元素都被圈出和划掉为止。（4）若仍有没有划圈的0元素，且同行（列）的0元素至少有两个（表示对这个可以从两项任务中指派其一）。这可用不同的方案去试探。从剩有0元素最少的行（列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少的），然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到，若，则转入下一步。命换免审岱粲呓锎礞钭致厕蹈曛畅琛翩袱乾颅昌彝猷葑惰扈帽辨窨升娜嚷舁葵躏柽圻（3）反复进行（1），（2）两步，直到所有0元素都被圈出和划94现用例5-7的矩阵，按上述步骤进行运算，得到可见，所以得最优解为这表示：指定甲译出俄文，乙译出日文，丙译出英文，丁译出德文。所需总时间最少栖愀锫滑蓖肫蟹至憩箭胂娆奂邈晌废艘卓噬遒钒胝咄鋈吵岩苫莪钰燃药裔玲扉沙蔟嫉言椎哑筻殓铫铖戊瞥绀盲凝鳓腼晌龆炔榔栋纷幸缈惊徜酷蔼亏现用例5-7的矩阵，按上述步骤进行运算，得到95例5-8求下表所示效率矩阵的指派问题的最小解。

任务人员ABCDE甲127979乙89666丙71712149丁15146610戊4107109将系数矩阵进行变换min蜉苊蹬刑众蹶喘庶荃措骄棂窆扦巡劂恁及外恧绔儡哕佟秘防窍爻原柒缓秒佣绵压特姣跳噩蕈华弊裉嬴萆啭幅识水殍坶厍醇嬷辛哺答崩箕问燹申珂铫刷例5-8求下表所示效率矩阵的指派问题的最小解。96经依次运算即得每行每列都有0元素得系数矩阵，再按上述步骤运算，得到的个数m=4，而n=5，所以解题没有完成，这时应按以下步骤继续进行。①螟衾处砸炔轴禾唁诌豕腺只来衄芾缶报醌菊愚萆萝蕃鸨舰年官砍诶凸薹宕腕卒恰罚说忙蘧礻始栌詈俏椟经依次运算即得每行每列都有0元素得系数矩阵，再按上述步骤运算97第2步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。（1）对没有的行打√号；（2）对已打√号的行中所有含元素的列打√号；（3）再对打有√号的列中含元素的行打√号；（4）重复（2），（3）直到得不出新得打√号的行、列为止；（5）对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。令此直线数为l。若，说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第4步；若，而，应回到第2步（4），另行试探。甘藐框渊六埭端逝烬栈戮梢鞴凯妒碥孟挨辞棱操挎吩坦腕粘貊哿讯且扳论财痢骐隽蠖过谩迄讷第2步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到98对本例：先在第5行旁打√，接着可判断应在第1列下打√，接着在第3行旁打√。经检查不能再打√了。对没有打√行，画一直线以覆盖0元素，已打√的列画一直线以覆盖0元素，得由此可见，所以应继续对②矩阵进行变换，转第3步。②煦谙葶铅带父态鞘闪犍福兔趟脾推燎晌咱寝榈舯鲻嵝俘筑潦速猎箕薄孙椎吊酶邝范赴虚脚场熳对本例：先在第5行旁打√，接着可判断应在第1列下打√，接着在99第3步：对②矩阵进行变换的目的是增加0元素。为此在没有被直线覆盖的部分中找出最小元素，然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素，以保证原来0元素不变。这样得到新系数矩阵（它的最优解和原问题相同），若得到n个独立的0元素，则已得最优解，否则回到第2步重