運(yùn)籌(第一章線性規(guī)劃)

2023/2/41運(yùn)籌學(xué)

OPERATIONSRESEARCH

2023/2/42第一章線性規(guī)劃及單純形法

(LinearProgramming,LP)線性規(guī)劃模型圖解法單純形法原理單純形法計(jì)算步驟單純形法的進(jìn)一步討論數(shù)據(jù)包絡(luò)分析2023/2/43§1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

1.1引例

例1生產(chǎn)計(jì)劃問(wèn)題

Ⅰ

Ⅱ能力設(shè)備A2212設(shè)備B4

016設(shè)備C0515利潤(rùn)23Ⅰ，Ⅱ各生產(chǎn)多少,可獲最大利潤(rùn)?2023/2/44注意模型特點(diǎn)解:設(shè)產(chǎn)品Ⅰ,Ⅱ產(chǎn)量分別為變量。2023/2/45線性規(guī)劃模型特點(diǎn)決策變量：向量決策人要考慮和控制的因素，非負(fù)。約束條件：關(guān)于的線性等式或不等式。目標(biāo)函數(shù)：為關(guān)于

的線性函數(shù)，求Z極大或極小2023/2/461.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型線性規(guī)劃模型的三個(gè)組成要素：1.決策變量:是決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，是問(wèn)題中要確定的未知量。2.目標(biāo)函數(shù):指問(wèn)題要達(dá)到的目的要求，表示為決策變量的函數(shù)。3.約束條件:指決策變量取值時(shí)受到的各種可用資源的限制，表示為含決策變量的等式或不等式。2023/2/47一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型：目標(biāo)函數(shù)：約束條件：2023/2/48簡(jiǎn)寫(xiě)形式：2023/2/49矩陣形式表示為：其中：2023/2/4101.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式：2023/2/411標(biāo)準(zhǔn)形式特點(diǎn)：4.決策變量取值非負(fù)。1.目標(biāo)函數(shù)為求極大值；2.約束條件全為等式；3.約束條件右端常數(shù)項(xiàng)全為非負(fù)；2023/2/412一般線性規(guī)劃問(wèn)題如何化為標(biāo)準(zhǔn)型：1.目標(biāo)函數(shù)求極小值：令：，即化為：2023/2/4132.約束條件為不等式：（1）當(dāng)約束條件為“≤”時(shí)如：可令：，顯然（2）當(dāng)約束條件為“≥”時(shí)如：可令：，顯然稱(chēng)為松弛變量。

稱(chēng)為剩余變量。2023/2/414松弛變量和剩余變量統(tǒng)稱(chēng)為松弛變量。（3）目標(biāo)函數(shù)中松弛變量的系數(shù)由于松弛變量和剩余變量分別表示未被充分利用的資源以及超用的資源，都沒(méi)有轉(zhuǎn)化為價(jià)值和利潤(rùn)，因此在目標(biāo)函數(shù)中系數(shù)為零。2023/2/4153.取值無(wú)約束的變量其中：令4.變量xj≤0，顯然如果變量

代表某產(chǎn)品當(dāng)年計(jì)劃數(shù)與上一年計(jì)劃數(shù)之差，顯然

的取值可能是正也可能是負(fù)，這時(shí)可令：2023/2/416例.將下述線性規(guī)劃模型化為標(biāo)準(zhǔn)型2023/2/417解：令得標(biāo)準(zhǔn)形式為：2023/2/418求解線性規(guī)劃問(wèn)題：就是從滿足約束方程組和約束不等式的決策變量取值中，找出使得目標(biāo)函數(shù)達(dá)到最大的值。1.4線性規(guī)劃問(wèn)題的解的概念2023/2/419

可行解：滿足約束條件的解稱(chēng)為可行解，可行解的集合稱(chēng)為可行域。最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。

基：約束方程組的系數(shù)矩陣中的一個(gè)滿秩子矩陣稱(chēng)為規(guī)劃問(wèn)題的一個(gè)基，基中的每一個(gè)列向量稱(chēng)為基向量，與基向量對(duì)應(yīng)的變量稱(chēng)為基變量，其他變量稱(chēng)為非基變量。

說(shuō)明：基通常不唯一。2023/2/420

基解：在約束方程組中，令所有非基變量為0，可以解出基變量的唯一解，這組解與非基變量的0共同構(gòu)成基解?；尚薪猓簼M足變量非負(fù)的基解稱(chēng)為基可行解?？尚谢簩?duì)應(yīng)于基可行解的基稱(chēng)為可行基。2023/2/421例：考察下述線性規(guī)劃問(wèn)題：2023/2/422（1）可行解，如或滿足約束條件，所以是可行解。（2）基系數(shù)矩陣其中

或

都構(gòu)成基。而不構(gòu)成基。2023/2/423（3）基向量、基變量是對(duì)應(yīng)于基的三個(gè)基向量，而是對(duì)應(yīng)于這三個(gè)基向量的基變量。（4）基解、基可行解、可行基是對(duì)應(yīng)于基的基解、基可行解。是對(duì)應(yīng)于基的基解、基可行解。均是可行基。練習(xí)：P14，例42023/2/424

為了便于建立n維空間中線性規(guī)劃問(wèn)題的有關(guān)概念及便于理解求解一般線性規(guī)劃問(wèn)題的單純形法的思路，先介紹圖解法。求解下述線性規(guī)劃問(wèn)題：§2線性規(guī)劃問(wèn)題的圖解法2023/2/425畫(huà)出線性規(guī)劃問(wèn)題的可行域：目標(biāo)函數(shù)等值線2023/2/4261、可行域：約束條件所圍成的區(qū)域。2、基可行解：對(duì)應(yīng)可行域的頂點(diǎn)。3、目標(biāo)函數(shù)等值線：4、目標(biāo)函數(shù)最優(yōu)值:最大截距所對(duì)應(yīng)的。

目標(biāo)函數(shù)等值線有無(wú)數(shù)條，且平行。（觀察規(guī)律)2023/2/427解的幾種情況：(2)無(wú)窮多最優(yōu)解：若目標(biāo)函數(shù)改為(1)唯一最優(yōu)解約束條件不變，則:目標(biāo)函數(shù)等值線此時(shí)，線段上所有點(diǎn)都是最優(yōu)值點(diǎn)。2023/2/428(4)無(wú)界解(3)無(wú)可行解：當(dāng)可行域?yàn)榭占瘯r(shí)，無(wú)可行解。若目標(biāo)函數(shù)不變，將約束條件1和3去掉，則可行域及解的情況見(jiàn)下圖。目標(biāo)函數(shù)等值線此時(shí)，目標(biāo)函數(shù)等值線可以向上無(wú)窮遠(yuǎn)處平移，Z值無(wú)界。2023/2/429幾點(diǎn)說(shuō)明：1、圖解法只能用來(lái)求解含有兩個(gè)決策變量的線性規(guī)劃問(wèn)題。2、若最優(yōu)解存在，則必在可行域的某個(gè)頂點(diǎn)處取得。3、線性規(guī)劃問(wèn)題的解可能是：唯一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)最優(yōu)解、無(wú)界解。2023/2/430§3．單純形法原理上圖中（1）（2）是凸集，（3）（4）不是凸集3.1預(yù)備知識(shí)

凸集：如果集合

中任意兩個(gè)點(diǎn)，其連線上的所有點(diǎn)也都是集合

中的點(diǎn)。頂點(diǎn)：如果對(duì)于凸集中的點(diǎn)

，不存在

中的任意其它兩個(gè)不同的點(diǎn)，使得在它們的連線上，這時(shí)稱(chēng)為凸集的頂點(diǎn)。2023/2/4313.2線性規(guī)劃問(wèn)題基本定理定理1:若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行域是凸集。證明:設(shè)是線性規(guī)劃的任意兩個(gè)可行解，則于是對(duì)于任意的，，則

所以也是問(wèn)題的可行解，即可行域是凸集。

2023/2/432引理:

線性規(guī)劃問(wèn)題的可行解X為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)。證明:設(shè)（1）必要性顯然。（2）設(shè)A的秩為m?？尚薪釾的前k個(gè)分量為正，且它們對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)，則。當(dāng)時(shí)，恰好構(gòu)成一組基，而恰是這組基對(duì)應(yīng)的基可行解。

2023/2/433

當(dāng)時(shí)，在基礎(chǔ)上從其余列向量中可以找出個(gè)線性無(wú)關(guān)的向量，恰好構(gòu)成一組基，而X就是這組基對(duì)應(yīng)的基可行解。2023/2/434定理2:

線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域（凸集）的頂點(diǎn)。證明:問(wèn)題即是要證明:X是基可行解X是可行域頂點(diǎn)，也即要證明其逆否命題：X不是基可行解X不是可行域頂點(diǎn)。（1）X不是基可行解X不是可行域頂點(diǎn)。假設(shè)X是可行解，但不是基可行解，X的前k個(gè)分量為正,其余分量為0，則有又X不是基可行解，所以由引理知，正分量對(duì)應(yīng)列向量線性相關(guān)。即存在一組不全為零的數(shù)，使得用非零常數(shù)乘以上式得：2023/2/4352023/2/436（1）+（3）得：（1）-（3）得：令選擇合適的，使得所有的于是均是可行解，并且，所以X不是可行域頂點(diǎn)。2023/2/437（2）X不是可行域頂點(diǎn)X不是基可行解。設(shè)不是可行域的頂點(diǎn)，因而可以找到可行域內(nèi)另兩個(gè)不同的點(diǎn)，使得用分量表示即為：

易知，當(dāng)，時(shí)，必有2023/2/438所以所以于是（1）-（2）得而不全為零，于是知線性相關(guān)，X不是基可行解。證畢。2023/2/439定理3:

若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。引理：

有界

凸集中的任何一點(diǎn)均可表示成頂點(diǎn)的凸組合。證明:假設(shè)是可行域頂點(diǎn)，不是可行域頂點(diǎn)，且目標(biāo)函數(shù)在處達(dá)到最優(yōu)，即2023/2/440由引理知：可表示為的凸組合，即因此假設(shè)是所有中最大者，則2023/2/441而是目標(biāo)函數(shù)的最大值，所以也是最大值，也即，目標(biāo)函數(shù)在可行域的某個(gè)頂點(diǎn)達(dá)到了最優(yōu)。從上述三個(gè)定理可以看出，要求線性規(guī)劃問(wèn)題的最優(yōu)解，只要比較可行域（凸集）各個(gè)頂點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值即可，最大的就是我們所要求的最優(yōu)解。2023/2/4423.3確定初始基可行解尋求最優(yōu)解的思路：線性規(guī)劃問(wèn)題的最優(yōu)解一定會(huì)在基可行解中取得，我們先找到一個(gè)初始基可行解。然后設(shè)法轉(zhuǎn)換到另一個(gè)基可行解，并使得目標(biāo)函數(shù)值不斷增大，直到找到最優(yōu)解為止。設(shè)給定線性規(guī)劃問(wèn)題：2023/2/443因此約束方程組的系數(shù)矩陣為：添加松弛變量得其標(biāo)準(zhǔn)形為：2023/2/444由于該矩陣含有一個(gè)單位子矩陣，因此，這個(gè)單位陣就是一組基，就可以求出一個(gè)基可行解：說(shuō)明：如果約束條件不全是形式，如含所有形式，則無(wú)法找到一個(gè)單位陣作為一組基，這時(shí)需要添加人工變量，在后面的內(nèi)容介紹。稱(chēng)其為初始基可行解。2023/2/4453.4從初始基可行解轉(zhuǎn)換為另一個(gè)基可行解

思路：對(duì)初始基可行解的系數(shù)矩陣進(jìn)行初等行變換，構(gòu)造出一個(gè)新的單位矩陣，其各列所對(duì)應(yīng)的變量即為一組新的基變量，求出其數(shù)值，就是一個(gè)新的基可行解。

設(shè)有初始基可行解，并可設(shè)前m個(gè)分量非零，即于是2023/2/446

由構(gòu)造初始可行基的方法知前m個(gè)基向量恰好是一個(gè)單位陣，所以約束方程組的增廣矩陣為2023/2/447由于任意系數(shù)列向量均可由基向量組線性表示，則非基向量中的用基向量組線性表示為：設(shè)有，則（1）+（2）得：2023/2/448由此式可知，我們找到了滿足約束方程組的另一個(gè)解，要使其成為可行解，只要對(duì)所有i=1,2,…m，下式成立要使其成為基可行解，上面m個(gè)式中至少有一個(gè)取零。（基可行解中非零分量的個(gè)數(shù)不超過(guò)m個(gè)。）（與比較）2023/2/449只要取于是前m個(gè)分量中的第個(gè)變?yōu)榱悖溆喾秦?fù)，第個(gè)分量為正，于是非零分量的個(gè)數(shù)，并可證得線性無(wú)關(guān)，所以是新的基可行解。2023/2/4503.4最優(yōu)性檢驗(yàn)和解的判別設(shè)有基可行解比較兩者對(duì)應(yīng)的目標(biāo)函數(shù)值，哪一個(gè)更優(yōu)？2023/2/4512）若對(duì)所有的，則，

就是最優(yōu)解。是判斷是否達(dá)到最優(yōu)解的標(biāo)準(zhǔn)，稱(chēng)為檢驗(yàn)數(shù)。1）當(dāng)時(shí)，，目標(biāo)函數(shù)值得到了改進(jìn)，

不是最優(yōu)解，需要繼續(xù)迭代。易知2023/2/452當(dāng)所有時(shí)，現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解即為最優(yōu)解。當(dāng)所有時(shí)，又對(duì)某個(gè)非基變量有則該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。如果存在某個(gè)，又向量的所有分量，對(duì)任意，恒有，則存在無(wú)界解。結(jié)論2023/2/453§4單純形法的計(jì)算步驟

設(shè)有線性規(guī)劃問(wèn)題：2023/2/454(1)找到初始可行基，建立初始單純形表.(4)重復(fù)二、三兩步，直至找到最優(yōu)解。單純形法的計(jì)算步驟

(2)進(jìn)行最優(yōu)性檢驗(yàn)。計(jì)算檢驗(yàn)數(shù)，若所有≤0則得最優(yōu)解，結(jié)束.否則轉(zhuǎn)下步.若某≥0而≤0，則最優(yōu)解無(wú)界，結(jié)束.否則轉(zhuǎn)下步.(3)從一個(gè)可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解。由最大增加原則確定進(jìn)基變量；由最小比值原則選擇出基變量；以為主元素進(jìn)行換基迭代。2023/2/455……(1)找到初始可行基，建立初始單純形表.00…………………是初始基。2023/2/456(2)進(jìn)行最優(yōu)性檢驗(yàn)計(jì)算檢驗(yàn)數(shù)，若所有≤0則得最優(yōu)解，結(jié)束.否則轉(zhuǎn)下步.若某≥0而≤0，則最優(yōu)解無(wú)界，結(jié)束.否則轉(zhuǎn)下步.檢驗(yàn)數(shù)的計(jì)算方法：基變量的檢驗(yàn)數(shù)一定為0。判斷是否達(dá)到最優(yōu)時(shí)，只要考慮非基變量檢驗(yàn)數(shù)。2023/2/457(3)從一個(gè)可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解。進(jìn)基變量由最大增加原則確定進(jìn)基變量：當(dāng)某些非基變量的檢驗(yàn)數(shù)時(shí)，為使目標(biāo)函數(shù)值增加地更快，一般選擇正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的非基變量進(jìn)基

，成為新的基變量。

由最小比值原則選擇出基變量；為確保新的基可行解的非零分量非負(fù)，按下述規(guī)則求得最小比值，其所對(duì)應(yīng)的原基變量中的出基。2023/2/458于是，新的一組基是：以為主元素進(jìn)行換基迭代：即利用初等行變換將進(jìn)基變量

所在的系數(shù)列變?yōu)閱挝涣邢蛄?，而變?yōu)?。這樣原來(lái)基矩陣中的就不再是單位向量，取而代之的是，這樣就找到了一組新的基。(4)重復(fù)二、三兩步，直至找到最優(yōu)解。2023/2/459說(shuō)明：若目標(biāo)函數(shù)是求最小，可以不必將其轉(zhuǎn)變?yōu)榍笞畲?，但在使用單純形法求解時(shí)，確定進(jìn)基變量，應(yīng)找負(fù)檢驗(yàn)數(shù)中最小者，并應(yīng)以檢驗(yàn)數(shù)全部為正作為判別最優(yōu)的條件。2023/2/460解將模型標(biāo)準(zhǔn)化例1求解下面的線性規(guī)劃問(wèn)題檢驗(yàn)數(shù)最大比值最小列單純形表，進(jìn)行迭代計(jì)算612023/2/4檢驗(yàn)數(shù)最大比值最小622023/2/4所有檢驗(yàn)數(shù)均已非正，已得到最優(yōu)解，最優(yōu)解即為632023/2/42023/2/464解將模型標(biāo)準(zhǔn)化例2求解下面的線性規(guī)劃問(wèn)題檢驗(yàn)數(shù)最大比值最小列單純形表，進(jìn)行迭代計(jì)算652023/2/4檢驗(yàn)數(shù)最大比值最小列單純形表，進(jìn)行迭代計(jì)算662023/2/4列單純形表，進(jìn)行迭代計(jì)算672023/2/4所有檢驗(yàn)數(shù)均已非正，已得到最優(yōu)解，最優(yōu)解即為2023/2/468特殊情況：（1）出現(xiàn)兩個(gè)或兩個(gè)以上相同的最大，此時(shí)可任選一個(gè)所對(duì)應(yīng)的變量作為進(jìn)基變量。

（2）利用規(guī)則決定出基變量時(shí)，出現(xiàn)兩個(gè)或兩個(gè)以上的最小比值，則迭代后，會(huì)出現(xiàn)一個(gè)或幾個(gè)基變量等于零的情況，我們稱(chēng)此為退化現(xiàn)象。進(jìn)而可能會(huì)出現(xiàn)迭代過(guò)程的循環(huán)，致使永遠(yuǎn)達(dá)不到最優(yōu)解。出現(xiàn)退化現(xiàn)象時(shí)，可考慮采用“勃蘭特”規(guī)則決定進(jìn)基變量和出基變量的選擇。2023/2/4695.1人工變量用單純形法解題時(shí)，需要有一個(gè)單位陣作為初始基。當(dāng)約束條件都是“≤”時(shí)，加入松弛變量就形成了初始基。但實(shí)際存在“≥”或“＝”型的約束，沒(méi)有現(xiàn)成的單位矩陣。采用人造基的辦法：添加人工變量，構(gòu)造單位矩陣.§5單純形法的進(jìn)一步討論2023/2/470

人工單位矩陣的構(gòu)造方法（1）在“”的不等式約束中減去一個(gè)剩余變量后可變?yōu)榈仁郊s束，但此剩余變量的系數(shù)是-1，所以再加入一個(gè)人工變量，其系數(shù)是+1，因而在系數(shù)矩陣中可得到一個(gè)相應(yīng)的單位向量，以便構(gòu)成初始單位陣，即初始基矩陣。（2）在原本就是“=”的約束中可直接添加一個(gè)人工變量，以便得到初始基矩陣。注意：人工變量是在等式中人為加進(jìn)的，只有它等于0時(shí)，約束條件才是它本來(lái)的意義。2023/2/4715.2大M法

沒(méi)有單位矩陣，不符合構(gòu)造初始基的條件，需加入人工變量。人工變量最終必須等于0才能保持原問(wèn)題性質(zhì)不變。為保證人工變量為0，在目標(biāo)函數(shù)中令其系數(shù)為（-M）。求最小值問(wèn)題中，人工變量系數(shù)取MM為無(wú)限大的正數(shù)，這是一個(gè)懲罰項(xiàng)，倘若人工變量不為零，則目標(biāo)函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)，所以必須將人工變量逐步從基變量中替換出去。如若到最終表中人工變量仍沒(méi)有置換出去，那么這個(gè)問(wèn)題就沒(méi)有可行解，當(dāng)然亦無(wú)最優(yōu)解。2023/2/472例3解線性規(guī)劃解化為標(biāo)準(zhǔn)型此時(shí)無(wú)單位矩陣作為初始基。2023/2/473添加人工變量，構(gòu)造初始基：（求最小值問(wèn)題中，人工變量系數(shù)需取M）2023/2/474初始單純形表：2023/2/4752023/2/476此時(shí)人工變量全部出基，并已達(dá)最優(yōu)條件。最優(yōu)解為，最優(yōu)值為注意：計(jì)算機(jī)上使用大M法時(shí)，需要用機(jī)器最大字長(zhǎng)的數(shù)字代替M，但當(dāng)某些系數(shù)與之較接近時(shí)，還是可能會(huì)出錯(cuò)。另外一種求解帶人工變量的線性規(guī)劃問(wèn)題的方法不會(huì)出現(xiàn)這種問(wèn)題-------兩階段法。2023/2/477例解線性規(guī)劃解按大M法構(gòu)造人造基，引入人工變量的輔助問(wèn)題如下：列單純形表，進(jìn)行迭代計(jì)算782023/2/4列單純形表，進(jìn)行迭代計(jì)算792023/2/4所有檢驗(yàn)數(shù)均已非正，且人工變量都已出基，已得到最優(yōu)解，最優(yōu)解即為2023/2/4805.3兩階段法

第一階段：構(gòu)造目標(biāo)函數(shù)只含人工變量的線性規(guī)劃問(wèn)題，求解后判斷原線性規(guī)劃問(wèn)題是否有基本可行解，若有，則進(jìn)行第二階段；第二階段：將第一階段的最終單純形表所對(duì)應(yīng)的解，去掉人工變量，作為第二階段的初始單純形表的初始基可行解，進(jìn)行單純形法的迭代。2023/2/481

解（1）化標(biāo)準(zhǔn)型、并添加人工變量得：

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

約束條件：

2023/2/482（2）構(gòu)造第一階段問(wèn)題：

說(shuō)明：原問(wèn)題目標(biāo)函數(shù)無(wú)論是求MAX還是求MIN，構(gòu)造的第一階段問(wèn)題目標(biāo)函數(shù)都是求最小MIN。2023/2/483求解第一階段問(wèn)題：2023/2/484此時(shí)所得可行解目標(biāo)函數(shù)值為0，故原規(guī)劃問(wèn)題有基可行解。轉(zhuǎn)入第二步。2023/2/485（3）去掉人工變量，得到第二階段的單純形表，在此基礎(chǔ)上繼續(xù)求解。最優(yōu)解為：2023/2/4865.4關(guān)于解的不同情況的判別

1、無(wú)窮多最優(yōu)解例：解：將問(wèn)題化為標(biāo)準(zhǔn)型：2023/2/4872023/2/488從上表中可知，已達(dá)最優(yōu)解，為，而，若將選為進(jìn)基變量迭代后，可得另一最優(yōu)解。上述兩最優(yōu)解分別對(duì)應(yīng)兩個(gè)頂點(diǎn)，而兩點(diǎn)連線上的點(diǎn)均是最優(yōu)解，故有無(wú)窮多最優(yōu)解。判別無(wú)窮多最優(yōu)解的方法：?jiǎn)渭冃伪淼臋z驗(yàn)數(shù)行已達(dá)最有性條件（全部小于或等于零），且有一個(gè)非基變量的檢驗(yàn)數(shù)為零，此時(shí)有無(wú)窮多最優(yōu)解。2023/2/489

2、無(wú)可行解例

用單純形表求解下列線性規(guī)劃問(wèn)題解化為標(biāo)準(zhǔn)型：2023/2/490單純形表求解線性規(guī)劃問(wèn)題2023/2/491所有檢驗(yàn)數(shù)均為非正，但單純形法的最終表里有人工變量大于零，則此線性規(guī)劃無(wú)可行解。2023/2/492

3、無(wú)界解例

用單純形表求解下面線性規(guī)劃問(wèn)題。解2023/2/493單純形表求解線性規(guī)劃問(wèn)題此時(shí)的檢驗(yàn)數(shù)仍為正，但系數(shù)列全為負(fù)，此時(shí)可判斷這個(gè)線性規(guī)劃問(wèn)題是無(wú)界的，即目標(biāo)函數(shù)值可以取得無(wú)限大。2023/2/494練習(xí)：用大M法求解下列線性規(guī)劃問(wèn)題1、2023/2/495解1：將模型化為標(biāo)準(zhǔn)型得：建立單純形表并計(jì)算如下2023/2/496顯然，檢驗(yàn)數(shù)已全部非正，已達(dá)最優(yōu)解，但非基變量X2的檢驗(yàn)數(shù)為0，故知此問(wèn)題有無(wú)窮多最優(yōu)解。2023/2/497練習(xí)：用大M法求解下列線性規(guī)劃問(wèn)題2、2023/2/498解2：將模型化為標(biāo)準(zhǔn)型得：建立單純形表并計(jì)算如下2023/2/4992023/2/4100最優(yōu)解為（4，4）2023/2/4101小結(jié)表格單純形表的使用（1）化線性規(guī)劃模型為標(biāo)準(zhǔn)型，建立初始單純形表。（2）根據(jù)單純形表按照最大增加原則選擇進(jìn)基變量；（3）按照最小比值原則選擇換出變量；（4）實(shí)施矩陣的初等變換進(jìn)行換基迭代；（5）建立新的單純形表；（6）重復(fù)上述過(guò)程直到求得最優(yōu)表格為止。2023/2/4102例連續(xù)投資問(wèn)題?，F(xiàn)有資金10萬(wàn)元，在其后3年預(yù)對(duì)四個(gè)項(xiàng)目進(jìn)行投資。A：從第1年到第3年每年初可投資，年末回收本利111%；B：第2年初投資，到第3年末回收本利125%，最大投資3萬(wàn)元；C：第3年初投資，到年末回收本利120%，最大投資4萬(wàn)元；D：每年初投資，次年末回收本利的115%。求：第3年末總資本最大的投資方案。§6線性規(guī)劃應(yīng)用舉例

2023/2/4103解：假設(shè)

表示第i年初投資于第j個(gè)項(xiàng)目的資金，i=1,2,3;j=A,B,C,D。則2023/2/4104例.混合配料問(wèn)題

某糖果廠用原料A、B、C加工成三種不同牌號(hào)的糖果甲、乙、丙。已知各種牌號(hào)糖果中A、B、C含量，原料成本，各種原料的每月限制用量，三種牌號(hào)糖果的單位加工費(fèi)及售價(jià)如下表，問(wèn)該廠每月生產(chǎn)這三種牌號(hào)糖果各多少千克，使該廠獲利最大，試建立該問(wèn)題的線性規(guī)劃數(shù)學(xué)模型。2023/2/41052023/2/4106解：用i=1,2,3分別代表原料A、B、C，用j=1,2,3分別代表甲、乙、丙三種糖果。設(shè)xij

為生產(chǎn)第j

種糖果使用的第i

種原料的質(zhì)量，則問(wèn)題的數(shù)學(xué)模型可歸結(jié)為：目標(biāo)函數(shù)2023/2/4107約束條件為2023/2/4108例.投資項(xiàng)目的組合問(wèn)題

興安公司有一筆30萬(wàn)元的資金，考慮今后三年內(nèi)用于下列項(xiàng)目的投資：三年內(nèi)的每年年初均可投入，每年獲利為投資額的20%，其本利可一起用于下一年的投資；2.只允許第一年初投入，于第二年年末收回，本利合計(jì)為投資額的150%，但此類(lèi)投資限額15萬(wàn)以內(nèi)；3.允許于第二年初投入，于第三年末收回，本利合計(jì)為投資額的160%，但限額投資20萬(wàn)元以內(nèi)；4.允許于第三年初投入，年末收回，可獲利40%，但限額為10萬(wàn)元以內(nèi)；試為該公司確定一個(gè)使第三年末本利總和為最大的投資組合方案。2023/2/4109解：用xij表示第i年初投放到j(luò)

項(xiàng)目的資金數(shù)，則可投資的變量表如下2023/2/4110由于第三年末收回的本利只包含第三年初項(xiàng)目一的投資、第二年初項(xiàng)目三的投資和第三年初項(xiàng)目四的投資，因此目標(biāo)函數(shù)為：第一年初投資總額為30萬(wàn)，因此有：第二年初的投資額與第一年末收回的本利總額相同：第三年初投資額與第二年末收回的本利總額相同：2023/2/4111再考慮各項(xiàng)目的投資限額，得到該問(wèn)題的線性規(guī)劃模型如下：2023/2/4112例.生產(chǎn)、庫(kù)存與設(shè)備維修綜合計(jì)劃紅光廠有2臺(tái)車(chē)床、1臺(tái)鉆床、1臺(tái)磨床，承擔(dān)4種產(chǎn)品的生產(chǎn)任務(wù)。已知各種產(chǎn)品所需設(shè)備工時(shí)及單位產(chǎn)品的售價(jià)如表1所示。對(duì)產(chǎn)品今后3個(gè)月的市場(chǎng)最大需求（小于最大需求時(shí)可全部售出）及各產(chǎn)品今后3個(gè)月的成本分別如表2、