數(shù)學(xué)建模規(guī)劃模型講解

1、Email:數(shù)學(xué)建模講義1最優(yōu)化模型 -線(xiàn)性規(guī)劃 2參考書(shū)目1. 陳寶林。最優(yōu)化理論與算法。清華大學(xué)出版社.2. 謝金星，薛毅。優(yōu)化建模與lindo/lingo優(yōu)化軟件. 清華大學(xué)出版社.3 背景知識(shí)運(yùn)籌學(xué)理論的一部分最早起源于中國(guó)古代公元前6世紀(jì)孫武所著的孫子兵法孫臏“斗馬術(shù)”，田忌與齊王賽馬，博弈論運(yùn)籌帷幄之中，決勝千里之外”。這千古名句也 可以說(shuō)是對(duì)張良運(yùn)籌思想的贊頌和褒獎(jiǎng)。國(guó)外起源與發(fā)展1738年,D.Bernoulli首次提出了效用的概念，并以此作為決策的標(biāo)準(zhǔn)。 41896年，V.Pareto首次從數(shù)學(xué)角度提出多目標(biāo)優(yōu)化問(wèn)題，引進(jìn)了Pareto最優(yōu)的概念。 丹麥電話(huà)工程師A.K.Er

2、lang開(kāi)展了關(guān)于電話(huà)局中繼線(xiàn)數(shù)目的話(huà)務(wù)理論的研究，1909年發(fā)表了他將概率論應(yīng)用于電話(huà)話(huà)務(wù)理論的研究論文：“概率論與電話(huà)會(huì)話(huà)”，開(kāi)排隊(duì)論研究的先河。1935-38年，英國(guó)為了正確地運(yùn)用新研制的雷達(dá)系統(tǒng)來(lái)對(duì)付德國(guó)飛機(jī)的空襲，在皇家空軍中組織了一批科學(xué)家，進(jìn)行新戰(zhàn)術(shù)試驗(yàn)和戰(zhàn)術(shù)效率評(píng)價(jià)的研究，并取得了滿(mǎn)意的效果。他們把自己從事的這種工作命名為“Operational Research”(運(yùn)籌學(xué)，或直譯為作戰(zhàn)研究)。1939年，蘇聯(lián)的. 總結(jié)了他對(duì)生產(chǎn)組織的研究，寫(xiě)了生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一書(shū)，是線(xiàn)性規(guī)劃應(yīng)用于工業(yè)生產(chǎn)問(wèn)題的經(jīng)典著作 背景知識(shí)（續(xù)）51947年,G.B.Dantzig提出了單純形

3、方法后，線(xiàn)性規(guī)劃便迅速形成為一個(gè)獨(dú)立的分支。 并逐級(jí)發(fā)展起來(lái)。英國(guó)運(yùn)籌學(xué)會(huì)1948年成立（1948-53年是運(yùn)籌學(xué)俱樂(lè)部，1953年11月起改名為學(xué)會(huì)）。 。二次大戰(zhàn)勝利后，美英各國(guó)不但在軍事部門(mén)繼續(xù)保留了運(yùn)籌學(xué)的研究核心，而且在研究人員、組織的配備及研究范圍和水平上，都得到了進(jìn)一步的擴(kuò)大和發(fā)展，同時(shí)運(yùn)籌學(xué)方法也向政府和工業(yè)等部門(mén)擴(kuò)展。1951年出版了新版（1946年的原版是保密的，1948年才撤銷(xiāo)保密）的P.M.Morse和G.E.Kimball的運(yùn)籌學(xué)方法（Methods of Operations Research），這是二戰(zhàn)結(jié)束后，對(duì)戰(zhàn)時(shí)整個(gè)運(yùn)籌學(xué)工作做系統(tǒng)的專(zhuān)業(yè)敘述的一本著作。195

4、1年,H.W.Kuhn與A.W.Tucker提出了Kuhn-Tucker條件，標(biāo)志著非線(xiàn)性規(guī)劃理論的初步形成。 背景知識(shí)（續(xù)）61952年5月美國(guó)運(yùn)籌學(xué)會(huì)成立，并創(chuàng)刊Operations Research。1953年,R.Bellman提出動(dòng)態(tài)規(guī)劃的名稱(chēng)，并闡述了最優(yōu)化原理。 1954年，D.R.Dantzig等研究旅行推銷(xiāo)員問(wèn)題時(shí)提出了分解的思想，成為整數(shù)規(guī)劃中兩大方法割平面法與分枝定界法的萌芽。 1955年,G.Dantzig首先考慮出現(xiàn)隨機(jī)變量的線(xiàn)性規(guī)劃問(wèn)題，這是最早提出的隨機(jī)規(guī)劃中的有補(bǔ)償二階段問(wèn)題。 1956年, L.R.Ford,Jr.與 D.R.Fulkerson提出并解決了網(wǎng)絡(luò)

5、最大流問(wèn)題，加強(qiáng)了圖論與線(xiàn)性規(guī)劃的聯(lián)系，促進(jìn)了優(yōu)化理論的研究。背景知識(shí)（續(xù)）71959年1月1日，國(guó)際運(yùn)籌學(xué)會(huì)聯(lián)合會(huì)(1FORS)正式宣告成立，當(dāng)時(shí)的聯(lián)合會(huì)只包括英、美、法三個(gè)國(guó)家的運(yùn)籌學(xué)會(huì)，首任（1959-61年）主席（當(dāng)時(shí)稱(chēng)為秘書(shū)，到1968年第四屆時(shí)才改稱(chēng)主席）為英國(guó)的Charles Goodeve。 背景知識(shí)（續(xù)）8運(yùn)籌學(xué)理論在中國(guó)的研究與發(fā)展1957年，經(jīng)中國(guó)科學(xué)院力學(xué)研究所所長(zhǎng)錢(qián)學(xué)森的倡導(dǎo)，在該所成立了由許國(guó)志領(lǐng)導(dǎo)的國(guó)內(nèi)第一個(gè)運(yùn)籌學(xué)研究組(后成室)。劉源張、周華章、桂湘云等是該組最早的一批研究人員，從此在我國(guó)開(kāi)始了現(xiàn)代運(yùn)籌學(xué)的研究。當(dāng)年秋季，又有大學(xué)畢業(yè)生顧基發(fā)、董澤清、徐映波、陳

6、錫康、郭紹僖、李秉全等分配進(jìn)入該組。 1958年，中國(guó)科學(xué)院數(shù)學(xué)研究所所長(zhǎng)華羅庚率領(lǐng)廣大研究人員，包括吳文俊、越民義、萬(wàn)哲先、王元等在內(nèi)，也開(kāi)展了運(yùn)籌學(xué)應(yīng)用課題的研究，并影響和帶動(dòng)了全國(guó)范圍內(nèi)各部門(mén)、各高校的運(yùn)籌學(xué)應(yīng)用和推廣工作。運(yùn)輸和農(nóng)業(yè)等部門(mén)的“圖上作業(yè)法”、“打麥場(chǎng)設(shè)計(jì)”、“中國(guó)郵遞員問(wèn)題”是典型的成果。背景知識(shí)（續(xù)）91959年2月，山東大學(xué)在數(shù)學(xué)系中設(shè)置了國(guó)內(nèi)最早的一個(gè)運(yùn)籌學(xué)專(zhuān)門(mén)化，由謝力同與鄭漢鼎執(zhí)教。自當(dāng)年暑假開(kāi)始，每年都有運(yùn)籌學(xué)方向的學(xué)生畢業(yè)，為我國(guó)運(yùn)籌學(xué)事業(yè)的發(fā)展作出了重要貢獻(xiàn)。 1959年，中國(guó)科學(xué)院數(shù)學(xué)研究所成立了運(yùn)籌學(xué)研究室，研究人員都由所內(nèi)其它室組調(diào)入。孫克定任研究室

7、主任，該室最早的一批研究人員有排隊(duì)論組的越民義、吳方、徐光煇、韓繼業(yè)；對(duì)策論組的吳文俊、江加禾、施閨芳；數(shù)學(xué)規(guī)劃組的朱永津、應(yīng)玫茜、馬仲蕃、凌開(kāi)誠(chéng)等。與此同時(shí)，全國(guó)范圍內(nèi)很多高校也有大批教師轉(zhuǎn)入運(yùn)籌學(xué)領(lǐng)域。 背景知識(shí)（續(xù)）101965年起，華羅庚和他的小分隊(duì)在全國(guó)工業(yè)部門(mén)開(kāi)始普及推廣統(tǒng)籌法的群眾運(yùn)動(dòng)。在此后的二十年中，為普及推廣雙法（統(tǒng)籌法與從1970年開(kāi)始普及推廣的優(yōu)選法），他們走訪(fǎng)了全國(guó)23個(gè)省市中幾百個(gè)城市的幾千個(gè)工廠，并向數(shù)百萬(wàn)人開(kāi)設(shè)講座開(kāi)展工作，取得了巨大的社會(huì)效益和經(jīng)濟(jì)效益。 1965年華羅庚統(tǒng)籌方法平話(huà)及其補(bǔ)充一書(shū)由中國(guó)工業(yè)出版社出版。 1970年起，華羅庚和他的小分隊(duì)開(kāi)始在全國(guó)

8、范圍內(nèi)普及推廣優(yōu)選法的群眾運(yùn)動(dòng)。從此，統(tǒng)籌與優(yōu)選雙法變得家喻戶(hù)曉，雙法的普及推廣也取得了極為可觀的社會(huì)、經(jīng)濟(jì)效益。1971年華羅庚優(yōu)選法平話(huà)及其補(bǔ)充一書(shū)由國(guó)防工業(yè)出版社出版。背景知識(shí)（續(xù)）111980年4月22-26日在山東濟(jì)南，召開(kāi)了中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)會(huì)成立暨第一屆代表大會(huì)。中國(guó)運(yùn)籌學(xué)倡導(dǎo)者之一，中國(guó)科學(xué)院副院長(zhǎng)華羅庚主持了會(huì)議，有來(lái)自各地科研機(jī)構(gòu)、高等院校、軍事部門(mén)、工交企業(yè)等有關(guān)單位的82名代表出席。華羅庚在大會(huì)開(kāi)幕式與閉幕式上均發(fā)表了講話(huà)，回顧了他在全國(guó)范圍普及推廣“雙法”的經(jīng)驗(yàn)和成果，勉勵(lì)大家以克敵攻堅(jiān)的進(jìn)取精神積極開(kāi)展運(yùn)籌學(xué)研究。會(huì)議作了12個(gè)專(zhuān)題學(xué)術(shù)報(bào)告和個(gè)人成果的幾十個(gè)分組報(bào)告。

9、中國(guó)數(shù)學(xué)會(huì)理事長(zhǎng)華羅庚被推選兼任運(yùn)籌學(xué)會(huì)理事長(zhǎng)，越民義、許國(guó)志、余潛修為副理事長(zhǎng)，桂湘云為秘書(shū)長(zhǎng)，推選常務(wù)理事11名，理事42名。會(huì)議決定學(xué)會(huì)掛靠在中科院應(yīng)用數(shù)學(xué)所背景知識(shí)（續(xù)）12優(yōu)化模型應(yīng)用的廣泛性1. 系統(tǒng)分析，即生產(chǎn)計(jì)劃和經(jīng)營(yíng)決策中的優(yōu)化問(wèn)題。例如：合理計(jì)劃生產(chǎn):運(yùn)輸，分配，布局，選址，指派，下料、配料等優(yōu)化問(wèn)題（linear programming）;合理開(kāi)發(fā)（或配置）資源:可再生資源的持續(xù)開(kāi)發(fā),不可再生資源的優(yōu)化配置（linear programming）合理運(yùn)行設(shè)備:設(shè)備的最有運(yùn)行（維修）方案.合理組合投資:追求最大受益、最小風(fēng)險(xiǎn)的投資組合方案（Multiobjective pr

10、ogramming） 132. 工程設(shè)計(jì)和控制中的非線(xiàn)性分析（Non-linear programming and optimal control）例如： 結(jié)構(gòu)系統(tǒng)最優(yōu)設(shè)計(jì)（人字架設(shè)計(jì)）機(jī)械零件或部件的最優(yōu)化設(shè)計(jì)(輪軸頸,凸輪設(shè)計(jì))化工設(shè)備最優(yōu)設(shè)計(jì)（單件或連鎖設(shè)備優(yōu)化設(shè)計(jì)）電力網(wǎng)絡(luò)和水力網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)（平衡條件）14歷屆數(shù)模競(jìng)賽所涉及的優(yōu)化問(wèn)題：94年 A題 逢山開(kāi)路（工程設(shè)計(jì)優(yōu)化問(wèn)題）目標(biāo)：工程造價(jià)最低決策：在若干約束下選擇一條最佳線(xiàn)路95年 B題：天車(chē)調(diào)度問(wèn)題（生產(chǎn)操作優(yōu)化問(wèn)題）目標(biāo)：年鋼產(chǎn)量最大決策：天車(chē)調(diào)度的最優(yōu)方案設(shè)計(jì)96年 A題：最優(yōu)捕魚(yú)策略（開(kāi)發(fā)資源優(yōu)化問(wèn)題）目標(biāo)：可持續(xù)捕撈的努

11、力量及最大捕撈量決策：在平衡條件下確定五年內(nèi)最佳捕撈方案1597年 A題：零件參數(shù)設(shè)計(jì)（產(chǎn)品參數(shù)優(yōu)化設(shè)計(jì)） 目標(biāo)：產(chǎn)品總造價(jià)最低（產(chǎn)品質(zhì)量損失費(fèi)用 零件制造成本費(fèi)用） 決策：零件參數(shù)的最佳水平組合方案98年 A題：組合投資問(wèn)題（風(fēng)險(xiǎn)決策優(yōu)化問(wèn)題） 目標(biāo)（二目標(biāo)）：收益最大，風(fēng)險(xiǎn)最小 決策：組合投資方案99年 A題：自動(dòng)化車(chē)床管理（排隊(duì)-更新問(wèn)題） 目標(biāo)：生產(chǎn)工序的效益（費(fèi)用最低）最大 決策：最佳檢驗(yàn)間隔河刀具更換策略1699年 B題：鉆井布局問(wèn)題(生產(chǎn)計(jì)劃優(yōu)化問(wèn)題) 目標(biāo)：最大限度利用初步、勘探時(shí)的舊井?dāng)?shù) 決策：在規(guī)定精度的前提下確定系統(tǒng)勘探時(shí)的最 佳網(wǎng)絡(luò)分布 2002年 A題：車(chē)燈線(xiàn)光源的優(yōu)

12、化設(shè)計(jì) 目標(biāo)：線(xiàn)光源的功率最小 決策:在滿(mǎn)足設(shè)計(jì)規(guī)范的條件下,計(jì)算線(xiàn)光源的長(zhǎng)度 B題：彩票中的數(shù)學(xué) 目標(biāo)：最大限度地吸引彩民積極購(gòu)買(mǎi)彩票 決策：在保證彩民和彩票公司的利益上如何設(shè)置最佳彩票方案1704年 A題：奧運(yùn)會(huì)場(chǎng)館周?chē)性O(shè)計(jì) 目標(biāo)：經(jīng)濟(jì)效益最大化，各個(gè)區(qū)域的平衡問(wèn)題 05年 B題：DVD在線(xiàn)租賃 目標(biāo)：滿(mǎn)足顧客的需要，經(jīng)濟(jì)效益最大化 06年 A題：出版社書(shū)號(hào)分配問(wèn)題 目標(biāo)：經(jīng)濟(jì)效益最大化，不同學(xué)科書(shū)號(hào)的平衡問(wèn)題 07年 B題：北京公交線(xiàn)路設(shè)計(jì) 目標(biāo)：時(shí)間最小化，車(chē)票錢(qián)最小化，轉(zhuǎn)站最小化08年 A題：中國(guó)學(xué)費(fèi)的評(píng)價(jià)系統(tǒng) 目標(biāo)：經(jīng)濟(jì)效益最大化，考慮到老百姓的支付能力 09年 醫(yī)院眼科病人的

13、等待系統(tǒng) 目標(biāo)：提高病床的周轉(zhuǎn)率，降低病人的抱怨程度18優(yōu)化模型的一般形式x:決策變量f(x):目標(biāo)函數(shù)gi(x)0:約束條件可行解：滿(mǎn)足約束條件的解最優(yōu)解：取得最值的可行解次優(yōu)解：一個(gè)較滿(mǎn)意的可行解可行集（域）：所有可行解組成的集合，19 最優(yōu)化問(wèn)題至少有兩要素：一是可能的方案；二是要追求的目標(biāo)。后者是前者的函數(shù)。如果第一要素與時(shí)間無(wú)關(guān)就稱(chēng)為靜態(tài)最優(yōu)化問(wèn)題，否則稱(chēng)為動(dòng)態(tài)最優(yōu)化問(wèn)題。20建立最優(yōu)化問(wèn)題數(shù)學(xué)模型的三要素： （1）決策變量和參數(shù)。決策變量是由數(shù)學(xué)模型的解確定的未知數(shù)。參數(shù)表示系統(tǒng)的控制變量，有確定性的也有隨機(jī)性的。 （2）約束或限制條件。 由于現(xiàn)實(shí)系統(tǒng)的客觀物質(zhì)條件限制，模型必須包

14、括把決策變量限制在它們可行值之內(nèi)的約束條件，而這通常是用約束的數(shù)學(xué)函數(shù)形式來(lái)表示的。21 一般的模型簡(jiǎn)化工作包括以下幾類(lèi)： （1）將離散變量轉(zhuǎn)化為連續(xù)變量。 （2）將非線(xiàn)性函數(shù)線(xiàn)性化。 （3）刪除一些非主要約束條件。 （3）目標(biāo)函數(shù)。這是作為系統(tǒng)決策變量的一個(gè)數(shù)學(xué)函數(shù)來(lái)衡量系統(tǒng)的效率，即系統(tǒng)追求的目標(biāo)。22線(xiàn)性規(guī)劃(LP)非線(xiàn)性規(guī)劃(NLP)整數(shù)規(guī)劃(IP)主要內(nèi)容23線(xiàn)性規(guī)劃1、概念和實(shí)例。2、線(xiàn)性規(guī)劃模型3、線(xiàn)性規(guī)劃的性質(zhì)。4、線(xiàn)性規(guī)劃的主要算法。5、用數(shù)學(xué)軟件包求解線(xiàn)性規(guī)劃問(wèn)題6、建模案例選講：投資的收益與風(fēng)險(xiǎn)24線(xiàn)性規(guī)劃：就是一個(gè)線(xiàn)性函數(shù)在線(xiàn)性等式或不等式約束條件下的極值問(wèn)題。線(xiàn)性規(guī)劃

15、研究的問(wèn)題主要有兩類(lèi)： 1、任務(wù)確定后，如何統(tǒng)籌安排，盡量做到用盡量少的人力和物力資源來(lái)完成任務(wù)； 2、有一定量的人力、物力資源，如何安排使用他們，使完成的任務(wù)（創(chuàng)造的利潤(rùn)）最多。 在生產(chǎn)管理和經(jīng)濟(jì)活動(dòng)中經(jīng)常提出這樣一類(lèi)問(wèn)題， 即如何合理地利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果。25線(xiàn)性規(guī)劃的數(shù)學(xué)模型有三要素，從實(shí)際問(wèn)題提煉成數(shù)學(xué)模型時(shí)，首先尋找需求解的未知量xj (j=1,n)，然后列舉三要素： 列寫(xiě)與自變量（未知量）有關(guān)的若干個(gè)線(xiàn)性約束條件（等式或不等式）。列寫(xiě)自變量xj取值限制（xj0，xj0或不限）。列寫(xiě)關(guān)于自變量的線(xiàn)性目標(biāo)函數(shù)值（極大值或極小值）。其中，前兩條稱(chēng)為可

16、行條件，最后一條稱(chēng)為優(yōu)化條件。符合這三個(gè)條件的數(shù)學(xué)模型通常稱(chēng)為線(xiàn)性規(guī)劃的一般型（general）。 26例1：某廠每日8小時(shí)的產(chǎn)量不低于1800件。為了進(jìn)行質(zhì)量控制，計(jì)劃聘請(qǐng)兩種不同水平的檢驗(yàn)員。一級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級(jí)檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15小時(shí)/件，正確率95%，計(jì)時(shí)工資3元/小時(shí)。檢驗(yàn)員每錯(cuò)檢一次，工廠要損失2元。為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級(jí)、二級(jí)檢驗(yàn)員各幾名？解： 設(shè)需要一級(jí)和二級(jí)檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：因檢驗(yàn)員錯(cuò)檢而造成的損失為：27故目標(biāo)函數(shù)為：約束條件為：28線(xiàn)性規(guī)劃模型：29某車(chē)間有甲、乙兩

17、臺(tái)機(jī)床，可用于加工三種工件。假定這兩臺(tái)車(chē)床的可用臺(tái)時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車(chē)床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表。問(wèn)怎樣分配車(chē)床的加工任務(wù)，才能既滿(mǎn)足加工工件的要求，又使加工費(fèi)用最低？例2 ：任務(wù)分配問(wèn)題30 解： 設(shè)在甲車(chē)床上加工工件1、2、3的數(shù)量分別為x1、x2、x3， 在乙車(chē)床上加工工件1、2、3的數(shù)量分別為x4、x5、x6。 可建立以下線(xiàn)性規(guī)劃模型：31例3: 飲食問(wèn)題每人每天食用的食品中含有各種必需的營(yíng)養(yǎng)素，家庭主婦面臨著一種抉擇：如何采購(gòu)食品，才能在保證必需營(yíng)養(yǎng)素最低需求量前提下花錢(qián)最少？這是典型的線(xiàn)性規(guī)

18、劃問(wèn)題。設(shè)有n種食品供選擇，m種營(yíng)養(yǎng)素應(yīng)保證一定量。令： xj每天食用的j種食品數(shù)量 cj單位j種食品的價(jià)格 aij單位 j 種食品含有i種營(yíng)養(yǎng)素?cái)?shù)量 bi每天對(duì)營(yíng)養(yǎng)i的最低需求量32針對(duì)問(wèn)題特點(diǎn),可列寫(xiě)線(xiàn)性規(guī)劃數(shù)學(xué)模型如下： (最低營(yíng)養(yǎng)需求約束) (自變量約束，食品量不會(huì)為負(fù))(目標(biāo)函數(shù)，使購(gòu)食品費(fèi)用取最小值（i=1,2,m; j=1,2,n） 33例4: Chebyslev近似給出一組方程 其中，mn，希求一組近似解x1，x2, xn使誤差盡量小。即求出一組解，使之代入方程組中，造成不滿(mǎn)足約束的方程的最大誤差量盡量小。這是長(zhǎng)期以來(lái)被認(rèn)為必存在的這樣一個(gè)解而又很難找到解的問(wèn)題，然而用線(xiàn)性規(guī)劃

19、求解卻比較方便。下面就討論如何建立該問(wèn)題的線(xiàn)性規(guī)劃數(shù)學(xué)模型。 設(shè)：34則問(wèn)題變?yōu)榍蟪鲆唤M xj (j=1,2,n) 使盡量小，于是變?yōu)椋?即： 且令min 為統(tǒng)一標(biāo)志，令 x0，則上述問(wèn)題變?yōu)橄率鼍€(xiàn)形規(guī)劃問(wèn)題 ：35自變量約束：x00，xj不限（j=1,2,n）目標(biāo)函數(shù)：x0min36從上面例子中看出，列寫(xiě)線(xiàn)性規(guī)劃數(shù)學(xué)模型的關(guān)鍵步聚為：根據(jù)問(wèn)題性質(zhì)，找出需求解的變量，即自變量。根據(jù)問(wèn)題的限制因素或條件，列出自變量的取值限制及與自變量有關(guān)的線(xiàn)性約束條件（等式約束或不等式約束）。根據(jù)問(wèn)題的目標(biāo)要求，列出自變量有關(guān)的線(xiàn)性目標(biāo)函數(shù)（極大值或極小值）。37線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式：2. 線(xiàn)性規(guī)劃的模型線(xiàn)性規(guī)劃

20、的模型結(jié)構(gòu)：目標(biāo)函數(shù)：約束變量：變量符號(hào)：目標(biāo)函數(shù)：約束變量：變量符號(hào)：383. 線(xiàn)性規(guī)劃的性質(zhì)線(xiàn)性規(guī)劃的可行域是凸集線(xiàn)性規(guī)劃可能有解、無(wú)解或無(wú)有限的最優(yōu)解線(xiàn)性規(guī)劃的最優(yōu)解在極點(diǎn)(頂點(diǎn))上凸集：對(duì)區(qū)域D中的任意兩個(gè)元素 x, y 和人意的非負(fù)數(shù)0a 1,元素ax+(1-a)y也在區(qū)域D中。39 線(xiàn)性規(guī)劃是最優(yōu)化方法發(fā)展最迅速，成就最大的一個(gè)分支，線(xiàn)性規(guī)劃發(fā)展的爆炸時(shí)期是20世紀(jì)50年代至60年代，其奠基人應(yīng)是蘇聯(lián)數(shù)學(xué)家Cantolovch 和美國(guó)數(shù)學(xué)家G.B.Danfzig。 1947年Dantzig提出了轟動(dòng)數(shù)學(xué)界的單純形法，為求解多維線(xiàn)性規(guī)劃問(wèn)題提供了一般的有效的工具； 1950-1965

21、年匈牙利的兩位數(shù)學(xué)家H.W.Kuhn和A.W.Tucker建立了線(xiàn)性規(guī)劃的對(duì)偶理論，為求結(jié)鞍點(diǎn)問(wèn)題提供了數(shù)學(xué)工具，兩位年輕的數(shù)學(xué)家建立了約束極值的最優(yōu)形條件，稱(chēng)為K-T條件。為求解非線(xiàn)性規(guī)劃奠定了理論基礎(chǔ)；4. 線(xiàn)性規(guī)劃的算法401958年美國(guó)數(shù)學(xué)家R.E.Gomery提出整數(shù)規(guī)劃的割平面法；1960年Rantzig and P.Wolfe研究成功線(xiàn)性規(guī)劃的分解算法，該算法為求解大規(guī)模線(xiàn)性規(guī)劃提供了強(qiáng)有力的工具；1979年-1984年蘇聯(lián)數(shù)學(xué)家L.G.Khachiyan和美國(guó)數(shù)學(xué)家N.A.Karmarka先后提出并完成了線(xiàn)性規(guī)劃的多項(xiàng)式算法轟動(dòng)了整個(gè)數(shù)學(xué)界。41線(xiàn)性規(guī)劃的主要算法單純形法（19

22、47年美國(guó)Dantzig） 修正單純形法，對(duì)偶單純形法。非多項(xiàng)式時(shí)間方法，對(duì)中小規(guī)模問(wèn)題非常有效，應(yīng)用廣泛。橢球方法（1979年蘇聯(lián)L.G.Khachiyan） 多項(xiàng)式時(shí)間方法，理論價(jià)值高，不常用，效果不理想。 時(shí)間復(fù)雜度為Karmarkar方法（1984美國(guó)N.A.Karmarka ） 內(nèi)點(diǎn)方法，多項(xiàng)式時(shí)間方法，理論價(jià)值高，有效，時(shí)間復(fù)雜度為 ， 對(duì)大規(guī)模問(wèn)題也十分有效.42單純形法算法思想 從一個(gè)可行域的某個(gè)頂點(diǎn)出發(fā)（基本可行解）出發(fā)，轉(zhuǎn)換到另一個(gè)更好的頂點(diǎn)（使目標(biāo)函數(shù)值有所改善的基本可行解，通過(guò)不斷改進(jìn)基本可行解），最終達(dá)到目標(biāo)函數(shù)最優(yōu)的頂點(diǎn)(求得問(wèn)題的最優(yōu)解)。43 Karmarkar

23、內(nèi)點(diǎn)方法算法思想 通過(guò)射影變換把原問(wèn)題轉(zhuǎn)化為在球域上極小化另一個(gè)線(xiàn)性函數(shù)。求出問(wèn)題在球域上的最優(yōu)解后，再用逆變換將該解返回到原決策空間里去，從而得到原問(wèn)題的近似解。重復(fù)以上過(guò)程，得到的點(diǎn)列在多項(xiàng)式時(shí)間內(nèi)收斂于原問(wèn)題的最優(yōu)解.445. 求解線(xiàn)性規(guī)劃問(wèn)題的算法軟件Matlab 可以求解任意規(guī)模的線(xiàn)性規(guī)劃問(wèn)題。Lingo 可以求解任意規(guī)模的線(xiàn)性規(guī)劃問(wèn)題，特別是整數(shù)線(xiàn)性規(guī)劃問(wèn)題,但是不易得到功能強(qiáng)大的版本.45用MATLAB優(yōu)化工具箱解線(xiàn)性規(guī)劃 1、模型：命令：x=linprog(c，A，b) 2、模型：命令：x=linprog（c，A，b，Aeq,beq）注意：若沒(méi)有不等式： 存在，則令A(yù)= ，b=

24、 .463、模型： 命令：1 x=linprog(c，A，b，Aeq,beq, VLB，VUB)2 x=linprog(c，A，b，Aeq,beq, VLB，VUB, x0)注意：1 若沒(méi)有等式約束: , 則令A(yù)eq= , beq= .2 其中x0表示初始點(diǎn) 474、命令：x,fval=linprog()返回最優(yōu)解x及x處的目標(biāo)函數(shù)值fval.注意：在linprog函數(shù)中，其中有一選擇“l(fā)argescale”，如果命令為“on”，則表示利用大規(guī)模的線(xiàn)性規(guī)劃算法求解，如果命令為“off”，則表示利用中小規(guī)模的線(xiàn)性規(guī)劃算法求解。求解大規(guī)模的線(xiàn)性規(guī)劃利用的是Karmarkar內(nèi)點(diǎn)方法，求解中小規(guī)模的

25、線(xiàn)性規(guī)劃利用的是一種修正的單純形法48解 :編寫(xiě)M文件xxgh1.m如下： c= -0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A= 0.01 0.01 0.01 0.03 0.03 0.03; 0.02 0 0 0.05 0 0; 0 0.02 0 0 0.05 0; 0 0 0.03 0 0 0.08; b=850; 700; 100; 900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)49解: 編寫(xiě)M文件xxgh2.m如下： c=6 3 4; A=0 1 0;

26、b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)50S.t.改寫(xiě)為：例3 : 問(wèn)題一的解答51編寫(xiě)M文件xxgh3.m如下:f = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 800; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;x,fval = linprog(f,A,b,Aeq,beq,

27、vlb,vub)52結(jié)果:x =0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004即在甲機(jī)床上加工600個(gè)工件2,在乙機(jī)床上加工400個(gè)工件1、500個(gè)工件3，可在滿(mǎn)足條件的情況下使總加工費(fèi)最小為13800。53例4: 問(wèn)題二的解答改寫(xiě)為：54編寫(xiě)M文件xxgh4.m如下： c = 40;36; A=-5 -3; b=-45; Aeq=; beq=; vlb = zeros(2,1); vub=9;15; %調(diào)用linprog函數(shù)： x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)55結(jié)果為： x =9.0000 0.0000 fval =360即只需聘用9個(gè)一級(jí)檢驗(yàn)員。注：本問(wèn)題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù)。故它是一個(gè)整數(shù)線(xiàn)性規(guī)劃問(wèn)題。這里把它當(dāng)成一個(gè)線(xiàn)性規(guī)劃來(lái)解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解。若用線(xiàn)性規(guī)劃解法求得的最優(yōu)解不是整