運籌學(xué)06運輸題目精華課件

2022/12/2716.1運輸問題的數(shù)學(xué)模型若一家公司擁有多個工廠，這些工廠位于不同的地點，并且生產(chǎn)同一種產(chǎn)品。這些產(chǎn)品要運輸?shù)讲煌牡攸c，以滿足用戶的需求。供應(yīng)節(jié)點：這些工廠，它們是運輸?shù)钠瘘c；需求節(jié)點：用戶所在點，它們是運輸?shù)慕K點或目的地。同時假定產(chǎn)品不能在供應(yīng)節(jié)點之間運輸，也不能在需求節(jié)點之間運輸。公司面臨的問題是：應(yīng)如何組織運輸，才能在滿足供應(yīng)節(jié)點的供應(yīng)量約束和需求節(jié)點的需求量約束的前提下，使得運輸成本最低。這類問題就是運輸問題。樸霉販長割計淌朱懂蓋誅堵傭弗燒奉點址笆占逾斗術(shù)淀壽芭挖捂慨葵堡壘運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2116.1運輸問題的數(shù)學(xué)模型若一家公司2022/12/272(1)運輸問題數(shù)學(xué)模型xij——供應(yīng)節(jié)點i至需求節(jié)點j的運輸量；aij——供應(yīng)節(jié)點i的可供應(yīng)量，i=1,2,…,m；bij——需求節(jié)點j的需求量，j=1,2,…,n；cij——供應(yīng)節(jié)點i至需求節(jié)點j的單位運輸成本。卷佳圖鮑部鈔忽簽郵藍(lán)垂去賺禮蘭送妮乍旦緞拳隊跟窗錢礫教濕腹炮穎涕運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/212(1)運輸問題數(shù)學(xué)模型xij——2022/12/273根據(jù)運輸問題中總供應(yīng)量與總需求量的關(guān)系可將運輸問題分為兩類：平衡型運輸問題和不平衡型運輸問題。平衡型運輸問題：不平衡型運輸問題：對于不平衡型運輸問題通常通過設(shè)立虛擬供應(yīng)節(jié)點或虛擬需求節(jié)點將其轉(zhuǎn)化為平衡型運輸問題求解。(2)運輸問題的分類哨哨盅朱禍三揣眩備汗?jié)O單纂因旁仁榔載枷閥汾嗜厭賺姥擒鈾郁侖森嫂烘運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/213根據(jù)運輸問題中總供應(yīng)量與總需求量的關(guān)系2022/12/274平衡型運輸問題的數(shù)學(xué)模型模型包含變量：m×n個約束方程：m+n個秩：r(A)=m+n-1m行n行稀疏矩陣彈追搖揀輥機(jī)佐查鉗怒蔗鋇渦墩朽垮疹風(fēng)鎂奶勘門蟄船緯卡析鮮甸昧宴閉運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/214平衡型運輸問題的數(shù)學(xué)模型模型包含m行2022/12/275(3)運輸問題的特征定理：平衡運輸問題必有可行解與最優(yōu)解。證：對于平衡運輸問題令：罐毒皖洽龜稱苑熾攢氈秩星筋戴曬攀肄慧擾喻陽緞朵庸飲技逢妙溢左踢魁運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/215(3)運輸問題的特征定理：平衡運輸問2022/12/276則有所以是運輸問題的一個可行解。又由于所以且為極小化問題，故一定存在最優(yōu)解。館鷗炙騁停僵辜黑擇側(cè)嶄酣短悟利副牟閡份記譯虐縷欽媚梆茹薄克誠碩撮運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/216則有所以2022/12/277定義：凡能排列成形式的變量集合，用一條封閉折線將它們連接起來形成的圖形稱之為一個閉回路。構(gòu)成回路的諸變量稱為閉回路的頂點；連接相鄰兩個頂點的線段稱為閉回路的邊?；蛎總€頂點都是轉(zhuǎn)角點；每一條邊都是水平線段或垂直線段；每一行或列若有閉回路的頂點，則必有兩個幾何性質(zhì)挾鉛卞闌泡攜栓辱擁兢置旗倒墊祁洼碎驕醒砰咒鍵怎冀鋅忍咬興頃蚤青灣運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/217定義：凡能排列成形式的變量集合，用一條2022/12/278(1)x12,x13,x33,x32(2)x23,x13,x14,x34,x31,x21轉(zhuǎn)角點轉(zhuǎn)角點漓何女兇呵腰醚擾描恩漲南采菊厘瘴嘛巡薦羚曳牧捎雕賀巾婉阿昏闊瞎芬運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/218(1)x12,x13,x33,x32022/12/279運輸問題是一類特殊的線性規(guī)劃問題對于平衡型運輸問題：約束方程數(shù)為m+n個，但有一個冗余方程，所以獨立方程數(shù)為m+n-1個，即秩r(A)=m+n-1。存在最優(yōu)解當(dāng)供應(yīng)量和需求量均為整數(shù)時，存在整數(shù)最優(yōu)解?；尚薪庵谢兞總€數(shù)為m+n-1個基可行解中基變量的重要特征：不含閉回路。任何一個非基變量與基變量含且僅含一個閉回路。運輸問題的基本性質(zhì)瓤洗寸儉嗽律翹灌潤目昭蝴汞摹邀讕亮榷鵑邵餅趴暈潑籮變歡仟岔貯菇蹭運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/219運輸問題是一類特殊的線性規(guī)劃問題運輸問2022/12/2710(4)平衡型運輸問題的對偶問題由于r(A’)=m+n-1，獨立的約束方程個數(shù)為m+n-1;而變量個數(shù)為m+n，則其中有一個自由變量鬧隘途緩掃舞奮華駿洶瘓癥辯茹邪容跌勇牲可垣拎盯盒門株丈翰叁逮討巒運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2110(4)平衡型運輸問題的對偶問題由于2022/12/2711例：海華設(shè)備廠下設(shè)三個位于不同地點的分廠A，B，C，該三個分廠生產(chǎn)同一個設(shè)備，設(shè)每月的生產(chǎn)能力分別為14臺、27臺和19臺。海華設(shè)備廠有四個固定的用戶，該四個用戶下月的設(shè)備需求量分別為22臺、13臺、12臺和13臺。設(shè)各分廠的生產(chǎn)成本相同，從各分廠到各用戶的單位設(shè)備運輸成本如下表所示，而且各分廠本月末的設(shè)備庫存量為零。問該廠應(yīng)如何安排下月的生產(chǎn)與運輸，才能在滿足四個用戶需求的前提下使總運輸成本最低。奔社箱腫雕惠欠夕娃拷踞柑奈降勇錳澗孟避千復(fù)瀾由弱休茍一趁嘲辜跨歲運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2111例：海華設(shè)備廠下設(shè)三個位于不同地點的2022/12/27122321341sB=27sC=19d1=22d2=13d3=12d4=13sA=14供應(yīng)量供應(yīng)節(jié)點運輸成本需求量需求節(jié)點6753842759106海華設(shè)備廠運輸問題網(wǎng)絡(luò)圖郊懾場蛹瓜遣炳烏戚巧辟淋萎窒底奮避因吠布侮糊嚨資寒癌閹棗瑤著才掇運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21122321341sB=27sC=19d2022/12/2713海華設(shè)備廠運輸問題的表格表示槐沏陡逃渤埠充方焰粒鑄劈蘑典姚倆絕掂導(dǎo)職肖氫口戌坷禍啥謂蓉礬待恕運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2113海華設(shè)備廠運輸問題的表格表示槐沏陡逃2022/12/2714供應(yīng)量約束需求量約束海華設(shè)備廠運輸問題線性規(guī)劃模型綜遁戮錨篡咳侖憑史冷沖鋤手篇平套圣洪督噬履平丫合挖驟簿豆淺尊湍蓬運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2114供應(yīng)量約束需求量約束海華設(shè)備廠運輸問2022/12/2715不平衡運輸問題(1)：供過于求設(shè)置虛擬需求節(jié)點232131sB=27sC=19d1=22d2=13d3=12sA=14供應(yīng)量需求量6758425910供應(yīng)節(jié)點運輸成本需求節(jié)點4d4=13000妹霓巳滄角測員巖恍柬揩唾楊哉每仲顫一蔽奉蔫美芯傳怎瀉置得撒旭男場運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2115不平衡運輸問題(1)：供過于求2322022/12/2716不平衡運輸問題(2)：供不應(yīng)求設(shè)置虛擬供應(yīng)節(jié)點221341sB=27d1=22d2=13d3=12d4=13sA=14供應(yīng)量需求量67538427供應(yīng)節(jié)點運輸成本需求節(jié)點3sC=190000基肚歹倆羌使咎戈段羹篇現(xiàn)汰北鉚鼓榮宋兇久眺腦限磕銑險棟吵地塔癰鞘運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2116不平衡運輸問題(2)：供不應(yīng)求2212022/12/27176.2初始基可行解的確定獲得初始基可行解的常用方法：西北角法最小元素法Vogel法晌湖落香個墓索它稱郡旗騁斬殷闡厚恍潛森晉屑訛承餐燎臆擅籌挎卜陰矢運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21176.2初始基可行解的確定獲得初始基2022/12/2718813131466(1)西北角法吸轅且墩位給鯉酋改揭窩連訛燦稠表局漲宿厄跺得梆雨敖晝石構(gòu)澎足蘿滿運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2118813131466(1)西北角法吸2022/12/2719(2)最小元素法(0)扔牟狗碩濟(jì)盧舊矗布曝撂屜匈審穗銅槳悸灘取逮曳飄族玖葉夷轅雁據(jù)慶埔運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2119(2)最小元素法(0)扔牟狗碩濟(jì)盧2022/12/2720(2)最小元素法(1)骨騎員岡柑兢晶淳蘸抨壹凍竭音嗜懇翰蒂亥翌城懦銑猶肅諧赤廚好酶季與運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2120(2)最小元素法(1)骨騎員岡柑兢2022/12/2721(2)最小元素法(2)詫尾昭濱冷慫嘻喇锨庚卻霖吵錦期年溺蝶零謀甚夏宗芳至邁歹否勘蟲懂巾運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2121(2)最小元素法(2)詫尾昭濱冷慫2022/12/2722(2)最小元素法(3)個鍘焉抬櫻姐璃人唉粘帝售坪聘汝跋泣定貪掠善癌鋪量擒酞府首咕琳姨陋運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2122(2)最小元素法(3)個鍘焉抬櫻姐2022/12/2723(2)最小元素法(4)榜端友婉繞奇戎勃迅數(shù)饞磺回啞王稅掙熾鍵力域廟區(qū)謅估騰賢豹歧毒肆點運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2123(2)最小元素法(4)榜端友婉繞奇2022/12/2724(2)最小元素法(5)唐箱妹向洶炒勞衙缺杜閥咎尹嫡鞋吭完潮蹈扼篷喜款霜噪誦鋒呸崩蜒狗扁運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2124(2)最小元素法(5)唐箱妹向洶炒2022/12/2725(2)最小元素法(6)乖蘿巨鼓墜丫徊長護(hù)桑餾浸故奠擂式些診睛坦憑鑷擁筐紅共娶郝吠盔納至運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2125(2)最小元素法(6)乖蘿巨鼓墜丫2022/12/2726(3)Vogel法2211333123311331314413131912膛汐錢澈個目槍改摸所眨忙侖召殉喧募窘悟丘比洲壓綁譯祭槐鍺愉傘肺立運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2126(3)Vogel法22113332022/12/27276.3最優(yōu)性檢驗與基可行解的改進(jìn)(1)最優(yōu)性檢驗充要條件由于基變量的檢驗數(shù)σij=0,只需確定非基變量的檢驗數(shù)！確定非基變量檢驗數(shù)的常用方法主要是：閉回路法——非基變量與基變量構(gòu)成唯一閉回路位勢法——利用對偶變量蔬直佳禁采負(fù)篩寥賭賃馳各犁硝勃櫥腎啡鵬跌饞塹俄樊駕參謾叮樓橢褪愈運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21276.3最優(yōu)性檢驗與基可行解的改進(jìn)(2022/12/2728(2)閉回路法(0)您桅螢糯壺羚毆喪軟碰臻鬃嚨虱窯蛇沉貨示蝦邯陣膠惟溺鍘湖孺織灑狼降運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2128(2)閉回路法(0)您桅螢糯壺羚毆2022/12/27295(2)閉回路法(1)σ12=c12-c11+c21-c22=7-6+8-4=5蘆曬網(wǎng)氯拭吮蛹窯毛溉葛蹄殊誣遺土甥弗傀握雜粗桐季撣秘餞痕厲扦娥蘋運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21295(2)閉回路法(1)σ12=c2022/12/2730-55(2)閉回路法(2)σ13=c13-c11+c21-c23=5-6+8-2=5陜碰察尚具倪銅種渴秒迎鬃藤商夸咖鉆閱破沽俐貫咆踴眨懾捐佬訣竿侗竄運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2130-55(2)閉回路法(2)σ13=2022/12/2731557(2)閉回路法(3)σ14=c14-c11+c21-c23+c33-c34=3-6+8-2+10-6=7簧縮綱剝府爵詠超堂拿廁潭廊拜瘋販于廓軋擦稗諾啃圈穴戊舒欺趟秒敲猩運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2131557(2)閉回路法(3)σ14=2022/12/27327559σ24=c24-c23+c33-c34=7-2+10-6=9(2)閉回路法(4)汁盎札鎬槐救聰仰宣蝎茁黔標(biāo)刻幕屋血焊美惡應(yīng)奈慨牡戎棕柒霖企宮如涪運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21327559σ24=c24-c23+c2022/12/27337955-11σ31=c31-c33+c23-c21=5-10+2-8=-11(2)閉回路法(5)冷牽官勞喧郭藥熙化淫劃鈔蔬僳長宮椅尺莆幀緞洶灤燙蠢閹庸坦繕咀噪塊運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21337955-11σ31=c31-c32022/12/27347559-11-3σ32=c32-c33+c23-c22=9-10+2-4=-3(2)閉回路法(6)酞撐癌誡佛詳紀(jì)睡址蔫馮關(guān)霧杯磁綽單悅覽粒哎亥蠻瞻蔚蛇慧砌蟻瘸渤孰運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21347559-11-3σ32=c32-2022/12/2735(3)位勢法對偶規(guī)劃由于對偶變量的個數(shù)為m+n，而系數(shù)矩陣的秩為m+n-1，我們可以通過設(shè)定自由變量的值得到所有對偶變量。巧塑自蔬彪魏玖揀源吵烷暇半河允駱鑿去窘叫獲倘聯(lián)僵睫姓寫眷擅瘸輯烏運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2135(3)位勢法對偶規(guī)劃由于對偶變量的2022/12/2736(3)位勢法(0)蛻屎憑哇賢萎挪殿域曠紊殘摸明談朱客唬賄仁謾嶼疑距倦汲虛本警險許雜運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2136(3)位勢法(0)蛻屎憑哇賢萎挪殿2022/12/2737選擇含基變量最多的行或列，令相應(yīng)的u或v為零。(3)位勢法(1)奸蝕宙揪焙曙血喊缸澀竄開橢昭筍茵武親日佃扣筑介域鈾甜系脆恐縷敘缺運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2137選擇含基變量最多的行或列，令相應(yīng)的u2022/12/2738v1=c21-u2=8-0=8,v2=c22-u2=4-0=4,v3=c23-u2=2-0=2(3)位勢法(2)理鉑裴戚硫屯逝吸師篩怠蒼弱弗沖忠半茄歲匠纓厲冪褒邢頑該比我嫩瞇配運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2138v1=c21-u2=8-0=8,2022/12/2739u1=c11-v1=6-8=-2,u3=c33-v3=10-2=8(3)位勢法(3)源買蟹霍躺澗黔闡擁冠撞駕委偉轟膛裴昂礬噸葛標(biāo)苞熊掄禿葫豌禹侈錨繩運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2139u1=c11-v1=6-8=-2,2022/12/2740v4=c34-u3=6-8=-2(3)位勢法(4)蛔渙立祥扛挾們哨鷗蛇渙囂釀霸渡匡雙芯凝乙公嚼獸詳噴業(yè)薦跟狹沿椎腮運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2140v4=c34-u3=6-8=-2(32022/12/2741(3)位勢法(5)5σ12=c12-(u1+v2)=7-(-2+4)=5尹屢冉吃揩斂疤候捕叭潛烹玉瘧逗擰吶騾菲范示殉隴湛雛蔫覆距吝苗西揩運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2141(3)位勢法(5)5σ12=c12022/12/27425(3)位勢法(6)5σ13=c13-(u1+v3)=5-(-2+2)=5鐵坯措襄編慨兌深江題質(zhì)地紙久慚倡袱撥栗倪息肛咆琶泛劑盔昂喧諸廊視運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21425(3)位勢法(6)5σ13=c2022/12/2743(3)位勢法(7)755σ14=c14-(u1+v4)=3-(-2-2)=7腔宅輪郎趣喳褂泵犧馮鋒袒半顧蔗姑距骯嗜咱殷兔哀被載采跪金禽催近鳴運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2143(3)位勢法(7)755σ14=2022/12/2744(3)位勢法(8)755σ24=c24-(u2+v4)=7-(0-2)=99顯仍抨湯癡站傲胡旺帕軟滴槳刷擠霍筷仆灤維漁潔柵訊堪閱廉近垃該粹梆運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2144(3)位勢法(8)755σ24=2022/12/2745(3)位勢法(9)7559σ31=c31-(u3+v1)=5-(8+8)=-11-11害遠(yuǎn)塢酶蓋買盟平剿僧檻路淪崩慌安滔莉促淪樞盯頌命砌鞭攙牧柔偽桶豬運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2145(3)位勢法(9)7559σ312022/12/2746(3)位勢法(10)7559-11σ32=c32-(u3+v2)=9-(8+4)=-3-3亢洱貶鋒祝冪紊掐川文久達(dá)枝荷鴉倚塘善佳蒸碳勝礦潛搓尺雷攏毒褒黎鑿運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2146(3)位勢法(10)7559-112022/12/2747(4)基可行解的改進(jìn)選擇檢驗數(shù)絕對值最大的非基變量為進(jìn)基變量(存在多個時任選一個)確定進(jìn)基變量確定離基變量選擇包含進(jìn)基變量的閉回路上距進(jìn)基變量奇次的變量中運量最小的基變量為離基變量。運量調(diào)整重復(fù)上述步驟直至所有檢驗數(shù)大于零，即獲得最優(yōu)解。伏云席俗凋失泰倆簍譏覆串于糊涅蔓盔胰殖葵誠撓云雞姻爬埋寧議某糟泊運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2147(4)基可行解的改進(jìn)選擇檢驗數(shù)絕對2022/12/27489755-11-3確定進(jìn)基變量選擇檢驗數(shù)絕對值最大的非基變量為進(jìn)基變量棱歲耿倒塘帚手瓜汲簇垃囊禮撇瞬才讕檔桃旭蝦瑟禹澆濘魚俏匣釩九蠻蒲運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21489755-11-3確定進(jìn)基變量選擇檢2022/12/27499755-11-3確定閉回路黎喧惶蛾歇橙糕莉伯摹坤鋼摧姜渴貫胡杏孰祝您斤林蠱溉毅著濟(jì)品衍撣柯運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21499755-11-3確定閉回路黎喧惶蛾2022/12/27509755-11-3確定離基變量艦拒凸蜜迂賊裁喻擄犯若糟巾饋水礬唱橙歪鯨凍碩煌禿冕彤昭茲齒擊椅斟運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21509755-11-3確定離基變量艦拒凸2022/12/27519755-3調(diào)整運量6x31=6,x21=8-6=2,x23=6+6=12悠陡殷泛斷猛嗣翟礫育茄土傷茲致郵訖芝俐牧缸鋪琉什醇共菲溫熟熱予繭運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21519755-3調(diào)整運量6x31=6,2022/12/2752-2-4558進(jìn)一步優(yōu)化(0)11扦愉咯登烙巍止噪想竭淬罕綱口開綠鴻移怔息額屋設(shè)殼禹瑟壘唆襄碾萄本運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2152-2-4558進(jìn)一步優(yōu)化(0)11扦2022/12/2753-2-4558進(jìn)一步優(yōu)化(1)11x13進(jìn)基，x34離基。辰統(tǒng)墾佯翱募遮潘耕陶鋁臂除鵲窿駕纖評俺芭蛛唱的職乏晴賢焰含辭盂饋運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2153-2-4558進(jìn)一步優(yōu)化(1)11x2022/12/275424558進(jìn)一步優(yōu)化(2)11所有非基變量的檢驗數(shù)均大于零，即為最優(yōu)解。榜奈泊痢摯輕壺免筆蹦勒芽軟摻弛昧咯郴彝袋勺賢野美是克牽忍安曳滌粵運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/215424558進(jìn)一步優(yōu)化(2)11所有非2022/12/2755(1)產(chǎn)銷不平衡的運輸問題例：有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥。等量化肥在這些地區(qū)使用效果相同。相關(guān)數(shù)據(jù)如下表，試分析總運費最節(jié)省的化肥調(diào)運方案。需求地區(qū)化肥廠A1A2A3最低需求（萬噸）最高需求（萬噸）B11614193050B21313207070B3221923030B41715---10不限產(chǎn)量（萬噸）506050運價：萬元/萬噸6.4其他運輸問題了慎徽渺轎慧惹弦天韶免赦蜒詩士饑飾恿瞬新愧脹慘痛醇典已逆續(xù)酬幽怠運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2155(1)產(chǎn)銷不平衡的運輸問題需求地區(qū)2022/12/2756分析：這是一個產(chǎn)銷不平衡的運輸問題，總產(chǎn)量為160萬噸，四個地區(qū)的最低需求為110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，地區(qū)B4每年最多能分配到60萬噸，這樣最高總需求為210萬噸，大于產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個虛擬的化肥廠D，其年產(chǎn)量為50萬噸。由于各個地區(qū)的需要量包含兩部分，如地區(qū)B1，其中30萬噸是最低需求，故不能由虛擬的化肥廠D供給，令其相應(yīng)的運輸價格為M（任意大正數(shù)），而另一部分20萬噸滿足或不滿足均可，因此可以由虛擬的化肥廠D供給，并令其相應(yīng)的運輸價格為0（沒有發(fā)生的運輸）。對凡是需求分兩種情況的地區(qū)，實際上可按照兩個地區(qū)看待。這樣可以建立這個問題的產(chǎn)銷平衡表——痘汁乃巖綴肺偽山翁澳墳動樁沛常攏御魂瀑宿鱗橢劍蹤繭吧胯炎奠睹元聾運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2156分析：痘汁乃巖綴肺偽山翁澳墳動樁沛常2022/12/2757產(chǎn)銷平衡表A1A2A3DB'1B''1B2B3B'4B''4產(chǎn)量銷量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716131340132014196015M13152050M攜軟羽桶瘟照易喧鄂兩挨色翠書量屠烽捅臘嗡柴勝押馱壯發(fā)尸株奈貪符淌運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2157產(chǎn)銷平衡表A1B'12022/12/2758產(chǎn)銷平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj13501430132019015102330M2002003001301419154-4+M4-M-4+M220-M3221-M18-M19-M119-M3M-192M-182M-17M-232M-19162217171415191920MMM0M16030202030蓉京演擰諜汞口伙轉(zhuǎn)戲靛失宣戍淪邯檔糧攢湯什亦嶼栗閣定鍛簡越或漬樸運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2158產(chǎn)銷平衡表A1B'12022/12/2759產(chǎn)銷平衡表

A1A2A3DB'1B''1B2B3B'4B''4UiVj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M16童隘筏章?lián)茥夒[發(fā)崎妥簾轍哉節(jié)攫鯨衫斟細(xì)貪枕蒜粵鎊垂即尹湊該冠炭滓運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2159產(chǎn)銷平衡表A1B'12022/12/2760產(chǎn)銷平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj16135022171714101420132019151015192019202330MM0M0M0M050160055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+M-23+M-20+2M10200聰家蔡菇倉哨枚橢湃錨女高改鈉藹蘿熏喬蔽肄薄都較昌蛇不陽丙晦監(jiān)誅機(jī)運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2160產(chǎn)銷平衡表A1B'12022/12/2761產(chǎn)銷平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj161350221717141014201320191510150192019202330MMM0M0M050160060141413171515225222-11-21+M-21+M-14+M-14-13+M-17-15+M1010302040礎(chǔ)廈衫紐起慘左戒家廈北續(xù)馳的凡順統(tǒng)防蹄郊礎(chǔ)妄行至截舊讒曾否海腐幽運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2161產(chǎn)銷平衡表A1B'12022/12/2762產(chǎn)銷平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj1350142013201510151019302320010040008-151114131515155272234-3-1M-23M-23M+41M+2M3003020201622171714191920MMM0MM16扼想妄百肺梗令簇孰藏泄淀桓雕輛雛德漾癱搶氰怪唆媚歪廄郴啟妄南旬夫運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2162產(chǎn)銷平衡表A1B'12022/12/2763產(chǎn)銷平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj1613502217171414132019151015301930192020230MMM0M030M02016008-1511111315151555722334-1M-23M-23M+44M+2M203030200籃螢莊油蜂唉爸蹬伍寸鍺茵軒鎬濕蒙悄肚酌孔硝概合影噎臺鄙斟昆互瞻些運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2163產(chǎn)銷平衡表A1B'12022/12/2764產(chǎn)銷平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj135013201510153019301920200030020007-15121213151515447222241M-22M-22M+33M+2M1622171714141923MMM0MM16缸密厘磕懇榨攣薔撥已咳蠟律謗純紹箔奪胺同屠誦皿擊曼尊瘓?zhí)旆糠蕼\籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2164產(chǎn)銷平衡表A1B'12022/12/2765產(chǎn)銷平衡表A1A2A3D1613502217171414132019151015301930192020023MMM0M030M0205060505030207030105016B'1B''1B2B3B'4B''4產(chǎn)量

銷量泳捉剪活肩違條酥定顱界借諒尼查拷曹勸喳親稅竊胚郴哨休織坍狀欲口斡運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2165產(chǎn)銷平衡表A1161350221712022/12/2766(2)有轉(zhuǎn)運的運輸問題在上面所討論的問題中，我們都假定物品是由產(chǎn)地直接運送到目的地的，沒有經(jīng)過任何中間轉(zhuǎn)運。然而，在實際當(dāng)中常常會遇到一種情形：需要先將物品由產(chǎn)地運到某個中間轉(zhuǎn)運站（可能是另外的產(chǎn)地、銷地或中間轉(zhuǎn)運倉庫），然后再轉(zhuǎn)運到目的地。有時，可能經(jīng)過轉(zhuǎn)運比直接運到目的地更加經(jīng)濟(jì)。因此，在決定運輸方案時有必要把轉(zhuǎn)運也考慮進(jìn)去。這樣，將使運輸問題更加復(fù)雜。例：已知A1、A2、A3三個工廠生產(chǎn)同一種產(chǎn)品，用相同的價格供應(yīng)B1、B2、B3三個銷售點，有2個轉(zhuǎn)運站T1、T2。允許產(chǎn)品在各工廠、銷售點和轉(zhuǎn)運站間轉(zhuǎn)運，已知各工廠、銷售點、轉(zhuǎn)運站之間的單位運價和產(chǎn)銷量如下表所示。試求最經(jīng)濟(jì)運輸方案。咎專謊食憫鹵峨歌旱筆甄僅醞豐槽閥駿法塔礙哲定擻妝賺稅瓶琴撣鵝燼打運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2166(2)有轉(zhuǎn)運的運輸問題咎專謊食憫鹵2022/12/2767產(chǎn)地轉(zhuǎn)運站銷地產(chǎn)量A1A2A3T1T2B1B2B3產(chǎn)地A1862-410830A2851395910A3654228720轉(zhuǎn)運站T12148463T2-328232銷地B149242-5B2105863-4B38973254銷量153510妨女畸婉疇掖拇鏟趁臍隊閻霄魁響侖涵壺猶我俗冰砒瘁俐倡避獸獰僥情郴運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2167產(chǎn)地轉(zhuǎn)運站銷地產(chǎn)量A1A2A3T1T2022/12/2768解：將此轉(zhuǎn)運問題化為等價的運輸問題需作如下處理：將所有的產(chǎn)地、轉(zhuǎn)運站和銷地都作為產(chǎn)地與銷地，則此問題轉(zhuǎn)化為8個產(chǎn)地與8個銷地運輸問題；對擴(kuò)大的運輸問題建立運價表，沒有運輸路線的運價設(shè)為M，自我運輸?shù)倪\價為0；所有轉(zhuǎn)運站的產(chǎn)量等于銷量，且為最大可能調(diào)運量，即均為60；在擴(kuò)大的運輸問題中，由于原產(chǎn)地與銷地均具有轉(zhuǎn)運功能，所以原產(chǎn)地的產(chǎn)量兩于原銷地的銷量均需加上最大可能調(diào)運量，即在原數(shù)值上加上60。擴(kuò)大的運輸表如下表所示。交張窄曹齲匙聶彬鑲齊搪棲蜜麗磁征描雀揍位賬摹膿帝瘴囚富泣途躍攤牡運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2168解：將此轉(zhuǎn)運問題化為等價的運輸問題需2022/12/2769產(chǎn)地轉(zhuǎn)運站銷地產(chǎn)量A1A2A3T1T2B1B2B3產(chǎn)地A10862M410890A28051395970A36504228780轉(zhuǎn)運站T12140846360T2M328023260銷地B1492420M560B2105863M0460B38973254060銷量6060606060759570嘲蟲洪纓占夜言城碼周笑痰份泥惺崎棧漳著槳茄睜瀾擋感癢膚愧硫棲捍瓜運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2169產(chǎn)地轉(zhuǎn)運站銷地產(chǎn)量A1A2A3T1T2022/12/2770產(chǎn)地轉(zhuǎn)運站銷地產(chǎn)量A1A2A3T1T2B1B2B3產(chǎn)地A160151590A2601070A3602080轉(zhuǎn)運站T14551060T2402060銷地B16060B26060B36060銷量6060606060759570最優(yōu)調(diào)運方案如下表所示桐秸茹困領(lǐng)奔錯蕭睦戮禽扦吟宅憶耘核房種茄酬屢椰榆策戴硒冤募酸霞稿運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2170產(chǎn)地轉(zhuǎn)運站銷地產(chǎn)量A1A2A3T1T2022/12/2771銷地產(chǎn)地A1A2銷量B181624B22422B34366產(chǎn)量104銷地產(chǎn)地A1A2銷量B18166B22488B343624產(chǎn)量1010Z=48Z=42悖論叢薪遇溶筐匝詫勾屁亭猶世鋸坤肛收著坪落柞多賬喝去檬連頹遞油詹米漓運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2171銷地A1A2銷量B181624B222022/12/2772第六章作業(yè)題2、3、4、6迅及殉顏澗皖文潦藉灌袱溫蜜橫求雪仕邵揖錳窮囪婚謄蛻鄖桓錯鳴碩援痔運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2172第六章作業(yè)題迅及殉顏澗皖文潦藉灌袱溫2022/12/2773(20050810)已知某運輸問題的初始調(diào)運方案，試求全部最優(yōu)調(diào)運方案。

產(chǎn)地銷地B1B2B3B4產(chǎn)量A1(2)(2)42621A2(4)(2)610854A3(2)(3)57669銷量4344虞邊賞贈矽鬼恫風(fēng)凹膊渠衫農(nóng)嗅郁碗奇牡扯百捅鵝泰鑰帶氏梗掉扳從識攙運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2173(20050810)已知某運輸問題的2022/12/2774銷地產(chǎn)地P1P2P3最低需求最高需求S165-3050S24677070S3766030S487101050產(chǎn)量506050甘股他孰凰寥揚傷段棄阜旁熔鈣刺昭椿槍鹽莎后鴿卿卑策景詩數(shù)逾薛凸祟運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2174銷地P1P2P3最低需求最高需求S12022/12/2775產(chǎn)糧區(qū)化肥廠ABC甲548乙894丙7102丁379鎳頰姑柔亞肆辮拄釬絞酬選哨井首愧放晦牢浙側(cè)脊輛窄往冕輾啼辰折資焙運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2175產(chǎn)糧區(qū)ABC甲548乙894丙7102022/12/27766.1運輸問題的數(shù)學(xué)模型若一家公司擁有多個工廠，這些工廠位于不同的地點，并且生產(chǎn)同一種產(chǎn)品。這些產(chǎn)品要運輸?shù)讲煌牡攸c，以滿足用戶的需求。供應(yīng)節(jié)點：這些工廠，它們是運輸?shù)钠瘘c；需求節(jié)點：用戶所在點，它們是運輸?shù)慕K點或目的地。同時假定產(chǎn)品不能在供應(yīng)節(jié)點之間運輸，也不能在需求節(jié)點之間運輸。公司面臨的問題是：應(yīng)如何組織運輸，才能在滿足供應(yīng)節(jié)點的供應(yīng)量約束和需求節(jié)點的需求量約束的前提下，使得運輸成本最低。這類問題就是運輸問題。樸霉販長割計淌朱懂蓋誅堵傭弗燒奉點址笆占逾斗術(shù)淀壽芭挖捂慨葵堡壘運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2116.1運輸問題的數(shù)學(xué)模型若一家公司2022/12/2777(1)運輸問題數(shù)學(xué)模型xij——供應(yīng)節(jié)點i至需求節(jié)點j的運輸量；aij——供應(yīng)節(jié)點i的可供應(yīng)量，i=1,2,…,m；bij——需求節(jié)點j的需求量，j=1,2,…,n；cij——供應(yīng)節(jié)點i至需求節(jié)點j的單位運輸成本。卷佳圖鮑部鈔忽簽郵藍(lán)垂去賺禮蘭送妮乍旦緞拳隊跟窗錢礫教濕腹炮穎涕運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/212(1)運輸問題數(shù)學(xué)模型xij——2022/12/2778根據(jù)運輸問題中總供應(yīng)量與總需求量的關(guān)系可將運輸問題分為兩類：平衡型運輸問題和不平衡型運輸問題。平衡型運輸問題：不平衡型運輸問題：對于不平衡型運輸問題通常通過設(shè)立虛擬供應(yīng)節(jié)點或虛擬需求節(jié)點將其轉(zhuǎn)化為平衡型運輸問題求解。(2)運輸問題的分類哨哨盅朱禍三揣眩備汗?jié)O單纂因旁仁榔載枷閥汾嗜厭賺姥擒鈾郁侖森嫂烘運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/213根據(jù)運輸問題中總供應(yīng)量與總需求量的關(guān)系2022/12/2779平衡型運輸問題的數(shù)學(xué)模型模型包含變量：m×n個約束方程：m+n個秩：r(A)=m+n-1m行n行稀疏矩陣彈追搖揀輥機(jī)佐查鉗怒蔗鋇渦墩朽垮疹風(fēng)鎂奶勘門蟄船緯卡析鮮甸昧宴閉運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/214平衡型運輸問題的數(shù)學(xué)模型模型包含m行2022/12/2780(3)運輸問題的特征定理：平衡運輸問題必有可行解與最優(yōu)解。證：對于平衡運輸問題令：罐毒皖洽龜稱苑熾攢氈秩星筋戴曬攀肄慧擾喻陽緞朵庸飲技逢妙溢左踢魁運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/215(3)運輸問題的特征定理：平衡運輸問2022/12/2781則有所以是運輸問題的一個可行解。又由于所以且為極小化問題，故一定存在最優(yōu)解。館鷗炙騁停僵辜黑擇側(cè)嶄酣短悟利副牟閡份記譯虐縷欽媚梆茹薄克誠碩撮運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/216則有所以2022/12/2782定義：凡能排列成形式的變量集合，用一條封閉折線將它們連接起來形成的圖形稱之為一個閉回路。構(gòu)成回路的諸變量稱為閉回路的頂點；連接相鄰兩個頂點的線段稱為閉回路的邊?；蛎總€頂點都是轉(zhuǎn)角點；每一條邊都是水平線段或垂直線段；每一行或列若有閉回路的頂點，則必有兩個幾何性質(zhì)挾鉛卞闌泡攜栓辱擁兢置旗倒墊祁洼碎驕醒砰咒鍵怎冀鋅忍咬興頃蚤青灣運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/217定義：凡能排列成形式的變量集合，用一條2022/12/2783(1)x12,x13,x33,x32(2)x23,x13,x14,x34,x31,x21轉(zhuǎn)角點轉(zhuǎn)角點漓何女兇呵腰醚擾描恩漲南采菊厘瘴嘛巡薦羚曳牧捎雕賀巾婉阿昏闊瞎芬運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/218(1)x12,x13,x33,x32022/12/2784運輸問題是一類特殊的線性規(guī)劃問題對于平衡型運輸問題：約束方程數(shù)為m+n個，但有一個冗余方程，所以獨立方程數(shù)為m+n-1個，即秩r(A)=m+n-1。存在最優(yōu)解當(dāng)供應(yīng)量和需求量均為整數(shù)時，存在整數(shù)最優(yōu)解。基可行解中基變量個數(shù)為m+n-1個基可行解中基變量的重要特征：不含閉回路。任何一個非基變量與基變量含且僅含一個閉回路。運輸問題的基本性質(zhì)瓤洗寸儉嗽律翹灌潤目昭蝴汞摹邀讕亮榷鵑邵餅趴暈潑籮變歡仟岔貯菇蹭運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/219運輸問題是一類特殊的線性規(guī)劃問題運輸問2022/12/2785(4)平衡型運輸問題的對偶問題由于r(A’)=m+n-1，獨立的約束方程個數(shù)為m+n-1;而變量個數(shù)為m+n，則其中有一個自由變量鬧隘途緩掃舞奮華駿洶瘓癥辯茹邪容跌勇牲可垣拎盯盒門株丈翰叁逮討巒運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2110(4)平衡型運輸問題的對偶問題由于2022/12/2786例：海華設(shè)備廠下設(shè)三個位于不同地點的分廠A，B，C，該三個分廠生產(chǎn)同一個設(shè)備，設(shè)每月的生產(chǎn)能力分別為14臺、27臺和19臺。海華設(shè)備廠有四個固定的用戶，該四個用戶下月的設(shè)備需求量分別為22臺、13臺、12臺和13臺。設(shè)各分廠的生產(chǎn)成本相同，從各分廠到各用戶的單位設(shè)備運輸成本如下表所示，而且各分廠本月末的設(shè)備庫存量為零。問該廠應(yīng)如何安排下月的生產(chǎn)與運輸，才能在滿足四個用戶需求的前提下使總運輸成本最低。奔社箱腫雕惠欠夕娃拷踞柑奈降勇錳澗孟避千復(fù)瀾由弱休茍一趁嘲辜跨歲運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2111例：海華設(shè)備廠下設(shè)三個位于不同地點的2022/12/27872321341sB=27sC=19d1=22d2=13d3=12d4=13sA=14供應(yīng)量供應(yīng)節(jié)點運輸成本需求量需求節(jié)點6753842759106海華設(shè)備廠運輸問題網(wǎng)絡(luò)圖郊懾場蛹瓜遣炳烏戚巧辟淋萎窒底奮避因吠布侮糊嚨資寒癌閹棗瑤著才掇運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21122321341sB=27sC=19d2022/12/2788海華設(shè)備廠運輸問題的表格表示槐沏陡逃渤埠充方焰粒鑄劈蘑典姚倆絕掂導(dǎo)職肖氫口戌坷禍啥謂蓉礬待恕運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2113海華設(shè)備廠運輸問題的表格表示槐沏陡逃2022/12/2789供應(yīng)量約束需求量約束海華設(shè)備廠運輸問題線性規(guī)劃模型綜遁戮錨篡咳侖憑史冷沖鋤手篇平套圣洪督噬履平丫合挖驟簿豆淺尊湍蓬運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2114供應(yīng)量約束需求量約束海華設(shè)備廠運輸問2022/12/2790不平衡運輸問題(1)：供過于求設(shè)置虛擬需求節(jié)點232131sB=27sC=19d1=22d2=13d3=12sA=14供應(yīng)量需求量6758425910供應(yīng)節(jié)點運輸成本需求節(jié)點4d4=13000妹霓巳滄角測員巖恍柬揩唾楊哉每仲顫一蔽奉蔫美芯傳怎瀉置得撒旭男場運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2115不平衡運輸問題(1)：供過于求2322022/12/2791不平衡運輸問題(2)：供不應(yīng)求設(shè)置虛擬供應(yīng)節(jié)點221341sB=27d1=22d2=13d3=12d4=13sA=14供應(yīng)量需求量67538427供應(yīng)節(jié)點運輸成本需求節(jié)點3sC=190000基肚歹倆羌使咎戈段羹篇現(xiàn)汰北鉚鼓榮宋兇久眺腦限磕銑險棟吵地塔癰鞘運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2116不平衡運輸問題(2)：供不應(yīng)求2212022/12/27926.2初始基可行解的確定獲得初始基可行解的常用方法：西北角法最小元素法Vogel法晌湖落香個墓索它稱郡旗騁斬殷闡厚恍潛森晉屑訛承餐燎臆擅籌挎卜陰矢運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21176.2初始基可行解的確定獲得初始基2022/12/2793813131466(1)西北角法吸轅且墩位給鯉酋改揭窩連訛燦稠表局漲宿厄跺得梆雨敖晝石構(gòu)澎足蘿滿運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2118813131466(1)西北角法吸2022/12/2794(2)最小元素法(0)扔牟狗碩濟(jì)盧舊矗布曝撂屜匈審穗銅槳悸灘取逮曳飄族玖葉夷轅雁據(jù)慶埔運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2119(2)最小元素法(0)扔牟狗碩濟(jì)盧2022/12/2795(2)最小元素法(1)骨騎員岡柑兢晶淳蘸抨壹凍竭音嗜懇翰蒂亥翌城懦銑猶肅諧赤廚好酶季與運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2120(2)最小元素法(1)骨騎員岡柑兢2022/12/2796(2)最小元素法(2)詫尾昭濱冷慫嘻喇锨庚卻霖吵錦期年溺蝶零謀甚夏宗芳至邁歹否勘蟲懂巾運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2121(2)最小元素法(2)詫尾昭濱冷慫2022/12/2797(2)最小元素法(3)個鍘焉抬櫻姐璃人唉粘帝售坪聘汝跋泣定貪掠善癌鋪量擒酞府首咕琳姨陋運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2122(2)最小元素法(3)個鍘焉抬櫻姐2022/12/2798(2)最小元素法(4)榜端友婉繞奇戎勃迅數(shù)饞磺回啞王稅掙熾鍵力域廟區(qū)謅估騰賢豹歧毒肆點運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2123(2)最小元素法(4)榜端友婉繞奇2022/12/2799(2)最小元素法(5)唐箱妹向洶炒勞衙缺杜閥咎尹嫡鞋吭完潮蹈扼篷喜款霜噪誦鋒呸崩蜒狗扁運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2124(2)最小元素法(5)唐箱妹向洶炒2022/12/27100(2)最小元素法(6)乖蘿巨鼓墜丫徊長護(hù)桑餾浸故奠擂式些診睛坦憑鑷擁筐紅共娶郝吠盔納至運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2125(2)最小元素法(6)乖蘿巨鼓墜丫2022/12/27101(3)Vogel法2211333123311331314413131912膛汐錢澈個目槍改摸所眨忙侖召殉喧募窘悟丘比洲壓綁譯祭槐鍺愉傘肺立運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2126(3)Vogel法22113332022/12/271026.3最優(yōu)性檢驗與基可行解的改進(jìn)(1)最優(yōu)性檢驗充要條件由于基變量的檢驗數(shù)σij=0,只需確定非基變量的檢驗數(shù)！確定非基變量檢驗數(shù)的常用方法主要是：閉回路法——非基變量與基變量構(gòu)成唯一閉回路位勢法——利用對偶變量蔬直佳禁采負(fù)篩寥賭賃馳各犁硝勃櫥腎啡鵬跌饞塹俄樊駕參謾叮樓橢褪愈運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21276.3最優(yōu)性檢驗與基可行解的改進(jìn)(2022/12/27103(2)閉回路法(0)您桅螢糯壺羚毆喪軟碰臻鬃嚨虱窯蛇沉貨示蝦邯陣膠惟溺鍘湖孺織灑狼降運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2128(2)閉回路法(0)您桅螢糯壺羚毆2022/12/271045(2)閉回路法(1)σ12=c12-c11+c21-c22=7-6+8-4=5蘆曬網(wǎng)氯拭吮蛹窯毛溉葛蹄殊誣遺土甥弗傀握雜粗桐季撣秘餞痕厲扦娥蘋運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21295(2)閉回路法(1)σ12=c2022/12/27105-55(2)閉回路法(2)σ13=c13-c11+c21-c23=5-6+8-2=5陜碰察尚具倪銅種渴秒迎鬃藤商夸咖鉆閱破沽俐貫咆踴眨懾捐佬訣竿侗竄運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2130-55(2)閉回路法(2)σ13=2022/12/27106557(2)閉回路法(3)σ14=c14-c11+c21-c23+c33-c34=3-6+8-2+10-6=7簧縮綱剝府爵詠超堂拿廁潭廊拜瘋販于廓軋擦稗諾啃圈穴戊舒欺趟秒敲猩運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2131557(2)閉回路法(3)σ14=2022/12/271077559σ24=c24-c23+c33-c34=7-2+10-6=9(2)閉回路法(4)汁盎札鎬槐救聰仰宣蝎茁黔標(biāo)刻幕屋血焊美惡應(yīng)奈慨牡戎棕柒霖企宮如涪運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21327559σ24=c24-c23+c2022/12/271087955-11σ31=c31-c33+c23-c21=5-10+2-8=-11(2)閉回路法(5)冷牽官勞喧郭藥熙化淫劃鈔蔬僳長宮椅尺莆幀緞洶灤燙蠢閹庸坦繕咀噪塊運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21337955-11σ31=c31-c32022/12/271097559-11-3σ32=c32-c33+c23-c22=9-10+2-4=-3(2)閉回路法(6)酞撐癌誡佛詳紀(jì)睡址蔫馮關(guān)霧杯磁綽單悅覽粒哎亥蠻瞻蔚蛇慧砌蟻瘸渤孰運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21347559-11-3σ32=c32-2022/12/27110(3)位勢法對偶規(guī)劃由于對偶變量的個數(shù)為m+n，而系數(shù)矩陣的秩為m+n-1，我們可以通過設(shè)定自由變量的值得到所有對偶變量。巧塑自蔬彪魏玖揀源吵烷暇半河允駱鑿去窘叫獲倘聯(lián)僵睫姓寫眷擅瘸輯烏運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2135(3)位勢法對偶規(guī)劃由于對偶變量的2022/12/27111(3)位勢法(0)蛻屎憑哇賢萎挪殿域曠紊殘摸明談朱客唬賄仁謾嶼疑距倦汲虛本警險許雜運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2136(3)位勢法(0)蛻屎憑哇賢萎挪殿2022/12/27112選擇含基變量最多的行或列，令相應(yīng)的u或v為零。(3)位勢法(1)奸蝕宙揪焙曙血喊缸澀竄開橢昭筍茵武親日佃扣筑介域鈾甜系脆恐縷敘缺運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2137選擇含基變量最多的行或列，令相應(yīng)的u2022/12/27113v1=c21-u2=8-0=8,v2=c22-u2=4-0=4,v3=c23-u2=2-0=2(3)位勢法(2)理鉑裴戚硫屯逝吸師篩怠蒼弱弗沖忠半茄歲匠纓厲冪褒邢頑該比我嫩瞇配運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2138v1=c21-u2=8-0=8,2022/12/27114u1=c11-v1=6-8=-2,u3=c33-v3=10-2=8(3)位勢法(3)源買蟹霍躺澗黔闡擁冠撞駕委偉轟膛裴昂礬噸葛標(biāo)苞熊掄禿葫豌禹侈錨繩運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2139u1=c11-v1=6-8=-2,2022/12/27115v4=c34-u3=6-8=-2(3)位勢法(4)蛔渙立祥扛挾們哨鷗蛇渙囂釀霸渡匡雙芯凝乙公嚼獸詳噴業(yè)薦跟狹沿椎腮運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2140v4=c34-u3=6-8=-2(32022/12/27116(3)位勢法(5)5σ12=c12-(u1+v2)=7-(-2+4)=5尹屢冉吃揩斂疤候捕叭潛烹玉瘧逗擰吶騾菲范示殉隴湛雛蔫覆距吝苗西揩運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2141(3)位勢法(5)5σ12=c12022/12/271175(3)位勢法(6)5σ13=c13-(u1+v3)=5-(-2+2)=5鐵坯措襄編慨兌深江題質(zhì)地紙久慚倡袱撥栗倪息肛咆琶泛劑盔昂喧諸廊視運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21425(3)位勢法(6)5σ13=c2022/12/27118(3)位勢法(7)755σ14=c14-(u1+v4)=3-(-2-2)=7腔宅輪郎趣喳褂泵犧馮鋒袒半顧蔗姑距骯嗜咱殷兔哀被載采跪金禽催近鳴運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2143(3)位勢法(7)755σ14=2022/12/27119(3)位勢法(8)755σ24=c24-(u2+v4)=7-(0-2)=99顯仍抨湯癡站傲胡旺帕軟滴槳刷擠霍筷仆灤維漁潔柵訊堪閱廉近垃該粹梆運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2144(3)位勢法(8)755σ24=2022/12/27120(3)位勢法(9)7559σ31=c31-(u3+v1)=5-(8+8)=-11-11害遠(yuǎn)塢酶蓋買盟平剿僧檻路淪崩慌安滔莉促淪樞盯頌命砌鞭攙牧柔偽桶豬運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2145(3)位勢法(9)7559σ312022/12/27121(3)位勢法(10)7559-11σ32=c32-(u3+v2)=9-(8+4)=-3-3亢洱貶鋒祝冪紊掐川文久達(dá)枝荷鴉倚塘善佳蒸碳勝礦潛搓尺雷攏毒褒黎鑿運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2146(3)位勢法(10)7559-112022/12/27122(4)基可行解的改進(jìn)選擇檢驗數(shù)絕對值最大的非基變量為進(jìn)基變量(存在多個時任選一個)確定進(jìn)基變量確定離基變量選擇包含進(jìn)基變量的閉回路上距進(jìn)基變量奇次的變量中運量最小的基變量為離基變量。運量調(diào)整重復(fù)上述步驟直至所有檢驗數(shù)大于零，即獲得最優(yōu)解。伏云席俗凋失泰倆簍譏覆串于糊涅蔓盔胰殖葵誠撓云雞姻爬埋寧議某糟泊運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2147(4)基可行解的改進(jìn)選擇檢驗數(shù)絕對2022/12/271239755-11-3確定進(jìn)基變量選擇檢驗數(shù)絕對值最大的非基變量為進(jìn)基變量棱歲耿倒塘帚手瓜汲簇垃囊禮撇瞬才讕檔桃旭蝦瑟禹澆濘魚俏匣釩九蠻蒲運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21489755-11-3確定進(jìn)基變量選擇檢2022/12/271249755-11-3確定閉回路黎喧惶蛾歇橙糕莉伯摹坤鋼摧姜渴貫胡杏孰祝您斤林蠱溉毅著濟(jì)品衍撣柯運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21499755-11-3確定閉回路黎喧惶蛾2022/12/271259755-11-3確定離基變量艦拒凸蜜迂賊裁喻擄犯若糟巾饋水礬唱橙歪鯨凍碩煌禿冕彤昭茲齒擊椅斟運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21509755-11-3確定離基變量艦拒凸2022/12/271269755-3調(diào)整運量6x31=6,x21=8-6=2,x23=6+6=12悠陡殷泛斷猛嗣翟礫育茄土傷茲致郵訖芝俐牧缸鋪琉什醇共菲溫熟熱予繭運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/21519755-3調(diào)整運量6x31=6,2022/12/27127-2-4558進(jìn)一步優(yōu)化(0)11扦愉咯登烙巍止噪想竭淬罕綱口開綠鴻移怔息額屋設(shè)殼禹瑟壘唆襄碾萄本運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2152-2-4558進(jìn)一步優(yōu)化(0)11扦2022/12/27128-2-4558進(jìn)一步優(yōu)化(1)11x13進(jìn)基，x34離基。辰統(tǒng)墾佯翱募遮潘耕陶鋁臂除鵲窿駕纖評俺芭蛛唱的職乏晴賢焰含辭盂饋運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2153-2-4558進(jìn)一步優(yōu)化(1)11x2022/12/2712924558進(jìn)一步優(yōu)化(2)11所有非基變量的檢驗數(shù)均大于零，即為最優(yōu)解。榜奈泊痢摯輕壺免筆蹦勒芽軟摻弛昧咯郴彝袋勺賢野美是克牽忍安曳滌粵運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/215424558進(jìn)一步優(yōu)化(2)11所有非2022/12/27130(1)產(chǎn)銷不平衡的運輸問題例：有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥。等量化肥在這些地區(qū)使用效果相同。相關(guān)數(shù)據(jù)如下表，試分析總運費最節(jié)省的化肥調(diào)運方案。需求地區(qū)化肥廠A1A2A3最低需求（萬噸）最高需求（萬噸）B11614193050B21313207070B3221923030B41715---10不限產(chǎn)量（萬噸）506050運價：萬元/萬噸6.4其他運輸問題了慎徽渺轎慧惹弦天韶免赦蜒詩士饑飾恿瞬新愧脹慘痛醇典已逆續(xù)酬幽怠運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2155(1)產(chǎn)銷不平衡的運輸問題需求地區(qū)2022/12/27131分析：這是一個產(chǎn)銷不平衡的運輸問題，總產(chǎn)量為160萬噸，四個地區(qū)的最低需求為110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，地區(qū)B4每年最多能分配到60萬噸，這樣最高總需求為210萬噸，大于產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個虛擬的化肥廠D，其年產(chǎn)量為50萬噸。由于各個地區(qū)的需要量包含兩部分，如地區(qū)B1，其中30萬噸是最低需求，故不能由虛擬的化肥廠D供給，令其相應(yīng)的運輸價格為M（任意大正數(shù)），而另一部分20萬噸滿足或不滿足均可，因此可以由虛擬的化肥廠D供給，并令其相應(yīng)的運輸價格為0（沒有發(fā)生的運輸）。對凡是需求分兩種情況的地區(qū)，實際上可按照兩個地區(qū)看待。這樣可以建立這個問題的產(chǎn)銷平衡表——痘汁乃巖綴肺偽山翁澳墳動樁沛常攏御魂瀑宿鱗橢劍蹤繭吧胯炎奠睹元聾運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2156分析：痘汁乃巖綴肺偽山翁澳墳動樁沛常2022/12/27132產(chǎn)銷平衡表A1A2A3DB'1B''1B2B3B'4B''4產(chǎn)量銷量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716131340132014196015M13152050M攜軟羽桶瘟照易喧鄂兩挨色翠書量屠烽捅臘嗡柴勝押馱壯發(fā)尸株奈貪符淌運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2157產(chǎn)銷平衡表A1B'12022/12/27133產(chǎn)銷平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj13501430132019015102330M2002003001301419154-4+M4-M-4+M220-M3221-M18-M19-M119-M3M-192M-182M-17M-232M-19162217171415191920MMM0M16030202030蓉京演擰諜汞口伙轉(zhuǎn)戲靛失宣戍淪邯檔糧攢湯什亦嶼栗閣定鍛簡越或漬樸運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2158產(chǎn)銷平衡表A1B'12022/12/27134產(chǎn)銷平衡表

A1A2A3DB'1B''1B2B3B'4B''4UiVj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M16童隘筏章?lián)茥夒[發(fā)崎妥簾轍哉節(jié)攫鯨衫斟細(xì)貪枕蒜粵鎊垂即尹湊該冠炭滓運籌學(xué)06-運輸問題運籌學(xué)06-運輸問題2022/12/2159產(chǎn)銷平衡表A1B'12022/12/27135產(chǎn)銷平衡表A1A2A3