第三章线性规划模型的建立 目前线性规划是应用最广泛、最成功的运筹学分支。在线性规划以及运筹学的其它 分支的应用中，一个重要的方面就是建立简繁适当、能反映实际向题的主要因素、得出正 确结论并能取得经济效治的数学隙型。一个经验不丰富的运筹学工作者要做到这一点.是 很不容易的。在大多数情况下建立数学模型要经过儿个阶段的精心思考。建立模型实际 上是一个多次迭代的过程每一次迭代大体上包括：实际向题的抽象、简化，作出假设、 明确变量和参数；形成明确的数学问题；解析的或数值地求解问题；对结果进行分析和验 证，如果符合实际即可应用，否则要进行修改，进入下一次的迭代。最初，为了将实际情 况简化得能较容易地建立一个粗略的、可以使用的模型，常常只考虑少量最重要的因素 而将较多次要因素略去。但这样建立的模型使得模型距实际情况较远，甚至得不出正确的 结论。因此，要在此基础上再加进一些被省略的因素中显得较重要的因素，变更已建立的 模型。然后再加进一些因素，重复建立模型，重复这一过程直到建立一个符合上述要求的 模型为止.此时如再加进不重要的因素，将使得模型变得太复杂，雄以求解或增加的求解 费用大于所取得的经济效益，从而使决策单位得不偿失。这一整套建立数学模型的过程 说起来比较简单，真正做到并不是一件轻而易举的事。有人说，建立数学模型，与其说是科 学，不如说是艺术，这是有一定道理的。 在数材中不可能计论实际工作中的大型问颗.因此本意只通时几个不同卷刑的被简 化的、较为标准的问题来说明建立模型的基本思路和技巧.当然客观现实是复杂的，干变 万化的，不可能有一套一成不变的方法，更不可能在教材中将建立线性规划模型的技巧罗 列无贵。要求从事这米工作的运算学工作著在时间中不断积累经哈，锻炼能力，探素技巧 充分发挥创造性和想象能力，达到热能生巧的地步 例1.混合问题 某石油公司用A.B和C三种原料混合成普通汽油、高级汽油和低铅汽油3种成品 出售.3种原料的单位成本儿每月最大购入量如表31 表3-1 原料单位成本（元/kg)每月最大购入量） 100 B 50 每公斤成品售价为：普通汽油d元高级汽油e元，低铅汽油了元. 低铅汽油每月最多销售50t, 各种汽油规格如下 普通汽油：A不少于20%.C不多于30% 高级汽油P:A不少于40%，B不少于10%，并不多于20%，C不多于10%， 低铅汽油L:B不少于30%。 要求建立线性规划模型，以决定各种汽油的销售数量来取得最大利润。 解通常，建立墩学草羽的第一步是确宗决策变量.如果我们设工1，工2。工3分别为3 种成品的数量，那么必须知道各种成品的成本和售价，以便决定.现在题目中已给出了 1
✂✁✂✄ ☎✂✆✂✝✂✞✂✟✂✠✂✡☞☛☞✌ ✍✏✎✒✑✒✓✒✔✒✕✒✖✒✗✒✘✒✙✒✚✒✛✒✜✢✙✒✣✒✤✒✥✒✦✒✧✒★✒✩✒✪✒✫✢✬✒✑✒✓✒✔✒✕✒✭✒✮✒✦✒✧✒★✒✥✒✯✒✰ ✩✱✪✱✥✱✗✱✘✳✲, ✴✱✵✱✶✱✷✥✱✸✱✹✱✺✱✖✱✻✱✼✱✽✱✾✱✿✱❀✱✜❂❁✱❃✱❄✱❅✱❆✱❇✱❈✱✥✱❉✷✱❊✱❋✜❂●✱❍✱■ ❏▲❑▲▼▲◆❁▲❖▲●▲P▲◗▲❘▲❙✱✥▲❚✱★▲❯✱❱✱✫ ✴✱✵P✱❲✱❳▲❨✱❩▲✥✱✦▲✧✱★✱❬▲❭✱❪✷✱❫✱❴▲❵✱✴▲❛, ✖ ❜✱❳✱❝✱❞✱✥✱✫❂✬✱❡✱❢✱❚✱❣✱❤✱✐, ✻✱✼✱❚✱★✱❯✱❱✷P✱❥✱❦✵✱❧✱♠✥✱♥✱♦✱♣✱q✱✫❂✻✱✼✱❯✱❱✱❅✱❆ r✖ ✴✱✵❢✱s✱t✱✉✱✥✱❥✱✈, ✇✱✴s✱t✱✉✱❡✱①r✱②✱③: ❅✱❆✱❇✱❈✱✥✱④✱⑤✱✜⑥✽✱⑦✱⑧⑥❭✱❍✒⑨✱⑩✒✜ ❶❏▲❷▲❸▲❹▲❺❚▲❻❽❼▲✣ ❶❏✥✱❚✱★▲❇✱❈✱❻❽❾▲❿✱✥✱➀▲❚✱➁▲➂✱➃✱❾▲❇✱❈✱❻❽➄❑✱➅✱➆▲➇✩✱❿❹❲ ➈⑧⑥➉➅✒➊✒➋❅✒❆✒➌✒➍✒✗✒✘✒⑧⑥➎✒➏✷➆✒➇✒➐✒➑⑧ ➆✒➒✐ ✴ s✒✥✒t✒✉✱✫⑥✙✒➓, ➔✒→✒➣❅✒❆✒❣ ❤✒✽✒⑦✒●✒❁✒↔✒❝✒❞✒➂✒✻✒✼✴✒✵✒↕✒➙✥✒✜⑥➍✒✭✒➛✒✘✒✥✒❯✒❱, ➜✒➜✒➝q✒➞✒➟❸✙✶✒✷✥ ❊✒❋, ➠➣ ↔▲❢▲s✷▲❊▲❋▲➙▲➡✫❽➢❵✱➤✻✱✼✱✥▲❯✱❱▲➛✱●✱❯▲❱✱➥▲❅✱❆▲❣✱❤✱↔▲➦, ➧▲➨●▲❳▲❍▲■❏✥ ❑✱▼✫ ❊✱➩, ✷ ✬ ➩✱➫✱➭r✱➯✱➲➆ ✴✱➳✱➵✱➸✱➙✥ ❊✱❋ ✲➻➺✱●✒↔✶✒✷✥ ❊✱❋, ❷✱➼✳➽✻✱✼✱✥ ❯✱❱✱✫⑥➾✱➚➯✱➲➆ ✴✱➳✱❊✱❋, ✶✱➪✻✱✼✱❯✱❱, ✶✱➪✱❵✱✴❥✱✈✱➶❴✻✱✼✴✱✵➊✱➋r✒➹✷ ➃✱✥ ❯✱❱➔✱➘✫ ➩✱➴➉➯✱➲➆❳✶✱✷✥ ❊✒❋, ➣ ➛✱●✱❯✱❱❷●✱➷➪✱➬, ➮ ✭✱➃✱❾✱➀✱➱➲✥✱➃✱❾ ✃✘✒❡✒❐✒❒✒❖✒●✒✥✒P✒◗✒❘✒❙, ❮ ➠➛✒❰✒Ï✒Ð✒Ñ✒●✒❳✒Ò✒Ó✒✫ ❵✒✴✒Ô✒Õ✻✒✼✒❚✒★✒❯✒❱✒✥✒❥✒✈, Ö▲×▲ØÚÙ↔▲✽▲Ð, Û ■❫▲❴◆❳▲✖✴▲Ü▲Ý➠❞✱Þ✱✥▲ß✱✫áà✱âÖ , ✻▲✼▲❚▲★▲❯▲❱, ã✯Ö✖▲ä ★ , ❳✱➉Ö✖✱å✱æ, ❵ ✖✱à✴✱ç✱è✱é✥✱✫ ✬✒ê✒ëì✲í❳✒➍✒❁✒î▼❅✒❆✒❬✒❭ì✲í✥✒❡✒❱✒❇✒❈, ❊✒➩✒ï✒ð✒➝✒ñ❥✒❦✵ ❳✒ò✒ó✒❱✒✥➵ ✽ ⑦✱✥✱✜❂↔➔✱ô✱õ✥✱❇✱❈Ø✱Ö ❶✻✱✼✱❯✱❱✱✥➫✱ï♣✱ö❹✱÷✱ø✫❂❀✱➾✱ù✱ú✱û✱❅✱✖➪✱➬✥ , ü❷ ý⑦✱✥, ❳✱➍✱❁✱à✴✱Õ✱✴✣✱❳❷✥✱✸✱þ, ➼❳✱➍✱❁✱✬✱ê✱ë✳✲➣✻✱✼✱✑✱✓✱✔✱✕✱❯✱❱✱✥÷✱ø✱ÿ ✂✁✂✄✫ ✷ ➃❮ ß❵ ó✱❬✱❭✱✥✱✦✱✧✱★✱❬✱❭✱❪✱✬➴✂☎ ✲➻❳✂✆✂✝✂✞✱P✱❲, ✟✂✠❁✂✡, ☛✂☞÷✱ø, ✌✩✂✍✂✎✂✏✂✑✱✓❹✂✒⑤✱❁✂✡, ✓✱❴✂✔❁✂✕ø✥✱➂✂✖✱✫ ✗ 1. ✘➋❇✱❈ ✙✂✚✂✛✂✜✂✢ ✘ A✜ B ❹ C ✣✂✤✂✥✂✦✂✘➋✣✂✧ñ✂★✛✜✪✩✂✫★ ✛✱❹✂✬✂✭★ ✛ 3 ✤ ✣✂✮ ❍✂✯✱✫ 3 ✤✂✥✂✦✥✱Ð✱Ñ✱✣ï ❦✇✂✰ ✙✱❡✂✱➒✱❸➉✂✲ 3–1✫ ✲ 3–1 ✥ ✦ Ð✱Ñ✱✣ï (✳/kg) ✇✂✰ ✙✱❡✂✱➒✱❸ (t) A a 100 B b 150 C c 50 ✇ ✜✂✴✣✂✮✂✯✂✵➔: ✧ ñ✂★✛ d ✳, ✩✂✫★ ✛ e ✳, ✬✂✭★ ✛ f ✳ ✫ ✬✂✭★ ✛✇✂✰ ✙✱❢✂✶✂✯ 50t✫ ✷ ✤✂★✛✔✂✸✱➉✱✐: ✧ ñ✂★✛ R:A ❳✱➟✱❐ 20%,C ❳✱❢✱❐ 30%; ✩✂✫★ ✛ P:A ❳✱➟✱❐ 40%,B ❳✱➟✱❐ 10%, ◆❳✱❢✱❐ 20%,C ❳✱❢✱❐ 10%; ✬✂✭★ ✛ L:B ❳✱➟✱❐ 30%✫ ✷ ➃✱✻✱✼✱✑✱✓✱✔✱✕✱❯✱❱, ✭✱❰ç✷ ✤✂★✛✥✂✶✂✯✱❚❸✱Ø❖✱●✱✙✱❡✂✹✂✺✱✫ ✻ ñ✱➜, ✻✱✼✱❚✱★✱❯✱❱✱✥✂✼✴ ✖✱✖❏ç❰✱Ï❷✱❸✫⑥➉➅✂✽✿✾⑩ x1 ✜ x2 ✜ x3 ✩✂❀➔ 3 ✤ ✣✂✮✱✥✱❚❸ , ❁✂❂✂❃✂❄✂❅✱è✷ ✤ ✣✂✮✱✥✱✣ï ❹✯✂✵, ✭✂❆✱❰ç cj ✫⑥û✱✬✱❈ ✍➻✲ ➽❈❇❍ → 1
2 第三章线性规划模型的建立 售价，但由于各种汽油的确切配方不知道，算不出各种汽油的单位成本，因此用上面定义 的决策变量不能建立问题的线性规划模型。 在这个问题里。必须作出两个决策，即每种汽油各用多少A、B和C原料及各生产多 少。遇到这种情况，采用双下标变量往往能顺利的建立模型。我们设： =种汽油中所用的原料kg) 其中i=A,B,C:=R,PL.这样j种汽油的生产量就是： tj-RL (3.1) 例如对普通汽油TR=xAR十EBR十xCR 与此相似，原料i的需要量就是 =4品，C D= (3.2 例如对原料A,DA=工AR十EAP+王A 目标函数是总销售收入减总成本的余额最大，即 max :=dT+eTp+fTL -aDA-bDg -cDc 将式(1.1)和(1.2)代入上式得： max 2 d(TAR+TBR+TCR)+e(TAP+IBP +TCP) +f(FAL+BL+CL)-a(EAR+AP+AL) -b(BR+BP+BL)-c(CR+cp+CL) 根据各种原料每月最大购入量列出第一组约束条件方程 EAB+E4P+E1L.<100000 BR+BP+xBL≤150000 rCR+xCp+xcL≤50000 第二组约束条件方程是对低铅汽油销售量的限制： xAL+xBL+xCL≤50000 第三组约束条件方程是各种汽油规格的限制。以普通汽油规格为例： 普通汽油中原料A的重量≥02， 普通汽油重量 即 TAR AR+rBR+eR之02
2 ❉❋❊❈●■❍✂❏✂❑✂▲✂▼✂◆❋❖❈P✂◗ ✯✿✵, ➢❙❘í❐✷ ✤✿★✛✥❏✿❚✿❯✸✒❳❅✒è, ❱ ❳✒❍ ✷ ✤✿★✛✥✒Ð✒Ñ✒✣ï, ❊✒➩✘r✹ ç✿❲ ✥✱❰✱Ï❷✱❸❳✱❁✱✻✱✼✱❇✱❈✱✥✱✑✱✓✱✔✱✕✱❯✱❱✱✫ ✬❵✱✵❇✱❈✂❳, ❃✂❄❭✱❍✂❨✵❰✱Ï, ➌✇✂✤✂★✛✂✷✘✱❢✱➟ A✜ B ❹ C ✥✂✦✮✷✕✂❩✱❢ ➟✱✫✪❬❴✱❵✂✤❣✱❤, ❭ ✘✂❪✱✐ô❷✱❸✂❫✂❫❁✂❴✂✹✱✥✱✻✱✼✱❯✱❱✱✫ ✽✂✾⑩ : xij = j✤✂★✛ ✲➻❒✱✘✱✥✥✂✦ i(kg) ✯✳✲ i = A, B, C;j = R, P,L✫ ❵✱➤ j ✤✂★✛✥✂✕✂❩❸✺✱✖: Tj = X C i=A xij , j = R, P,L. (3.1) ❵➉✱➄✂✧ñ✂★✛ TR = xAR + xBR + xCR ✫ ã✱➩✂❛✂❜, ✥✂✦ i ✥✂❝✷❸✺✱✖: Di = X L j=R xij ,i = A, B, C. (3.2) ❵➉✱➄✥✂✦ A,DA = xAR + xAP + xAL ✫ ✍ ô✂❞❚✱✖✂❡✂✶✂✯✂❢➒✂❣❡✱✣ï ✥✂❤✂✐✱✙✱❡, ➌ max z = dTr + eTp + fTL − aDA − bDB − cDC . ➣✂❥ (1.1) ❹ (1.2) ✉➒r ❥ ● : max z = d(xAR + xBR + xCR) + e(xAP + xBP + xCP ) +f(xAL + xBL + xCL) − a(xAR + xAP + xAL) −b(xBR + xBP + xBL) − c(xCR + xCP + xCL) ❦✂❧✷ ✤✂✥✂✦✱✇✂✰ ✙✱❡✂✱➒✱❸❍✂✼✴✂♠✂♥✂♦✂♣✱Ü✸✱✈: xAR + xAP + xAL ≤ 100000 xBR + xBP + xBL ≤ 150000 xCR + xCP + xCL ≤ 50000 ✼✂q♠✂♥✂♦✂♣✱Ü✸✱✈✱✖✱➄✬✂✭★ ✛✶✂✯❸✥✂r✂s: xAL + xBL + xCL ≤ 50000 ✼✣✂♠✂♥✂♦✂♣✱Ü✸✱✈✱✖✷ ✤✂★✛✔✂✸✱✥✂r✂s✱✫⑥✭✂✧ñ✂★✛✔✂✸➔ ❵ : ✧ ñ✂★✛ ✲✥✂✦ A ✥✶ ❸ ✧ ñ✂★✛✶ ❸ ≥ 0.2, ➌ xAR xAR + xBR + xCR ≥ 0.2
即 -0.8EAR +0.2BR+0.2ICR<0. 与此相似，普通汽油规格2为： -0.3xAR-0.3xBR+0.7xCR≤0： 高级汽油规格1： -0.6zAP +0.4FBP+0.; 高级汽油规格2： 0.1zAP -0.9rBP+0.1rCP <0; -0.2FAP+0.8FBP-0.2rCP S0. 高级汽油规格3 -0.1xAp-0.1xBp+0.9zcp≤0： 低铅汽油规格： 0.3FAL -0.7FBL +0.3FCL S0. 非负约束： Fij 20,i=A,B,C:j=R,P,L. 这就是这个问题的线性规划模型。 用单纯形法求出这个问题的最优解后，决策者不但知道有利的各种汽油数量，而且知 道各种汽油的确切配方。 例2.多阶段投资问题 某公司有20万元可用于投资，投资方案有以下5种，每种方案的投资额不受限制. 方案A:5年内每年都可投资，年初投资1元2年后可收回1.2元 方案B:5年内每年都可投资，年初投资1元，3年后可收回1.3元 方案C:只在第1年初有一次投资机会，每投资1元4年后可收回1,4元 方案D:只在第2年初有一次投资机会，每投资1元，4年后可收回1.7元 方案E:只在第4年初有一次投资机会.每投资1元1年后可收回1.4元 此外每年年初若将1元存入银行，年末可收获106元 投资所得的收益和银行利息可用于投资， 要求建立线性规划棋型，使公司在5年末收获的资金最多. 解将投资和收益情况归纳成表32，对建立数学模型将有帮助。表中投资方案的下 标表示投资年份。用F表示未投资完而存入银行的金额。在第4年，因有投资方案E,所 以没有F4.此外不考虑B4,A5和B,。因这些投资收回时已超过了5年的期限。 表32中虚线的起点是当年年初的投资额，虚线的终点为当年年初的可用金额（第1 年年初是20万元)，两者必须相等。这样对第1年至第5年年初的投资情况，都可建立 个约束条件方程
3 ➌ −0.8xAR + 0.2xBR + 0.2xCR ≤ 0. ã✱➩✂❛✂❜, ✧ ñ✂★✛✔✂✸ 2 ➔: −0.3xAR − 0.3xBR + 0.7xCR ≤ 0; ✩✂✫★ ✛✔✂✸ 1: −0.6xAP + 0.4xBP + 0.4xCP ≤ 0; ✩✂✫★ ✛✔✂✸ 2: 0.1xAP − 0.9xBP + 0.1xCP ≤ 0; −0.2xAP + 0.8xBP − 0.2xCP ≤ 0. ✩✂✫★ ✛✔✂✸ 3: −0.1xAP − 0.1xBP + 0.9xCP ≤ 0; ✬✂✭★ ✛✔✂✸: 0.3xAL − 0.7xBL + 0.3xCL ≤ 0. t✂✉♥✂♦: xij ≥ 0,i = A, B, C; j = R, P,L. ❵ ✺✱✖❵✱✵❇✱❈✱✥✱✑✱✓✱✔✱✕✱❯✱❱✱✫ ✘✱Ð✂✈✱❼✱þ✱➃✱❍ ❵✱✵❇✱❈✱✥✱✙✂✇✱❾✱➚, ❰✱Ï✱❪✱❳✱➢❅✱èà✂✹✱✥✷ ✤✂★✛❚❸ , ➠✂①❅ è ✷ ✤✂★✛✥❏✂❚✂❯✸✱✫ ✗ 2. ❢❧✱♠✂②✂③❇✱❈ ✙✂✜✂✢à 20 ý✳ ➍✱✘✱❐②✂③, ②✂③✸✂④✱à✱✭✱✐ 5 ✤, ✇✂✤✸✂④✱✥②✂③✐✱❳✂⑤✂r✂s✱✫ ✸✂④ A:5 ⑥❋⑦➻✇✂⑥✂⑧➍ ②✂③, ⑥ ➓②✂③ 1 ✳,2 ⑥ ➚✱➍✂❢❋⑨ 1.2 ✳; ✸✂④ B:5 ⑥❋⑦➻✇✂⑥✂⑧➍ ②✂③, ⑥ ➓②✂③ 1 ✳,3 ⑥ ➚✱➍✂❢❋⑨ 1.3 ✳; ✸✂④ C: ➝✬✂✼ 1 ⑥ ➓✱à✴ s②✂③✂⑩✂❶, ✇✂②✂③ 1 ✳,4 ⑥ ➚✱➍✂❢❋⑨ 1.4 ✳; ✸✂④ D: ➝✬✂✼ 2 ⑥ ➓✱à✴ s②✂③✂⑩✂❶, ✇✂②✂③ 1 ✳,4 ⑥ ➚✱➍✂❢❋⑨ 1.7 ✳; ✸✂④ E: ➝✬✂✼ 4 ⑥ ➓✱à✴ s②✂③✂⑩✂❶, ✇✂②✂③ 1 ✳,1 ⑥ ➚✱➍✂❢❋⑨ 1.4 ✳. ➩✂❷, ✇✂⑥✂⑥➓✂❸➣ 1 ✳✂❹➒✂❺✱➇, ⑥✂❻➍✂❢✂❼ 1.06 ✳ ✫ ②✂③❒✱●✱✥✂❢✱❙❹✂❺✱➇✹✂❽✱➍✱✘✱❐②✂③✫ ✷ ➃✱✻✱✼✱✑✱✓✱✔✱✕✱❯✱❱, ➛✜✂✢✬ 5 ⑥✂❻❢✂❼✱✥③✂❾✙✱❢✱✫ ✻ ➣✿②✿③❹❢✒❙✒❣✒❤✿❿✿➀✒✣✿✲ 3-2, ➄✒✻✒✼✒❚✒★✒❯✒❱➣ à✿➁✿➂✒✫✪✲ì✲②✿③✸✿④✒✥✒✐ ô✲✂➃②✂③✂⑥✂➄✫❂✘ F ✲✂➃✂➅②✂③✂➆➠❹ ➒✂❺✱➇✥❾✐✱✫❂✬✂✼ 4 ⑥, ❊à②✂③✸✂④ E, ❒ ✭✂➇✱à F4 ✫ ➩✂❷❳✱q✱➞ B4, A5 ❹ B5 ✫ ❊✱❵✱➳✂②✂③❢❋⑨➴ ➽❈➈❥ → 5 ⑥ ✥✂➉✂r✱✫ ✲ 3-2 ✲❈➊✱✑✱✥× ❛✖✱❀⑥✂⑥➓✱✥②✂③✐ , ➊✱✑✱✥✂➋❛✱➔❀⑥✂⑥➓✱✥✱➍✱✘❾✐ (✼ 1 ⑥✂⑥➓✱✖ 20 ý✳), ❨✱❪❃✂❄✂❛✂➌✫ ❵✱➤➄✂✼ 1 ⑥✱➨✼ 5 ⑥✂⑥➓✱✥②✂③❣✱❤, ⑧➍✱✻✱✼✴ ✵✂♥✂♦✂♣✱Ü✸✱✈:
4 第三章线性规划模型的建立 表3-2 年份（年初）1 3 A 5 6 A1· 1.241 B1..... 1.3B1 1.4C 1.06F 1.24 1.3B D2. 1.7D2 A3, 1.2A3 1.3B3 106F A山 1.2A4 E4.... 1.4E Fs. 1.06F 第1年：A1+B1+C1+F=200000: 第2年：A2+B2+D3+F2=1.06F: A2+B2+D2+-1.06=0 第3年：A3+B+A-1.241-1.0GF2=0: 第4年：44+E4-1.3B1-1.242-1.06F3=0: 第5年：-1.4C1-1.3B2-12A3-1.4E4=0 非负约束： A,B,C,D,E5,F≥0，j=1,,5 目标函数是第6年年初（第5年年末）收回的资金最大： maxz=1.7D2+1.3B3+1.2A4+1.06F. 这个问题也可以用动态规划解决 例3.生产进度问题 某工厂生产的一种产品需求有季节性只能在4个月内销售，生产也要在这4个月内 进行.可以在正常工作时间生产，也可以因生产能力的限制而在加班时间生产。某个月产 品的产量可以大于当月的销售量而将多余的产品存贮，但要在当月付出存贮费。第4月未 要将产品全部售完.以免存到第2年。 产品在正常工作时间生产，每月最多能生产100单位，单位成本为15元。在加班时间 生产，每月最多能生产30单位，单位成本为20元。每月生产量及其平均单位成本不一定 要相等。存贮费每月每单位0.2元.4个月的需求量分别为50,130,150及100单位.要求 建立线性规划模型以确定每月在正常时间及加班时间各生产多少产品，使总成本最小
4 ❉❋❊❈●■❍✂❏✂❑✂▲✂▼✂◆❋❖❈P✂◗ ✲ 3–2 ⑥✂➄ (⑥ ➓ ) 1 2 3 4 5 6 A1 . . . . . . . . . . . . . . . 1.2A1 B1 . . . . . . . . . . . . . . . . . . . . . . . . 1.3B1 C1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4C1 F1 . . . . . . 1.06F1 A2 . . . . . . . . . . . . . . . 1.2A2 B2 . . . . . . . . . . . . . . . . . . . . . . . . 1.3B2 D2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7D2 F2 . . . . . . A3 . . . . . . . . . . . . . . . 1.2A3 B3 . . . . . . . . . . . . . . . . . . . . . . . . 1.3B3 F3 . . . . . . 1.06F3 A4 . . . . . . . . . . . . . . . 1.2A4 E4 . . . . . . 1.4E4 F5 . . . . . . 1.06F5. ✼ 1 ⑥: A1 + B1 + C1 + F1 = 200000; ✼ 2 ⑥: A2 + B2 + D2 + F2 = 1.06F1; ➀ : A2 + B2 + D2 + F2 − 1.06F1 = 0; ✼ 3 ⑥: A3 + B3 + F3 − 1.2A1 − 1.06F2 = 0; ✼ 4 ⑥: A4 + E4 − 1.3B1 − 1.2A2 − 1.06F3 = 0; ✼ 5 ⑥: F5 − 1.4C1 − 1.3B2 − 1.2A3 − 1.4E4 = 0; t✂✉♥✂♦: Aj , Bj , Cj , Dj , Ej , Fj ≥ 0, j = 1, . . . , 5. ✍ ô✂❞❚✱✖✂✼ 6 ⑥✂⑥➓ (✼ 5 ⑥✂⑥✂❻) ❢❋⑨➻✥③✂❾✙✱❡: max z = 1.7D2 + 1.3B3 + 1.2A4 + 1.06F5. ❵✱✵❇✱❈✂➍✱➍✱✭✱✘✂➎✂➏✱✔✱✕✱❾✱❰✱✫ ✗ 3. ✕✂❩➆✂➐❇✱❈ ✙❬✂➑✂✕✂❩✱✥✴✂✤❩✂✮✂❝✱➃✱à✂➒✂➓✱✓, ➝❁✱✬ 4 ✵✂✰❋⑦✶✂✯, ✕✂❩✂➍✷ ✬❵ 4 ✵✂✰❋⑦ ➆✱➇✫❂➍✱✭✱✬✱■➜❬✱❭➴✂☎✕✂❩, ➍✱➍✱✭ ❊✕✂❩✱❁✂✡✱✥✂r✂s➠✬➲✂➔➴✂☎✕✂❩✱✫ ✙ ✵✂✰ ❩ ✮▲✥→❩❸➍▲✭▲❡▲❐▲❀✰ ✥✂✶→✯❸➠➣ ❢→❤✱✥→❩✂✮❹→➣, ➢ ✷ ✬▲❀✰→↔❍ ❹→➣✃✫↕✼ 4 ✰→❻ ✷✱➣❩✂✮✂➙✂➛✂✯➆, ✭✂➜❹✂➣✱❴✼ 2 ⑥ ✫ ❩→✮▲✬▲■➜❬▲❭➴→☎✕✂❩, ✇→✰ ✙▲❢▲❁→✕→❩ 100 Ð▲Ñ, Ð▲Ñ▲✣ï▲➔ 15 ✳ ✫❽✬➲→➔➴→☎ ✕✂❩, ✇✂✰ ✙✱❢✱❁✂✕✂❩ 30 Ð✱Ñ, Ð✱Ñ✱✣ï✱➔ 20 ✳ ✫ ✇✂✰ ✕✂❩❸✮✱✯✂➝✂➞✱Ð✱Ñ✱✣ï ❳✴✱ç ✷✂❛✂➌✫ ❹✂➣✃✇✂✰✱✇Ð✱Ñ 0.2 ✳ ✫ 4 ✵✂✰ ✥✂❝✱➃❸✩✂❀➔ 50,130,150 ✮ 100 Ð✱Ñ✱✫ ✷ ➃ ✻✱✼✱✑✱✓✱✔✱✕✱❯✱❱✱✭ ❏ç✱✇✂✰ ✬✱■➜✱➴✂☎✮➲✂➔➴✂☎✷✕✂❩✱❢✱➟✂❩✂✮, ➛✂❡✱✣ï ✙✂➟✱✫
解设 马=在第j月正常工作时间内生产的产品数 j=1,2,34 斯=在第了月加班时间内生产的产品数 1=1.2.3.4 =在第月末存贮的产品数 j=1,2,3. 生产能力限制约束条件方程 x)≤100， 5≤30， j=1,2,3,4 满足需求的约束条件方程是 x1+1-21-50, 2+h+-22=130, +g+2-28=150, 4+3+=100. 非负约束条件是 %320,j-1,2,3.4 目标函数是 minz=15(1+x2+x3+x4)+20(1+9+g+4)+0.2(a+2+23): 例4.工厂选址问题 有A.B、C三个原料产地，其原料要在工厂加工，制成成品，再在销售地出售.A.B 两地又是销售地.已知有关数据如表33 表33 华料产量 地点 每牛成品销量 每万地成，品所需下费 (仟元 30 5. 26 13 4 24 0 3 4t原料制成1t成品， AB问距离150km,BC间距离200km.CA问距离100km. 原料运费每万吨公里300元，成品运费每万吨公里250元. 如在B地设厂，每年生产成品不能超过5万吨，在A、B设厂，生产规模不受限制。 要求建立线性规划模型，使决策人能够决定在哪儿个地点设厂，生产能力多大，以达 到总费用（为简化问题，这里只包括产品加工费、原料及成品运费）最小的目的。 解在建立模型之前，先检查一下题目中所给数据是否产销平衡
5 ✻ : ⑩ xj = ✬✂✼ j ✰ ■ ➜❬✱❭➴✂☎❋⑦✕✂❩✱✥✂❩✂✮✱❚, j = 1, 2, 3, 4; yj = ✬✂✼ j ✰ ➲✂➔➴✂☎❋⑦✕✂❩✱✥✂❩✂✮✱❚, j = 1, 2, 3, 4; zj = ✬✂✼ j ✰✂❻✂❹✂➣✥✂❩✂✮✱❚, j = 1, 2, 3. ✕✂❩✱❁✂✡✂r✂s♥✂♦✂♣✱Ü✸✱✈: xj ≤ 100, yj ≤ 30, j = 1, 2, 3, 4 ➠✂➡❝✱➃✱✥♥✂♦✂♣✱Ü✸✱✈✱✖: x1 + y1 − z1 = 50, x2 + y2 + z1 − z2 = 130, x3 + y3 + z2 − z3 = 150, x4 + y4 + z3 = 100. t✂✉♥✂♦✂♣✱Ü✖ : xj , yj , zj ≥ 0, j = 1, 2, 3, 4. ✍ ô✂❞❚✱✖: min z = 15(x1 + x2 + x3 + x4) + 20(y1 + y2 + y3 + y4) + 0.2(z1 + z2 + z3). ✗ 4. ❬✂➑✂➢✂➤✱❇✱❈ à A✜ B ✜ C ✣✱✵✂✥✂✦❩✱➂, ✯ ✥✂✦✱✷✬✱❬✂➑➲❬ , s✱✣✱✣✂✮, ➯✬✂✶✂✯✱➂✱❍✂✯✱✫ A✜ B ❨✱➂✂➥✱✖✂✶✂✯✱➂✱✫ ➽❅à✂➦✱❚❧➉✂✲ 3–3✫ ➧ 3-3 ➨➫➩ ➭➲➯➲➳➲➵➲➸➲➺ (➻ t) ➭➲➯➲➼➲➽➲➾➲➚➲➺ (➻ t) ➭➻➲➪➼➲➽➲➶➲➹➲➘➲➴➲➷ (➬➲➮) A 30 7 5.5 B 26 13 4 C 24 0 3 4t ✥✂✦s✱✣ 1t ✣✂✮✱✫ AB ☎➥✂➱ 150km,BC ☎➥✂➱ 200km,CA ☎➥✂➱ 100km✫ ✥✂✦✦✃✇ ý✂✃✜❳ 300 ✳, ✣✂✮✱✦✃✇ ý✂✃✜❳ 250 ✳ ✫ ➉✱✬ B ➂✱⑩✂➑, ✇✂⑥✕✂❩✱✣✂✮✱❳✱❁➈❥ 5 ý✂✃, ✬ A✜ B ⑩✂➑, ✕✂❩✱✔✱❯✱❳✂⑤✂r✂s✱✫ ✷ ➃✒✻✒✼✒✑✒✓✒✔✒✕✒❯✒❱, ➛✒❰✒Ï✒â✒❁✿❐✒❰ç ✬✿❒✒❦✵ ➂ ❛⑩✿➑, ✕✿❩✒❁✿✡✒❢✒❡, ✭ ✓ ❴ ❡✃✘ (➔✽✱⑦✱❇✱❈, ❵ ❳ ➝②✱③❩✂✮➲❬✃✜ ✥✂✦✮✱✣✂✮✱✦✃ ) ✙✂➟✱✥ ✍✢✥✱✫ ✻ ✬✱✻✱✼✱❯✱❱✂❮✱✎, ❰✂Ï✂Ð✱✴✐✱❈ ✍➻✲➻❒❇❚❧✖✱➎✂❩✂✶✂➝✂Ñ✱✫
6 第三章线性规划模型的建立 每年原料产量80万t,恰好是每年成品销售量20万t的4倍，产销平衡。 我们用两套双下标决策变量，使模型建立容易一些，看起来清楚一些。设 x=每年由产地：运到建厂地j的原料吨数（万）， i=A,B,C:j=A,B,C. =每年由建厂地运到销售地k的成品吨数（万）， i=A.B,C:k=A,B. 第一组约束条件是各地的原料数量（本地生产加外地运来减运往外地的数量）等于成 品数量的4倍 30+BA+CA-EAB -FAC =4(VAA+UAB). 式中即出现xBA,又出现工AB,看起来是矛盾的.但在决策时预先不知道那一个方向 是有利的方向，因此把这两种可能都考虑进去，由于目标函数是求生产成本最小，因此不 可能产生对流运输。 26+TAR+ICR-TRA -IRC =4(URA+URR). 24+AC BC CA-ICB=4(NCA+CB) 第二组约束条件是各地工厂运到销售地的成品数量恰好满足需要： VAA +UBA+UCA=7 VAB VBB +VCB=13. 第三组约束条件是在B地设厂的生产规模受限制 BA十BB≤5. 最后是非负约束 x≥0，i=A,B,Cj=A,B,C:i≠j 5≥0，j=A,B,C:k=A,B. 目标函数为总费用最小： min 2=5.5(AA+VAB)+4(yBA+yBB)+3(uCA+yCB) +0.3[150(AB+BA+100(AC+CA) +200(BC+CB)]+0.25[150(AB+BA)+100ycA+200yCBl. 例5.下料问题 用长度为7.4m的圆钢截断成制造某种机床所需的3个轴坯，长度分别为2.9m、2.1m 1.5m,现需要制造100台机床.要求建立线性规划模型，以寻求最佳的截断方案使所需圆 钢最少 解在以前讨论的问题中，决策变量大都被确定为与产品或原料有关的数量，但在 一些问题（如本例题中，这样确定决策变量。往往很难甚至不能建立线性规划模型。所
6 ❉❋❊❈●■❍✂❏✂❑✂▲✂▼✂◆❋❖❈P✂◗ ✇✂⑥✂✥✂✦❩❸ 80 ý t, Ò✂Ó✖✇✂⑥✣✂✮✂✶✂✯❸ 20 ý t ✥ 4 Ô, ❩✂✶✂➝✂Ñ✱✫ ✽✂✾✘✂❨Õ ❪✱✐ô❰✱Ï❷✱❸, ➛✱❯✱❱✱✻✱✼✱❝✱❞✴✱➳, Õ×✱Ø✂Ö✂×✴✱➳✫⑥⑩ xij = ✇✂⑥ ❘❈❩✱➂ i ✦ ❴✻✂➑✱➂ j ✥✥✂✦✃❚ (ý t), i = A, B, C; j = A, B, C. yjk = ✇✂⑥ ❘➻✻✂➑✱➂ j ✦ ❴ ✶✂✯✱➂ k ✥✱✣✂✮✃❚ (ý t), i = A, B, C; k = A, B. ✼✴→♠→♥→♦→♣▲Ü✖✷➂✱✥✥✂✦❚❸ (ï ➂→✕→❩➲❷ ➂▲✦Ø→❣✦❫❷ ➂▲✥✱❚❸ ) ➌ ❐▲✣ ✮✱❚❸✥ 4 Ô: 30 + xBA + xCA − xAB − xAC = 4(yAA + yAB). ❥ ✲➻➌✱❍✱û xBA, ➥✱❍✱û xAB, Õ×✱Ø✖✂Ø✂Ù✱✥✱✫ ➢✱✬✱❰✱Ï➴✂Ú✂❰❳ ❅✱è✂❁✱✴✱✵✸❋Û ✖✒à✿✹✒✥✒✸❙Û, ❊✒➩✿Ü✒❵❨ ✤ ➍✒❁⑧q✒➞➆ ➡, ❘í❐ ✍ ô✿❞❚✒✖✒➃✿✕✿❩✒✣ï ✙✿➟, ❊✒➩❳ ➍✱❁✂❩✂✕✱➄✂Ý✱✦✂Þ✱✫ 26 + xAB + xCB − xBA − xBC = 4(yBA + yBB), 24 + xAC + xBC − xCA − xCB = 4(yCA + yCB). ✼✂q♠✂♥✂♦✂♣✱Ü✖✷➂✱❬✂➑✱✦❴ ✶✂✯✱➂✱✥✱✣✂✮✱❚❸ Ò✂Ó➠✂➡❝ ✷: yAA + yBA + yCA = 7, yAB + yBB + yCB = 13. ✼✣✂♠✂♥✂♦✂♣✱Ü✖✱✬ B ➂✱⑩✂➑✱✥✂✕✂❩✱✔✱❯✂⑤✂r✂s: yBA + yBB ≤ 5. ✙✱➚✱✖t✂✉♥✂♦: xij ≥ 0,i = A, B, C; j = A, B, C;i 6= j yjk ≥ 0, j = A, B, C; k = A, B. ✍ ô✂❞❚ ➔ ❡✃✘✱✙✂➟: min z = 5.5(yAA + yAB) + 4(yBA + yBB) + 3(yCA + yCB) +0.3[150(xAB + xBA + 100(xAC + xCA) +200(xBC + xCB)] + 0.25[150(yAB + yBA) + 100yCA + 200yCB]. ✗ 5. ✐ ✦ ❇✱❈ ✘àß➐ ➔ 7.4m ✥âáäãàåà✆✣àsà✑✙ ✤à⑩→æ❒→❝✥ 3 ✵àçàè, ß➐✩à❀➔ 2.9m✜ 2.1m✜ 1.5m, û✂❝✷ s✂✑ 100 é✂⑩✂æ✫ ✷ ➃✱✻✱✼✱✑✱✓✱✔✱✕✱❯✱❱, ✭✂ê✱➃✱✙✂ë✱✥✂å✂✆✱✸✂④✱➛✱❒✂❝❋á ã✱✙✱➟✱✫ ✻ ✬✱✭✱✎✱î▼✥✱❇✱❈✳✲, ❰✱Ï❷✱❸❡ ⑧✱➵❏ç✱➔✱ã❩✂✮✱➀✥✂✦à✂➦✱✥✱❚❸✫❂➢✱✬ ✴✒➳❇✒❈ (➉ï ❵❈ ) ✲ , ❵✒➤❏ç❰✒Ï❷✒❸✫ ❫✿❫❜➮✒➧✒➨❳✒❁✒✻✒✼✒✑✒✓✒✔✒✕✒❯✒❱✒✫✢❒
7 以，一般的说在线性规划中，我们将变量定义为从事某项活动方的次数.在这个例题 中，我们设为按第种方案截断的圆钢根数截断圆钢的方案有以下8种 表3-4 轴坯长度(m) 截断圆铜方学 0 00 2.1 0 03210 15 00 剩下料头长度(m)0.10.30.901.10.20.81.4 在成品规格较多，原料长度较长，截断方案很多时，上表轴坯长度最好按长短从上到 下排列，对第一行数字，从左到右逐渐减少，在第一行数字相等时，第二行数字从左到右逐 渐减少等等，这样不但便于考虑方案，而且可以避免遗漏 目标函数是刺下的料头最少，即： mim2-0.11+0.3z2+0.9g+1.1z5+0.2x6+0.8r7+1.4z8 目标函数也可以为截断的圆钢根数最少，即： min:= 读者不难验证这两个目标是一致的， 约束条件方程是每种长度的轴坏至少是100根以及非负约束： 2x1+x2+x3+x4≥100， 2x2+x3+3x6+2x6+x7≥100， 1+3+34+2z6+3,+48≥100 20且为整数j=1,2,…,8 最后一组约束条件除了马≥0外还要求 是整数，这是由题目本身决定的.因为 一根圆钢截掉一段，就算全用掉了.这个问题本来是整数规划向题放在这里讨论主要是 说明确定决策变量的一种有效方法. 例6.收缩问题 这个何题是在生产过程中，由于原料体积收缩，成品体积小于原料体积而发生的。例 如某工厂生产1、2、3三种瓶装液体产品，都是用不同体积的液体原料A和B混合而成。 在加工过程中，A的体积收缩10%，B的体积收缩20%，在A.B收缩后再混合 A的成本为4元/L,每月最多可买到4000L:B的成本为2元/L,每月最多可买到 4500L.三种产品每升的售价分别为5元.6元、4元。市场最大需求量分别为2000、3000 和4000L.各种成品的规格为 产品1中，A必须恰为B的2倍 产品2中.A最少右40%.B不多千30% 产品3中，A不超过20%，至少有B50%
7 ✭ , ✴✂ì✥Ö , ✬✱✑✱✓✱✔✱✕✳✲, ✽✂✾➣ ❷✱❸ xj ç✂❲✱➔✱❮ß✙✂í✂î➎ j ✥✱s✱❚✱✫⑥✬❵✱✵❵❈ ✲ , ✽✂✾⑩ xj ➔✂ï✼ j ✤✸✂④✂å✂✆✱✥❋á❈ã❦❚ , å✂✆❋á❈ã✱✥✱✸✂④✱à✱✭✱✐ 8 ✤: ✲ 3–4 ç✂èß➐ (m) åð✆ñáòã ✸ð④ x1 x2 x3 x4 x5 x6 x7 x8 2.9 2 1 1 1 0 0 0 0 2.1 0 2 1 0 3 2 1 0 1.5 1 0 1 3 0 2 3 4 ó✐ ✦✂ôß➐ (m) 0.1 0.3 0.9 0 1.1 0.2 0.8 1.4 ✬✒✣✿✮✒✔✿✸✒↔✒❢, ✥✿✦ß➐↔✿ß, å✿✆✒✸✿④✒❜✒❢➴, r✲ ç✿èß➐✙Ó✿ïß✿õ❮ r ❴ ✐✂ö , ➄✂✼✴ ➇❚✂÷, ❮✂ø✱❴✂ù✂ú✂û❣➟ ; ✬✂✼✴ ➇❚✂÷❛✂➌✱➴, ✼✂q➇❚✂÷❮✂ø✱❴✂ù✂ú û ❣➟ ➌✂➌, ❵✱➤❳✱➢✂❆✱❐✱q✱➞✱✸✂④, ➠✂①➍✱✭✂ü✂➜✄✂ý✫ ✍ ô✂❞❚✱✖ó✐✱✥✦✂ô✙✱➟, ➌ : min z = 0.1x1 + 0.3x2 + 0.9x3 + 1.1x5 + 0.2x6 + 0.8x7 + 1.4x8. ✍ ô✂❞❚✂➍✱➍✱✭ ➔å✂✆✱✥❋á❈ã❦❚✱✙✱➟, ➌ : min z = X 8 j=1 xj . þ❪✱❳➮ ❲➈ , ❵ ❨ ✵ ✍ ô✖ ✴✂ÿ✥✱✫ ♥✂♦✂♣✱Ü✸✱✈✱✖✇✂✤ß➐✥ç✂è✱➨➟✱✖ 100 ❦✭✱✮t✂✉♥✂♦: 2x1 + x2 + x3 + x4 ≥ 100, 2x2 + x3 + 3x5 + 2x6 + x7 ≥ 100, x1 + x3 + 3x4 + 2x6 + 3x7 + 4x8 ≥ 100, xj ≥ 0① ➔✱Ô❚ , j = 1, 2, . . . , 8 ✙✱➚✴✂♠✂♥✂♦✂♣✱Ü✁✱→ xj ≥ 0 ❷, ✂✱✷➃ xj ✖ Ô❚ , ❵ ✖❋❘➻❈ ✍ ï✁✄❰ ç ✥✱✫ ❊✱➔ ✴ ❦ á❈ã✂å✁☎✴✱♠, ✺ ❱➙✱✘✁☎→ ✫ ❵✱✵❇✱❈ï Ø✖ Ô❚✱✔✒✕✱❇✱❈, ✆ ✬❵ ❳✱î▼❉ ✷✖ Ö ❶❏ç❰✱Ï❷✱❸✥✴✂✤à✱❘✱✸✱þ✱✫ ✗ 6. ❢✁✝✱❇✱❈ ❵✱✵❇✱❈✱✖✱✬✂✕✂❩✱❥✱✈✳✲, ❘➻❐✥✂✦①✂✝✂❢✁✝, ✣✂✮✱①✂✝✂➟✱❐✥✂✦①✂✝➠✍✂✕✱✥✱✫ ❵ ➉✙❬→➑→✕→❩ 1✜ 2✜ 3 ✣→✤✟✞✟✠✟✡①→❩→✮, ⑧✖▲✘▲❳▲ò▲①→✝▲✥✡① ✥→✦ A ❹ B ✘➋➠✣▲✫ ✬➲❬✱❥✱✈✳✲,A ✥✱①✂✝✂❢✁✝ 10%, B ✥✱①✂✝✂❢✁✝ 20%, ✬ A✜ B ❢✁✝✱➚➯ ✘➋✫ A ✥✒✣ï✒➔ 4 ✳/L, ✇✿✰ ✙✒❢✒➍☞☛❴ 4000L; B ✥✒✣ï✒➔ 2 ✳/L, ✇✿✰ ✙✒❢✒➍☞☛❴ 4500L✫ ✣✂✤❩✂✮✇✁✌✥✂✯✂✵✱✩✂❀➔ 5 ✳ ✜ 6 ✳ ✜ 4 ✳ ✫✎✍✁✏✱✙✱❡✂❝✱➃❸✩✂❀➔ 2000✜ 3000 ❹ 4000L✫ ✷ ✤ ✣✂✮✱✥✱✔✂✸➔: ❩✂✮ 1 ✲ , A ❃✂❄✂Ò✱➔ B ✥ 2 Ô; ❩✂✮ 2 ✲ , A ✙✱➟✱à 40%,B ❳✱❢✱❐ 30%; ❩✂✮ 3 ✲ , A ❳➈❥ 20%, ➨➟✱à B50%✫
8 主因章线确规划论型的建立 要求建立使该、司取得最大利就的线性规划模型。 解这个问题和这题1的不 处仅在于 ,料在加工过程中多积。我们可以设决策 变量是料的休积而调整成及售 ,可可以设英策变量为成及中的料的休积而调整的料 的单位晟本。现在采用后者，设 =在产及j中所用料i的升数 i=AB:J=1,2. 因到是成及中 料的体积，为划产成及需要多积后的A1L,就需要购进10/9L的A 可就是A多积后1L的成本是4×号. 市标函数是 min 5(AI +B1)+6(A2+B2)+4(A3+xB3) -4×号（A+EA2+xA3)-2×(B1+Bm+xB3) 约束条件方程为： 受的料数量上次的约束 (A1+A2+工A3)≤4000 9(eB1+EB2+xB3)≤4500 受需求量上次的约束 xA1+xB1≤2000， 工A2+rB2≤3000， EA3+B3≤4000. 受产及规方决上次的约束 EA1-2xB1=0, 0.6E42-0.4xB2>0. -0.3A2+0.7z2≤0， 0.8xA-0.2xB≤0， -0.5zA3+0.5zB3≥0. 非负约束： xy20.i-A,B:j=1,2,3 例冬发间汽车运输问题 现举产说明建立模型的技巧，为不使问题太大，我们举出下面简化了的问题。 最汽车运输、司经例A、B.C 害发入间的某运输业务，任意两个生发从间有 、路通，运量及每车的利就如中度种36所求
8 ❉❋❊❈●■❍✂❏✂❑✂▲✂▼✂◆❋❖❈P✂◗ ✷ ➃✱✻✱✼✱➛✁✑✜✂✢❖✱●✱✙✱❡✂✹✂✺✱✥✱✑✱✓✱✔✱✕✱❯✱❱✱✫ ✻ ❵✒✵❇✒❈❹✿❵❈ 1 ✥✒❳✒ò✿❮☞✒☞✓✒✬✒❐✥✿✦✬➲❬✒❥✒✈ì✲❢☞✝✒✫ ✽✿✾➍✒✭✒⑩✒❰✒Ï ❷✒❸✖ ✥✿✦✥✒①✿✝➠☞✔Ô ✣✿✮✿✯✿✵, ➍✒➍✒✭✒⑩✒❰✒Ï❷✒❸➔✣✿✮ì✲✥✿✦✥✒①✿✝➠☞✔Ô✿✥✿✦ ✥✱Ð✱Ñ✱✣ï ✫⑥û✱✬❭ ✘✱➚✱❪, ⑩ xij = ✬✂❩✂✮ j ✲➻❒✱✘✥✂✦ i ✥✌❚ , i = A, B; J = 1, 2, 3. ❊ xij ✖✱✣✂✮✳✲✥✂✦✥✱①✂✝, ➔✕✂❩✱✣✂✮✂❝✷ ❢✁✝✱➚✱✥ A1L, ✺✂❝✷ ✱➆ 10/9L ✥ A, ➍✱✺✱✖ A ❢✁✝✱➚ 1L ✥✱✣ï ✖ 4 × 10 9 ✫ ✍ ô✂❞❚✱✖: min z = 5(xA1 + xB1) + 6(xA2 + xB2) + 4(xA3 + xB3) −4 × 10 9 (xA1 + xA2 + xA3) − 2 × 10 8 (xB1 + xB2 + xB3). ♥✂♦✂♣✱Ü✸✱✈➔: ⑤✥✂✦❚❸r✂s✱✥♥✂♦: 10 9 (xA1 + xA2 + xA3) ≤ 4000, 10 8 (xB1 + xB2 + xB3) ≤ 4500. ⑤✂❝✱➃❸r✂s✱✥♥✂♦: xA1 + xB1 ≤ 2000, xA2 + xB2 ≤ 3000, xA3 + xB3 ≤ 4000. ⑤✂❩✂✮✱✔✂✸❰r✂s✱✥♥✂♦: xA1 − 2xB1 = 0, 0.6xA2 − 0.4xB2 ≥ 0, −0.3xA2 + 0.7xB2 ≤ 0, 0.8xA3 − 0.2xB3 ≤ 0, −0.5xA3 + 0.5xB3 ≥ 0. t✂✉♥✂♦: xij ≥ 0,i = A, B; j = 1, 2, 3. ✗ 7. ✕ ✍ ☎✂★✁✖✦✂Þ✱❇✱❈ û✱Þ❵✱Ö ❶✻✱✼✱❯✱❱✱✥÷✱ø, ➔❳✱➛✱❇✱❈✱➷✱❡, ✽✂✾Þ✱❍✱✐✱✹✱✽✱⑦→ ✥✱❇✱❈✱✫ ✙ ★✁✖✦✂Þ✜✂✢P✁✗ A✜ B ✜ C ✣✱✵✁✕✍✂❮☎ ✥✁✘✁✙✱✦✂Þ✁✚✁✛, ✜✁✢❨ ✵✁✕✍✂❮☎à ✜ö✁✣ñ, ✘✱✦❸✮✇✁✖✥✂✹✂✺✱➉✂✲ 3-5 ❹✲ 3-6 ❒✂➃✱✫
9 每周用运量(。)表3-5 每利润（元）表36 到的ABC 到的ABC 的A 150250 的 150200 100 200 B 300 500100 100150 线任意有汽250每周每运汽 最多在两个市间单程运行4次，由于技术上及 业务上的原因，全蓝部汽 就建立利润简线性规划模型 周色须停餐小女汽是在及有利解中不计个本。要方 解 就这个问题简数 模型，有两得不 简思路，从而有两得确定取经变量简方数 两个模暑不不 简线性规划模啦。第一得方数是者照例5这料同题简方数以采取大得 方案简次数作下取经变量。第、得方数下3这标变量。现分别叙述如这。 题目中规定周程汽每，须由A城开， ,建多运设4个明变，周量须 回A城所以 汽每运设路线可以有8个，设下采取第方得设每路线简次数，即者此路线设每简汽每 数，设每路线如模3-7所示 模3-7 标号) 设每路线 标号(). 设每路线 A→B-A→CA 5 A→CA一B一A A→B→C→A A+C→B→A 3 ABCBA 7 A+7→B→0+A A→B→A→B→A AC→ACA 由于题目中规定在每不计个本，求此可能产进在每运设.设 =A一B间简重每数 =A一C间简重每数 欢=B一A间简重每数： =B一C间简重每数 =C一A间简重每数 %=C一B间简重每数 目标加数下 maxz=1501+200h+50g+300g4+1005+150 第组约束可件方变是者8得设每路线开设简汽每数等于250辆求在每不计个本 所以全都开化
9 ✇✁✤✘✱✦❸ (✖) ✲ 3–5 ❴✁✥ ✍ ✥ A B C A 150 250 B 100 200 C 500 100 ✇✁✖✹✂✺ (✳) ✲ 3–6 ❴✁✥ ✍ ✥ A B C A 150 200 B 50 300 C 100 150 ✑✜✂✢à ★✁✖ 250 ✦, ✇✁✤✱✇✁✦✂★✁✖✙✱❢✱✬✂❨✵✁✕✍ ☎Ð✱✈✱✦➇ 4 s , ❘➻❐÷ær✮ ✚✁✛r✥✥✱❊, ➙✂➛★✁✖✱✇✁✤✂❻✂❃✂❄✁✧✁★ A ✕✁✩✫✪✁✖ ⑨✭✬✁✮✁✯✁✰✁✱, ✲✁✳✁✴✁✵✁✶✁✩✫✷✁✸✁✹ ✺✁✻✁✼✰✁✱✁✽✁✾✁✿✁❀✁❁✁❂✁❃✩ ❄ ✹ ✺✁❅✁❆✁❇✁❈✽✁❉✁❊✁❂✁❃, ✯✁❋✁●✳✁❍✽✁■✁❏, ❑✁▲✯✁❋✁●✁▼✁◆✁❖✁P✁◗✁❘✁✽✁❙✁❚, ❋❆✟❯✟❱✟❲✟❳✳✟❍✽✟✾✟✿✁❀✟❁✁❂✟❃✩❩❨✟❬●✟❙✁❚✁❭✟❪✁❫✟❴ 5 ❵✟❛❇✟❈✽✟❙✟❚, ❜✟❝✟❞✟❡● ❙✁❢✁✽✁❣✁❉✁❤✁✐✁❖✁P✁◗✁❘✩✫❨✁❥●✁❙✁❚✁✐ 3 ❵✁❦◗✁❘✩✫❧✁♠✁♥✁♦✁♣✁q✁❵✁✩ ❈sr✭t❀✁◆✁✉✁✈✪✁✇✁①✁②④③ A ⑤✁⑥✁⑦, ✻✁⑧✁⑨✁⑩ 4 ❆✁❶✁❷, ✉✁❸①✁②✁❹④❺ A ⑤, ❻✁❜ ✪✁✇⑨✁⑩❏✁✾✁❼❜ ✯ 8 ❆ , ❽ xj ✐❝✁❞✁❨ j ●⑩ ✇❏✁✾✁✽✁❣✁❉, ❾❪✁❿✁❏✁✾⑩ ✇ ✽✪✁✇ ❉ , ⑩ ✇❏✁✾q❯ 3–7 ❻✁➀✁✩ ❯ 3-7 ❦✁➁ (j) ⑩ ✇❏✁✾ ❦✁➁ (j) ⑩ ✇❏✁✾ 1 A → B → A → C → A 5 A → C → A → B → A 2 A → B → C → A 6 A → C → B → A 3 A → B → C → B → A 7 A → C → B → C → A 4 A → B → A → B → A 8 A → C → A → C → A ③✭➂❈sr✭t❀✁◆✁✬✇✁✳✁✴✁✵✁✶, ➃❿✁❼✁➄✁➅✁➆✁✬✇⑨✁⑩✩✫❽ y1 = A → B➇ ✽✁➈✇❉ ; y2 = A → C➇ ✽✁➈✇❉ ; y3 = B → A➇ ✽✁➈✇❉ ; y4 = B → C➇ ✽✁➈✇❉ ; y5 = C → A➇ ✽✁➈✇❉ ; y6 = C → B➇ ✽✁➈✇❉ . r ❦✁➉❉✁✐: max z = 150y1 + 200y2 + 50y3 + 300y4 + 100y5 + 150y6. ❨✁❬✁➊✁➋✁➌✁➍✁➎❙❷❭✁❪ 8 ●⑩ ✇❏✁✾⑥⑩✽✪✁✇❉✁➏➂ 250 ➐ (➃✬ ✇✁✳✁✴✁✵✁✶, ❻✁❜✁➑✁➒✁⑥✁⑦): X 8 j=1 xj = 250
10 第三章线性规划模型的建立 第二组约束条件方程是两地间运行的重车数小于等于运量： h≤150： V2≤250： s≤100 4≤200 y5<500 6≤100. 第三组约束条件方程是两地间的重车数小于等于空重车总数 h≤x1+2++2红4+工 2≤T1+x5+x6+7+2x8 ≤1+x3+2x4+5+x6 ≤2++7 5≤x1+x2+x5+x7+2x8 6≤x3+x6+r7 最后一组约束是非负及整数约束： ≥0，西为整数， 这个线性规刻模型有14个决策变量，13个约束条件方程（不包括非负及整数约束） 若城市数增多，要列举所有行车方案而不遗漏，费时费事，第三组约束条件也很容易列错。 因此这个模型在题目规模较大时没有使用价值。 如果用3下标变量，就可克服上述缺点 现设 x张=第i次从j地开往k地的空重车数： =第i次从j地开往k地的重车数： i=1,2,3,4j=A,B,Ck=A,B,C 根据题目所给，可以列出表3-8. 表38 第1次第2次第3次第4次 A→B T3AB B→A T2BA T3RA TABA C-A C→B T2CB TI3CB 题目中规定的周初只能从A出发，周末全部返回A以及每周最多单程运行4次，都 在表38中确定决策变量时考虑到了
10 ➓④➔✭→↔➣✁↕✁➙✁➛✁➜✁➝④➞✭➟✁➠ ❨✁❥✁➊✁➋✁➌✁➍✁➎❙❷❭✁❋✁➡➇⑨✁⑩✽✁➈✇❉✁➢➂➏ ➂⑨❘ : y1 ≤ 150; y2 ≤ 250; y3 ≤ 100; y4 ≤ 200; y5 ≤ 500; y6 ≤ 100. ❨✁➤✁➊✁➋✁➌✁➍✁➎❙❷❭✁❋✁➡➇ ✽✁➈✇❉✁➢➂➏ ➂✬✁➈✇✁➥❉ : y1 ≤ x1 + x2 + x3 + 2x4 + x5; y2 ≤ x1 + x5 + x6 + x7 + 2x8; y3 ≤ x1 + x3 + 2x4 + x5 + x6; y4 ≤ x2 + x3 + x7; y5 ≤ x1 + x2 + x5 + x7 + 2x8; y6 ≤ x3 + x6 + x7. ✻✁➦❬✁➊✁➋✁➌❭✁➧✁➨✁➩✁➫✁❉➋✁➌: xj ≥ 0, xj✐✁➫✁❉, j = 1, 2, . . . , 8; yk ≥ 0, yk✐✁➫✁❉, k = 1, 2, . . . , 6. ❅✁❆✾✁✿✁❀✁❁✁❂✁❃✁✯ 14 ❆❖✁P✁◗✁❘, 13 ❆ ➋✁➌✁➍✁➎❙❷ (✳✁➭✁➯➧✁➨✁➩✁➫✁❉➋✁➌)✩ ➲ ⑤✟➳❉✟➵⑧ , ✷✟➸✟➺✟❻✯⑩ ✇❙✟❢▲✟✳✟➻✟➼, ➽✟➾✟➽✟➚, ❨✟➤✟➊✟➋✟➌✟➍✟➎✟✲✟➪✟➶✟➹✟➸✟➘✟✩ ➃❿❅✁❆❂✁❃★❈sr ❀✁❂✁➴✼➾ ✮✁✯✁➷✁➬✁➮✁➱✩ q✁✃➬ 3 ❵✁❦◗✁❘, ❐ ❼✁❒✁❮✁❰♣✁Ï✁Ð✁✩ ❧✁❽ xijk = ❨ i ❣❑ j ➡ ⑥✁Ñ k ➡✁✽✁✬✁➈✇❉ ; yijk = ❨ i ❣❑ j ➡ ⑥✁Ñ k ➡✁✽✁➈✇❉ ; i = 1, 2, 3, 4; j = A, B, C; k = A, B, C. Ò✁Ó❈sr ❻✁Ô, ❼ ❜✁➸✁⑦ ❯ 3–8✩ ❯ 3–8 ❨ 1 ❣ ❨ 2 ❣ ❨ 3 ❣ ❨ 4 ❣ A → B x1AB x3AB A → C x1AC x3AC B → A x2BA x3BA x4BA B → C x2BC x3BC C → A x2CA x3CA x4CA C → B x2CB x3CB ❈sr✭t❀✁◆✁✽✁✉✁✈✁Õ✁➄❑ A ⑦✁Ö, ✉✁❸➑✁➒✁❹④❺ A ❜ ➩✁×✁✉✻✁⑧✁❶✁❷✁⑨✁⑩ 4 ❣ , Ø ★❯ 3–8 t▼✁◆✁❖✁P✁◗✁❘➾✁Ù✁Ú✁Û✁Ü✁✩