【文章內(nèi)容簡介】 x5 0 x4 3 1 1 1 1 0 0 x5 9 1 4 7 0 1 2 x1 1 1 0 1 4/3 1/3 3 x2 2 0 1 2 1/3 1/3 －Ｚ 8 0 0 1 5/3 1/3 b1 4b1/33 ?????????????????????????????????????????????3/3334931313134911111bbbbB3b1/3 9/4≤b1 ≤9 35b1/3 39 CB XB cj 2 3 3 0 0 xj b x1 x2 x3 x4 x5 0 x4 2 1 1 1 1 0 0 x5 9 1 4 7 0 1 2 x1 1/3 1 0 1 4/3 1/3 3 x2 7/3 0 1 2 1/3 1/3 －Ｚ 19/3 0 0 1 5/3 1/3 右端常數(shù) b發(fā)生改變 0 X5 1 3 0 3 4 1 3 X2 2 1 1 1 1 0 －Ｚ 6 1 0 0 3 0 最小比值 1 1 40 右端常數(shù) b發(fā)生改變 CB XB cj 2 3 3 0 0 ? xj b x1 x2 x3 x4 x5 0 x4 3 1 1 1 1 0 0 x5 9 1 4 7 0 1 2 x1 1 1 0 1 4/3 1/3 3 x2 2 0 1 2 1/3 1/3 －Ｚ 8 0 0 1 5/3 1/3 b2 4b2/3 ???????????????????????????????????????????13/3/4331313134322221bbbbBb2/31 3≤b2 ≤12 b2/35 41 增加一個變量 若企業(yè)在計劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn)，則在知道新產(chǎn)品的單位利潤，單件資源消耗量時，可以在最優(yōu)表中補充一列，其中的前 m行可以由基矩陣的逆矩陣得到，而檢驗數(shù)行也可以由與其它列相同的方法計算得到。若檢驗數(shù)非正，則原最優(yōu)解仍為最優(yōu)，原生產(chǎn)計劃不變，不生產(chǎn)這種新產(chǎn)品；否則，當檢驗數(shù)為正時，則應以該變量進基，作單純形迭代，從而找出新的最優(yōu)解。 42 靈敏度分析 例 2 CB XB cj 2 3 3 0 0 ? xj b x1 x2 x3 x4 x5 0 x4 3 1 1 1 1 0 0 x5 9 1 4 7 0 1 2 x1 1 1 0 1 4/3 1/3 3/5 3 x2 2 0 1 2 1/3 1/3 6 －Ｚ 8 0 0 1 5/3 1/3 5 x6 2 3 5/3 1/3 2/3 5 x6 3/5 3/5 0 3/5 4/5 1/5 1 3 x2 9/5 1/5 1 11/5 3/5 2/5 0 －Ｚ 42/5 2/5 0 3/5 11/5 1/5 0 －Ｚ43 增加一個約束 在企業(yè)的生產(chǎn)過程中 ， 經(jīng)常有一些突發(fā)事件產(chǎn)生 ， 造成原本不緊缺的某種資源變成為緊缺資源 ， 對生產(chǎn)計劃造成影響 ， 所以需要增加約束條件 。 1） 若把目前的最優(yōu)解代入新增加的約束 ， 能滿足約束條件 ， 則說明該增加的約束對最優(yōu)解不構成影響 ， 即不影響最優(yōu)生產(chǎn)計劃的實施 。 2)若當前最優(yōu)解不滿足新增加的約束 ， 則應把新的約束添到原問題的最優(yōu)表內(nèi)新的一行中去 ， 用對偶單純形方法來進行迭代 ， 求出新的最優(yōu)解 。 44 靈敏度分析 例 增加約束 CB XB cj 2 3 3 0 0 xj b x1 x2 x3 x4 x5 0 x4 3 1 1 1 1 0 0 x5 9 1 4 7 0 1 0 x6 5 2 2 1 0 0 2 x1 1 1 0 1 4/3 1/3 3 x2 2 0 1 2 1/3 1/3 0 x6 5 2 2 1 0 0 －Ｚ 8 0 0 1 5/3 1/3 0 x6 0 0 1 0 0 1 0 522 321 ??? xxx45 靈敏度分析 增加約束 522 321 ??? xxx CB XB cj 2 3 3 0 0 0 xj b x1 x2 x3 x4 x5 x6 2 x1 1 1 0 1 4/3 1/3 0 3 x2 2 0 1 2 1/3 1/3 0 0 x6 5 2 2 1 0 0 1 2 x1 1 1 0 1 4/3 1/3 0 3 x2 2 0 1 2 1/3 1/3 0 0 x6 1 0 0 1 2 0 1 －Ｚ 8 0 0 1 5/3 1/3 0 最小比值 1 5/6 46 靈敏度分析 A中元素改變 如果 N中數(shù)據(jù)改變 ， 可以用增加一個變量來處理 如果 B中元素改變 ， 則情況較復雜 ， 一般需要修改問題后重新求解 47 運輸問題 問題的提出 一般的運輸問題就是要解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運到若干個銷地 ， 在每個產(chǎn)地的供應量與每個銷地的需求量已知 ， 并知道各地之間的運輸單價的前提下 ， 如何確定一個使得總的運輸費用最小的方案 。 48 ? 例 某公司從兩個產(chǎn)地 A A2將物品運往三個銷地 B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應如何調(diào)運可使總運輸費用最小？ 單位運費 B1 B2 B3 產(chǎn)量 A1 6 4 6 200 A2 6 5 5 300 銷量 150 150 200 49 ? 解：產(chǎn)銷平衡問題：總產(chǎn)量 = 總銷量＝ 500 ? 設 xij 為從產(chǎn)地 Ai運往銷地 Bj的運輸量，得到下列運輸量表： B1 B2 B3 產(chǎn)量 A1 x11 x12 x13 200 A2 x21 x22 x23 300 銷量 150 150 200 Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 . x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij ≥ 0 ( i = 2； j = 3） 50 運輸規(guī)劃問題的數(shù)學模型 ? 運輸問題的一般形式：產(chǎn)銷平衡 A A … 、 Am 表示某物資的 m個產(chǎn)地； B B … 、 Bn 表示某物質(zhì)的 n個銷地； ai 表示產(chǎn)地 Ai的產(chǎn)量； bj 表示銷地 Bj 的銷量； cij 表示把物資從產(chǎn)地 Ai運往銷地 Bj的單位運價。設 xij 為從產(chǎn)地 Ai運往銷地 Bj的運輸量，得到下列一般運輸量問題的模型： ? ?? ??minjijij xcz1 1m i n????????????????????njmixnjbxmiaxtsijjmiijnjiij,1。,1,0,1,1.11????51 變化： 1）有時目標函數(shù)求最大。如求利潤最大或營業(yè)額最大等； 2）當某些運輸線路上的能力有限制時，在模型中直接加入約束條件（等式或不等式約束 )； 3）產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。 ? 定理 : 設有 m個產(chǎn)地 n個銷地且產(chǎn)銷平衡的運輸問題，則 基變量數(shù)為 m+n1。 52 表上作業(yè)法 ? 表上作業(yè)法是一種求解運輸問題的特殊方法，其 實質(zhì)是單純形法。 步驟 描述 方法 第一步 求初始基行可行解（初始調(diào)運方案） 最小元素法、元素差額法、 第二步 求檢驗數(shù)并判斷是否得到最優(yōu)解當非基變量的檢驗數(shù) σij全都非負時得到最優(yōu)解，若存在檢驗數(shù) σij 0，說明還沒有達到最優(yōu)，轉第三步。 閉回路法和位勢法 第三步 調(diào)整運量，即換基，選一個變量出基，對原運量進行調(diào)整得到新的基可行解，轉入第二步 53 表上作業(yè)法 例 2 某運輸資料如下表所示： 單位 銷地 運價 產(chǎn)地 產(chǎn)量 3 11 3 10 7 1 9 2 8 4 7 4 10 5 9 銷量 3 6 5 6 4321 BBBB321AAA問：應如何調(diào)運可使總運輸費用最??？ 54 ?解：第 1步 求初始方案 方法 1：最小元素法 基本思想是就近供應，即從運價最小的地方開始供應（調(diào)運），然后次小，直到最后供完為止。 B1 B2 B3 B4 產(chǎn)量 A1 7 A2 4 A3 9 銷量 3 6 5 6 3 11 3 10 1 9 2 7 4 10 5 8 3 4 1 6 3 3 55 總的運輸費＝ (3 1)+(6 4) +(4 3) +(1 2)+(3 10)+(3 5)=86元 元素差額法對最小元素法進行了改進，考慮到產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方案。 8 5 10 2 1 20 15 15 15 5 10 總運費是 z=10 8+5 2+15 1=105 最小元素法： 56 8 5 10 2 1 20 15 15 5 15 10 總運費 z=10 5+15 2+5 1=85 后一種方案考慮到 C11與 C21之間的差額是 8－ 2=6，如果不先調(diào)運x21，到后來就有可能 x11≠0，這樣會使總運費增加較大，從而先調(diào)運 x21，再是 x22，其次是 x12 用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。 57 方法 2： Vogel法 元素差額法 1）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。 B1 B2 B3 B4 產(chǎn)量 行差額 A1 7 7 A2 4 1 A3 9 1 銷量 3 6 5 6 列差額 2 5 1 3 3 11 3 10 1 9 2 7 4 10 5 8 58 2）再從差值最大的行或列中找出最小運價確定供需關系和供需數(shù)量。當產(chǎn)地或銷地中有一方數(shù)量供應完畢或得到滿足時，劃去運價表中對應的行或列。 重復 1)和 2)，直到找出初始解為至。 B1 B2 B3 B4 產(chǎn)量 行差額 A1 7 7 A2 4 1 A3 9 1 銷量 3 6 5 6 列差額 2 5 1 3 3 11 3 10 1 9 2 7 4 10 5 8 5 59 單位 銷地 運價 產(chǎn)地 產(chǎn)量 行差 額 3 11 3 10 7 1 9 2 8 4 7 4 10 5 9 銷量 3 6 5 6 列差額 4321 BBBB321AAA7 1 1 3 5 2 1 5 60 單位 銷地 運價