人大講義運(yùn)籌學(xué)非常好的一份講義PPT課件

1、1運(yùn)運(yùn) 籌籌 學(xué)學(xué)中國人民大學(xué)2010.10第1頁/共564頁第一章 緒 論第2頁/共564頁運(yùn)籌學(xué)概況簡述 運(yùn)籌學(xué)(Operations Research) 直譯為“運(yùn)作研究”。 運(yùn)籌學(xué)是運(yùn)用科學(xué)的方法(如分析、試驗(yàn)、量化等)來決定如何最佳地運(yùn)營和設(shè)計各種系統(tǒng)的一門學(xué)科。第3頁/共564頁運(yùn)籌學(xué)概況簡述運(yùn)籌學(xué)概況簡述 運(yùn)籌學(xué)能夠?qū)?jīng)濟(jì)管理系統(tǒng)中的人力、物力、財力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。 通常以最優(yōu)、最佳等作為決策目標(biāo)，避開最劣的方案。第4頁/共564頁運(yùn)籌學(xué)在工商管理中的應(yīng)用 生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等

2、。 庫存管理：多種物資庫存量的管理，庫存方式、庫存量等。 運(yùn)輸問題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、運(yùn)輸工具的調(diào)度以及建廠地址的選擇等。第5頁/共564頁運(yùn)籌學(xué)在工商管理中的應(yīng)用運(yùn)籌學(xué)在工商管理中的應(yīng)用 人事管理：對人員的需求和使用的預(yù)測，確定人員編制、人員合理分配，建立人才評價體系等。 市場營銷：廣告預(yù)算、媒介選擇、定價、產(chǎn)品開發(fā)與銷售計劃制定等。第6頁/共564頁運(yùn)籌學(xué)在工商管理中的應(yīng)用運(yùn)籌學(xué)在工商管理中的應(yīng)用 財務(wù)和會計：包括預(yù)測、貸款、成本分析、定價、證券管理、現(xiàn)金管理等。 其他： 設(shè)備維修、更新，項(xiàng)目選擇、評價，工程優(yōu)化設(shè)計與管理等。第7頁/共564頁運(yùn)籌學(xué)的產(chǎn)生和發(fā)展 運(yùn)籌學(xué)思

3、想的出現(xiàn)可以追溯到很早“田忌齊王賽馬”（對策論）、孫子兵法等都體現(xiàn)了優(yōu)化的思想。 “Operational Research”這一名詞最早出現(xiàn)在第二次世界大戰(zhàn)期間 美、英等國家的作戰(zhàn)研究小組為了解決作戰(zhàn)中所遇到的許多錯綜復(fù)雜的戰(zhàn)略、戰(zhàn)術(shù)問題而提出的。第8頁/共564頁運(yùn)籌學(xué)的產(chǎn)生和發(fā)展運(yùn)籌學(xué)的產(chǎn)生和發(fā)展 戰(zhàn)后這些研究成果被應(yīng)用到生產(chǎn)、經(jīng)濟(jì)領(lǐng)域，并得到迅速發(fā)展有關(guān)理論和方法的研究、實(shí)踐不斷深入。 1947年美國數(shù)學(xué)家丹捷格(G.B.Dantzig）提出了求解線性規(guī)劃的有效方法單純形法。第9頁/共564頁運(yùn)籌學(xué)的產(chǎn)生和發(fā)展運(yùn)籌學(xué)的產(chǎn)生和發(fā)展 數(shù)學(xué)對運(yùn)籌學(xué)的作用是有關(guān)理論和方法的研究基礎(chǔ)，是建立運(yùn)籌

4、學(xué)模型的工具。 計算機(jī)的發(fā)展，促進(jìn)運(yùn)籌學(xué)的進(jìn)一步發(fā)展高速、可靠的計算是運(yùn)籌學(xué)解決問題的基本保障。第10頁/共564頁運(yùn)籌學(xué)的分支線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動態(tài)規(guī)劃多目標(biāo)規(guī)劃隨機(jī)規(guī)劃模糊規(guī)劃等第11頁/共564頁運(yùn)籌學(xué)的分支運(yùn)籌學(xué)的分支圖與網(wǎng)絡(luò)理論存儲論排隊(duì)論決策論對策論排序與統(tǒng)籌方法可靠性理論等第12頁/共564頁運(yùn)籌學(xué)方法使用情況( (美1983)1983)第13頁/共564頁 運(yùn)籌學(xué)方法在中國使用情況運(yùn)籌學(xué)方法在中國使用情況 ( (隨機(jī)抽樣隨機(jī)抽樣) )第14頁/共564頁運(yùn)籌學(xué)的推廣應(yīng)用前景 據(jù)美勞工局1992年統(tǒng)計預(yù)測:社會對運(yùn)籌學(xué)應(yīng)用分析人員的需求從1990年到2005年，其增長百分

5、比預(yù)測為73%,增長速度排到各項(xiàng)職業(yè)的前三位。第15頁/共564頁運(yùn)籌學(xué)的推廣應(yīng)用前景運(yùn)籌學(xué)的推廣應(yīng)用前景結(jié)論:-運(yùn)籌學(xué)在國內(nèi)或國外的推廣應(yīng)用前景是非常廣闊的。-工商企業(yè)對運(yùn)籌學(xué)應(yīng)用的需求是很大的。-在工商企業(yè)推廣運(yùn)籌學(xué)方面有大量的工作要做。第16頁/共564頁運(yùn)籌學(xué)解決問題的過程 1）提出問題：認(rèn)清問題。 2）尋求可行方案：建模、求解。 3）確定評估目標(biāo)及方案的標(biāo)準(zhǔn)或方法、途徑。 4）評估各個方案：解的檢驗(yàn)、靈敏性分析等。第17頁/共564頁運(yùn)籌學(xué)解決問題的過程運(yùn)籌學(xué)解決問題的過程 5）選擇最優(yōu)方案：決策。 6）方案實(shí)施：回到實(shí)踐中。 7）后評估：考察問題是否得到完滿解決。 1）2）3）形成

6、問題；4）5）分析問題：定性分析與定量分析相結(jié)合，構(gòu)成決策。第18頁/共564頁如何學(xué)習(xí)運(yùn)籌學(xué)課程如何學(xué)習(xí)運(yùn)籌學(xué)課程 學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析、理解有關(guān)的概念、思路上。在自學(xué)過程中，應(yīng)該多向自己提問，例如一個方法的實(shí)質(zhì)是什么，為什么這樣進(jìn)行，怎么進(jìn)行等。 自學(xué)時要掌握三個重要環(huán)節(jié)：第19頁/共564頁如何學(xué)習(xí)運(yùn)籌學(xué)課程如何學(xué)習(xí)運(yùn)籌學(xué)課程 1.認(rèn)真閱讀教材和參考資料，以指定教材為主，同時參考其他有關(guān)書籍。一般每一本運(yùn)籌學(xué)教材都有自己的特點(diǎn)，但是基本原理、概念都是一致的。注意主從，參考資料會幫助你開闊思路，使學(xué)習(xí)深入。但是，把時間過多放在參考資料上，會導(dǎo)致思路分散，不利于學(xué)好。 第20頁/共56

7、4頁 2.要在理解了基本概念和理論的基礎(chǔ)上研究例題，注意例題是為了幫助理解概念、理論的。作業(yè)練習(xí)的主要作用也是這樣，它同時還有讓你自己檢查自己學(xué)習(xí)的作用。因此，做題要有信心，要獨(dú)立完成，不要怕出錯。因?yàn)?，整個課程是一個整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學(xué)到一定程度，知識融會貫通起來，你自己就能夠?qū)λ鲱}目的正確性作出判斷。如何學(xué)習(xí)運(yùn)籌學(xué)課程如何學(xué)習(xí)運(yùn)籌學(xué)課程第21頁/共564頁 3、要學(xué)會做學(xué)習(xí)小結(jié)。每一節(jié)或一章學(xué)完后，必須學(xué)會用精煉的語言來概述該書所講內(nèi)容。這樣，你才能夠從較高的角度來看問題，更深刻地理解有關(guān)知識和內(nèi)容。這就稱作“把書讀薄”，若能夠結(jié)合相關(guān)參考文獻(xiàn)并深入理解，把相關(guān)知識從更深入、

8、廣泛的角度進(jìn)行論述，則稱為“把書讀厚”。如何學(xué)習(xí)運(yùn)籌學(xué)課程如何學(xué)習(xí)運(yùn)籌學(xué)課程第22頁/共564頁23 第二章 線性規(guī)劃建模及單純形法本章內(nèi)容重點(diǎn)w線性規(guī)劃模型與解的主要概念w線性規(guī)劃的單純形法，線性規(guī)劃多解分析w線性規(guī)劃應(yīng)用建模第23頁/共564頁241.1.線性規(guī)劃的概念 例2.1:某工廠擁有A、B、C 三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示： 產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3 32 26565設(shè)備B2 21 14040設(shè)備C0 03 37575利潤（元/件）1500150025002500 第24

9、頁/共564頁25 問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？ 解：設(shè)變量 xi 為第 i 種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i1，2）。根據(jù)題意，我們知道兩種產(chǎn)品的生產(chǎn)受到設(shè)備能力（機(jī)時數(shù)）的限制。對設(shè)備A：兩種產(chǎn)品生產(chǎn)所占用的機(jī)時數(shù)不能超過65，于是我們可以得到不等式：3 x1 + 2 x2 65； 對設(shè)備B：兩種產(chǎn)品生產(chǎn)所占用的機(jī)時數(shù)不能超過40，于是我們可以得到不等式：2 x1 + x2 40；1.1.線性規(guī)劃的概念線性規(guī)劃的概念第25頁/共564頁26 對設(shè)備C ：兩種產(chǎn)品生產(chǎn)所占用的機(jī)時數(shù)不能超過75，于是我們可以得到不等式：3x2 75 ；另外，產(chǎn)品數(shù)不可能為負(fù)，即 x1 ,x2 0

10、。 同時，我們有一個追求目標(biāo)，即獲取最大利潤。于是可寫出目標(biāo)函數(shù)z為相應(yīng)的生產(chǎn)計劃可以獲得的總利潤： z = 1500 x1 + 2500 x2 綜合上述討論，在加工時間以及利潤與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下，把目標(biāo)函數(shù)和約束條件放在一起，可以建立如下的線性規(guī)劃模型：1.1.線性規(guī)劃的概念第26頁/共564頁27目標(biāo)函數(shù) Max z =1500 x1+2500 x2約束條件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 1.1.線性規(guī)劃的概念第27頁/共564頁28 這是一個典型的利潤最大化的生產(chǎn)計劃問題。其中，“Max”是英文單詞“Maximize

11、”的縮寫，含義為“最大化”；“s.t.”是“subject to”的縮寫，表示“滿足于”。因此，上述模型的含義是：在給定條件限制下，求使目標(biāo)函數(shù) z 達(dá)到最大的x1 ,x2 的取值。1.1.線性規(guī)劃的概念第28頁/共564頁29一般形式 目標(biāo)函數(shù)：Max(Min)z = c1x1 + c2x2 + + cnxn 約束條件： a11x1+a12x2+a1nxn( =, )b1a21x1+a22x2+a2nxn( =, )b2 . . . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ， ，xn 01.1.線性規(guī)劃的概念線性規(guī)劃的概念第29頁/共564頁30標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：

12、Max z = c1x1 + c2x2 + + cnxn 約束條件：A11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 01.1.線性規(guī)劃的概念第30頁/共564頁31 可以看出，線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個特點(diǎn)：目標(biāo)最大化、約束為等式、決策變量均非負(fù)、右端項(xiàng)非負(fù)。 對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式: 1.1.線性規(guī)劃的概念第31頁/共564頁32 1.極小化目標(biāo)函數(shù)的問題： 設(shè)目標(biāo)函數(shù)為 Min

13、 f = c1x1 + c2x2 + + cnxn 則可以令z -f ，該極小化問 題與下面的極大化問題有相同的最優(yōu) 解，即 Max z = -c1x1 - c2x2 - - cnxn 但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即 Min f - Max z1.1.線性規(guī)劃的概念第32頁/共564頁33 2、約束條件不是等式的問題： 設(shè)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 可以引進(jìn)一個新的變量s ，使它等于約束右邊與左邊之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 顯然，s 也具有非負(fù)約束，即s0，

14、 這時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn+s = bi1.1.線性規(guī)劃的概念第33頁/共564頁34 當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時，類似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 顯然，s 也具有非負(fù)約束，即s0，這時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi 1.1.線性規(guī)劃的概念第34頁/共564頁35 為了使約束由不等式成為等式而引進(jìn)的變量 s 稱為“松弛變量”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的松弛變量。1.1.線

15、性規(guī)劃的概念第35頁/共564頁36 例2.2：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0 1.1.線性規(guī)劃的概念 解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令 z= -f = -3.6x1+5.2x2-1.8x3 第36頁/共564頁37其次考慮約束，有2個不等式約束，引進(jìn)松弛變量x4，x5 0。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題： Max z = - 3.6

16、 x1 + 5.2 x2 - 1.8 x3s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 01.1.線性規(guī)劃的概念第37頁/共564頁38 3. 變量無符號限制的問題：在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。當(dāng)某一個變量xj沒有非負(fù)約束時，可以令 xj = xj- xj”其中 xj0，xj”0即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然xj的符號取決于xj和xj”的大小。1.1.線性規(guī)劃的概念第38頁/共564頁39 4.右端項(xiàng)有負(fù)值的問題：在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)

17、必須每一個分量非負(fù)。當(dāng)某一個右端項(xiàng)系數(shù)為負(fù)時，如 bim，秩(A A) = m，b b Rm 。在約束等式中，令n維空間的解向量： x x = (x1，x2，xn)T 2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第77頁/共564頁78 中n-m個變量為零，如果剩下的m個變量在線性方程組中有唯一解，則這n個變量的值組成的向量x x就對應(yīng)于n維空間Rn中若干個超平面的一個交點(diǎn)。當(dāng)這n個變量的值都是非負(fù)時，這個交點(diǎn)就是線性規(guī)劃可行域的一個極點(diǎn)。 根據(jù)以上分析，我們建立以下概念： （1）線性規(guī)劃的基：對于線性規(guī)劃的約束條件 AxAx=b b， x x0 0 2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第

18、78頁/共564頁79 設(shè)B B是A A矩陣中的一個非奇異（可逆）的mm子矩陣，則稱B B為線性規(guī)劃的一個基。用前文的記號，A A=( p p1 1 ，p p2 2 ，p pn n ) ，其中 p pj j=( a1j ，a2j ，amj )T Rm ，任取A A中的m個線性無關(guān)列向量 p pj j Rm 構(gòu)成矩陣 B B=( p pj1 j1 ，p pj2 j2 ，p pjmjm )。那么B B為線性規(guī)劃的一個基。 我們稱對應(yīng)于基B B的變量xj1 ，xj2，xjm為基變量；而其他變量稱為非基變量。2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第79頁/共564頁80 可以用矩陣來描述這些概念。

19、 設(shè)B B是線性規(guī)劃的一個基，則A A可以表示為 A A= = B , NB , N x x也可相應(yīng)地分成 x xB B x x= x xN N 其中x xB為m維列向量，它的各分量稱為基變量，與基B B的列向量對應(yīng)；x xN為n-m列向量，它的各分量稱為非基變量，與非基矩陣N N的列向量對應(yīng)。這時約束等式AxAx=b b可表示為 2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第80頁/共564頁81 x xB B,N = b b x xN 或 BxBxB + NxNxN = b b 如果對非基變量x xN取確定的值，則xB有唯一的值與之對應(yīng) x xB = B B-1b b - B B-1NxNx

20、N 特別，當(dāng)取x xN = 0 0，這時有x xB=B B-1b b。關(guān)于這類特別的解，有以下概念。2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第81頁/共564頁82 （2）線性規(guī)劃問題的基本解、基本可行解和可行基： 對于線性規(guī)劃問題，設(shè)矩陣B B = ( p pj1j1，p pj2j2，p pjmjm ) 為一個基，令所有非基變量為零，可以得到m個關(guān)于基變量xj1 ，xj2 ，xjm的線性方程，解這個線性方程組得到基變量的值。我們稱這個解為一個基本解；若得到的基變量的值均非負(fù)，則稱為基本可行解，同時稱這個基B B為可行基。2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第82頁/共564頁83 矩

21、陣描述為，對于線性規(guī)劃的解 x xB B B-1b b x x= = x xN 0 稱為線性規(guī)劃與基B B對應(yīng)的基本解。若其中B B-1b b0 0，則稱以上的基本解為一基本可行解，相應(yīng)的基B B稱為可行基。 2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第83頁/共564頁84 我們可以證明以下結(jié)論：線性規(guī)劃的基本可行解就是可行域的極點(diǎn)。 這個結(jié)論被稱為線性規(guī)劃的基本定理，它的重要性在于把可行域的極點(diǎn)這一幾何概念與基本可行解這一代數(shù)概念聯(lián)系起來，因而可以通過求基本可行解的線性代數(shù)的方法來得到可行域的一切極點(diǎn)，從而有可能進(jìn)一步獲得最優(yōu)極點(diǎn)。2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第84頁/共56

22、4頁85 例2.9: 考慮例2.8的線性規(guī)劃模型 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0 注意，線性規(guī)劃的基本解、基本可行 解（極點(diǎn)）和可行基只與線性規(guī)劃問 題標(biāo)準(zhǔn)形式的約束條件有關(guān)。2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第85頁/共564頁86 3 2 1 0 0A A = = P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5 = = 2 1 0 1 0 0 3 0 0 1 A A

23、矩陣包含以下10個33的子矩陣： B B1 1=p p1 1 ，p p2 2 ，p p3 3 B B2 2=p p1 1 ，p p2 2 ，p p4 4 B B3 3=p p1 1 ，p p2 2 ，p p5 5 B B4 4=p p1 1 ，p p3 3 ，p p4 4 B B5 5=p p1 1 ，p p3 3 ，p p5 5 B B6 6=p p1 1 ，p p4 4 ，p p5 5 B B7 7=p p2 2 ，p p3 3 ，p p4 4 B B8 8=p p2 2 ，p p3 3 ，p p5 5 B B9 9=p p2 2 ，p p4 4 ，p p5 5 B B1010=p p3

24、3 ，p p4 4 ，p p5 5 2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第86頁/共564頁87 其中B B4= 0，因而B B4不是該線性規(guī)劃問題的基。其余均為非奇異方陣，因此該問題共有9個基。 對于基B B3=p p1 1 ，p p2 2 ，p p5 5 ，令非基變量x3 3 = 0， x4 = 0，在等式約束中令x3 = 0，x4 = 0，解線性方程組： 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，對應(yīng)的基本可行解： x x=(x1 ，x2

25、，x3 ，x4 ，x5)T=(15，10，0，0，45)T。于是對應(yīng)的基B B3是一個可行基。2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第87頁/共564頁88 類似可得到 x x(2) = (5,25,0,5,0)T （對應(yīng)B B2） x x(7) = (20,0,5,0,75)T （對應(yīng)B B5） x x(8) = (0,25,15,15,0)T （對應(yīng)B B7） x x(9) = (0,0,65,40,75)T （對應(yīng)B B10） 是基本可行解； 而x x(3)= (0,32.5,0,7.5,-22.5)T（對應(yīng)B B9） x x(4)= (65/3,0,0,-10/3,75)T （對應(yīng)

26、B B6） x x(5)= (7.5,25,-7.5,0,0)T （對應(yīng)B B1） x x(6) = (0,40,-15,0,-45)T （對應(yīng)B B8） 是基本解。2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第88頁/共564頁89 因此，對應(yīng)基本可行解（極點(diǎn)） 的B B2 B B3 B B5 B B7 B B10都是可行基。 這里指出了一種求解線性規(guī)劃問題的可能途徑，就是先確定線性規(guī)劃問題的基，如果是可行基，則計算相應(yīng)的基本可行解以及相應(yīng)解的目標(biāo)函數(shù)值。由于基的個數(shù)是有限的（最多個），因此必定可以從有限個基本可行解中找到最優(yōu)解。2.2.線性規(guī)劃解的概念線性規(guī)劃解的概念 第89頁/共564頁9

27、0 利用求解線性規(guī)劃問題基本可行解（極點(diǎn)）的方法來求解較大規(guī)模的問題是不可行的。單純形法的基本思路是有選擇地取基本可行解，即是從可行域的一個極點(diǎn)出發(fā)，沿著可行域的邊界移到另一個相鄰的極點(diǎn)，要求新極點(diǎn)的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差。 3.3.單單 純純 形形 法法第90頁/共564頁91 由上節(jié)的討論可知，對于線性規(guī)劃的一個基，當(dāng)非基變量確定以后，基變量和目標(biāo)函數(shù)的值也隨之確定。因此，一個基本可行解向另一個基本可行解的移動，以及移動時基變量和目標(biāo)函數(shù)值的變化，可以分別由基變量和目標(biāo)函數(shù)用非基變量的表達(dá)式來表示。同時，當(dāng)可行解從可行域的一個極點(diǎn)沿著可行域的邊界移動到一個相鄰的極點(diǎn)的過程中，所有非基

28、變量中只有一個變量的值從0開始增加，而其他非基變量的值都保持0不變。3.3.單單 純純 形形 法法第91頁/共564頁923.3.單單 純純 形形 法法初始基本可行解初始基本可行解是否最優(yōu)解或是否最優(yōu)解或無限最優(yōu)解無限最優(yōu)解? ?結(jié)束結(jié)束沿邊界找新沿邊界找新的基本可行解的基本可行解NY單純形法的基本過程第92頁/共564頁93考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題：Max z = c1x1 + c2x2 + + cnxn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 . . . am1 x1 + am2 x2 +

29、+ amn xn = bm x1 , x2 , , xn 0 x1 c1 b1 a11 a12.a1n x2 c2 b2 a21 a22.a2nx x= . C C= . B B= . A A= . . . . . . . . . xn cn bn am1 am2.amn 3.3.單單 純純 形形 法法第93頁/共564頁94這里，矩陣A A表示為：A A = ( p p1 1 ，p p2 2 ，p pn n ) ，其中 p pj j = ( a a1j 1j ，a a2j 2j ，a amjmj )T Rm。若找到一個可行基，無防設(shè)B B = ( p p1 1 ，p p2 2 ，p pm m

30、 ) ，則m個基變量為 x1 , x2 , , xm，n-m個非基變量為 xm+1 ，xm+2 ，xn 。通過運(yùn)算，所有的基變量都可以用非基變量來表示：3.3.單單 純純 形形 法法第94頁/共564頁953.3.單單 純純 形形 法法 x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）( 2-11 ) . . . xm=bm-（amm+1xm+1+amm+2xm+2+amnxn） 把它們代入目標(biāo)函數(shù)，得 z = z+m+1xm+1+m+2xm+2+nxn ( 2-12 )其中 j=cj-（c1a1j + c2

31、a2j + + cm amj） 我們把由非基變量表示的目標(biāo)函數(shù)形式稱為基B B相應(yīng)的目標(biāo)函數(shù)典式典式。第95頁/共564頁96單純形法的基本步驟可描述如下： （1）尋找一個初始的可行基和相應(yīng)基本可行解（極點(diǎn)），確定基變量、非基變量以及基變量、非基變量（全部等于0）和目標(biāo)函數(shù)的值，并將目標(biāo)函數(shù)和基變量分別用非基變量表示； 3.3.單單 純純 形形 法法第96頁/共564頁97 （2）在用非基變量表示的目標(biāo)函數(shù)表達(dá)式（2-12）中，我們稱非基變量xj的系數(shù)（或其負(fù)值）為檢驗(yàn)數(shù)記為 j 。若 j 0，那么相應(yīng)的非基變量xj，它的值從當(dāng)前值0開始增加時，目標(biāo)函數(shù)值隨之增加。這個選定的非基變量xj稱為“

32、進(jìn)基變量”，轉(zhuǎn)（3）。如果任何一個非基變量的值增加都不能使目標(biāo)函數(shù)值增加，即所有 j 非正，則當(dāng)前的基本可行解就是最優(yōu)解，計算結(jié)束；3.3.單單 純純 形形 法法第97頁/共564頁98 （3）在用非基變量表示的基變量的表達(dá)式（2-11）中，觀察進(jìn)基變量增加時各基變量變化情況，確定基變量的值在進(jìn)基變量增加過程中首先減少到0的變量xr ，滿足，=minbi /aij aij 0 = br /arj這個基變量xr稱為“出基變量”。當(dāng)進(jìn)基變量的值增加到 時，出基變量xr的值降為0時，可行解就移動到了相鄰的基本可行解（極點(diǎn)），轉(zhuǎn)（4）。3.3.單單 純純 形形 法法第98頁/共564頁99如果進(jìn)基變量

33、的值增加時，所有基變量的值都不減少，即所有aij 非正，則表示可行域是不封閉的，且目標(biāo)函數(shù)值隨進(jìn)基變量的增加可以無限增加，此時，不存在有限最優(yōu)解，計算結(jié)束； （4）將進(jìn)基變量作為新的基變量，出基變量作為新的非基變量，確定新的基、新的基本可行解和新的目標(biāo)函數(shù)值。在新的基變量、非基變量的基礎(chǔ)上重復(fù)（1）。3.3.單單 純純 形形 法法第99頁/共564頁100 例2.10：用單純形法的基本思路解例2.8的線性規(guī)劃問題 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1

34、, x2 , x3 , x4 , x5 03.3.單單 純純 形形 法法第100頁/共564頁101第一次迭代：（1）取初始可行基B B10= (p p3 3 , p, p4 4 , p, p5 5)，那么x3 ，x4 ，x5為基變量，x1 ，x2為非基變量。將基變量和目標(biāo)函數(shù)用非基變量表示： z z=1500 x1+2500 x2 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2當(dāng)非基變量x1，x2=0時，相應(yīng)的基變量和目標(biāo)函數(shù)值為x3=65，x4=40，x5= 75，z = 0，得到當(dāng)前的基本可行解：x x=(0,0,65,4

35、0,75)T，z = 0 。這個解對應(yīng)于圖2-7的D、E交點(diǎn)。3.3.單單 純純 形形 法法第101頁/共564頁102 （2）選擇進(jìn)基變量。在目標(biāo)函數(shù)z z = 1500 x1 + 2500 x2中，非基變量x1，x2的系數(shù)都是正數(shù)，因此 x1 ，x2進(jìn)基都可以使目標(biāo)函數(shù)z增大，但x2的系數(shù)為2500，絕對值比x1的系數(shù)1500大，因此把x2作為進(jìn)基變量可以使目標(biāo)函數(shù)z增加更快。選擇x2為進(jìn)基變量，使x2的值從0開始增加，另一個非基變量x1保持零值不變。3.3.單單 純純 形形 法法第102頁/共564頁103 （3）確定出基變量。在約束條件 x3 = 65 - 3 x1 - 2 x2 x4

36、 = 40 - 2 x1 - x2 x5 = 75 - 3 x2中，由于進(jìn)基變量x2在3個約束條件中的系數(shù)都是負(fù)數(shù)，當(dāng)x2的值從0開始增加時，基變量x3 、x4 、x5的值分別從當(dāng)前的值65、40和75開始減少，當(dāng)x2增加到25時，x5首先下降為0成為非基變量。這時，新的基變量為x3 、x4 、x2 ，新的非基變量為x1 、x5 ，當(dāng)前的基本可行解和目標(biāo)函數(shù)值為：x x = (0，25，15，15，0)T，z = 62500。這個解對應(yīng)于圖中的C、D交點(diǎn)。 3.3.單單 純純 形形 法法第103頁/共564頁104第二次迭代： （1）當(dāng)前的可行基為B B7 = (p p2 2 , p, p3

37、3 , , p p4 4)，那么x2 ，x3 ，x4為基變量，x1 ，x5為非基變量。將基變量和目標(biāo)函數(shù)用非基變量表示： z = 62500 + 1500 x1 (2500/3) x5 x2 = 25 (1/3) x5x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 3.3.單單 純純 形形 法法第104頁/共564頁105 （2）選擇進(jìn)基變量。在目標(biāo)函數(shù)z = 62500 + 1500 x1 (2500/3) x5 中，非基變量x1的系數(shù)是正數(shù)，因此 x1進(jìn)基可以使目標(biāo)函數(shù)z增大，于是選擇x1進(jìn)基，使x1的值從0開始增加, 另一個非基變量

38、x5保持零值不變。 (3)確定出基變量。在約束條件 x2 = 25 (1/3) x5x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 3.3.單單 純純 形形 法法第105頁/共564頁106中，由于進(jìn)基變量x1在兩個約束條件中的系數(shù)都是負(fù)數(shù)，當(dāng)x1的值從0開始增加時，基變量x3 、x4的值分別從當(dāng)前的值15、15開始減少，當(dāng)x1增加到5時，x3首先下降為0成為非基變量。這時，新的基變量為x1 、x2 、x4 ，新的非基變量為x3 、x5 ，當(dāng)前的基本可行解和目標(biāo)函數(shù)值為：x x = (5，25，0，5，0)T，z = 70000。這個解對

39、應(yīng)于圖中的A、C交點(diǎn)。3.3.單單 純純 形形 法法第106頁/共564頁107第三次迭代： （1）當(dāng)前的可行基為B B2 = (p p1 1 , , p p2 2 , p, p4 4 )，那么x1 ，x2 ，x4為基變量，x3 ，x5為非基變量。將基變量和目標(biāo)函數(shù)用非基變量表示： z = 70000 500 x3 500 x5x1 = 5 (1/3) x3 + (2/9) x5 x2 = 25 (1/3) x5x4 = 5 + (2/3) x3 (1/9) x5 3.3.單單 純純 形形 法法第107頁/共564頁108 （2）選擇進(jìn)基變量。在目標(biāo)函數(shù)z = 70000 500 x3 500

40、 x5 中，非基變量x3 、x5的系數(shù)均不是正數(shù)，因此進(jìn)基都不可能使目標(biāo)函數(shù)z增大，于是得到最優(yōu)解，x x* * = (5，25，0，5，0)T，最優(yōu)目標(biāo)值為z* = 70000。這個解對應(yīng)于圖2-7的A、C交點(diǎn)。我們也稱相應(yīng)的基B B2 = (p p1 1 , , p p2 2 , , p p4 4)為最優(yōu)基最優(yōu)基。計算結(jié)束。3.3.單單 純純 形形 法法第108頁/共564頁1093 3、 單 純 形 法 表格單純形法 考慮： bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b

41、1 a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 0第109頁/共564頁1103 3、 單 純 形 法加入松弛變量： Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0第110頁/共56

42、4頁111顯然，xj = 0 j = 1, , n ; xn+i = bi i = 1 , , m 是基本可行解 對應(yīng)的基是單位矩陣。以下是初始單純形表： m m其中：f = - cn+i bi j = cj - cn+i aij 為檢驗(yàn)數(shù) cn+i = 0 i= 1,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1, , m3 3、 單 純 形 法c1 cn cn+1 cn+m CB XB x1 xn xn+1 xn+m i cn+1 xn+1 b1 a11 a1n a1n+1 a1n+m 1 cn+2 xn+2 b2 a21 a2

43、n a2n+1 a2n+m 2 cn+m xn+m bm am1 amn amn+1 amn+m m -z f 1 n 0 0 第111頁/共564頁1123 3、 單 純 形 法1500 2500 0 0 0 CB XB x1 X2 x3 x4 x5 i 0 x3 65 3 2 1 0 0 32.5 0 x4 40 2 1 0 1 0 40 0 x5 75 0 (3) 0 0 1 25 -z 0 1500 2500* 0 0 0 0 x3 15 (3) 0 1 0 -2/3 5 0 x4 15 2 0 0 1 -1/3 7. 5 2500 x2 25 0 1 0 0 1/3 -z -6250

44、0 1500* 0 0 0 -2500/3 1500 x1 5 1 0 1/3 0 -2/ 9 0 x4 5 0 0 -2/3 1 1/9 2500 x2 25 0 1 0 0 1/3 -z -70000 0 0 -500 0 -500 例例2.10?；瘶?biāo)準(zhǔn)形式：?；瘶?biāo)準(zhǔn)形式：Max z =1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0 最優(yōu)解 x1 = 5 x2 = 25 x4 = 5（松弛標(biāo)量，表示B設(shè)備有5個機(jī)時的剩余） 最優(yōu)值

45、 z* = 70000 第112頁/共564頁113注意：單純形法中， 1、每一步運(yùn)算只能用矩陣初等行變換； 2、表中第3列的數(shù)總應(yīng)保持非負(fù)（ 0）； 3、當(dāng)所有檢驗(yàn)數(shù)均非正（ 0）時，得到最優(yōu)單純形表。3 3、 線 性 規(guī) 劃 第113頁/共564頁114 一般情況的處理及注意事項(xiàng)的強(qiáng)調(diào)：主要是討論初始基本可行解不明顯時，常用的方法。要弄清它的原理，并通過例題掌握這些方法，同時進(jìn)一步熟悉用單純形法解題。 考慮一般問題： bi 0 i = 1 , , m3.3.單單 純純 形形 法法第114頁/共564頁115Max z = c1x1 + c2x2 + + cnxn s.t. a11x1+a1

46、2x2 +a1nxn = b1 a21x1+a22x2 +a2nxn = b2 . . . am1x1+am2x2+amnxn = bm x1 ，x2 ， ，xn 03.3.單單 純純 形形 法法第115頁/共564頁116大M M法： 引入人工變量 xn+i 0 （i = 1 , , m）及充分大正數(shù) M 。得到：Max Max z = c1x1 +c2x2 +cnxn -Mxn+1 -Mxn+m s.t. s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 . . . .

47、. . am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0 03.3.單單 純純 形形 法法第116頁/共564頁117顯然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解。對應(yīng)的基是單位矩陣。 結(jié)論：若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , , m 則是原問題的最優(yōu)解；否則，原問題無可行解。3.3.單單 純純 形形 法法第117頁/共564頁118 兩階段法： 引入人工變量 xn+i 0，i = 1 , m； 構(gòu)造: Max z = - xn+1 - x

48、n+2 - - xn+m s.t. a11x1+a12x2+ +a1nxn+xn+1 = b1 a21x1+a22x2+ +a2nxn+xn+2 = b2 . . . am1x1+am2x2+ +amnxn+xn+m = bm x1,x2 . xn ,xn+1,xn+m 03.3.單單 純純 形形 法法第118頁/共564頁119 第一階段求解上述問題： 顯然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解,它對應(yīng)的基 是單位矩陣。 結(jié)論：若得到的最優(yōu)解滿足 xn+i=0 i=1 , , m 則是原問題的基本可行解;否則，原問題無可行解。 得到原問題

49、的基本可行解后，第二階段求解原問題。3.3.單單 純純 形形 法法第119頁/共564頁120例2.11：（LP）Max z = 5x1 + 2x2 + 3x3 - x4 s.t. x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 03.3.單單 純純 形形 法法第120頁/共564頁121 Max z = 5x1+2x2+3x3-x4-Mx5-Mx6 s.t. x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6 =20 x1+2x2+4x3+x4 =26 x1 ,x

50、2 ,x3 ,x4 ,x5 ,x6 03.3.單單 純純 形形 法法第121頁/共564頁1225 2 3 -1 -M -M CB XB x1 x2 x3 x4 x5 x6 i -M x5 15 1 2 3 0 1 0 5 -M x6 20 2 1 (5) 0 0 1 4 -1 x4 26 1 2 4 1 0 0 6.5 -z 35M+26 3M+6 3M+4 8M+7 0 0 0 -M x5 3 -1/5 (7/5) 0 0 1 -3/5 15/7 3 x3 4 2/5 1/5 1 0 0 1/5 20 -1 x4 10 -3/5 6/5 0 1 0 -4/5 25/3 -z 3M-2 -M

51、/5+16/5 7/5M+13/5 0 0 0 -8/5M-7/5 2 x2 15/7 -1/7 1 0 0 5/7 -3/7 3 x3 25/7 (3/7) 0 1 0 -1/7 2/7 25/3 -1 x4 52/7 -3/7 0 0 1 -6/7 -2/7 -z -53/7 25/7 0 0 0 -M-13/7 -M-2/7 2 x2 10/3 0 1 1/3 0 2/3 -1/3 5 x1 25/3 1 0 7/3 0 -1/3 2/3 -1 x4 11 0 0 1 1 -1 0 -z -112/3 0 0 -25/3 0 -M-2/3 -M+8/3 大大M M法法 （LP - M）

52、得到最優(yōu)解：(25/3，10/3，0，11)T 最優(yōu)目標(biāo)值：112/33.3.單單 純純 形形 法法第122頁/共564頁123 第一階段問題（LP - 1） Max z = - x5 - x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 03.3.單單 純純 形形 法法第123頁/共564頁1240000-1-1CBXBx1x2x3x4x5x6i-1x5151230105-1x62021(5)00140 x42612410

53、06.5-z35338000-1x53-1/5(7/5)001-3/515/70 x342/51/51001/5200 x410-3/56/5010-4/525/3-z3-1/57/5000-8/50 x215/7-1/71005/7-3/70 x325/73/7010-1/72/725/30 x452/7-3/7001-6/7-2/7-z00000-1-1第一階段第一階段 (LP - 1） 得到原問題的基本可行解: (0，15/7，25/7，52/7)T 3.3.單單 純純 形形 法法第124頁/共564頁125523-1CBXBx1x2x3x4i2x215/7-1/71003x325/7(

54、3/7)01025/3-1x452/7-3/7001-z-53/725/70002x210/3011/305x125/3107/30-1x4110011-z-112/300-25/30第二階段第二階段 把基本可行解填入表中 得到原問題的最優(yōu)解:(25/3，10/3，0，11)T 最優(yōu)目標(biāo)值：112/33.3.單單 純純 形形 法法第125頁/共564頁126 注意：單純形法中 1、每一步運(yùn)算只能用矩陣初等行變換； 2、表中第3列(b列)的數(shù)總應(yīng)保持非負(fù)（0）； 3、當(dāng)所有檢驗(yàn)數(shù)均非正（0）時，得到最優(yōu)單純形表。若直接對目標(biāo)求最h，要求所有檢驗(yàn)數(shù)均非負(fù)； 4、當(dāng)最優(yōu)單純形表存在非基變量對應(yīng)的檢驗(yàn)

55、數(shù)為零時，可能存在無窮多解；3.3.單單 純純 形形 法法第126頁/共564頁127 5、關(guān)于退化和循環(huán)。如果在一個基本可行解的基變量中至少有一個分量xBi=0 (i=1,2,m)，則稱此基本可行解是退化的基本可行解。一般情況下，退化的基本可行解（極點(diǎn)）是由若干個不同的基本可行解（極點(diǎn)）在特殊情況下合并成一個基本可行解（極點(diǎn)）而形成的。退化的結(jié)構(gòu)對單純形迭代會造成不利的影響。3.3.單單 純純 形形 法法第127頁/共564頁128 可能出現(xiàn)以下情況： 進(jìn)行進(jìn)基、出基變換后，雖然改變了基，但沒有改變基本可行解（極點(diǎn)），目標(biāo)函數(shù)當(dāng)然也不會改進(jìn)。進(jìn)行若干次基變換后，才脫離退化基本可行解（極點(diǎn)），

56、進(jìn)入其他基本可行解（極點(diǎn)）。這種情況會增加迭代次數(shù)，使單純形法收斂的速度減慢。 在特殊情況下，退化會出現(xiàn)基的循環(huán)，一旦出現(xiàn)這樣的情況，單純形迭代將永遠(yuǎn)停留在同一極點(diǎn)上，因而無法求得最優(yōu)解。3.3.單單 純純 形形 法法第128頁/共564頁129 在單純形法求解線性規(guī)劃問題時，一旦出現(xiàn)這種因退化而導(dǎo)致的基的循環(huán)，單純形法就無法求得最優(yōu)解，這是一般單純形法的一個缺陷。但是實(shí)際上，盡管退化的結(jié)構(gòu)是經(jīng)常遇到的，而循環(huán)現(xiàn)象在實(shí)際問題中出現(xiàn)得較少。盡管如此，人們還是對如何防止出現(xiàn)循環(huán)作了大量研究。1952年Charnes提出了“攝動法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法

57、”，3.3.單單 純純 形形 法法第129頁/共564頁130 這些方法都比較復(fù)雜，同時也降低了迭代的速度。1976年，Bland提出了一個避免循環(huán)的新方法，其原則十分簡單。僅在選擇進(jìn)基變量和出基變量時作了以下規(guī)定： 在選擇進(jìn)基變量時，在所有 j 0的非基變量中選取下標(biāo)最小的進(jìn)基； 當(dāng)有多個變量同時可作為出基變量時，選擇下標(biāo)最小的那個變量出基。這樣就可以避免出現(xiàn)循環(huán),當(dāng)然，這樣可能使收斂速度降低。3.3.單單 純純 形形 法法第130頁/共564頁131 合理利用線材問題：如何下料使用材最少。 配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤。 投資問題：從投資項(xiàng)目中選取方案，使投資回報最大。4

58、.4.線性規(guī)劃應(yīng)用 一、線性規(guī)劃一、線性規(guī)劃-第131頁/共564頁132產(chǎn)品生產(chǎn)計劃：產(chǎn)品生產(chǎn)計劃：合理利用人合理利用人力、物力、財力等，使獲利最力、物力、財力等，使獲利最大。大。勞動力安排：勞動力安排：用最少的勞動用最少的勞動力來滿足工作的需要。力來滿足工作的需要。運(yùn)輸問題：運(yùn)輸問題：如何制定調(diào)運(yùn)方如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。案，使總運(yùn)費(fèi)最小。4.4.線性規(guī)劃應(yīng)用線性規(guī)劃應(yīng)用第132頁/共564頁133 數(shù)學(xué)規(guī)劃的建模有許多共同點(diǎn)，要遵循下列原則： (1)容易理解。建立的模型不但要求建模者理解，還應(yīng)當(dāng)讓有關(guān)人員理解。這樣便于考察實(shí)際問題與模型的關(guān)系，使得到的結(jié)論能夠更好地應(yīng)用于解決實(shí)際

59、問題。 (2)容易查找模型中的錯誤。這個原則的目的顯然與(1)相關(guān)。常出現(xiàn)的錯誤有：書寫錯誤和公式錯誤。4.4.線性規(guī)劃應(yīng)用線性規(guī)劃應(yīng)用第133頁/共564頁134 (3)容易求解。對線性規(guī)劃來說，容易求解問題主要是控制問題的規(guī)模，包括決策變量的個數(shù)和約束條件的個數(shù)。這條原則的實(shí)現(xiàn)往往會與(1)發(fā)生矛盾，在實(shí)現(xiàn)時需要對兩條原則進(jìn)行統(tǒng)籌考慮。4.4.線性規(guī)劃應(yīng)用線性規(guī)劃應(yīng)用第134頁/共564頁135 建立線性規(guī)劃模型的過程可以分為四個步驟： (1)設(shè)立決策變量； (2)明確約束條件并用決策變量的線性等式或不等式表示； (3)用決策變量的線性函數(shù)表示目標(biāo)，并確定是求極大（Max）還是極?。∕in

60、）； (4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。4.4.線性規(guī)劃應(yīng)用線性規(guī)劃應(yīng)用第135頁/共564頁136 例2.12：某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下： 班次時間所需人數(shù)16：00 10：0060210：00 14：0070314：00 18：0060418：00 22：0050522： 2：002062：00 6：0030 人力資源分配的問題設(shè)司機(jī)和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作8h，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?第136頁/共564頁137 解：設(shè) xi 表示第i班次時開始上班的司機(jī)和乘