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