第二章-線(xiàn)性規(guī)劃問(wèn)題與計(jì)算機(jī)求解mem運(yùn)籌學(xué)

1、第二章　線(xiàn)性規(guī)劃問(wèn)題與計(jì)算機(jī)求解,§1　問(wèn)題的提出 §2　圖解法 §3　單純形法 §4 計(jì)算機(jī)求解,§1　問(wèn)題的提出,例1. 某工廠(chǎng)在計(jì)劃期內(nèi)要安排Ⅰ、Ⅱ兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、資源的限制，如下表：?jiǎn)栴}：工廠(chǎng)應(yīng)分別生產(chǎn)多少單位Ⅰ、Ⅱ產(chǎn)品才能使工廠(chǎng)獲利最多？,設(shè)生產(chǎn)產(chǎn)品Ⅰ數(shù)量為x1,產(chǎn)品Ⅱ數(shù)量為x2 , 線(xiàn)性規(guī)劃

2、模型為：產(chǎn)品 Ⅰ利潤(rùn)：84 – (1×10 設(shè)備+ 2×12 原料A) = 50 (元)產(chǎn)品BⅡ利潤(rùn)：140 – (1×10 設(shè)備+1×12 原料A +1×18 原料B) = 100 (元) 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 ≤ 300

3、 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0,例2. 某飼料公司希望用玉米、紅薯兩種

4、原料來(lái)配置一種混合飼料，已知兩種原料含三種營(yíng)養(yǎng)成分和混合飼料對(duì)營(yíng)養(yǎng)成分的要求如下表：?jiǎn)栴}：公司應(yīng)任何采購(gòu)兩種原材料，使即滿(mǎn)足營(yíng)養(yǎng)要求，又使成本最少？,線(xiàn)性規(guī)劃模型：混合飼料中玉米數(shù)量x1，紅薯數(shù)量x2 目標(biāo)函數(shù)：Min z = 2 x1 + 1.8 x2 約束條件：s.t. 8 x1 + 4x2 ≥ 20

5、 3x1 + 6 x2 ≥18 x1 + 5x2 ≥ 16 x1 , x2 ≥ 0,線(xiàn)性規(guī)劃問(wèn)題主要類(lèi)型,資源分配問(wèn)題（resource-allocation）以?符號(hào)表

6、示的函數(shù)約束稱(chēng)為資源約束，這些限制要求使用的資源必須小于等于所能提供的資源的數(shù)量。資源分配問(wèn)題的共性就是它們的函數(shù)約束全部為資源約束。 使用的資源數(shù)量 ? 可用的資源數(shù)量成本收益平衡問(wèn)題 （cost-benefit-trade-off）以?符號(hào)表示的函數(shù)約束為收益約束，形式為收益取得的水平必須大于等于最低可接受水平。收益約束反映了管理層所規(guī)定的目標(biāo)。如果所有約束均為收益約束，這一問(wèn)題為成本收益平衡問(wèn)題。 完成的水

7、平 ? 最低可接受的水平,網(wǎng)絡(luò)配送問(wèn)題（distribution-network）以＝符號(hào)表示的函數(shù)約束稱(chēng)為確定需求的約束，它們表示了一定數(shù)量的確定的需求，提供的數(shù)量等于要求的數(shù)量。網(wǎng)絡(luò)配送問(wèn)題的共性就是它們的主要函數(shù)約束為一種特定形式的確定需求的約束。 提供的數(shù)量＝需要的數(shù)量 混合問(wèn)題（mixed Problem）除以上三類(lèi)以外的問(wèn)題，這一類(lèi)型包括了三類(lèi)約束函數(shù),建模過(guò)程1.理解要解決的問(wèn)題，了解解題目標(biāo)和條件；

8、2.定義決策變量（ x1 ，x2 ，… ，xn ），每一組值表示一個(gè)方案； Decision variables 決策變量3.用決策變量的函數(shù)形式寫(xiě)出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)； Objective function 目標(biāo)函數(shù)4.用一組決策變量的線(xiàn)性等式或線(xiàn)性不等式表示解決問(wèn)題過(guò)程中必須遵循的約束條件; Constraints 約束,一般形式目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + …

9、+ cn xn 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… ……

10、 am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 非負(fù)性,例1.目標(biāo)函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400

11、 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標(biāo)值 z = 27500,§2　圖 解 法,對(duì)于只有兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題，可以在平面直角坐標(biāo)系上作

12、圖表示線(xiàn)性規(guī)劃問(wèn)題的有關(guān)概念，并求解。 下面通過(guò)例1詳細(xì)講解其方法：,§2圖解法 畫(huà)出可行域 滿(mǎn)足約束的區(qū)域,(1)分別取決策變量X1 , X2 為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1的每個(gè)約束條件都代表一個(gè)半平面。,（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線(xiàn)，然后確定不等式所決定的半平面。,（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-

13、1所示。,§2 圖 解 法 確定等值線(xiàn)與梯度,（4）目標(biāo)函數(shù)z =50x1+100x2，當(dāng)z取某一固定值時(shí)得到一條直線(xiàn)，直線(xiàn)上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱(chēng)之為“等值線(xiàn)”。平行移動(dòng)等值線(xiàn)，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，O是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。,250,200,,,,,,,43,§2　圖解法 確定最優(yōu)解,平行移動(dòng)等值線(xiàn)，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行

14、域內(nèi)實(shí)現(xiàn)了最大化,B的坐標(biāo)為最優(yōu)解。解方程組得最優(yōu)解：x1=50, x2=250, 這時(shí)z =27500。點(diǎn)A，B，C，D，O是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限,x2= 250,x1+ x2=300,,,31,x1+x2=300,,,,E,,重要結(jié)論：如果線(xiàn)性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解；無(wú)窮多個(gè)最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)?max z=50x1+50x2，則線(xiàn)段BC上的

15、所有點(diǎn)都代表了最優(yōu)解；無(wú)界解。即可行域的范圍延伸到無(wú)窮遠(yuǎn)，目標(biāo)函數(shù)值可以無(wú)窮大或無(wú)窮小。一般來(lái)說(shuō)，這說(shuō)明模型有錯(cuò)，忽略了一些必要的約束條件；無(wú)可行解。若在例1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x2≥1200，則可行域?yàn)榭沼颍淮嬖跐M(mǎn)足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。,進(jìn) 一 步 討 論 求極小化問(wèn)題,例2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350噸（A，B兩種材料有一定替代性），其中A原料至少購(gòu)進(jìn)125噸

16、。但由于A(yíng)，B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的價(jià)格為2萬(wàn)元，每噸B原料的價(jià)格為3萬(wàn)元，試問(wèn)在滿(mǎn)足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買(mǎi)A，B兩種原料，使得購(gòu)進(jìn)成本最低？,解：目標(biāo)函數(shù)： Min f = 2x1 + 3 x2 約束條件： s.t. x1 + x2

17、 ≥ 350 x1 ≥ 125 2x1 + x2 ≤ 600 x1 , x2 ≥ 0 采用圖解法。如下圖：得Q點(diǎn)坐標(biāo)（250，100）為最優(yōu)解。,線(xiàn)性規(guī)劃的標(biāo)

18、準(zhǔn)化,一般形式目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + … + cn xn 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2

19、 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 標(biāo)準(zhǔn)形式目標(biāo)函數(shù)： Max z = c

20、1 x1 + c2 x2 + … + cn xn 目標(biāo)最大化； 約束條件： s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 約束為等式；

21、 …… …… am1 x1 + am2 x2 + … + amn xn = bm決策變量均非負(fù)； x1 ，x2 ，… ，xn ≥ 0，bi ≥0 右端項(xiàng)非負(fù)。,1.極小化目標(biāo)函數(shù)的問(wèn)題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2

22、 + … + cnxn (可以)令 z ＝ -f ， 則該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即 Max z =－c1x1－c2x2 － …－cnxn 但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即 Min f ＝－Max z2 右端項(xiàng)有負(fù)值的問(wèn)題： 如 bi<0，則把該等式約束兩端同時(shí)乘以－1，得到： －ai1 x

23、1－ai2 x2 － … － ain xn = － bi,非標(biāo)準(zhǔn)形式的線(xiàn)性規(guī)劃非標(biāo)準(zhǔn)形式的線(xiàn)性規(guī)劃,非標(biāo)準(zhǔn)形式的線(xiàn)性規(guī)劃非標(biāo)準(zhǔn)形式的線(xiàn)性規(guī)劃,3、約束條件不是等式的問(wèn)題：1）設(shè)約束條件為： ai1 x1+ai2 x2+ … +ain xn ≤bi 可以引進(jìn)一個(gè)新的松弛變量 s ，使它等于約束右邊與左邊之差 s =bi–(ai1 x1 + ai2 x2 + … + ain xn ) 顯然，s≥0， 這時(shí)新的約束條件成為

24、 ai1 x1+ai2 x2+ … +ain xn+s = bi2） 當(dāng)約束條件為： ai1 x1+ai2 x2+ … +ain xn ≥ bi 時(shí) 類(lèi)似地令剩余變量 s =(ai1 x1+ai2 x2+ … +ain xn)－ bi ； s≥0， 這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ … +ain xn－s = bi4. 當(dāng)某一個(gè)變量xj無(wú)約束，既沒(méi)有非負(fù)約束時(shí)，可以令 xj

25、 = xj’－xj” 其中 xj’≥0， xj”≥0,例5：將以下線(xiàn)性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式  Min f = 2 x1－3x2 + 4 x3 s.t. 3 x1 + 4x2 － 5 x3 ≤6 2 x1 + x3 ≥8 x1 + x2 + x3 = －9

26、 x1 , x3 ≥ 0 ， x2 無(wú)約束解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 z = －f = －2x1+3x2－4x3 其次考慮約束，有2個(gè)不等式約束，引進(jìn)松弛變量 x4，x5 ≥0。 第三個(gè)約束條件的右端值為負(fù)，在等式兩邊同時(shí)乘－1。 x2 無(wú)約束， 令 x2 = x2’－x2” 其中 x2’≥0， x2”≥0,通過(guò)以上變換，可以得到以下標(biāo)準(zhǔn)形式的線(xiàn)性規(guī)劃

27、問(wèn)題： Max z = －2x1 + 3 (x2’－x2”) － 4x3 s.t. 3x1+ 4(x2’－x2”) －5x3 +x4 = 6 2x1 + x3 － x5 = 8 －x1 －(x2’－x2”)

28、－x3 = 9 x1 , x2’, x2” , x3 , x4 , x5 ≥ 0,§3　單純形法,§3.1　單純形法的基本思路和原理單純形法的基本思路：從可行域中某一個(gè)頂點(diǎn)開(kāi)始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是,則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱(chēng)之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函

29、數(shù)值最優(yōu)的解，或者能判斷出線(xiàn)性規(guī)劃問(wèn)題無(wú)最優(yōu)解為止。通過(guò)例1的求解來(lái)介紹單純形法:在加上松弛變量之后我們可得到（增廣形式）標(biāo)準(zhǔn)型如下：目標(biāo)函數(shù)：max z＝ 50x1+100 x2 max z＝ 50x1+100 x2約束條件：x1+x ≤ 300 x1+x2 + x3 ＝ 300， 2x1+x2

30、≤400 2x1+ x2 +x4 ＝ 400， +x2 ≤250. x2 +x5 ＝ 250. x1，x2≥0

31、 xj≥0 （j=1，2, …5）,,,31,一. 基本概念,上例線(xiàn)性規(guī)劃的系數(shù)矩陣, 其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個(gè)數(shù)n，為了找到一個(gè)初始基本可行解，先介紹以下幾個(gè)線(xiàn)性規(guī)劃的基本概念。基： 已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中m×m階非 奇異子矩陣（即可逆矩陣），則稱(chēng)B是線(xiàn)性規(guī)劃問(wèn)題中的一個(gè)基?；蛄浚夯鵅中的

32、一列即稱(chēng)為一個(gè)基向量。基B中共有m個(gè)基向量。p2、 p4、p5 非基向量：在A(yíng)中除了基B之外的一列則稱(chēng)之為基B的非基向量。 p1、 p3基變量：與基向量pi相應(yīng)的變量xi叫基變量，基變量有m個(gè)。 x2、x4、x5 非基變量：與非基向量pj相應(yīng)的變量 xj 叫非基變量，非基變量有n-m個(gè)。 x1、 x3,,為基,由線(xiàn)性代數(shù)的知識(shí)知道，如果我們?cè)诩s束方程組系數(shù)矩陣中找到一個(gè)基，令這個(gè)基的非基變量為零，再求解這個(gè)m元線(xiàn)性方程組就可得到

33、唯一的解了，這個(gè)解我們稱(chēng)之為線(xiàn)性規(guī)劃的基本解。不同的基有不同的基解 對(duì)于A(yíng)的一個(gè)基， 令非基變量x１，x3 ＝0。這時(shí)約束方程就變?yōu)榛兞康募s束方程： x2 ＝ 300， 求解得到此線(xiàn)性規(guī)劃的一個(gè)基本解：  x2 + x4 ＝ 400，x1=0，x2 = 300，x3 =0，x4=

34、100，x5 =－50 x2 +x5 = 250. X1=(x1, x2, x3 , x4, x5 ) T =(0, 300, 0,100, －50 ) T不滿(mǎn)足該線(xiàn)性規(guī)劃x4≥0，x5≥0的約束條件，顯然不是此線(xiàn)性規(guī)劃的可行解， 若取基 則令非基變量x2，x3 ＝0，得到一個(gè)解：x1=300，x2=0，x3 =0，x4=100，x5=130 D點(diǎn)我們把滿(mǎn)足非負(fù)條件的一個(gè)基本解

35、叫做基本可行解，并把這樣的基叫做可行基。線(xiàn)性規(guī)劃的每一個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn),,20,,29,二. 初始基可行解 單位矩陣為初始基,我們能否找到的一個(gè)基能保證在求解之后得到的解一定是基本可行解呢？由于在線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型中要求bj都大于等于零，如果我們能找到一個(gè)基是單位矩陣，或者說(shuō)一個(gè)基是由單位矩陣的各列向量所組成（至于各列向量的前后順序是無(wú)關(guān)緊要的事）例如，那么顯然所求得的基本解一定是基本可行解，這個(gè)單位矩陣或由單位矩

36、陣各列向量組成的基一定是可行基。實(shí)際上這個(gè)基本可行解中的各個(gè)變量或等于某個(gè)bj或等于零。,在本例題中我們就找到了一個(gè)基是單位矩陣。 在第一次找可行基時(shí)，所找到的基或?yàn)閱挝痪仃嚮驗(yàn)橛蓡挝痪仃嚨母髁邢蛄克M成，稱(chēng)之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將通過(guò)填加人工變量構(gòu)造初始可行基，具體做法在以后詳細(xì)講述。,三、 最優(yōu)性檢驗(yàn),所謂最優(yōu)性檢驗(yàn)就是判

37、斷已求得的基本可行解是否是最優(yōu)解。1. 最優(yōu)性檢驗(yàn)的依據(jù)——檢驗(yàn)數(shù)σj 一般來(lái)說(shuō)目標(biāo)函數(shù)中既包括基變量，又包括非基變量。現(xiàn)在我們要求只用非基變量來(lái)表示目標(biāo)函數(shù)， 這只要在約束等式中通過(guò)移項(xiàng)等處理就可以用非基變量來(lái)表示基變量，然后用非基變量的表示式代替目標(biāo)函數(shù)中基變量，這樣目標(biāo)函數(shù)中只含有非基變量了，或者說(shuō)目標(biāo)函數(shù)中基變量的系數(shù)都為零了。此時(shí)目標(biāo)函數(shù)中所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù)，把變量xi的檢驗(yàn)數(shù)記為σi。顯然所有基

38、變量的檢驗(yàn)數(shù)必為零。 在本例題中目標(biāo)函數(shù)為50x1+100x2。由于初始可行解中x1，x2為非基變量，所以此目標(biāo)函數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知σ1=50，σ2=100，σ3=0，σ4= 0，σ5=0。,2.最優(yōu)解判別定理,對(duì)于求最大目標(biāo)函數(shù)的問(wèn)題中，對(duì)于某個(gè)基本可行解，如果所有檢驗(yàn)數(shù) ≤0，則這個(gè)基本可行解是最優(yōu)解。下面我們用通俗的說(shuō)法來(lái)解釋最優(yōu)解判別定理。設(shè)用非基變量表示的目標(biāo)函數(shù)為如

39、下形式： 由于所有的xj的取值范圍為大于等于零，當(dāng)所有的 都小 于等于零時(shí)，可知 是一個(gè)小于等于零的數(shù)，要使 z 的值最大，顯然 只有為零。我們把這些xj取為非基變量(即令這些 xj的值為零)，所求得的基本可行解就使目標(biāo)函數(shù)值最大為z0。**對(duì)于求目標(biāo)函數(shù)最小值的情況，只需把 ≤0改為 ≥0,四、 基變換,通過(guò)檢驗(yàn)，我們知道這

40、個(gè)初始基本可行解不是最優(yōu)解。需要進(jìn)行基變換找到一個(gè)新的可行基，具體的做法是從可行基中換一個(gè)列向量，得到一個(gè)新的可行基，使得求解得到的新的基本可行解，其目標(biāo)函數(shù)值更優(yōu)。為了換基就要確定換入變量與換出變量。 1。入基變量的確定 從最優(yōu)解判別定理知道，當(dāng)某個(gè)σj＞0時(shí)，非基變量xj變?yōu)榛兞?，不取零值可以使目?biāo)函數(shù)值增大，故我們要選基檢驗(yàn)數(shù)大于0的非基變量換到基變量中去（稱(chēng)之為入基變量）。若有兩個(gè)以上的σj＞0，則為了使目標(biāo)函數(shù)增加得更大

41、些，一般選其中的σj最大者的非基變量為入基變量，即按最大σ法則選入基變量：在本例題中σ2=100是檢驗(yàn)數(shù)中最大的正數(shù)，故選x2為入基變量。,2. 出基變量的確定我們把確定出基變量的方法概括如下：把已確定的入基變量在各約束方程中的正的系數(shù)除以其所在約束方程中的常數(shù)項(xiàng)的值，把這一值記為θi,把其中最小比值所在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變換中可以確保新得到的bj值都大于等于零。即按最小θ法則確定出基變

42、量:以基變量xk代替出基變量xr,得到一個(gè)新的基可行解。以上過(guò)程可以通過(guò)單純型表來(lái)實(shí)現(xiàn)。,五　單純形法的表格形式,在講解單純形法的表格形式之前，先從一般數(shù)學(xué)模型里推導(dǎo)出檢驗(yàn)數(shù) 的表達(dá)式。 可行基為m階單位矩陣的線(xiàn)性規(guī)劃模型如下（假設(shè)其系數(shù)矩陣的前m列是單位矩陣）： 以下用 表示基變量，用

43、 表示非基變量。,把第i個(gè)約束方程移項(xiàng)，就可以用非基變量來(lái)表示基變量xi， 把以上的表達(dá)式帶入目標(biāo)函數(shù)，就有 其中：,單純型表,單純形法的計(jì)算步驟 (表格方式),第一步:求出線(xiàn)性規(guī)劃的初始基本可行解 通過(guò)加松弛變量，剩余變量，人工變量方式將線(xiàn)性規(guī)劃化成標(biāo)準(zhǔn)型，其中約束方程的系數(shù)矩陣包含一個(gè)單位矩陣，以這個(gè)單位矩陣作為

44、基，得到問(wèn)題的一個(gè)初始基可行解 以求解例1為例,Max z ＝ 50x1+100 x2 s.t. x1+ x2 ≤ 300 2x1+x2 ≤ 400 x2 ≤ 250 xj≥0 （j=1, 2）,,Max z ＝ 50x1+100x2 s.t. x1 + x2 + x3

45、 ＝300 2x1+ x2 +x4 ＝ 400 x2 +x5 ＝ 250 xj≥0 （j = 1,2,3,4,5）,,單純形表格求解例2,,,在上表中第3個(gè)基變量x5已被x2代替，故基變量列中的第3個(gè)基變量應(yīng)變?yōu)閤2。由于第0次迭代表中的主元a32已經(jīng)為1，因此第3行不變。為

46、了使第1行的a12為0，只需把第3行×(-1)加到第1行即可。同樣可以求得第2行。求得第1次迭代的基本可行解為 x3 =50, x4 =150, x2=250, x1=0, x5=0, z=25000?？尚杏駻點(diǎn)坐標(biāo),,,,,,,,,19,,,,,,從上表可以看出，第一次迭代的 ，因此不是最優(yōu)解。設(shè)x1為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此， x3為出基變量，a1

47、1為主元，繼續(xù)迭代如下表所示。,從上表中可知第二次迭代得到的基本可行解為x1=50, x2=250, x3 =0, x4 =50, x5=0，這時(shí)z = 27500。由于檢驗(yàn)數(shù)都<0，因此所求得的基本可行解為最優(yōu)解， z=27500為最優(yōu)目標(biāo)函數(shù)值。實(shí)際上，我們可以連續(xù)地使用一個(gè)單純形表，不必一次迭代重畫(huà)一個(gè)表頭。,單純形表格求解例2,在zj行中填入第j列與CB列中對(duì)應(yīng)的元素相乘相加所得的值，如z2=0×1+0×

48、;1+0×1=0，所在zi行中的第2位數(shù)填入0；在 行中填入cj-zj 所得的值，如 ；z表示把初始基本可行解代入目標(biāo)函數(shù)求得的目標(biāo)函數(shù)值，即z =b×CB；初始基本可行解為x3=300, x4= 400,x5 = 250, x1=0, x2= 0;確定x3為出基變量；由于 ，

49、 因此確定x2為入基變量。出基變量所在行，入基變量所在列的交匯處為主元，這里是 a32=1，,,,在上表中第3個(gè)基變量x5已被x2代替，故基變量列中的第3個(gè)基變量應(yīng)變?yōu)閤2。由于第0次迭代表中的主元a32已經(jīng)為1，因此第3行不變。為了使第1行的a12為0，只需把第3行×(-1)加到第1行即可。同樣可以求得第2行。求得第1次迭代的基本可行解為 x3 =50, x4 =150, x2=250, x1=0, x5=0, z=25

50、000?？尚杏駻點(diǎn)坐標(biāo),,,,,,,,從上表可以看出，第一次迭代的 ，因此不是最優(yōu)解。設(shè)x1為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此，s1為出基變量，a11為主元，繼續(xù)迭代如下表所示。,從上表中可知第二次迭代得到的基本可行解為x1=50, x2=250, x3 =0, x4 =50, x5=0，這時(shí)z = 27500。由于檢驗(yàn)數(shù)都<0，因此所求得的基本可行解為最優(yōu)解，

51、z=27500為最優(yōu)目標(biāo)函數(shù)值。實(shí)際上，我們可以連續(xù)地使用一個(gè)單純形表，不必一次迭代重畫(huà)一個(gè)表頭。,,,,,,求解例,用單純形法求解線(xiàn)性規(guī)劃M(mǎn)ax z ＝ 4x1+3 x2 s.t. x1+ ≤ 6 2x2 ≤ 8 2 x1+3 x2 ≤ 18 xj≥0 （j=1, 2）,,Max z ＝4x1+3x2 s.t

52、. x1 + x3 ＝6 2 x2 +x4 ＝ 8 2x1+ 3x2 +x5 ＝ 18 xj≥0 （j = 1,2,3,4,5）,,,,最優(yōu)解為x1=6, x2=2, x3=0, x4=4, x5= 0，這時(shí)z =30,六、大M法,

53、一、大M法以第二章的例2來(lái)講解如何用單純形表的方法求解目標(biāo)函數(shù)值最小的線(xiàn)性規(guī)劃問(wèn)題。目標(biāo)函數(shù)：約束條件：加入松弛變量和剩余變量變?yōu)闃?biāo)準(zhǔn)型，得到新的約束條件如下：,max z = －2x1－3x2.約束條件：x1+x2－s1 = 350， x1 －s2 = 125，

54、 2x1+x2 +s3 = 600， x1，x2，s1，s2，s3 ≥0,為了得到單位矩陣，引進(jìn)人工變量a1和a2 。人工變量只能取零值。一旦人工變量取正值，那么有人工變量的約束方程和原始的約束方程就不等價(jià)了，這樣所求得的解就不是原線(xiàn)性規(guī)劃的解了。為了竭盡全力地要求人工變量為零，我們規(guī)定人工變量在目標(biāo)函數(shù)中的系數(shù)為－M，這里M為任意大的數(shù)。這樣只要人工變量＞0，所

55、求的目標(biāo)函數(shù)最大值就是一個(gè)任意小的數(shù)。這樣為了使目標(biāo)函數(shù)實(shí)現(xiàn)最大就必須把人工變量從基變量中換出。如果一直到最后，人工變量仍不能從基變量中換出，也就是說(shuō)人工變量仍不為零，則該問(wèn)題無(wú)可行解。此例的數(shù)學(xué)模型如下所示： 目標(biāo)函數(shù)： max z=－2x1－3x2－Ma1－Ma2. 約束條件：x1+x2－s1 +a1 =350，

56、 x1 －s2 +a2 =125， 2x1+x2 +s3 =600，

57、 x1，x2，s1，s2，s3，a1，a2≥0. 像這樣，為了構(gòu)造初始可行基得到初始可行解，把人工變量“強(qiáng)行”地加到原來(lái)的約束方程中去，又為了盡力地把人工變量從基變量中替換出來(lái)就令人工變量在求最大值的目標(biāo)函數(shù)里的系數(shù)為－M，這個(gè)方法叫做大M法，M叫做罰因子。,,,,§4 線(xiàn)性規(guī)劃問(wèn)題的計(jì)算機(jī)求解,可以使用由芝加哥大學(xué)的L.E.Schrage開(kāi)發(fā)的Lindo計(jì)算機(jī)軟件包的微型計(jì)算機(jī)版本Lindo/PC。一般書(shū)中介紹

58、用Excel電子表格求解線(xiàn)性規(guī)劃,本書(shū)主要用Excel電子表格求解,用易理解方式輸入數(shù)據(jù)和構(gòu)筑數(shù)據(jù)之間的聯(lián)系 定義目標(biāo)單元格（目標(biāo)函數(shù)） 確定可變單元（決策變量） 添加約束變量（Adding Constraints）,建立一個(gè)電子表格模型 P26,借用Excel中SUMPRODUCT函數(shù)來(lái)表達(dá)兩個(gè)向量點(diǎn)乘，既兩行對(duì)應(yīng)元素相乘后求和，本書(shū)采用區(qū)域（單元格）名稱(chēng)方式，見(jiàn)P79,以偉恩德玻璃制品公司產(chǎn)品組合問(wèn)題為例,Max

59、 z = 300 x1 + 500 x2 約束條件：s.t. x1 + ≤ 4 2 x2 ≤ 12 3x1 + 2x2 ≤ 18