運(yùn)籌學(xué)運(yùn)輸問(wèn)題ppt課件(已修改)
2025-05-19 22:16 本頁(yè)面
【正文】 1 第三章 運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題 約束條件的系數(shù)矩陣具有特殊的結(jié)構(gòu)，有更為簡(jiǎn)單的求解方法，從而節(jié)約大量的計(jì)算時(shí)間和費(fèi)用。 2 產(chǎn)地 m個(gè) , Ai表示， i=1,2,???,m； 產(chǎn)量 ai , i=1,2,???,m 銷(xiāo)地 產(chǎn)地 B1 B2 ?????? Bn 產(chǎn)量 A1 c11 c12 ?????? c1n a1 A2 c21 c22 ?????? c2n a2 ?????? ?????? ?????? ?????? ?????? ?????? Am cm1 cm2 ?????? cmn am 銷(xiāo)量 b1 b2 ?????? bn 表 要求使總運(yùn)費(fèi)最小的調(diào)運(yùn)方案。 Cij: 從 Ai到 Bj運(yùn)輸單位物資的運(yùn)價(jià) 銷(xiāo)售地 n個(gè)， Bj 表示， j=1,2,???,n； 銷(xiāo)售量 bj， j=1,2,???,n， 、運(yùn)輸問(wèn)題的數(shù)學(xué)模型 3 產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題 數(shù)學(xué)模型 解 : 假設(shè) xij 表示從 Ai到 Bj 的運(yùn)量 ,則所求的數(shù)學(xué)模型為 : ?????njjmii ba11總產(chǎn)量等于其總銷(xiāo)量，即 ???????????????????? ???? ?njmixmiaxnjbxxcZijinjijjmiijminjijij,2,1。,2,10,2,1,2,1m i n111 1????4 LP問(wèn)題 m?n個(gè)變量， m + n個(gè)約束條件 . 單純形法求解，在每個(gè)約束上加入一個(gè)人工變量 若 m =4， n = 5，變量個(gè)數(shù)就有 29個(gè)之多，非常復(fù)雜。 ???????????????????? ???? ?njmixmiaxnjbxxcZijinjijjmiijminjijij,2,1。,2,10,2,1,2,1m i n111 1????5 基本概念與重要結(jié)論 系數(shù)矩陣特點(diǎn)： （ 1）元素等于 0或 1； （ 2）每列只有兩個(gè)元素為 1，其余都是 0； （ 3）每一個(gè)變量，在前 m個(gè)約束方程中只出現(xiàn)一次，在后 n個(gè)約束方程中也只出現(xiàn)一次。 表上作業(yè)法 ???????????????????????101010010101110000001100000011,,,1221111????????????????????????????????????????????????????Axxxxxxmnmnnmi j ji1ni j ij1x b j 1 , 2 , , nx a i 1 , 2 , , m????????? ??????6 運(yùn)輸問(wèn)題的解 代表著一個(gè)運(yùn)輸方案 變量 xij的值 由 Ai調(diào)運(yùn)數(shù)量為 xij的物品給 Bj。 基變量 m+n1個(gè)， 只有 m+n1個(gè)約束條件是線性獨(dú)立的。 進(jìn)一步我們想知道，怎樣的 m+n1個(gè)變量會(huì)構(gòu)成一組基變量？ 7 01111)1(11111111111?????列展開(kāi)按第?????mD???????????????????????101010010101110000001100000011,,,1221111????????????????????????????????????????????????????Axxxxxxmnmnn8 基本概念 閉回路 ),1,1,1 slnjjj ls ?? ???且互不相同凡是能排成 ,(,, 1132222111 sjijijijijiji iixxxxxx sss ??互不相同，且 ,1 mik ?? ,1 sk ??形成的變量的集合 頂點(diǎn) 出現(xiàn)在閉回路中的變量 閉回路的邊 相鄰兩個(gè)變量用一條直線相連 例 設(shè) m = 3， n = 4，表 x34 x32 A3 x24 x21 A2 x12 x11 A1 B4 B3 B2 B1 銷(xiāo)地 產(chǎn)地 x1 x1 x3 x3 x2 x21 構(gòu)成一個(gè)閉回路。 9 x34 x32 A3 A2 x14 x12 A1 B4 B3 B2 B1 銷(xiāo)地 產(chǎn)地 10 定理 ： m+n1個(gè)變量 構(gòu)成基變量的充分必要條件是它不包含有任何閉回路。 )1(, 2211 ??? nmsxxx ss jijiji ?11 求解運(yùn)輸問(wèn)題的一種簡(jiǎn)化方法，實(shí)質(zhì)是單純形法。 （ 1）找初始基可行解 即在 (m?n) 產(chǎn)銷(xiāo)平衡表上給出m+n 1個(gè)數(shù)字格 不能構(gòu)成閉回路，且行和等于產(chǎn)量，列和等于銷(xiāo)售量； （ 2）求非基變量檢驗(yàn)數(shù) 在表上求出空格的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如果達(dá)到最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)入下一步； （ 3）確定換入變量和換出變量，找出新的基可行解，在表上用閉回路法進(jìn)行調(diào)整。 （ 4）重復(fù)（ 2）、（ 3）步，直到求得最優(yōu)解為止。 表上作業(yè)法 12 基本思想 就近供應(yīng)。即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開(kāi)始確定產(chǎn)銷(xiāo)關(guān)系，依次類(lèi)推，直到給出初始方案為止。 （ 1） 確定初始基可行解 ① 方法一：最小元素法 例 某公司有 3個(gè)生產(chǎn)同類(lèi)產(chǎn)品的工廠，生產(chǎn)的產(chǎn)品由 4個(gè)銷(xiāo)售點(diǎn)銷(xiāo)售，各工廠的生產(chǎn)量、各銷(xiāo)售點(diǎn)的銷(xiāo)售量以及各工廠到各銷(xiāo)售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如表 。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷(xiāo)售點(diǎn)的需要量的前提下，使總的運(yùn)費(fèi)為最小。 13 表 銷(xiāo)地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1