4运筹学第三章2007.ppt

运筹学基础 例二 例二 例三 例四 例四 例四 例五 例三 对运输问题的数学模型（假定产销平衡） 例三 例三 例三 例三 例三 例三 例三 四、几点说明 　　由于总产量大于总销量，所以多余物资应储存在产地。设某产地Ai的多余存储量为xi,n+1，于是运输问题的约束条件方程组为： 则 可将不平衡的运输问题（3.3）化为如下的平衡运输问题 令 二、产量小于销量的运输问题 这时可增加一个设想的产地Am+1，其产量为 并令该产地到销地Bｊ的运价Cｍ＋１.ｊ＝０（ｊ＝１，２，…，ｎ），同样可将不平衡的运输问题转化为平衡的运输问题。 　　如无特别说明，本章仅限于对平衡问题的运输问题求解的讨论。 　　同一般的线性规划问题一样，运输问题的最优解也一定能在它的基本可行解中找到。由于运输问题的约束系数矩阵Ａ的前ｍ行之和恰好等于后ｎ行之和，即矩阵Ａ的行向量组线性相关，因此Ａ的秩必小于ｍ+ｎ． 例 某石油公司设有四个炼油厂，它们生产普通汽油，并为七个销售区服务，生产和需求情况如下： 第四节 应用问题举例 从炼油厂运往第j个销售区每公升汽油平均运费（单位：角/公升），应如何调运，使运费最省。 如下表： 48 14 12 14 8 销量 22 A3 10 A2 16 A1 产量 B4 B3 B2 B1 4 12 4 11 2 10 3 9 8 5 11 6 最小元素法 8 2 10 14 8 6 运价：246 b 求检验数 要判断一个调运方案是否已是最优，就要判断方案所对应的基础可行解是否最优。在单纯形法中（目标函数为极小化），根据非基变量（空格）的检验数来判别的。若检验数中都是正值，则已求得最优。 如何根据初始调运表求得检验数？ 空格Xij的检验数= （第奇数次拐角点运价之和-第偶数次拐角点运价之和） 空格X21的检验数= 4-6+5-4 = -1 空格X14的检验数=4-5+4-5=- 2 空格X31的检验数 = -1 检验数不都为正值，原方案不是最优解 目标函数： n m j=1 i=1 min Z = ∑ ∑ Cij xij n j=1 ∑ xij = ai i=1,2,…m 产量约束： 销量约束： m i=1 ∑ xij = bj j=1,2,…n xij ≥0 n m j=1 i=1 max w = ∑ aiui ＋ ∑ bj vj ui+vj ≤cij ui、vj无约束 σ = C-CBB-1A= C-YA σj = cij-(u1,u2…… um ,v1,v2……vn)pj = cij-ui-vj 基变量对应的 σ应该等于零 n+m-1个等式,但有n+m个变量 无穷多解 解称为位势 （2） 对偶变量法（位势法） u1+v1=6 u1+v2=5 u2+v2=4 u2+v3=7 u2+v4=5 u3+v4=8 有七个变量，但只有六个方程，有一个自由变量，一般令u1=0 空格（非基变量）的检验数 =Cij- （ ui+vj) （3）解的改进 从一个方案调整到最优方案的过程，就是单纯形法的过程。 选择检验数（一般取最小）为负值的空格所对应的变量为进基变量，在进基变量的回路中，比较偶数拐角点的运量，选择一个具有最小运量的基变量作为出基变量， 并调整运量=min(偶数拐角点的运量) 48 14 12 14 8 销量 22 A3 10 A2 16 A1 产量 B4 B3 B2 B1 4 12 4 11 2 10 3 9 8 5 11 6 最小元素法 8 2 10 14 8 6 运价：246 b 0 48 14 12 14 8 销量 22 A3 10 A2 16 A1 产量 B4 B3 B2 B1 4 12 4 11 2 10 3 9 8 5 11 6 最小元素法 8 2 10 14 8 6 运价：246 b 2 48 14 12 14 8 销量 22 A3 10 A2 16 A1 产量 B4 B3 B2 B1 4 12 4 11 2 10 3 9 8 5 11 6 最小元素法 8 2 10 14 8 4 运价：246 b 2 48 14 12 14 8 销量 22 A3 10 A2 16 A1 产量 B4 B3 B2 B1 4 12 4 11 2 10 3 9 8 5 11 6 最小元素法 8 2 12 14 8 4 运价：246 b 2 48 14 12 14 8 销量 22 A3 10 A2 16 A1 产