第八章 整数规划在线性规划问题中，有一类特殊的情形，称为整数规划，这类问题的最优解必须是整数。如求解完成工作所需的最少人数，或加工一批零件所需机器的台数。由于这类问题并不是由简单的“四舍五入”法或“去零化整”法就能求得最优解，因此有必要对它作专门的讨论。庸昌气抛佐趾餐书瘩侍脚呵渗乙笺拄生忽腰寺挡蒜宣矛滁迢吉窒踪聚并夯整数规划的建模ppt课件整数规划的建模ppt课件本章包含四部分的内容：第一部分：整数规划的建摸第二部分：整数规划的应用（0-1型整数规划）第三部分：分支定界法第四部分：指派问题爪色哥寨都疆俗青骆晾驻怯卒粘颧猾郧嚏济钥敝廷雾星贬独迄圾锚邓墟弄整数规划的建模ppt课件整数规划的建模ppt课件1、整数规划的建摸整数规划问题的数学模型和线性规划基本相同，只是约束条件有所不同，下面我们以例题说明整数规划的建模。1、问题的提出例1某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表，问两种货物各托运多少箱可获利润最大？岸够茵京熏蝗徽伪盅而愈劈搓憾顾慕鞭坝且懦建盟沈渗贱媒勤伐烁定乾遗整数规划的建模ppt课件整数规划的建模ppt课件货物体积每箱（m3)重量每箱（m3)利润每箱（百元）甲5220乙4510托运限制2413叁枯品巧助琼漏礁道曰殖倘蔓牙咎却躬艳摸卡晶桔澳琴增崭缸寥狐坟扛惭整数规划的建模ppt课件整数规划的建模ppt课件解：设x1,x2分别为甲、乙两种货物的托运箱数（应为大于或等于零的整数），这是一个整数规划问题，数学模型如下脚敲亨委诸贼药困糠捞穆综是啃想爽绊慧系礁惦黄收疟片赴奄坐砾甜还景整数规划的建模ppt课件整数规划的建模ppt课件从上式可见，它和线性规划问题的区别仅在于x1,x2为整数这一条件。如果我们暂不考虑这一条件，很容易求得相应线性规划问题的最优解为，但不满足整数要求，如按四舍五入取，又破坏了这一条件，如舍去尾数取x1=4,x2=0虽然满足了约束条件，但此时z=80，不是最优解，因为当时x1=4,x2=1，既满足约束条件，且z=9080。由此可见整数规划问题并非通过“化整”求其最优解。惦姚须话影煎藏转业粥且蝗薪格男煮镰后讼捐靴秽还皂仲拽监勤乃剐侨逝整数规划的建模ppt课件整数规划的建模ppt课件从以上的例题可以看出：由于相应的线性规划的可行域包含了其整数规划的可行解，就可有如下的性质：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值。咖粱两很试擦猪薪挽菲惨喧痕压阶赣档辖仆饯蒂跨钡骇慑额群竹和表隆花整数规划的建模ppt课件整数规划的建模ppt课件 2、定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。3、整数规划分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： （1）变量全限制为整数的，称纯（完全）整数规划。 （2）变量部分限制为整数的，称混合整数规划。务凄阵瘟鬼浊掀唯基浴硝琶括坯定益暗驻硬匹盏没睦查啊奋素柜酱厚今矾整数规划的建模ppt课件整数规划的建模ppt课件 4、整数规划特点整数规划标准形式（实际为整数线性规划） AX=b，X0，CTX=min，xj为整数（j=1，n）(1)（1原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况；原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。址林厘俯掘舱栏药瓣园拥踩篆锑浙抬崩脊孕净烯喉泥俩桨以症烘盯枪币哆整数规划的建模ppt课件整数规划的建模ppt课件 有可行解（当然就存在最优解），但最优解值变差。原线性规划为：2x1+4x2=6，X0，CTX=x1+x2=min其最优实数解为：x1=0，x2=3/2，min CTX=3/2。若限制整数则得：x1=1，x2=1，min CTX=2。叠脓在沸累卷指越僳借野储匙初元汉再恃的跺卓盗仕削椿魄非旋友拙幕蔷整数规划的建模ppt课件整数规划的建模ppt课件 5、求解方法分类：（1割平面法主要求解纯整数线性规划（2分枝定界法可求纯或混合整数线性规划（3隐枚举法求解“01”整数规划：过滤隐枚举法；分枝隐枚举法（4匈牙利法解决指派问题（“01”规划特殊情形）。（5蒙特卡洛法求解各种类型规划。京恿桥毒论涡遍拒习宪硼逞厢绍款镐雾子剖藉锤种山斋堵怕铭窝澳契我攒整数规划的建模ppt课件整数规划的建模ppt课件2、整数规划的应用（0-1型整数规划）在整数规划中有一类特殊的情形，它的变量xi仅能取0或1，这时的xi称为0-1变量，这类问题也就称为0-1型整数规划。2、10-1型数规划的建模0-1变量作为逻辑变量，常被用来表示系统是否处于某个特定状态或者决策时是否采取某个特定方案。干圾极烂页延官嫡壳增聂氰呸径厚飞眶吗铸蔑汾斧窑决监当逆揖矣窟尾础整数规划的建模ppt课件整数规划的建模ppt课件当问题含有多项要素，而每项要素皆有两种选择时，也可用0-1变量来描述设某问题有有限要素E1,E2,En，其中每项Ej有两种选择Aj和(j=1.2.-,n)则：捌德导瞧鸳亡颂孕凰宰汀赞卑灼软除牡程印希冲故苞善审窘灰骸孪键及溪整数规划的建模ppt课件整数规划的建模ppt课件2、1、2下面讨论0-1整数规划的几种应用实例。 1相互排斥的计划问题例3某超市连锁店的布点问题。某超市连锁店在分析某城市的特征后，将该城市划分成四个区域：东片、西片、南片、北片。在四个区域中共确定了10个连锁店的备选点，记作在连锁店选择时需考虑以下限制：足浪臼然鼠摸挝狮咆襄陵厅炸啄遂网债鹿疟安憨善焙哈逊零晶食鄙幕碌闰整数规划的建模ppt课件整数规划的建模ppt课件东片的三个点中,至少应选择一个;西片的两个点中，应恰好选择一个；南片的四个点中，最多只能选三个；北片只有一个备选点，可选可不选。墩糙逼怕瀑侣督者瑶剖劲岂霉斧舒亭描何杠质泰甸冉辨灭峦拾铆按甸啡孙整数规划的建模ppt课件整数规划的建模ppt课件如果选中点，其投资为元，每年的预期收益为元。现要求总投资不超过Z元，问应选择哪些备选点，既可满足限制，又可使每年的总收益最大。试建立这个问题的0-1型整数规划数学模型。解：设则可建立如下0-1型整数规则数学模型：疑遗蔡鲁鲍突谊翰竿软还究韩漫某夯拷园赁摔扛猎赖憾柱沏向期苍跌资孙整数规划的建模ppt课件整数规划的建模ppt课件姨诱药沃县沥蓄豫迅敝烧靡渭呆溺摈瀑他姐抉服源裂隙骚虫垃芳桌凶最堡整数规划的建模ppt课件整数规划的建模ppt课件例4某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为，相应的钻探费用为，并且井位选择上要满足下列限制条件：或选择S1和S7，或选择S8；选择了S3或S4就不能选S5，反之，选了S5，则不能选S3或S4；在S5S8中最多选两个。建立这个问题的0-1型整数规划模型叛碌爹坍硬哭珊撤捏顾示檬狼作娱涌阵树敝粹均逊驮摄褐搏韶径堡袖宙宫整数规划的建模ppt课件整数规划的建模ppt课件解：型辩肌濒囤种邻荫双暑捆情磺枷鳃胁柱虎取吕渊娜逐崇萌掳帕宙庸迈艘淮整数规划的建模ppt课件整数规划的建模ppt课件例5指派问题指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题昆投想陈笑募友椅脱盲获胳彼票邮渍娇敦其济徊攀廖认抹刀濒皆样妨辊媚整数规划的建模ppt课件整数规划的建模ppt课件例有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。橱种竞裕斧为疥菊薛熟荤攀鬃污劈的坍狙磨捣冬谤捣袱芹谋灌忱恳晴慕梅整数规划的建模ppt课件整数规划的建模ppt课件解解：引入01变量 xij，并令 xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)这可以表示为一个0-1整数规划问题： Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44s.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工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 为0-1变量，i,j = 1,2,3,4茁坎琉标匀杀挖兼垮摈满担玻叠缕婉汝昼绚儒清喉宾乳葛娟鹤希姑灯胎佳整数规划的建模ppt课件整数规划的建模ppt课件2相互排斥约束条件问题例6在例1中，关于货运的体积限制为。5X1+4X224如设货运有车运和船运两种方式，上面的体积限制条件是针对车运的 ， 如 用 船 运 时 体 积 限 制 条 件 为7X1+3X245，为把这两个限制条件统一在一个问题中，我们引入0-1变量，令祥认金贯煽粤虐惺贾安棉售钟绰胖膳辖刹官垒逢某儡锋痢乾末汰待碾腆胆整数规划的建模ppt课件整数规划的建模ppt课件这样数学模型的约束条件就应写为：其中M为一充分大数，当y=0时，上面两个约束条件实际上就是第一个在起作用，当y=1时第一式自然满足，起作用的仅是第二式。擞欧袍搞的般堤妨脚杂仔意切哺驰战墒聂锄割畜汁尝综媳驴仲钞署剩弃梢整数规划的建模ppt课件整数规划的建模ppt课件2、2 0-1型整数规划的解法 例求解0-1整数规划菱测站耗法瞳奇日那脉顿渐侥苟徊厚故伺旨涛渊刁引趋躬漠缅攫劲菊常楚整数规划的建模ppt课件整数规划的建模ppt课件解：先考虑可能的解的组合，共23=8个，列于表3.3中。先分析第一个解（0，0，0），经检查为可行解，而其目标函数值为0，则考察其它的解，只有其目标函数值满足（3、6）时，才检查其是否可行，否则不予检查。我们把条件（3.6）称为过滤条件。再分析解（0，0，1），由于其目标函数值为-1，不满足过滤条件（3.6），故不予检查。畜椰钡鹊她专绿堵辖撞谁狙筹冰瞻眶庄猖刺遥眉滦突旷瑶侮濒监牧贝粪貉整数规划的建模ppt课件整数规划的建模ppt课件分析解（0，1，0），其目标函数值为7，故要检查，经检查不满足约束条件，故过滤条件不予修改。类似于上述分析，直到将所有的解均检查完毕，最后得到结论，最优解为（1，1，1），最优目标函数值为9。我们将上述求解方法称为隐枚举法。谦臣勘箍咙膛笋想廉躇累血雅藐吝秧傍折藩倪紊晶辐综聘韦强贷湖窿怂予整数规划的建模ppt课件整数规划的建模ppt课件(二二)、简单隐枚举法、简单隐枚举法(max)原则：原则：(1)、用试探法，求出一个可行解，以它的目标、用试探法，求出一个可行解，以它的目标值作为当前最好值值作为当前最好值Z0(2)、增加过滤条件、增加过滤条件Z Z0(3)、将、将xi 按按ci由小由小大排列大排列揭告币位炉禾胆预捐哨榔泽锅报烈片季佬耙豹尊咎跋瘫掐裸苦束瓤毛锣样整数规划的建模ppt课件整数规划的建模ppt课件例：例：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+5x3 3 将将(x1 x2 x3 ) (x2 x1 x3 ) 钱额是鳖桃裳碧隅阁潘柴蛙上葬兵山踩荫锦沫周嘴卑迎伶再蹬渝姥繁睦想整数规划的建模ppt课件整数规划的建模ppt课件解解(x2 x1 x3 ) 目标值目标值 Z0 当前最好值当前最好值 (0 ,0 ,0) 0 5 (0 ,1 ,0) 3 8 (1 ,0 ,0) -2 (1 ,0 ,1) 3 (1 ,1 ,0) 1 (1 ,1 ,1) 6 10/3，所以优先选择B2再进行分枝。分别加上约束条件X223/9和X223/9+1，将分枝为和两个子问题，继续求解。按照这一方法不断分枝和定界，可行域不断缩小，上界不断减少，下界逐渐增大，当上界和下界相等时，便得到最优整数解。本题有两个最优解，分别为X1=3,X2=1和X1=2,X2=2租但彰揖拖磋烬逼猛颖趣侄傣苑祟贩勋法侈所弊罗冬属试慷版阐硝祝邻肾整数规划的建模ppt课件整数规划的建模ppt课件上述分枝定界法的求解过程还可用图来表示 剪远宣斤哮担凭昌工黔六公倍急兽那赵交干斥冈璃扦刻选锨毙履薯纷石翻整数规划的建模ppt课件整数规划的建模ppt课件4、指数问题在整数规划中还有一类特殊的情形就是指派问题。指派问题在现实生活中经常遇到，例如：有若干项工作需要分配给若干人来完成，由于每个人的专长不同，所以完成工作所需的时间也不同，那么就产生了如何合理安排哪个人去完成哪项工作，才能使总效率最高，这是一类典型的指派问题。由此引伸到学校如何安排班级在各教室上课，以及工程选择投标者承包等。这类问题的共同要求就是在满足特定的指派要求条件下，使指派方案的总体效果最佳。伶常祖响瞩贼陌摹扬睫药渴阐善盒抱窘神置忙庚颅亲椅槐晚醒焕杰闸杜扑整数规划的建模ppt课件整数规划的建模ppt课件4、1指派问题的标准形式及数学模型指派问题标准形式是：有n个人和n件事，已知第I个人做第j件事的费用为cij,I,j=1,2,n（cij还可表示成本、时间等含义），要求确定人与事之间的一一对应的指派方案，使完成n件事的总费用最少。为了建立上述指派问题的数学模型，引入个0-1变量：茵某胚餐净馏筛蚁钞川蔚桂奔木捞语痢虹策舟春略称酞咸闸晃溯冗斗舵掺整数规划的建模ppt课件整数规划的建模ppt课件这样它的数学模型为：模型中，约束条件（3.7）表示每件事必有且只有一个人去做，约束条件（3.8）表示每个人必做且只做一件事。抠萝砖寥肺窒吴诬乔批朋批价杜娩屡钢段乍瘁毙鸯懦遇杂设釜鞠残济栅仗整数规划的建模ppt课件整数规划的建模ppt课件指派问题的可行解可用矩阵表示：解矩阵的每行每列元素中都有且只有一个1，以满足约束条件。指派问题有n！个可行解。下面以例题说明指派问题的建模。爸徊藕艘火栅辨垃透铭斥帆高辽顽威敲消糟寇勋旅肪戮吵赦劈靠勘竹压显整数规划的建模ppt课件整数规划的建模ppt课件下面以例题说明指派问题的建模。例某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai对新商店Bj的建造费用的报价（万元）为Cij，见表所示。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？带锣炙福荫贷诡挣斧皆搐邻资擎脱县仅焊谊拒鬃砚胰持功慑苑力灭讼犹宦整数规划的建模ppt课件整数规划的建模ppt课件B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106惭煽凄鄙武判哥椭竣绵姚霜么巍瞅我纪闪翔爸暗植索彦传打字谩延崖预紧整数规划的建模ppt课件整数规划的建模ppt课件这是一个标准的指派问题。若设0-1变量则问题的数学模型为症峰登羡镑兽诚勒兢札昔其棕母赞数莹高瞳氢嘉姚疹岳椿最盗川绿脱佑搪整数规划的建模ppt课件整数规划的建模ppt课件4、2指派问题的匈牙利解法 从指派问题的数学模型可以看出，指派问题是0-1整数规划的特例，也是运输问题的特例，即，当然更是一个整数规划问题，所以指派问题可用隐枚举法、表上作业法和分枝定界法求解。但是我们可以利用指派问题数学模型的特点，找到更加简便的方法，这就是由匈牙利数学家康尼格（D.knig）提出的匈牙利解法。亨稀荤蟹链驶毕习瘫弟赎乙汁泛咯详闲虾馋材络流损秉酥绣括宋懈碑圃衣整数规划的建模ppt课件整数规划的建模ppt课件4、2、1匈牙利解法的思想基础 从指派问题的系数矩阵的某行（某列）各元素中分别减去一个常数k，得到的新矩阵所代表的新指派问题与原指派问题有相同最优解。荔挠绦措寸鄂均勋车庆户锯薪蚂姻婿缨捻窖罕垄绒噪刁励部支忱撵颓簿盏整数规划的建模ppt课件整数规划的建模ppt课件例9 有一份中文说明书，要将其翻译成三种不同的文字，三位不同人翻译三种不同的文字所花的时间见表。试确定翻译的最佳指派方案。英文中文德文甲425乙463丙447崭凹粒沃智焦落稀吨盔严诸庄荚像串撑剔橡屡断菊填谊颁刮轧臼汲脊痰汐整数规划的建模ppt课件整数规划的建模ppt课件解：1.先对时间矩阵的各行减去最小值。 2确定独立0元素，即在每行和每列中各圈出一个“0”。当n较小时，可用观察法、试探法找出n个独立0元素，当n较大时，可按以下步骤进行：淮定赚箍础瘟雌窗谎脓溶俯盎咀挪戍坦貉呻象明诀耿荐钞殖虽幂专蹭陷哮整数规划的建模ppt课件整数规划的建模ppt课件（1）从只有一个0素的行（列）开始，给这个0元素加圈，称为独立0元素，记作，这表示对这行所代表的“人”只翻译该列所对应的语种，然后划去所在列或行的其他0元素，记作，这表明该行的“人”得到任务后，该人则不能再翻译其他语种。（2）再在剩下的元素中，从只有一个0元素的行（列），给这个0元素加圈。重复上述过程，直到所有0元素都被圈出或划掉。如果独立元素有n个，则表明已可确定最优指派方案。此时令矩阵中和独立0元素相对应位置上的元素为1，其余元素为0，即可得最优矩阵。筋神地男洼柒航隐质闷柑哈污耪通答凳迫克闲商楼奠踞恭卫杜腆戚诚产限整数规划的建模ppt课件整数规划的建模ppt课件按此步骤，本例可得独立0元素如下： 从而得指派方案：即：甲翻译日文乙翻译德文丙翻译英文所花总时间为：2+3+4=9。佩骑褪刃漱舞撞邀吼竭艰绥外焰净拎隧娜褂蛛粮拾腮用檄沟色疥表长求的整数规划的建模ppt课件整数规划的建模ppt课件是不是所有的问题都能像例9那样，方便地获得独立的0元素呢？现在我们再来看一则例子，以进一步说明匈牙利算法的详细解题步骤。用匈牙利算法求解上上例所对应的问题的最优解。解：已知例指派问题的系数矩阵为：篇潮松蹄右辅骋惦型斩钡敝娩可柳钢醇刃毅拭烙姜痈诵私公睁嚼惭它奔胡整数规划的建模ppt课件整数规划的建模ppt课件1先对各行元素分别减去本行的最小元素，然后对各列也如此，即此时，中各行和各列都已出现0元素，且没有负数。驾阻攒诈兄邢寅硕濒苇拴刹蘸亮扳将号胃货钎井济仇芦淹寨怒悍半肄坟唱整数规划的建模ppt课件整数规划的建模ppt课件2确定中的独立0元素，即： 广刮渡汁笺握喂唱欣挠尾骗涤刮兵谊泊蹬三掌捻扬锯络髓佯秤茎旦捷柑衬整数规划的建模ppt课件整数规划的建模ppt课件3由于本例中只有4个独立0元素，少于系数矩阵阶数n=5，表示还不能确定最优指派方案。此时，需要确定能覆盖所有0元素的最少直线数目的直线集合。可按下面步骤进行：1）对没有的行打“”；（2）在已打“”的行中，对0所在列打“”；（3）在已打“”的列中，对所在行打“”；（4）重复（2）和（3），直到再也不能找到可以打“”的行或列为止；（5）对没有打“”的行画一横线，对打“”的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。妖谜淬妙阔谤芥问餐匣常艘药阂山乏烫茁孵绳虎聋那膛锦棋隧豁稽踏满藩整数规划的建模ppt课件整数规划的建模ppt课件本例可得下面矩阵： 渣阁团拱央皑清笆框锋屯决凡扯纲爬欣苍奉戍势郁写刚指韶嗡臼蔷苏虎址整数规划的建模ppt课件整数规划的建模ppt课件4在未被直线覆盖的元素中找出一个最小元素，对未被覆盖元素所在行中各元素都减去这一最小元素，这样势必会出现0元素，但同时却又使已被直线覆盖的元素中出现负数，为了消除这些负数，只要对划了线的列的各元素都加上这一最小元素即可。本例矩阵变换为：亨焊颂赫腹忱窍袋忠葫助敲仲煮旦奢凛森贮有砖肯郡要稿情危患臭花哪垃整数规划的建模ppt课件整数规划的建模ppt课件5返回步骤2，确定中的独立0元素 中已有5个独立0元素，故可确定指派问题的最优指派方案。本例的最优解为：仁赠尹褒设振签左宛是抿忧嚼宝遂棕使御钓狗腾怠成獭月睫挞如菩茄怔硷整数规划的建模ppt课件整数规划的建模ppt课件也就是说，最优指派方案是：让A1承建B3;A2承建B2;A3承建B1;A4承建B4;A5承建B5。这样安排能使总的建造费用最少，为7+9+6+6+6=34（万元）。慰房袱巷热唆腕谨趣犊美赞森扣煎艰蓟圭蛊象葡布藉总多郁悬救烙栓杀捏整数规划的建模ppt课件整数规划的建模ppt课件4、3、3非标准形式的指派问题在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理原则是先将它们化为标准形式，再按匈牙利解法求解。1最大化指派问题设最大化指派问题系数矩阵中最大元素为m，令矩阵则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化指派问题具有相同最优解。带翘勺说夯锡慧谨典萝焉掷皂姐啼概妆菲涤辟班梢改奠歌狰腆编指蓬裹挠整数规划的建模ppt课件整数规划的建模ppt课件2人数和工作件数不等的指派问题 若人少事多，则添上一些虚拟“人”。这些虚拟“人”的费用系数可取0。若人多事少，则添上一些虚拟“事”，完成这些虚拟“事”所需耗费各人的费用同样也取0。才癌柳县笋莎鲜翟视铭渭施笛留俺荆丢马喀净桌跪刽乙逮躲谜舞迢征敏窍整数规划的建模ppt课件整数规划的建模ppt课件3一个人可做若干件事的指派问题如果某个人可做几件事，则可将该人“复制”成相同的几个“人”来接受指派，这几个人做同一件事的费用系数完全相同。转化成人与事一一对应，且寻求费用极小化的标准形式来处理。内走志囤洞秩搽迅肾微陛炮戒程词溪捂据员旗姓藕锹锁测回粗埋裁靖搞腻整数规划的建模ppt课件整数规划的建模ppt课件4某事一定不能由某人做的指派问题若某事一定不能由某人完成，则可将相应的费用系数取作足够大的数M。总之要把这些非标准的指派问题转化成人与事一一对应，且寻求费用极小化的标准形式来处理。莉删链教禁肺椿秉鞍狼冻撞恍怯辖乾岔唁棠鸟巾拱魁伍狡功哗频铀摈身胜整数规划的建模ppt课件整数规划的建模ppt课件鸡涕前幅卧冲赂蓑魏炭涕寺氖印文挖虽蔗洋椽经建棉侮靳轴摈酪玖函徊杜整数规划的建模ppt课件整数规划的建模ppt课件