上海财经大学《运筹学》课件-第三章

1上海财经大学

运筹学第三章特殊线性规划——运输问题2特殊线性规划——运输问题运输问题的一般描述模型的一般形式引例

这里有三家工厂，都将产品运往三个不同的商店（见下图）。每个工厂以产品件数表示出每周生产能力见下表1。每家商店平均需求量见下表2。工厂1工厂3工厂2商店1商店3商店2表1表2

商店123供应量（件/周）507020工厂123需求量（件/周）5060303特殊线性规划——运输问题但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪家商店。能否列出线性最优化模型？决策存在什么样的约束条件？模型评价涉及什么样的准则？有那些决策变量？由工厂每件产品运往各商店的费用（元）123123310125338104上海财经大学运筹学特殊线性规划——运输问题模型建立决策变量——有待确定的是从每家工厂i（i=1，2，3）运输多少件产品到每家商店j（j=1，2，3）去。因此，方便的办法是用双下标来表示决策变量即Xij。目标函数——利用运输费用表中的数据，我们希望其值为最小的是：

MinZ=由工厂1运出产品的总费用----3X11+2X12+3X13+由工厂2运出产品的总费用----10X21+5X22+8X23

+由工厂3运出产品的总费用----X31+3X32+10X33即：MinZ=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的供应约束）5上海财经大学运筹学特殊线性规划——运输问题约束条件——对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。对商店1必须有X11+X21+X31=50

对商店2必须有X12+X22+X32=60

对商店3必须有X13+X23+X33=30于是，用于解此问题的线性最优化模型是：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33

X11+X12+X13=50X21+X22+X23=70X31+X32+X33=20X11+

X21+

X31

=

50Xij≥0且为整数

X12+X22+

X32

=

60i=1，2，3X13+

X23+

X33

=

30j=1，2，3s.t.6上海财经大学运筹学特殊线性规划——运输问题运输问题模型分析一般形式：某种物资有m个产地Ai，产量（供应量）是ai（i=1，2，…，m），有n个销地Bj，销量（需求量）是bj（j=1，2，…，n）。从运到的单位运价为cij（i=1，2，…，m；j=1，2，…，n），如何安排运输可使总运费最小？产大于销——

ai

≥

bjMinZ=

CijXij

xij≤ai

（i=1，2，…，m）

xij

=bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；

j=1，2，…，n）销大于产——

ai

≤

bjMinZ=

CijXij

xij=ai

（i=1，2，…，m）

xij≤bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；

j=1，2，…，n）7上海财经大学运筹学特殊线性规划——运输问题产销平衡——

ai

=bj

注意！这种模型具有特殊的形式：所有决策变量的约束条件，其系数均等于1；而且，每个决策变量仅出现于两个约束条件之中。这些特性表明，解这类线性最优化模型的单纯形法中有一种特殊的方法可用来解这个问题——这是解这类模型的特别有效的一种方法。而且上述特性还表明，可以给这类线性最优化模型以一种象网络模型式的形象化的说明。MinZ=

CijXij

xij

=ai

（i=1，2，…，m）

xij

=bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；j=1，2，…，n）8上海财经大学运筹学特殊线性规划——运输问题模型特点1、运输问题有有限最优解2、运输问题约束条件系数矩阵A=11…1111…1……………………11…111…1111……………………111（m+n）×（mn）9上海财经大学运筹学特殊线性规划——运输问题产销平衡运输问题的对偶问题（P）MinZ=

CijXij

xij

=ai

（i=1，2，…，m）

xij

=bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；j=1，2，…，n）（D）MaxW=∑aiUi

+∑bjVj

Ui+Vj

≥Cij

Ui

，Vj

，自由变量（i=1，2，…，m；j=1，2，…，n）10上海财经大学运筹学特殊线性规划——运输问题运输问题的求解方法求解此问题的一个十分有效的方法是表上作业法：

（1）产销平衡问题——总产量等于总销量的运输问题

a、建立作业表

b、确定初始调运方案（最小元素法）

c、现行方案的最优性检验（位势法）

d、现行方案的调整（闭回路法）11上海财经大学运筹学特殊线性规划——运输问题例1——

甲（B1）、乙（B2）、丙（B3）、丁（B4）三城市所需煤炭由三个煤矿A1、A2、A3供应，有关数据如表，表中数字为单位运费（万元／万吨），请制订使总运费最小的调运计划。销地B1销地B2销地B3销地B4产量产地A137645产地A224322产地A343853销量332212上海财经大学运筹学特殊线性规划——运输问题a、建立平衡调运作业表B1B2B3B4产A137645A224322A343853销33223运价Xij调运量，当其为非基变量时不予填写

ij检验数，当其为基变量的检验数时不予填写13上海财经大学运筹学特殊线性规划——运输问题b、确定初始调运方案（最小元素法）3运价Xij调运量，当其为非基变量时不予填写

ij检验数，当其为基变量的检验数时不予填写376424324385A1A2A3B1B2B3B4

产量销量332252321143022214上海财经大学运筹学b、确定初始调运方案（Vogel——沃格尔法）

销地产地B1B2B3B4产量行罚数1234A137645111A2223220A34385311销量332210列罚数11132214130045203322015上海财经大学运筹学b、确定初始调运方案（Vogel——沃格尔法）

销地产地B1B2B3B4产量A137645302A22232202A3438533销量33221016上海财经大学运筹学特殊线性规划——运输问题c、现行方案的最优性检验（位势法）102223376424324385A1A2A3B1B2B3B4

Ui

Vj由

ij=Cij-（Ui+Vj）计算位势Ui

，Vj

，因对基变量而言有

ij=0，即Cij-（Ui+Vj）=0令U1=003764-1-4再由

ij=Cij-（Ui+Vj）计算非基变量的检验数

ij-2-2-1565当存在非基变量的检验数

kl

<0且

kl

=min{ij}时，令Xkl进基。从表中知可选X23进基。17上海财经大学运筹学特殊线性规划——运输问题d、现行方案的调整（闭回路法）102223376424324385A1A2A3B1B2B3B4

Ui

Vj03764-1-4-2-2-1565调整量

={从进基变量X23出发的闭回路中奇拐点上基变量的最小值}=2。调整步骤为：闭回路上偶拐点处基变量的值+

闭回路上奇拐点处基变量的值-

23018上海财经大学运筹学特殊线性规划——运输问题d、现行方案的调整（闭回路法）1022223376424324385A1A2A3B1B2B3B4

Ui

Vj重复步骤C、检验当前调运方案（基可行解）的最优性如非最优方案，则擦去Ui、Vj和

ij然后重新计算。30037-144-42-2-1585019上海财经大学运筹学特殊线性规划——运输问题d、现行方案的调整（闭回路法）1022023376424324385A1A2A3B1B2B3B4

Ui

Vj重复步骤C、检验当前调运方案（基可行解）的最优性如非最优方案，则擦去Ui、Vj和

ij然后重新计算。30374-3-46021565当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费minZ=9+0+8+0+6+9=3220上海财经大学运筹学特殊线性规划——运输问题表上作业法的几点说明：1、若运输问题的某一基可行解有多个非基变量的检验数为负时，在迭代时可取它们中任一非基变量进基均可使目标函数值得到改善，但通常取最小者对应的非基变量进基。2、当迭代到最优解时，有某非基变量的检验数为0时，则问题有无穷多最优解。3、当在表上作业时，同时划去了一行和一列运输价格时，就出现了退化，此时必须在当前划去的运价中某一空格填入一个0，表示该格中的变量是取值为0的基变量。21上海财经大学运筹学特殊线性规划——运输问题进一步讨论一、产销不平衡的运输问题——总产量小于总销量的运输问题例2——有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。需求地区化肥厂B1B2B3B4产量（万吨）A11613221750A21413191560A3192023---50最低需求（万吨）最高需求（万吨）3050707003010不限运价：万元/万吨22上海财经大学运筹学特殊线性规划——运输问题进一步讨论分析：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，地区B4每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D，其年产量为50万吨。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表——23上海财经大学运筹学特殊线性规划——运输问题进一步讨论例2产销平衡表A1A2A3DB'1B''1B2B3B'4B''4

产量销量171714141319151519192023MMM0M0M050605050302070301050161622132030203050202040301010030202024上海财经大学运筹学特殊线性规划——运输问题进一步讨论产销平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj13501430132019015102330M2002003001301419154-4+M4-M-4+M220-M3221-M18-M19-M119-M3M-192M-182M-17M-232M-19162217171415191920MMM0M1603020203025上海财经大学运筹学特殊线性规划——运输问题进一步讨论产销平衡表

A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M1626上海财经大学运筹学特殊线性规划——运输问题进一步讨论产销平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj16135022171714101420132019151015192019202330MM0M0M0M050160055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+M-23+M-20+2M1020027上海财经大学运筹学特殊线性规划——运输问题进一步讨论产销平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj161350221717141014201320191510150192019202330MMM0M0M050160060141413171515225222-11-21+M-21+M-14+M-14-13+M-17-15+M101030204028上海财经大学运筹学特殊线性规划——运输问题进一步讨论产销平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj1350142013201510151019302320010040008-151114131515155272234-3-1M-23M-23M+41M+2M3003020201622171714191920MMM0MM1629上海财经大学运筹学特殊线性规划——运输问题进一步讨论产销平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj1613502217171414132019151015301930192020230MMM0M030M02016008-1511111315151555722334-1M-23M-23M+44M+2M20303020030上海财经大学运筹学特殊线性规划——运输问题进一步讨论产销平衡表A1A2A3DB'1B''1B2B3B'4B''4

Ui

Vj135013201510153019301920200030020007-15121213151515447222241M-22M-22M+33M+2M1622171714141923MMM0MM1631上海财经大学运筹学特殊线性规划——运输问题进一步讨论产销平衡表A1A2A3D1613502217171414132019151015301930192020023MMM0M030M0205060505030207030105016B'1B''1B2B3B'4B''4

产量

销量32上海财经大学运筹学特殊线性规划——运输问题进一步讨论二、有转运的运输问题在上面所讨论的问题中，我们都假定物品是由产地直接运送到目的地的，没有经过任何中间转运。然而，在实际当中常常会遇到一种情形：需要先将物品由产地运到某个中间转运站（可能是另外的产地、销地或中间转运仓库），然后再转运到目的地。有时，可能经过转运比直接运到目的地更加经济。因此，在决定运输方案时有必要把转运也考虑进去。这样，将使运输问题更加复杂。3.1运输问题的一般数学模型有m个产地生产某种物资，有n个地区需要该类物资令a1,a2,…,am表示各产地产量，b1,b2,…,bn表示各销地的销量，

ai=bj称为产销平衡设xij表示产地i

运往销地j

的物资量，wij表示对应的单位运费，则我们有运输问题的数学模型如下：运输问题有m

n个决策变量，m+n

个约束条件。由于产销平衡条件，只有m+n–1个相互独立，因此，运输问题的基变量只有m+n–1个3.2运输问题的求解方法约束条件非常有规律，技术系数非0即1基变量的个数远小于决策变量的个数采用表上作业法，称为位势法和踏石法运算中涉及两个表：运费表和产销平衡表(分配表)3.2.1寻找初始可行解的方法

1、西北角法从x11开始分配，从西北向东南方向逐个分配xij的分配公式例3.2.1

例3.2.1西北角法2、最低费用法采用最小费用优先分配的原则，看一步f(x)=121，比西北角法低843、运费差额法采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分配的原则，看两步f(x)=98，比最低费用法又低了233.2.2利用位势法检验分配方案是否最优不采用单纯型法，如何获得xij的检验数找到原问题的基础可行解，保持互补松弛条件，求出对应对偶问题的解，若该对偶问题的解非可行，则原问题的解不是最优解；否则，达到最优解

位势法的原理为满足互补松弛条件，原问题中xij被选为基变量，即xij0，则要求对偶问题中ui+vj=wij，即该行的松弛变量为0共有m+n1个基变量xij

，因此可得m+n1个等式ui+vj=wijm+n1个等式只能解出m+n1个ui和vj

，而一共有m+n个ui和vj

，但可令任一个ui或vj=0，从而解出其它m+n1个的值；这就是位势法令zij=ui+vj

，其相当原问题xij的机会费用若对所有非基变量有zij

wij0，即ui+vj

wij，表明当前ui和vj

是对偶问题的可行解，由互补松弛定理可知当前m+n1个基变量xij

是最优解，否则从zij

wij>0中找最大者，对应xij就是入变量