《运筹学——线性规划 Linear Programming（LP）》课程教学资源（PPT课件）第三章 特殊线性规划——运输问题

线性规划 Linear Programming(LP) 第三章 特殊线性规划 运输问题

1 线性规划 Linear Programming（LP） 第三章 特殊线性规划—— 运输问题

线性规划 Linear Programming(LP) 特殊线性规划——运输问题 运输问题的一般描述模型的一般形式 引例这里有三家工厂,都将产品运往三个不同的商店(见下 图)。每个工厂以产品件数表示出每周生产能力见下表1。每家商 店平均需求量见下表2。 表1 商店32[商店123 工厂 供应量(件/周)507020 商店1 表2 工厂123 商店2 需求量(件/周)506030 工厂3 2

2 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 运输问题的一般描述 模型的一般形式 引例 这里有三家工厂，都将产品运往三个不同的商店（见下 图）。每个工厂以产品件数表示出每周生产能力见下表1。每家商 店平均需求量见下表2。 工厂1 工厂3 工厂2 商店1 商店3 商店2 表1 表2 商店 1 2 3 供应量（件/周） 50 70 20 工厂 1 2 3 需求量（件/周） 50 60 30

线性规划 Linear Programming(LP) 特殊线性规划——运输问题 但是,由于运货距离不同,各个工厂运往各商店的货物的运输费用是 不同的。费用如下表,我们的问题是确定由哪家工厂运送多少件产品到哪 家商店。 能否列出线性最优化模型? 决策存在什么样的约束条件? 模型评价涉及什么样的准则?有那些决策变量? 每件产品运往各商店的费用(元) 由工厂 3 2253 338 2 10 3 10 3

3 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是 不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪 家商店。 能否列出线性最优化模型？ 决策存在什么样的约束条件？ 模型评价涉及什么样的准则？ 有那些决策变量？ 由工厂 每件产品运往各商店的费用（元） 1 2 3 1 2 3 3 10 1 2 5 3 3 8 10

线性规划 Linear Programming(LP) 特殊线性规划——运输问题 模型建立 决策变量—有待确定的是从每家工厂i(i=1,2,3)运输多少件产品到 每家商店j(j=1,2,3)去。因此,方便的办法是用双下标来表示决策变 量即Xij。 目标函数—利用运输费用表中的数据,我们希望其值为最小的是: MinZ=由工厂1运出产品的总费用——3x1+12X12+3X13 +由工厂2运出产品的总费用——10x21+5X2+823 +由工厂3运出产品的总费用 X31+3x32+10X3 即:MinZ=3x1+2X12+3x13+10X21+5x2+8X23+X31+3x32+10X3 约束条件—需要把决策变量的约束条件当作方案生成源。 对工厂1必须有X1+x12+X13=50(对工厂1的供应约束) 对工厂2必须有X21+2+X23=70(对工厂2的供应约束) 对工厂3必须有X31+X32+X3=20(对工厂3的供应约束)

4 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 模型建立 决策变量——有待确定的是从每家工厂i（i=1，2，3）运输多少件产品到 每家商店j（j=1，2，3）去。因此，方便的办法是用双下标来表示决策变 量即 Xij。 目标函数——利用运输费用表中的数据，我们希望其值为最小的是： Min Z = 由工厂1运出产品的总费用---- 3X11+ 2X12+ 3X13 +由工厂2运出产品的总费用----10X21+ 5X22+ 8X23 +由工厂3运出产品的总费用---- X31+ 3X32+10X33 即：Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33 约束条件——需要把决策变量的约束条件当作方案生成源。 对工厂1必须有 X11+X12+X13 = 50 （对工厂1的供应约束） 对工厂2必须有 X21+X22+X23 = 70 （对工厂2的供应约束） 对工厂3必须有 X31+X32+X33 = 20 （对工厂3的供应约束）

线性规划 Linear Programming(LP) 特殊线性规划——运输问题 约束条件对每家商店来说,也需要一个逻辑关系式来说明每个星期运 到的产品总数应等于每周的需求量 对商店1必须有X1+X21+X31=50 对商店2必须有x12+X2132=60 对商店3必须有x13+X23+3=30 于是,用于解此问题的线性最优化模型是 MinZ=3x112X12+3X13+10X21+5X2+8X23+x31+3x32+10X3 11TA127A13 50 21TA22+A23 70 s. t X31+x32+X3=20 21 31 50X;≥0且为整数 X1+ 22 32 60i=1,2,3 X12+ X3=30j=1,2,3

5 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 约束条件——对每家商店来说，也需要一个逻辑关系式来说明每个星期运 到的产品总数应等于每周的需求量。 对商店1必须有 X11+X21+X31 = 50 对商店2必须有 X12+X22+X32 = 60 对商店3必须有 X13+X23+X33 = 30 于是，用于解此问题的线性最优化模型是： Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33 X11+X12+X13 = 50 X21+X22+X23 = 70 X31+X32+X33 = 20 X11+ X21+ X31 = 50 Xij≥0 且为整数 X12+ X22+ X32 = 60 i=1，2，3 X13+ X23+ X33 = 30 j=1，2，3 s. t

线性规划 Linear Programming(LP) 特殊线性规划——运输问题 运输问题模型分析 般形式 某种物资有m个产地A1,产量(供应量)是a1(i=1,2,…,m),有n 个销地B;销量(需求量)是b;(j=1,2,…,n)。从运到的单位运价为 c;(i=1,2,…,m;j=1,2,…,n),如何安排运输可使总运费最小? 产大于销 ∑a;≥∑b 销大于产 ∑a;≤∑b MinZ=ΣΣC11 Minz=Σ∑C141 ∑x;≤a;(i=1,2, ∑x;=a;(i=1,2, (j=1,2,…,n) Σx1;≤b;(j=1,2,…,n) x;;≥0(1=1,2,…,m; 1≥0(i=1,2,…,m; J=1 n j=1,2, 6

6 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 运输问题模型分析 一般形式： 某种物资有m个产地Ai，产量（供应量）是ai（i=1，2，…，m），有n 个销地Bj，销量（需求量）是bj（j=1，2，…，n）。从运到的单位运价为 cij（i=1，2，…，m；j=1，2，…，n），如何安排运输可使总运费最小？ 产大于销——  ai ≥  bj Min Z= CijXij  xij≤ai （i=1，2，…，m）  xij =bj （j=1，2，…，n） xij≥0 （i=1，2，…，m； j=1，2，…，n） 销大于产——  ai ≤  bj Min Z= CijXij  xij=ai （i=1，2，…，m）  xij≤bj （j=1，2，…，n） xij≥0 （i=1，2，…，m； j=1，2，…，n）

线性规划 Linear Programming(LP) 特殊线性规划——运输问题 产销平衡 ∑a;=∑b 注意!这种模型具有特殊的形式:所有决策变量的约束条件, 其系数均等于1;而且,每个决策变量仅出现于两个约束条件之中。 这些特性表明,解这类线性最优化模型的单纯形法中有一种特殊的 方法可用来解这个问题—这是解这类模型的特别有效的一种方法。 而且上述特性还表明,可以给这类线性最优化模型以一种象网络模 型式的形象化的说明。 Minz=2ΣC11 2x1=81(i=1,2,…m) ∑x ij=b;(j=1,2,…,n) xi;≥0(i=1,2,…,m;j1,2,…,n)

7 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 产销平衡——  ai =  bj 注意！这种模型具有特殊的形式：所有决策变量的约束条件， 其系数均等于1；而且，每个决策变量仅出现于两个约束条件之中。 这些特性表明，解这类线性最优化模型的单纯形法中有一种特殊的 方法可用来解这个问题——这是解这类模型的特别有效的一种方法。 而且上述特性还表明，可以给这类线性最优化模型以一种象网络模 型式的形象化的说明。 Min Z=   CijXij  xij =ai （i=1，2，…，m）  xij =bj （j=1，2，…，n） xij≥0 （i=1，2，…，m；j=1，2，…，n）

线性规划 Linear Programming(LP) 特殊线性规划——运输问题 模型特点 1、运输问题有有限最优解 2、运输问题约束条件系数矩阵 A (m+n)×(mn) 8

8 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 模型特点 1、运输问题有有限最优解 2、运输问题约束条件系数矩阵 A = 1 1 … 1 1 1 1 … 1 …………………………………………………… 1 1 … 1 1 1 … 1 1 1 1 …………………………………………………… 1 1 1 （m+n）×（mn）

线性规划 Linear Programming(LP) 特殊线性规划——运输问题 产销平衡运输问题的对偶问题 (P)Minz=ΣΣC11; ∑x;;=a;(i=1,2,…,m) Σx1;=b;(j=1,2, x;≥0(i=1,2,…,m;j1,2,…,n) (D) Max w=2a; U;+2b, Vi u1+V≥Cj U,V,自由变量 (i=1,2 =1,2,∴,n) 9

9 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 产销平衡运输问题的对偶问题 （P） Min Z=   CijXij  xij =ai （i=1，2，…，m）  xij =bj （j=1，2，…，n） xij≥0 （i=1，2，…，m；j=1，2，…，n） （D） Max W = ∑ai Ui + ∑bj Vj Ui + Vj ≥ Cij Ui ， Vj ，自由变量 （i = 1，2，… ，m ；j = 1，2，… ，n ）

线性规划 Linear Programming(LP) 特殊线性规划——运输问题 运输问题的求解方法 求解此问题的一个十分有效的方法是表上作业法: (1)产销平衡问题—总产量等于总销量的运输问题 a、建立作业表 b、确定初始调运方案(最小元素法) c、现行方案的最优性检验(位势法) d、现行方案的调整(闭回路法) 10

10 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 运输问题的求解方法 求解此问题的一个十分有效的方法是表上作业法： （1）产销平衡问题——总产量等于总销量的运输问题 a、建立作业表 b、确定初始调运方案（最小元素法） c、现行方案的最优性检验（位势法） d、现行方案的调整（闭回路法）