第一講緒論、線性規(guī)劃引論(運籌學基礎-清華大學,王永縣)

1、偉倫樓南405電話：62789897(O)，62785184(H)E-mail: W 第一講1 緒論o運籌學簡述 o運籌學的主要內(nèi)容 o本課程教材和參考書o本課程特點和要求o本課程授課方式與考核 2 線性規(guī)劃引論o線性規(guī)劃概述 o從實際問題中提煉數(shù)學模型舉例第一講o運籌學（Operations Research）是系統(tǒng)工程的最重要的理論基 礎 之 一 ， 在 美 國 有 人 把 運 籌 學 稱 之 為 管 理 科 學(Management Science)。運籌學所研究的問題，可簡單地歸結(jié)為一句話：“依照給定條件和目標，從眾多方案中選擇最佳方案”，故有人稱之為最優(yōu)化技術。o1938年英國最早出

2、現(xiàn)了軍事運籌學，命名為“Operational Research”,1942年，美國從事這方面工作的科學家命其名為“Operations Research”這個名字一直延用至今。o美國運籌學的早期著名工作之一是研究深水炸彈起爆深度問題。當飛機發(fā)現(xiàn)潛艇后，飛機何時投擲炸彈及炸彈的引爆引度是多少？運籌學工作者對大量統(tǒng)計數(shù)字進行認真分析后，提出如下決策：1.僅當潛艇浮出水面或剛下沉時，方投擲深水炸彈。2炸彈的起爆深度為離水面25英尺（這是當時深水炸彈所容許的最淺起爆點）。空軍采用上述決策后，所擊沉潛艇成倍增加，從而為運籌學增添了榮譽。第一講o也許有人懷疑，運籌學是研究從眾多方案（甚至無限多個方案）中

3、選佳的優(yōu)化技術，那么在當代計算機技術迅速發(fā)展的今天，這種優(yōu)化技術是否會喪失其重要性？事實正相反，新型計算機的出現(xiàn)，恰為運籌學的應用開辟了新天地。o假設有70艘油輪向70個港口運貨，已知每艘油輪駛向每個港口的費用，油輪公司需制訂出最優(yōu)運輸方案。采用全枚舉法（窮舉法）需計算方案數(shù)為70!(大于10100 ）；IBM公司當時生產(chǎn)的大計算機1秒種大約可算出109（即10億）個方案。若要逐個算出全部方案，則需調(diào)用占有空間為1050個地球一樣大的IBM公司生產(chǎn)的眾多大計算機同時計算幾百億年以上。而在這種大機器上用線性規(guī)劃的單純形法計算只需幾秒鐘（這是整數(shù)規(guī)劃問題）。o可見，將運籌學與計算機科學及其它科學結(jié)

4、合應用，將會產(chǎn)生更好的效果。 第一講o運籌學發(fā)展到今天，內(nèi)容已相當豐富，分支也很多。對其內(nèi)容的分類方法不盡相同，主要是根據(jù)解決的問題特點以及技術本身特點來分類。根據(jù)解決問題的主要特征可分兩大類：確定型和概率型。其中確定型包含：線性規(guī)劃，整數(shù)規(guī)劃，動態(tài)規(guī)劃，非線性規(guī)劃，多目標決策及確定性存貯等；概率型中包含：回歸分析，決策論，對策論，排隊論，馬爾可夫鏈，圖論與網(wǎng)絡，概率存貯及搜索技術等。o本課將闡述運籌學中最基本的部分規(guī)劃論（即線性規(guī)劃，整數(shù)規(guī)劃，動態(tài)規(guī)劃及非線性規(guī)劃）。 第一講o先修課：高等數(shù)學，基礎概率、線性代數(shù)o教材：運籌學規(guī)劃論及網(wǎng)絡，王永縣編著o參考書：教材后面的參考文獻（共16本）第

5、一講o目的：不僅掌握優(yōu)化理論方法的專業(yè)知識，更重要的是提高分析問題和解決問題的能力。o方法：強調(diào)思路、觀點及弄清物理概念，掌握一定的理論推導能力，但不搞純數(shù)學公式。o避免2種傾向：只羅列方法，不講本質(zhì)；或只追求數(shù)學推導，掩蓋物理概念。o內(nèi)容為2部分：基本技術和開闊思路。第一講o本課程授課方式（3學時/周，共11周）講授為主，結(jié)合習題作業(yè)o作業(yè)成績A（10），B（8），C（6），D（0）D為不交作業(yè)，重在參與o每人準備1個作業(yè)本，寫上姓名，班級第一講o線性規(guī)劃的廣泛應用是計算機時代的產(chǎn)物。o1902年，Julius Farkas 發(fā)表論文，闡述有關線性規(guī)劃問題。o1938年，英國人康德進行較詳細

6、研究。o1947年，美國學者George Dantzig（丹茨格）發(fā)明了求解線性規(guī)劃的單純形法（1951年發(fā)表），從而為線性規(guī)劃的推廣奠定了基礎。有人認為，求解線性規(guī)劃的單純形算法可與求解線性方程組的高斯消元法相媲美。第一講o線性規(guī)劃的數(shù)學模型有三要素，從實際問題提煉成數(shù)學模型時，首先尋找需求解的未知量xj (j=1,n)，然后列舉三要素： 1.列寫與自變量（未知量）有關的若干個線性約束條件（等式或不等式）。2.列寫自變量xj取值限制（xj0，xj0或不限）。3.列寫關于自變量的線性目標函數(shù)值（極大值或極小值）。o其中，前兩條稱為可行條件，最后一條稱為優(yōu)化條件。符合這三個條件的數(shù)學模型通常稱為

7、線性規(guī)劃的一般型（general）。 第一講例1-1飲食問題o每人每天食用的食品中含有各種必需的營養(yǎng)素，家庭主婦面臨著一種抉擇：如何采購食品，才能在保證必需營養(yǎng)素最低需求量前提下花錢最少？o這是典型的線性規(guī)劃問題。設有n種食品供選擇，m種營養(yǎng)素應保證一定量。令：xj每天食用的j種食品數(shù)量cj單位j種食品的價格aij單位j種食品含有 i種營養(yǎng)素數(shù)量bi每天對營養(yǎng)i的最低需求量第一講針對問題特點，可列寫線性規(guī)劃數(shù)學模型如下： （最低營養(yǎng)需求約束） （自變量約束，食品量不會為負） （目標函數(shù)，使購食品費用取最小值） （i=1,2,m; j=1,2,n） ininuibxaxaxa21110jxmin

8、2211nnxcxaxcz0jx第一講例1-2 Chebyslev近似給出一組方程 o其中，mn，希求一組近似解x1，x2, xn使誤差盡量小。即求出一組解，使之代入方程組中，造成不滿足約束的方程的最大誤差量盡量小。這是長期以來被認為必存在的這樣一個解而又很難找到解的問題，然而用線性規(guī)劃求解卻比較方便。下面就討論如何建立該問題的線性規(guī)劃數(shù)學模型。 設：), 2 , 1(2211mibxaxaxaininii), 2 , 1(2211mixaxaxabniniiiim,max21第一講o則問題變?yōu)榍蟪鲆唤Mxj(j=1,2,n)使盡量小，于是變?yōu)椋?即： 且令min 為統(tǒng)一標志，令 x0，則上述問題變?yōu)橄率鼍€形規(guī)劃問題 ：), 2 , 1(mii), 2 , 1(11mixaxabninii第一講), 2 , 1(110110mibxaxaxbxaxaxininiinini不等式約束：自變量約束：x00，xj不限（j=1,2,n）目標函數(shù)：x0min第一