第二章-線性規(guī)劃問題與計算機求解mem運籌學(xué)

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

2、模型為：產(chǎn)品 Ⅰ利潤：84 – (1×10 設(shè)備+ 2×12 原料A) = 50 (元)產(chǎn)品BⅡ利潤：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、原料來配置一種混合飼料，已知兩種原料含三種營養(yǎng)成分和混合飼料對營養(yǎng)成分的要求如下表：問題：公司應(yīng)任何采購兩種原材料，使即滿足營養(yǎng)要求，又使成本最少？,線性規(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,線性規(guī)劃問題主要類型,資源分配問題（resource-allocation）以?符號表

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

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

8、2.定義決策變量（ x1 ，x2 ，… ，xn ），每一組值表示一個方案； Decision variables 決策變量3.用決策變量的函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)； Objective function 目標(biāo)函數(shù)4.用一組決策變量的線性等式或線性不等式表示解決問題過程中必須遵循的約束條件; 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　圖 解 法,對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作

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

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

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

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

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

17、 ≥ 350 x1 ≥ 125 2x1 + x2 ≤ 600 x1 , x2 ≥ 0 采用圖解法。如下圖：得Q點坐標(biāo)（250，100）為最優(yōu)解。,線性規(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 右端項非負(fù)。,1.極小化目標(biāo)函數(shù)的問題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2

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

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

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

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

27、問題： 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　單純形法的基本思路和原理單純形法的基本思路：從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)解，如不是,則再找另一個使得其目標(biāo)函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否是最優(yōu)解。直到找到一個頂點為其最優(yōu)解，就是使得其目標(biāo)函

29、數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。通過例1的求解來介紹單純形法:在加上松弛變量之后我們可得到（增廣形式）標(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,一. 基本概念,上例線性規(guī)劃的系數(shù)矩陣, 其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個數(shù)n，為了找到一個初始基本可行解，先介紹以下幾個線性規(guī)劃的基本概念。基： 已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中m×m階非 奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問題中的一個基。基向量：基B中的

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

33、唯一的解了，這個解我們稱之為線性規(guī)劃的基本解。不同的基有不同的基解 對于A的一個基， 令非基變量x１，x3 ＝0。這時約束方程就變?yōu)榛兞康募s束方程： x2 ＝ 300， 求解得到此線性規(guī)劃的一個基本解：  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不滿足該線性規(guī)劃x4≥0，x5≥0的約束條件，顯然不是此線性規(guī)劃的可行解， 若取基 則令非基變量x2，x3 ＝0，得到一個解：x1=300，x2=0，x3 =0，x4=100，x5=130 D點我們把滿足非負(fù)條件的一個基本解

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

36、陣各列向量組成的基一定是可行基。實際上這個基本可行解中的各個變量或等于某個bj或等于零。,在本例題中我們就找到了一個基是單位矩陣。 在第一次找可行基時，所找到的基或為單位矩陣或為由單位矩陣的各列向量所組成，稱之為初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將通過填加人工變量構(gòu)造初始可行基，具體做法在以后詳細講述。,三、 最優(yōu)性檢驗,所謂最優(yōu)性檢驗就是判

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

38、變量的檢驗數(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)解判別定理,對于求最大目標(biāo)函數(shù)的問題中，對于某個基本可行解，如果所有檢驗數(shù) ≤0，則這個基本可行解是最優(yōu)解。下面我們用通俗的說法來解釋最優(yōu)解判別定理。設(shè)用非基變量表示的目標(biāo)函數(shù)為如

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

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

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

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

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

44、基，得到問題的一個初始基可行解 以求解例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個基變量x5已被x2代替，故基變量列中的第3個基變量應(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?？尚杏駻點坐標(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，這時z = 27500。由于檢驗數(shù)都<0，因此所求得的基本可行解為最優(yōu)解， z=27500為最優(yōu)目標(biāo)函數(shù)值。實際上，我們可以連續(xù)地使用一個單純形表，不必一次迭代重畫一個表頭。,單純形表格求解例2,在zj行中填入第j列與CB列中對應(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個基變量x5已被x2代替，故基變量列中的第3個基變量應(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。可行域A點坐標(biāo),,,,,,,,從上表可以看出，第一次迭代的 ，因此不是最優(yōu)解。設(shè)x1為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此，s1為出基變量，a11為主元，繼續(xù)迭代如下表所示。,從上表中可知第二次迭代得到的基本可行解為x1=50, x2=250, x3 =0, x4 =50, x5=0，這時z = 27500。由于檢驗數(shù)都<0，因此所求得的基本可行解為最優(yōu)解，

51、z=27500為最優(yōu)目標(biāo)函數(shù)值。實際上，我們可以連續(xù)地使用一個單純形表，不必一次迭代重畫一個表頭。,,,,,,求解例,用單純形法求解線性規(guī)劃Max 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，這時z =30,六、大M法,

53、一、大M法以第二章的例2來講解如何用單純形表的方法求解目標(biāo)函數(shù)值最小的線性規(guī)劃問題。目標(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,為了得到單位矩陣，引進人工變量a1和a2 。人工變量只能取零值。一旦人工變量取正值，那么有人工變量的約束方程和原始的約束方程就不等價了，這樣所求得的解就不是原線性規(guī)劃的解了。為了竭盡全力地要求人工變量為零，我們規(guī)定人工變量在目標(biāo)函數(shù)中的系數(shù)為－M，這里M為任意大的數(shù)。這樣只要人工變量＞0，所

55、求的目標(biāo)函數(shù)最大值就是一個任意小的數(shù)。這樣為了使目標(biāo)函數(shù)實現(xiàn)最大就必須把人工變量從基變量中換出。如果一直到最后，人工變量仍不能從基變量中換出，也就是說人工變量仍不為零，則該問題無可行解。此例的數(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)造初始可行基得到初始可行解，把人工變量“強行”地加到原來的約束方程中去，又為了盡力地把人工變量從基變量中替換出來就令人工變量在求最大值的目標(biāo)函數(shù)里的系數(shù)為－M，這個方法叫做大M法，M叫做罰因子。,,,,§4 線性規(guī)劃問題的計算機求解,可以使用由芝加哥大學(xué)的L.E.Schrage開發(fā)的Lindo計算機軟件包的微型計算機版本Lindo/PC。一般書中介紹

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

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