第一章线性规划基础 人们在生产实践中，常常遇到如下的问题：如何运用现有资源（如人力、机器小时、 原材料等安排生产，使产值最大或利润最高？对给定的任务，如何统筹安排，以便用最少 的资源消耗去完成任务.对于这种从生产的计划与组织中提出的以达到最大收益或最小 支付为目标的问题的研究，构成了运筹学的一个重要分支一数学规划论，而线性规划侧 是其中发展最早、理论比较成熟、应用最为广泛的 一个分支 早在1939年苏联数学家康特洛维奇就对运筹学中的一些问题进行了研究.特别是 在Dantzig和Khn等数学家提出了单纯形法和对偶理论后，大大完善了线性规划的理论 和计算方法，促进了线性规划乃至运筹学的快速发展和广泛的应用. S1.1线性规划问题的一般模型 用线性规划解决实际问题的基本步骤是先建立问题的数学模型，然后对模型求解所 谓建立数学模型，就是将问题用数学语言描述出来 下面先用两个简单的模型来说明什么是线性规划间题以及如何建立线性搜划模型 例1.有甲、乙两种产品，都要在车间A和车间B加工，有关资料如表1-1. 表1-1 产品 在A加工时数在B加工时数 单位产品利润 市场限制 甲 2 1 2 1 1 4 ≤7 车间可用工时 10 间如何组织生产，使利润最大？ 解问题是要确定使得利润最大的甲、乙两种产品的产量，不妨设 1=甲产品的产量 x2=乙产品的产量 因为车间A和车间B的可用工时分别为10和8，所以加工x1单位的产品甲和x2 单位的产品乙在车间A和车间B消耗的工时不应超过车间A和B的可用工时，同时产 品乙的产量不应超过市场需求的限制，可见车间A、B的可用工时和乙产品的市场需求量 是限制产品产量的几个因素或条件，因此五1和2应满足以下不等式： 2z1+x2≤10， (A车间工时限制) (1.1) x1+T2≤8. (B车间工时限制 (1.2) 2≤7， (产品乙的市场限制) (1.3) 另外产品的产量还必须为正数，因此1、2还应满足 ≥0，对一切 (1.4) 1
✂✁✂✄ ☎✂✆✂✝✂✞✂✟✂✠ ✡☞☛☞✌☞✍☞✎☞✏☞✑✓✒, ✔☞✔☞✕☞✖☞✗☞✘☞✙☞✚☞✛: ✗☞✜☞✢☞✣☞✤☞✥☞✦☞✧ (✗✡☞★☞✩✫✪☞✬☞✭☞✮☞✩ ✯✱✰✱✲✱✳) ✴✱✵✍✱✎, ✶ ✎✱✷✱✸✱✹✱✺✱✻✱✼✱✸✱✽? ✾✱✿✱❀✱✙✱❁✱❂, ✗✱✜✱❃✱❄✱✴✱✵, ❅✱❆✱✣✸✱❇ ✙☞✦☞✧☞❈☞❉☞❊☞❋☞●☞❁☞❂. ✾☞❍☞■☞❏☞❑✍☞✎✙☞▲☞▼☞◆☞❖☞P ✒❘◗☞❙ ✙☞❅☞❚☞✖✸☞✹☞❯☞❱☞✺☞✸☞✭ ❲✱❳✱❨❬❩❪❭✙✱✚✱✛✱✙✱❫✱❴, ❵✱●✱❛✱✢✱❄✱❜✱✙✱❝✱❞✱❡✱❢✱❣❲ —- ❤✱❜✱✐✱▼✱❥, ❦✱❧✱♠✱✐✱▼✱♥ ♦✱♣ ✒rq✱s✱✸✱t✱✩✫✉❥✇✈r①✱●✱②✩✫③✣✸❨✱④✱⑤✙✱❝✱❞✱❣❲ . t✱✌ 1939 ⑥, ⑦✱⑧✱❤✱❜✱⑨✱⑩✱❶✱❷✱❸✱❹✱❺☞✾☞✢✱❄☞❜ ✒✙☞❝✱❻☞✚☞✛✱❼☞❽☞❛✱❫☞❴. ❶✱❾♦ ✌ Dantzig ❿ Kuhn ✳❤✱❜✱⑨◗✱❙ ❛✱➀✱➁✱➂✱➃✱❿✱✾✱➄✉❥✱➅, ✹✱✹❋✱➆✱❛✱❧✱♠✱✐✱▼✱✙✉❥ ❿✱▲✱➇✱➈✱➃, ➉✱❼✱❛✱❧✱♠✱✐✱▼✱➊✱➋✱✢✱❄✱❜✱✙✱➌✱➍q✱s❿④✱⑤✙③ ✣. §1.1 ➎➐➏➐➑➐➒➐➓➐➔➐→➐➣➐↔➐↕➛➙ ✣✱❧✱♠✱✐✱▼✱➜✱➝✏✱➞✚✱✛✱✙✱➟✱➠✱➡✱➢♦✱➤✱➥✱➦✚✱✛✱✙✱❤✱❜✱➧✱➨, ➩✱➅✱✾✱➧✱➨✱➫✱➜. ➭ ➯✱➥✱➦❤✱❜✱➧✱➨, ❺ ♦✱➲✚✱✛✱✣✱❤✱❜✱➳✱➵✱➸✱➺❙✱➻. ✘✱➼➤ ✣✱➽✱❞✱➾✱➀✱✙✱➧✱➨➻✱➚✇➪r➶✱➹♦ ❧✱♠✱✐✱▼✱✚✱✛✱❅✱➘✱✗✱✜➥✱➦❧✱♠✱✐✱▼✱➧✱➨. ➴ 1. ✥✇➷ ✩➮➬➽✱❏✎✱➱, ✃✱❢✌✱❐✱❒ A ❿❐✱❒ B ❮✱❰, ✥✱Ï✱✦✲ ✗✱Ð 1–1. Ð 1–1 ✎✱➱ ✌ A ❮✱❰✮ ❤ ✌ B ❮✱❰✮ ❤ ➀✱Ñ✎✱➱✱✻✱✼ (Ò) Ó✱Ô✱Õ✱Ö ➷ 2 1 6 – ➬ 1 1 4 ≤ 7 ❐✱❒✱×✣✱❰✮ 10 8 ✚✱✗✱✜✱❖✱P✍✱✎, ✶ ✻✱✼✱✸✱✹? Ø ✚✱✛♦ ❢✱Ù✱❀✱✶✱Ú✻✱✼✱✸✱✹✙✇➷ ✩➮➬➽✱❏✎✱➱✙✎✱Û, Ü✱Ý✱Þ x1 = ➷✎✱➱✙✎✱Û; x2 = ➬r✎✱➱✙✎✱Û. ß❨❐☞❒ A ❿❐☞❒ B ✙× ✣☞❰✮ ❣☞❾❨ 10 ❿ 8, ➭☞❅☞❮☞❰ x1 ➀☞Ñ☞✙✎☞➱ ➷❘❿ x2 ➀✱Ñ✱✙✎✱➱✇➬r✌✱❐✱❒ A ❿❐✱❒ B ❈✱❉✱✙✱❰✮ Ü③✱à✱á✱❐✱❒ A ❿ B ✙× ✣✱❰✮ , â✮✱✎ ➱ã➬✙✎äÛÜ③äàäáÓ✱Ôäå➫✱✙Õ✱Ö, ×äæä❐ä❒ A✩ B ✙× ✣ä❰✮ ❿ ➬➮✎ä➱✙Ó✱Ô✱å➫Û ♦ Õ✱Ö✎✱➱✱✎✱Û✙✱ç✱❞ß✱è✺✱é✱ê, ß✱ë x1 ❿ x2 ③✱ì✱í❅✱✘✱Ü✳✱î: 2x1 + x2 ≤ 10, (A❐✱❒❰✮ Õ✱Ö) (1.1) x1 + x2 ≤ 8, (B❐✱❒❰✮ Õ✱Ö) (1.2) x2 ≤ 7, (✎✱➱✇➬✙Ó✱Ô✱Õ✱Ö) (1.3) ï✱ð✎✱➱✙✎✱Û✱ñ✱ò✱ó❨✱ô❤✱õ ß✱ë x1 ✩ x2 ñ✱③✱ì✱í xj ≥ 0, ✾✱❝✱öj. (1.4) 1
第一章线性规划基础 我们称式(21)-2.4)为约束条件，其中式(2.4)称为非值约束 本问题追求的目标是在满足约束条件(2.1)(2.4)的条件下，确定获得最大利润的甲 乙两种产品的产量1和2.若以z表示利润，则有z=61+4红2，追求的目标为利润最 大，可用下式表示 max z=6x+4x (1.5) 式(2.1)-(2.5)就是本问题的数学模型，一般用下面的形式表示。 max z=6x1+4x2 满足 2x1+r2<10.(A车间工时限制 1+2≤8， (B车间工时限制 x2≤7. (产品乙的市场限制) 王≥0，对一切5. 一般建立线性规划问题的模型可按如下步骤进行： 1,确宗决策变量 确定决策变量就是将问题中的未知量用变量来表示，用来表示未知量的变量就是决 策变量，如例1中的x1和2.确定合适的决策变量是建立线性规刘问题模型的关键，它 直接涉及到能否成功地建立数学模型。 2.确定目标函数 每一个线性规划问题都有一个诅求的目标，确定目标函数就是将追求的目标用决策 变量表示出来，如例1中的式(2.5). 3.确定约束条件方程 一个问题通常有若干个约束条件（限制条件），一个线性规划问题就是要在这些条件 的限制下，找到最好的行动方案。在建立模型时要把这些约束条件用数学公式表示出来 (一般为不等式).如例1中式(2.124 例2.某工厂用丽与橡胶生产3种产品A、B、C,有关资料如表1-2. 表1-2 单位产品 单位产品 产晶 单位产品利润 钢消耗量 橡胶消耗量 A 2 3 0 3 32 已知每天可获得100单位的钢和120单位的橡胶，问每天生产A、B、C各多少使总 利润最大？ 解设 x1=产品A的日产量 x2=产品B的日产量 3=产品C的日产量。 则该问题的数学模型是
2 ÷✇ørùûú✱ü✱ý✱þ✱ÿ✁ ✂☛✁✄î (2.1)–(2.4) ❨✁☎✁✆é✱êõ ♣ ✒î (2.4) ✄❨✁✝✁✞✁☎✁✆. ➠✱✚✱✛✁✟✱➫✱✙ ❩❪❭♦✌☞ì✱í☎✠✆é☞ê (2.1)–(2.4) ✙é✱ê✘✱õ✫Ù✱❀✁✡✱Ú✸✱✹☞✻☞✼✙✓➷ ➬➽✱❏✎✱➱✙✎✱Û x1 ❿ x2. ☛✱❅ z Ð✁☞✻✱✼õ ♥✱✥ z = 6x1 + 4x2. ✟✱➫✱✙ ❩❪❭✱❨✻✱✼✱✸ ✹ õ × ✣✱✘îÐ✁☞: max z = 6x1 + 4x2 (1.5) î (2.1)–(2.5) ❺ ♦ ➠✱✚✱✛✱✙✱❤✱❜✱➧✱➨✱õ✫❝✁✌✱✣✱✘✱➼✱✙✱➂îÐ✁☞✁✍ max z = 6x1 + 4x2 ì✱í 2x1 + x2 ≤ 10, (A❐✱❒❰✮ Õ✱Ö) x1 + x2 ≤ 8, (B❐✱❒❰✮ Õ✱Ö) x2 ≤ 7. (✎✱➱✇➬✙Ó✱Ô✱Õ✱Ö) xj ≥ 0, ✾✱❝✱öj. ❝✁✌➥✱➦❧✱♠✱✐✱▼✱✚✱✛✱✙✱➧✱➨×✁✎✗✱✘✱➡✱➢✱❼✱❽✁✍ 1. Ù✱❀✑✏✁✒✁✓✁✔ Ù☞❀☞➝✠✕✠✖Û ❺ ♦☞➲✚☞✛ ✒✙✠✗✠✘Û ✣✠✖Û☞➻Ð✠☞, ✣➻Ð✠☞✠✗✠✘Û ✙✠✖Û ❺ ♦➝ ✕✁✖Û õ✫✗✁✙ 1 ✒✙ x1 ❿ x2. Ù✱❀✁✚✁✛✱✙✱➝✁✕✁✖Û♦✱➥✱➦❧✱♠✱✐✱▼✱✚✱✛✱➧✱➨✱✙☞Ï✁✜, ✢ ✣✁✤✁✥➘✱✖✁✦✁✧✱●✁★✁✩➥✱➦❤✱❜✱➧✱➨. 2. Ù✱❀✫✪✭✬✁✮✁✯ ✰ ❝☞❞☞❧☞♠☞✐☞▼☞✚☞✛☞✃☞✥☞❝☞❞✠✟☞➫☞✙ ❩ ❭ , Ù☞❀ ❩ ❭✠✱❤☞❺♦☞➲✟☞➫☞✙ ❩ ❭ ✣☞➝✠✕ ✖ Û Ð✁☞❙✱➻, ✗✁✙ 1 ✒✙î (2.5). 3. Ù✱❀☎✑✲✁✳✁✴✁✵✁✶ ❝☞❞☞✚☞✛✠✷☞✔☞✥✠☛✠✸☞❞☎✠✆é☞ê (Õ☞Öé☞ê), ❝☞❞☞❧☞♠☞✐☞▼☞✚☞✛☞❺♦ ❢ ✌■☞❻é☞ê ✙Õ☞Ö✘, ✹☞✖✸✠✺✙☞❽✠✻☞➈✠✼. ✌➥☞➦➧☞➨✮ ❢✠✽☞■☞❻☎✠✆é☞ê✣ ❤☞❜✿✾îÐ✠☞❙☞➻ (❝✁✌❨Ü✳✱î). ✗✁✙ 1 ✒î (2.1)–(2.4). ➴ 2. ❀✱❰✁❁✱✣✁❂✱◆✁❃✁❄✍✱✎ 3 ❏ ✎✱➱ A✩ B ✩ C, ✥✱Ï✱✦✲ ✗✱Ð 1–2. ❅ 1–2 ❆❈❇ ❉❈❊❆❈❇ ❋❈●❈❍❈■ ❉❈❊❆❈❇ ❏❈❑❈●❈❍❈■ ❉❈❊❆❈❇❈▲❈▼ A 2 3 40 B 3 3 45 C 1 2 24 ◆✘✰✁❖× ✡✱Ú 100 ➀✱Ñ✱✙✁❂✱❿ 120 ➀✱Ñ✱✙✁❃✁❄, ✚✰✁❖✍✱✎ A✩ B✩ C P✁◗❇ ✶✁❘ ✻✱✼✱✸✱✹? Ø Þ x1 = ✎✱➱ A ✙❚❙ ✎✱Û, x2 = ✎✱➱ B ✙❚❙ ✎✱Û, x3 = ✎✱➱ C ✙❚❙ ✎✱Û. ♥✁❯✱✚✱✛✱✙✱❤✱❜✱➧✱➨♦ :
51.2线性规划问的标准型 3 max 40x1+452+24x3 满足 21+32+3≤100， 31+32+2≤120 工5≥0，对一切5. 从以上两个例题我们看到，这两个问题都有如下共同特征 1.每个问题都有一个追求的目标，这个目标可表示为一组变量的线性函数，按照问题 的不同，追求的目标可以为最大也可以为最小 2.问题中有若干约束条件，用来表示问题中的限制或要求，这些约束条件可用线性等 式或线性不等式表示： 3.间题中用一组决策变量(x ,】来表示一种方案。在满足约束条件的前提 下，变量的一组取值就表示一个具体的方案，同时变量一般应满足非负要求.如果变量可 连续取值，问题有无穷组解.在例题中就是有无穷组生产方案可供选择.我们的任务就是 要选择一组或多组方案，使目标函数值最大或最小，从选择方案的角度来说这就是规划 问题从使目标函数最大或最小的角度来说，这就是优化问题 我们把具有上述3个特征的问题称为线性规划问题 S1.2线性规划问题的标准型 线性规划问题的数学模型，可以有简繁不同的3种描述形式： 1.对具休的线性规划问题，都将模型列成以下形式： max/min 2=c11+c2r2+...+cnEn; 满足 a11x1+a12x2+..+a1nxn≤(=，≥)b1 a21+a22++2nxn≤（←，≥b2 ami+am272+,t amnin (=,>)bm x:>0.i=1.2....n 2.为了讨论方便，有时将线性规划问题列成以下简式： max/min 满足 20,j=1,2 3.有时用矩阵和向量描述线性规划向题。以便于数学上的讨论 max/min 2=CX; 满足 ∫AX≤(=，≥b, 1X20
§1.2 ú✱ü✱ý✱þ❲❱✭❳❲❨✭❩✁❬✁❭ 3 max z = 40x1 + 45x2 + 24x3; ì✱í 2x1 + 3x2 + x3 ≤ 100, 3x1 + 3x2 + 2x3 ≤ 120, xj ≥ 0, ✾✱❝✱öj. ❑✱❅✁❪✱➽✱❞✁✙✱✛✂☛✁❫✖, ■✱➽✱❞✱✚✱✛✱✃✱✥✱✗✱✘✁❴✱â✱❶✁❵: 1. ✰ ❞✱✚✱✛✱✃✱✥✱❝✱❞✁✟✱➫✱✙ ❩❪❭, ■✱❞ ❩❪❭× Ð✁☞❨❝✱❖✁✖Û ✙✱❧✱♠✱❤, ✎✁❛✚✱✛ ✙✱Ü✱â, ✟✱➫✱✙ ❩❪❭× ❅ ❨✸✱✹, ❜ × ❅ ❨✸✱✭; 2. ✚✱✛ ✒✥✁☛✁✸☎✁✆é✱ê, ✣➻Ð✁☞✱✚✱✛ ✒✙Õ✱Ö✺ ❢✱➫, ■✱❻☎✁✆é✱ê✱×✣✱❧✱♠✳ î✺ ❧✱♠✱Ü✳✱îÐ✁☞; 3. ✚✱✛ ✒✣✱❝✱❖✱➝✁✕✁✖Û (x1, x2, . . . , xn) ➻Ð✁☞✱❝✱❏✱➈✁✼. ✌✱ì✱í☎✁✆é✱ê✙✁❝◗ ✘, ✖ Û ✙✱❝✱❖✁❞✷ ❺✱Ð✁☞✱❝✱❞✁❡✁❢✱✙✱➈✁✼✱õ✫â✮ ✖ Û ❝✁✌③✱ì✱í✝✁✞❢✱➫. ✗✁❣✁✖Û✱× ❤✁✐❞✷ , ✚✱✛✱✥✁❥✁❦✱❖✱➜. ✌ ✙✱✛ ✒❺ ♦ ✥✁❥✁❦✱❖✍✱✎➈✁✼×✁❧✁♠✠♥. ✂☛ ✙✱❁✱❂✱❺♦ ❢♠✁♥❝✱❖✺ ◗✱❖✱➈✁✼, ✶ ❩❪❭✁✱❤ ✷✱✸✱✹✱✺✱✸✱✭. ❑♠✁♥➈✁✼✱✙✁♦✁♣➻✱➚, ■✱❺♦ ✐✱▼ ✚✱✛. ❑✱✶ ❩❪❭✁✱❤ ✸✱✹✱✺✱✸✱✭✙✁♦✁♣➻✱➚, ■✱❺♦✁q✁r✚✱✛. ✂☛✽✁❡✱✥✁❪✱➺ 3 ❞✱❶✁❵✱✙✱✚✱✛✄❨ts✁✉✁✈✁✇✁①✁②. §1.2 ➎➐➏➐➑➐➒➐➓➐➔➐→④③④⑤➐➙ ❧✱♠✱✐✱▼✱✚✱✛✱✙✱❤✱❜✱➧✱➨, × ❅✱✥✱➾✁⑥✱Ü✱â✱✙ 3 ❏✱➸✱➺✱➂î : 1. ✾✁❡✁❢✱✙✱❧✱♠✱✐✱▼✱✚✱✛, ✃➲ ➧✱➨✁⑦✱●✱❅✱✘✱➂î : max/min z = c1x1 + c2x2 + . . . + cnxn; ì✱í a11x1 + a12x2 + . . . + a1nxn ≤ (=, ≥)b1, a21x1 + a22x2 + . . . + a2nxn ≤ (=, ≥)b2, . . . . . . . . . . . . am1x1 + am2x2 + . . . + amnxn ≤ (=, ≥)bm, xj ≥ 0, j = 1, 2, . . . , n 2. ❨ ❛✁⑧✱❥✱➈✱❆, ✥✮➲ ❧✱♠✱✐✱▼✱✚✱✛✁⑦✱●✱❅✱✘✱➾î : max/min z = Xn j=1 cjxj ; ì✱í Xn j=1 aijxj ≤ (=, ≥)bi ,i = 1, 2, . . . , m, xj ≥ 0, j = 1, 2, . . . 3. ✥✮ ✣✁⑨✁⑩✱❿❲❶Û ➸✱➺✱❧✱♠✱✐✱▼✱✚✱✛, ❅✱❆✱❍✱❤✱❜✁❪✱✙✁⑧✱❥: max/min z = CX; ì✱í ( AX ≤ (=, ≥)b, X ≥ 0
第一章线性规划基础 其中 C=(1,c2,,m)} A=aijmxn,i=1,2,,m;j=1,2,, X=（x1,2,.,xn) b=(61.b2.....om)T 称A为约束条件方程的系数矩阵，一般有0<m<n. 由上可见，线性规划模型的目标函数，可以是求最大值（例如追求利润最大，也可以 是求最小值（例如追求成本最小：约束条件方程可以为“≤”(，也可以为“≥”或“-”，在实 际向题中表示资源约束和对某一种成分的最低含量等.对一般的线性规划模型，可以从经 济上作如下解释 这个模型系统包括分享有限资源：（位=1,2，：m)的若干项活动j(G=1,2,,n归 第j个活动每单位需要的第i种资源的量为；作为对这些投入的回报，第j个活动每 个单位的产出（成本、效益等为“<”形式的约束条件意味着各项活动消耗的某种资 源的数量。不应超过资源的可用量“≥”形式的约束条件意味着某项活动中对某种资源消 耗的最低要求。 线性规划目标函数和约束条件方程的多样性给我们讨论带来不便，为了便于以后的 讨论，本书规定线性规划的标准型为： 满足 ∑a两=，i=1,2m 马20，j=1,2,,n 我们还规定上式中的：≥0.若问题中有：<0，可对等式两端同时乘以一1.实际问题的 线性规划模型必须转化为标准型，然后求解 如果根据实际问题建立起来的线性规划模型不是标准型的，可用下述方法将它化成 标准型： 1.若目标是 可令=-，将目标函数转化为 m=- 2.若约束方程是“≤”形式，可在方程左端加上非负变量，将方程转化为等式方程。如 (2.1)可转化为 2x1+x2+x3=10,x3≥0. 这里3的经济意义是A车间没有用完的工时，我们称3为松弛变量： 3.若约束方程是“≥”形式，可在方程左端减去非负变量，将方程转化为等式方程我 们称这个非负变量为多余变量
4 ÷✇ørùûú✱ü✱ý✱þ✱ÿ✁ ♣ ✒ : C = (c1, c2, . . . , cn); A = [aij ]m×n,i = 1, 2, . . . , m; j = 1, 2, . . . , n; X = (x1, x2, . . . , xn) T ; b = (b1, b2, . . . , bm) T . ✄ A ❨✁☎✁✆é✱ê➈✁❷✱✙✁❸✱❤✁⑨✁⑩✱õ✫❝✁✌✱✥ 0 < m < n. ❹ ❪×☞æ, ❧☞♠☞✐☞▼☞➧☞➨☞✙ ❩ ❭✠✱❤, × ❅ ♦ ➫ ✸☞✹☞✷ (✙☞✗✠✟☞➫✻☞✼☞✸☞✹), ❜ × ❅ ♦ ➫ ✸✱✭✱✷ (✙✱✗✁✟✱➫✱●✱➠✸✱✭); ☎✁✆é✱ê➈✁❷× ❅ ❨ “≤”(, ❜ × ❅ ❨ “≥” ✺ “=”, ✌✱✏ ➞ ✚✱✛ ✒Ð✁☞✱✦✱✧☎✁✆❿✱✾✁❀✱❝✱❏✱●✱❣✱✙✸✁❺✁❻✱Û✳ . ✾✱❝✁✌✱✙✱❧✱♠✱✐✱▼✱➧✱➨, × ❅✱❑✁❼ ❽ ❪✁❾✱✗✱✘✱➜✁❿: ■✱❞✱➧✱➨✁❸✱❃✁➀✁➁✱❣✁➂✱✥Õ ✦✱✧ bi (i = 1, 2, . . . , m) ✙✁☛✁✸✁➃✁➄✁✻ j (j = 1, 2, . . . , n); ➅ j ❞✁➄✁✻✰ ➀✱Ñå ❢✱✙➅ i ❏✱✦✱✧✱✙Û❨ aij ; ❾ ❨✾✱■✱❻✁➆✁➇✱✙❲➈✭➉, ➅ j ❞✁➄✁✻✰ ❞✱➀✱Ñ✱✙✎✱❙ (●✱➠✩➋➊✱❱✳ ) ❨ cj ; “≤” ➂î ✙☎✁✆é✱ê✁➌✁➍✁➎P✁➃✁➄✠✻✱❈☞❉✱✙✠❀✱❏☞✦ ✧✱✙✱❤Û , Ü③✱à✱á✦✱✧✱✙× ✣Û ; “≥” ➂î ✙☎✁✆é✱ê✁➌✁➍✁➎❀✁➃✁➄✁✻ ✒✾✁❀✱❏✱✦✱✧✱❈ ❉✱✙✸✁❺❢✱➫. ❧☞♠☞✐☞▼ ❩ ❭✠✱❤☞❿☎✠✆é☞ê➈✠❷☞✙✠◗✠➏☞♠☞✿✂☛⑧☞❥✠➐➻ Ü☞❆, ❨ ❛☞❆☞❍☞❅☞➅☞✙ ⑧✱❥, ➠✁➑✱✐✱❀✱❧✱♠✱✐✱▼✱✙❭✁➒➨ ❨ : max z = Xn j=1 cjxj ; ì✱í Xn j=1 aijxj = bi ,i = 1, 2, . . . , m, xj ≥ 0, j = 1, 2, . . . , n ✂☛✱ñ✐✱❀✁❪î ✒✙ bi ≥ 0. ☛✱✚✱✛ ✒✥ bi < 0, × ✾ ✳✱î➽✁➓✱â✮✁➔❅ −1. ✏✱➞✚✱✛✱✙ ❧✱♠✱✐✱▼✱➧✱➨ò✱ó✁→r❨✱❭✁➒➨✱õ✫➩✱➅✱➫✱➜. ✗✠❣✠➣✠↔✏☞➞✚☞✛➥☞➦✠↕➻ ✙☞❧☞♠☞✐☞▼☞➧☞➨☞Ü♦❭✠➒➨☞✙, × ✣☞✘☞➺☞➈☞➃➲ ✢r ● ❭✁➒➨: 1. ☛ ❩❪❭♦ min z = Xn j=1 cjxj ×✁➙ z = −z 0 , ➲ ❩❪❭✁✱❤ →r❨ : max z 0 = − Xn j=1 cjxj . 2. ☛ ☎✁✆➈✁❷♦ “≤” ➂î , ×✱✌➈✁❷✁➛✁➓✱❮✁❪✝✁✞✖ Û , ➲➈✁❷→r❨✳✱î➈✁❷. ✗ (2.1) ×✁→r❨ : 2x1 + x2 + x3 = 10, x3 ≥ 0. ■✁➜ x3 ✙✁❼❽➌✁➝♦ A ❐✱❒✁➞✥✱✣✱❋✱✙✱❰✮ , ✂☛✁✄ x3 ❨✑➟✁➠✓✁✔; 3. ☛ ☎✁✆➈✁❷♦ “≥” ➂î , ×✱✌➈✁❷✁➛✁➓✁➡✱❊✝✁✞✖ Û , ➲➈✁❷→r❨✳✱î➈✁❷. ✂ ☛✁✄■✱❞✝✁✞✖ Û❨t➢✁➤✓✁✔;
$1.3线性规划问的图解法 5 一般情况下，松弛变量和多余变量在目标函数中的系数C=0: 4.若有一个变量k没有非负约束（称为自由变量），为了满足标型对变量的非负 要求，可令xk=-xm,其中≥0，xm≥0.由于可能大于xm ,也可能小于xm,所以xk可能为正，也可能为负。 例3.将下列线性规划问题化为标准型： min x=T1+2x2 满足 2x1+3x2≤6. 1+≥4 王1-z2=3, x1≥0. 解对自由变量2作楷换，令2=3一x4,其中3≥0，x4≥0.再引入松跑变量 ,多余变量6，得： ma 2x3+2z4 足 2x1+3x3-3z4+x5=6 I+T3-TA-T6=4. 1-+4=3 x5≥0，j=1,3,4,5,6. 线性规划问题模型都包含有如下基本的假设：()成比例性：2)独立性：(3)可分性：4确 定性所谓成比例性就是同一个问题的同一活动范围内，某一活动对目标函数的贡献和 对资源的消耗与活动的水平成正比例.成比例性假设将保证目标函数和约束条件为线性 的.在实际生活中，真正的线性是少有的，对此类问题有时可用线性规划模型近似地描述， 所谓独立性指任一变量的参数c和a,对其它变量不产生影响.例如，例1中生产产 品甲得到的利润不受产品乙的数量的影响，如果没有这个假定，问 题就复杂化了.所谓可分性就是允许变量取值带小数所谓确定性就是假设所有参 数C、a,和都是确定的.遇到不确定的情况，可利用灵敏度分析、参数规划或随机线性 规划来解决 S1.3线性规划问题的图解法 只有两个或三个变量的线性规划问题，可以用图解法来求解.图解法简单直观，便于 理解线性规划问题的基本概念和求解的基本原理，但实用价值不大下面用例1来说明线 性规划问题的图解法 例4.用图解法解例1中的线性规划问题例1的数学模型为 max z=6r1+4x2 满足 21+x2≤10， x1+2≤8， x2≤7， ≥0，对一切
§1.3 ú✱ü✱ý✱þ❲❱✭❳❲❨✁➥✭➦❲➧ 5 ❝✁✌✁➨✁➩✱✘, ➫✁➭✁✖Û ❿✁◗✁➯✁✖Û✱✌ ❩❪❭✁✱❤ ✒✙✁❸✱❤ cj = 0; 4. ☛✱✥✱❝✱❞✁✖Û xk ➞ ✥ ✝✁✞✁☎✁✆ (✄❨➳➲✭➵✓✁✔), ❨ ❛ì✱í❭✁➒➨✱✾✁✖Û ✙✝✠✞ ❢✱➫, ×✁➙ xk = xl − xm, ♣ ✒ xl ≥ 0, xm ≥ 0. ❹ ❍ xl × ✦✹ ❍ xm , ❜ × ✦ ✭ ❍ xm, ➭✱❅ xk × ✦ ❨✱ô, ❜ × ✦ ❨✁✞. ➴ 3. ➲ ✘✁⑦✱❧✱♠✱✐✱▼✱✚✱✛r❨✱❭✁➒➨: min z = x1 + 2x2; ì✱í 2x1 + 3x2 ≤ 6, x1 + x2 ≥ 4, x1 − x2 = 3, x1 ≥ 0. Ø ✾➺➸ ❹ ✖ Û x2 ❾✠➻✠➼, ➙ x2 = x3 − x4, ♣ ✒ x3 ≥ 0, x4 ≥ 0. ➽✠➾✠➇✠➫✠➭✠✖Û x5, ◗✁➯✁✖Û x6, Ú: max z 0 = −x1 − 2x3 + 2x4; ì✱í 2x1 + 3x3 − 3x4 + x5 = 6, x1 + x3 − x4 − x6 = 4, x1 − x3 + x4 = 3, xj ≥ 0, j = 1, 3, 4, 5, 6. ❧✱♠✱✐✱▼✱✚✱✛✱➧✱➨✱✃✁➀❻ ✥✱✗✱✘✱➟✱➠✱✙✁➚✱Þ: ➪✱●✇✈✭✙✱♠; ➶✁➹➦ ♠; ➘× ❣✱♠; ➴✱Ù ❀☞♠. ➭ ➯ ●➬➷➴✉ ❺ ♦ â☞❝☞❞☞✚☞✛☞✙☞â☞❝✠➄✠✻✠➮✃➱✠❐, ❀☞❝✠➄✠✻☞✾ ❩ ❭✠✱❤☞✙✠❒✠❮☞❿ ✾☞✦☞✧☞✙☞❈☞❉☞◆✠➄✠✻☞✙✠❰✠Ï☞●ô ✈Ð✙. ●✓✈Ð✙☞♠✠➚☞Þ➲✠Ñ✠Ò ❩ ❭✠✱❤☞❿☎✠✆é☞ê❨❧☞♠ ✙. ✌✱✏✱➞✱✍➄ ✒ , Ó ô ✙✱❧✱♠♦❇ ✥✱✙, ✾ ë✁Ô✚✱✛✱✥✮✱×✣✱❧✱♠✱✐✱▼✱➧✱➨✁Õ✠Ö✁✩✱➸☞➺. ➭ ➯Ø×✁Ù✉ØÚ❁✱❝✁✖Û xj ✙✁Û✱❤ cj ❿ aij ✾ ♣ ✢✁✖Û Ü ✎✱✍✁Ü✁Ý. ✙✱✗, ✙ 1 ✒r✍✱✎✱✎ ➱ ➷rÚ✱✖✱✙✻✱✼Ü✁Þ✎✱➱✇➬✙✱❤Û ✙Ü✁Ý, ✗✁❣➞ ✥✱■✱❞✁➚✱❀, ✚ ✛✱❺✁ß✁àr ❛. ➭ ➯âá✁ã✉ ❺ ♦✁ä✁å✖ Û ❞✷ ➐ ✭❤. ➭ ➯âæ✁ç✉ ❺ ♦ ➚✱Þ✱➭✱✥✁Û ❤ cj ✩ aij ❿ bi ✃♦ Ùä❀ä✙. ✕ä✖äÜäÙä❀ä✙è➨è➩, ×ä✻✣èéèêè♣ä❣èë✩ Ûä❤ä✐✱▼✺✁ì✱✪❧✱♠ ✐✱▼➻➜✱➝. §1.3 ➎➐➏➐➑➐➒➐➓➐➔➐→④í④î④ï ð✥✱➽✱❞✺✁ñ❞✁✖Û ✙✱❧☞♠☞✐✱▼☞✚✱✛, × ❅✱✣✁ò✱➜✱➃➻ ➫✱➜. ò✱➜✱➃✱➾✱➀✣✁ó, ❆✱❍ ✉➜✱❧✱♠✱✐✱▼✱✚✱✛✱✙✱➟✱➠✁ô✁õ✱❿✱➫✱➜✱✙✱➟✱➠✯✉ , ö ✏ ✣✁÷✷ Ü✹ . ✘✱➼✱✣✁✙ 1 ➻✱➚✇➪❧ ♠✱✐✱▼✱✚✱✛✱✙✁ò✱➜✱➃. ➴ 4. ✣✁ò✱➜✱➃✱➜✁✙ 1 ✒✙✱❧✱♠✱✐✱▼✱✚✱✛. ✙ 1 ✙✱❤✱❜✱➧✱➨❨ : max z = 6x1 + 4x2; ì✱í 2x1 + x2 ≤ 10, x1 + x2 ≤ 8, x2 ≤ 7, xj ≥ 0, ✾✱❝✱öj
6 第一章线性规划基础 解如图1-1，建立以1和2为坐标轴的直角坐标系，则第一象限（包括坐标轴）是 满足非负约束1≥0和2≥0的一切点的集合.问题中的每一个约束表示一个半平面， 将题目中的3条不等式约束条件方程改成等式方程画出直线，这3条直线左下方（包括 直线本身)和两条坐标轴围成的平面区域(3个半平面在第一象限的公共部分)，就是满足 所有约束条件的点的集合，称为可行域 目标函数z=61+4红2在坐标平面上，表示以z为参数的一族平行直线.其中的任 意一条，是产生相同利润的点的集合，称为等值线。例如6证1+4红2=12直线上所有的点 都产生12元的利润.另外，目标函数z=6z1+4红2在任一点的梯度方向为(6,4)，与目标 函数的等值线垂直。沿梯度方向目标函数值增大，沿相反方向则使目标函数值减小.按此 原则，将直线61+42=12沿右上方平行移动所得的直线，就 是目标函数比12大的直线.因为我们要使目标函数值最大，就希望找到一条使：值 尽可能大，但至少包含可行域内一点的等值线，这就是图1-1中：=6的等直线.任 z>36的等直线上将不包含可行域内的点.因此z=36就是这个问题的最大利润，此等 值线上唯一属于可行域内的点为(2,6)，即1=2,2=6是这个间题的最优解注意这 点正好是直线21+2=10和1+2=8的交点，也就是构成可行域的多边形的顶点。 101 2x1+x2=10 8 x2=7 2,6) 24 4 =36 2 x1+2=8 =12 图1-1 表1-3 顶点 2=6x1+42 T2 0 1 7 34 36 30
6 ÷✇ørùûú✱ü✱ý✱þ✱ÿ✁ Ø ✗èò 1–1, ➥ä➦❅ x1 ❿ x2 ❨èøä❭èù✙✣ ♦øä❭❸äõ ♥➅❝✁úÕ (➀è➁øä❭èù) ♦ ì✱í✝✁✞✁☎✁✆ x1 ≥ 0 ❿ x2 ≥ 0 ✙✱❝✱ö✁û✱✙✁ü✁✚. ✚✱✛ ✒✙✰ ❝✱❞☎✁✆Ð✁☞✱❝✱❞✁ý✁Ï✱➼✱õ ➲ ✛ ❩ ✒✙ 3 é Ü✳✱î☎✁✆é✱ê➈✁❷✁þ✱●✳✱î➈✁❷, ÿ ❙ ✣ ❧, ■ 3 é✣ ❧✁➛✱✘✱➈ (➀✁➁ ✣ ❧✱➠✁) ❿✱➽éø✱❭✁ù ➱r●✱✙✁Ï✱➼✁✂✁✄ (3 ❞✁ý✁Ï✱➼✌➅❝✁úÕ ✙✁✾✁❴✁☎✱❣), ❺ ♦ì✱í ➭✱✥☎✁✆é✱ê✙✁û✱✙✁ü✁✚, ✄❨ á✁✆✁✝. ❩❪❭✁✱❤ z = 6x1 + 4x2 ✌ø✱❭Ï✱➼✁❪, Ð✁☞✱❅ z ❨Û✱❤✱✙✱❝✁✞✁Ï✱❽✣ ❧. ♣ ✒✙✱❁ ➌❝ é , ♦✎✱✍✁✟â✻✱✼✙✁û✱✙✁ü✁✚, ✄❨✡✠✁☛✁s. ✙✱✗ 6x1 + 4x2 = 12 ✣ ❧✁❪✱➭✱✥✱✙✁û, ✃ ✎✱✍ 12 Ò✱✙✻✱✼. ï✱ð, ❩❪❭✁✱❤ z = 6x1 + 4x2 ✌ ❁✱❝✁û✱✙✁☞✁♣✱➈❲❶❨ (6, 4), ◆ ❩❪❭ ✱❤✱✙✳✷ ❧✁✌✣ . ✍✁☞✁♣✱➈❲❶ ❩❪❭✁✱❤ ✷✁✎✱✹, ✍ ✟✁✏➈❲❶r♥✱✶ ❩❪❭✁✱❤ ✷ ➡ ✭ . ✎ë ✯ ♥, ➲✣ ❧ 6x1 + 4x2 = 12 ✍✁✑✁❪✱➈✁Ï✱❽✁✒✁✻✱➭✱Ú✱✙✣ ❧, ❺ ♦ ❩❪❭✁✱❤✇✈ 12 ✹ ✙✣ ❧. ß❨✂☛❢✱✶ ❩❪❭✁✱❤ ✷✱✸✱✹, ❺✁✓✁✔✁✹✱✖✱❝é ✶ z ✷ ✕× ✦✹ , ö☞➋❇ ➀ ❻☞×❽✖✄✃❐❘❝✠û☞✙✳✷ ❧, ■☞❺♦ ò 1–1 ✒ z = 36 ✙✳✣ ❧. ❁☞❝ z > 36 ✙✳✣ ❧✁❪➲ Ü✁➀❻✱×❽✁✄✃❐r✙✠û. ß✱ë z = 36 ❺ ♦■✱❞✱✚✱✛✱✙✸✱✹✱✻✱✼, ë✳ ✷ ❧✁❪✁✗✱❝✁✘✱❍× ❽✁✄❲❐r✙✁û❨ (2, 6), ✙ x1 = 2,x2 = 6 ♦■✱❞✱✚✱✛✱✙✸q ➜. ✚ ➌■✱❝ ûô✺♦✣ ❧ 2x1 + x2 = 10 ❿ x1 + x2 = 8 ✙✁✛✁û, ❜✱❺♦ ❵✱●× ❽✁✄✱✙✁◗✁✜✱➂✁✢✁✣✁û. x1 + x2 = 8 (2, 6) x2 = 7 2x1 + x2 = 10 z=12 z=24 z=36 ✲ x1 0 2 4 6 8 10 ✻ x2 0 2 4 6 8 10 ò 1–1 ✤ 1–3 ✣✁û z = 6x1 + 4x2 x1 x2 0 0 0 0 7 28 1 7 34 2 6 36 5 0 30
$1.3线性规划问题的图解法 一般地，我们定义可行域的边界上改变方向的点为可行域的顶点，下一章我们将证明 线件想问颜的品优解可可以在可可仁域的佰占上找到因此我们不必解容丝古线只需求出 可行域的顶点并计算每一顶点的目标函数值就可以从中找出最优解.这个问题的各个顶 点的目标值如表1-3所示. 可见得到最大利润的点是1=2,2=6. 例5.若例1中甲和乙的利润都是每单位4元则目标函数为z=4红1+42，试用图 解法求该问题的最优解 解从图1-1可知.等值线是平行千约束条件古线1+2=8的一族平行线当 值由小变大，等值线向右上方移动时，至少包含可行域内一点的等值线与约束条件直线 1+x2=8重合.在点(1,7)和点(2,6)之间的线段上的任一点都使z值最大.这就表明 问题有无穷多个最优解，其中两个解是1=1,2=7和x1=2,2=6,目标函数值就是 32.我们称这种情况为线性规划问题有多重最优解，简称有多重解
§1.3 ✥✁✦✁✧✁★✪✩✬✫✪✭✁✮✬✯✪✰ 7 ✱✳✲✳✴, ✵✳✶✳✷✳✸✳✹✳✺✳✻✳✢✳✜✳✼✳✽✁✾✳✿✁❀❂❁✬✢✳❃✁❄✁✹✳✺✁✻✳✢❆❅✳❇, ❈✱✳❉✵✳✶✳❊✳❋❂● ❍✁■✁❏✁❑✁▲✁▼✢✁◆✁❖✁P✁✹✁◗✁❘✁✹✁✺✁✻✁✢✁✣✁❃✁✽✁❙✁❚. ❯✁❱✁✵✁✶✁❲✁❳✁❨✁❩✁❬✁❭❍ , ❪✁❫✁❴✁❵ ✹✁✺✁✻✁✢✁✣✁❃✁❛✁❜✁❝✁❞✱✣✁❃✁✢❢❡❤❣✁✐✁❥✁❦, ❧✁✹✁◗✁♠✪♥✬❙✁❵✁◆✁❖✁P. ♦✁♣▲✁▼✢✁q✁♣✁✣ ❃✁✢❢❡❤❣✁❦✁r✤ 1–3 s✁t. ✹✁✉✁✈✁❚✁◆✁✇✁①✁②✁✢✁❃✁③ x1 = 2,x2 = 6. ④ 5. ⑤✁⑥ 1 ♥✁⑦✬⑧✪⑨✬✢✁①✁②✁⑩✁③✁❞✁❶✁❷ 4 ❸, ❹❢❡❤❣✁✐✁❥✁❄ z = 4x1 + 4x2, ❺✁❻✁❼ P✁❽✁❴✁❾▲✁▼✢✁◆✁❖✁P. ❿ ♠✖❼ 1–1 ✹✖➀, ❬✖❦❍③✖➁✖✺✖➂✖➃✖➄✖➅✖➆✖❭❍ x1 + x2 = 8 ✢✱✖➇➁✖✺❍ . ➈ z ❦➊➉➌➋➍✿➍✇, ❬➍❦❍ ❁➌➎➍✽➍❀➍➏➍➐➍➑, ➒➍➓➍➔➍→➍✹➍✺➍✻➊➣ ✱❃➍✢➍❬➍❦❍➍↔➃➍➄➍➅➍➆➍❭❍ x1 + x2 = 8 ↕✁➙. ❘✁❃ (1, 7) ⑧✁❃ (2, 6) ➛✁➜✁✢❍✁➝✽✁✢✁➞✱❃✁⑩✁➟ z ❦✁◆✁✇. ♦✁❧✤ ● ▲✁▼✁➠✁➡✁➢✁➤♣✁◆✁❖✁P, ➥✪♥✬➦✁♣✁P✁③ x1 = 1,x2 = 7 ⑧ x1 = 2,x2 = 6, ❡❤❣✁✐✁❥✁❦✁❧✁③ 32. ✵✁✶✁➧✁♦✁➨✁➩✁➫✁❄❍✁■✁❏✁❑✁▲✁▼➯➭✁➲✁➳✁➵✁➸❿ , ➺✁➧➠✡➲✁➳❿
第一章线性规划基础 习题 1.一个毛纺厂用羊毛和涤纶生产A、B、C三种混纺毛料，生产1单位产品所需要的 原料如表1-4所列。 表1-4 羊毛 涤纶 3 2 B C 4 4 3种产品的单位利润分别为4、1,5.每月可购进的原料限额为羊毛8000单位，涤 纶3000单位，问此毛纺厂应如何安排生产才能获得最大利润？请建立线性规划模型。 2.某饲料厂生产的一种动物饲料由6种配料混合配成。每种配料中所含的营养成分 A、B及单位配料购入价由表1-5给出 表1-5 12345 6 102 B 单位配料购入价353060502712 每单位饲料中至少应含A9单位，B19单位.问饲料厂如何配方，使饲料的成本最低且 能满足要求？要求建立此问题的线性规划模型 3.某工厂生产A、B、C三种产品，在车间1、2连续加工，用一种每天购入数量最多 为300单位的原料.车间1、2每天可用工时为320,200.放置产品的成品仓库面积也有限 制，如只生产产品A,可放置400单位，而每单位B的放置面积2倍于A.每单位C的放 置面积为A的1/3. 每单位A在车间1要加工1h,在车间2要加工1/2h,需1单位原料，利润为1元 每单位B在车间1要加工2h,在车间2要加工1/3泓，需1/4单位原料，利润为2元 每单位C在车间1要加工1/4h.在车间2要加工1/4h.需1/8单位原料.利润为1.5 元 问如何安排生产使利润最大？要求建立此何题的线性规刻模型， 4其汽车 题16 车辆种类 成本（元/辆） 收入() 9000 -12000 四轮有等箍车 800 串使车（茶小车掩2判 6000 16000 轮买等车 5000 12000 可驶新卡车的对只有30人该 新增的任务能力如只务卡车，可务50如，一 如卡车任务时间3春于以便有拖车麦成这拖车4倍于无盖车种要求卡车如数
8 ➻✪➼✬➽➾✥✁✦✁✧✁★✁➚✁➪ ➶ ➹ 1. ✱♣✁➘✁➴✁➷✁❻✁➬✁➘✁⑧✁➮✁➱✁✃✁❐ A❒ B ❒ C ❮✁➨✁❰✁➴✁➘✁Ï, ✃✁❐ 1 ❶✁❷✁❐✁Ð✁s✁❫✁Ñ✁✢ Ò Ï✁r✤ 1–4 s✁Ó. ✤ 1–4 ➬ ➘ ➮ ➱ A 3 2 B 1 1 C 4 4 3 ➨✁❐✁Ð✁✢✁❶✁❷✁①✁②✁Ô✁Õ✁❄ 4❒ 1❒ 5. ❞✁Ö✁✹✁×✁Ø✁✢Ò Ï✁Ù✁Ú✁❄✁➬✁➘ 8000 ❶✁❷, ➮ ➱ 3000 ❶✁❷, ▲❱✁➘✁➴✁➷✁Û✁r✁Ü✁Ý✁Þ✁✃✁❐✁ß✁à✁á✁✈✁◆✁✇✁①✁②? â✁ã✁ä❍✁■✁❏✁❑✁å✁æ. 2. ç✁è✁Ï✁➷✁✃✁❐✁✢✱➨✁➐✁é✁è✁Ï✪➉ 6 ➨✁ê✁Ï✁❰✁➙✁ê✁ë. ❞✁➨✁ê✁Ï✪♥✬s✁→✁ì✁í✁î✁ë✁Ô A❒ B ï✁❶✁❷✁ê✁Ï✁×✁ð✁ñ✪➉ ✤ 1–5 ò✁❵. ✤ 1–5 1 2 3 4 5 6 A 1 0 2 2 1 2 B 0 1 3 1 3 2 ❶✁❷✁ê✁Ï✁×✁ð✁ñ 35 30 60 50 27 12 ❞✁❶✁❷✁è✁Ï✪♥✬➒✁➓✁Û✁→ A9 ❶✁❷,B19 ❶✁❷. ▲è✁Ï✁➷✁r✁Ü✁ê✁❀, ➟✁è✁Ï✁ì✁ë✁ó✁◆✁ô✁õ à✁ö✁÷✁Ñ✁❴? Ñ✁❴✁ã✁ä✁❱▲✁▼ì❍✁■✁❏✁❑✁å✁æ. 3. ç✁ø✁➷✁✃✁❐ A❒ B ❒ C ❮✁➨✁❐✁Ð, ❘✁ù✁➜ 1❒ 2 ú✁û✁ü✁ø, ❻✱➨✁❞✁ý✁×✁ð✁❥✁þ✁◆➤ ❄ 300 ❶✁❷✁ìÒ Ï. ù✁➜ 1❒ 2 ❞✁ý✁✹✁❻✁ø✁➑✁❄ 320,200. ÿ✁✁❐✁Ð✁ì✁ë✁Ð✁✂✁✄✁☎✁✆✁✝➠Ù ✞ , r✁❪✁✃✁❐✁❐✁Ð A, ✹✁ÿ✁ 400 ❶✁❷, ✟✁❞✁❶✁❷ B ì✁ÿ✁✁☎✁✆ 2 ✠✁➂ A. ❞✁❶✁❷ C ì✁ÿ ✁☎✁✆✁❄ A ì 1/3. ❞✁❶✁❷ A ❘✁ù✁➜ 1 Ñ✁ü✁ø 1h, ❘✁ù✁➜ 2 Ñ✁ü✁ø 1/2h, ❫ 1 ❶✁❷Ò Ï, ①✁②✁❄ 1 ❸. ❞✁❶✁❷ B ❘✁ù✁➜ 1 Ñ✁ü✁ø 2h, ❘✁ù✁➜ 2 Ñ✁ü✁ø 1/3h, ❫ 1/4 ❶✁❷Ò Ï, ①✁②✁❄ 2 ❸. ❞✁❶✁❷ C ❘✁ù✁➜ 1 Ñ✁ü✁ø 1/4h, ❘✁ù✁➜ 2 Ñ✁ü✁ø 1/4h, ❫ 1/8 ❶✁❷Ò Ï, ①✁②✁❄ 1.5 ❸. ▲r✁Ü✁Ý✁Þ✁✃✁❐✁➟✁①✁②✁◆✁✇? Ñ✁❴✁ã✁ä✁❱▲✁▼ì❍✁■✁❏✁❑✁å✁æ. 4. ç✁✡✁ù✁☛✁☞✁✌✁✍➠✁✎✁✏ 50 ✑✁❸✁✹✁❻✁➂✁✒✁✇✁ù✁✓, ➠ 4 ➨✁ù✁✹✁✔✁✕✁✖, ❞✁✗✁ù✁ì✁ë ó✁ï✁❞✁✘✁✙✁✚✁ð✁r✤ 1–6 s✁Ó. ✛ 1–6 ✜✣✢✥✤✣✦ ✧✩★ (✪/✢ ) ✫✩✬ (✪) ✭✩✜ 9000 −12000(✮✩✯) ✰✩✱✩✲✩✳✩✴✜ 8000 29500 ✵✩✶✩✷✴✜ (✸ ✢✩✭✩✜✴ 2 ✢ ) 6000 16000 ✰✩✱✩✹✩✳✩✴✜ 5000 12000 ✹✁✺✁✻✁✼✁✽✁ù✁ì✁✍✁✾✁❪➠ 30 ✿. ❾✁✌✁✍✁✼✁❀✁ì✁❁✁❂✁à✁❃✁r✖❪✁❂❄✽✖ù, ✹✁❂ 50 ✗, ✱ ✗✁✽✁ù✁ì✁❁✁❂✁➑✁➜ 3 ✠✁➂✁❅✁❆➠✁❇✁❈ù✁❉❋❊❍●✁■❈ù,4 ✠✁➂➡✁❇✁❈ù. ❏✁Ñ✁❴✁✽✁ù✁✗✁❥
$1.3线性规划问题的图解法 9 与拖车组数之比最少为43. 问该公司怎样使用资金使每季度收入最大？要求建立此问题的线性规划模型， 5.将下列线性规划问题模型化为标准型 min z=-3x1+4x2-2x3+5x1: 满足 4x1-x2+2x3-x4=-2 1+2+33-x4≤14， -r1+3x2-工3+2r422 x1,x2.x3>0 6.用图解法解下列线性规划问题： (1) max 2=工1十C2: 满足 -x1+x2≤4 31+5r2≤30， 5x1+22≤20， x1,x2≥0. (2) min =3x+22: 满足 x1+2r2≥4， 1+62≥6， 1,2≥0
§1.3 ✥✁✦✁✧✁★✪✩✬✫✪✭✁✮✬✯✪✰ 9 ↔✁❈ù✁❑✁❥✁➛❋▲✬◆✁➓✁❄ 4:3. ▲❾✁✌✁✍✁▼✁◆✁➟✁❻✎✁✏➟✁❞✁✘✁✙✁✚✁ð✁◆✁✇? Ñ✁❴✁ã✁ä✁❱▲✁▼ì❍✁■✁❏✁❑✁å✁æ. 5. ❊✁❈✁Ó❍✁■✁❏✁❑✁▲✁▼✁å✁æ✁❖❄✁❣✁Pæ : min z = −3x1 + 4x2 − 2x3 + 5x4; ö✁÷ 4x1 − x2 + 2x3 − x4 = −2, x1 + x2 + 3x3 − x4 ≤ 14, −x1 + 3x2 − x3 + 2x4 ≥ 2, x1, x2, x3 ≥ 0. 6. ❻✁❼✁P✁❽✁P✁❈✁Ó❍✁■✁❏✁❑✁▲✁▼: (1) max z = x1 + x2; ö✁÷ −x1 + x2 ≤ 4, 3x1 + 5x2 ≤ 30, 5x1 + 2x2 ≤ 20, x1, x2 ≥ 0. (2) min z = 3x1 + 2x2; ö✁÷ x1 + 2x2 ≥ 4, x1 + 6x2 ≥ 6, x1, x2 ≥ 0