用Excel求解運(yùn)籌學(xué)中最大流問題詳細(xì)操作示例ppt課件

1、用用Excel解最大流問題解最大流問題Author：GS.Wang 最大流問題最大流問題在一個(gè)流通網(wǎng)絡(luò)中每條道路弧有一定在一個(gè)流通網(wǎng)絡(luò)中每條道路弧有一定的流通才干容量從圖中一個(gè)地方結(jié)的流通才干容量從圖中一個(gè)地方結(jié)點(diǎn)到另一個(gè)地方走什么路才干使經(jīng)過(guò)的點(diǎn)到另一個(gè)地方走什么路才干使經(jīng)過(guò)的流量最大？這就是一個(gè)典型的最大流問題。流量最大？這就是一個(gè)典型的最大流問題。 最大流問題具有的特征最大流問題具有的特征1.網(wǎng)絡(luò)中一切的流通來(lái)源網(wǎng)絡(luò)中一切的流通來(lái)源于一個(gè)叫源點(diǎn)的結(jié)點(diǎn)于一個(gè)叫源點(diǎn)的結(jié)點(diǎn)2.全部流終止于一個(gè)叫收點(diǎn)的全部流終止于一個(gè)叫收點(diǎn)的結(jié)點(diǎn)結(jié)點(diǎn)3.經(jīng)過(guò)每條道路的流只允許沿經(jīng)過(guò)每條道路的流只允許沿著箭頭方向

2、流動(dòng)著箭頭方向流動(dòng)4.目的是使從源點(diǎn)到收點(diǎn)的總目的是使從源點(diǎn)到收點(diǎn)的總流量最大流量最大 最大流問題可以歸結(jié)為線性最大流問題可以歸結(jié)為線性規(guī)劃問題用規(guī)劃問題用Excel求解求解？ 求解圖示流通網(wǎng)絡(luò)圖的最大流1.形狀變量xij： 每條道路的流量xij是從結(jié)點(diǎn)i流到結(jié)點(diǎn)j的流量2.目的函數(shù)： maxfx使從源節(jié)點(diǎn)出發(fā)的流量到達(dá)最大3.約束條件：a.中間結(jié)點(diǎn)的流入量等于它的流出量 b.每條道路的流量不能夠大于它的容量 c.每條道路的流量不能夠是負(fù)值首先利用知條件和數(shù)據(jù)建立兩個(gè)表格。上表是知表，下表是未知表。Yi是源結(jié)點(diǎn)，Sj是收結(jié)點(diǎn)。上表的數(shù)據(jù)是有向道路i j的容量。1. 形狀變量形狀變量xij是道路

3、是道路i j的流量。的流量。2.目的函數(shù)目的函數(shù)fx是源點(diǎn)是源點(diǎn)Y1的總的總流出量。流出量。3.求出各個(gè)流出結(jié)點(diǎn)流出量和各個(gè)流入結(jié)點(diǎn)的流入量。求出各個(gè)流出結(jié)點(diǎn)流出量和各個(gè)流入結(jié)點(diǎn)的流入量。 H10單元格中輸入單元格中輸入目的函數(shù)計(jì)算公式目的函數(shù)計(jì)算公式 用拖曳方法填入其用拖曳方法填入其它流出結(jié)點(diǎn)的流出它流出結(jié)點(diǎn)的流出量計(jì)算公式量計(jì)算公式 C15單元格中輸入單元格中輸入S2的的流入量的計(jì)算公式流入量的計(jì)算公式用拖曳方法填入其它流入用拖曳方法填入其它流入結(jié)點(diǎn)的流入量計(jì)算公式結(jié)點(diǎn)的流入量計(jì)算公式 添加約束條件添加約束條件約束條件約束條件1：各道路：各道路的流量小于等于容量的流量小于等于容量約束條件約束條件2：各道路：各道路的流量不允許出現(xiàn)的流量不允許出現(xiàn)負(fù)值。負(fù)值。約束條件約束條件3：各中間：各中間結(jié)點(diǎn)的流出量等于結(jié)點(diǎn)的流出量等于流入量。流入量。 最后結(jié)果