線性規(guī)劃教學(xué)課件、

《線性規(guī)劃教學(xué)課件、》由會員分享，可在線閱讀，更多相關(guān)《線性規(guī)劃教學(xué)課件、（137頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第一章第一章 線性規(guī)劃線性規(guī)劃(Linear Programming)線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃圖解法線性規(guī)劃圖解法線性規(guī)劃問題解的性質(zhì)線性規(guī)劃問題解的性質(zhì) 單純形法單純形法 單純形法的其他問題討論單純形法的其他問題討論 線性規(guī)劃應(yīng)用舉例線性規(guī)劃應(yīng)用舉例 WinQSBWinQSB軟件應(yīng)用軟件應(yīng)用線性規(guī)劃的基本特點(diǎn)線性規(guī)劃的基本特點(diǎn)uLPLP是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一；是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一；uLPLP是運(yùn)籌學(xué)中最基本的方法之一，網(wǎng)絡(luò)分析、整是運(yùn)籌學(xué)中最基本的方法之一，網(wǎng)絡(luò)分析、整數(shù)規(guī)劃、目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃等都是以數(shù)規(guī)劃、目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃等都是以L

2、PLP為基為基礎(chǔ)的；礎(chǔ)的；u解決稀缺資源最優(yōu)分配的有效方法，是付出的費(fèi)解決稀缺資源最優(yōu)分配的有效方法，是付出的費(fèi)用最小或獲得的收益最大用最小或獲得的收益最大線性規(guī)劃的研究對象線性規(guī)劃的研究對象u有一定的人力、財(cái)力、資源條件下，如何合理安有一定的人力、財(cái)力、資源條件下，如何合理安排使用，效益最高；排使用，效益最高；u某項(xiàng)任務(wù)確定后，如何安排人、財(cái)、物，使之最某項(xiàng)任務(wù)確定后，如何安排人、財(cái)、物，使之最省省典型應(yīng)用典型應(yīng)用合理利用線材問題：如何下料，使用材最少？配料問題：在原料供應(yīng)量的限制下，如何獲得最大利潤？投資問題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物、財(cái)?shù)?，使獲利

3、最大勞動力安排：用最少的勞動力來滿足工作的安排運(yùn)輸問題：如何制定調(diào)整方案，使總運(yùn)費(fèi)最??？第一節(jié)第一節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 一、線性規(guī)劃問題的提出一、線性規(guī)劃問題的提出p有多少種配比方案？為什麼？有多少種配比方案？為什麼？p何為最好？何為最好？ 產(chǎn)產(chǎn) 品品資資 源源 甲甲乙乙每天可用于產(chǎn)品生產(chǎn)每天可用于產(chǎn)品生產(chǎn)的資源量的資源量設(shè)備設(shè)備1116材料材料A3236材料材料B565利潤（元）利潤（元）9070【例【例1-11-1】已知某企業(yè)生產(chǎn)資料如下表所示，問如何安排生產(chǎn)】已知某企業(yè)生產(chǎn)資料如下表所示，問如何安排生產(chǎn)才能企業(yè)使利潤最大？才能企業(yè)使利潤最大？數(shù)學(xué)模型：數(shù)學(xué)

4、模型： x1 0 , x2 0s.t.設(shè)甲產(chǎn)品的生產(chǎn)量為設(shè)甲產(chǎn)品的生產(chǎn)量為x x1 1, ,乙產(chǎn)品的生產(chǎn)量為乙產(chǎn)品的生產(chǎn)量為x x2 2，則：，則：217090maxxxz1621 xx362321 xx6552x 【例【例1-21-2】設(shè)某種動物每天需要攝入的蛋白質(zhì)、礦物質(zhì)、維設(shè)某種動物每天需要攝入的蛋白質(zhì)、礦物質(zhì)、維生素的最低量及生素的最低量及A A、B B、C C、D D、E E五種飼料每公斤營養(yǎng)成分的含五種飼料每公斤營養(yǎng)成分的含量及單位價(jià)格如下表所示。要求既滿足該種動物每天營養(yǎng)成分量及單位價(jià)格如下表所示。要求既滿足該種動物每天營養(yǎng)成分的需要量，又使總的費(fèi)用最省。的需要量，又使總的費(fèi)用最

5、省。 目標(biāo)函數(shù)：目標(biāo)函數(shù)： 滿足約束條件滿足約束條件 ABCDE每天最低攝入量(克)蛋白質(zhì)(克)礦物質(zhì)(克)維生素(克)310.520.5110.20.2622180.50.870030100價(jià)格(元/千克)27438設(shè)設(shè) 為第為第j j種飼料的每天使用量，則：種飼料的每天使用量，則：jx5432183472minxxxxxz0,1008 . 022 . 05 . 0305 . 022 . 05 . 07001862354321543215432154321xxxxxxxxxxxxxxxxxxxx jx二、線性規(guī)劃問題數(shù)學(xué)模型的一般形式二、線性規(guī)劃問題數(shù)學(xué)模型的一般形式3.3.線性規(guī)劃問題數(shù)學(xué)

6、模型的組成要素：線性規(guī)劃問題數(shù)學(xué)模型的組成要素： (1) (1)變量，或稱決策變量變量，或稱決策變量，它們是問題中所要解決的未知量，它們是問題中所要解決的未知量，表明規(guī)劃中用數(shù)量表示的方案、措施，可由決策者決定和控制；表明規(guī)劃中用數(shù)量表示的方案、措施，可由決策者決定和控制； (2 (2) )目標(biāo)函數(shù)目標(biāo)函數(shù)，是決策變量的函數(shù)，按問題的目標(biāo)不同分別是決策變量的函數(shù)，按問題的目標(biāo)不同分別在這個(gè)函數(shù)前加上在這個(gè)函數(shù)前加上maxmax或或minmin； (3)(3)約束條件約束條件，由一組含決策變量的等式或不等式組成，由一組含決策變量的等式或不等式組成，表明決策變量取值時(shí)所受到的各種資源條件的限制。表

7、明決策變量取值時(shí)所受到的各種資源條件的限制。 假定線性規(guī)劃問題中含有假定線性規(guī)劃問題中含有n n個(gè)決策變量個(gè)決策變量x xj j(j(j1 1，n)n)，在目標(biāo)函數(shù)中在目標(biāo)函數(shù)中x xj j的系數(shù)為的系數(shù)為c cj j(c(cj j通常稱為價(jià)值系數(shù)通常稱為價(jià)值系數(shù)) )；有；有m m種資源種資源的限制，每種資源數(shù)量用的限制，每種資源數(shù)量用b bi i(i(i=1,.m)=1,.m)表示；用表示；用a aijij表示變量表示變量x xj j取值為取值為1 1個(gè)單位時(shí)所消耗或含有的第個(gè)單位時(shí)所消耗或含有的第i i種資源的數(shù)量，通常稱種資源的數(shù)量，通常稱a aijij為技術(shù)系數(shù)或消耗系數(shù)。為技術(shù)系數(shù)

8、或消耗系數(shù)。 nnxcxcxcz2211 (min) max目標(biāo)函數(shù)：目標(biāo)函數(shù)：約束條件：約束條件：線性規(guī)劃問題的數(shù)學(xué)模型的一般形式：線性規(guī)劃問題的數(shù)學(xué)模型的一般形式：11212111 )( bxaxaxann 22222121 )( bxaxaxannmnmnmmbxaxaxa )( 22110 ,21nxxx為目標(biāo)函數(shù)；為目標(biāo)函數(shù)；為資源約束；為資源約束；為非負(fù)約束。為非負(fù)約束。x xj j決策變量；決策變量；c cj j價(jià)值系數(shù)；價(jià)值系數(shù)；a aijij技術(shù)（消耗）系數(shù)；技術(shù)（消耗）系數(shù)；b bi i資源常量，資源常量，b bi i0線性規(guī)劃模型的簡寫形式為線性規(guī)劃模型的簡寫形式為：nj

9、jjxc1 z min)(max 或目標(biāo)函數(shù)：目標(biāo)函數(shù)：約束條件：約束條件：)21(j0)21(i )(1nxmbxajnjijij、式中：式中：) , , , (21ncccC=nxxX1 mjjjaap1 mbbb1用向量形式表達(dá)時(shí)，模型可寫為用向量形式表達(dá)時(shí)，模型可寫為：= 0 )(. (min) maxjjjxbxptsCXz，或矩陣形式為：矩陣形式為：2212222111211mmmnnaaaaaaaaaACXz min)( max或 0 )(.XbAXts或其中：其中：A A為約束方程組（約束條件）的系數(shù)矩陣。為約束方程組（約束條件）的系數(shù)矩陣。三、線性規(guī)劃問題的標(biāo)準(zhǔn)形式三、線性規(guī)

10、劃問題的標(biāo)準(zhǔn)形式njjjxczMax1), 1(0), 1(. .1njxmibxatsjnjijij化一般形式為標(biāo)準(zhǔn)形式的方法：化一般形式為標(biāo)準(zhǔn)形式的方法： 1 1、目標(biāo)函數(shù)為求極小值，即為、目標(biāo)函數(shù)為求極小值，即為: :njjjxcz1minnjjjxczMax1因?yàn)榍笠驗(yàn)榍驧in zMin z，等價(jià)于求，等價(jià)于求Max(-z)Max(-z)，令，令z=-zz=-z，即化為：，即化為：2 2右端項(xiàng)右端項(xiàng)b bi i0 0 只需將等式或不等式兩端同乘只需將等式或不等式兩端同乘(-1)(-1)，則等式右端項(xiàng)必大于，則等式右端項(xiàng)必大于零。零。 3 3約束條件為不等式：約束條件為不等式： 當(dāng)約束條

11、件為當(dāng)約束條件為“”時(shí)，需將約束條件左端加松弛變量；時(shí)，需將約束條件左端加松弛變量； 當(dāng)約束條件為當(dāng)約束條件為“”時(shí)，需將約束條件左端減去剩余變時(shí)，需將約束條件左端減去剩余變量。量。4 4取值無約束的變量取值無約束的變量 可令可令x xx-xx-x”，其中，其中x0 x0，x”0 x”0 5 5對對x0 x0的情況的情況 令令xx-x-x，顯然，顯然x0 x0 【例【例1-31-3】將下述線性規(guī)劃化為標(biāo)準(zhǔn)形式】將下述線性規(guī)劃化為標(biāo)準(zhǔn)形式 解：解：上述問題中令：上述問題中令：取值無約束321321321321321, 0, 0632442392. .32minxxxxxxxxxxxxtsxxxz

12、ZZ 得到得到 ZZmax11xx 333xxx 在第一個(gè)約束條件的左端加入一個(gè)松弛變量在第一個(gè)約束條件的左端加入一個(gè)松弛變量 )0(44xx在第二個(gè)約束條件是左端減去一個(gè)剩余變量在第二個(gè)約束條件是左端減去一個(gè)剩余變量 )0(55xx將第三個(gè)約束條件兩端同乘將第三個(gè)約束條件兩端同乘“-1” -1” 該問題的標(biāo)準(zhǔn)形式為：該問題的標(biāo)準(zhǔn)形式為： 0,63324422392. .00332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz第二節(jié)第二節(jié) 線性規(guī)劃線性規(guī)劃圖解法圖解法一、什么是圖解法一、什么是圖解法二、圖解法步驟二、圖解法步

13、驟【例例1-41-4】用圖解法求解下列線性規(guī)劃問題：】用圖解法求解下列線性規(guī)劃問題： 三、圖解法舉例三、圖解法舉例 圖解法的步驟可概括為：圖解法的步驟可概括為： ( (一一) )建立平面直角坐標(biāo)系；建立平面直角坐標(biāo)系； ( (二二) )利用約束條件，確定線性規(guī)劃問題解的可行域；利用約束條件，確定線性規(guī)劃問題解的可行域； ( (三三) )繪制目標(biāo)函數(shù)的等值線和法線；繪制目標(biāo)函數(shù)的等值線和法線； ( (四四) )沿法線方向移動目標(biāo)函數(shù)等值線至可行域的邊緣，沿法線方向移動目標(biāo)函數(shù)等值線至可行域的邊緣，尋求問題最優(yōu)解。若該問題存在最優(yōu)解，則在可行域的邊緣得尋求問題最優(yōu)解。若該問題存在最優(yōu)解，則在可行域

14、的邊緣得到問題的最優(yōu)解。到問題的最優(yōu)解。 0,655362316. .7090max212212121xxxxxxxtsxxz)()()()(dcba0 x2 x10,6553623167090max212212121xxxxxxxxxz)()()()(dcba(a)(b)(c)(4,12)可行域可行域等值線等值線 最優(yōu)解：最優(yōu)解：x1 = 4， x2 = 12最優(yōu)目標(biāo)函數(shù)值：最優(yōu)目標(biāo)函數(shù)值：z = 1200z = 12000 x2 x1(a)(b)(c)四、線性規(guī)劃問題解的可能結(jié)果四、線性規(guī)劃問題解的可能結(jié)果 （一）無窮多最優(yōu)解（一）無窮多最優(yōu)解0,6553623166090max21221

15、2121xxxxxxxxxz)()()()(dcba (二二)無界解無界解0,6556090max21221xxxxxz (三三)無解無解2123maxxxz0,622212121xxxxxx五、圖解法求解線性規(guī)劃問題給我們的啟示五、圖解法求解線性規(guī)劃問題給我們的啟示p線性規(guī)劃的可行域是一個(gè)什么形狀？ 多邊形，而且是“凸”形的多邊形。p最優(yōu)解在什么位置獲得？ 在邊界，而且是在某個(gè)頂點(diǎn)獲得。思考結(jié)論：p線性規(guī)劃的約束集（即可行域）是一個(gè)凸多面體。凸多面體是凸集的一種。所謂凸集是指：集中任兩點(diǎn)的連 線仍屬此集。p線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行域的頂點(diǎn)獲得。因?yàn)椋蓤D解法可知，只有當(dāng)目標(biāo)直

16、線平移到邊界時(shí)， 才能使目標(biāo)函數(shù)值z達(dá)到最大限度的優(yōu)化。問題：本性質(zhì)有何重要意義？ 它使得在可行域中尋優(yōu)的工作由“無限”上升為“有 限”，從而為線性規(guī)劃的算法設(shè)計(jì)提供了重要基礎(chǔ)。p線性規(guī)劃解的幾種情況線性規(guī)劃解的幾種情況1、可行域?yàn)榉忾]的有界區(qū)域(a)有唯一的最優(yōu)解；(b)有一個(gè)以上的最優(yōu)解；2、可行域?yàn)榉欠忾]的無界區(qū)域(a)有唯一的最優(yōu)解；(b)有一個(gè)以上的最優(yōu)解；(c)目標(biāo)函數(shù)無界（即雖有可行解，但在可行域中，目標(biāo)函數(shù)可以無限增大或無限減?。蚨鴽]有最優(yōu)解。3、可行域?yàn)榭占蚨鴽]有可行解。第三節(jié)第三節(jié) 線性規(guī)劃問題解的性質(zhì)線性規(guī)劃問題解的性質(zhì) 1. .滿足所有約束滿足所有約束條件（包括

17、非負(fù)條件）條件（包括非負(fù)條件）的解。的解。 可行解的集合稱為可行可行解的集合稱為可行集，或可行域。集，或可行域。 2. .使目標(biāo)函數(shù)達(dá)使目標(biāo)函數(shù)達(dá)到極值的解（理應(yīng)屬于到極值的解（理應(yīng)屬于可行解集）?？尚薪饧?040B30 x2x1O4x1+5x2 2003x1+10 x2 3009x1+4x2 36010040 50可行解可行解可行域可行域最優(yōu)解最優(yōu)解原原LP：Max Z=7x1+12x2 s.t. 0,300103200543604921212121xxxxxxxxm為約束方程的個(gè)數(shù)，為約束方程的個(gè)數(shù)， n為變量的個(gè)數(shù)，為變量的個(gè)數(shù)，約束方程組約束方程組的系數(shù)矩陣的系數(shù)矩陣A（ m n

18、），且），且m 0 x5=60 因此因此。 這種用來確定出基變量的規(guī)則稱為這種用來確定出基變量的規(guī)則稱為 。 新的基變量新的基變量x1,x5x1,x5；新的非基變量；新的非基變量x2,x3,x4x2,x3,x4； 寫出寫出 當(dāng)用非基變量表示目標(biāo)函數(shù)的表達(dá)式中，當(dāng)用非基變量表示目標(biāo)函數(shù)的表達(dá)式中，時(shí)，時(shí)，當(dāng)前的基本可行解就是當(dāng)前的基本可行解就是! ! 為什麼？為什麼？ 分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式，分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式，如果如果，基本思路基本思路: : 先找出一個(gè)基可行解，判斷其是否為最優(yōu)解，如果為否，則先找出一個(gè)基可行解，判斷其是否為最優(yōu)解，如果為否，則轉(zhuǎn)換到相鄰的基可行解

19、，并使目標(biāo)函數(shù)值不斷增大，直到找到最轉(zhuǎn)換到相鄰的基可行解，并使目標(biāo)函數(shù)值不斷增大，直到找到最優(yōu)解為止。優(yōu)解為止。二、單純形法的求解步驟二、單純形法的求解步驟1.1.確定初始基可行解確定初始基可行解 1maxnjjjxcz=)4 . 1 (), 1(0)3 . 1 (1njxbxPjnjjj對于標(biāo)準(zhǔn)形的線性規(guī)劃問題：對于標(biāo)準(zhǔn)形的線性規(guī)劃問題： 約束條件的變量的系數(shù)矩陣中總會存在一個(gè)單位矩陣：約束條件的變量的系數(shù)矩陣中總會存在一個(gè)單位矩陣：=100010001),(21mPPP 當(dāng)約束條件均為當(dāng)約束條件均為號時(shí)，加上松弛變量號時(shí)，加上松弛變量x xs1s1,x,xs2s2, ,x,xsmsm的系數(shù)

20、的系數(shù)矩陣即為單位矩陣。矩陣即為單位矩陣。mPP,1mxx,1nmmxxx,21稱為基向量，同其對應(yīng)的變量稱為基向量，同其對應(yīng)的變量稱為基變量，稱為基變量，模型中的其它變量模型中的其它變量稱為非基變量。稱為非基變量。用非基變量表示基變量可得到：用非基變量表示基變量可得到：=+nmnmmmmmmmmnnmmmmnnmmmmxaxaxabxxaxaxabxxaxaxabx22,11,222, 211, 222122, 111, 111TmTnmmbbxxxxX)0 , 0 ,(),(111)0(=+令所有非基變量等于零，即可找到一個(gè)解令所有非基變量等于零，即可找到一個(gè)解: :簡寫為：簡寫為：nin

21、mmimmiiixaxaxabx22,11,+=(1.5)2.2.最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) 將將(1.5)(1.5)式代入目標(biāo)函數(shù)：式代入目標(biāo)函數(shù)： 1njjjxcZ=11nmjjjmiiixcxc+=+=111nmjjjminmjjijiixcxabc+=+=+=111nmjjmiijijmiiixaccbc+=+=設(shè)：設(shè)：10miijiacz=則：則：jjjzc =檢驗(yàn)數(shù)檢驗(yàn)數(shù)1miijijjacc=設(shè)：設(shè)：10miijiacz=則：則：jjjzc =檢驗(yàn)數(shù)檢驗(yàn)數(shù)1miijijjacc= TmkbbbX0 , 0 ,21nmjxj, 10j0lm 定理定理1.51.5（無窮多最優(yōu)解）（無窮多最

22、優(yōu)解）設(shè)設(shè) 為對應(yīng)為對應(yīng)于基于基B B的一個(gè)基可行解，且對于一切的一個(gè)基可行解，且對于一切 有有 ，同時(shí)又存在某個(gè)非基變量的檢驗(yàn)數(shù)同時(shí)又存在某個(gè)非基變量的檢驗(yàn)數(shù) ，則線性規(guī)劃問題存，則線性規(guī)劃問題存在無窮多最優(yōu)解。在無窮多最優(yōu)解。 TmkbbbX0 , 0 ,21nmjxj, 10j kX 定理定理1.41.4（最優(yōu)解）（最優(yōu)解）設(shè)設(shè) 為對應(yīng)于基為對應(yīng)于基B B的的一個(gè)基可行解，且對于一個(gè)基可行解，且對于 一切有一切有 ，則，則 為線為線性規(guī)劃問題的最優(yōu)解。性規(guī)劃問題的最優(yōu)解。 TmkbbbX0 , 0 ,210lmmialmi, 10, 定理定理1.61.6（無界解）（無界解）設(shè)設(shè) 為對應(yīng)于

23、基為對應(yīng)于基B B的的一個(gè)基可行解，存在某個(gè)非基變量的檢驗(yàn)數(shù)一個(gè)基可行解，存在某個(gè)非基變量的檢驗(yàn)數(shù) ，且，且有有 ，則線性規(guī)劃問題具有無界解。，則線性規(guī)劃問題具有無界解。3.3.尋找新的基可行解尋找新的基可行解 確定進(jìn)基變量確定進(jìn)基變量 lmjjnmj+=+=, 1, 0max對應(yīng)的變量對應(yīng)的變量 為進(jìn)基變量。為進(jìn)基變量。lmx確定離基變量確定離基變量 lmhhlmilmiiabmiaab+=, 1, 0min對應(yīng)的變量對應(yīng)的變量 為離基變量。為離基變量。hx迭代計(jì)算迭代計(jì)算 lmPlmha,lmha,lmP 對于列向量對于列向量 ，以，以 為主元素，將為主元素，將 變?yōu)樽優(yōu)? 1，其余變?yōu)椋?/p>

24、其余變?yōu)? 0，即將向量，即將向量 變換為單位向量。變換為單位向量。 重復(fù)重復(fù)2 2、3 3直到所有的檢驗(yàn)數(shù)小于等于直到所有的檢驗(yàn)數(shù)小于等于0 0為止，則問題得到最為止，則問題得到最優(yōu)解。優(yōu)解。 第第1 1步：確定初始基可行解，列出初始單純形表。步：確定初始基可行解，列出初始單純形表。 為了書寫規(guī)范和便于計(jì)算，對單純形法的計(jì)算設(shè)計(jì)了一種為了書寫規(guī)范和便于計(jì)算，對單純形法的計(jì)算設(shè)計(jì)了一種專門表格，稱為單純形表。專門表格，稱為單純形表。 jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001Ziibc0 0 ijijja

25、cc 二、單純形表二、單純形表 第第2 2步：最優(yōu)性檢驗(yàn)。步：最優(yōu)性檢驗(yàn)。 如表中所有檢驗(yàn)數(shù)如表中所有檢驗(yàn)數(shù)j j00，且基變量中不含有人工變量時(shí)，且基變量中不含有人工變量時(shí)，表中的基可行解即為最優(yōu)解，計(jì)算結(jié)束。對基變量中含人工變表中的基可行解即為最優(yōu)解，計(jì)算結(jié)束。對基變量中含人工變量時(shí)的解的最優(yōu)性檢驗(yàn)將在下一節(jié)中討論。當(dāng)表中存在量時(shí)的解的最優(yōu)性檢驗(yàn)將在下一節(jié)中討論。當(dāng)表中存在j j00又又P Pj j000，對應(yīng)的變量，對應(yīng)的變量x xj j就可作為換入基的變量，就可作為換入基的變量，當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于零時(shí)，一般從中找出最大一個(gè)當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于零時(shí)，一般從中找出最大一個(gè)k k。0|

26、maxjjlmlmx作為進(jìn)基變量作為進(jìn)基變量( (也稱換入變量也稱換入變量) )確定進(jìn)基變量。確定進(jìn)基變量。 確定離基變量。確定離基變量。 根據(jù)最小根據(jù)最小的規(guī)則確定：的規(guī)則確定： lmhhlmilmiiaboaab,|minhx確定確定是離基的變量是離基的變量( (也稱換出變量也稱換出變量) )。lmha,元素元素 決定了從一個(gè)基可行解到相鄰基可行解的轉(zhuǎn)移去向，決定了從一個(gè)基可行解到相鄰基可行解的轉(zhuǎn)移去向，取名主元素。取名主元素。 以以a ah,m+lh,m+l，為主元素進(jìn)行迭代。，為主元素進(jìn)行迭代。 迭代計(jì)算迭代計(jì)算 第第4 4步：重復(fù)第步：重復(fù)第2 2，3 3兩步，直到所有的檢驗(yàn)數(shù)小于等

27、于兩步，直到所有的檢驗(yàn)數(shù)小于等于0 0時(shí)，時(shí)，計(jì)算結(jié)束。計(jì)算結(jié)束?！纠纠?-51-5】用單純形法求解線性規(guī)劃問題】用單純形法求解線性規(guī)劃問題 0,6553623167090max212212121xxxxxxxxxz解：解：將上述問題化為標(biāo)準(zhǔn)形式有：將上述問題化為標(biāo)準(zhǔn)形式有： 0,6553623167090max543215242132121xxxxxxxxxxxxxxxz其約束條件系數(shù)矩陣為：其約束條件系數(shù)矩陣為： 100500102300111列出初始單純形表為：列出初始單純形表為： cj 90 70 0 0 0 cBxBb x1 x2 x3 x4 x5000 x3x4x5163665

28、1 1 1 0 0 3 2 0 1 0 0 5 0 0 1j i36/316/10900 x3x1x5 j90070000651215001001/32/370901x2x1x5 j401/31-1/300100-30012181312013-10500-1551410-2100-300-20-1/2Max z2xl+x2 0,21xx52x 2461x 1552x22xx1例：利用單純形法求解下列問題例：利用單純形法求解下列問題化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型 0,54321xxxxx 15532xx 0002max54321xxxxxz 552xxx1 24641xx 2x2cj 2 1 0 0 0

29、cBxBb x1 x2 x3 x4 x5000 x3x4x515245 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1j i24/65/1020 x3x1x5 j2010001412/30-1/61001/61/3021x3x1x2 j150510001/30-1/303123/215/20015/4-15/23/2010-1/43/27/21001/4-1/2000-1/4-1/2建立初始單純形表如下：建立初始單純形表如下：第五節(jié)第五節(jié) 單純形法的其他問題討論單純形法的其他問題討論一、關(guān)于標(biāo)準(zhǔn)形為最小化問題一、關(guān)于標(biāo)準(zhǔn)形為最小化問題目標(biāo)函數(shù)為最小化的標(biāo)準(zhǔn)形式，最優(yōu)性檢驗(yàn)的判別定理

30、目標(biāo)函數(shù)為最小化的標(biāo)準(zhǔn)形式，最優(yōu)性檢驗(yàn)的判別定理 ： TmkbbbX0 , 0 ,21nmjxj, 10j kX 定理定理1.71.7（最優(yōu)解）（最優(yōu)解）設(shè)設(shè) 為對應(yīng)于基為對應(yīng)于基B B的一個(gè)基可行解，且對于一切的一個(gè)基可行解，且對于一切 有有 ，則，則 為線性規(guī)劃問題的最優(yōu)解。為線性規(guī)劃問題的最優(yōu)解。 TmkbbbX0 , 0 ,21nmjxj, 1 0j0lm 定理定理1.81.8（無窮多最優(yōu)解）（無窮多最優(yōu)解）設(shè)設(shè) 為對為對應(yīng)于基應(yīng)于基B B的一個(gè)基可行解，且對于一切的一個(gè)基可行解，且對于一切 有有 ，同時(shí)又存在某個(gè)非基變量的檢驗(yàn)數(shù)，同時(shí)又存在某個(gè)非基變量的檢驗(yàn)數(shù) ，則，則線線性規(guī)劃問題

31、存在無窮多最優(yōu)解。性規(guī)劃問題存在無窮多最優(yōu)解。 TmkbbbX0 , 0 ,210lmmialmi, 10, 定理定理1.91.9（無界解）（無界解）設(shè)設(shè) 為對應(yīng)于基為對應(yīng)于基B B的一個(gè)基可行解，存在某個(gè)非基變量的檢驗(yàn)數(shù)的一個(gè)基可行解，存在某個(gè)非基變量的檢驗(yàn)數(shù) ，且，且有有 ，則線性規(guī)劃問題具有無界解。，則線性規(guī)劃問題具有無界解。二、人工變量法二、人工變量法 【例【例1-61-6】用單純形法求解線性規(guī)劃問題】用單純形法求解線性規(guī)劃問題 0,12210243423max321321321321321xxxxxxxxxxxxxxxz解：解：將其化成標(biāo)準(zhǔn)形式有將其化成標(biāo)準(zhǔn)形式有 0,1221024

32、340023max543213215321432154321xxxxxxxxxxxxxxxxxxxxxz 上述標(biāo)準(zhǔn)化模型中，不存在單位矩陣，為構(gòu)造單位矩陣，則上述標(biāo)準(zhǔn)化模型中，不存在單位矩陣，為構(gòu)造單位矩陣，則需要通過添加人工變量的方法，人為構(gòu)造一個(gè)單位矩陣，該方需要通過添加人工變量的方法，人為構(gòu)造一個(gè)單位矩陣，該方法即所謂的人工變量法。法即所謂的人工變量法。 1. 1.大大M M法法 大大M M法又稱懲罰法，其法又稱懲罰法，其基本思想基本思想是：約束條件加入人工變量是：約束條件加入人工變量后，為使目標(biāo)函數(shù)取值不受影響，給定它們在求最大值后，為使目標(biāo)函數(shù)取值不受影響，給定它們在求最大值(max

33、)(max)的的目標(biāo)函數(shù)中的系數(shù)為目標(biāo)函數(shù)中的系數(shù)為(-M)(-M)(稱為懲罰因子，稱為懲罰因子，M M為任意大的正數(shù)為任意大的正數(shù)) )，以作為對基變量中存在人工變量的懲罰，從而迫使人工變量從以作為對基變量中存在人工變量的懲罰，從而迫使人工變量從基變量中分離出來，否則目標(biāo)函數(shù)將不能實(shí)現(xiàn)最大化。基變量中分離出來，否則目標(biāo)函數(shù)將不能實(shí)現(xiàn)最大化。 添加人工變量后，例添加人工變量后，例1-61-6的數(shù)學(xué)模型形式變?yōu)椋旱臄?shù)學(xué)模型形式變?yōu)椋?0,1221024340023max765432173215321643217654321xxxxxxxxxxxxxxxxxxxxMxMxxxxxxz列出初始單純形

34、表如下：列出初始單純形表如下： cj32-100- M- McBxBbx1X2x3x4x5x6x7- Mx64-431-101040 x5101-1201005- Mx712-2100011j3-2M2+M-1+2M-M000-mx60 x5- 1x3ji38-60-101-1-330010-2-2100011- 2M5-6M5M-M000213/58/32x20 x5-1x3j-6/53/510-1/501/5-1/531/5003/51-3/5-7/511/5-2/501-2/502/53/550000-M1-M53/531/32x21301012-1-33x131/310015/3-1-

35、7/3-1x319/300102/30-1/3j000-5-25/35-M38/3-M 計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只能用很大的數(shù)代替計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只能用很大的數(shù)代替M, ,可能造成計(jì)算可能造成計(jì)算機(jī)上的錯(cuò)誤，故多采用兩階段法。機(jī)上的錯(cuò)誤，故多采用兩階段法。 2 2、兩階段法、兩階段法第一階段：第一階段：添加人工變量，重新構(gòu)造目標(biāo)函數(shù)添加人工變量，重新構(gòu)造目標(biāo)函數(shù) 將原問題加入人工變量，構(gòu)造僅含人工變量的新的目標(biāo)函將原問題加入人工變量，構(gòu)造僅含人工變量的新的目標(biāo)函數(shù)，并要求實(shí)現(xiàn)最小化。新的目標(biāo)函數(shù)形式如下：數(shù)，并要求實(shí)現(xiàn)最小化。新的目標(biāo)函數(shù)形式如下： mnnnxxxw21min), 1, 2 , 1

36、(02211222222121111212111mnnnjxbxxaxaxabxxaxaxabxxaxaxajmmnnmnmmnnnnnn 求解上述線性規(guī)劃問題。若求解上述線性規(guī)劃問題。若w=0w=0，則原線性規(guī)劃問題存在，則原線性規(guī)劃問題存在基可行解，計(jì)算轉(zhuǎn)入第二階段；若基可行解，計(jì)算轉(zhuǎn)入第二階段；若w0w0，則原線性規(guī)劃問題無，則原線性規(guī)劃問題無可行解，計(jì)算停止?？尚薪?，計(jì)算停止。 第二階段：第二階段：對原目標(biāo)函數(shù)求解對原目標(biāo)函數(shù)求解 在第一階段的最終單純形表中，將才在第一階段的最終單純形表中，將才c cj j行的數(shù)字換為原目標(biāo)行的數(shù)字換為原目標(biāo)函數(shù)的系數(shù)，并且去掉表中含有人工變量的列，繼

37、續(xù)求解。函數(shù)的系數(shù)，并且去掉表中含有人工變量的列，繼續(xù)求解。 將例將例1-61-6問題利用兩階段法進(jìn)行求解。問題利用兩階段法進(jìn)行求解。 第一階段：添加人工變量，重新構(gòu)造目標(biāo)函數(shù)。例第一階段：添加人工變量，重新構(gòu)造目標(biāo)函數(shù)。例1-61-6用兩用兩階段法求解時(shí)，第一階段的線性規(guī)劃問題可寫為：階段法求解時(shí)，第一階段的線性規(guī)劃問題可寫為： 0,122102434min7654321732153216432176xxxxxxxxxxxxxxxxxxxxxxw將上述數(shù)學(xué)模型標(biāo)準(zhǔn)化后，用單純形法求解過程見下表：將上述數(shù)學(xué)模型標(biāo)準(zhǔn)化后，用單純形法求解過程見下表： cj00000- 1-1cBxBbx1X2x3

38、x4x5x6x7- 1x64-431-101040 x5101-1201005- 1x712-2100011j-212-1000-1x60 x50 x3ji38-60-101-1-330010-2-210001-2-65-100013/58/30 x20 x50 x3j-6/53/510-1/501/5-1/531/5003/51-3/5-7/511/5-2/501-2/502/53/500000-1-153/5可以看出：可以看出：W=0W=0，該問題有解；轉(zhuǎn)入第二階段。，該問題有解；轉(zhuǎn)入第二階段。cj32-100cBxBbx1x2x3x4x52x23/5-6/510-1/500 x531/5

39、3/5003/51-1x311/5-2/501-2/50j500002x213010123x131/310015/31x319/300102/3j000-5-22/3i第二階段：第二階段： 得最優(yōu)解。得最優(yōu)解。 將第一階段得到的最終單純形表的人工變量列去掉，將目將第一階段得到的最終單純形表的人工變量列去掉，將目標(biāo)標(biāo)C Cj j行換為原怒表函數(shù)的系數(shù)，再進(jìn)行迭代。行換為原怒表函數(shù)的系數(shù)，再進(jìn)行迭代。31/3三、單純形法計(jì)算中退化與循環(huán)問題三、單純形法計(jì)算中退化與循環(huán)問題 1 1、單純形法計(jì)算中按最小比值來確定離基變量時(shí)，有時(shí)存、單純形法計(jì)算中按最小比值來確定離基變量時(shí)，有時(shí)存在兩個(gè)以上相同的最小

40、比值，這樣在下一次迭代中就會出現(xiàn)一在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就會出現(xiàn)一個(gè)或多個(gè)基變量等于零的情形，這就出現(xiàn)了所謂的退化解。當(dāng)個(gè)或多個(gè)基變量等于零的情形，這就出現(xiàn)了所謂的退化解。當(dāng)存在退化解時(shí)，就有可能出現(xiàn)迭代計(jì)算的循環(huán)。存在退化解時(shí)，就有可能出現(xiàn)迭代計(jì)算的循環(huán)。 勃蘭特規(guī)則：勃蘭特規(guī)則： (1) (1)當(dāng)存在多個(gè)當(dāng)存在多個(gè) 且相等時(shí)，選取且相等時(shí)，選取 中下標(biāo)值最小中下標(biāo)值最小的變量作為進(jìn)基變量；的變量作為進(jìn)基變量； 0j0j (2) (2)當(dāng)按當(dāng)按規(guī)則計(jì)算出現(xiàn)兩個(gè)或兩個(gè)以上相同的最小比值時(shí)，規(guī)則計(jì)算出現(xiàn)兩個(gè)或兩個(gè)以上相同的最小比值時(shí)，選取下標(biāo)值最小的變量作為離基變量。選取下

41、標(biāo)值最小的變量作為離基變量。 2 2、為確定出基變量要計(jì)算比值，該比值、為確定出基變量要計(jì)算比值，該比值= =解解答列元素答列元素/ /主元列元素。主元列元素。 1212121min2.220(1,2)jzxxxxs txxxj （ ）12123124LPmax2.220(1,2,3,4)jzxxxxxs txxxxj 標(biāo)標(biāo)準(zhǔn)準(zhǔn)化化：15用用單單純純形形方方法法解解下下列列線線性性規(guī)規(guī)例例劃劃問問題題。四、解的其它情況四、解的其它情況列列單單純純形形表表：12343411000211100221011100jBBjjjCCXbxxxxxxcz 220iiiibaa (1)列列單單純純形形表表：

42、11140(0,2,0,4),2Xzxxx 1 1此此表表已已是是最最優(yōu)優(yōu)表表。但但非非基基變變量量 的的檢檢驗(yàn)驗(yàn)數(shù)數(shù)=0=0。選選擇擇 為為進(jìn)進(jìn)基基變變量量，只只有有為為出出基基變變量量，旋旋轉(zhuǎn)轉(zhuǎn)變變換換如如下下。(2)123424110002111004101100102jBBjjjCCXbxxxxxxcz 列列單單純純形形表表：123421110006012104101100102jBBjCCXbxxxxxx 2120(4,6,0,0) ,2LP(1)TXzXXX 此此表表也也是是最最優(yōu)優(yōu)表表。有有無無窮窮最最優(yōu)優(yōu)解解：(3)jjcz1212122max25.25100(1,2)jzxx

43、xxs txxxj （ ）12123124LPmax25.25100(1,2,3,4)jzxxxxxs txxxxj 標(biāo)標(biāo)準(zhǔn)準(zhǔn)化化：列列單單純純形形表表：123434210005111001025012100jBBjjjCCXbxxxxxxcz 110iiiibaa 列列單單純純形形表表：123431210001003 211 20515 201 20601jBBjjjCCXbxxxxxxcz LP有有進(jìn)進(jìn)基基變變量量，而而無無出出基基變變量量。無無最最優(yōu)優(yōu)解解。20 (1,2)iai121212max0.330(1,2)jzxxxxs txxxj ( (2 2) ) 5x解解（2 2）標(biāo)標(biāo)準(zhǔn)

44、準(zhǔn)化化后后，增增加加人人工工變變量量 ：1251231245max0.330(1,2,3,4,5)jzxxMxxxxs txxxxxj (2) (2) 12345351100001110033101113100jBBjjjCMCXbxxxxxxMxczMMM 1BCC B A (1,1,0,0,)(0,)MM-11100-11100-310-11-310-11(1,1,0,0,)(3,0,)MMMMM(13,1,0,0)MMM12345251100101110032011122010jBBjjjCMCXbxxxxxxMxczMMM LP5maxx 所所有有的的檢檢驗(yàn)驗(yàn)數(shù)數(shù)0,0,此此表表為為最

45、最優(yōu)優(yōu)表表（問問題題）, ,但但人人工工變變量量 (=3)(=3)仍仍為為基基變變量量, ,則則原原無無可可行行解解。12123123(2)min221.260(1,2,3)jzxxxxxs txxxxj - -1123461376752221260(1,2,3,4,5,6,7(n2mi)jxxxxxxxxxxxxxxxj 123456767000001111121101016121010172001100jBBCCXbxxxxxxxxx jjjcz 0j 則則原原問問題題無無可可行行解解，從從而而無無最最優(yōu)優(yōu)解解。70min 此此表表已已為為最最優(yōu)優(yōu)表表，121211212max203031

46、0150,30,40,0.zxxxxxxxx x標(biāo)數(shù)約條目函束件練習(xí)練習(xí)1 1：單純形表求解下列線性規(guī)劃問題：單純形表求解下列線性規(guī)劃問題121212212max5050300,2400,250,0.zxxxxxxxx xs.t練習(xí)練習(xí)2 2：用單純形法表求解下面的線性規(guī)劃問：用單純形法表求解下面的線性規(guī)劃問題。題。1122111111112211221112max. .,.,00mmmmnnmmnnmmnnmmmmmnnmmnizc xc xc xcxc xxaxa xbxaxa xbs txaxaxbx xxxb （）LP設(shè)設(shè)為為：12121(,.,),(,.,0,.,0)mTmmiiBP

47、 PPXb bbzc 顯顯然然初初始始可可行行基基為為初初始始基基可可行行解解為為五、單純形法小結(jié)五、單純形法小結(jié)1111(1,2,.,)max()niiijjj mmnmiijiijjij mixba ximzc bcc ax 或或?qū)憣憺闉椋簃ax()BNBNzC bCC A X01max()njjjj mzzcz x 111101()BNBNBjjNnj mBzC B bCC B N xxB bB Nzxx 記記相相應(yīng)應(yīng)于于基基 下下的的消消去去為為系系統(tǒng)統(tǒng)為為：判判斷斷最最優(yōu)優(yōu)及及換換基基變變換換：01max()njjjj mzzczx 0jjjcz 當(dāng)當(dāng)所所有有的的檢檢驗(yàn)驗(yàn)數(shù)數(shù)時(shí)時(shí)，得

48、得到到最最優(yōu)優(yōu)；0kkkkczx 當(dāng)當(dāng)有有檢檢驗(yàn)驗(yàn)數(shù)數(shù)時(shí)時(shí)，換換基基變變換換：為為進(jìn)進(jìn)基基變變量量1min0milikliiklklkbbaxaaa 為為出出基基變變量量 為為旋旋轉(zhuǎn)轉(zhuǎn)中中心心；第六節(jié)第六節(jié) 線性規(guī)劃應(yīng)用舉例線性規(guī)劃應(yīng)用舉例l合理利用線材問題：合理利用線材問題：如何下料如何下料使用材最少。使用材最少。l配料問題：配料問題：在原料供應(yīng)量的限在原料供應(yīng)量的限制下如何獲取最大利潤。制下如何獲取最大利潤。l投資問題：投資問題：從投資項(xiàng)目中選取從投資項(xiàng)目中選取方案，使投資回報(bào)最大。方案，使投資回報(bào)最大。線性規(guī)劃線性規(guī)劃-l產(chǎn)品生產(chǎn)計(jì)劃：產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、合理利用人力、物力

49、、財(cái)力等，使獲利最大。財(cái)力等，使獲利最大。l勞動力安排：勞動力安排：用最少的勞動力來滿足用最少的勞動力來滿足工作的需要。工作的需要。l運(yùn)輸問題：運(yùn)輸問題：如何制定調(diào)運(yùn)方案，使總?cè)绾沃贫ㄕ{(diào)運(yùn)方案，使總運(yùn)費(fèi)最小。運(yùn)費(fèi)最小。 數(shù)學(xué)規(guī)劃的建模有許多共同點(diǎn)，要遵循下列原則： (1)容易理解。建立的模型不但要求建模者理解，還應(yīng)當(dāng)讓有關(guān)人員理解。這樣便于考察實(shí)際問題與模型的關(guān)系，使得到的結(jié)論能夠更好地應(yīng)用于解決實(shí)際問題。 (2)容易查找模型中的錯(cuò)誤。這個(gè)原則的目的顯然與(1)相關(guān)。常出現(xiàn)的錯(cuò)誤有：書寫錯(cuò)誤和公式錯(cuò)誤。 (3)容易求解。對線性規(guī)劃來說，容易求解問題主要是控制問題的規(guī)模，包括決策變量的個(gè)數(shù)和約束

50、條件的個(gè)數(shù)。這條原則的實(shí)現(xiàn)往往會與(1)發(fā)生矛盾，在實(shí)現(xiàn)時(shí)需要對兩條原則進(jìn)行統(tǒng)籌考慮。 建立線性規(guī)劃模型的過程可以分為四個(gè)步驟： (1)設(shè)立決策變量； (2)明確約束條件并用決策變量的線性等式或不等式表示； (3)用決策變量的線性函數(shù)表示目標(biāo)，并 確 定 是 求 極 大 （ M a x ） 還 是 極 ?。∕in）； (4)根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性。一、混合配料問題一、混合配料問題 【例【例1-71-7】某工廠要用三種原材料】某工廠要用三種原材料C C、P P、H H混合調(diào)配出三種混合調(diào)配出三種不同規(guī)格的產(chǎn)品不同規(guī)格的產(chǎn)品A A、B B、D D。已知產(chǎn)品的規(guī)格、產(chǎn)品單價(jià)、每天

51、。已知產(chǎn)品的規(guī)格、產(chǎn)品單價(jià)、每天能供應(yīng)的原材料數(shù)量及原材料單價(jià)如表能供應(yīng)的原材料數(shù)量及原材料單價(jià)如表1-101-10、表、表1-111-11所示。問所示。問該廠如何安排生產(chǎn)，利潤收入最大？該廠如何安排生產(chǎn)，利潤收入最大？表表1-1025不限D(zhuǎn)原材料P不超過50%35原材料C不少于25%B原材料P不超過25%50原材料C不少于50%A單價(jià)(元/kg)規(guī)格要求產(chǎn)品名稱表表1-113560H25100P65100C單價(jià)(元/kg)每天最大供應(yīng)量(kg)原材料名稱解：解：設(shè)設(shè)A Ac c表示表示A A產(chǎn)品中產(chǎn)品中C C的成分，其數(shù)量用的成分，其數(shù)量用x x1 1表示；表示； A AP P表示表示A A

52、產(chǎn)品中產(chǎn)品中P P的成分，其數(shù)量用的成分，其數(shù)量用x x2 2表示；表示； A AH H表示表示A A產(chǎn)品中產(chǎn)品中H H的成分，其數(shù)量用的成分，其數(shù)量用x x3 3表示；表示； B BC C表示表示B B產(chǎn)品中產(chǎn)品中C C的成分，其數(shù)量用的成分，其數(shù)量用x x4 4表示；表示； B BH H表示表示B B產(chǎn)品中產(chǎn)品中H H的成分，其數(shù)量用的成分，其數(shù)量用x x6 6表示；表示； B BP P表示表示B B產(chǎn)品中產(chǎn)品中P P的成分，其數(shù)量用的成分，其數(shù)量用x x5 5表示；表示； D DC C表示表示D D產(chǎn)品中產(chǎn)品中D D的成分，其數(shù)量用的成分，其數(shù)量用x x7 7表示；表示； D DH H表

53、示表示D D產(chǎn)品中產(chǎn)品中H H的成分，其數(shù)量用的成分，其數(shù)量用x x9 9表示表示. . D DP P表示表示D D產(chǎn)品中產(chǎn)品中P P的成分，其數(shù)量用的成分，其數(shù)量用x x8 8表示；表示； 321xxxAAAAHPC654xxxBBBBHPC987xxxDDDDHPC依據(jù)題意，得：依據(jù)題意，得： 依據(jù)產(chǎn)品規(guī)格要求得：依據(jù)產(chǎn)品規(guī)格要求得： HPCCAAAA21HPCPAAAA41HPCCBBBB41HPCPBBBB210212121HPCAAA0414341HPCAAA0414143HPCBBB0212121HPCBBB整理得：整理得： 100CCCDBA100PPPDBA60HHHDBA依據(jù)

54、原材料每天供應(yīng)量限制得：依據(jù)原材料每天供應(yīng)量限制得：該問題的線性規(guī)劃數(shù)學(xué)模型為：該問題的線性規(guī)劃數(shù)學(xué)模型為： 963852741987654321352565253550maxxxxxxxxxxxxxxxxxxxz9 , 2 , 10601001000212121041414304143410212121963852741654654321321jxxxxxxxxxxxxxxxxxxxxxxj二、生產(chǎn)計(jì)劃安排問題二、生產(chǎn)計(jì)劃安排問題 【例【例1-81-8】某廠生產(chǎn)】某廠生產(chǎn)、三種產(chǎn)品，都分別經(jīng)三種產(chǎn)品，都分別經(jīng)A A、B B兩兩道工序加工。設(shè)道工序加工。設(shè)A A工序可分別在設(shè)備工序可分別在設(shè)備

55、A A1 1或或A A2 2上完成，有上完成，有B B1 1、B B2 2、B B3 3三種設(shè)備可用于完成三種設(shè)備可用于完成B B工序。已知產(chǎn)品工序。已知產(chǎn)品可在可在A A、B B任何一種任何一種設(shè)備上加工；產(chǎn)品設(shè)備上加工；產(chǎn)品可在任何規(guī)格的可在任何規(guī)格的A A設(shè)備上加工，但完成設(shè)備上加工，但完成B B工工序時(shí)，只能在序時(shí)，只能在B B1 1設(shè)備上加工；產(chǎn)品設(shè)備上加工；產(chǎn)品只能在只能在A A2 2與與B B2 2設(shè)備上加工。設(shè)備上加工。加工單位產(chǎn)品所需工序時(shí)間及其它各項(xiàng)數(shù)據(jù)見下表，試安排最加工單位產(chǎn)品所需工序時(shí)間及其它各項(xiàng)數(shù)據(jù)見下表，試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最

56、大。設(shè)備產(chǎn)品設(shè)備有效臺時(shí)設(shè)備加工費(fèi)A151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料費(fèi)（元/件）0.250.350.50售價(jià)（元/件）1.252.002.80 解：解：設(shè)產(chǎn)品設(shè)產(chǎn)品、的產(chǎn)量分別為的產(chǎn)量分別為x x1 1,x,x2 2,x,x3 3件。件。 產(chǎn)品產(chǎn)品有有6 6種加工方案，分別利用設(shè)備種加工方案，分別利用設(shè)備(A(A1 1,B,B1 1)(A)(A1 1,B,B2 2)(A)(A1 1,B,B3 3)(A)(A2 2，B B1 1)(A)(A2 2,B,B2 2)(A)(A2 2,B,B3 3) )，

57、各方案加工的產(chǎn)，各方案加工的產(chǎn)品品數(shù)量用數(shù)量用X Xllll，x x1212，x x1313，x x1414，x x1515，x x1616表示；產(chǎn)品表示；產(chǎn)品有有2 2種加工種加工方案，即方案，即(A(A1 1,B,B1 1)(A)(A2 2,B,B1 1) )，加工數(shù)量用，加工數(shù)量用x x2121，x x2222表示；產(chǎn)品表示；產(chǎn)品只有只有1 1種加工方案種加工方案(A(A2 2,B,B2 2) )，加工數(shù)量等于，加工數(shù)量等于x x3 3。 222121615141312111xxxxxxxxxx 工廠的盈利為產(chǎn)品售價(jià)減去相應(yīng)的原料費(fèi)和設(shè)備加工費(fèi)。產(chǎn)工廠的盈利為產(chǎn)品售價(jià)減去相應(yīng)的原料費(fèi)和設(shè)

58、備加工費(fèi)。產(chǎn)品加工量只受設(shè)備有效臺時(shí)的限制。故可建立如下線性規(guī)劃模型：品加工量只受設(shè)備有效臺時(shí)的限制。故可建立如下線性規(guī)劃模型： )(35. 00 . 2()(25. 025. 1 (max2221161514131211xxxxxxxxz)12977(03. 0)10555(05. 0)05. 080. 2(22211514211312113xxxxxxxxx)12977(03. 0)10555(05. 0)05. 080. 2(22211514211312113xxxxxxxxx04000777000444000866610000129777600010555161331512222114

59、1132216151421131211ijxxxxxxxxxxxxxxxxxxx三、生產(chǎn)與存貯問題三、生產(chǎn)與存貯問題 解：解：設(shè)設(shè)x xijij為為i i種產(chǎn)品種產(chǎn)品j j月份在正常時(shí)間內(nèi)生產(chǎn)的數(shù)量，月份在正常時(shí)間內(nèi)生產(chǎn)的數(shù)量， 為為第第i i種產(chǎn)品種產(chǎn)品j j月份在加班時(shí)間內(nèi)生產(chǎn)的數(shù)量。該廠盈利總額為生月份在加班時(shí)間內(nèi)生產(chǎn)的數(shù)量。該廠盈利總額為生產(chǎn)的產(chǎn)的5 5種產(chǎn)品銷售價(jià)減去成本和庫存費(fèi)用。問題的限制條件有兩種產(chǎn)品銷售價(jià)減去成本和庫存費(fèi)用。問題的限制條件有兩項(xiàng)：一是各個(gè)月的正常和加班的允許工時(shí)，二是滿足交貨要求。項(xiàng)：一是各個(gè)月的正常和加班的允許工時(shí)，二是滿足交貨要求。本例的線性規(guī)劃模型可表示

60、為本例的線性規(guī)劃模型可表示為: : ijx 【例【例1-91-9】某廠簽訂了】某廠簽訂了5 5種產(chǎn)品種產(chǎn)品(i(i1 1，5)5)上半年的交貨合上半年的交貨合同。已知各產(chǎn)品在第同。已知各產(chǎn)品在第j j月月(j(j1 1，6)6)的合同交貨量的合同交貨量D Dijij，該月，該月售價(jià)售價(jià)s sijij、成本價(jià)、成本價(jià)c cijij及生產(chǎn)及生產(chǎn)1 1件時(shí)所需工時(shí)件時(shí)所需工時(shí)a aijij。該廠第。該廠第j j月的正常月的正常生產(chǎn)工時(shí)為生產(chǎn)工時(shí)為t tj j，但必要時(shí)可加班生產(chǎn)，第，但必要時(shí)可加班生產(chǎn)，第j j月允許的最多加班工月允許的最多加班工時(shí)不超過時(shí)不超過 ，并且加班時(shí)間內(nèi)生產(chǎn)出來的產(chǎn)品每件成

61、本增加額，并且加班時(shí)間內(nèi)生產(chǎn)出來的產(chǎn)品每件成本增加額外費(fèi)用外費(fèi)用 元；若生產(chǎn)出來的產(chǎn)品當(dāng)月不交貨，每件庫存元；若生產(chǎn)出來的產(chǎn)品當(dāng)月不交貨，每件庫存1 1個(gè)月個(gè)月交存貯費(fèi)交存貯費(fèi)p pi i元。試為該廠設(shè)計(jì)一個(gè)保證完成合同交貨，又使上元。試為該廠設(shè)計(jì)一個(gè)保證完成合同交貨，又使上半年預(yù)期盈利總額為最大的生產(chǎn)計(jì)劃安排。半年預(yù)期盈利總額為最大的生產(chǎn)計(jì)劃安排。 jtijcijxijx 解：解：設(shè)設(shè) 為為i i種產(chǎn)品種產(chǎn)品j j月份在正常時(shí)間內(nèi)生產(chǎn)的數(shù)量，月份在正常時(shí)間內(nèi)生產(chǎn)的數(shù)量， 為為第第i i種產(chǎn)品種產(chǎn)品j j月份在加班時(shí)間內(nèi)生產(chǎn)的數(shù)量。月份在加班時(shí)間內(nèi)生產(chǎn)的數(shù)量。本例的線性規(guī)劃模型可表示為本例的線

62、性規(guī)劃模型可表示為: : 516115161)()()(maxijjkikikikiijijijijijijijijDxxpxccsxcsz0)6 , 1()()6 , 1()6 , 1(115151ijjkjkikikikijijijijijijxjDxxjtxajtxa某廠在今后四個(gè)月內(nèi)需租用倉某廠在今后四個(gè)月內(nèi)需租用倉庫堆放物資。已知各月份所需庫堆放物資。已知各月份所需倉庫面積數(shù)字列于倉庫面積數(shù)字列于1-1表中。表中。倉庫租借費(fèi)用隨合同期定，期倉庫租借費(fèi)用隨合同期定，期限越長折扣越大，具體數(shù)字見限越長折扣越大，具體數(shù)字見表表1-2。租借倉庫的合同每月。租借倉庫的合同每月初都可辦理，每份合

63、同具體規(guī)初都可辦理，每份合同具體規(guī)定租用面積數(shù)和期限。因此該定租用面積數(shù)和期限。因此該廠可根據(jù)需要，在任何一個(gè)月廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同，每次辦理時(shí)初辦理租借合同，每次辦理時(shí)可簽一份，也可簽若干份租用可簽一份，也可簽若干份租用面積和租借期限不同的合同，面積和租借期限不同的合同，總目標(biāo)是使所付租借費(fèi)用最小，總目標(biāo)是使所付租借費(fèi)用最小，試建立上述問題的線性規(guī)劃模試建立上述問題的線性規(guī)劃模型。型。月份1 2 3 4所需倉庫面積（100m2)15 10 20 12表1-1合同租借期限1個(gè)月 2個(gè)月 3個(gè)月 4個(gè)月合同期內(nèi)的租費(fèi)（元/100m2)2800 4500 6000 7300表1

64、-2班次工作時(shí)間所需人數(shù)(人)1 6:0010:0060210:0014:0070314:0018:0060418:0022:0050522:00 2:00206 2:00 6:0030 若該醫(yī)院值班護(hù)士分別在各時(shí)間段開始時(shí)上班，并連續(xù)工作若該醫(yī)院值班護(hù)士分別在各時(shí)間段開始時(shí)上班，并連續(xù)工作8 8小時(shí)。問該醫(yī)院最少需要多少護(hù)士，才能滿足工作需要？小時(shí)。問該醫(yī)院最少需要多少護(hù)士，才能滿足工作需要？ 解：解：設(shè)設(shè)x xi i表示第表示第i i班開始時(shí)上班的護(hù)士人數(shù)。根據(jù)題意，該班開始時(shí)上班的護(hù)士人數(shù)。根據(jù)題意，該問題的數(shù)學(xué)模型為：問題的數(shù)學(xué)模型為： 654321minxxxxxxz6 , 2 ,

65、10603020506070616554433221jxxxxxxxxxxxxxj四、人力資源分配問題四、人力資源分配問題 【例【例1-101-10】某醫(yī)院護(hù)士值】某醫(yī)院護(hù)士值班班次及每班所需要的護(hù)士班班次及每班所需要的護(hù)士人數(shù)如右表所示。人數(shù)如右表所示。 某商場決定：營業(yè)員某商場決定：營業(yè)員每周連續(xù)工作每周連續(xù)工作5天后，天后，連續(xù)休息連續(xù)休息2天，輪流休天，輪流休息，根據(jù)統(tǒng)計(jì)，商場息，根據(jù)統(tǒng)計(jì)，商場每天需要的營業(yè)員如每天需要的營業(yè)員如右表所示，問商場人右表所示，問商場人力資源部應(yīng)如何安排力資源部應(yīng)如何安排每天的上班人數(shù)，使每天的上班人數(shù)，使商場總的營業(yè)員最少？商場總的營業(yè)員最少？一300五

66、480二300六600三350日550四400 現(xiàn)有一批某種型號的圓鋼長現(xiàn)有一批某種型號的圓鋼長8 8米，需要截取米，需要截取2.52.5米長的毛坯米長的毛坯100100根，長根，長1.31.3米的毛坯米的毛坯200200根。問如何才能既滿足需要，又能使總根。問如何才能既滿足需要，又能使總的用料最少？的用料最少？100200 3 2 1 0 0 2 4 62.5米米1.3米米需要需要根數(shù)根數(shù) 一一 二二 三三 四四下料下料 下料下料 件數(shù)件數(shù) 方式方式毛坯型號毛坯型號五、合理下料問題五、合理下料問題 設(shè) 為按第 種方式下料的原材料件數(shù)jxj1234min Zxxxx12323432100. . 2462000(1,2,3,4)jxxxs txxxxj 某工廠計(jì)劃做某工廠計(jì)劃做100套鋼架，需要用長分別套鋼架，需要用長分別為為2.9m、2.1m和和1.5m的圓鋼各一根。已知的圓鋼各一根。已知可做原料使用的圓鋼每根長可做原料使用的圓鋼每根長7.4m，問如何，問如何下料才能使所用原料最??？下料才能使所用原料最??？六、連續(xù)投資問題六、連續(xù)投資問題 【例【例1-111-11】某部門在今后五年內(nèi)考