1 2 2 600 广 州 3 6 3 上 海 3 6 4 4 4 3 6 天津 2 5 1 400 大 连 4
↑
供应量
图 3—1 公司运输网络
对于发点1、2有供应量约束
x13+x14≤600 x23+x24+x28≤400
对于中转点3、4有平衡约束
x13+x23 ??x35 ??x36 ??x37 ??x38 = 0 x14+x24 ??x45 ??x46 ??x47 ??x48 = 0
对于需求点5、6、7、8有需求量约束
x35+x45 = 200 x36+x46 = 150 x37+x47 = 350 x38+x48 +x28 = 300
由此可得该问题的线性规划模型
min f = 2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37
+6x38+4x45+4x46+6x47+5x48 x13+x14≤600 x23+x24+x28≤400
x13+x23 ??x35 ??x36 ??x37 ??x38 = 0 x14+x24 ??x45 ??x46 ??x47 ??x48 = 0 x35+x45 = 200 x36+x46 = 150 x37+x47 = 350 x38+x48 +x28 = 300
xij≥0，对于所有i、j
第三章——16
5 南京 200
6 济 南 150 350
7 南昌 8 青 岛 300 ↑
需求量
对于上述模型，用单纯形法可以得到最优解，但如果将其转化成运输问题模型，用表上作业法求解不仅简单而且直观。具体做法是：每个中转站对于发点来说可以看作是销地，其销量为所有可以运到该地的产量之和；每个中转站对于销地来说可以看作是产地，其产量等于其销量。这样，该问题就变成了4个产地、6个销地的运输问题。产地到销地的单位运价的处理办法是：中转站自己到自己的运价为0，网络图中，不能直接运输的产地到销地之间的运价为M，其余运价直接用网络图中标明的数字。问题的产销平衡表如下表所示。
表3—21 销地 产地 1（广州） 2（大连） 3（上海） 4（天津） 需求量
用表上作业法，可求得该问题的最优调运方案如表3—22所示。 表3—22 销地 产地 1（广州） 2（大连） 3（上海） 4（天津） 需求量 即，广州向中转站上海运550台，天津运50台；大连向中转站天津运100台，直接向青岛运300台；中转站上海向南京和南昌分别运200台和350台；中转站天津向济南运150台。最小运费为4600元
3(上海) 4(天津) 5(南京) 6(济南) 7(南昌) 8(青岛) 550 450 1000 50 100 850 1000 200 200 150 150 350 350 300 300 供应量 600 400 1000 1000 3000 3000 3(上海) 4(天津) 5(南京) 6(济南) 7(南昌) 8(青岛) 2 3 0 M 1000 3 1 M 0 1000 M M 2 4 200 M M 6 4 150 M M 3 6 350 M 4 6 5 300 供应量 600 400 1000 1000 3000 3000 第三章——17
习 题 三
1．判断表3—23、表3—24中给出的调运方案能否作为表上作业法求解的初始基可行解？为什么？
表3—23 销 地 产地 A1 A2 A3 需求量
表3—24 销 地 产地 A1 A2 A3 需求量
2．用表上作业法求解下面运输问题
表3—25 销地 单价 产地 A1 A2 A3 需求量 3．产地A1、A2及销地B1、B2、B3的有关数据如下表。销地B1、B2、B3允许缺货，产地A1、A2允许存储。问怎样调配，使总费用最少？建立其数学模型，并用表上作业法求解。
第三章——18
B1 50 0 50 B2 100 100 B3 150 150 B4 0 50 50 供应量 200 100 50 B1 60 10 70 B2 100 100 B3 140 10 150 B4 50 50 供应量 200 100 70 B1 3 12 6 300 B2 9 20 11 500 B3 8 7 13 900 B4 6 10 14 600 供应量 600 1000 700 表3—26 销地 单价 产地 A1 A2 需求量 单位缺货费 B1 4 6 50 3 B2 6 2 100 8 B3 8 4 100 5 供应量 200 200 单位存储费 5 4 4．某百货公司去外地采购A、B、C、D四种规格的服装，数量分别为A——1500套；B——2000套，C——3000套，D——3500套。有三个城市可供应上述规格服装，供应数量为城市I——2500套，II——2500套，III——5000套。由于这些城市的服务质量、运价等销售情况不一，预计售出后的利润（元/套）也不同，详见表3-52。
表3—27
I II III A 10 8 9 B 5 2 3 C 6 7 4 D 7 6 8 请帮助该公司确定一个预期盈利最大的采购方案。
5．甲、乙、丙三个城市每年分别需煤炭320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量为A——400万吨，B——450万吨。由煤矿至各城市的单位运价（万元/万吨）见表3—28。
表3—28
A B 甲 15 12 乙 18 25 丙 22 16 由于需大于供，经研究平衡决定，甲城市供应量不少于280万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。此外甲城市每缺1万吨煤损失10万元，丙城市每缺1万吨煤损失12万元。试求将供应量分配完又使总费用（包括缺货费）为最低的调运方案。
6．某厂要完成合同规定的三个时期的某产品订货任务，现已知各时期工厂的生产能力、合同任务、生产单位产品的成本等数据如表3—29所示。又已知单位产品每时期存储费为1，现要求：建立该问题的LP数学模型；将其化为运输问题，并用表上作业法求解该问题。
第三章——19
表3—29 时期 1 2 3
生产能力 30 20 25 定货量 20 15 20 生产成本 8 12 11 第三章——20