第七章整数规划 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 z=6z1+4r2=23 4 32 3 2 2+4r2=13 1 0 012346” 01支1古6扩4 S7.3整数规划模型举例 一般整数规划问题，其建立模型的基本思路和技巧与建立线性规划模型无多大区别， 只是对要求取整数解的变量增加一个整数约束条件. 本节着重讨论整数规划模型中部分变量是0-1变量的模型以及01规划模型.在建 立某些问题的整数规划模型时，如能巧妙运用0-1变量，将使模型容易建立。下面讨论的 几个问题足以说明这一点 一、投资问题 举例说明.某投资公可可用于投资的资金是b,有几个投资项目可供选择，项目j每 年利润是G,需要资金是4，要求建立数学模型，以选定投资项目，使每年总利润最大 解 一看，这个问题应首先选收益率值最大的那个项目，其次选值次大的项 目，直到剩余资金少于任一个项目为止.但这样做不一定是最有利方案. 对行项目.只有投资和不投资两种选择因此我们用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
$7.3整数规划模型举例 3 对投资间题不可以考虑以下两种情况 一如果一组投资项目是互相排斥的，即在一组投资项目J中，至多能选择一个项 目，此时要对上述模型增加一个约束条件： 1 而取消≤1，因前式已满足后式 仁、如果只有在选择投资项目1的条件下，才能考虑是否选择项目k,则要增加一个 约束条件工≤.此式表示当五=0时，必须为0.即如果不选择1，必不能选择k.当 x1=1时，xk可等于0，也可等于1，即选择1后，k可被选择也可不被选择 二、在p个约束条件中至少要满足k个约束条件 用下式表达p个约束条件： ay≤i=1.2 设是0-1变量.如果第i个约束条件是k个约束条件中的1个，=1：否则，=0， 对p个约束条件的每1个约束条件都加进，使之成为： 盒sA+-a=1 0≤h≤1，是整数 M是很大的数，在求出数学模型的解后，如=1，第1个约束条件是有效的：如 班=0，则第i个约束条件的右端值是：+M,这是一个很大的数，使此约束条件不可能有 约束力（成为多余的约束条件方程。 题中规定至少要满足k个约束条件，应加一个约束条件 上≥k 如果规定必须满足k个约束条件则上式中的“≥”，改为“” 三、成本跳跃式增加的线性规划问题 在求产品产量的线性规划问题中，都假定生产费用分两部分，一部分与产量成线性关 系，在数学模型中考虑，构成线性目标函数.另一都分是固定的，不随产量变动，即总是存 在的，在模型中可以不考虑但在实际工作中，有一部分生产费用，或发生，或不发生，其发 生与否和产量有关，但显然不是线性关系.下面我们举两个例子讨论. 例2.设某问题的线性规划模型如下： max =C1T1+C2T2+C3T3 满足 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-602≤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
6 第七章整数规划 五、0-1变量多项式 如果在前面的投资问题中，补充两点：1.项目必须在项目k和项目1同时投资的前 提下才可以投资2.项目k和项目1同时投资时，可增获利润.那么这时的棋型将成为： max 满足 p≤xk, 0≤与≤1且为整数，对一切 模型的目标函数和约束方程中都出现了变量多项式，从而成为一个非线性的0-1规 划问题。采用下面的方法，可以将问题转化为线性的0-1规刻问题 1.所有x:的非零幂用x,替换.这是因为 x号=x,n=1,2, 2.用0-1变量xQ替换乘积ⅡcQ,Q为连乘的马的下标集合，xQ应满足： 之+1-0 (.1) o≤(MQ1 (7.2) 式中1Q一集合Q中元素的个数. 式（亿.1）的成立将保证，当对一切j∈Q有工)=1时，xQ必等于1. 式(72)的成立将保证仅当对一切j∈Q,有=1时，xQ才可等于1，任一)=0 时，则xQ必等于0. 对于上面的例题可用Y代替x,但需增加约束 2张++1-2 士≤(k+)/2 模型变为： max&= 满足 ∑4≤b, = xp≤x, x>xk+x1-1. 丈≤(rk+)/2. 0≤西≤1，对一切
6 ☞✁✌✁✍✏✎✁✑✁✒✁✓ ➷✿ 0–1 ➬❀➮❀➱❀✃➊ ✶s❽➇ ✻ ✗❇ ❒ ✭✮❿♣, ❐❿❒Ó ✂ : 1. ❊ ➎ p ✲✳ ❽❊ ➎ k â❊ ➎ l ë➅❿❇❒✗➇ ❮ ➊✌å✢✌✣ ❇ ❒ ; 2. ❊ ➎ k â❊ ➎ l ë➅✁❇❒➅, ✢✌ß✁❰✁❍✁■ c 0 . ❚✁➢❯✌➅✗✌è✌é✁✞✌✾▲: max z = Xn j=1 cjxj + c 0xkxl ; ◆✌❖ Xn j=1 ajxj ≤ b, xp ≤ xkxl , 0 ≤ xj ≤ 1➴✌▲✌✴✦ , ❩ ✩✁❞j. è❭é❭✗ ➎➟➏❭➑✦ â❭ï❭ð➶❭ú ♣t ù❭ó❭▼ ✙❭✚➆❊✖✉, ❂❭➌❭✾▲❭✩❭➡❭✇✏❭✑❭✗ 0–1 ✒ ✓ ✭✌✮. ❜ ➋➊✁✻✗✌➶❣ , ✢✌✣✁✞✭✌✮✁Ï✌❚✌▲✏✌✑✌✗ 0–1 ✒✌✓✭✌✮: 1. ✷ ❜ xj ✗✇✁Ð✁Ñ➋ xj ➯✁Ò. ❯✌★✌❳✌▲ x n j = xj , n = 1, 2, . . . . 2. ➋ 0–1 ✙✌✚ xQ ➯✁Ò✁Ó✁Ô Q j∈Q xj ,Q ▲✌➢✁Ó✗ xj ✗➊✌➏✁Õ● ,xQ á✌◆✌❖: xQ ≥ X j∈Q xj + 1 − |Q|, (7.1) xQ ≤ ( X j∈Q xj )/|Q|. (7.2) ✉ ♣ |Q|—- Õ ● Q ♣❺Ï✁Ö✗➡✦ . ✉ (7.1) ✗✌✾✫ ✞❡✁❢, ✇❩ ✩✁❞ j ∈ Q ❜ xj = 1 ➅,xQ ✲✌❈❹ 1. ✉ (7.2) ✗✌✾✫ ✞❡✁❢, ×✁✇❩ ✩✁❞ j ∈ Q, ❜ xj = 1 ➅,xQ å✢✌❈❹ 1, Õ✌✩ xj = 0 ➅, ⑤ xQ ✲✌❈❹ 0. ❩✌❹➂✁✻✗ ✵✌✮✢✌➋ x 0 ➭✁➯ xkxl , ✧✁❏ß✌àï✌ð x 0 ≥ xk + xl + 1 − 2, x 0 ≤ (xk + xl)/2. è✌é✌✙▲: max z = Xn j=1 cjxj + c 0x 0 ; ◆✌❖ Xn j=1 ajxj ≤ b, xp ≤ x 0 , x 0 ≥ xk + xl − 1, x 0 ≤ (xk + xl)/2, 0 ≤ xj ≤ 1, ❩ ✩✁❞j
57.4分枝定界算法 0≤x≤1 为整数对一切， x为整数 至此，问题已成为一个线性0-1规划问题， §7.4分枝定界算法 求解整数规划问题比较成功的方法是分枝定界算法.这种算法，可以解纯整数规划 问题和混合格数规问题 这个算法的步骤是先不考虑整数约束条件求出相应线性规划问题的最优解，如果这 个解满足已定的整数约束，它就是整数规划问题的最优解.如果有一个或多个整数约束未 被满足，就任选一个应是整数而不是整数解的变量工，设它的解是，不是整数定义 是小于的最大整数，将原问题分成两枝.一枝是原问题约束条件加xk≤⑦]构成，另 一枝是原问题约束条件加≥⑦】+1构成.解这两个分枝的新线性规划问题。对不满足 原问题整数约束的新问题，再按上述办法进行新的分枝，直到发生下面所说的情况才停止 分枝我们仍用本章的例1来说明。表7一1为例1的不考虑整数约束最优单纯形表 表7-1 64000 CB 2 6 0 6 ci-zi 00-元-0 这个问题的相应线性规划问题的最优解是x1=多，2=2，工1不符合整数约束]= 2,将原问题分别加上1≤2和1≥3就构成两个子问题为描述方便，构造一个树形图 原问题为出发节点1，向下分成两枝，如图7-4. 图7-4 图7-5 现在画出原问题及新加约束条件的图解，如图7-5.图中，区域α表示第1个子间题 的可行域区域b表示第2个子问题的可行域.画阴影的区域（不包括边界线）排除在两 个子问题的可行域之外，但它不包含1为整数的解，这样就不会在解两个子何题时把最 优可行解遗漏掉
§7.4 Ø✁Ù✁Ú✁Û✁Ü☎Ý 7 0 ≤ x 0 ≤ 1, xj▲✌✴✦ , ❩ ✩✁❞j, x 0▲✌✴✦ . s✌❨, ✭✌✮❿Ø✾ ▲✌✩✌➡✏✌✑ 0–1 ✒✌✓✭✌✮. §7.4 Þ✤ß✤à✤á✤â✡➽ ✱✖ ✴✦❭✒❭✓✭❭✮➥ã➧ä✾✖å❭✗❭➶❣ ★❹æ✖ç✖è✖é✖ê✖ë. ❯❭Ô❢❭❣, ✢❭✣❭✖✖ì✴✦❭✒❭✓ ✭✌✮✌â✁í● ✴✦✌✒✌✓✭✌✮. ❯❭➡❢❭❣✗✖î✖ï★❭➹❊❭õ❭ö✴✦ ï❭ð❭ñ❭ò❭✱❭ù✖♦❭á✏❭✑❭✒❭✓✭❭✮✗❭✔❭✕❭✖, ✶❭s❭❯ ➡ ✖ ◆✌❖❿Ø✝▲✗✴✦ ï✌ð, ➞❉ ★✌✴✦✌✒✌✓✭✌✮✗✌✔✌✕✌✖. ✶✌s❜✩✌➡❫ ➆✌➡✌✴✦ ï✌ð✁ð ❛◆❖, ❉ Õ×✩➡á★✴✦➌✌❊★✌✴✦✖✌✗✙✌✚ xk, ❵ ➞ ✗✖ ★ bk, ❊★✴✦ , ▲❿ñ [bk] ★ ✥❹ bk ✗✌✔✌➔✴✦ , ✞ ➤✌✭✌✮❴✾Ó✁ò. ✩✁ò✌★✁➤✌✭✌✮✌ï✌ð✌ñ✌òà xk ≤ [bk] →✾ , ➣ ✩✁ò✌★✁➤✌✭✌✮✌ï✌ð✌ñ✌òà xk ≥ [bk] + 1 →✾ . ✖❯✌Ó✌➡❴ ò ✗Ò✏✌✑✌✒✌✓✭✌✮. ❩❊◆✌❖ ➤✌✭✌✮✌✴✦ ï✌ð✗Ò ✭✌✮, →✁ó➂✌➨✁ô❣➀✌þÒ✗❴ ò, ✗✁✜➛❡➊✁✻✌✷✽✌✗❧✁♠✌å✁õ✁❳ ❴ ò. ☛✌☞✁ö✌➋✁✬✁÷✁ø✁ù 1 ú✁û☎ü. ❬ 7–1 ý ù 1 ø✁þ✁ÿ✁✁✂✁✄✁☎✁✆✁✝✁✞✁✟✁ì✁✠✁✡✁☛ ✡ 7–1 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 2 0 1 1 3 − 1 3 0 6 x1 5 2 1 0 −1 6 2 3 0 zj 6 4 1 3 8 3 0 cj − zj 0 0 − 1 3 − 8 3 0 ☞✁✌✁✍✁✎ø✁✏✁✑✁✒✁✓✁✔✁✕✍✁✎ø✁✝✁✞✁✖✁✗ x1 = 5 2 ,x2 = 2, x1 þ✁✘✁✙✁✂✁✄✁☎✁✆. [b1] = 2, ✚✁✛✍✁✎✁✜✁✢✁✣✁✤ x1 ≤ 2 ✥ x1 ≥ 3 ✦✁✧✁★✁✩✌✁✪✁✍✁✎. ý✁✫✁✬✁✭✁✮, ✧✁✯✁✰✌✁✱✠✁✲. ✛ ✍✁✎ý✁✳✁✴✁✵✁✶ 1, ✷✹✸✜ ★✁✩✁✺, ✻ ✲ 7–4. ✲ 7–4 ✲ 7–5 ✼✁✽✁✾✳✁✛✍✁✎✁✿✁❀✁✣☎❁✆❁❂✁❃✖ø✁✲❁✖, ✻ ✲ 7–5. ✲❅❄, ❆✁❇ a ✡✁❈✁❉ 1 ✌✁✪✁✍✁✎ ø❁❊❁❋❇, ❆❁❇ b ✡❁❈❁❉ 2 ✌❁✪❁✍❁✎ø❁❊❁❋❇. ✾❁●❁❍ø❆❁❇ (þ❁■❁❏❁❑❁▲❁✒) ▼❁◆✽✩ ✌❁✪❁✍❁✎ø❁❊❁❋❇❁❖❁P, ◗❁❘þ❁■❁❙ x1 ý✂❁✄✖ø❁✖, ☞❁❚✦ þ❁❯✽✖ ✩ ✌❁✪❁✍❁✎❁❱❁❲✝ ✞✁❊✁❋✁✖✁❳✁❨✁❩
8 第七章整数规划 现在求第1个问题的最优解，将x1≤2代入表7-2中的第2个方程并加入松弛变 量得下式： 两-号+= 加到表7-1中去，如表7-2. 7-2 64000 TTa aT 1 0 0 00 -21 64 Ci-Zi 在上转轴，得第一个子问题的最优解表，如表7-3. 表7-3 64000 CB 0 0 4 0 6 4 1 0 4 0 0 -1 0 为解第2个子问题，将1≥3即1=6+3代入表7-1的第2个方程整理后得： 6+有到4+西=-号 将上式加进表7-L,得到表7-4 表7-4 64000 CB TB 6 1T2gx4工5 1 0 05 6 0 在g上转轴，得如表7-5
8 ❬✁❭✁❪❴❫✁❵✁❛✁❜ ✼✁✽✁❝❉ 1 ✌✁✍✁✎ø✁✝✁✞✁✖, ✚ x1 ≤ 2 ❞✁❡✡ 7–2 ❄✝ø✁❉ 2 ✌✭✁❢, ❣ ✣❡✁❤✁✐✁❥ ❦ x5 ❧✸✁♠: 1 6 x3 − 2 3 x4 + x5 = − 1 2 . ✣✁♥✡ 7–1 ❄✹♦, ✻✡ 7–2. ✡ 7–2 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 2 0 1 1 3 − 1 3 0 6 x1 5 2 1 0 −1 6 2 3 0 0 x5 − 1 2 0 0 1 6 − 2 3 1 zj 6 4 1 3 8 3 0 cj − zj 0 0 −1 3 −8 3 0 ✽ a34 ✤✁♣✁q, ❧ ❉✰ ✌✁✪✁✍✁✎ø✁✝✁✞✁✖✁✡, ✻✡ 7–3. ✡ 7–3 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 9 4 0 1 1 4 0 − 1 2 6 x1 2 1 0 0 0 1 0 x4 3 4 0 0 − 1 4 1 − 2 3 zj 6 4 1 0 4 cj − zj 0 0 −1 0 −4 ý✖✁❉ 2 ✌✁✪✁✍✁✎, ✚ x1 ≥ 3 r x1 = x5 + 3 ❞✁❡✡ 7–1 ø✁❉ 2 ✌✭✁❢, ✂✁s✁t❧: − 1 6 x3 + 2 3 x4 + x5 = − 1 2 . ✚ ✤ ♠ ✣✁✉✡ 7–1, ❧ ♥✡ 7–4. ✡ 7–4 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 2 0 1 1 3 − 1 3 0 6 x1 5 2 1 0 − 1 6 2 3 0 0 x5 −1 2 0 0 −1 6 2 3 1 zj 6 4 1 3 8 3 0 cj − zj 0 0 − 1 3 − 8 3 0 ✽ a33 ✤✁♣✁q, ❧✻✡ 7–5
$74制非负纯算全 75 ci→ 64000 CR R 0 0 33 -4 c-2为 0 00 -d 则必74混始的还多合以一个例如必76
§7.4 ✈✁✇✁①✁②✁③❅④ 9 ✡ 7–5 cj → 6 4 0 0 0 cB xB b x1 x2 x3 x4 x5 4 x2 1 0 1 0 1 2 6 x1 3 1 0 0 0 -1 0 x3 3 0 0 1 -4 -6 zj 6 4 0 4 2 cj − zj 0 0 0 −4 −2 ⑤✲ 7–4 ⑥✁⑦ø✱✠✁✲✁⑧✣✩ ✌ ✵✁✶, ✻ ✲ 7–6
10 第七章整数规划 图7-6 当发生下述3种情况之一时，树的某个分枝就不再往下延伸 1,该分枝上的子问题没有可行解.此时增加一个约束条件也不可能有可行解 2.已求得一个不违反任何整数约束的解此时如再增加约束条件，即使求到最优解 其目标函数也不可能变得更优 3.此子问题的目标函数值不优于任一不违反整数约束的另一子向题的目标函数值 因此时如对此子问题再分枝，新的子问题由于增加约束条件，其目标函数值不会优于不违 反整数约束的那个子问题。所以没有必要再分枝了 在图7-6中，由于第3种情况发生，第一个子问题不再往下分枝：由于第2种情况发生 第2个子问题不再往下分枝这样，全部分枝都终止延伸，求得最优解：（红1,2）=(3,1)， $7.5全整数规划算法 算法要求 1.目标函数为“mim”型，目标函数中决策变量的系数全为整数 2.约束条件方程中决策变量的系数矩阵A和右端值向量b的元素全为整数： 3.约束条件全为“≤”型 为了易于理解后面介绍的算法，先举一个简单的计算例子.设有如下整数规划模型： min z=7x1+12x2+15x3: 满足 4x1+8x2+5x3>15. 31+2r2+6a3≥14 x≥0且为整数 这个例子满足了前两个要求.约束变换后，也满足了第3个要求，即 min z=7x1+12x9+15x3 满足 -41-82-5r3≤-15 -3x1-2x2-6x3≤-14 (.3) 工1之0且为整数 按向题（亿.3）列出下表（表7-7）： 表7-7 0 7 12 15 -15 -4 -8 -5 -14 -3 -2 -6
10 ❬✁❭✁❪❴❫✁❵✁❛✁❜ ✲ 7–6 ⑨✴✁⑩✁✸✁✬ 3 ❶✁❷✁❸✁❖✁✰❱ , ✱ø✁❹✌✁✜✺✁✦þ✁❺✁❻✸✁❼✁❽: 1. ❾ ✜ ✺ ✤ø✪✁✍✁✎✁❿✁➀❊✁❋✁✖. ➁❱⑧✣✰ ✌☎✁✆✁❂✁❃✁➂✁þ✁❊✁➃➀❊✁❋✁✖. 2. ➄❝ ❧✰ ✌þ✁➅✁➆✁➇✁➈✁✂❁✄❁☎✁✆✖ø✁✖. ➁❱ ✻❺✁⑧✣☎✁✆✁❂✁❃, r✁➉❝♥✝✁✞✁✖, ➊➌➋➎➍✁➏✄✁➂✁þ✁❊✁➃❥❧✁➐✞ . 3. ➁✪❁✍❁✎ø ➋➑➍❁➏✄❁➒✖þ❁✞❁➓❁➇✰ þ❁➅❁➆❁✂❁✄❁☎❁✆✖ø❁➔✰ ✪❁✍❁✎ø ➋➑➍❁➏✄❁➒, →➁❱ ✻✁➣✁➁✪✁✍✁✎❺✜ ✺, ❀ø✪✁✍✁✎❅↔ ➓✁⑧✣☎✁✆✁❂✁❃, ➊➌➋➎➍✁➏✄✁➒✁þ✁❯✁✞✁➓✁þ✁➅ ➆✁✂✁✄✁☎✁✆✁ø✁↕✌✁✪✁✍✁✎, ➙✁➛ ❿✁➀✁➜✁➝❺✜ ✺✁➞. ✽✲ 7–6 ❄ , ↔ ➓➟❉ 3 ❶➟❷➟❸➟✴➟⑩, ❉✰ ✌➟✪➟✍➟✎þ➟❺➟❻✸ ✜ ✺; ↔ ➓➟❉ 2 ❶➟❷➟❸➟✴➟⑩, ❉ 2 ✌✁✪✁✍✁✎þ✁❺✁❻✸ ✜ ✺. ☞✁❚, ➠✁➡✜ ✺✁➢✁➤✁➥✁❼✁❽, ❝ ❧ ✝✁✞✁✖: (x1, x2) = (3, 1), §7.5 ➦➨➧➨➩➨➫➨➭➨➯➨➲ ➳✁➵✁➝❝ : 1. ➋➎➍✁➏✄ ý “min” ➸, ➋➎➍✁➏✄❅❄✹➺✁➻❥ ❦✁ø✁➼✁✄➠✁ý✂✁✄; 2. ☎✁✆✁❂✁❃✭✁❢ ❄✹➺✁➻❥ ❦✁ø✁➼✁✄✁➽✁➾ A ✥✁➚✁➪➒ ✷❦ b ø✁➶✁➹➠✁ý✂✁✄; 3. ☎✁✆✁❂✁❃➠✁ý “≤” ➸. ý✁➞✁➘➓✁s✁✖✁t✁➴✁➷✁➬✁ø➳✁➵, ➮✁➱✁✰✌✁✃✟✁ø✁❐➳ù✪ . ❒ ➀ ✻✁✸✂✁✄✁✔✁✕✁❮➸: min z = 7x1 + 12x2 + 15x3; ❰✁Ï 4x1 + 8x2 + 5x3 ≥ 15, 3x1 + 2x2 + 6x3 ≥ 14, xj ≥ 0Ð✁ý✂✁✄. ☞✁✌ù✪✁❰✁Ï➞✁Ñ✁✩✌✁➝❝ . ☎✁✆❥✁Òt , ➂❰✁Ï➞❉ 3 ✌✁➝❝ , r min z = 7x1 + 12x2 + 15x3; ❰✁Ï −4x1 − 8x2 − 5x3 ≤ −15, −3x1 − 2x2 − 6x3 ≤ −14, xj ≥ 0Ð✁ý✂✁✄. (7.3) Ó✍✁✎ (7.3) Ô✁✳✁✸✡ (✡ 7–7): ✡ 7–7 0 7 12 15 −15 −4 −8 −5 −14 −3 −2 −6