线性规划 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