运筹学-4.运输问题第四章

第四 问本章主要内容问题的求解—问题应用—1第一 问题的数学模一、数学模销产销产646x6x5x53设xij表示Ai到Bj的运量。3MinZ

5x225x2x11x12x13s.t.x11x21 0;i1,2;j1,2,x13x232MinZcijMinZciji1j xijni产量约jm ijjj1,2,n销量约束ixij有m个地区生产某种物资，有n个地区需要该类物令a1a2am表示各产地产量b1,b2bn表示各销地的销设xij表示产地i运往销地j的物资量，cij表示对应的单位运m一般满足产销平衡m ai bji j3三、变量xij的系数列向量的特在例1中 问题的系数矩阵为

1 010000

000

r(A)231一般情况下 问

1

i决策变量xij的系数列向量

1m 00 问题系数矩阵的秩为m+n-14四、闭回概 例2（P94例销产337④③19284③①7459⑥③3656闭回路：以某空格为起点，用水平或垂直线向前闭回路：以某空格为起点，用水平或垂直线向前划，当碰到恰当的数字格后，转900继续前进，直到回到起始空5闭回路与变量所对应的系数列向量组线性相关性的结论 问题一组变量构成闭回路的充要条件是这变量所对应的系数列向量线性例如，闭回路（x11x21x23,结论 问题的一个可行解是基可行解的充要条件是数字格的个数为m+n-1这m+n-1个数字格不构成闭回作业一、表上作业法的步基可行Nij0?Y二、初始基可行解的确最小元素销产例销产

36563656Z3164124331035伏格尔法例 销产

A A1②A A2①A A

7007000041111912-- ③ ③ 25132-132-122-1-Z231125132-132-122-1-3835在以上两种方法中，有几点需要注意这两种方法得出的解均为初始一般由伏格尔法得出的解比最小元素法得出的更接近在以上方法过程中，不可同时划去行三、求检验数并进行最优解的判闭回路 例销产销产337④③1219284③①1-7459⑥③3656验数均为2)空格检验数ijcijcij 最优性判别准则：当所有ij0时 问题达到最优。显然该问题至此尚未达到最优位势例6由最小元素法得出初始解,如下销产337④③19284③①7459⑥③3656注）行势、列势的定义与计算对数字格而uivj 检验数的计算：空格ijcij(uivj),数字格ij0行势、列势可不唯一，但检验数是一位势法的理论依据（互补松弛定理 MinZcij i1 ( xij xiji

MaxZaiuibjvi juivjs.t.uv无约束xij0,(i1,,m;j 结论x(0)(（0,v(0)

)是(L)D)的可行解,则x(0)(u

(0),

(0) ij 是(L)(D)的最优解的充要条件是

(0

)ij x

ij位势法的计算过令按ui+vj=cij相继确定其他数字格的ui和计算空格的检验④④③③①⑥③392547-1829121033销产因为λ11=-1<0,因而该问题至此尚未达到最优解从最小负检验数所对应的空格进行调例7对由最小元素法得出的初始解进行调销产33销产3312⑤192③71①-8⑥③

011;41

调整方1找出闭再按调整后的解由位势法计算空格的检验五、典 问题解题步骤示由最小元素法求得初始基可销产337④③19284③①7459⑥③3656Z3164124331035由位势法求检验计算空格的检验数。如λ11=3

令④③③①⑥③392547-1④③③①⑥③392547-1829121033销产因为λ24=-1<0,因而该问题至此尚未达到最优解从最小负检验数所对应的空格进行销产33销产331⑤1292③714①-85⑥③

011;41

调整方1找出闭02⑤②③21①9⑥③5478202⑤②③21①9⑥③547829133销产393计算空格的检验数。如λ11=3

令0按ui+vj=cij相0因为所有的λij≥0,至此该问题已经达到最优解最优解Z5321031186435第三节产销不平衡 问一、定理：方程组j

xij

aixijbji1xij0,(i1,,m;j1,,n) 有解的充要条件是：bji1 j1证明：（1）先证必要性x0是方程组的解，且x(0 ij 则j

(0xijx

ai,i

(0xijx

bm m 而ai

x(0x n

x(0xij

bi i j(2)再证充分性

j1i

j 若aibj记aibji j i j若0，由于ai0，bj0，则ij则x(0)0是方程组的解ij

bj又若0，x

(0)ij

aib n(0)

aibj

a a

(0)则xij

b

ai。同理xij

bj j

j i 产销平问题有可行解 问题有最优问题有最优解产销平二、产销不平衡问题的处 若产销aibj),i1 j n虚设一个销Bn1使aibjci,n1i1 j1 若产销aibj),则虚设一个产地Am1i1 jm1 且使aibj，i1 j1且

cm+1,j=例8求下 问题的最优产甲乙丙丁戊产159522866317424863759销44624 假设“己”的虚拟销量为2，各实际产地到其的运费为。如下产甲乙丙丁戊己产1590522860631740248637509446242用表上作业法可以求出例9（P105例需求地I产ABC最低需求（万吨0不在产销平衡表中增加一个假想的化肥厂D，年产量为万吨；将需求分两种情况的地区，实际按两个地区看这样可将该问题化为产销平衡问题需求地IV产ABCMMDM0M0M0根据表上作业法计算，可得该问题的最优方案，如下需求地IV（万吨D0销量（万吨第四节应用例10（P107例某厂按合同规定须于当年每个季度末分别提供，1，，、等费用0.15万元。要求在完成合同的作出使该厂全年总费用最小的季生产能力单位成本/万Ⅳ解：设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同有

还要满足生产能力：x11还要满足生产能力：x11x12x13x14xx x44jiIIji