1、第一章 線(xiàn) 性 規(guī) 劃及單純形法,1、一般線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型,2、圖解法,4、單純形法的計(jì)算步驟,5、單純形法的進(jìn)一步討論,6、線(xiàn)性規(guī)劃模型的應(yīng)用,3、單純形法原理,為了完成一項(xiàng)任務(wù)或達(dá)到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務(wù)或達(dá)到一定的目的，這個(gè)過(guò)程就是規(guī)劃。,例1 有一正方形鐵皮，如何截取x使容積為最大？,x,a,此為無(wú)約束極值問(wèn)題,一、一般線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型,（一）、問(wèn)題的提出,例2 已知資料如下表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？或如何考慮利潤(rùn)大，產(chǎn)品好銷(xiāo)。,模 型,max Z = 2x1 + 3x2,x1 0 , x2 0,s.t.,2x1

2、 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12,此為帶約束的極值問(wèn)題,1、問(wèn)題中總有未知的變量，需要我們?nèi)ソ鉀Q。,要求：有目標(biāo)函數(shù)及約束條件，一般有非負(fù)條件存在，由此組成規(guī)劃數(shù)學(xué)模型。,如果在規(guī)劃問(wèn)題的數(shù)學(xué)模型中，變量是連續(xù)的（數(shù)值取實(shí)數(shù)）其目標(biāo)函數(shù)是有關(guān)線(xiàn)性函數(shù)（一次方），約束條件是有關(guān)變量的線(xiàn)性等式或不等式，這樣，規(guī)劃問(wèn)題的數(shù)學(xué)模型是線(xiàn)性的。反之，就是非線(xiàn)性的規(guī)劃問(wèn)題（其中一個(gè)條件符合即可）。,（二）線(xiàn)性規(guī)劃問(wèn)題的數(shù)學(xué)模型,目標(biāo)函數(shù)：,約束條件：,2、線(xiàn)性規(guī)劃數(shù)學(xué)模型的一般形式,也可以記為如下形式：,目標(biāo)函數(shù)：,約束條件：,如將上例用表格表示如下：,設(shè)變量,向 量 形

3、 式：,矩陣形式：,規(guī) 劃,確定型 隨機(jī)型,靜態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃,線(xiàn) 性規(guī) 劃 非線(xiàn)性規(guī)劃,整數(shù)規(guī)劃 非整數(shù)規(guī)劃,整數(shù)規(guī)劃 非整數(shù)規(guī)劃,3、規(guī)劃類(lèi)型,（三）線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式,1、標(biāo)準(zhǔn)形式,其中bi為非負(fù),2、特征： .目標(biāo)函數(shù)為求極大值，也可以用求極小值； .所有約束條件（非負(fù)條件除外）都是等式，右端常數(shù)項(xiàng)為非負(fù)； .變量為非負(fù)。,3、轉(zhuǎn)換方式：,.目標(biāo)函數(shù)的轉(zhuǎn)換,如果是求極小值即 ，則可將目標(biāo)函數(shù)乘以（1），可化為求極大值問(wèn)題。,也就是：令 ，可得到上式。,即,.約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。,稱(chēng)為松弛變量,稱(chēng)為剩余變量,.變量的變換,若存在取值無(wú)約束的變量 ，可令 其中：,例 1

4、 將下列線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式,為無(wú)約束（無(wú)非負(fù)限制）,解: 用 替換 ，且 ，,將第3個(gè)約束方程兩邊乘以（1）,將極小值問(wèn)題反號(hào)，變?yōu)榍髽O大值,標(biāo)準(zhǔn)形式如下：,引入變量,例2 將線(xiàn)性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型,為無(wú)約束,解：,例3 將下述線(xiàn)性規(guī)劃模型化為標(biāo)準(zhǔn)形式。,標(biāo)準(zhǔn)形式,（四）線(xiàn)性規(guī)劃問(wèn)題的解,1、解的概念, 可行解：滿(mǎn)足約束條件、的解為可行解。所有解的集合為可行解的集或可行域。, 最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。, 基：B是矩陣A中mn階非奇異子矩陣（B0），則B是一個(gè)基。,則稱(chēng) Pj ( j = 1 2 m) 為基向量。 Xj 為基變量，否則為非基變量。, 基解：滿(mǎn)足條件，但不滿(mǎn)足條

5、件的所有基對(duì)應(yīng)的解，最多為 個(gè)。, 基可行解：滿(mǎn)足非負(fù)約束條件的基解，簡(jiǎn)稱(chēng)基可行解。, 可行基：對(duì)應(yīng)于基可行解的基稱(chēng)為可行基。,非可行解,可 行 解,基解,基可行解,Max z=2x1+3x2 st. x1+x23 x1+2x24 x1,x20,Max z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x40,A=,x1 x2 x3 x4,1 1 1 0 1 2 0 1,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。,設(shè),B=,1 0 0 1,，令,，則,| B |=10,令 x1=x2 =0

6、，則 x3 =3, x4=4，X=(0,0,3,4)T,例：,x3 x4,基變量,令,B=,1 1 1 0,x1 x3,，則,令 x2=x4 =0，則 x3 =-1, x1=4，X=(4,0,-1,0)T,| B |=-10,非基可行解,基可行解,標(biāo)準(zhǔn)化,建立直角坐標(biāo) ，圖中陰影部分及邊界上的點(diǎn)均為其解，是由約束條件來(lái)反映的。,例1,二、圖 解 法,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,作 圖, 最 優(yōu) 解：x1 = 4 x2 = 2,有唯一最優(yōu)解，Z = 14,x2,x1,(4 2),例2,例3,無(wú)窮多最優(yōu)解,無(wú)界解,x1,x1,x2,x2,x1,x2,無(wú)可行解,例4,

7、練習(xí)1, 線(xiàn)性規(guī)劃問(wèn)題的可行域是凸集（凸多邊形）。,凸集,凸集,不是凸集,頂 點(diǎn), 最優(yōu)解一定是在凸集的某一頂點(diǎn)實(shí)現(xiàn)（頂點(diǎn)數(shù)目不超過(guò) 個(gè)）,三、單純形法原理, 先找一個(gè)基可行解，與周?chē)旤c(diǎn)比較，如不是最大，繼續(xù)比較，直到找出最大為止。,3、解的情況,唯 一 解 無(wú) 窮 解 無(wú) 界 解 無(wú)可行解,有最優(yōu)解,無(wú)最優(yōu)解,（一）、基本思想,將模型的一般形式變成標(biāo)準(zhǔn)形式，再根據(jù)標(biāo)準(zhǔn)型模型，從可行域中找一個(gè)基可行解，并判斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個(gè)基可行解，當(dāng)目標(biāo)函數(shù)達(dá)到最大時(shí)，得到最優(yōu)解。,（二）、線(xiàn)性規(guī)劃模型的標(biāo)準(zhǔn)形式,1、標(biāo)準(zhǔn)形式,四、單純形法,（三）、單純形法,例一、,

8、變成標(biāo)準(zhǔn)型,約束方程的系數(shù)矩陣,為基變量,為非基變量,I 為單位矩陣且線(xiàn)性獨(dú)立,Max z=2x1+3x2 st. x1+x23 x1+2x24 x1,x20,Max z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x40,A=,x1 x2 x3 x4,1 1 1 0 1 2 0 1,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。,設(shè),B=,1 0 0 1,，令,，則,| B |=10,令 x1=x2 =0，則 x3 =3, x4=4，X=(0,0,3,4)T,回顧：,x3 x4,基變量,令

9、,B=,1 1 1 0,x1 x3,，則,令 x2=x4 =0，則 x3 =-1, x1=4，X=(4,0,-1,0)T,| B |=-10,非基可行解,基可行解,標(biāo)準(zhǔn)化,令：,則：, 基本可行解為（0 0 12 8 16 12） 此時(shí)，Z = 0,然后，找另一個(gè)基可行解。即將非基變量換入基變量中，但保證其余的非負(fù)。如此循環(huán)下去，直到找到最優(yōu)解為止。,注意：為盡快找到最優(yōu)解，在換入變量時(shí)有一定的要求。如將目標(biāo)系數(shù)大的先換入等。,找出一個(gè)初始可行解,是否最優(yōu),轉(zhuǎn)移到另一個(gè)目標(biāo)函數(shù) （找更大的基可行解）,最優(yōu)解,是,否,循 環(huán),直到找出為止，核心是：變量迭代,結(jié)束,其步驟總結(jié)如下：,當(dāng) 時(shí)， 為換

10、入變量,確定換出變量,為換出變量,接下來(lái)有下式：,用高斯法，將 的系數(shù)列向量換為單位列向量，其步驟是：,結(jié)果是：,代入目標(biāo)函數(shù)：,有正系數(shù)表明：還有潛力可挖，沒(méi)有達(dá)到最大值；,此時(shí)：令 得到另一個(gè)基本可行解 （0，3，6，2，16，0）,有負(fù)系數(shù)表明：若要剩余資源發(fā)揮作用，就必須支付附加費(fèi)用。當(dāng) 時(shí)，即不再利用這些資源。,如此循環(huán)進(jìn)行，直到找到最優(yōu)為止。,本例最優(yōu)解為： （4，2，0，0，0，4）,（四）、單純形表,例 題：,2 3 0 0 0 0,12/2,8/2,12/4,3,x2,3,0,1,0,0,0,1/4,2,6,2,0,1,0,0,-1/2,1,0,0,1,0,0,-1/2,-9

11、,0,0,0,0,2,-3/4,2 0 0 0 0 -3/4,6/2,2,16/4,0 0 0 -2 0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5 x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,0 0 0 -2 0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5

12、x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,練習(xí),（一）、模型情況 變 量：xj0 xj0 xj無(wú)約束 結(jié) 1、組成 約束條件： = b 目標(biāo)函數(shù)： max min 果 2 、變量 xj0 令 xj= -xj ， xj0 xj0 不處理 xj 無(wú)約束 令xj = xj xj, xj0 , xj0,唯一最優(yōu) 無(wú)窮最優(yōu) 無(wú)界解 無(wú)可行解,五、單純形法的進(jìn)一步討論,例：,加入人工變量后，目的是找到一個(gè)單位向量，叫人工基。其目標(biāo)價(jià)值系數(shù)要確定，但不能影響目標(biāo)函數(shù)的取值。一般可采用兩種方法處理：大M法和兩階段法。,即假定人工變量在目標(biāo)函數(shù)中的系

13、數(shù)為M（任意大正數(shù)），如果是求極大值，需加-M；如果是求極小值，需加M。如基變量中還存在M，就不能實(shí)現(xiàn)極值。,.大M法：,最優(yōu)解為（4 1 9 0 0 0 0），Z = 2,最優(yōu)解為（4 1 9 0 0 0 0），Z = 2,用計(jì)算機(jī)處理數(shù)據(jù)時(shí)，只能用很大的數(shù)代替M,可能造成計(jì)算機(jī)上的錯(cuò)誤，故多采用兩階段法。,第一階段： 在原線(xiàn)性規(guī)劃問(wèn)題中加入人工變量，構(gòu)造如下模型：,.兩階段法：,對(duì)上述模型求解（單純形法），若W=0,說(shuō)明問(wèn)題存在基本可行解，可以進(jìn)行第二個(gè)階段；否則，原問(wèn)題無(wú)可行解，停止運(yùn)算。,第二階段：在第一階段的最終表中，去掉人工變量，將目標(biāo)函數(shù)的系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，作為第二階

14、段計(jì)算的初始表（用單純形法計(jì)算）。,例：,第一階段,第二階段,最優(yōu)解為（4 1 9 0 0），目標(biāo)函數(shù) Z = -2,設(shè)規(guī)劃模型約束條件為 ，需加入人工變量 ，而得到一個(gè)mm的單位矩陣，即基變量組合。因人工變量為虛擬變量，且存在于初始基本可行解中，需要將它們從基變量中替換出來(lái)。若基變量中不含有非零的人工變量，表示原問(wèn)題有解。若當(dāng) ，而還有人工變量（非零）時(shí)，則表示原問(wèn)題無(wú)可行解。,1、目標(biāo)函數(shù)：max , min,3、無(wú)可行解的判斷：運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止， 仍含有人工變量，無(wú)可行解。,5、退化： 即計(jì)算出的（用于確定換出變量）存在有兩個(gè)以上相同的最小比值，會(huì)造成下一次迭代中由一個(gè)或幾個(gè)基變量等

15、于零，這就是退化（會(huì)產(chǎn)生退化解）。 雖任意換出變量，目標(biāo)函數(shù)值不變，但此時(shí)不同的基卻表示為同一頂點(diǎn)，其特例是永遠(yuǎn)達(dá)不到最優(yōu)解。需作如下處理： .當(dāng) 中出現(xiàn)兩個(gè)以上最大值時(shí)，選下標(biāo)最小的非基變量為換入變量； .當(dāng)中出現(xiàn)兩個(gè)以上最小值時(shí)，選下標(biāo)最小的基變量為換出變量。,根據(jù)上表列出初始單純形表 A,（二）、線(xiàn)性規(guī)劃小結(jié),A,練習(xí),作業(yè),一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿(mǎn)足以下條件時(shí)，才能建立線(xiàn)性規(guī)劃模型。 .要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線(xiàn)性函數(shù)； .存在著多種方案； .要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線(xiàn)性等式或不等式描述。,六、線(xiàn)性規(guī)劃模型的應(yīng)用,（一）、資源的合理

16、利用,一般提法： 某廠計(jì)劃在下一生產(chǎn)周期內(nèi)生產(chǎn)B1,B2, Bn種產(chǎn)品，要消耗A1,A2, Am種資源，已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限制以及每件產(chǎn)品可獲得的利潤(rùn)如表所示，問(wèn)如何安排生產(chǎn)計(jì)劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤(rùn)最大？,（二）、生產(chǎn)組織與計(jì)劃問(wèn)題,一般提法：某工廠用機(jī)床A1,A2, Am 加工B1,B2, Bn 種零件。在一個(gè)周期內(nèi)，各機(jī)床可能工作的機(jī)時(shí)（臺(tái)時(shí)），工廠必須完成各種零件的數(shù)量、各機(jī)床加工每個(gè)零件的時(shí)間（機(jī)時(shí)/個(gè)）和加工每個(gè)零件的成本（元/個(gè)）如表所示，問(wèn)如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使總成本最低？,（三）、合理下料問(wèn)題,一般提法 設(shè)用

17、某種原材料截取零件A1,A2, Am的毛坯。根據(jù)以往的經(jīng)驗(yàn)，在一種原材料上可以有B1,B2, Bn種不同的下料方式，每種下料方式可截得的各種毛坯個(gè)數(shù)以及每種零件的需要量如表所示，問(wèn)應(yīng)如下料才能既滿(mǎn)足需要又使原材料消耗最少？,現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米，需要截取2.5米長(zhǎng)的毛坯100根，長(zhǎng)1.3米的毛坯200根。問(wèn)如何才能既滿(mǎn)足需要，又能使總的用料最少？,100 200,3 2 1 0 0 2 4 6,2.5米 1.3米,需要 根數(shù),一 二 三 四,下料 下料 毛 件數(shù) 方式 坯型號(hào),設(shè)變量為 第 j 種方法的所有 原料件數(shù),例題1：,（四）、合理配料問(wèn)題,一般提法 某飼養(yǎng)場(chǎng)用n種飼料B1,B

18、2, Bn配置成含有m種營(yíng)養(yǎng)成分A1,A2, Am的混合飼料，其余資料如表所示。問(wèn)應(yīng)如何配料，才能既滿(mǎn)足需要，又使混合飼料的總成本最低？,例題2：,某人每天食用甲、乙兩種食物（如豬肉、雞蛋），其資料如下： 問(wèn)兩種食物各食用多少， 才能既滿(mǎn)足需要、又使 總費(fèi)用最??？,設(shè)：Xj 表示Bj 種食 物用量。,（五）、運(yùn) 輸 問(wèn) 題,已知資料如表所示：,模型如下：,某運(yùn)輸問(wèn)題的資料如下：,例題3：,（六）、作物布局問(wèn)題,此外，還有連續(xù)投資、投入產(chǎn)出等模型問(wèn)題。,例2.2 某地區(qū)有三個(gè)礦山A1，A2，A3，生產(chǎn)同一種礦物。另外有四個(gè)這種礦物消費(fèi)地（鐵廠）B1，B2，B3，B4。各礦山產(chǎn)量及鐵廠的需要量和礦

19、山將礦物運(yùn)到鐵廠的單位運(yùn)價(jià)如表2-2。問(wèn)應(yīng)如何調(diào)運(yùn)，才使總運(yùn)費(fèi)最?。?（一）運(yùn)輸問(wèn)題的數(shù)學(xué)模型,解：該題有兩個(gè)限制條件：一個(gè)是產(chǎn)量，一個(gè)是需量。目標(biāo)是總運(yùn)費(fèi)最省。 設(shè)：xij表示從第i個(gè)礦山運(yùn)往第j個(gè)鐵廠的礦物運(yùn)量。這樣得到以下兩組線(xiàn)性方程組： （1）各礦山礦物的生產(chǎn)量與運(yùn)出量平衡方程：,（2）各鐵廠礦物供應(yīng)量與需要量平衡方程,（3）礦物的運(yùn)輸量應(yīng)非負(fù),（4）目標(biāo)函數(shù),（二）資源最優(yōu)利用的數(shù)學(xué)模型,例2.3 某廠生產(chǎn)A、 B產(chǎn)品1kg需用資源數(shù)見(jiàn)表2-3 ，已知生產(chǎn)A1kg價(jià)值7千元，B1kg12千元。應(yīng)該生產(chǎn)A和B產(chǎn)品各多少才能使總價(jià)值最大。,解：設(shè)A、B兩產(chǎn)品的計(jì)劃產(chǎn)量為x1、x2 則數(shù)學(xué)

20、模型為：,（三）機(jī)床負(fù)荷問(wèn)題的數(shù)學(xué)模型,例2.4 設(shè)某車(chē)間需加工甲、乙兩種零件。這兩種零件可以在三種不同機(jī)床銑床、六角車(chē)床、自動(dòng)機(jī)床上進(jìn)行加工。機(jī)床數(shù)及生產(chǎn)效率如表2-4。,（三）機(jī)床負(fù)荷問(wèn)題的數(shù)學(xué)模型,此表說(shuō)明，在一臺(tái)銑床上一個(gè)工作日可以加工15件甲零件或20件乙零件，余類(lèi)同。該車(chē)間共有3臺(tái)銑床，3臺(tái)六角車(chē)床，1臺(tái)自動(dòng)機(jī)床。問(wèn)如何合理安排機(jī)床的加工任務(wù)，使得在產(chǎn)品配套比例條件下（設(shè)甲、乙零件1:1配套），使成套產(chǎn)品的數(shù)量達(dá)到最大。,解：設(shè)xij表示第i種機(jī)床用來(lái)生產(chǎn)第j種產(chǎn)品的臺(tái)數(shù)，則數(shù)學(xué)模型為： （1）加工甲、乙產(chǎn)品機(jī)床臺(tái)數(shù)平衡方程：,（2）甲、乙零件配套比例平衡方程：,（3）變量非負(fù)：,（4）目標(biāo)函數(shù)求成套產(chǎn)品數(shù)量最大：,（四）人員分配的數(shù)學(xué)模型,例2.5 有四件工作，分配給四人，每人能力不同，工作效率也不同如表2-5，規(guī)定每項(xiàng)工作由一個(gè)人擔(dān)任和每個(gè)工人只分配一項(xiàng)工作。問(wèn)應(yīng)分配哪個(gè)人去完成哪項(xiàng)工作可使總效率達(dá)到最大。,解：設(shè)xij表示i個(gè)工人分配擔(dān)任第j項(xiàng)工作的情況，并xij取1和0兩個(gè)值， xij=1，表示第i個(gè)工人分配擔(dān)任第j項(xiàng)工作； xij