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

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

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

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

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

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

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

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

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