运筹学 运输问题1008版

运筹学基础毕德春辽东学院信息技术学院运筹学运输问题1008版第1页第4章

运输问题运输问题数学模型线性规划对偶单纯形法运筹学运输问题1008版第2页第1节运输问题数学模型运筹学运输问题1008版第3页1运输问题提出运筹学运输问题1008版第4页1.1.1引例第1节运输问题数学模型│运输问题提出例：某食品企业经销主要产品之一是糖果，它下面设有三个加工厂，天天糖果生产量分别为：A1-7t，A2-4t，A3-9t。该企业把这些糖果分别运往四个地域门市销售，各销售点每日销量为：B1-3t，B2-6t，B3-5t，B4-6t.已知从各工厂到各销售门市部每吨糖果运价为下表所表示。问该食品企业应怎样调运，在满足各门市部销售需求量情况下，使总运费支出为最少?

门市部加工厂B1B2B3B4产量（万吨）A1710867A2597124A336589销量（万吨）3656运筹学运输问题1008版第5页解：这是一个产销平衡运输问题，设Xij表示从Ai调运产品到Bj数量（吨），其数学模型是：1.1.1引例第1节运输问题数学模型│运输问题提出运筹学运输问题1008版第6页2运输问题数学模型特征运筹学运输问题1008版第7页1.2.1运输问题数学模型特征第1节运输问题数学模型│运输问题数学模型特征

运筹学运输问题1008版第8页1.2.1运输问题数学模型特征第1节运输问题数学模型│运输问题数学模型特征

运筹学运输问题1008版第9页1.2.1运输问题数学模型特征第1节运输问题数学模型│运输问题数学模型特征

运筹学运输问题1008版第10页第2节表上作业法运筹学运输问题1008版第11页1初始可行方案（即初始基可行解）确定运筹学运输问题1008版第12页例：运输问题以下表2.1.1案例第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第13页该运输问题数学模型为：2.1.1案例第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第14页最小元素法：优先满足运价（或运距）最小供销业务。例：运输问题以下表，请用最小元素法求解最初方案2.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第15页最小元素0.1产量400和销量300最小者2.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第16页最小元素0.22.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第17页最小元素0.32.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第18页最小元素0.42.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第19页最小元素0.52.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第20页0.30.10.20.42.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第21页

销地产地产量

4124111610398511622销量14121448①例：用最小元素法给出下面运输问题初始方案2.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第22页

销地产地产量

412411162109108511622销量8141448①②2.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第23页

销地产地产量

412112109108511622销量814121448①②③2.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第24页

销地产地产量

4121182109108116销量8121448①②③④2.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第25页

销地产地产量

412118210910811销量81248①③④⑤②2.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第26页

销地产地产量

4128210910811销量81248①③④⑤⑥⑥②2.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第27页此时得到一个初始调运方案（初始可行解）：总运费为（目标函数值）其余变量全等于零。2.1.2最小元素法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第28页西北角例：用西北角法给出下面运输问题一个初始方案。2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第29页例：用西北角法给出下面运输问题一个初始方案。

销地产地产量41241121039108511622销量141214482.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第30页

销地产地产量

41241121039108511622销量14121448①2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第31页

销地产地产量

41241121039108511622销量121448①2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第32页

销地产地产量

41241121039108511622销量14121448①②2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第33页

销地产地产量

412411210398511622销量14121448①②2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第34页

销地产地产量

412411210398511622销量14121448①②③2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第35页

销地产地产量

412411210398511622销量141448①②③2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第36页

销地产地产量

412411210398511622销量14121448①②③④2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第37页

销地产地产量

4124112103985116销量14121448①③②④2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第38页

销地产地产量

4124112103985116销量14121448①③②④⑤2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第39页

销地产地产量

4124112103985116销量141248①③②④⑤2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第40页

销地产地产量

4124112103985116销量14121448①③②④⑤⑥⑥2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第41页此时得到一个初始调运方案（初始可行解）：其余变量全等于零。总运费为（目标函数值）2.1.3西北角法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第42页沃格尔（Vogel）法：运输表中各行各列最小运价与次小运价之差值（罚数）应尽可能地小。或者说：优先供给罚数最大行（或列）中最小运费方格，以防止将运量分配到该行（或该列）次小方格中。2.1.4沃格尔（Vogel）法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第43页例：用沃格尔法给出下面运输问题一个初始方案。销地产地产量行罚数1234124111602103910181161销量8121448列罚数12513232.1.4沃格尔（Vogel）法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第44页销地产地产量行罚数123

412411160021039101185112212销量8141248列罚数12513221332.1.4沃格尔（Vogel）法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第45页销地产地产量行罚数123

41241116000103911185112212销量141248列罚数12513221332122.1.4沃格尔（Vogel）法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第46页销地产地产量行罚数456

41211710396851122销量1448列罚数412562.1.4沃格尔（Vogel）法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第47页销地产地产量行罚数456

412117010360851122销量1448列罚数4125262.1.4沃格尔（Vogel）法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第48页此时得到一个初始调运方案（初始可行解）：其余变量全等于零。总运费为（目标函数值）2.1.4沃格尔（Vogel）法第2节表上作业法│初始可行方案（即初始基可行解）确实定

运筹学运输问题1008版第49页2解最优性检验运筹学运输问题1008版第50页下面用最小元素法所确定初始基本可行解来说明。与单纯性原理相同，现目标是运费最少，故检验每一个非基变量检验数是否2.2.1回路法（cyclemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第51页

销地产地产量412104611168210239108145118622销量8141214482.2.1回路法（cyclemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第52页

销地产地产量

412104611168210239108145118622销量8141214482.2.1回路法（cyclemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第53页

销地产地产量

412104611168210239108145118622销量8141214482.2.1回路法（cyclemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第54页

销地产地产量

412104611168210239108145118622销量8141214482.2.1回路法（cyclemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第55页

销地产地产量

412104611168210239108145118622销量8141214482.2.1回路法（cyclemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第56页

销地产地产量

412104611168210239108145118622销量8141214482.2.1回路法（cyclemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第57页

销地产地产量

412104611168210239108145118622销量8141214482.2.1回路法（cyclemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第58页用LP对偶理论能够证实，检验数公式为：其中分别称为行位势、列位势。有基变量所对应检验数为零，可从m+n-1个等式解出全部行位势、列位势。能够证实，不论令为何值，一直不变。即将不会随取值而改变。为此，在求解方程组时，为计算简便，可指定一个位势等于一个较小整数或零。2.2.2位势法（dualvariablemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第59页

销地产地产量412104611168210239108145118622销量814121448行位势列位势2.2.2位势法（dualvariablemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第60页

销地产地产量

412104611168210239108145118622销量8141214482.2.2位势法（dualvariablemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第61页

销地产地产量412104611168210239108145118622销量814121448行位势列位势2.2.2位势法（dualvariablemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第62页

销地产地产量

412104611168210239108145118622销量8141214482.2.2位势法（dualvariablemethod）第2节表上作业法│解最优性检验

运筹学运输问题1008版第63页3解改进运筹学运输问题1008版第64页选择进基变量标准：即选择非基变量中检验数最小一个进基。在进基格点所对应闭回路上，定义顶点序号：自进基格点起选定一个方向（比如顺时针方向），依次为第一格、第二格、…在奇数格点上降低调整量，在偶数格点上增加调整量。其中调整量为为闭回路中偶数格点}2.3.1解改进原理第2节表上作业法│解改进运筹学运输问题1008版第65页

销地产地产量

41241116821039108145118622销量8141214482.3.2解改进方法第2节表上作业法│解改进运筹学运输问题1008版第66页

销地产地产量

412124411168210329108145118622销量8141214482.3.2解改进方法第2节表上作业法│解改进运筹学运输问题1008版第67页若在最优解中，某个非基变量检验数为零，则该问题有没有穷多个最优解（相当于当无整数要求而言）此时得到一个最优解：其余变量全等于零。总运费为（目标函数值）2.3.2解改进方法第2节表上作业法│解改进运筹学运输问题1008版第68页

销地产地产量

412124411168210329108145118622销量8141214482.3.2解改进方法第2节表上作业法│解改进运筹学运输问题1008版第69页

销地产地产量

412124111621039108145118622销量8141214482.3.2解改进方法第2节表上作业法│解改进运筹学运输问题1008版第70页

销地产地产量

441212411164210369108145118622销量8141214482.3.2解改进方法第2节表上作业法│解改进运筹学运输问题1008版第71页此时得另一个最优解：其余变量全等于零。总运费为（目标函数值）2.3.2解改进方法第2节表上