2019/6/20 非标准形式的指派问题 3.5运输向题的中转向题 非标准形式的湘同愿 该人化作肌叫 价以 例8.、腾飞电子公司在大连和广州 6 来不 岛较适，公司同意大连分厂向青岛直 A性 3.5运榆向题的中转问题 3.5远输向题的中转问题 新公得置 器：凝 先公：赞 在之。电之 △性 3.5远榆问题的中转向题 3.5远输间题的中转向题 扩大的给产平与运价表】 M 2 S M 品 2.运给表中不可能方名的运取 作M自身对白身的试为0， 、对干最使方名。其中气，为身时身的运量，实际上性 A性 702019/6/20 10 55 非标准形式的指派问题 3. 一个人可做几件事的指派问题——若某个人可以做几件事，则 将该人化作几个“人”来接受指派。这几个“人”做同一件事 的费用系数当然都一样。 4. 某事一定不能由某人做的指派问题——若某事一定不能由某人 做，则可将相应的费用系数取为足够大的数 M 。 非标准形式的指派问题 56 3.5 运输问题的中转问题 在原运输问题上增加若干转运站。运输方式有：产地 → 转运站、转 运站 → 销地、产地 → 产地、产地 → 销地、销地 → 转运站、销地 → 产 地等。 例8、腾飞电子仪器公司在大连和广州 有两个分厂生产同一种仪器，大连分厂 每月生产400台，广州分厂每月生产600 台。该公司在上海和天津有两个销售公 司负责对南京、济南、南昌、青岛四个 城市的仪器供应。另外因为大连距离青 岛较近，公司同意大连分厂向青岛直接 供货，运输费用如图，单位是百元。问应该如何调运仪器， 可使总运输费用最低？图中 1- 广州、2 - 大连、 3 - 上海、4 - 天津、5 - 南京、6 - 济南、7 - 南昌、8 - 青岛 57 解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型： 目标函数：Min f = 所有可能的运输费用（运输单价与运输量乘积之和） 约束条件： 对产地（发点） i ：输出量 - 输入量 = 产量 对转运站（中转点）：输入量 - 输出量 = 0 对销地（收点） j ：输入量 - 输出量 = 销量 例8．（续） 目标函数： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48 约束条件： s.t. 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 = 1,2,3,4,5,6,7,8 3.5 运输问题的中转问题 58 3.5 运输问题的中转问题 用EXCEL软件求得结果： x13 = 550 x14 =50 ； x23 = 0 x24 = 100 x28 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 。 最小运输费用为：4600百元 例9、某公司有A1、 A2、 A3三个分厂生产某种物资，分别供应B1、 B2、 B3、 B4 四个地区的销售公司销售。假设质量相同，有关数据如下表： 试求总费用为最少的调运方案。 假设： 1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运； 2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地； 3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之 间转运。 B1 B2 B3 B4 产量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量 3 6 5 6 和=20 59 3.5 运输问题的中转问题 运价如下表： 解：把此转运问题转化为一般运输问题： 1、把所有产地、销地、转运站都同时看作产地和销地； 2、运输表中不可能方案的运费取作M，自身对自身的运费为0； 3、Ai： 产量为 20+原产量， 销量为 20； Ti ： 产量、销量均为 20； Bi： 产量为 20， 销量为 20 +原销量，其中20为各点可能变化的最大流量 4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。 A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 A1 1 3 2 1 4 3 3 11 3 10 A2 1 --- 3 5 --- 2 1 9 2 8 A3 3 --- 1 --- 2 3 7 4 10 5 T1 2 3 1 1 3 2 2 8 4 6 T2 1 5 --- 1 1 1 4 5 2 7 T3 4 --- 2 3 1 2 1 8 2 4 T4 3 2 3 2 1 2 1 --- 2 6 B1 3 1 7 2 4 1 1 1 4 2 B2 11 9 4 8 5 8 --- 1 2 1 B3 3 2 10 4 2 2 2 4 2 3 B4 10 8 5 6 7 4 6 2 1 3 60 3.5 运输问题的中转问题 扩大的运输问题产销平衡与运价表： A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 产量 A1 0 1 3 2 1 4 3 3 11 3 10 27 A2 1 0 M 3 5 M 2 1 9 2 8 24 A3 3 M 0 1 M 2 3 7 4 10 5 29 T1 2 3 1 0 1 3 2 2 8 4 6 20 T2 1 5 M 1 0 1 1 4 5 2 7 20 T3 4 M 2 3 1 0 2 1 8 2 4 20 T4 3 2 3 2 1 2 0 1 M 2 6 20 B1 3 1 7 2 4 1 1 0 1 4 2 20 B2 11 9 4 8 5 8 M 1 0 2 1 20 B3 3 2 10 4 2 2 2 4 2 0 3 20 B4 10 8 5 6 7 4 6 2 1 3 0 20 销量 20 20 20 20 20 20 20 23 26 25 26 240