PPT《关于退化问题》

关于退化问题

1、初始解退化 即所求初始基变量的个数少于 m+n?1.

必须补足基变量的个数,否则不能正常解出 m+n 个ui 和vj (如填写一个数字同时满足了一厂一商,则需在同行或同列中填写一个数字0,以保证恰好有m+n-1个数字),基可行解中不能有某个基变量独占一行一列

2、迭代过程中出现退化 闭合回路中偶数次基变量同时有多个达到最小,变换后,有多个原基变量变为 0,选运费最大者为退基变量,其余保留在新的基解中 供大于求 供不应求 增加虚拟销地 增加虚拟产地 产销平衡的运输问题 对应的运距(或运价) ? 转化 3.3 运输问题的推广

一、产销不平衡的运输问题 例2 供大于求的运输问题 运费及产销量表

180 100

30 40

30 销量

70 40

50 20

6 4

5 8

3 2

7 5

6 5

1 2 A1 A2 A3 A4 产量 B1 B2 B3 例2 解: 引入虚拟销地B4,(或理解为仓库),就地 销售 ,运费为零

180 180

30 40

30 80 销量

70 40

50 20

6 4

5 0

8 3

2 0

7 5

6 0

5 1

2 0 A1 A2 A3 A4 产量 B1 B2 B3 B4 例2 求初始方案: 用最小元素法,但零视为最大元素.(?)

180 180

30 40

30 80 销量

70 40

50 20

6 4

5 0

8 3

2 0

7 5

6 0

5 1

2 0 A1 A2 A3 A4 产量B1 B2 B3 B4 /20

20 /30

10 /10

10 /10

60 /30

30 /30 /50 6/30 4/10

5 0/30

8 3/10 2/30

0 7

5 6 0/50

5 1/20

2 0

1 0

2 3

3 0 -3

3 例2 检验 所以,此方案为最优方案.其调运费用为:30*6 + 10*4 + 10*3 +30*2 + 20*1 =

330 例题3:弹性需求问题(P96) 设有三个化肥厂供应四个地区,资料如下: 10不限

030 7070

3050 最低需求最高需求

506050 1715 -

221923 131320

161419 A B C 产量 丁丙乙甲运价 地区化肥厂 例题3:解题思路: 设法转化为标准型本题产量160万吨,最低需求110万吨,最高需求无限.实质上比较现实的最高需求为210万吨(根据现有产量)产量大于最低需求;

小于最高需求.而标准型是:产量=销量.处理办法:设想一个虚拟化肥厂D,其年产量50万吨,但这个产量只能供应可有可无的最高需求部分,于是各地的需求也应分为两个部分:基本需求、机动需求虚拟产量的运输费用为零,但它对于基本需求来讲,运费为无穷大. 例题3:建模

1 产量 丁2 丁1 丙乙甲2 甲1 运价 地区煤矿

210210 50

10 30

70 20

30 需求量

50 60

50 50 1715M0 1715MM

2219230 131320M

1614190 161419M A B C D

1 产量 丁2 丁1 丙乙甲2 甲1 运价 地区煤矿

210210 50

10 30

70 20

30 需求量

50605050 1715M0 1715MM

2219230 131320M

1614190 161419M A B C D

30 20

20 30

50 20

10 30

20 20

30 20

0 例题3:求解(Vogel法)

50 10

30 70

20 30

50 60

50 50 1715M0 1715MM

2219230 131320M

1614190 161419M /50 /20 /30 /0 /20 /30 /20

7 7 /30

7 12

8 6

7 8 -8

8 /10 得最优调运方案:C供应甲

50、A和B供应乙

70、B供应丁40(万t),不供应丙.最低调运费用为:50*19 + 70*13 + 40*15 = 2460(万元) 例题3:检验 特点: 调运的物资不是由产地直接运送到销地,而是经过若干中转站送达.求解思路:转化成一个等价的产销平衡运输问题,再用表上作业法求出最优调运方案. 如何转化 ?

二、转运问题 第一步,将产地、转运点、销地重新编排,转运点既作为产地又作为销地;

第二步,各地之间的运距(或运价)在原问题运距(运价)表基础上进行扩展:从一地运往自身的单位运距(运价)记为零,不存在运输线路的则记为M(一个足够大的正数);

第三步,由于经过转运点的物资量既是该点作为销地的需求量,又是该点作为产地时的供应量,但事先又无法获取该数量的确切值,因此通常将调运总量作为该数值的上界.对于产地和销地也作类似的处理.(参见P98例4)

三、运输模型的应用 例题4:某机床厂定下一年合同分别于各季度末交货.已知各季度生产成本不同,允许存货,存储费0.12万元/台季,

三、四季度可以加班生产,加班生产能力8台/季,加班费用3万元/台25301545 10.5510.81111.1

30322028 1234 交货台数 单位成本(万元) 正常生产能力 季度 例4 分析: 可用线性规划,但用运输问题更简单要决策的问题是各季度生产量和交货量设xij表示第i季度生产第j季度交货的台数因加班时间生产成本不同,故要区别开来,三四季度可加班,视同增加两个季度需求量合计115台,生产能力合计126台,供需不平衡,因此,增加一虚拟季度交货. 例4 建模: .

126126 25

30 15

45 11 需求量

30 32

20 8

28 8 10.55 10.67 10.79 10.91

0 M 10.8 10.92 11.04

0 M M

11 11.12

0 M M

14 14.12

0 M M M 11.1

0 M M M 14.1

0 1季度正常生产2季度正常生产3季度正常生产3季度加班生产4季度正常生产4季度加班生产 产量 虚拟

1 2

3 4 季度 成本 交货生产 例4 结果

126126 25

30 15

45 11 需求量

30 32

20 8

28 8

25 5

30 2

10 10

8 28

5 3 1季度正常生产2季度正常生产3季度正常生产3季度加班生产4季度正常生产4季度加班生产 产量 虚拟

1 2

3 4 季度 生产 交货生产 例题5 航运调度问题(P1023.6) 某航运公司承担六个城市A、B、C、D、E、F之间的四条航线,已知各航线的起点、终点及每天所需的航班数如下表.又知各城市之间的航行天数,假定船只型号相同,装卸货时间各一天,问该公司至少要配备多少条船才能满足需要?

3 2

1 1 DCFB EBAD

1234 每天航班数 终点 起点 航线 例5 城市之间航行天数表 .

0 1

2 14

7 7

1 0

3 13

8 8

2 3

0 15

5 5

14 13

15 0

17 20

7 8

5 17

0 3

7 8

5 20

3 0 ABCDEF A B C D E F Cij 例5 问题分析 所需船只分为两部分:(1)各航线航行、装船、卸船所占用的船只

5710915 3211

195915 2222

173713 1234 所需船数 航班数 小计 装卸天数 航行天数 航线 累计共需91条船 例5 问题分析(续1) (2)各港口之间调度所需船只数 -1-122-31

120130 012301 ABCDEF 余缺 开出 到达 港口 A B C D E F

1 2

1 3 调度中心 若无空驶,则91条船刚好够用,但虚线箭头都是空驶 例5 问题分析(续2) 有的可在一个港口卸货后马上装运(如一条船从E到D后再起程赴B).若港口没有空船,则要从其它港口调度而来.将船由多余船只的港口调往需用船只的港口为空船行驶.由上表可知:C、D、F港口有多余船只可供调出,而A、B、E港口则需要调入空船.问题的核心是:如何使空驶船的数量为最少?亦即如何按照最近原则调度船只. 例5 问题分析(续3) 为此建立下表所示的运输问题,其单位运价取为相应一对港口城市间的航行天数.

3 1

1 每天缺少船数

221 5

17 3

3 13

8 2

14 7 C D F 每天多余船数 E B A 至由 例五 解题结果 由初始方案调整后得最优解

3 1

1 每天缺少船只

2 2

1 1

1 1

1 1 C D F 每天多余船只 E B A 目标值为:2+5+13+17+3=40,说明各港口之间调度所需船只至少为40条.该公司至少要配备 91+40=131条船,才能满足4条航线正常运输的需要. ........