文档介绍：线性规划 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
但是,由于运货距离不同,各个工厂运往各商店的货物的运输费用是不同的。费用如下表,我们的问题是确定由哪家工厂运送多少件产品到哪家商店。
能否列出线性最优化模型? 有那些决策变量?
模型评价涉及什么样的准则? 决策存在什么样的约束条件?
由工厂
每件产品运往各商店的费用(元)
1
2
3
1
2
3
3
10
1
2
5
3
3
8
10
运输问题的建模
模型建立
决策变量——有待确定的是从每家工厂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的供应约束)
运输问题的建模
约束条件——对每家商店来说,也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。
对商店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.
运输问题的建模