第4部分線規(guī)劃

第4部分線規(guī)劃第1節(jié)線性規(guī)劃的數(shù)學(xué)模型一、線性規(guī)劃問題人類社會(huì)的主要矛盾：欲望與現(xiàn)實(shí)的矛盾企業(yè)會(huì)遇到市場(chǎng)的局限、產(chǎn)能的局限、配件的局限、資金的局限，這些限制妨礙了我們對(duì)利益的追求，于是人們拓展市場(chǎng)、擴(kuò)大產(chǎn)能、積累資金……但是無論如何，約束始終是存在的，這是人類無法擺脫的宿命。我們能夠做的就是最優(yōu)化地配置資源，在既定的條件下把資源的效用發(fā)揮到極致。例1.生產(chǎn)計(jì)劃問題某公司生產(chǎn)A、B兩種礦產(chǎn)品，銷路不成問題。制約因素主要有技術(shù)工人、設(shè)備臺(tái)時(shí)和原材料供應(yīng)。已知資源產(chǎn)品A產(chǎn)品B產(chǎn)品資源限量人力64300設(shè)備46280礦石28320售價(jià)（元/公斤）80140該公司應(yīng)該如何制定每天的生產(chǎn)計(jì)劃，使其產(chǎn)值最大？

例1.生產(chǎn)計(jì)劃問題設(shè)X1為A產(chǎn)品產(chǎn)量，X2為B產(chǎn)品的產(chǎn)量，用z表示產(chǎn)值，則每天的產(chǎn)值表示為maxz=80X1+140X2，稱為目標(biāo)函數(shù)。將制約因素表達(dá)出來，即有：人力不超過300工時(shí):6X1+4X2≤300設(shè)備不超過280臺(tái)時(shí):4X1+6X2≤280礦石不超過320公斤:2X1+8X2≤320例1.生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型：例2.護(hù)士排班問題醫(yī)院的護(hù)士24小時(shí)都需要值班，不同時(shí)段需要的人數(shù)不同，按照4小時(shí)一個(gè)時(shí)段排班，每班工作8小時(shí)，具體的統(tǒng)計(jì)數(shù)據(jù)如下表：序號(hào)時(shí)段最低人數(shù)16：00-10：0060210：00-14：0070314：00-18：0060418：00-22：0050522：00-2：002062：00-6：0030例2.護(hù)士排班問題設(shè)第時(shí)段上班的人數(shù)為Xj例2.護(hù)士排班問題線性規(guī)劃問題的一般特征max(min)z=二、線性規(guī)劃模型的標(biāo)準(zhǔn)型線性規(guī)劃模型的標(biāo)準(zhǔn)型1.縮寫形式

線性規(guī)劃模型的標(biāo)準(zhǔn)型2.向量形式線性規(guī)劃模型的標(biāo)準(zhǔn)型3.矩陣形式三、非標(biāo)準(zhǔn)型的轉(zhuǎn)化1.約束條件不等式的轉(zhuǎn)化

①約束條件不等式為“≤”時(shí)。在不等式左邊加上一個(gè)松弛變量②約束條件不等式為“≥”時(shí)。在不等式左邊減去一個(gè)剩余變量2.自由變量個(gè)別問題中存在無非負(fù)要求的變量，這時(shí)令，XK=X’K-X’’K,則X’K≥0，X’’K≥03.極小化的目標(biāo)函數(shù)若目標(biāo)函數(shù)為min，令Z=-Z’，使Z’=－CX。求maxZ’等價(jià)于求minZ例3.

寫出例1的標(biāo)準(zhǔn)型例4.

將下列轉(zhuǎn)化為標(biāo)準(zhǔn)型設(shè)Z=-Z’，令X3=X’3-X’’3，再引入松弛變量X4和剩余變量X5第2節(jié)線性規(guī)劃的基本概念和定理一、線性規(guī)劃的基本概念1.可行解滿足所有約束條件的解稱為可行解“一致同意原則”2.可行域可行解的集合叫做可行域3.基矩陣約束方程的系數(shù)矩陣A是m×n階的矩陣，設(shè)n＞m，則A中必有個(gè)m階的方陣，若方陣的行列式值不為0，即方陣為非奇異子陣，則可基于這個(gè)矩陣求得一組解，這個(gè)矩陣就叫做這組解的基矩陣，相應(yīng)的這組解就叫做基解例1的系數(shù)矩陣右端項(xiàng)以子矩陣為基，求得以子矩陣為基，求得以子矩陣為基，求得一、線性規(guī)劃的基本概念4.基可行解立足于基矩陣得到的解叫做基解，基解中的可行解叫做基可行解。前述都是基解，是基可行解，而不是基可行解，因?yàn)椴粷M足非負(fù)性約束。一、線性規(guī)劃的基本概念5.凸集設(shè)K是n維歐式空間的一個(gè)點(diǎn)集，若任意兩點(diǎn)均有則稱K為凸集。凸集的幾何意義是：集合K中任意兩點(diǎn)連線上的點(diǎn)仍然屬于K。二、線性規(guī)劃的圖解法以例1.生產(chǎn)計(jì)劃問題為例5075250255075100125150x1x2ABCD三、線性規(guī)劃的基本定理定理1.線性規(guī)劃的可行域是凸集。定理2.線性規(guī)劃的可行解為基可行解的充要條件是：X的非零分量所對(duì)應(yīng)的系數(shù)列向量線性無關(guān)。定理3.如果線性規(guī)劃有可行解，則一定有基可行解。定理4.線性規(guī)劃問題的基可行解對(duì)應(yīng)于可行域的頂點(diǎn)。定理5.若線性規(guī)劃問題的可行域非空有界，則線性規(guī)劃問題的最優(yōu)解一定可以在其可行域的某個(gè)頂點(diǎn)上得到。特殊的線性規(guī)劃問題1.無窮多解當(dāng)目標(biāo)函數(shù)與某個(gè)約束條件平行時(shí)，有無窮多最優(yōu)解。5075250255075100125150X1x2特殊的線性規(guī)劃問題2.無界解若可行域是一個(gè)開區(qū)間，有可能出現(xiàn)“沒有最好，只有更好”——最優(yōu)解無界的情形。50100500100150特殊的線性規(guī)劃問題3.無可行解當(dāng)約束條件相互矛盾時(shí)，可行域是一個(gè)空集，即呈現(xiàn)沒有可行解的情形50100500100150第3節(jié)線性規(guī)劃的單純形解法單純形法的解題思路：1.從可行解到基解誰做人大代表？2.從基解到最優(yōu)解誰說了算？一、單純形法的代數(shù)解釋顯然，的系數(shù)矩陣是一個(gè)非奇異子陣，以此為基得到一個(gè)基可行解，即：不生產(chǎn)A產(chǎn)品，也不生產(chǎn)B產(chǎn)品，人力剩余300工時(shí)，設(shè)備剩余280臺(tái)時(shí)，即礦石剩余320公斤。

仍以例1.為例一、單純形法的代數(shù)解釋顯然，不是最優(yōu)解,Z(0)=0.令X2≠0，保持X1=0，生產(chǎn)量取決于資源的支持：解得左式的含義是什么？右式為什么是min？得到第二組基可行解一、單純形法的代數(shù)解釋分析：X(1)=(0,40,140,40,0)T,Z(1)=5600，是否最優(yōu)？將基變量用非基變量線性表示：代入目標(biāo)函數(shù)：解釋各參數(shù)的內(nèi)涵，X1的系數(shù)為45，表明生產(chǎn)A產(chǎn)品有利可圖，于是當(dāng)前解還不是最優(yōu)解。一、單純形法的代數(shù)解釋兩個(gè)非基變量中，保持X5為0，迫使X1≠0

解得：于是得到一組新解：[更正]新解是否最優(yōu)呢？還需要進(jìn)一步檢驗(yàn)更正：教材82頁數(shù)字錯(cuò)誤，X3取值由70改為60一、單純形法的代數(shù)解釋將代入目標(biāo)函數(shù)進(jìn)行檢驗(yàn)兩個(gè)非基變量的系數(shù)均為負(fù)值，說明閑置設(shè)備或剩余礦石都將使產(chǎn)值減少，故此判斷：當(dāng)前的解已是最優(yōu)解。二、單純形法原理1.尋找初始基可行解設(shè)有如下線性規(guī)劃模型以前m列為基矩陣B，相應(yīng)地為基變量，非基變量取零值，則得到一組解

2.最優(yōu)性檢驗(yàn)將基變量用非基變量線性表示：代入Z

3.基變換當(dāng)某個(gè)非基變量的檢驗(yàn)數(shù)時(shí)，說明還有改進(jìn)的空間，于是讓進(jìn)基，而基變量的個(gè)數(shù)是有限的，只能是m個(gè)，這時(shí)必須迫使原有的某個(gè)基變量出基，誰出來呢？憑“實(shí)力”較量：令

比值最小的變量就是出基變量。一進(jìn)一出就叫做一次基變換。4.線性變換進(jìn)基出基，交叉點(diǎn)上的系數(shù)叫做主元素（或樞軸元素），用高斯消去法將主元素變?yōu)?，同列中的其它元素變?yōu)榱悖纱说玫揭唤M新的基解回到2.進(jìn)行最優(yōu)性檢驗(yàn)，直至所有的就可以宣布：已經(jīng)得到了最優(yōu)解。求解過程結(jié)束。三、單純形表的格式和算法為了使單純形法的計(jì)算更加便捷和規(guī)范，dantzig設(shè)計(jì)了一種表格，將前述運(yùn)算過程納入表格之中，這個(gè)表格叫做單純形表。將例1標(biāo)準(zhǔn)化后，裝入表格進(jìn)行求解Cj80140000CiXBbx1x2x3x4x5θi0x330064100750x42804601046.70x53202[8]001σj80140↑0000X31405010-1/2280X440[5/2]001-3/4140x2401/41001/8160σj45↑000-17.50X360001-2180X1161002/5-3/10140x236010-1/101/5σj000-18-4四、單純形法的矩陣描述

將標(biāo)準(zhǔn)型拆分：將約束條件移項(xiàng)：左乘得：代入目標(biāo)函數(shù)得：第4節(jié)線性規(guī)劃應(yīng)用舉例與求解線性規(guī)劃的核心在于應(yīng)用應(yīng)用的關(guān)鍵在于建模建模的要點(diǎn)在于變量設(shè)置用合適的變量表達(dá)目標(biāo)函數(shù)、約束條件，就得到了數(shù)學(xué)模型。求解可以借助計(jì)算機(jī)軟件例5.污水處理問題河流沿岸有某公司的兩個(gè)化工廠，A廠每天排放污水2萬方；B廠每天排放污水1.4萬方。A廠排出的污水流到B廠之前，有20％可以自然凈化。根據(jù)環(huán)保要求，河水中污水含量不得超過0.2％。已知A廠污水處理成本1000元/萬方，B廠污水處理成本800元/萬方。問公司應(yīng)該如何分配污水處理的數(shù)量，使得總成本最低？A廠B廠500萬立方/天200萬立方/天例5.污水處理問題建模解：設(shè)A廠處理X1萬方/天，B廠處理X2萬方/天主要約束：①A廠的排放點(diǎn)不超標(biāo)：②B廠的排放點(diǎn)不超標(biāo)：A廠處理量不可能超過2萬方B廠處理量不可能超過1.4萬方例5.污水處理問題建模例5.數(shù)據(jù)輸入例5.結(jié)果輸出例6.合理下料問題某學(xué)校為建造車棚，需要用100個(gè)鋁合金三角架作龍骨，底梁長度2.9米，兩個(gè)斜梁分別是2.1米和1.5米，已知原料長度7.4米。問如何下料使得所用原料最省？2.9m2.1m1.5m例6.合理下料問題建模解：本題的變量設(shè)置不是顯而易見的。首先要設(shè)計(jì)若干個(gè)截取方案，把按照某方案截取的根數(shù)作為決策變量。方案要盡可能完備，遺漏了方案則會(huì)影響最優(yōu)化的結(jié)果。長度方案123456782.9M2.1M1.5M103201022120013111030004余料00.10.20.30.80.91.11.4例6.合理下料問題建模例6.數(shù)據(jù)輸入例6.結(jié)果輸出例7.滾動(dòng)投資問題新任經(jīng)理發(fā)現(xiàn)小金庫里有100萬元資金，令企劃部找項(xiàng)目投資，力爭(zhēng)第五年末本利和最大。企劃部提出四個(gè)投資項(xiàng)目：A項(xiàng)目，從第一年到第四年每年年初投資，并于次年末收回本利110％，每年至少投資10萬元；B項(xiàng)目，第二年初投資，第五年末收回本利135％，投資額度不超過20萬元；C項(xiàng)目，第三年初投資，第五年末收回本利125％，投資額度在20-40萬元之間；D項(xiàng)目，每年年初投資，年末收回本利104％。問應(yīng)該如何安排不同項(xiàng)目不同年度的投資額度？例7.滾動(dòng)投資問題解：設(shè)第i年投資于j項(xiàng)目的金額為萬元第一年第二年第三年第四年第五年A項(xiàng)目1.1B項(xiàng)目1.35D項(xiàng)目1.04C項(xiàng)目1.25例7.滾動(dòng)投資問題建模例7.數(shù)據(jù)處理首先進(jìn)行變量置換，依出現(xiàn)次序排列用代換，原有數(shù)學(xué)模型變?yōu)椋豪?.數(shù)據(jù)輸入例7.結(jié)果輸出第5節(jié)對(duì)偶問題與靈敏度分析一、對(duì)偶問題的提出線性規(guī)劃的另一面賣產(chǎn)品還是賣資源？賣資源所得不少于賣產(chǎn)品對(duì)立的等價(jià)問題例8.資源轉(zhuǎn)讓問題

例1.的思考：A、B兩種產(chǎn)品，市場(chǎng)前景很好，銷路不成問題?，F(xiàn)在有意轉(zhuǎn)換經(jīng)營方式，擬將各種資源出租出讓，問公司轉(zhuǎn)讓資源的價(jià)格底線是什么？資源產(chǎn)品A產(chǎn)品B產(chǎn)品資源限量人力64300設(shè)備46280礦石28320售價(jià)（元/公斤）80140例8.的分析與建模思考：將三種資源出讓，應(yīng)該不少于原有的收益，否則企業(yè)寧愿選擇繼續(xù)自己生產(chǎn)。決策的約束條件是：出租制造產(chǎn)品所耗的資源不少于自行生產(chǎn)該產(chǎn)品的收益；目標(biāo)函數(shù)是：資源轉(zhuǎn)讓的收益底線。例8.的分析與建模設(shè)勞動(dòng)力、設(shè)備臺(tái)時(shí)和礦石的出讓價(jià)格分別為生產(chǎn)A產(chǎn)品的資源至少應(yīng)帶來80元的產(chǎn)值生產(chǎn)B產(chǎn)品的資源至少應(yīng)帶來140元的產(chǎn)值目標(biāo)函數(shù)：轉(zhuǎn)讓的收益底線例8.的分析與建模二、原問題與對(duì)偶問題的關(guān)系原問題和對(duì)偶問題是相互對(duì)應(yīng)的關(guān)系1.原問題目標(biāo)函數(shù)max，約束條件是“≤”形式；對(duì)偶問題目標(biāo)函數(shù)min，約束條件是“≥”形式。2.原問題的價(jià)值系數(shù)對(duì)應(yīng)對(duì)偶問題的右端項(xiàng)，原問題的右端項(xiàng)對(duì)應(yīng)對(duì)偶問題的價(jià)值系數(shù)；3.原問題的變量對(duì)應(yīng)對(duì)偶問題的約束條件，原問題有n個(gè)變量，對(duì)偶問題就有n個(gè)約束條件。原問題有m個(gè)約束條件，對(duì)偶問題就有m個(gè)變量。4.原問題系數(shù)矩陣的轉(zhuǎn)置就是對(duì)偶問題系數(shù)矩陣三、對(duì)偶問題的基本性質(zhì)（1）對(duì)稱性：對(duì)偶問題的對(duì)偶是原問題。（2）弱對(duì)偶性：極大化原問題的任意可行解的目標(biāo)值，不可能超過極小化的對(duì)偶問題的任意可行解的目標(biāo)值。（3）無界性：若其中一個(gè)問題無界，則另一問題無可行解。（4）強(qiáng)對(duì)偶性：若兩個(gè)互為對(duì)偶的問題之一有最優(yōu)解、那么另一個(gè)必有最優(yōu)解，且兩者目標(biāo)函數(shù)值相等。三、對(duì)偶問題的基本性質(zhì)ZX三、對(duì)偶問題的基本性質(zhì)（5）互補(bǔ)松弛定理：和分別是原問題和其對(duì)偶問題的最優(yōu)解的充分必要條是:

這個(gè)定理的含義是：對(duì)偶問題的原始變量對(duì)應(yīng)原問題的松弛變量，原問題的原始變量對(duì)應(yīng)對(duì)偶問題的剩余變量，兩者“你死我活”、“勢(shì)不兩立”，甚至有時(shí)還會(huì)“同歸于盡”。例9.對(duì)偶定理的運(yùn)用例7.設(shè)有線性規(guī)劃問題如下：已知其最優(yōu)解為，求對(duì)偶問題的最優(yōu)解。解：根據(jù)對(duì)偶規(guī)則，寫出其對(duì)偶問題：故有：根據(jù)對(duì)偶定理有如下對(duì)應(yīng)關(guān)系：三、對(duì)偶問題的基本性質(zhì)(6)原問題檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問題的一組解（證明略）原問題檢驗(yàn)數(shù)的反數(shù)恰好對(duì)應(yīng)對(duì)偶問題的解。原問題松弛變量對(duì)應(yīng)對(duì)偶問題的原始變量原問題原始變量對(duì)應(yīng)對(duì)偶問題的剩余變量四、對(duì)偶最優(yōu)解的經(jīng)濟(jì)解釋——影子價(jià)格

的含義是：在其它條件不變的情況下，增加一個(gè)單位的第i種資源所引起的目標(biāo)函數(shù)最優(yōu)值的變化。亦即：每單位第i種資源對(duì)目標(biāo)函數(shù)值的貢獻(xiàn)率。對(duì)資源bi求偏導(dǎo)數(shù)：影子價(jià)格的應(yīng)用影子價(jià)格不是市場(chǎng)價(jià)格，只是企業(yè)資源配置狀況的反應(yīng)，揭示了資源的稀缺度。注意：影子價(jià)格僅僅是“邊際效用”揭示了稀缺資源和過剩資源提示了購入資源的代價(jià)提示了出讓注意的底線判斷新產(chǎn)品的開發(fā)價(jià)值五、靈敏度分析決策現(xiàn)在將來過去數(shù)據(jù)實(shí)施拷問支持問題：環(huán)境是不斷變化的，模型給定的價(jià)值系數(shù)、資源限量、技術(shù)系數(shù)也會(huì)發(fā)生變化，那么最優(yōu)解的結(jié)構(gòu)穩(wěn)定性如何呢？靈敏度分析就是要解答這樣的問題：在保持最優(yōu)基不變的前提下，各類參數(shù)的允許變化范圍是什么。靈敏度分析靈敏度分析案例例10.某藝術(shù)陶瓷制品公司生產(chǎn)6種定型產(chǎn)品，原料車間制成磁泥和釉漿之后，還需要經(jīng)過成型、上釉、貼花/彩繪、焙燒四道工序。產(chǎn)品資源P1P2P3P4P5P6資源限量（分鐘）成型3524648000上釉11.511.2212500貼花0.1--0.1--0.15--200彩繪--5--6--84000焙燒1212312500單位價(jià)格5080407010060

根據(jù)銷售合同，P1最多生產(chǎn)600件，P4至少生產(chǎn)80件，P6最多生產(chǎn)500件，其余產(chǎn)品銷路較好。請(qǐng)根據(jù)資源情況求出最優(yōu)生產(chǎn)計(jì)劃，并且根據(jù)靈敏度分析結(jié)果回答下述問題：1.本公司的資源配置狀況如何？2.如果可以增加資源，應(yīng)該優(yōu)先增加哪種？3.為什么P5的價(jià)格最高卻不生產(chǎn)該產(chǎn)品？4.產(chǎn)品P4是否盈利，如果續(xù)簽合同應(yīng)該如何定價(jià)？5.如果客戶要求P6降價(jià)5元，生產(chǎn)計(jì)劃有沒有變化？6.產(chǎn)品P1的價(jià)格上限為什么是infinity?7.產(chǎn)品P2的價(jià)格下限為什么是-infinity?8.解讀約束條件1的靈敏度分析參數(shù)之間的關(guān)聯(lián)。9.如果彩繪師傅同意加班，每小時(shí)100元工資值不值？最多安排多長的加班時(shí)間？10.主打產(chǎn)品P3的價(jià)格在什么區(qū)間波動(dòng)最優(yōu)解不變？最優(yōu)值變不變？例10.詳解第6節(jié)運(yùn)輸問題一、運(yùn)輸問題的結(jié)構(gòu)m個(gè)產(chǎn)地，n個(gè)銷地，從第i個(gè)產(chǎn)地到第j個(gè)銷地的單位運(yùn)輸費(fèi)用。如何確定一個(gè)調(diào)運(yùn)方案．使得總運(yùn)費(fèi)最省？產(chǎn)銷B1B2…Bn產(chǎn)量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam銷量b1b2…bn二、非標(biāo)運(yùn)輸問題1.供需不平衡的運(yùn)輸問題產(chǎn)大于銷：增加一個(gè)虛擬的銷地銷大于產(chǎn)：增加一個(gè)虛擬的產(chǎn)地例4-11（略）二、非標(biāo)運(yùn)輸問題2.彈性需求問題例12.三個(gè)統(tǒng)配煤礦給四個(gè)地區(qū)供應(yīng)煤炭，作為冬季取暖之用。甲地區(qū)（華北）最低需求30萬噸，最高需求50萬噸；乙地區(qū)（東北）需求70萬噸；丙地區(qū)（廣東）最低需求為零，最高需求30萬噸；丁地區(qū)（上海）最低需求10萬噸，最高不限。供給數(shù)量、需求數(shù)量及相應(yīng)運(yùn)費(fèi)數(shù)據(jù)如下表：如何安排調(diào)運(yùn)方案，使總運(yùn)費(fèi)最少？2.彈性需求問題地區(qū)煤礦甲乙丙丁產(chǎn)量ABC1614191313202219231715－506050最低需求最高需求3050707003010不限2.彈性需求問題分析：數(shù)學(xué)講究嚴(yán)謹(jǐn)和明確，多大的或多小的數(shù)字都好處理，唯獨(dú)模棱兩可的事情不好處理。首先，將剛性部分與彈性部分區(qū)分開來其次，界定丁地區(qū)的“多多益善”第三，以最高需求為基準(zhǔn)建立供需平衡點(diǎn)第四，設(shè)置一個(gè)虛擬煤礦D，用以彌補(bǔ)產(chǎn)能的缺口最后，參數(shù)設(shè)計(jì)，運(yùn)籌學(xué)如何說“no”2.彈性需求問題建模地區(qū)煤礦甲1甲2乙丙丁1丁2產(chǎn)量ABCD161419M1614190131320M22192301715MM1715M050605050需求3020703010502102.彈性需求問題的求解計(jì)算機(jī)不認(rèn)得懲罰項(xiàng)M，必須轉(zhuǎn)換為具體數(shù)值，M只要“足夠大”即可，設(shè)，取值243.航運(yùn)調(diào)度問題例13.航運(yùn)公司經(jīng)營六個(gè)港口之間的四條航線航線起點(diǎn)終點(diǎn)航班數(shù)/天航行天數(shù)1234EBADDCFB3211173713終點(diǎn)起點(diǎn)ABCDEFABCDEF01214771031388230155514131501720785170378520303.航運(yùn)調(diào)度問題假定船只型號(hào)相同，裝船、卸船各需要一天時(shí)間，問該公司至少需要配備多少條船才能滿足運(yùn)營的需要？解題思路：分類：載重船與空駛船載重船分航線測(cè)算，共計(jì)91艘空駛船多少艘？3.航運(yùn)調(diào)度問題ABCFDE1213調(diào)度中心港口每天到達(dá)數(shù)每天需求數(shù)余缺ABCDEF012301120130-1-1+2+2-3+13.航運(yùn)調(diào)度問題供方需方ABE需求量CDF23514131778