习 题1. 某油田产量为Q 吨/年，分别供应A 、B 、C 、D 四个城市，各城市每年的原油需求量分别为10、50、5、35吨。
油田与各城市间有八条通路相联系（如图所示），每条通路的允许流量和费用如表所示。
问如何安排运送计划最为经济？试建立此问题的数学模型。
通路 1 2 3 4 5 6 7 8 允许流量 40 10 20 40 40 70 18 40 单位运输费用10804010357040852. 某冷饮店要制定七八月份的日进货计划。
该品质的冷饮进货成本为每箱30元，销售价为50元，当天销售后每箱可获利20元。
如果剩一箱，由于冷藏及其它原因要亏损10元。
今年的市场情况不清楚，但有前两年同期120天的日销售资料如表所示。
试问今年平均每天进多少箱为好？日销售量（箱）完成销售的天数100 24 110 48 120 36 130123. 试将下列线性规划问题化为标准型。
⎪⎪⎩⎪⎪⎨⎧≥-=-+-≥+-≤++-+-=无约束，，321321321321321052327..32min x x x x x x x x x x x x t s x x x f4. 试写出下列线性规划问题的对偶问题。
⎪⎪⎩⎪⎪⎨⎧≥=+≥-≤++=无约束，21212121210510342023..54max x x x x x x x x t s x x f 4 56732 81 油田 A C B D5. 某工厂计划生产A 、B 两种产品，生产这两种产品需要煤、电力和劳动力三种资源。
已知该厂可利用的煤有360吨，电力有200千瓦，劳动力有300个，生产每千克产品的资源消耗量和可获得的利润如表所示。
问该厂应生产A 、B 两种产品各多少千克才能使总利润最大？请用单纯形法求解。
A B资源 限制量 煤 9 4 360 电力 4 5 200 劳动力 3 10 300 利润7126. 设有如图所示的网络图，计算网络图中各节点的最早、最迟时间，并求出关键路线。
7. 从油田铺设管道，把原油运输到原油加工厂。
要求管道必须沿着如图所示的给定路线进行铺设，图中顶点1为油田，顶点8为原油加工厂，弧权为相应路段的管道长度，应如何铺设管道，才能使油田到原油加工厂的管道总长最短？试用标号算法确定其最短距离及其相应的路线。
产品资源消耗量/kg资源1 3 5 24A B G F DH E C 47 7 10 5 3 23 7 54 59 54 1 6 76 4 41 2 3 4 5 678习题解答1. 某油田产量为Q 吨/年，分别供应A 、B 、C 、D 四个城市，各城市每年的原油需求量分别为10、50、5、35吨。
油田与各城市间有八条通路相联系（如图所示），每条通路的允许流量和费用如表所示。
问如何安排运送计划最为经济？试建立此问题的数学模型。
通路 1 2 3 4 5 6 7 8 允许流量 40 10 20 40 40 70 18 40 单位运输费用1080401035704085解：设各条通路要安排的全年运油总量分别为x j （j =1, 2, …, 8）。
本问题的目标为总运输费用最小，即876543218540703510408010min x x x x x x x x f +++++++=首先，考虑各城市需求量约束，则有）（供应城市）（供应城市）（供应城市）（供应城市D C B A 3555010876265375481≥+++≥--≥-+≥-x x x x x x x x x x x x其次，总供应量不能超过油田产量，即Q x x x x ≤+++4321再次，各条通路的运量不能超过其允许流量，则有404020104054321≤≤≤≤≤x x x x x 401870876≤≤≤x x x 故该问题的数学模型为4 56 7328 1 油田 A C B D⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎧=≥≤≤≤≤≤≤≤≤≤+++≥+++≥--≥-+≥-+++++++=)8,,1(040187040402010403555010..8540703510408010min 87654321432187626537548187654321 j x x x x x x x x x Qx x x x x x x x x x x x x x x x t s x x x x x x x x f j2. 某冷饮店要制定七八月份的日进货计划。
该品质的冷饮进货成本为每箱30元，销售价为50元，当天销售后每箱可获利20元。
如果剩一箱，由于冷藏及其它原因要亏损10元。
今年的市场情况不清楚，但有前两年同期120天的日销售资料如表所示。
试问今年平均每天进多少箱为好？日销售量（箱）完成销售的天数概率值 100 24 24/120=0.2 110 48 48/120=0.4 120 36 36/120=0.3 130 12 12/120=0.1合计1201.0解：先根据前两年的销售数据，确定不同日销售量的出现概率值，如上表所示。
再根据每天可能的销售量，计算不同进货方案的收益值，并编成如下所示的决策表。
100箱C 1 P(C 1) = 0.2 110箱C 2 P(C 2) = 0.4 120箱C 3 P(C 3) = 0.3 130箱C 4 P(C 4) = 0.1 100箱A 1 2000 2000 2000 2000 110箱A 2 1900 2200 2200 2200 120箱A 3 1800 2100 2400 2400 130箱A 41700200023002600最后由公式),()()(41j j i j i C A U C P A U ∑==计算各销售方案的期望利润值，则U(A 1) = 2000×0.2+2000×0.4+2000×0.3+2000×0.1=2000 U(A 2) = 1900×0.2+2200×0.4+2200×0.3+2200×0.1=2140销 售 结 局 利润（元）方 案U(A 3) = 1800×0.2+2100×0.4+2400×0.3+2400×0.1=2160 U(A 4) = 1700×0.2+2000×0.4+2300×0.3+2600×0.1=2090 故最优方案2160}2090,2160,2140,2000max{)(max ===∈*i AA i A U A i可见，日进货120箱的计划方案A 3的期望利润值最大，应选为最优方案。
3. 试将下列线性规划问题化为标准型。
⎪⎪⎩⎪⎪⎨⎧≥-=-+-≥+-≤++-+-=无约束，，321321321321321052327..32min x x x x x x x x x x x x t s x x x f 解：令333x x x ''-'=且3x '、03≥''x 在第一个约束条件中引入松弛变量x 4，第二个约束条件中引入剩余变量x 5，第三个约束条件两边同乘以1，同时将目标函数变为求最大值，整理可得⎪⎪⎩⎪⎪⎨⎧≥'''=''-'+-=-''-'+-=+''-'++''-'+-=-='0522327..332min max 543321332153321433213321x x x x x x x x x x x x x x x x x x x x t s x x x x f f ，，，，，4. 试写出下列线性规划问题的对偶问题。
⎪⎪⎩⎪⎪⎨⎧≥=+≥-≤++=无约束，21212121210510342023..54max x x x x x x x x t s x x f 解：令222x x x ''-'=且2x '、02≥''x 将第二个约束条件两边同乘以1，第三个约束条件转化为两个不等式，则原问题可改写为⎪⎪⎪⎩⎪⎪⎪⎨⎧≥'''≤''-'+-≤''+'--⇒≥''-'+-≤''-'+-≤''-'+''-'+=05551033420223..554max 221221221221221221221x x x x x x x x x x x x x x x x x x t s x x x f ，，由原问题与对偶问题的关系，可得相应的对偶问题为⎪⎪⎩⎪⎪⎨⎧≥-≥-+--≥+-+≥+--+--=0532532443..551020min 43214321432143214321y y y y y y y y y y y y y y y y t s y y y y f ，，，5. 某工厂计划生产A 、B 两种产品，生产这两种产品需要煤、电力和劳动力三种资源。
已知该厂可利用的煤有360吨，电力有200千瓦，劳动力有300个，生产每千克产品的资源消耗量和可获得的利润如表所示。
问该厂应生产A 、B 两种产品各多少千克才能使总利润最大？请用单纯形法求解。
A B资源 限制量 煤 9 4 360 电力 4 5 200 劳动力 3 10 300 利润712解：设产品A 、B 的产量分别为x 1、x 2千克，则上述安排生产计划问题的数学模型为⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤++=03001032005436049..127max 2121212121x x x x x x x x t s x x f ， 将模型标准化，可得⎪⎪⎩⎪⎪⎨⎧=≥=++=++=+++=5,,2,103001032005436049..127max 52142132121 j x x x x x x x x x x t s x x f j ，表1 初始单纯形表c j712 0 0 0 θiC B X B b x 1 x 2 x 3 x 4 x 5 0 x 3 360 9 4 1 0 0 90 0 x 4 200 4 5 0 1 0 40 0 x 5 3003 [10] 0 0 1 30 σj712产品资源消耗量/kg资源表2 x 5替换为x 2后的单纯形表c j712 0 0 0 θiC B X B b x 1 x 2 x 3 x 4 x 5 0 x 3 240 39/5 0 1 0 -2/5 400/13 0 x 4 50 [5/2] 0 0 1 -1/2 20 12 x 2 303/10 1 0 0 1/10 100 σj17/5-6/5表3 x 4替换为x 1后的单纯形表c j7 12 0 0 0 θiC B X B b x 1 x 2 x 3 x 4 x 5 0 x 3 84 0 0 1 -78/25 29/25 — 7 x 1 20 1 0 0 2/5 -1/5 — 12 x 2 240 1 0 -3/25 4/25 — σj-34/25-13/25表3最后一行的所有检验数σj 都已为负或零，这表示目标函数值已不可能再增大，于是得到最优解[][]T T x x x x x X 0084242054321==*且相应的最优值（即工厂的最大总利润）f * = 428。