簡(jiǎn)介:運(yùn)籌學(xué)復(fù)習(xí),1、線性規(guī)劃的基本概念2、單純形法和對(duì)偶單純形法3、對(duì)偶線性規(guī)劃4、運(yùn)輸問題5、目標(biāo)規(guī)劃6、整數(shù)規(guī)劃7、網(wǎng)絡(luò)最大流問題8、網(wǎng)絡(luò)最短路徑問題,第一章線性規(guī)劃模型和單純形法,線性規(guī)劃問題一般模型目標(biāo)函數(shù)MAX,MIN約束條件≥,,≤變量符號(hào)≥0,UNR,≤0線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)MIN約束條件變量符號(hào)≥0,非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式極大化目標(biāo)函數(shù)轉(zhuǎn)化為極小化目標(biāo)函數(shù)系數(shù)變號(hào)約束條件是不等式轉(zhuǎn)化為等式“≤”約束加上松弛變量“≥”約束減去松弛變量變量沒有符號(hào)限制轉(zhuǎn)化為變量非負(fù)沒有符號(hào)限制的變量用兩個(gè)非負(fù)變量的差表示例如MAXZ3X14X22X35X4ST4X1X22X3X44X1X23X3X4≤142X13X2X32X4≥3X1≥0,X2≥2,X3≤0,X4UNR,線性規(guī)劃的圖解,畫約束直線確定滿足約束條件的半平面所有半平面的交集凸多邊形線性規(guī)劃的可行域畫兩條目標(biāo)函數(shù)等值線確定目標(biāo)函數(shù)優(yōu)化的方向平行移動(dòng)目標(biāo)函數(shù)等值線得到線性規(guī)劃的最優(yōu)解,線性規(guī)劃問題的概念基設(shè)標(biāo)準(zhǔn)形式的LP問題的約束方程組的秩為M,B是系數(shù)矩陣A中的M階滿秩子矩陣,則稱B是該LP問題的一個(gè)基。基變量B中的每一個(gè)列向量成為基向量,對(duì)應(yīng)的變量為基變量,共有M個(gè)。非基變量B以外的列向量稱為非基向量,對(duì)應(yīng)變量成為非基變量,共有NM個(gè)?;A(chǔ)解對(duì)應(yīng)基B,令所有的非基變量為零,求解約束方程組AXB,可惟一得出基變量的一組值,這樣得到的N個(gè)變量的一組解成為一個(gè)“基礎(chǔ)解”。基礎(chǔ)可行解如果一個(gè)基礎(chǔ)解中的所有變量都大于或等于0,則稱這個(gè)基礎(chǔ)解為“基礎(chǔ)可行解”。退化解基解中的非零分量的個(gè)數(shù)小于M個(gè)時(shí),即某個(gè)基變量為零時(shí),此時(shí)為退化解。線性規(guī)劃的基本定理線性規(guī)劃的基礎(chǔ)可行解就是可行域的極點(diǎn)。,,線性規(guī)劃的基本概念,MINZX12X2STX1X2≥41X1X2≥22X2≤53X1,X2≥0,引進(jìn)松弛變量X3,X4,X5MINZX12X2STX1X2X34X1X2X42X2X55X1,X2X3,X4,X5≥0,基礎(chǔ)解,O,A,B,C,D,E,F,G,B,,E,F,四邊形BEFG,基礎(chǔ)可行解,可行域,目標(biāo)函數(shù)等值線,最優(yōu)解,,,,B,5,G,A不是可行解,是由于變量()0,則XNI0,如果XNI0,則WI0,邊際利潤(rùn)大于0的資源,在最優(yōu)生產(chǎn)計(jì)劃條件下沒有剩余,WMJXJ0,如果WMJ0,則XJ0,如果XJ0,則WMJ0,最優(yōu)生產(chǎn)計(jì)劃條件下有剩余的資源,其邊際利潤(rùn)等于0,差額成本大于0(機(jī)會(huì)成本大于利潤(rùn))的產(chǎn)品,不安排生產(chǎn),安排生產(chǎn)的產(chǎn)品,差額成本等于0(機(jī)會(huì)成本等于利潤(rùn)),靈敏度分析主要分析當(dāng)所給問題數(shù)據(jù)改變時(shí),原有解的可行性和最有優(yōu)性有何變化。目標(biāo)函數(shù)中系數(shù)的變化約束條件右端常數(shù)的變化約束條件左端系數(shù)的變化引入新的變量引入新的約束,利用對(duì)偶單純形法求解,MINZ4X16X218X3STX13X3≥3X22X3≥5X1,X2,X3≥0,第三章運(yùn)輸問題,運(yùn)輸問題的模型,運(yùn)輸問題的表格表示,運(yùn)輸表中一個(gè)基必須具備的特點(diǎn)1、一個(gè)基應(yīng)占表中的MN1格2、構(gòu)成基的同行同列格子不能構(gòu)成閉回路3、一個(gè)基在表中所占的格子應(yīng)包括表的每行和每列,初始基可行解的求法西北角法最小元素法,最優(yōu)解的獲得,運(yùn)輸問題,用最小元素法得到一個(gè)初始基礎(chǔ)可行解,125,85,180,30,35,75,7,求非基變量X11的檢驗(yàn)數(shù),125,85,180,30,35,75,7,8,求非基變量X14的檢驗(yàn)數(shù),125,85,180,30,35,75,7,8,4,求非基變量X22的檢驗(yàn)數(shù),125,85,180,30,35,75,7,8,6,7,求非基變量X31的檢驗(yàn)數(shù),125,85,180,30,35,75,7,8,4,7,1,求非基變量X32的檢驗(yàn)數(shù),125,85,180,30,35,75,7,8,4,7,1,4,求非基變量X33的檢驗(yàn)數(shù),125,85,180,30,35,75,7,8,6,7,1,4,X3375進(jìn)基,X230離基,X243075105,X3418075105,確定進(jìn)基變量和離基變量,125,85,105,35,,3,,,,,,,求非基變量X11的檢驗(yàn)數(shù),125,85,105,35,,3,4,,,,,求非基變量X14的檢驗(yàn)數(shù),125,85,105,35,,3,4,8,,,,,,,求非基變量X22的檢驗(yàn)數(shù),125,85,105,35,6,4,4,8,,,,,求非基變量X23的檢驗(yàn)數(shù),125,85,105,35,,5,4,4,7,8,,,,,求非基變量X31的檢驗(yàn)數(shù),125,85,105,35,,5,4,4,7,3,8,,,,,得到最優(yōu)解X1285,X1335,X21125,X24105,X3375,X34105MINZ3660,求非基變量X32的檢驗(yàn)數(shù),,不平衡運(yùn)輸問題發(fā)大于收,則虛設(shè)收地,運(yùn)價(jià)為零發(fā)小于收,則虛設(shè)發(fā)地,運(yùn)價(jià)為零靈敏度分析基變量的運(yùn)價(jià)調(diào)整非基變量的運(yùn)價(jià)調(diào)整,物流配送案例,騰飛電子儀器廠在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器。大連分廠每月生產(chǎn)400臺(tái).廣州分廠每月生產(chǎn)600臺(tái)。該公司在上海和天津有兩個(gè)物流配送服務(wù)網(wǎng)點(diǎn),負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器進(jìn)行配送供應(yīng)。另外,因?yàn)榇筮B距離青島較近,公司同意大連分廠向青島直接供貨。這些城市間的每臺(tái)儀器的運(yùn)輸費(fèi)用標(biāo)在兩個(gè)城市間的弧上,單位為百元。公司應(yīng)該如何調(diào)運(yùn)儀器可使總運(yùn)輸費(fèi)用最低,廣州600,南昌350,天津,南京200,濟(jì)南150,大連400,青島300,上海,,,,,,,,,,,,,,2,4,4,6,3,6,2,5,6,1,4,3,3,多工廠模型,一家公司有A和B兩個(gè)工廠,每個(gè)工廠生產(chǎn)兩種同樣的產(chǎn)品,一種是普通的,每件利潤(rùn)10元一種是精制的,每件利潤(rùn)15元兩廠采用相同的加工工藝研磨和拋光A廠每周的研磨能力為80小時(shí),拋光能力為60小時(shí)B廠每周的研磨能力為60小時(shí),拋光能力為75小時(shí)兩廠生產(chǎn)各類單位產(chǎn)品所需的研磨和拋光工時(shí)以小時(shí)計(jì)如表所示另外,每類每件產(chǎn)品都消耗4公斤的原材料,該公司每周可獲得原材料120公斤問應(yīng)該如何制定生產(chǎn)計(jì)劃,分析先假定每周分配原料給A廠75公斤,B廠45公斤設(shè)X1為A廠的普通產(chǎn)品產(chǎn)量X2為A廠的精制產(chǎn)品產(chǎn)量X3為B廠的普通產(chǎn)品產(chǎn)量X4為B廠的精制產(chǎn)品產(chǎn)量,A廠模型MAXZ10X115X2ST4X14X2≤75原料A4X12X2≤80研磨A2X15X2≤60拋光AX1,X2≥0最優(yōu)解1125,75,利潤(rùn)225剩余20小時(shí)的研磨時(shí)間,B廠模型MAXZ10X315X4ST4X34X4≤45原料B5X33X4≤60研磨B5X36X4≤75拋光BX3,X4≥0最優(yōu)解1125,375,利潤(rùn)1685剩余2625小時(shí)的研磨時(shí)間和75小時(shí)的拋光工時(shí),假設(shè)建立一個(gè)公司模型,讓模型去確定原材料的分配MAXZ10X115X210X315X4ST4X14X24X34X4≤1204X12X2≤802X15X2≤605X33X4≤605X36X4≤75X1,X2,X3,X4≥0最優(yōu)解X1917,X2833,X4125,Z40415,多周期動(dòng)態(tài)生產(chǎn)計(jì)劃問題,考慮某廠配套生產(chǎn)產(chǎn)品問題今年頭四個(gè)月收到的訂單數(shù)量分別為3000,4500,3500和5000件該廠正常生產(chǎn)每月可生產(chǎn)產(chǎn)品3000件,利用加班還可生產(chǎn)1500件正常生產(chǎn)成本為每件5000元,加班生產(chǎn)還要追加1500元的成本,庫存成本為每件每月200元問該廠如何組織生產(chǎn)才能使生產(chǎn)成本最低,第五章目標(biāo)規(guī)劃,,概念偏差變量實(shí)際值與目標(biāo)值之間差距的變量表示,通常以DIDI表示,分別為正、負(fù)偏差變量,且有DI0、DI0,DIDI0優(yōu)先因子描述問題中目標(biāo)重要性程度的差別,一般用PI表示,通常I值越小,代表的優(yōu)先程度越高。目標(biāo)約束用來描述允許對(duì)給定目標(biāo)值有一定偏離程度的限制條件。,目標(biāo)規(guī)劃模型的特點(diǎn)1、引進(jìn)正負(fù)偏差變量2、模型中必須有目標(biāo)約束3、目標(biāo)函數(shù)為偏差變量的表達(dá)式4、以優(yōu)先級(jí)因子描述目標(biāo)的重要性程度目標(biāo)規(guī)劃的解法單純形法按單純形法求解一搬目標(biāo)規(guī)劃問題的滿意解。求解時(shí)需按優(yōu)先級(jí)的順序進(jìn)行逐步優(yōu)化。各目標(biāo)具有相同等級(jí)的目標(biāo)規(guī)劃各目標(biāo)具有不同優(yōu)先等級(jí)的目標(biāo)規(guī)劃各目標(biāo)具有賦權(quán)優(yōu)先等級(jí)的目標(biāo)規(guī)劃,第六章整數(shù)規(guī)劃,整數(shù)規(guī)劃的基本概念變量的取值為整數(shù)的LP問題為整數(shù)規(guī)劃問題。整數(shù)規(guī)劃的一般模型整數(shù)規(guī)劃的解法割平面法(純整數(shù)規(guī)劃)分支定界法,人力資源安排,某超市物流配送中心,星期六有4個(gè)裝卸工人當(dāng)班.要分別指派他們?nèi)ネ瓿?項(xiàng)不同的裝卸工作.每人做各項(xiàng)工作所取得的利潤(rùn)如下表所示.應(yīng)如何合理地指派這4人的工作,才能使配送中心獲得的利潤(rùn)最大。,,點(diǎn)與(有向)邊每一條邊和兩個(gè)節(jié)點(diǎn)關(guān)聯(lián),一條邊可以用兩個(gè)節(jié)點(diǎn)的標(biāo)號(hào)表示(I,J),路徑(PATH)前后相繼并且方向相同的邊序列P{1,2,2,3,3,4},4,2,3,1,4,2,3,1,網(wǎng)絡(luò)由點(diǎn)和邊組成,第七章網(wǎng)絡(luò)規(guī)劃,圖的基本概念,連通圖任意兩個(gè)節(jié)點(diǎn)之間至少有一條鏈的圖稱為連通圖,2,4,3,5,1,圈CYCLE起點(diǎn)和終點(diǎn)重合的鏈稱為圈Ρ{1,2,2,4,3,4,1,3}圈中各條邊方向不一定相同,4,2,3,1,,樹TREE無圈的連通圖稱為樹樹中只與一條邊關(guān)聯(lián)的節(jié)點(diǎn)稱為懸掛節(jié)點(diǎn),回路(CIRCUIT)起點(diǎn)和終點(diǎn)重合的路徑稱為回路Μ{1,2,2,4,4,1}回路中各條邊方向相同,4,2,3,1,,鏈(CHAIN)前后相繼并且方向不一定相同的邊序列稱為鏈C{1,2,3,2,3,4},4,2,3,1,樹的性質(zhì),任何樹至少有一個(gè)懸掛節(jié)點(diǎn),2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,,,如果樹的節(jié)點(diǎn)個(gè)數(shù)為M,則邊的個(gè)數(shù)為M1,樹中任意兩個(gè)節(jié)點(diǎn)之間只有唯一的一條鏈,在樹的任意兩個(gè)不相鄰的節(jié)點(diǎn)之間增加一條邊,則形成唯一的圈,最小支撐樹,由網(wǎng)絡(luò)的所有節(jié)點(diǎn)(M個(gè))和網(wǎng)絡(luò)的M1條邊組成的樹稱為網(wǎng)絡(luò)的支撐樹,構(gòu)成支撐樹的各邊賦權(quán)之和最小的為最小支撐樹。,最小支撐樹的算法KRUSKAL算法PRIM算法最短路問題D氏算法最短鏈問題網(wǎng)絡(luò)上的最大流問題最小割集,1,2,5,4,3,6,7,最大流問題,3,6,11,2,7,4,3,8,4,7,12,5,UIJ,,求從1到7的最大流,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,UIJ,,檢查每一條邊不飽和的方向,用表示,X0,X0,X0,X0,X0,X0,X0,X0,X0,X0,X0,X0,,①→②→⑥→⑦?MIN{?12,?26,?67}MIN{3,6,12}3①→③→⑤→⑦?MIN{?13,?35,?57}MIN{11,4,5}4,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,UIJ,,尋找從1到7的不飽和鏈,用表示,求出每一條不飽和鏈的間隙?,X0,X0,X0,X0,X0,X0,X0,X0,X0,X0,X0,X0,?3,,?6,?12,?11,?4,?5,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,UIJ,,增加不飽和鏈的流量檢查每一條邊不飽和的方向,用表示,X3,X3,X4,X0,X0,X0,X0,X0,X3,X4,X4,X0,,F7,F7,尋找從1到7的不飽和鏈,用表示,求出每一條不飽和鏈的間隙?,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,UIJ,,X3,X3,X4,X0,X0,X0,X0,X0,X3,X4,X4,X0,?7,F7,F7,,①→③→④→⑥→⑦?MIN{?13,?34,?46,?67}MIN{7,3,4,8}3,?3,?4,?9,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,UIJ,,增加不飽和鏈的流量檢查每一條邊不飽和的方向,用表示,X3,X3,X7,X0,X0,X3,X3,X0,X6,X4,X4,X0,,F10,F10,尋找從1到7的不飽和鏈,用表示,求出每一條不飽和鏈的間隙?,,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,UIJ,,X3,X3,X7,X0,X0,X3,X3,X0,X6,X4,X4,X0,,F10,F10,①→③→②→⑥→⑦?MIN{?13,?32,?26,?67}MIN{4,2,3,6}2,?4,?2,?3,?6,增加不飽和鏈的流量檢查每一條邊不飽和的方向,用表示,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,UIJ,,X3,X5,X9,X2,X0,X3,X3,X0,X8,X4,X4,X0,F12,F12,,,,尋找從1到7的不飽和鏈,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,UIJ,,X3,X5,X9,X2,X0,X3,X3,X0,X8,X4,X4,X0,F12,F12,已不存在從1到7的不飽和鏈。獲得最大流,F(xiàn)12X{1,3},X{2,4,5,6,7}最小割集為{1,2,3,2,3,4,3,5},用表示最小割集的容量為U12U32U34U35323412,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,最短路徑問題,求1到8的最短路徑,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,W10,X{1}MIN{02,06,03}MIN{2,6,3}2,W22,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,W10,X{1,2}MIN{29,25,24,06,03}MIN{11,7,6,6,3}3,W43,W22,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,W10,W22,X{1,2,4}MIN{29,25,24,06,37,36,310}MIN{11,7,6,6,10,9,13}5,W36,W43,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,W10,W22,X{1,2,3,4}MIN{29,25,68,36,310}MIN{11,7,14,9,13}7,W67,W43,W36,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,W10,W22,X{1,2,3,4,6}MIN{29,74,711,310}MIN{11,11,18,13}11,W511,W43,W36,W67,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,W10,W22,X{1,2,3,4,5,6}MIN{1112,77,711,310}MIN{23,14,18,13}13,W713,W43,W36,W67,W511,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,W10,W22,X{1,2,3,4,6,7}MIN{1112,77,136}MIN{23,14,19}14,W814,W43,W36,W67,W511,W713,,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,W10,W22,X{1,2,3,4,6,7,8}MIN{1112,77,136}MIN{23,14,19}14,W814,W43,W36,W67,W511,W713,W814,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,W10,W22,W43,W36,W67,W511,W713,W814,從1到8的最短路徑為14,最短路徑為1→2→6→8從1到其他節(jié)點(diǎn)的最短路徑如上圖紅線所示,其中到3和5的最短路徑有兩條。,一、最短路徑問題,求從A到E的最短路徑,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F5E0,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F4D15,F5E0,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F4D22,F5E0,F4D15,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F4D22,F5E0,F3C18,F4D15,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F4D22,F5E0,F3C27,F4D15,F3C18,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F4D22,F5E0,F3C312,F4D15,F3C18,F3C27,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F4D22,F5E0,F3C312,F4D15,F2B120,F3C27,F3C18,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F4D22,F5E0,F3C312,F4D15,F2B214,F3C27,F3C18,F2B121,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F4D22,F5E0,F3C312,F4D15,F2B319,F3C27,F3C18,F2B121,F2B214,,,,,,,,,,,,,,,,,,,,,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,F4D22,
下載積分: 4 賞幣
上傳時(shí)間:2024-01-06
頁數(shù): 115
大小: 1.64(MB)
子文件數(shù):