1、1 .一般線性規(guī)劃問題的數(shù)學(xué)模型，2 .圖解法，3 .單純形法原理，4 .單純形法的計(jì)算順序，5 .進(jìn)一步討論單純形法，6 .單純形法的改進(jìn)，7 .例子和Matlab的解法，第一章線性規(guī)劃和單純形法，1 .一般線性規(guī)劃問題的數(shù)學(xué)模型，如附圖所示一、問題的提出，有企業(yè)計(jì)劃生產(chǎn)I、ii兩種產(chǎn)品。 這兩種產(chǎn)品要分別用a、b、c、d四種設(shè)備加工。 生產(chǎn)產(chǎn)品I，各設(shè)備分別為2、1、4、0h，生產(chǎn)產(chǎn)品ii，各設(shè)備必須分別為2、2、0、4h。 已知在各設(shè)備的計(jì)劃期間生產(chǎn)這兩種產(chǎn)品的能力分別為12、8、16、12h，另外，生產(chǎn)產(chǎn)品I的企業(yè)可以獲得2元利潤(rùn)，生產(chǎn)產(chǎn)品ii的企業(yè)可以獲得3元利潤(rùn)，企業(yè)可以安排生產(chǎn)兩

2、種產(chǎn)品多少1 .一般線性規(guī)劃問題的數(shù)學(xué)模型，條件：實(shí)現(xiàn)目的：2，線性規(guī)劃問題的數(shù)學(xué)模型，三個(gè)組成部分：1 .決策變量：是決策者為了實(shí)現(xiàn)計(jì)劃目標(biāo)所采取的方案、措施，問題中應(yīng)確定的未知量。 2 .目標(biāo)函數(shù)：指定要實(shí)現(xiàn)問題的目的的請(qǐng)求，并且是被表示為決策變量的函數(shù)。 3 .約束條件：根據(jù)在確定變量取值時(shí)接收的各種可用資源的限制，被表示為包含確定變量的方程式或不等式。 一般線性規(guī)劃問題的數(shù)學(xué)模型：目標(biāo)函數(shù)：制約條件：簡(jiǎn)稱：矩陣形為：中：三，線性規(guī)劃問題的標(biāo)準(zhǔn)形，標(biāo)準(zhǔn)形：標(biāo)準(zhǔn)形的特征：4 .決定變量的值不為負(fù)。 1 .目標(biāo)函數(shù)求極大值，2 .制約條件都是方程式，制約條件右端的常數(shù)項(xiàng)都不是負(fù)，一般的線性規(guī)

3、劃問題是標(biāo)準(zhǔn)型：1 .目標(biāo)函數(shù)是極小值：令：即：2 .制約條件是不等式：(1)制約條件是“”的情況：可能：很明顯，(2)制約條件是“”的情況稱為剩馀變量。緩和變量和剩馀變量統(tǒng)稱為緩和變量，(3)目標(biāo)函數(shù)中的緩和變量的系數(shù)表示緩和變量和剩馀變量分別未被充分利用的資源和超過的資源，所以沒有被轉(zhuǎn)換成價(jià)值和利益，所以在目標(biāo)函數(shù)中系數(shù)為0。 3 .取值沒有制約的變量。 如果變量x表示產(chǎn)品的年計(jì)劃數(shù)和上一年計(jì)劃數(shù)的差，則x取的值是正還是負(fù)是明確的，在此情況下，可以：例如，將下一個(gè)線性計(jì)劃建模為標(biāo)準(zhǔn)形，解：取標(biāo)準(zhǔn)形：求解線性計(jì)劃問題：從滿足約束方程和約束不等式的決定變量中取值，找到目標(biāo)函數(shù)為最大的值。 四、

4、線性規(guī)劃問題的解、可行解：滿足制約條件的解稱為可執(zhí)行解，可執(zhí)行解的集合稱為可執(zhí)行域。 最佳解：使目標(biāo)函數(shù)為最大值的可執(zhí)行解。 基：約束方程的滿秩子矩陣被稱為規(guī)劃問題的一個(gè)基，基中的各列向量被稱為基向量，與基向量相對(duì)應(yīng)的變量被稱為基變量，其他變量被稱為非基變量。 基解：在制約方程式中，所有的非基變量都為0，可以解基變量的唯一的解，該解和非基變量的0一起構(gòu)成基解。 基本可執(zhí)行解：滿足變量的非負(fù)的基本解稱為基本可執(zhí)行解，可執(zhí)行基：對(duì)應(yīng)于基本可執(zhí)行解的基本稱為可執(zhí)行基，例4說明基本、基本變量、基本可執(zhí)行解和可執(zhí)行基是什么，實(shí)現(xiàn)目的： n維空間中線性規(guī)劃問題的概念的確立和解決一般的線性規(guī)劃問題的單求解下

5、一個(gè)線性規(guī)劃問題：2 .線性規(guī)劃問題的圖解法，畫出線性規(guī)劃問題的可能域：目標(biāo)函數(shù)的幾何意義：確定最佳解：圖解法的步驟：建立坐標(biāo)系，建立滿足圖中所示約束條件的解的范圍，創(chuàng)建目標(biāo)函數(shù)的圖表，確定最佳解。無限多最佳解的情況：目標(biāo)函數(shù)和某個(gè)制約條件正好平行，沒有邊界解(或沒有最佳解)的情況：可執(zhí)行域上沒有邊界，沒有可執(zhí)行解的情況：制約條件沒有共同范圍，圖解法的啟發(fā)：線性規(guī)劃問題的情況：唯一最佳解，無限多最佳解，沒有邊界解線性規(guī)劃問題存在可執(zhí)行域時(shí)，如果在可執(zhí)行域中存在作為凸集的線性規(guī)劃問題的最佳解，則最佳解或最佳解之一一定能在可執(zhí)行域的頂點(diǎn)取得的解題的想法是，首先尋找凸集的任一頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值。

6、 比較該相鄰頂點(diǎn)的函數(shù)值，如果更好，則按點(diǎn)移動(dòng)，直到找到最佳解為止。 3 .單純形法的原理、凸集：如果是集合c中的任意兩點(diǎn)，其連接上的所有點(diǎn)都是集合c中的點(diǎn)。 上圖的(1)(2)是凸點(diǎn)集合，(3)(4)不是凸點(diǎn)集合，因?yàn)轫旤c(diǎn)：對(duì)于凸點(diǎn)集合c中的點(diǎn)x，不存在c中的其他兩個(gè)不同點(diǎn)，所以x在它們的連接上時(shí)，將x稱為凸點(diǎn)集合的頂點(diǎn)。 一、線性規(guī)劃問題的基本定理，定理一線性規(guī)劃問題中存在可執(zhí)行解的話，問題的可執(zhí)行域就是凸集。 定理二線性規(guī)劃問題的基本可執(zhí)行解x對(duì)應(yīng)于線性規(guī)劃問題可執(zhí)行域(凸集)的頂點(diǎn)。 定理三、線性規(guī)劃問題中如果有最佳解的話，必然存在一個(gè)基本可行的解才是最佳解。 根據(jù)以上三個(gè)定理求出線性

7、規(guī)劃問題的最佳解，只要比較與可執(zhí)行區(qū)域(凸集)的各頂點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值即可，最大的是我們求出的最佳解。 定理1 :如果LP模型中存在可執(zhí)行解，則可執(zhí)行區(qū)域?yàn)橥辜?證明：假設(shè)maxz=CXst.AX=bX0，其可能域?yàn)閏，X1、X2為其可能解，X1X2，則X1c、X2c，即AX1=b、AX2=b、X10、X20， x為x1、x2連接線上的點(diǎn)，即x=x c是凸集合。 三個(gè)基本定理：引理：線性規(guī)劃問題的可執(zhí)行解X=(x1，x2，xn)T為基本可執(zhí)行解的充分條件是，與x的正分量對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。 證明： (1)必要性：與x基本可執(zhí)行解x的正分量對(duì)應(yīng)的系數(shù)列向量的線性獨(dú)立，可以設(shè)為X=(x

8、1，x2，xk，0，0)T，如果x是基本可執(zhí)行解，則根據(jù)基本可執(zhí)行解的定義，與x1，x2，xk對(duì)應(yīng)的系數(shù)列向量P1，P2，Pk是線性的(2)充分性：設(shè)與x正分量對(duì)應(yīng)的系數(shù)列向量的線性獨(dú)立x為基本可能解的a的等級(jí)為m，則x的正分量的個(gè)數(shù)km； 當(dāng)k=m時(shí)，x1、x2和xk的系數(shù)列向量P1、P2、 Pk構(gòu)成基礎(chǔ)，8756； x基本上是可能的解。 在k0、xj=0時(shí)，yj=ZJ=0，8756； pjyj=，j=1，n，pjyj=b(1)，j=1，r，pjzj=b(2)，j=1，r，(yj-zj)pj=0，j=1，r，(1)-(2)是必要的，(y1-Z1 ) P1 (y1 z1=CX1=CX0-C=z

9、max-C、z2=cX2=cx0c=zmaxcz0=zmaxz1、z0=zmaxz2、8756； z1=z2=z0，即X1、X2也是最佳解，如果X1、X2還不是頂點(diǎn)，則頂點(diǎn)可以這樣遞歸地推論直到成為最佳解為止。 因此，基本上找到可行的解作為最佳解是必然的。 定理3 :線性計(jì)劃模型中如果有最優(yōu)解，基本上一定存在可執(zhí)行的解。 證明：如果X0=(X10，X20，xn0)T是線性規(guī)劃模型的最佳解，則z0=zmax=CX0的X0基本上不是可能的解，即不是頂點(diǎn)，足夠小的話，X1=X0-0，x2=x0，即x1， x2是可能的解，簡(jiǎn)單的形法的計(jì)算步驟：初始基本上是可能的解，STOP，y，n，二，確定初始基本可

10、行解，線性規(guī)劃問題的最佳解必須在基本可行解中獲得，我們首先找到了初始基本可行解。 然后，切換至可以在別的基礎(chǔ)上執(zhí)行的解，直到找到最佳解為止。給出的線性規(guī)劃問題：所以約束方程的系數(shù)矩陣為：因?yàn)樵摼仃嚢粋€(gè)單位子矩陣，所以以該單位矩陣為基礎(chǔ)，一個(gè)基本可執(zhí)行解：其標(biāo)準(zhǔn)形式為：三，從初始基本可執(zhí)行解變換為另一個(gè)基本可執(zhí)行解，對(duì)初始可執(zhí)行解的系數(shù)矩陣進(jìn)行初等行變換，構(gòu)建一個(gè)新的單位矩陣從一個(gè)基本可執(zhí)行解到另一個(gè)基本可執(zhí)行解的轉(zhuǎn)換在不損失一般性的情況下，基本可執(zhí)行解X0=(x10，x20，x0，XM 0，0， 0)T，前m個(gè)分量為正值，秩為m，其系數(shù)矩陣為p1p2、 pmpm1、 pj.pnb 10、0

11、a1、m1a1j1nb101、0a2、m1a2ja2nb200、1am m 1amjamnbm， 喀嚓喀嚓喀嚓喀嚓喀嚓喀嚓地653即Pj=aijpi，移項(xiàng)，兩端乘以0 (2)，i=1，m，i=1，m 通過全部將xi0-aij0取得得足夠小，i=1、m、X1=(x10-a1j、x20-a2j、xm0-amj、0、0)T也是可以理解的。 假設(shè)min-aij0=-，則X1的前m個(gè)組件中至少有一個(gè)xL1為0。 xi0，aij，aLj，xL0，I，8756； p1、P2、PL-1、PL 1、Pm、Pj與線性沒有關(guān)系。x1也是基本上可能的解。 四、最優(yōu)檢查和解的判別，四、最優(yōu)檢查和解的判別，在所有情況下，

12、與現(xiàn)有頂點(diǎn)相對(duì)應(yīng)的基本可執(zhí)行解是最優(yōu)解。 在所有情況下，還有一個(gè)非基變量，在能發(fā)現(xiàn)的情況下，這個(gè)線性規(guī)劃問題有無限的最佳解。 3 .存在一個(gè)者，存在向量的所有分量，并且可選地，如果是一定的，則存在邊界解。 由于0，有以下結(jié)論： z1=z0 j，4 .簡(jiǎn)單形法的計(jì)算步驟，第一步：求初始可執(zhí)行解的列初始簡(jiǎn)單形表，表的最上列是各變量的目標(biāo)函數(shù)中的系數(shù)，最左列是各基變量的目標(biāo)函數(shù)中的系數(shù)。 2 .表的最后一行是檢查數(shù)。 第二步：進(jìn)行最佳性檢查，表中所有的檢查數(shù)，表中的基本可執(zhí)行解是問題的最佳解，到現(xiàn)在為止計(jì)算了，不然就轉(zhuǎn)到下一步。 第三步：轉(zhuǎn)換為新的基本可執(zhí)行解，構(gòu)建新的單純形表，1 .確定變換變量，

13、2 .確定變換變量，3 .轉(zhuǎn)換為新的單純形表，(1)、(2)、(3)檢測(cè)常數(shù)的求出方法與初始單純形表的求出方法相同，第四步重復(fù)三個(gè)步驟，例子5用簡(jiǎn)單形式法求解線性規(guī)劃問題，解：把原來的線性規(guī)劃問題變成標(biāo)準(zhǔn)形式的第一步驟：基于系數(shù)矩陣的單位矩陣部分，得到初始基的可執(zhí)行解，列出初始簡(jiǎn)單形式表，第三步驟：1 .確定變換變量，2 .確定變換變量由于上表中所有的檢驗(yàn)數(shù)都在零以下，所以得到了最佳解，最佳解為：代入目標(biāo)函數(shù)，最佳值：計(jì)算檢驗(yàn)數(shù)具有相同的值時(shí)，可以從其中選擇一個(gè)變量作為代入變量。 如果計(jì)算值相同，也可以從其中選擇一個(gè)作為轉(zhuǎn)換變量。 注意：5 .簡(jiǎn)單形法的進(jìn)一步研究，一、人工變量法，上節(jié)例5的線

14、性規(guī)劃問題的考察：化標(biāo)準(zhǔn)形：其系數(shù)矩陣為：系數(shù)矩陣中存在單位矩陣，因此容易找到初始可執(zhí)行基。 然而，可能不同，考慮下一個(gè)線性規(guī)劃問題：標(biāo)準(zhǔn)型：例6，此問題的系數(shù)矩陣：因?yàn)榇司仃囍胁话瑔挝痪仃?，所以很難找到初始基礎(chǔ)。 當(dāng)這個(gè)線性規(guī)劃問題的系數(shù)矩陣不包含單位矩陣時(shí)，我們通常采用添加人工變量的方法，人工構(gòu)建單位矩陣。 這種方法是人工變量法。 為了構(gòu)建單位矩陣，在系數(shù)矩陣中添加了兩列單位列向量，系數(shù)矩陣為：線性規(guī)劃問題的制約條件為：人為地添加，因此被稱為對(duì)應(yīng)的變量，人工變量。在添加目標(biāo)函數(shù)中人工變量的系數(shù)：人工變量之前，在線性規(guī)劃問題的標(biāo)準(zhǔn)形式中，每個(gè)約束條件都已經(jīng)是等式約束，并且為了確保等式約束是

15、不變的，在最佳解中，人工變量的取值必須為0。 因此，如果將目標(biāo)函數(shù)中的人工變量的系數(shù)設(shè)為任意大的負(fù)值來表示為“”的話，只要人工變量不使值為零，目標(biāo)函數(shù)就不能極大化。 由于目標(biāo)函數(shù)加：m處理人工變量的方法，大m法，求解過程：所以最佳解是：二，二階段法，大m處理人工變量時(shí)，計(jì)算機(jī)求解產(chǎn)生了錯(cuò)誤，從而產(chǎn)生了二階段法。 的雙曲馀弦值。 第一階段：首先，解決目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題。 將目標(biāo)函數(shù)中其他變量的系數(shù)設(shè)為零，將人工變量的系數(shù)設(shè)為某個(gè)正的常數(shù)(一般為1 )，在保持原來的問題約束條件的同時(shí)，求出將該目標(biāo)函數(shù)極小化時(shí)的解。 第二階段：從第一階段的最終單純形表中刪除人工變量，根據(jù)原問題的目標(biāo)函數(shù)繼續(xù)尋找原問題的最佳解。 三、關(guān)于解的判別，所有情況下，又有一個(gè)非基變量，可以發(fā)現(xiàn)的情況下，這個(gè)線性規(guī)劃問題有無限的最佳解。 例7 .解線性規(guī)劃問題：在圖解法中，我們知道這個(gè)問題有無限解。 其標(biāo)準(zhǔn)形為：用單純形法計(jì)算，最終的單純形表為：從表中得到最佳解