运筹学-第2章.ppt

运筹学 主讲人：朱建明 2014 年 10 月 应用数学系 第2章 运输问题 运输问题的数学模型和解法 1 不平衡运输模型 2 转运模型 3 分配问题 4 引例：公司物资配送问题 引例： 公司物资配送问题 300 共计 85 4 300 共计 70 3 100 3 65 2 125 2 80 1 75 1 库存量 仓库 产量 罐头加工厂 685 388 682 995 3 791 690 416 352 2 867 654 513 464 1 罐头加工厂 4 3 2 1 单位：美元 仓库 第一节 运输问题的数学模型和解法 一、平衡运输问题的线性规划模型 例1 假设西门子公司在全国不同地方有三家工厂 O1、O2、 O3，四家地区零售中心 D1、D2、D3、D4，未来 3 个月供 需数据如下两表： 13500 2500 O3 3 6000 O2 2 5000 O1 1 生产能力 工厂 起点 13500 1500 D4 4 2000 D3 3 4000 D2 2 6000 D1 1 销售量 零售中心 目的地 第一节 运输问题的数学模型和解法 一、平衡运输问题的线性规划模型 单位运输成本如下表： 5 4 5 2 O3 3 2 5 7 O2 6 7 2 3 O1 D4 D3 D2 D1 起点\目的地 问：如何运输才能使得总运输成本最小？ 第一节 运输问题的数学模型和解法 一、平衡运输问题的线性规划模型 1、网络模型 第一节 运输问题的数学模型和解法 一、平衡运输问题的线性规划模型 2、LP模型 设xij表示从Oi到Dj的运输量，i=1,2,3,j=1,2,3,4. min z=∑∑ c i j x i j x11 + x12 + x13 + x14 = 5000 O1 x21 + x22 + x23 + x24 = 6000 O2 x31 + x32 + x33 + x34 = 2500 O3 x11 + x21 + x31 = 6000 D1 x12 + x22 + x32 = 4000 D2 x13 + x23 + x33 = 2000 D3 x14 + x24 + x34 = 1500 D4 xi j ≥ 0 第一节 运输问题的数学模型和解法 一、平衡运输问题的线性规划模型 2、LP模型 1) 最优解与最优值 x11 = 3500 x12 = 1500 x22 = 2500 x23 = 2000 x24 = 1500 x31 = 2500 其余 xij = 0 z= 39500 注意：最优解值都是整数，此非巧合 2) 定理 若所有起运点的供货量和目的地的需求量都是整数，运输问题的最优解总是整数。 第一节 运输问题的数学模型和解法 一、平衡运输问题的线性规划模型 3、一般平衡运输问题的LP模型 第一节 运输问题的数学模型和解法 二、表格作业法 1、方法比较 1) LP方法—只能使用于小、中型问题（若有100个起运点和 1000个目的地时，变量将有100,000 个） 2) 表格作业法—可以简化计算，对大型问题更有效率 2、表格作业法的思路（本质上单纯形法） 1)表格模型表达运输问题 2)求一个初始可行解 （最小元素法或差额法） 3)计算检验数并判断是否为最优? （踏石法或乘数法） 4)迭代到另外一个可行解以改善解的质量 5)重复上述步骤直到求出最优解 第一节 运输问题的数学模型和解法 二、表格作业法 3、表格作业法求解例1 1）最小元素法 2）踏石法(闭回路法) 第一节 运输问题的数学模型和解法 二、表格作业法 4、表格作业法的基本要求 1）平衡的运输问题(总供给等于总需求） 2）基变量的个数（石头块数）为 m+n-1 5、表格作业法求解例1 1）差额法 2）乘数法 第一节 运输问题的数学模型和解法 二、表格作业法 6、退化的基本可行解（石头个数＜m+n-1) 第一节 运输问题的数学模型和解法 本节