[管理學]表上作業(yè)法-文庫吧
2025-09-20 02:10 本頁面
【正文】 得的最大數。然后按運價從小到大順序填數。若某行（列）的產量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。 注 :應用西北角法和最小元素法，每次填完數，都只劃去一行或一列，只有最后一個元例外（同時劃去一行和一列）。當填上一個數后行、列同時飽和時，也應任意劃去一行（列），在保留的列（行）中沒被劃去的格內標一個 0。 最優(yōu)性檢驗就是檢查所得到的方案是不是最優(yōu)方案 。 檢查的方法與單純形方法中的原理相同 ， 即計算檢驗數 。 由于目標要求極小 ， 因此 ， 當所有的檢驗數都大于或等于零時該調運方案就是最優(yōu)方案；否則就不是最優(yōu) ，需要進行調整 。 下面介紹兩種求檢驗數的方法 。 二、基本可行解的最優(yōu)性檢驗 閉回路法 為了方便 ， 我們以上表給出的初始基本可行解方案為例 ， 考察初始方案的任意一個非基變量 ， 比如 x24。 根據初始方案 ，產地 A2 的產品是不運往銷地 B4 的 。 如果現在改變初始方案 ， 把 A2 的產品運送 1 個單位給 B4 ， 那么為了保持產銷平衡 ， 就必須使 x14 或 x34 減少 1 個單位；而如果 x14 減少 1 個單位 ， 第 1 行的運輸量就必須增加 1 個單位 ， 例如 x13 增加 1 個單位 ，那么為了保持產銷平衡 ， 就必須使 x23 減少 1 個單位 。 這個過程就是尋找一個以非基變量 x24 為起始頂點的閉回路 —— {x24 ， x14 ，x13 ， x23 }， 這個閉回路的其他頂點均為基變量 (對應著填上數字的格 )。 容易計算出上述調整使總的運輸費用發(fā)生的變化為 8 – 10 + 3 – 2 ＝ 1 ， 即總的運費減少 1 個單位 ， 這就說明原始方案不是最優(yōu)方案 ， 可以進行調整以得到更好的方案 。 可以證明，如果對閉回路的方向不加區(qū)別（即只要起點及其他所有頂點完全相同，而不區(qū)別行進方向），那么以每一個非基量為起始頂點的閉回路就存在而且唯一。因此，對每一個非基變量可以找到而且只能找到唯一的一個閉回路。 下表中用虛線畫出以非基變量 x22 為起始頂點的閉回路 。 銷地 產地 B1 B2 B3 B4 產量 3 [ ] 11 [ ] 3 4 10 3 7 1 3 9 [ ] 2 1 8 [ ] 4 7 [ ] 4 6 10 [ ] 5 3 9 銷量 3 6 5 6 20(產銷平衡 ) A1 A2 A3 可以計算出以非基變量 x22 為起始頂點的閉回路調整使總的運輸費用發(fā)生的變化為 9 – 2 + 3 – 10 + 5 – 4 ＝ 1 即總的運費增加 1 個單位 ， 這就說明這個調整不能改善目標值 。 從上面的討論可以看出 ， 當某個非基變量增加一個單位時 ， 有若
教學課件相關推薦
鄂ICP備17016276號-1