數(shù)學(xué)建模優(yōu)化模型課件

數(shù)學(xué)建模-------優(yōu)化模型數(shù)學(xué)建模-------優(yōu)化模型第二講線性規(guī)劃建模方法第三講整數(shù)規(guī)劃建模方法第四講指派問(wèn)題第六講圖論簡(jiǎn)介第五講動(dòng)態(tài)規(guī)劃建模第一講數(shù)學(xué)建模概論第二講線性規(guī)劃建模方法第三講整數(shù)規(guī)劃建模方法第四講第一章數(shù)學(xué)建模概論1.1數(shù)學(xué)建模由來(lái)1.2從現(xiàn)實(shí)對(duì)象到數(shù)學(xué)模型1.3數(shù)學(xué)建模的重要意義1.4數(shù)學(xué)建模的方法和步驟1.5數(shù)學(xué)模型的特點(diǎn)和分類1.6近幾年國(guó)內(nèi)競(jìng)賽題1.7怎樣學(xué)習(xí)數(shù)學(xué)建模與競(jìng)賽組隊(duì)1.8撰寫(xiě)數(shù)學(xué)建模論文第一章數(shù)學(xué)建模概論1.1數(shù)學(xué)建模由來(lái)?1985年由美國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)和美國(guó)運(yùn)籌學(xué)會(huì)聯(lián)合主辦大學(xué)生數(shù)學(xué)建模競(jìng)賽（MCM)1.1數(shù)學(xué)建模由來(lái)?在上世紀(jì)70年代末和80年代初，英國(guó)著名的劍橋大學(xué)專門(mén)為研究生開(kāi)設(shè)了數(shù)學(xué)建模課程

?數(shù)學(xué)建模作為一門(mén)嶄新的課程在20世紀(jì)80年代進(jìn)入我國(guó)高校，蕭樹(shù)鐵先生1983年在清華大學(xué)首次為本科生講授數(shù)學(xué)模型課程，他是我國(guó)高校開(kāi)設(shè)數(shù)學(xué)模型課程的創(chuàng)始人?1985年由美國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)和美國(guó)運(yùn)籌?1992年由中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)舉辦全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽（94年起由國(guó)家教委高教司和中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)共同舉辦）?1987年由姜啟源教授編寫(xiě)了我國(guó)第一本數(shù)學(xué)建模教材?2005年全國(guó)數(shù)學(xué)建模競(jìng)賽，共有來(lái)自全國(guó)30個(gè)省、市、自治區(qū)的795所高校8492支隊(duì)（其中甲組6556隊(duì)、乙組1936隊(duì)）、25476名來(lái)自各個(gè)專業(yè)的大學(xué)生參加本次競(jìng)賽?1992年由中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)舉辦全國(guó)大?

95年我校參加全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽，最初開(kāi)設(shè)選修課是因?yàn)閰⒓訑?shù)學(xué)建模競(jìng)賽的需要，選修的學(xué)生數(shù)較少，而且必須是往年成績(jī)較優(yōu)的學(xué)生才允許選修

?

97年學(xué)校決定在原有基礎(chǔ)上，在部分專業(yè)開(kāi)設(shè)數(shù)學(xué)建模必修課，并同時(shí)對(duì)其他專業(yè)開(kāi)設(shè)數(shù)學(xué)建模選修課

?2000年起結(jié)合課程教學(xué)與競(jìng)賽安排，在每年五月底或六月初舉辦全校大學(xué)生數(shù)學(xué)建模競(jìng)賽

?近兩年數(shù)學(xué)建模課程每年選課人數(shù)2000余人?95年我校參加全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽，最初開(kāi)設(shè)選修課是因?1995-2009年學(xué)生參加全國(guó)大學(xué)生數(shù)學(xué)建模竟賽及獲獎(jiǎng)情況：

年份參賽全國(guó)全國(guó)省一等獎(jiǎng)省二等獎(jiǎng)省三等獎(jiǎng)隊(duì)數(shù)一等獎(jiǎng)二等獎(jiǎng)19953111119964111119977222111998742611999712312000101332200110213220021512351200315233362004161324422413832819302532373318

?1995-2009年學(xué)生參加全國(guó)大學(xué)生數(shù)學(xué)建模竟賽及獲獎(jiǎng)2006年獲一等獎(jiǎng)1隊(duì)，二等獎(jiǎng)3隊(duì)2007年獲一等獎(jiǎng)1隊(duì)，二等獎(jiǎng)5隊(duì)2008年獲一等獎(jiǎng)4隊(duì)，二等獎(jiǎng)4隊(duì)2009年獲一等獎(jiǎng)2隊(duì)，二等獎(jiǎng)2隊(duì)

?2006-2009年學(xué)生參加美國(guó)大學(xué)生數(shù)學(xué)建模竟賽及獲獎(jiǎng)情況：

2006年獲一等獎(jiǎng)1隊(duì)，二等獎(jiǎng)3隊(duì)?2006-2009年玩具、照片、飛機(jī)、火箭模型……~實(shí)物模型地圖、電路圖、分子結(jié)構(gòu)圖……~符號(hào)模型模型是為了一定目的，對(duì)客觀事物的一部分進(jìn)行簡(jiǎn)縮、抽象、提煉出來(lái)的原型的替代物模型集中反映了原型中人們需要的那一部分特征1.2

從現(xiàn)實(shí)對(duì)象到數(shù)學(xué)模型我們常見(jiàn)的模型玩具、照片、飛機(jī)、火箭模型……~實(shí)物模型地圖、電路圖、分你碰到過(guò)的數(shù)學(xué)模型——“航行問(wèn)題”用x

表示船速，y表示水速，列出方程：答：船速每小時(shí)20千米/小時(shí).甲乙兩地相距750千米，船從甲到乙順?biāo)叫行?0小時(shí)，從乙到甲逆水航行需50小時(shí)，問(wèn)船的速度是多少?x=20y=5求解你碰到過(guò)的數(shù)學(xué)模型——“航行問(wèn)題”用x表示船速，y表示航行問(wèn)題建立數(shù)學(xué)模型的基本步驟

作出簡(jiǎn)化假設(shè)（船速、水速為常數(shù)）；

用符號(hào)表示有關(guān)量（x,y表示船速和水速）；

用物理定律（勻速運(yùn)動(dòng)的距離等于速度乘以時(shí)間）列出數(shù)學(xué)式子（二元一次方程）；

求解得到數(shù)學(xué)解答（x=20,y=5）；

回答原問(wèn)題（船速每小時(shí)20千米/小時(shí)）。航行問(wèn)題建立數(shù)學(xué)模型的基本步驟作出簡(jiǎn)化假設(shè)（船速、水速為常數(shù)學(xué)模型(MathematicalModel)和數(shù)學(xué)建模（MathematicalModeling)對(duì)于一個(gè)現(xiàn)實(shí)對(duì)象，為了一個(gè)特定目的，根據(jù)其內(nèi)在規(guī)律，作出必要的簡(jiǎn)化假設(shè)，運(yùn)用適當(dāng)?shù)臄?shù)學(xué)工具，得到的一個(gè)數(shù)學(xué)結(jié)構(gòu)。建立數(shù)學(xué)模型的全過(guò)程（包括表述、求解、解釋、檢驗(yàn)等）數(shù)學(xué)模型數(shù)學(xué)建模數(shù)學(xué)模型(MathematicalModel)和對(duì)于一1.3

數(shù)學(xué)建模的重要意義

電子計(jì)算機(jī)的出現(xiàn)及飛速發(fā)展；

數(shù)學(xué)以空前的廣度和深度向一切領(lǐng)域滲透。數(shù)學(xué)建模作為用數(shù)學(xué)方法解決實(shí)際問(wèn)題的第一步，越來(lái)越受到人們的重視。

在一般工程技術(shù)領(lǐng)域數(shù)學(xué)建模仍然大有用武之地；

在高新技術(shù)領(lǐng)域數(shù)學(xué)建模幾乎是必不可少的工具；

數(shù)學(xué)進(jìn)入一些新領(lǐng)域，為數(shù)學(xué)建模開(kāi)辟了許多處女地。1.3數(shù)學(xué)建模的重要意義電子計(jì)算機(jī)的出現(xiàn)及飛速發(fā)展；數(shù)學(xué)建模的具體應(yīng)用

分析與設(shè)計(jì)

預(yù)報(bào)與決策

控制與優(yōu)化

規(guī)劃與管理數(shù)學(xué)建模計(jì)算機(jī)技術(shù)知識(shí)經(jīng)濟(jì)如虎添翼數(shù)學(xué)建模的具體應(yīng)用分析與設(shè)計(jì)預(yù)報(bào)與決策控制與優(yōu)化規(guī)

數(shù)學(xué)建模的基本方法機(jī)理分析測(cè)試分析根據(jù)對(duì)客觀事物特性的認(rèn)識(shí)，找出反映內(nèi)部機(jī)理的數(shù)量規(guī)律將對(duì)象看作“黑箱”,通過(guò)對(duì)量測(cè)數(shù)據(jù)的統(tǒng)計(jì)分析，找出與數(shù)據(jù)擬合最好的模型機(jī)理分析沒(méi)有統(tǒng)一的方法，主要通過(guò)實(shí)例研究(CaseStudies)來(lái)學(xué)習(xí)。以下建模主要指機(jī)理分析。二者結(jié)合用機(jī)理分析建立模型結(jié)構(gòu),用測(cè)試分析確定模型參數(shù)1.4

數(shù)學(xué)建模的方法和步驟數(shù)學(xué)建模的基本方法機(jī)理分析測(cè)試分析根據(jù)對(duì)客觀事物特性的認(rèn)識(shí)

數(shù)學(xué)建模的一般步驟模型準(zhǔn)備模型假設(shè)模型構(gòu)成模型求解模型分析模型檢驗(yàn)?zāi)Ｐ蛻?yīng)用模型準(zhǔn)備了解實(shí)際背景明確建模目的搜集有關(guān)信息掌握對(duì)象特征形成一個(gè)比較清晰的‘問(wèn)題’數(shù)學(xué)建模的一般步驟模型準(zhǔn)備模型假設(shè)模型構(gòu)成模型求解模型分析模型假設(shè)針對(duì)問(wèn)題特點(diǎn)和建模目的作出合理的、簡(jiǎn)化的假設(shè)在合理與簡(jiǎn)化之間作出折中模型構(gòu)成用數(shù)學(xué)的語(yǔ)言、符號(hào)描述問(wèn)題發(fā)揮想像力使用類比法盡量采用簡(jiǎn)單的數(shù)學(xué)工具

數(shù)學(xué)建模的一般步驟模針對(duì)問(wèn)題特點(diǎn)和建模目的作出合理的、簡(jiǎn)化的假設(shè)在合理與簡(jiǎn)化之模型求解各種數(shù)學(xué)方法、軟件和計(jì)算機(jī)技術(shù)如結(jié)果的誤差分析、統(tǒng)計(jì)分析、模型對(duì)數(shù)據(jù)的穩(wěn)定性分析模型分析模型檢驗(yàn)與實(shí)際現(xiàn)象、數(shù)據(jù)比較，檢驗(yàn)?zāi)Ｐ偷暮侠硇?、適用性模型應(yīng)用

數(shù)學(xué)建模的一般步驟模型各種數(shù)學(xué)方法、軟件和計(jì)算機(jī)技術(shù)如結(jié)果的誤差分析、統(tǒng)計(jì)分析數(shù)學(xué)建模的全過(guò)程現(xiàn)實(shí)對(duì)象的信息數(shù)學(xué)模型現(xiàn)實(shí)對(duì)象的解答數(shù)學(xué)模型的解答表述求解解釋驗(yàn)證(歸納)(演繹)表述求解解釋驗(yàn)證根據(jù)建模目的和信息將實(shí)際問(wèn)題“翻譯”成數(shù)學(xué)問(wèn)題選擇適當(dāng)?shù)臄?shù)學(xué)方法求得數(shù)學(xué)模型的解答將數(shù)學(xué)語(yǔ)言表述的解答“翻譯”回實(shí)際對(duì)象用現(xiàn)實(shí)對(duì)象的信息檢驗(yàn)得到的解答實(shí)踐現(xiàn)實(shí)世界數(shù)學(xué)世界理論實(shí)踐數(shù)學(xué)建模的全過(guò)程現(xiàn)實(shí)對(duì)象的信息數(shù)學(xué)模型現(xiàn)實(shí)對(duì)象的解答數(shù)學(xué)模型1.5

數(shù)學(xué)模型的特點(diǎn)和分類模型的逼真性和可行性模型的漸進(jìn)性模型的穩(wěn)定性模型的可轉(zhuǎn)移性模型的非預(yù)制性模型的條理性模型的技藝性模型的局限性

數(shù)學(xué)模型的特點(diǎn)1.5數(shù)學(xué)模型的特點(diǎn)和分類模型的逼真性和可行性模型的漸進(jìn)數(shù)學(xué)模型的分類應(yīng)用領(lǐng)域人口、交通、經(jīng)濟(jì)、生態(tài)……數(shù)學(xué)方法初等數(shù)學(xué)、微分方程、規(guī)劃、統(tǒng)計(jì)……表現(xiàn)特性描述、優(yōu)化、預(yù)報(bào)、決策……建模目的了解程度白箱灰箱黑箱確定和隨機(jī)靜態(tài)和動(dòng)態(tài)線性和非線性離散和連續(xù)數(shù)學(xué)模型的分類應(yīng)用領(lǐng)域人口、交通、經(jīng)濟(jì)、生態(tài)……數(shù)學(xué)方法1.6近幾年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題1.6近幾年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題數(shù)學(xué)建模優(yōu)化模型ppt課件數(shù)學(xué)建模優(yōu)化模型ppt課件數(shù)學(xué)建模優(yōu)化模型ppt課件數(shù)學(xué)建模優(yōu)化模型ppt課件1.7怎樣學(xué)習(xí)數(shù)學(xué)建模與競(jìng)賽組隊(duì)數(shù)學(xué)建模與其說(shuō)是一門(mén)技術(shù)，不如說(shuō)是一門(mén)藝術(shù)技術(shù)大致有章可循藝術(shù)無(wú)法歸納成普遍適用的準(zhǔn)則想像力洞察力判斷力

學(xué)習(xí)、分析、評(píng)價(jià)、改進(jìn)別人作過(guò)的模型

親自動(dòng)手，認(rèn)真作幾個(gè)實(shí)際題目1.7怎樣學(xué)習(xí)數(shù)學(xué)建模與競(jìng)賽組隊(duì)數(shù)學(xué)建模與其說(shuō)是一門(mén)根據(jù)數(shù)學(xué)建模競(jìng)賽章程，三人組成一隊(duì)。

這三人中必須一人數(shù)學(xué)基礎(chǔ)較好，

一人應(yīng)用數(shù)學(xué)軟件（如Matlab,lindo,maple等）和編程（如c,Matlab,vc++等）的能力較強(qiáng)，

一人科技論文寫(xiě)作的水平較好。

?科技論文的寫(xiě)作要求整篇論文的結(jié)構(gòu)嚴(yán)謹(jǐn)，語(yǔ)言要有邏輯性，用詞要準(zhǔn)確。

?

三人之間要能夠配合得起來(lái)。若三人之間配合不好，會(huì)降低效率，導(dǎo)致整個(gè)建模的失敗。根據(jù)數(shù)學(xué)建模競(jìng)賽章程，三人組成一隊(duì)。這三人中必須一人數(shù)?

如果可能的話，最好是數(shù)學(xué)好的懂得編程的一些知識(shí)，編程好的了解建模，搞論文寫(xiě)作也要了解建模，這樣會(huì)合作得更好。因?yàn)閿?shù)學(xué)好的在建立模型方案時(shí)會(huì)考慮到編程的便利性，以利于編程；編程好的能夠很好地理解模型，論文寫(xiě)作的能夠更好、更完全地闡述模型。否則會(huì)出現(xiàn)建立的模型不利于編程，程序不能完全概括模型，論文寫(xiě)作時(shí)會(huì)漏掉一些不經(jīng)意的東西。?在合作的過(guò)程中，最好是能夠在三人中找出一個(gè)所謂的組長(zhǎng)，即要能夠總攬全局，包括任務(wù)的分配，相互間的合作和進(jìn)度的安排。?如果可能的話，最好是數(shù)學(xué)好的懂得編程的一些知識(shí)，編程好的?在建模過(guò)程中出現(xiàn)意見(jiàn)不統(tǒng)一——如何處理？?jī)H我個(gè)人的經(jīng)驗(yàn)而言，除了一般的理解與尊重外，我覺(jué)得最重要的一點(diǎn)就是“給我一個(gè)相信你的理由”和“相信我，我的理由是……”，不要作無(wú)謂的爭(zhēng)論。

?在建模過(guò)程中出現(xiàn)意見(jiàn)不統(tǒng)一——如何處理？?jī)H我個(gè)人的經(jīng)驗(yàn)而言1.8撰寫(xiě)數(shù)學(xué)建模論文1、摘要:問(wèn)題、模型、方法、結(jié)果2、問(wèn)題重述3、模型假設(shè)與記號(hào)4、分析與建立模型5、模型求解6、模型檢驗(yàn)7、模型推廣8、參考文獻(xiàn)9、附錄1.8撰寫(xiě)數(shù)學(xué)建模論文1、摘要:問(wèn)題、模型、方法、第二講線性規(guī)劃建模方法一、從現(xiàn)實(shí)問(wèn)題到線性規(guī)劃模型二、線性規(guī)劃模型的求解三、線性規(guī)劃建模實(shí)例四、線性規(guī)劃的對(duì)偶問(wèn)題第二講線性規(guī)劃建模方法一、從現(xiàn)實(shí)問(wèn)題到線性規(guī)劃模型二、線例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時(shí)間480小時(shí)至多加工100公斤A1

制訂生產(chǎn)計(jì)劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?

可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？每天:一、從現(xiàn)實(shí)問(wèn)題到線性規(guī)劃模型例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶3公斤A112小1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

線性規(guī)劃模型(LP)時(shí)間480小時(shí)至多加工100公斤A1

50桶牛奶每天1桶牛奶3公斤A112小時(shí)8小時(shí)4公斤A2或獲利2模型分析與假設(shè)

比例性可加性連續(xù)性xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比xi對(duì)約束條件的“貢獻(xiàn)”與xi取值成正比xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無(wú)關(guān)xi對(duì)約束條件的“貢獻(xiàn)”與xj取值無(wú)關(guān)xi取值連續(xù)A1,A2每公斤的獲利是與各自產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)線性規(guī)劃模型模型分析與假設(shè)比例性可加性連續(xù)性xi對(duì)目標(biāo)函數(shù)的“貢A1A2現(xiàn)有資源設(shè)備128臺(tái)時(shí)甲4016公斤乙0412公斤利潤(rùn)2030（元）制訂生產(chǎn)計(jì)劃,使每天獲利最大例2工廠生產(chǎn)兩種產(chǎn)品A1,A2,已知生產(chǎn)單位產(chǎn)品情況如表：設(shè)生產(chǎn)A1、A2分別x1、x2公斤

maxz=20x1+30x2(1)目標(biāo)函數(shù)約束條件決策變量一、從現(xiàn)實(shí)問(wèn)題到線性規(guī)劃模型A1A2現(xiàn)有資源設(shè)備128臺(tái)時(shí)甲4016公斤乙0412公斤線性規(guī)劃模型標(biāo)準(zhǔn)型:maxz=c1x1+c2x2+…+cnxn(LP)線性規(guī)劃模型標(biāo)準(zhǔn)型矩陣表示：maxz=c

x

max(min)z=c1x1+c2x2+…+cnxn線性規(guī)劃模型一般形式：線性規(guī)劃模型標(biāo)準(zhǔn)型:maxz=c1x1+c2x2+…1.線性規(guī)劃的一般形化為標(biāo)準(zhǔn)型一般步驟(1)Minz=cx轉(zhuǎn)化為maxz’=-cx(2)加松弛變量yi

(3)加剩余變量yi(4)若存在可正可負(fù)變量xi

令1.線性規(guī)劃的一般形化為標(biāo)準(zhǔn)型(1)Minz=cx

maxz=20x1+30x2(1)標(biāo)準(zhǔn)型(1),

x1+2x2+x3=8(2),4

x1+0

x2+x4=16(3),0x1+4x2+x5=12

maxz=20x1+30x2

x1+2x2+x3=84

x1+0

x2+x4=160x1+4x2+x5=12x1,x2,x3,x4,x5s.tmaxz=20x1+30x2(1)標(biāo)準(zhǔn)型(1)例將下述線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型Minz=-

x1+2x2-3x3無(wú)約束標(biāo)準(zhǔn)型maxz’=

x1-2x2+3(x4–x5)+0x6+0x7(1),x3=

x4-x5,x4,x5(2),

x1+x2+x3+x6=7(3),

x1-x2+x3-x7=2例將下述線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型Minz=-x1+合理下料問(wèn)題有長(zhǎng)度為8米的某型號(hào)圓鋼，現(xiàn)需要長(zhǎng)度為2.5米的毛坯100根，長(zhǎng)度為1.3米的毛坯200根，如何選者下料方式，所需總用料最省？解：可能的下料方式：2.51.3130222314406設(shè)按第i種下料方式的圓鋼xi根，i=1,2,3,4

minz=x1+x2+x3+x4有一組決策變量,約束條件是決策變量的線性等式或不等式,目標(biāo)函數(shù)是決策變量的線性函數(shù),這樣的規(guī)劃問(wèn)題稱為線性規(guī)劃.記為（LP）合理下料問(wèn)題有長(zhǎng)度為8米的某型號(hào)圓鋼，現(xiàn)需要長(zhǎng)度為2.5米的例.某小區(qū)一個(gè)24小時(shí)營(yíng)業(yè)便利店,一天各時(shí)段所需服務(wù)員最少人數(shù)如下表.根據(jù)實(shí)際情況,要求每個(gè)服務(wù)員必須連續(xù)工作八小時(shí),試建立需服務(wù)員總?cè)藬?shù)最少的排班方案數(shù)學(xué)模型.班次123456時(shí)間2-66-1010-1414-1818-2222-2人48107124解：設(shè)各班次新增服務(wù)員數(shù)分別為x1,x2,x3,x4,x5,x6,則minz=

x1+x2+x3+x4+x5+x6且xi為整數(shù)例.某小區(qū)一個(gè)24小時(shí)營(yíng)業(yè)便利店,一天各時(shí)段所需服務(wù)員最少人連續(xù)投資問(wèn)題某部門(mén)計(jì)劃5年內(nèi)用一百萬(wàn)投資下列項(xiàng)目：A：從第一年到第四年初需投資，此年末回收本利115%B:第三年初需投資，第五年末回收本利125%，投資額≤40萬(wàn)C:第二年初需投資，第五年末回收本利140%，投資額≤30萬(wàn)D：每年初可購(gòu)買公債，當(dāng)年末歸還，利息6%如何投資，五年后獲利最大？解：設(shè)第i年初投資項(xiàng)目A,B,C,D分別為xiA,xiB,xiC,

xiD萬(wàn)元,i=1,2,3,4,5x1A+x1D=100,x2A+x2C+x2D=1.06x1D,x3A+x3B+x3D=1.06x2D+1.15

x1A,x4A+x4D=1.06x3D+1.15

x2A,x5D=1.06x4D+1.15

x3A,x2C≤40,x3B≤30,xiA,xiB,xiC,

xiD≥0i=1,2,3,4,5.MaxZ=1.15x4A+1.40x2C+1.25x3B+1.06x5Ds.t.連續(xù)投資問(wèn)題某部門(mén)計(jì)劃5年內(nèi)用一百萬(wàn)投資下列項(xiàng)目：解：設(shè)第i二、線性規(guī)劃模型的求解（一）圖解法（n<=3時(shí)）（二）單純形法（三）數(shù)學(xué)軟件：如LINDO軟件二、線性規(guī)劃模型的求解（一）圖解法（n<=3時(shí)）（二）單純形maxz=c

x(LP)可行解：滿足約束條件AX=b,X最優(yōu)解:可行解中使目標(biāo)最優(yōu)的。即X*∈D,且任意X∈D,CX*≥CX可行集：所有可行解的集合的X的值maxz=cx(LP)可行解：滿足約束條件AX=b,XA1A2現(xiàn)有資源設(shè)備128臺(tái)時(shí)甲4016公斤乙0412公斤利潤(rùn)2030（元）制訂生產(chǎn)計(jì)劃,使每天獲利最大工廠生產(chǎn)兩種產(chǎn)品A1,A2,已知生產(chǎn)單位產(chǎn)品情況如下：設(shè)生產(chǎn)A1、A2分別x1、x2公斤

maxz=20x1+30x2(1)A1A2現(xiàn)有資源設(shè)備128臺(tái)時(shí)甲4016公斤乙0412公斤（一）圖解法（n<=3時(shí)）(1)在平面上作出可行集ABCD34Z=60Z=140Z=0由圖解法直觀得:n=2時(shí),(LP)的可行集是凸多邊形,最優(yōu)解可以在其某個(gè)頂點(diǎn)處達(dá)到.線性規(guī)劃基本性質(zhì):(LP)的可行集是凸多面體,最優(yōu)解可以在凸多面體的某個(gè)頂點(diǎn)處達(dá)到.線性規(guī)劃求解思路:通過(guò)代數(shù)的方法描述高維空間凸多面體的頂點(diǎn),再使用經(jīng)濟(jì)的方法來(lái)求出達(dá)到極值的頂點(diǎn).x1x20(2)在可行集中找最優(yōu)解

maxz=20x1+30x2(1)（一）圖解法（n<=3時(shí)）(1)在平面上作出可行集ABCD3（二）單純形法1.基、基本可行解的概念(頂點(diǎn)的代數(shù)描述)2.單純形法一般步驟（二）單純形法1.基、基本可行解的概念(頂點(diǎn)的代數(shù)描述)2.引入松弛變量x3,x4,x5,化為標(biāo)準(zhǔn)形:引入松弛變量x3,x4,x5,化為標(biāo)準(zhǔn)形:顯然A的秩為3,任取3個(gè)線性無(wú)關(guān)的列向量,如P1,P2,

P3稱為一組基,記為B=(P1,P2,

P3)。P1,P2,

P3

稱為基向量,

基向量對(duì)應(yīng)的變量x1,x2,x3稱為基變量,其余列向量

P4,

P5

稱為非基向量,

記為N=(P4,

P5).非基對(duì)應(yīng)的變量x4,x5稱為非基變量.A=(B,N),相應(yīng)x=(xB,xN)T,c=(cB,cN)令非基變量xN

=0,解得基變量xB=B-1b,稱(xB,xN)為基解.Ax=BxB+NxN=b,則xB=B-1b-B-1NxN,解的所有變量的值都非負(fù)，則稱為基可行解，此時(shí)的基稱為可行基.顯然A的秩為3,任取3個(gè)線性無(wú)關(guān)的列向量,如P1,P2于是f=cBxB+cNxN,Ax=BxB+NxN=b,

則xB=B-1b-B-1NxN,f=cBB-1b+(cN–cBB-1N)xN

將A寫(xiě)成A=(B,N),相應(yīng)x=(xB,xN)T,c=(cB,cN)基對(duì)應(yīng)的變量xB稱為基變量,非基對(duì)應(yīng)的變量xN稱為非基變量.令非基變量xN=0,解得基變量xB=B-1b,稱(xB,xN)為基解.解的所有變量的值都非負(fù)，則稱為基可行解，此時(shí)的基稱為可行基.基可行解對(duì)應(yīng)的目標(biāo)值為f=cBB-1b。

若可行基進(jìn)一步滿足:cN–cBB-1N≥0,則對(duì)一切可行解x,必有f(x)≥cBB-1b,此時(shí)稱基可行解x=(B-1b,0)T為最優(yōu)解.于是f=cBxB+cNxN,Ax=另一個(gè)基本可行解定理：(LP)的可行集的頂點(diǎn)與(LP)的

基本可行解一一對(duì)應(yīng)。單純形法基本思想：目標(biāo)重復(fù)此更優(yōu)過(guò)程單純形法基本步驟：不是最優(yōu)解更優(yōu)目標(biāo)重復(fù)此過(guò)程(LP)的某個(gè)基本可行解最優(yōu)解(LP)的某個(gè)基基可行解另一個(gè)基基本可行解最優(yōu)解另一個(gè)基定理：(LP)的可行集的頂點(diǎn)與(LP)的單純形法4.基可行解是最優(yōu)解的判定準(zhǔn)則因?yàn)閒=cBB-1b+(cN–cBB-1N)xN，即f-0?xB+(cBB-1N-cN)xN=cBB-1b4.基可行解是最優(yōu)解的判定準(zhǔn)則因?yàn)閒=cBB-1b5.基可行解的改進(jìn)5.基可行解的改進(jìn)改進(jìn)方法：返回改進(jìn)方法：返回Maxz=2x1+3x2+x3解:本題特點(diǎn)是約束方程系數(shù)矩陣含單位子矩陣1111014701

A=()1001

B0=(P4,P5))=(X0=(0,0,0,3,9)TZ0=8Maxz=2x1+3x2+x3A1A2利潤(rùn)甲112乙143丙174資源39Max{2,3,1}=3x2進(jìn)基x4=3-x1-x2-x3x5=9-x1-4x2-7x3=3-x2=9-4x2x5出基Min{3/1,9/4}=9/4)(14→)(01初等行變換111103147019

A=()→1111031/417/401/49/4

)(→3/40–3/41–1/43/41/417/401/49/4

)(B1=(P4,P2))=(1001

Maxz=2x1+3x2+x3解:本題特點(diǎn)是約束一、單純形法的基本思想

1、頂點(diǎn)的逐步轉(zhuǎn)移

即從可行域的一個(gè)頂點(diǎn)（基本可行解）開(kāi)始，轉(zhuǎn)移到另一個(gè)頂點(diǎn)（另一個(gè)基本可行解）的迭代過(guò)程，轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí)，問(wèn)題也就得到了最優(yōu)解。一、單純形法的基本思想

1、頂點(diǎn)的逐步轉(zhuǎn)移即

根據(jù)線性規(guī)劃問(wèn)題的可行域是凸多邊形或凸多面體，一個(gè)線性規(guī)劃問(wèn)題有最優(yōu)解，就一定可以在可行域的頂點(diǎn)上找到。

于是，若某線性規(guī)劃只有唯一的一個(gè)最優(yōu)解，這個(gè)最優(yōu)解所對(duì)應(yīng)的點(diǎn)一定是可行域的一個(gè)頂點(diǎn)；若該線性規(guī)劃有多個(gè)最優(yōu)解，那么肯定在可行域的頂點(diǎn)中可以找到至少一個(gè)最優(yōu)解。頂點(diǎn)轉(zhuǎn)移的依據(jù)？根據(jù)線性規(guī)劃問(wèn)題的可行域是凸多邊形或凸多面體

轉(zhuǎn)移條件？轉(zhuǎn)移結(jié)果？使目標(biāo)函數(shù)值得到改善得到LP最優(yōu)解，目標(biāo)函數(shù)達(dá)到最優(yōu)值（單純形法的由來(lái)？）

2．需要解決的問(wèn)題：

(1)為了使目標(biāo)函數(shù)逐步變優(yōu)，怎麼轉(zhuǎn)移？

(2)目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)——

判斷標(biāo)準(zhǔn)是什麼？

轉(zhuǎn)移條件？二、單純形法原理（用代數(shù)方法求解LP）勞動(dòng)力原材料利潤(rùn)A112B143C173現(xiàn)有資源39例1二、單純形法原理（用代數(shù)方法求解LP）勞動(dòng)力原材料利潤(rùn)A11第一步：引入非負(fù)的松弛變量x4,x5,將該LP化為標(biāo)準(zhǔn)型第一步：引入非負(fù)的松弛變量x4,x5,將該LP化為標(biāo)準(zhǔn)型第二步：尋求初始可行基，確定基變量對(duì)應(yīng)的基變量是x4，x5；

第三步：寫(xiě)出初始基本可行解和相應(yīng)的目標(biāo)函數(shù)值第二步：尋求初始可行基，確定基變量對(duì)應(yīng)的基變量是x兩個(gè)關(guān)鍵的基本表達(dá)式：①用非基變量表示基變量的表達(dá)式兩個(gè)關(guān)鍵的基本表達(dá)式：②用非基變量表示目標(biāo)函數(shù)的11111表達(dá)式請(qǐng)解釋結(jié)果的經(jīng)濟(jì)含義——不生產(chǎn)任何產(chǎn)品，資源全部節(jié)余（x4=3，x5=9），三種產(chǎn)品的總利潤(rùn)為0?、谟梅腔兞勘硎灸繕?biāo)函數(shù)的11111表達(dá)式請(qǐng)解釋結(jié)果的經(jīng)濟(jì)含第四步：分析兩個(gè)基本表達(dá)式，看看目標(biāo)函數(shù)是否可以改善？①分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式

非基變量前面的系數(shù)均為正數(shù)，所以任何一個(gè)非基變量進(jìn)基都能使Z值增加通常把非基變量前面的系數(shù)叫“檢驗(yàn)數(shù)”；第四步：分析兩個(gè)基本表達(dá)式，看看目標(biāo)函數(shù)是否可以改善？①②選哪一個(gè)非基變量進(jìn)基？

選x2為進(jìn)基變量（換入變量）問(wèn)題：能否選其他的非基變量進(jìn)基？

任意一個(gè)

任意一個(gè)正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量

最大正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量

排在最前面的正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量×

②選哪一個(gè)非基變量進(jìn)基？任意一個(gè)×③確定出基變量：?jiǎn)栴}討論

x2進(jìn)基意味著其取值從0變成一個(gè)正數(shù)（經(jīng)濟(jì)意義——生產(chǎn)B產(chǎn)品），能否無(wú)限增大？

當(dāng)x2增加時(shí)，x4，x5如何變化？

現(xiàn)在的非基變量是哪些？

具體如何確定換出變量？③確定出基變量：x2進(jìn)基意味著其取值從0變成一個(gè)正數(shù)（由用非基變量表示基變量的表達(dá)式

當(dāng)x2增加時(shí)，x4，x5會(huì)減小，但有限度——必須大于等于0，以保持解的可行性！于是由用非基變量表示基變量的表達(dá)式當(dāng)x2增加時(shí)，x4，x5會(huì)減

當(dāng)x2的值從0增加到9/4時(shí)，x5首先變?yōu)?，此時(shí)x4=3/4>0因此選x5為出基變量（換出變量）。這種用來(lái)確定出基變量的規(guī)則稱為“最小比值原則”（或θ原則）。如果P1≤0，會(huì)出現(xiàn)什麼問(wèn)題？

最小比值原則會(huì)失效！當(dāng)x2的值從0增加到9/4時(shí)，x5首先變?yōu)?，此時(shí)

基變換新的基變量——x2,x4；新的非基變量x1,x3,x5；寫(xiě)出用非基變量表示基變量的表達(dá)式：可得新的基本可行解

X（1）=（0，9/4，0，3/4，0）T由基變換可得新的基本可行解由⑤寫(xiě)出用非基變量表示目標(biāo)函數(shù)的表達(dá)式:可得相應(yīng)的目標(biāo)函數(shù)值為Z（1）=27/4檢驗(yàn)數(shù)仍有正的返回①進(jìn)行討論。⑤寫(xiě)出用非基變量表示目標(biāo)函數(shù)的表達(dá)式:可得相應(yīng)的目標(biāo)函數(shù)值第五步：上述過(guò)程何時(shí)停止？當(dāng)用非基變量表示目標(biāo)函數(shù)的表達(dá)式中，非基變量的系數(shù)（檢驗(yàn)數(shù)）全部非正時(shí)，當(dāng)前的基本可行解就是最優(yōu)解!

為什麼？——分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式，如果讓負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的變量進(jìn)基，目標(biāo)函數(shù)值將下降！第五步：上述過(guò)程何時(shí)停止？——分析用非基變量表示目標(biāo)函數(shù)的表三、表格單純形法：

1、

初始單純形表的建立

(1)表格結(jié)構(gòu)：

x1x2x3

x4x523300z11110147013x49x523300z三、表格單純形法：x1x2x3（2）表格設(shè)計(jì)依據(jù)：把目標(biāo)函數(shù)表達(dá)式改寫(xiě)成方程的形式，和原有的m個(gè)約束方程組成一個(gè)具有n+m+1個(gè)變量、m+1個(gè)方程的方程組：（2）表格設(shè)計(jì)依據(jù)：取出系數(shù)寫(xiě)成增廣矩陣的形式：

Xn+1，…，Xn+m所對(duì)應(yīng)的系數(shù)列向量構(gòu)成一個(gè)基取出系數(shù)寫(xiě)成增廣矩陣的形式：Xn+1，…，Xn+m所對(duì)應(yīng)的用矩陣的初等行變換將目標(biāo)函數(shù)中基變量系數(shù)化為零,這時(shí)變成0，相應(yīng)的增廣矩陣變成如下形式：其中，，j=1，2，…，n；

用矩陣的初等行變換將目標(biāo)函數(shù)中基變量系數(shù)化為零,這時(shí)（3）檢驗(yàn)數(shù)的兩種計(jì)算方法：①利用矩陣的行變換，把目標(biāo)函數(shù)表達(dá)式中基變量前面的系數(shù)變?yōu)?；②使用計(jì)算公式——

增廣矩陣的最后一行就是用非基變量表示目標(biāo)函數(shù)的表達(dá)式，σj（j=1，2，…，n）就是非基變量的檢驗(yàn)數(shù)。（3）檢驗(yàn)數(shù)的兩種計(jì)算方法：增廣矩陣的最后2、例1的表格單純形法計(jì)算過(guò)程：

x1x2x3x4x5

23300z111103x4147019x5

23300z3/4

0

-3/4

1

-1/43/4x41/417/401/49/4x25/40–9/40-3/4z-27/410-14/3-1/31x1012-1/31/32x200-1-5/3-1/3z-8從最優(yōu)表可知:該LP的最優(yōu)解是

X*=(1,2,0,0,0)T

相應(yīng)的目標(biāo)函數(shù)最優(yōu)值是Zmax=8**2、例1的表格單純形法計(jì)算過(guò)程：x1x2求解：Maxz=4x1+x2+x3解:本題約束方程系數(shù)矩陣不含單位子矩陣√√√*x1x2x3x4x523100z111103x4147019x523100z3/4

0

-3/4

1

-1/43/4x41/417/401/49/4x25/40–17/40-3/4z-27/4√√√*10-14/3-1/31x1012-1/31/32x200-3-5/3-1/3Z-8階段Ⅰ：MaxW=4x1+x2+x3求解：Maxz=4x1+x2+x3解:本題約束方單純形法小結(jié)

求解思想－－

頂點(diǎn)的逐步轉(zhuǎn)移，

條件是使目標(biāo)函數(shù)值不斷得到改善。單純形法小結(jié)求解思想－－表格單純形法求解步驟第一步：將LP化為標(biāo)準(zhǔn)型，并加以整理。引入適當(dāng)?shù)乃神Y變量、剩余變量和人工變量，使約束條件化為等式，并且約束方程組的系數(shù)陣中有一個(gè)單位陣。

（這一步計(jì)算機(jī)可自動(dòng)完成）

確定初始可行基，寫(xiě)出初始基本可行解表格單純形法求解步驟第一步：將LP化為標(biāo)準(zhǔn)型，并加以整理。第二步：最優(yōu)性檢驗(yàn)計(jì)算檢驗(yàn)數(shù)，檢查：所有檢驗(yàn)數(shù)是否≤0？

是——結(jié)束，寫(xiě)出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值；還有正檢驗(yàn)數(shù)——檢查相應(yīng)系數(shù)列≤

0？是——結(jié)束，該LP無(wú)“有限最優(yōu)解”！不屬于上述兩種情況，轉(zhuǎn)入下一步—基變換。

確定是停止迭代還是轉(zhuǎn)入基變換？第二步：最優(yōu)性檢驗(yàn)計(jì)算檢驗(yàn)數(shù)，檢查：

選擇（最大）正檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列為主元列，主元列對(duì)應(yīng)的非基變量為換入變量；最小比值對(duì)應(yīng)的行為主元行，主元行對(duì)應(yīng)的基變量為換出變量。第三步：基變換確定進(jìn)基變量和出基變量。選擇（最大）正檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列為主元列，主元列

利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)?，進(jìn)基變量對(duì)應(yīng)的檢驗(yàn)數(shù)變成0，從而得到一張新的單純形表，返回第二步。第四步換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算)完成一次迭代，得到新的基本可行解和相應(yīng)的目標(biāo)函數(shù)值利用矩陣的初等行變換把主元列變成單位向量，主元素變?yōu)樵摰^(guò)程直至下列情況之一發(fā)生時(shí)停止

檢驗(yàn)數(shù)行全部變?yōu)榉钦?；（得到最?yōu)解）或主元列≤

0（最優(yōu)解無(wú)界）

停止迭代的標(biāo)志（停機(jī)準(zhǔn)則）該迭代過(guò)程直至下列情況之一發(fā)生時(shí)停止停止迭代的標(biāo)志計(jì)算機(jī)求解時(shí)的注意點(diǎn)1、輸入數(shù)據(jù)中的分?jǐn)?shù)，需先化為小數(shù)再執(zhí)行輸入過(guò)程。2、每一張迭代表格中由基變量列（Basic）和B(i)列（解答列）可以讀出現(xiàn)行解及相應(yīng)的目標(biāo)函數(shù)值，同時(shí)顯示進(jìn)基變量和出基變量，從而很容易識(shí)別主元列、主元行和主元素。3、最終表顯示最優(yōu)解、最優(yōu)目標(biāo)函數(shù)值及總的迭代次數(shù)。如遇該線性規(guī)劃無(wú)可行解或無(wú)“有限最優(yōu)解”，則屏幕將顯示有關(guān)信息：

NOfeasiblesolution.

或**unboundedsolution!!!計(jì)算機(jī)求解時(shí)的注意點(diǎn)1、輸入數(shù)據(jù)中的分?jǐn)?shù)，需先化為小數(shù)再執(zhí)行求解：Maxz=5x1+x2+3x3化為標(biāo)準(zhǔn)性Maxz=5x1+x2+3x3約束方程的系數(shù)矩陣不含單位子矩陣，兩段法求解：1.構(gòu)造輔助規(guī)劃求得原問(wèn)題的初始可行基;2.單純形表求解原問(wèn)題求解：Maxz=5x1+x2+3x3化為標(biāo)準(zhǔn)性M（2）

兩階段法

第一階段：建立輔助線性規(guī)劃并求解，以判斷原線性規(guī)劃是否存在基本可行解。輔助線性規(guī)劃的結(jié)構(gòu)：目標(biāo)函數(shù)W為所有人工變量之和的相反數(shù)，目標(biāo)要求是使目標(biāo)函數(shù)極大化，約束條件與原線性規(guī)劃相同。Maxw=-x5(FP)x5人工變量（2）兩階段法Maxw=-x5(FP)x5人工變量

求解結(jié)果①W最優(yōu)值=0——即所有人工變量取值全為0（為什麼？），均為非基變量，最優(yōu)解是原線性規(guī)劃的一個(gè)基本可行解，轉(zhuǎn)入第二階段；②W最優(yōu)值=0——但人工變量中有等于0的基變量，構(gòu)成退化的基本可行解，可以轉(zhuǎn)化為情況①；如何轉(zhuǎn)化？

選一個(gè)不是人工變量的非基變量進(jìn)基，把在基中的人工變量替換出來(lái)③W最優(yōu)值>0——至少有一個(gè)人工變量取值>0,說(shuō)明基變量中至少有1個(gè)人工變量,表明原問(wèn)題沒(méi)有可行解,討論結(jié)束。求解結(jié)第二階段：

將第一階段的最優(yōu)解作為初始可行解，目標(biāo)函數(shù)換成原問(wèn)題的目標(biāo)函數(shù)，進(jìn)行單純形迭代，求出最優(yōu)解。問(wèn)題討論:如何實(shí)施?需要重新建立初始單純形表嗎？

實(shí)施中，在第一階段最優(yōu)表格中劃去人工變量列，將表頭部分和CB列的價(jià)值系數(shù)換成原問(wèn)題的價(jià)值系數(shù)(把目標(biāo)函數(shù)換成原線性規(guī)劃的目標(biāo)函數(shù))，繼續(xù)迭代，直至求出最優(yōu)解。第二階段：實(shí)施中，在第一階段最優(yōu)表格中劃去人工變

x5

0000-1w211103x4-120014x5

-12000w+45/2

0

1

1

-1/21x4-1/21001/22x20000-1w從最優(yōu)表可知:該FP的最優(yōu)解是X*=(0,2,0,1,0)T相應(yīng)的目標(biāo)函數(shù)最優(yōu)值是Wmax=0x1x2x3x4

5130z5/2

0

1

1

1x4-1/21002x211/2030z-21

0

2/5

2/52/5x1011/5

1/5

11/5x2004/5-11/5z-21/55/2

0

1

1

1x3-1/21002x2-200-3z-5從最優(yōu)表可知:原(LP)的最優(yōu)解X*=(0,2,1,0)T

相應(yīng)的目標(biāo)函數(shù)最優(yōu)值Zmax=5***

例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時(shí)間480小時(shí)至多加工100公斤A1

制訂生產(chǎn)計(jì)劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?

可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？每天:三、線性規(guī)劃建模實(shí)例例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶3公斤A112小1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

線性規(guī)劃模型(LP)時(shí)間480小時(shí)至多加工100公斤A1

50桶牛奶每天1桶牛奶3公斤A112小時(shí)8小時(shí)4公斤A2或獲利2模型分析與假設(shè)

比例性可加性連續(xù)性xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比xi對(duì)約束條件的“貢獻(xiàn)”與xi取值成正比xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無(wú)關(guān)xi對(duì)約束條件的“貢獻(xiàn)”與xj取值無(wú)關(guān)xi取值連續(xù)A1,A2每公斤的獲利是與各自產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)線性規(guī)劃模型模型分析與假設(shè)比例性可加性連續(xù)性xi對(duì)目標(biāo)函數(shù)的“貢模型求解

圖解法

x1x20ABCDl1l2l3l4l5約束條件目標(biāo)函數(shù)

Z=0Z=2400Z=3360z=c(常數(shù))~等值線c在B(20,30)點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù)可行域?yàn)橹本€段圍成的凸多邊形目標(biāo)函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。模型求解圖解法x1x20ABCDl1l2l3l4l5約束模型求解

軟件實(shí)現(xiàn)

LINDO6.1max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤(rùn)3360元。模型求解軟件實(shí)現(xiàn)LINDO6.1max72x1+6結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）結(jié)果解釋OBJECTIVEFUNCTIONVA結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量原料增加1單位,利潤(rùn)增長(zhǎng)48時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！

聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？2元！結(jié)果解釋OBJECTIVEFUNCTIORANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)RANGESINWHICHTHEBASISISU現(xiàn)工廠決策者考慮停產(chǎn)A1,A2,接受外來(lái)加工問(wèn)：接受外來(lái)加工可行條件？設(shè)原材料每桶

y1元，機(jī)器價(jià)格每小時(shí)y2元，加工能力每公斤y3元工廠同意合作前提:另一方接受的可能性：(LP)的對(duì)偶問(wèn)題現(xiàn)工廠決策者考慮停產(chǎn)A1,A2,接受外來(lái)加工問(wèn)：接受外來(lái)加工

35元可買到1桶牛奶，買嗎？若買，每天最多買多少?設(shè)該廠現(xiàn)有生產(chǎn)條件下原材料每桶價(jià)值y1元,機(jī)器價(jià)格每小時(shí)價(jià)值y2元,加工能力每公斤價(jià)值y3元(LP)(DP)(DP)稱為(LP)的對(duì)偶問(wèn)題35元可買到1桶牛奶，買嗎？若買，每天最多買多少?設(shè)該廠現(xiàn)對(duì)稱形式的對(duì)偶問(wèn)題(LP)maxz=cT

x(DP)minw=bT

y性質(zhì)：若x0和y0分別是(LP)和(DP)的可行解，則bTy0≥cTx0;bTy0=cTx0x0和y0分別是(LP)和(DP)的最優(yōu)解對(duì)稱形式的對(duì)偶問(wèn)題(LP)maxz=cTx(DP)mi(LP)(DP)1.(DP)中約束與(LP)中變量符號(hào)一致2.(DP)中變量與(LP)中約束符號(hào)相反(LP)(DP)1.(DP)中約束與(LP)中變量符號(hào)一致2結(jié)果解釋

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價(jià)格有意義時(shí)約束右端的允許變化范圍原料最多增加10時(shí)間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶!(目標(biāo)函數(shù)不變)結(jié)果解釋RANGESINWHICHTHEBASIS例2奶制品的生產(chǎn)銷售計(jì)劃

在例1基礎(chǔ)上深加工1桶牛奶3千克A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤0.8千克B12小時(shí),3元1千克獲利44元/千克0.75千克B22小時(shí),3元1千克獲利32元/千克制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大30元可增加1桶牛奶，3元可增加1小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？50桶牛奶,480小時(shí)至多100公斤A1

B1，B2的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？例2奶制品的生產(chǎn)銷售計(jì)劃在例1基礎(chǔ)上深加工1桶牛奶1桶牛奶

3千克A1

12小時(shí)8小時(shí)4千克A2

或獲利24元/千克獲利16元/kg

0.8千克

B12小時(shí),3元1千克獲利44元/千克0.75千克B22小時(shí),3元1千克獲利32元/千克出售x1千克A1,

x2千克A2，

X3千克B1,x4千克B2原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

目標(biāo)函數(shù)

利潤(rùn)約束條件非負(fù)約束

x5千克A1加工B1，x6千克A2加工B2附加約束

1桶牛奶3千克A112小時(shí)8小時(shí)4千克A2或模型求解

軟件實(shí)現(xiàn)

LINDO6.1OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No模型求解軟件實(shí)現(xiàn)LINDO6.1OBJ

OBJECTIVEFUNCTIONVALUE1)3460.800

VARIABLEVALUEREDUCEDCOST

X10.0000001.680000

X2168.0000000.000000

X319.2000010.000000

X40.0000000.000000

X524.0000000.000000

X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2結(jié)果解釋每天銷售168千克A2和19.2千克B1，利潤(rùn)3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24千克A1全部加工成B1

除加工能力外均為緊約束OBJECTIVEFUNCTIONVA結(jié)果解釋OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES