Chapter 6 Transportation and Assignment Problems 数学模型P195-196 运输问题和指派问题 运输问题是一种线性规划问题 用上面讲的运输问题的数学模型去理解。 决策变量:设x;为从罐头厂i运送到仓库j车数(i=1,2,3;j=1,2,3,4) 目标函数:总成本最小化MinC=S464x1+S513x12+S654x13+S867x14+ S352x2x1+S416x2+s690x23+$791x24+ S995x31+S682x32+S388x33+S685x34 约束条件(由于75+125+100=80+65+70+85,即总供应=总需求,平衡运输问题): 罐头厂1: x11+x12+x13+x14=75 罐头厂2: 1+x2+x23+x24=125 罐头厂3: x31+x32+x33+x34=100 仓库1 x1+x2+x31=80 仓库2: 12+x22+x32=65 仓库3: x13+x23+x3=70 仓库4 x14+x24+x34=85 且非负: 与≥0(=1,2,3;j=1,2,3,4 RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 数学模型P195－196 运输问题是一种线性规划问题 用上面讲的运输问题的数学模型去理解。 决策变量：设 xij 为从罐头厂i 运送到仓库j的车数(i = 1, 2, 3; j = 1, 2, 3, 4) 目标函数：总成本最小化 Min C = $464x11 + $513x12 + $654x13 + $867x14 + $352x21 + $416x22 + $690x23 + $791x24 + $995x31 + $682x32 + $388x33 + $685x34 约束条件（由于75＋125＋100＝80＋65＋70＋85，即总供应＝总需求，平衡运输问题）： 罐头厂 1: x11 + x12 + x13 + x14 = 75 罐头厂 2: x21 + x22 + x23 + x24 = 125 罐头厂 3: x31 + x32 + x33 + x34 = 100 仓库 1: x11 + x21 + x31 = 80 仓库 2: x12 + x22 + x32 = 65 仓库 3: x13 + x23 + x33 = 70 仓库 4: x14 + x24 + x34 = 85 且 非负： xij ≥ 0 (i = 1, 2, 3; j = 1, 2, 3, 4)
Chapter 6 Transportation and Assignment Problems 6.1TP& r company Distribution Probl输间题和指派间题 案例研究:P&T公司的配送问题(续) 作为一个运输问题的P&T公司电子表格描述 P194P&T公司的配送问题P&Tco. Distribution prob|em 单位成本c 目的地(仓库) 萨克拉门托「盐湖城赖皮特城_澳尔巴古 出发地(源)贝林翰 s464 513 654 867 (罐头厂) 尤基尼 $352 s416 $690 $791 艾尔贝.李 995 682 388 685 运输量x 目的地(仓库) 萨克拉门托盐湖城赖皮特城「澳尔巴古「总运出量 供应量 出发地(源)贝林翰 20 55 75 75 (罐头厂)尤基尼 80 45 0 125 125 艾尔贝李 0 70 100 100 总运入量 80 70 总成本 需求量 80 65 衡运输条件: 总供应总需求 300 300 RUC Information School, Ye Xiang, 2 为平衡运输问题
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 6.1 P&T Company Distribution Problem 案例研究： P&T公司的配送问题（续） 作为一个运输问题的P&T公司电子表格描述 P194 P&T公司的配送问题 P&T Co. Distribution Problem 单位成本ci j 目的地(仓库) 萨克拉门托 盐湖城 赖皮特城 澳尔巴古 出发地(源) 贝林翰 $464 $513 $654 $867 (罐头厂) 尤基尼 $352 $416 $690 $791 艾尔贝.李 $995 $682 $388 $685 运输量xi j 目的地(仓库) 萨克拉门托 盐湖城 赖皮特城 澳尔巴古 总运出量 供应量 出发地(源) 贝林翰 0 20 0 55 75 = 75 (罐头厂) 尤基尼 80 45 0 0 125 = 125 艾尔贝.李 0 0 70 30 100 = 100 总运入量 80 65 70 85 = = = = 总成本 需求量 80 65 70 85 $152,535 平衡运输条件： 总供应 总需求 300 = 300 为平衡运输问题
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 Characteristics of Transportation Problems 6,2运输问题的特征P192 每一个出发地都有一定的供应量( supply)要配送到目 的地,每一个目的地都有一定的需求量( demand), 需要接收从出发地发出的产品 需求假设( The requirements Assumption) 可行解特性( The Feasible Solutions Property) 成本假设( The Cost Assumption) 整数解性质( Integer Solutions Property) 求解运输问题( Solving transportation Problems) RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 Characteristics of Transportation Problems 6.2 运输问题的特征P192 每一个出发地都有一定的供应量（supply）要配送到目 的地，每一个目的地都有一定的需求量（demand）， 需要接收从出发地发出的产品 需求假设（The Requirements Assumption） 可行解特性（The Feasible Solutions Property） 成本假设（The Cost Assumption） 整数解性质（Integer Solutions Property） 求解运输问题（Solving Transportation Problems）
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 The requirements Assumption 需求假设P192 需求假设( The requirements Assumption): 每一个出发地都有一个固定的供应量,所有的 供应量都必须配送到目的地。与之相类似,每 个目的地都有一个固定的需求量,整个需求 量都必须由出发地满足(平衡运输问题) RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 The Requirements Assumption 需求假设 P192 需求假设（The Requirements Assumption）： 每一个出发地都有一个固定的供应量，所有的 供应量都必须配送到目的地。与之相类似，每 一个目的地都有一个固定的需求量，整个需求 量都必须由出发地满足 （平衡运输问题）
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 The Feasible solutions Property 可行解特性P192 可行解特性( The Feasible Solutions Property): 当且仅当供应量的总和等于需求量的总和时, 平衡运输问题才有可行解 RuC Information School, Ye Xiang 2007
Chapter 6 Transportation and Assignment Problems 运输问题和指派问题 RUC Information School ,Ye Xiang ,2007 The Feasible Solutions Property 可行解特性 P192 可行解特性（The Feasible Solutions Property）： 当且仅当供应量的总和等于需求量的总和时， 平衡运输问题才有可行解