第七章整数规划 S7.1概述 我们知道线性规划最优解的基变量取值可以带小数，但是一些实际问题，常常要求基 变量的取值必须是整数例如，所求的解是机器的台数、完成工作的人数、从A地运往B 地的货车数等等，带小数的解就不符合要求初看起来，为了满足解必须是整数的要求，只 要把线性规划带小数的最优解“舍入化整”就可以了，但这样的解不可能是最优解.因此 对全部或一部分决策变量的取值要求为整数的线性规划问题，必须有能够产生整数解的 算法这类问题称为整数规划问题. 整数规划问题中如果所有的变量都限制为非负整数，就称为纯整数规划或全整数 规划如果只有一部分变量限制为整数，则称为混合整数规划整数规划中变量取值限制 为0或1的.此变量歇为01峦量.全部变量都是0-1变量的问颗.称为0-1规问题 由于整数规划的算法很繁，在电子计算机上求解花费机时多，因此在解变量取值要求 为整数的问题以前，最好能估计一下不用整数规划求解而用线性规划的解凑整时，目标函 数值损失的上限如果损失不大就可以不用整数规划而用线性规划求解再凑格.以免得不 偿失 我们称最优非整数解为连续解，它的目标函数为：若一个连续解凑整的目标函数 值为，很明显，对一个求极大目标函数值的整数规划问题，。一，就是上述目标函数值 损失的上界 §7.2整数规划问题的图解法 为了帮助理解整数规划问题求解方法先讨论下列简单向题 例1.某工厂有资金13万元用于购置新机器，可在两种机器中任意选购.已知机器 每台购置费2万元B为4万元.该工厂维修能力只能维修7台机器B:若维修机器A,1 台折算2台机器B.已知1台A可增加产值6万元，一台B可增加产值4万元，问应购 置机器A和B各多少台，才能使年产值增加最多？ 解 这个问题的整数规划模型是 nax z =6r+4 满足 2x1+4r2≤13 2r1+x2≤7， 1,2≥0. 、1,2为整数 它和线性想脚不同之外只在干增加了最后一个约成条件.现在暂不考虑整数约声 用图解法求解图7-1画出两个约束条件方程及目标函数值为23的等值线，最优解是 x1=2.5.r2=2.2=23. 整数规划问题没有可行域。但有一组可行点.就是在线性规划问题的可行域内坐标为 整数的点，如图7-2中（1,2）=2,2)等很明显，我们将等值线从左下方向右上方平行 1
✂✁✂✄ ☎✂✆✂✝✂✞ §7.1 ✟✡✠ ☛✌☞✌✍✌✎✌✏✌✑✌✒✌✓✌✔✌✕✌✖✌✗✌✘✌✙✌✚✌✛✌✜✌✢✌✣✌✤✌✥✌✦, ✧✌★✌✩✌✪✌✫✌✬✌✭✌✮, ✯✌✯✌✰✌✱✘ ✙✌✚✌✗✌✛✌✜✌✲✌✳★✌✴✦ . ✵✌✶, ✷✌✱✗✌✖★✌✸✌✹✗✌✺✌✦✌✻✽✼✌✾✌✿✌❀✌✗✌❁✌✦✌✻✽❂ A ❃✌❄✌❅ B ❃ ✗✌❆✌❇✌✦✌❈✌❈, ✤✌✥✌✦✌✗✌✖✌❉✌❊✌❋✌●✰✌✱. ❍✌■✌❏✌❑, ▲✌▼✌◆✌❖✖✌✲✌✳★✌✴✦✌✗✰✌✱, P ✰✌◗✏✌✑✌✒✌✓✌✤✌✥✌✦✌✗✌✔✌✕✌✖ “❘✌❙✌❚✌✴” ❉✌✢✌✣ ▼, ✧✌❯✌❱✗✌✖✌❊✌✢✌❲★ ✔✌✕✌✖. ❳✌❨, ❩❭❬❭❪❭❫✩ ❪❭❴❭❵❭❛✙❭✚❭✗❭✛❭✜✰❭✱❭▲❭✴✦❭✗❭✏❭✑❭✒❭✓✭❭✮, ✲❭✳❭❜❭❲❭❝❭❞❭❡✴✦❭✖❭✗ ❢✌❣. ❯✌❤✌✭✌✮✌✐✌▲❦❥✌❧✌♠✌♥♦✭✌✮. ✴✦❭✒❭✓✭❭✮q♣r✶❭s❭✷❜❭✗❭✙❭✚❭t❭✉❭✈▲❭✇❭①❭✴✦ , ❉✐❭▲③②❭❥❭❧❭♠❭♥ ❫③④❥❭❧ ♠✌♥; ✶✌s✌P❜✩ ❪✌❴✙✌✚✌✉✌✈▲✌✴✦ , ⑤✌✐✌▲⑦⑥✌⑧✌❥✌❧✌♠✌♥; ✴✦✌✒✌✓ ♣✙✌✚✌✛✌✜✌✉✌✈ ▲ 0 ❫ 1 ✗ , ❨✙✌✚✐✌▲ 0–1 ⑨✌⑩, ❬✌❪✙✌✚✌t★ 0–1 ✙✌✚✌✗✭✌✮, ✐✌▲ 0–1 ♠✌♥✌❶✌❷. ❸❺❹✴✦✌✒✌✓✌✗❢✌❣✌❻✌❼, ❽❿❾❺➀✌➁❢✸✌➂✌✱✖✌➃✌➄✸✌➅✌➆, ❳✌❨✌❽✖✌✙✌✚✌✛✌✜✰✌✱ ▲✌✴✦✌✗✭✌✮✣✌➇, ✔✌➈✌❲✌➉➁✌✩✌➊❊✌➋✴✦✌✒✌✓✱✖✌➌✌➋✌✏✌✑✌✒✌✓✌✗✌✖✌➍✴✌➅, ➎➐➏✌➑ ✦✌✜✌➒✌➓✌✗➂✉ . ✶✌s➒✌➓✌❊✌➔✌❉✌✢✌✣✌❊✌➋✴✦✌✒✌✓✌➌✌➋✌✏✌✑✌✒✌✓✱✖✌→✌➍✴, ✣✌➣✌↔✌❊ ↕➓ .☛❭☞✐ ✔❭✕✇❭✴✦❭✖▲➛➙❭➜❭➝, ➞ ✗ ➎➟➏❭➑✦ ▲ zc; ➠❭✩❭➡❭➢❭➤✖❭➍✴ ✗ ➎➟➏❭➑✦ ✜ ▲ zr, ❻❿➥❺➦, ❩ ✩✌➡✌✱✌➧➔ ➎➐➏✌➑✦✌✜✌✗✴✦✌✒✌✓✭✌✮, zc − zr ❉ ★✌➂✌➨➩➎➐➏✌➑✦✌✜ ➒✌➓✌✗➂✌➫. §7.2 ➭✡➯✡➲✡➳✡➵✡➸✡➺✡➻✡➼✡➽ ▲✌▼✌➾✌➚✌➪✖ ✴✦✌✒✌✓✭✌✮✌✱✖✌➶❣ , ➹✌➘✌➴✌➊✌➷✌➬✌➮✌✭✌✮. ➱ 1. ✃ ✿✌❐✌❜✌❒✌❮ 13 ❰✌Ï➋❹✌Ð✌Ñ✌Ò✸✌✹, ✢ ❽✌Ó✌Ô✌✸✌✹❿♣❺Õ✌Ö✌×Ð . Ø✍✸✌✹ A Ù✺Ð✌Ñ➄ 2 ❰✌Ï,B ▲ 4 ❰✌Ï. Ú ✿✌❐✌Û✌Ü✌❲✌ÝP❲✌Û✌Ü 7 ✺✸✌✹ B; ➠ Û✌Ü✸✌✹ A,1 ✺✌Þ❢ 2 ✺✸✌✹ B. Ø✍ 1 ✺ A ✢✌ß✌à✌❞✌✜ 6 ❰✌Ï, ✩ ✺ B ✢✌ß✌à✌❞✌✜ 4 ❰✌Ï, ✭✌áÐ Ñ ✸✌✹ A â B ã✌➆✌ä✺ , å ❲✌æ✌ç✌❞✌✜✌ß✌à✌✔➆? ➝ ❯✌➡✌✭✌✮✗✴✦✌✒✌✓✌è✌é★: max z = 6x1 + 4x2 ◆✌❖ 2x1 + 4x2 ≤ 13, 2x1 + x2 ≤ 7, x1, x2 ≥ 0, x1, x2▲✌✴✦ . ➞êâ✏ê✑ê✒ê✓ê❊êëêìêíPê❽❹ßêà▼ ✔êî✩ê➡êïêðêñêò. óê❽êô❊êõêö✴✦ ïêð, ➋❭÷❭✖❣ ✱✖ . ÷ 7–1 ø❭ù❭Ó❭➡❭ï❭ð❭ñ❭ò➶❭úêû ➎ü➏ê➑✦ê✜▲ 23 ✗❭❈❭✜❭✏, ✔❭✕❭✖★ x1 = 2.5,x2 = 2,z = 23. ✴✦✌✒✌✓✭✌✮✌ý❜✌✢✌þ✌ÿ, ✧ ❜✩✁✢✌þ✁✂, ❉ ★✌❽✏✌✑✌✒✌✓✭✌✮✗✌✢✌þ✌ÿ☎✄✝✆➏✌▲ ✴✦✌✗✁✂, ✶ ÷ 7–2 ♣ (x1, x2) = (2, 2) ❈ . ❻❿➥❺➦, ☛✌☞✁✞✌❈✌✜✌✏✌❂✁✟➊➶☎✠✝✡➂➶✁☛❭þ 1
2 第七章整数规划 移动，直线的每一位置对应于一个越来趣大的目标函数值.先经过(2,2)，目标函数值为 20,到达(3,1)就不能再移动了，此时得到这个问题的最优整数解1=3,2=1，目标函 数值为22万元 王2 T2 71 7 2x1+x2=7 2=6z1+4r2=23 4 32 3 2 2+4r2=13 1 0 01234方6” 01支1古6扩4 S7.3整数规划模型举例 一般整数规划问题，其建立模型的基本思路和技巧与建立线性规划模型无多大区别， 只是对要求取整数解的变量增加一个整数约束条件. 本节着重讨论整数规划模型中部分变量是0-1变量的模型以及01规划模型.在建 立某些问题的整数规划模型时，如能巧妙运用0-1变量，将使模型容易建立。下面讨论的 几个问题足以说明这一点 一、投资问题 举例说明.某投资公可可用于投资的资金是b,有几个投资项目可供选择，项目j每 年利润是G,需要资金是a,要求建立数学模型，以选定投资项目，使每年总利润最大 解 一看，这个问题应首先选收益率台值最大的那个项目，其次选值次大的项 目，直到剩余资金少于任一个项目为止.但这样做不一定是最有利方秦， 对行项目.只有投资和不投资两种选择因此我们用01变量来表示这两种状态假 设项目j被采用，=1：否则，x=0.0-1规划棋型如下 max 满足 0≤西≤1，对一切j 工是整数 后两个约束条件保证了不是0就是1
2 ☞✁✌✁✍✏✎✁✑✁✒✁✓ ✔✖✕, ✗ ✏❭✗Ù ✩✖✘Ñ❭❩á ❹✩❭➡✖✙❭❑✖✙➔❭✗ ➎➟➏❭➑✦❭✜. ➹✖✚✖✛ (2, 2), ➎➟➏❭➑✦❭✜▲ 20, ✜✁✢ (3, 1) ❉✌❊✌❲✌→✔✁✕▼, ❨✌➅↔ ✜✌❯✌➡✌✭✌✮✗✌✔✌✕✴✦✌✖ x1 = 3, x2 = 1, ➎➐➏✌➑ ✦✌✜▲ 22 ❰✌Ï. 2x1 + x2 = 7 z = 6x1 + 4x2 = 23 2x+4x2 = 13 ✲ x1 0 1 2 3 4 5 6 7 ✻ x2 0 1 2 3 4 5 6 7 ✲ x1 0 1 2 3 4 5 6 7 ✻ x2 0 1 2 3 4 5 6 7 §7.3 ➭✡➯✡➲✡➳✤✣✤✥✤✦✤✧ ✩✁★✌✴✦✌✒✌✓✭✌✮, ✩✁✪✁✫è✌é✌✗✌✘✁✬✁✭✁✮â✖✯✁✰✖✱✖✪✁✫✏✌✑❭✒❭✓✌è❭é✁✲➆➔✁✳✖✴, P✌★❩ ✰✌✱✛ ✴✦✌✖✌✗✌✙✌✚✌ß✌à✩✌➡✌✴✦ ï✌ð✌ñ✌ò. ✬✖✵✖✶✖✷➘❭➴❭✴✦❭✒❭✓❭è❭é ♣❪❭❴✙❭✚★ 0–1 ✙❭✚❭✗❭è❭é❭✣❭û 0–1 ✒❭✓❭è❭é. ❽✖✪ ✫✌✃✌✪✌✭✌✮✗✴✦✌✒✌✓✌è✌é➅, ✶❲ ✰✁✸✌❄➋ 0–1 ✙✌✚, ✞✌æ✌è✌é✁✹✁✺✪✁✫. ➊✁✻✌➘✌➴✗ ✼ ➡✌✭✌✮✌❖✣✁✽ ➥❯✌✩✂ . ✾❀✿❂❁❀❃❀❄❀❅ ❆ ✵✽ ➥ . ✃✖❇❒✖❈✖❉❭✢❭➋❹❇ ❒❭✗❭❒❭❮★ b, ❜✼ ➡✖❇❒✖❊ ➎ ✢✖❋×✖●, ❊ ➎ j Ù ç✁❍✁■★ cj , ❏✌✰❒✌❮★ aj , ✰✌✱✁✪✁✫✦✁❑✌è✌é, ✣ ×✁▲✁❇❒✁❊ ➎ , æÙç✁▼✁❍✁■✌✔✌➔. ➝❖◆✌✩✌■, ❯✌➡✌✭✌✮✌á✁P✌➹✌×✁◗✁❘✁❙ cj aj ✜✌✔✌➔✌✗✁❚➡ ❊ ➎ , ✩✁❯✌× cj aj ✜ ❯➔✌✗✁❊ ➎ , ✗✁✜✁❱✁❲❒✌❮ä ❹ Õ✌✩✌➡❊ ➎➐▲✁❳. ✧✌❯✌❱✁❨❊✩✁▲✌★✔✌❜✁❍✌➶✁❩. ❩ j ❊ ➎ , P❜❇ ❒ â❊❇ ❒ Ó✌Ô✌×✁●, ❳✌❨☛✌☞✌➋ 0–1 ✙✌✚❑✁❬✁❭✌❯✌Ó✌Ô✁❪✁❫. ❴ ❵✁❊ ➎ j ❛✁❜➋ ,xj = 1; ❝✌⑤,xj = 0. 0–1 ✒✌✓✌è✌é✶✌➊: max z = Xn j=1 cjxj ; ◆✌❖ Xn j=1 ajxj ≤ b, 0 ≤ xj ≤ 1, ❩ ✩✁❞j, xj★✌✴✦ . îÓ✌➡✌ï✌ð✌ñ✌ò✁❡✁❢✌▼ xj ❊★ 0 ❉ ★ 1
$73鉴性规划模整举例 3 对投资间题不可以考虑以下两种情况 一如果一组投资不目是互相中斥的，即在一组投资不目J中，至多能选择一个不 目，此时要对上述模型增加一个约束条件： 1 而取消≤1，因前式已满足后式 仁、如果只有在选择投资不目的条件下，才能考虑是否选择不目k,则要增加一个 约束条件x≤1.此式表示当=0时，工必须为0.即如果不选择1，必不能选择k.当 x1=1时，xk可等于0，也可等于1，即选择1后，k可被选择也可不被选择 二、在p个则束条件中至少要满在k个则束条件 用下式表可P个约束条件 ay≤6i=1.2n j=1 设是0-1变量.如果第i个约束条件是k个约束条件中的1个，=1：否则，=0， 对p个约束条件的每1个约束条件都加进，使之成为： 盒sA+-a=1 0≤h≤1，是整数 M是很大的数在求出数米模型的解后，如=1，第个约束条件是有效的：如 班=0，则第i个约束条件的右端值是：+M,这是一个很大的数，使此约束条件不可能有 约束力（成为多 2 如果规为必须满足k个约束条件则上式中的“≥”，改为“” 时、多本跳跃下用加的标规函运题 在求产品产量的线性规划问题中，都、为生产费用分两部分，一部分求产量成线性关 大量在 大在数模型中考虑， 生求否和产量有关，但显然不是线性关大.下面我们举两个例子讨论. 例2.设某问题的线性规划模型如下： max z=C1x1+2T2+x3 满足 8r1+2x2+3r3≤400， 4r1+5r2+6x3<300 ≥0，对一切5
§7.3 ✎✁✑✁✒✁✓✁❣✁❤✁✐✁❥ 3 ❩ ❇ ❒ ✭✌✮✁❦✢✌✣✌õ✌ö✌✣ ➊✌Ó✌Ô✁❧✁♠: (✩)✻ ✶✌s✌✩✁✁❇❒✁❊ ➎➐★✖♥✁♦✖♣✖q✗ , r✌❽✌✩✁✁❇❒✁❊ ➎ J ♣, s✌➆❲×✁●✌✩✌➡❊ ➎ , ❨✌➅✌✰❩ ➂✌➨è✌é✌ß✌à✩✌➡✌ï✌ð✌ñ✌ò: X j∈J xj ≤ 1 ➌✌✛✁t xj ≤ 1, ❳➇✁✉ Ø❺◆✌❖î✁✉. (✈)✻ ✶✌s✌P❜ ❽✌×✁●✁❇❒✁❊ ➎ l ✗ñ✌ò✌➊, å ❲✌õ✌ö★✁❝✌×✁●❊ ➎ k, ⑤✌✰ß✌à✩✌➡ ï✌ð✌ñ✌ò xk ≤ xl . ❨ ✉❬✁❭✁✇ xl = 0 ➅,xk ✲✌✳▲ 0, r✌✶✌s❊×✁● l, ✲✌❊✌❲×✁● k. ✇ xl = 1 ➅,xk ✢✌❈❹ 0, ① ✢✌❈❹ 1, r✌×✁● l î ,k ✢ ❛✌×✁●✁①✢✌❊❛✌×✁●. ②✿❂③ p ④❀⑤❀⑥❀⑦❀⑧⑩⑨❷❶❹❸❻❺❻❼❹❽ k ④❀⑤❀⑥❀⑦❀⑧ ➋➊ ✉❬✁✢ p ➡✌ï✌ð✌ñ✌ò: Xn j=1 aijxj ≤ bi ,i = 1, 2, . . . , p. ❵ yi ★ 0–1 ✙✚ . ✶s❿❾ i ➡ïðñò★ k ➡ïðñò♣✗ 1 ➡,yi = 1; ❝⑤, yi = 0. ❩ p ➡✌ï✌ð✌ñ✌ò✗Ù 1 ➡✌ï✌ð✌ñ✌òt✌à✁➀ yi , æ✌ì✌✾▲: Xn j=1 aijxj ≤ bi + (1 − yi)M,i = 1, 2, . . . , p. 0 ≤ yi ≤ 1, yi★✌✴✦ . M ★ ❻➔ê✗ê✦, ❽ê✱êù ✦➁❑êèêéê✗ê✖êî, ✶ yi = 1, ❾ i ➡êïêðêñêòê★❜➁➂ê✗; ✶ yi = 0, ⑤✁❾ i ➡✌ï✌ð✌ñ✌ò✗✁✡✁➃✌✜★ bi + M, ❯✌★✌✩✌➡❻➔✌✗✌✦, æ ❨✌ï✌ð✌ñ✌ò❊✌✢✌❲✌❜ ï✌ðÝ (✾ ▲✌➆✁❲✗ï✌ð✌ñ✌ò➶✌ú). ✮❿♣✒ ▲✁s✌ä✌✰✌◆✌❖ k ➡✌ï✌ð✌ñ✌ò, á à✩✌➡✌ï✌ð✌ñ✌ò: Xp i=1 yi ≥ k. ✶✌s✒ ▲ ✲✌✳◆✌❖ k ➡✌ï✌ð✌ñ✌ò, ⑤✌➂✉ ♣✗ “≥”, ➄✌▲ “=”. ➅✿❂➆❀➇❀➈❀➉❹➊❻➋❻➌❹➍❻➎❹➏❻➐❻➑❹❄❻❅ ❽✌✱❞✁➒✌❞✌✚✌✗✌✏✌✑✌✒✌✓✭✌✮❿♣, t❴✁▲❡✌❞✌➄✌➋❴ Ó ❪✌❴, ✩ ❪✌❴✱❞✌✚✌✾✌✏✌✑✁➓ ➔ , ❽✦✁❑✌è✌é ♣õ✌ö, →✾✌✏✌✑ ➎➐➏✌➑✦ . ➣✌✩❪✌❴★☎↔✝▲✗ , ❊✁↕✌❞✌✚✌✙✕ , r▼★✁➙ ❽ ✗ , ❽è✌é ♣✢✌✣✌❊✌õ✌ö. ✧✌❽✌✫✌✬✿✌❀ ♣, ❜✩ ❪✌❴❡✌❞✌➄✌➋, ❫✁➛❡ , ❫❊➛❡ , ✩ ➛ ❡ ✱✁❝✌â❞✌✚✌❜✁➓, ✧ ➦✁➜❊★ ✏✌✑✁➓✁➔. ➊✁✻☛✌☞❆ Ó✌➡✌✵✌➀✌➘✌➴. ➱ 2. ❵✃✌✭✌✮✗✌✏✌✑✌✒✌✓✌è✌é✶✌➊: max z = c1x1 + c2x2 + c3x3; ◆✌❖ 8x1 + 2x2 + 3x3 ≤ 400, 4x1 + 5x2 + 6x3 ≤ 300, xj ≥ 0, ❩ ✩✁❞j
4 第七章整数规划 现在要增加约束条件如生产某种产品，不论生产多少，都要产生一笔费用，例如工人 培训费，即>0时，不管取什么数，都要产生费用，只有=0时，5=0. 解原有的两个约束条件限制了x1,2,3的最大值分别为50,60,50.现设功是0-] 变量x1≤50hx2≤602，xr3≤50g为新增的约束条件，再在目标函数内减去(1功+ 班+购).这样，当马取值为1至其最大值时，必为1，目标函数中一定要减去：当 取0时，在约束条件中斯可为0也可为1，但因要使目标函数最大，将迫使功取0因 此不会产生.这就符合了题意. 这个问题的整数规划模型是 max 2-c11+c2x2+c3x3-(f11+f2欢+f3g: 满足 /8x1+2r2+3x3≤400， 41+5x2+6r3≤300， x1-501≤0， 2-60y2≤0， 3-50yy≤0， 0≤斯≤1，对一切 为整数，对一切5，x≥0，对一切方. 其实模型中产量的最大值，可用一个很大的数M代替，即≤M,这样做效果不 例3.设两种产品的单位毛利润分别是c和2，需要的工时分别是6和4，成本和工 时的关系如图7-3所示，要求建立一个整数规划模型，使成本在跳跃式增加的情况下，求 出最优的两种产品产量 成本（元） 2000 1500 1000 0 1000 200300040i00工时 图7-3
4 ☞✁✌✁✍✏✎✁✑✁✒✁✓ ó✌❽✌✰ß✌àï✌ð✌ñ✌ò: ✶❡✌❞✃✌Ô❞✁➒, ❊➴ ❡✌❞➆✌ä, t ✰ ❞✌❡✩✁➝➄✌➋, ✵✌✶✿✌❁ ➞✁➟✌➄, r xj > 0 ➅, ❊✁➠✌✛✁➡✁➢✌✦, t ✰ ❞✌❡✌➄✌➋ fj , P❜ xj = 0 ➅,fj = 0. ➝ ➤ ❜✌✗Ó✌➡✌ï✌ð✌ñ✌ò✉✌✈▼ x1,x2,x3 ✗✌✔✌➔✌✜❴✴▲ 50, 60,50. ó❵ yj ★ 0–1 ✙❭✚,x1 ≤ 50y1,x2 ≤ 60y2, x3 ≤ 50y3 ▲Òß❭✗ï❭ð❭ñ❭ò, → ❽ ➎➟➏❭➑✦➥✄➧➦✖➨ (f1y1 + f2y2 + f3y3). ❯✌❱, ✇ xj ✛✌✜▲ 1 s✁✩✔✌➔✌✜➅,yj ✲ ▲ 1, ➎➐➏✌➑✦ ♣❺✩✁▲✌✰➦✁➨ fj ; ✇ xj ✛ 0 ➅, ❽✌ï✌ð✌ñ✌ò❿♣ yj ✢ ▲ 0 ① ✢ ▲ 1, ✧✌❳✌✰æ ➎➐➏✌➑✦✌✔✌➔, ✞✁➩✌æ yj ✛ 0, ❳ ❨ ❊✁➫✌❞✌❡ fj . ❯ ❉✌❋✌●▼✌✮✌Ö. ❯✌➡✌✭✌✮✗✴✦✌✒✌✓✌è✌é★: max z = c1x1 + c2x2 + c3x3 − (f1y1 + f2y2 + f3y3); ◆✌❖ 8x1 + 2x2 + 3x3 ≤ 400, 4x1 + 5x2 + 6x3 ≤ 300, x1 − 50y1 ≤ 0, x2 − 60y2 ≤ 0, x3 − 50yy ≤ 0, 0 ≤ yj ≤ 1, ❩ ✩✁❞j yj▲✌✴✦ , ❩ ✩✁❞j, xj ≥ 0, ❩ ✩✁❞j. ✩✌✫è✌é ♣❞✌✚✌✗✌✔✌➔✌✜, ✢✌➋✩✌➡❻➔✌✗✌✦ M ➭✁➯, r xj ≤ Myj , ❯✌❱✁❨➂ s ❊ ✙ . ➱ 3. ❵Ó✌Ô❞✁➒✌✗➮✁✘✁➲❍✁■❴✴★ c1 â c2, ❏✌✰✗✌✿➅ ❴✴★ 6 â 4, ✾✁✬â✿ ➅ ✗✖➓✖➔✶ ÷ 7–3 ✷✖❭, ✰❭✱✖✪✖✫❭✩❭➡❭✴✦❭✒❭✓❭è❭é, æ❭✾✖✬❽✖➳✖➵✉❭ß❭à❭✗❧✖♠❭➊, ✱ ù ✔✌✕✌✗Ó✌Ô❞✁➒✌❞✌✚. ✲ ✿➅ 0 1000 2000 3000 4000 5000 ✻ ✾✁✬ (Ï) 0 500 1000 1500 2000 ÷ 7–3
57.3整数规划模型举例 解设是0-1变量当成本在第讠个范围内时，=1上：否则斯=0，整数规划模型 是 ma 2=9T1+c22-10001-15002-18003 满足 T6x1+4r2<2000w1+30002+5000w3 0≤斯≤1，对一切j 为整数，对一切i,工≥0，对一切 可以看出，斯中只能有一个为1，其余两个为0，所以目标函数中减去此范围的成本 工时的约束方程的右端也只有一项。 四、工厂选址问题 已知有n个市场，又有m个地点可建工厂为简化向题，假定每个地点只能建一个工 厂，设在地点i的工厂年生产能力限制为C,年生产费用是F.市场方对产品的需求量是 D,必须得到满足，从建厂地i到市场j的单位产品运输费用是·要求建立整数规划模 型，使生产成本及运输费用总和最小 解设两组决策变量 =从建厂地点i运到市场j的产品单位数 1.在地点i建 = 0,在地点i不建厂 目标函数为： min&=了 tgu+Fie 1扫 =1 工厂年生产能力的约束条件方程是： 2ws0=12 上式表示，在地点i不设厂时，班=0，左端必为0.在i设厂时，班=1，从i运往各地产 品数量之和小于等于该厂年生产能力 保证每个市场的需求都被满足的约束条件方程是： 对的非负约束及对斯取值的约束条件方程是 0≤h≤1，且为整数i-1,2,,m ≥0
§7.3 ✎✁✑✁✒✁✓✁❣✁❤✁✐✁❥ 5 ➝ ❵ yj ★ 0–1 ✙✌✚, ✇✾✁✬❽✁❾ j ➡✁➸☎➺ ✄➅,yj = 1; ❝✌⑤ yj = 0, ✴✦✌✒✌✓✌è✌é ★: max z = c1x1 + c2x2 − 1000y1 − 1500y2 − 1800y3; ◆✌❖ 6x1 + 4x2 ≤ 2000y1 + 3000y2 + 5000y3, y1 + y2 + y3 = 1, 0 ≤ yj ≤ 1, ❩ ✩✁❞j yj▲✌✴✦ , ❩ ✩✁❞j, xj ≥ 0, ❩ ✩✁❞j. ✢❭✣ ■❭ù,yj ♣rP❲❭❜✩❭➡❭▲ 1, ✩✖❲❭Ó❭➡❭▲ 0, ✷ ✣ ➎➟➏❭➑✦ ♣➦✖➨❨✖➸➥➺✗❭✾✖✬, ✿➅ ✗ï✌ð➶✌ú✌✗✁✡✁➃①✌P❜✩ ❊ . ➻ ✿❂➼❀➽❀➾❀➚❻❄❹❅ Ø✍✌❜ n ➡✁➪✁➶, ➹❜ m ➡✌❃✂✌✢✪ ✿✌❐. ▲✌➬✌❚✌✭✌✮, ❴✁▲Ù ➡✌❃✂ P❲✪✌✩✌➡✿ ❐ , ❵ ❽✌❃✂ i ✗✌✿✌❐✌ç✌❡✌❞✌❲✌Ý✌✉✌✈▲ Ci , ç✌❡✌❞✌➄✌➋★ Fi . ➪✁➶ j ❩❞✁➒✌✗❏✌✱✚ ★ Dj , ✲✌✳✌↔✜✌◆✌❖, ❂✪ ❐ ❃ i ✜✁➪✁➶ j ✗➮✁✘❞✁➒❄✁➘➄✌➋★ tij . ✰✌✱✁✪✁✫✌✴✦✌✒✌✓✌è é , æ✌❡✌❞✌✾✁✬✌û❄✁➘➄✌➋✁▼â✔✌✥. ➝ ❵Ó✁❵✌❛✙✌✚: xij = ❂✪ ❐ ❃ ✂ i ❄✁✜✁➪✁➶ j ✗✌❞✁➒➮✁✘✦ . yi = ( 1, ❽✌❃✂ i ✪ ❐ , 0, ❽✌❃✂ i ❊✪ ❐ . ➎➐➏✌➑✦ ▲: min z = Xm i=1 Xn j=1 tijxij + Xm i=1 Fiyi . ✿✌❐✌ç✌❡✌❞✌❲✌Ý✌✗ï✌ð✌ñ✌ò➶✌ú★: Xn j=1 xij ≤ Ciyi ,i = 1, 2, . . . , m. ➂ ✉❬✁❭, ❽✌❃✂ i ❊✁❵✌❐➅,yi = 0, ✟✁➃✌✲▲ 0. ❽ i ❵✌❐➅,yi = 1, ❂ i ❄✌❅✌ã✌❃❞ ➒✌✦✌✚✌ìâ✥❹❈❹Ú ❐✌ç✌❡✌❞✌❲✌Ý. ❡✁❢Ù ➡✁➪✁➶✗❏✌✱t❛✌◆✌❖✗ï✌ð✌ñ✌ò➶✌ú★: Xm i=1 xij ≥ Dj , j = 1, 2, . . . , n. ❩ xij ✗✇✌①✌ï✌ðû❩ yi ✛✌✜✌✗ï✌ð✌ñ✌ò➶✌ú★: 0 ≤ yi ≤ 1, ➴✌▲✌✴✦ ,i = 1, 2, . . . , m xij ≥ 0