5運輸問題+指派問題判斷題ppt課件

1、1、運輸問題的基可行解中基變量的個數一定是mn1個。 2、運輸問題是一種特殊形式的 LP 問題，因而其求解結果也可能會有唯一的最優(yōu)解或多個最優(yōu)解。 3、應用表上作業(yè)法的最小元素法確定運輸問題的初始調運方案時，遇有退化基本可行解時，一定注意補 0, 否則，初始調運方案的數字格數目不滿足：數字格數目=m+n-1。 4、運輸問題是一種特殊的 LP 問題，總有可行解存在。 5、分支定界法的分支約束為和。 6、整數線性規(guī)劃的目標函數值一定優(yōu)于其松弛問題的目標函數值。 7、運輸問題不是線性規(guī)劃問題。 8、運輸問題通常用表上作業(yè)法求解。 9、運輸問題不可能有無界解。 10、運輸問題的m+n個約束條件都是線性

2、獨立的。,1-5 BAAAA 6-10 BBAAB,1,;,11、運輸問題的基可行解中基變量的個數一定是mn1個。 12、運輸問題有m+n-1個基變量。 13、運輸問題的解中非零變量的個數不能大于m+n-1個。 14、最小元素法的基本思想是優(yōu)先考慮單位運價最小的運輸業(yè)務。 15、沃格爾法的基本思想是，如果罰數的值很大時，不按最小運價組織運輸就會造成很大損失，故優(yōu)先考慮罰數最大的行或列中單位運價最小的元素。 16、運輸問題的解的最優(yōu)性檢驗可用閉回路法。 17、運輸表中，每一個空格總可以和一些填有數字的格用水平線或垂直線連在一閉合回路上。 18、閉回路都是一個簡單的矩形，不可以是由水平和垂直線組成

3、的其它更復雜的封閉多邊形。 19、產量大于銷量時，可虛擬一產地。,11-15 BAAAA 16-19 AABB,2,;,20、當迭代到運輸問題的最優(yōu)解時，如果有某個非基變量的檢驗數等于零，則說明該運輸問題有無窮最優(yōu)解。 21、產銷平衡問題是說產地與銷地的個數相等。 22、求解運輸問題時，表上作業(yè)法一般比單純形法簡單方便。 23、表上作業(yè)法求解運輸問題的基本步驟是確定初始調運方案，最優(yōu)性檢驗，方案調整。 24、指派問題的效率矩陣的每一行（或每一列）的各元素分別減去一個該行（或該列）的最小元素，得到一個新的效率矩陣，則以該新矩陣為效率矩陣的指派問題與原問題有相同的最優(yōu)解。 25、按最小元素法給出的

4、初始基可行解，從每一空格出發(fā)可找到而且僅能找到惟一的閉回路。 26、運輸問題用最小元素法可以直接求得最優(yōu)解。 27、運輸問題模型是一種特殊的線性規(guī)劃模型，所以運輸問題也可以用單純形法求解。,20 A 21-25 BAAAA 26-27 BA,3,;,28、表上作業(yè)法實質上就是求解運輸問題的單純形法。 29、運輸問題一般來講，用沃格爾法求解的初始解優(yōu)于用最小元素法求解的最優(yōu)解。 30、運輸問題一定存在最優(yōu)解。 31、用分支定界法求解整數規(guī)劃問題時，求對應松弛問題極大值的目標值是各分枝的上界。 32、整數規(guī)劃中，割平面的構造應滿足能割掉松弛問題的最優(yōu)解，但不割掉原問題的可行解。 33、割平面方法是

5、通過不斷改進松弛問題，來求得線性規(guī)劃問題的最優(yōu)解。 34、匈牙利算法是求解指派問題的一種常見算法。 35、匈牙利法是對指派問題求最小值的一種求解方法。 36、指派問題矩陣中，覆蓋所有零元素的最小直線數等于獨立零元素的最大個數。,28-30 AAA 31-36 AAAAAA,4,;,37、指派問題的每個元素都加上同一個常數k，并不會影響最優(yōu)分配方案。 38、指派問題是一種特殊的運輸問題。 39、指派問題目標是使得完成n件事情的總費用最小。 40、將指派問題效率表中的每一行元素同時減去一個數后最優(yōu)解不變。 41、用位勢法計算檢驗數時，每一行（或列）的位勢的值是唯一的，所以每一個空格的檢驗數是唯一的。 42、當所有產地的產量和銷地的銷量都是整數時，運輸問題的最優(yōu)解也是整數。