1、第二章線性規(guī)劃問題與計(jì)算機(jī)求解,1問題的提出 2圖解法 3單純形法 4 計(jì)算機(jī)求解,1問題的提出,例1. 某工廠在計(jì)劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、資源的限制，如下表： 問題：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？,設(shè)生產(chǎn)產(chǎn)品數(shù)量為x1,產(chǎn)品數(shù)量為x2 , 線性規(guī)劃模型為： 產(chǎn)品 利潤(rùn)：84 (110 設(shè)備+ 212 原料A) = 50 (元) 產(chǎn)品B利潤(rùn)：140 (110 設(shè)備+112 原料A +118 原料B) = 100 (元) 目標(biāo)函數(shù)：Max z = 50 x1 + 100 x2 約束條件：s.t. x1 + x2 30

2、0 2 x1 + x2 400 x2 250 x1 , x2 0,例2. 某飼料公司希望用玉米、紅薯兩種原料來配置一種混合飼料，已知兩種原料含三種營(yíng)養(yǎng)成分和混合飼料對(duì)營(yíng)養(yǎng)成分的要求如下表： 問題：公司應(yīng)任何采購(gòu)兩種原材料，使即滿足營(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 3x1 + 6 x2 18 x1 + 5x2 16 x1 , x2 0,線性規(guī)劃問題主要類型,資源分配問題（resource-allocation）以符號(hào)表示的函數(shù)約束稱為資源約束，這些限制

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

4、特定形式的確定需求的約束。 提供的數(shù)量需要的數(shù)量 混合問題（mixed Problem）除以上三類以外的問題，這一類型包括了三類約束函數(shù),建模過程 1.理解要解決的問題，了解解題目標(biāo)和條件； 2.定義決策變量（ x1 ，x2 ， ，xn ），每一組值表示一個(gè)方案； Decision variables 決策變量 3.用決策變量的函數(shù)形式寫出目標(biāo)函數(shù)，確定最大化或最小化目標(biāo)； Objective function 目標(biāo)函數(shù) 4.用一組決策變量的線性等式或線性不等式表示解決問題過程中必須遵循的約束條件; Constraints 約束,一般形式 目標(biāo)函數(shù)： Max （Min） z = c1 x1 +

5、 c2 x2 + + cn xn 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 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 (B) x2 250 (C) x1 0 (D) x2 0 (E) 得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標(biāo)值 z = 2750

6、0,2圖 解 法,對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。 下面通過例1詳細(xì)講解其方法：,2圖解法 畫出可行域 滿足約束的區(qū)域,(1)分別取決策變量X1 , X2 為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1的每個(gè)約束條件都代表一個(gè)半平面。,（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。,（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如圖2-1所示。,2 圖 解 法 確定等值線與梯度,（4）目標(biāo)函數(shù)z =50 x1+100 x2，當(dāng)z取某一固定

7、值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(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)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(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é)論： 如果線性規(guī)劃有最優(yōu)解，則一定有一個(gè)可行

8、域的頂點(diǎn)對(duì)應(yīng)一個(gè)最優(yōu)解； 無窮多個(gè)最優(yōu)解。若將例1中的目標(biāo)函數(shù)變?yōu)?max z=50 x1+50 x2，則線段BC上的所有點(diǎn)都代表了最優(yōu)解； 無界解。即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小。一般來說，這說明模型有錯(cuò)，忽略了一些必要的約束條件； 無可行解。若在例1的數(shù)學(xué)模型中再增加一個(gè)約束條件4x1+3x21200，則可行域?yàn)榭沼?，不存在滿足約束條件的解，當(dāng)然也就不存在最優(yōu)解了。,進(jìn) 一 步 討 論 求極小化問題,例2 某公司由于生產(chǎn)需要，共需要A，B兩種原料至少350 噸（A，B兩種材料有一定替代性），其中A原料至少購(gòu)進(jìn)125 噸。但由于A，B兩種原料的規(guī)格不同，各自所需的加

9、工時(shí)間 也是不同的，加工每噸A原料需要2個(gè)小時(shí)，加工每噸B原料需 要1小時(shí)，而公司總共有600個(gè)加工小時(shí)。又知道每噸A原料的 價(jià)格為2萬元，每噸B原料的價(jià)格為3萬元，試問在滿足生產(chǎn)需 要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買A，B兩種 原料，使得購(gòu)進(jìn)成本最低？,解：目標(biāo)函數(shù)： Min f = 2x1 + 3 x2 約束條件： s.t. x1 + x2 350 x1 125 2x1 + x2 600 x1 , x2 0 采用圖解法。如下圖：得Q點(diǎn)坐標(biāo)（250，100）為最優(yōu)解。,線性規(guī)劃的標(biāo)準(zhǔn)化,一般形式 目標(biāo)函數(shù)： Max （Min） z = c1 x1 + c2 x2 + + cn xn

10、 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)： Max z = c1 x1 + c2 x2 + + cn xn 目標(biāo)最大化； 約束條件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 約束為等式； am1 x1 + am2 x2 + + amn xn = bm 決

11、策變量均非負(fù)； x1 ，x2 ， ，xn 0，bi 0 右端項(xiàng)非負(fù)。,1.極小化目標(biāo)函數(shù)的問題： 設(shè)目標(biāo)函數(shù)為 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 則該極小化問題與下面的極大化問題有相同的最優(yōu)解， 即 Max z =c1x1c2x2 cnxn 但必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但它們 最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即 Min f Max z 2 右端項(xiàng)有負(fù)值的問題： 如 bi0，則把該等式約束兩端同時(shí)乘以1，得到： ai1 x1ai2 x2 ain xn = bi,非標(biāo)準(zhǔn)形式的線性規(guī)劃非標(biāo)準(zhǔn)形式的線性規(guī)劃,非標(biāo)準(zhǔn)形式的線性規(guī)劃非標(biāo)準(zhǔn)形

12、式的線性規(guī)劃,3、約束條件不是等式的問題： 1）設(shè)約束條件為： ai1 x1+ai2 x2+ +ain xn bi 可以引進(jìn)一個(gè)新的松弛變量 s ，使它等于約束右邊與左邊之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 顯然，s0， 這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ +ain xn+s = bi 2） 當(dāng)約束條件為： ai1 x1+ai2 x2+ +ain xn bi 時(shí) 類似地令剩余變量 s =(ai1 x1+ai2 x2+ +ain xn) bi ； s0， 這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ +ain xns = bi 4. 當(dāng)

13、某一個(gè)變量xj無約束，既沒有非負(fù)約束時(shí)，可以令 xj = xjxj” 其中 xj0， xj”0,例5：將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 Min f = 2 x13x2 + 4 x3 s.t. 3 x1 + 4x2 5 x3 6 2 x1 + x3 8 x1 + x2 + x3 = 9 x1 , x3 0， x2 無約束 解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 z = f = 2x1+3x24x3 其次考慮約束，有2個(gè)不等式約束，引進(jìn)松弛變量 x4，x5 0。 第三個(gè)約束條件的右端值為負(fù)，在等式兩邊同時(shí)乘1。 x2 無約束， 令 x2 = x2x2” 其中 x20， x2”0,通過以上變換，可以

14、得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題： Max z = 2x1 + 3 (x2x2”) 4x3 s.t. 3x1+ 4(x2x2”) 5x3 +x4 = 6 2x1 + x3 x5 = 8 x1 (x2x2”) x3 = 9 x1 , x2, x2” , x3 , x4 , x5 0,3單純形法,3.1單純形法的基本思路和原理 單純形法的基本思路：從可行域中某一個(gè)頂點(diǎn)開始，判斷此頂點(diǎn)是否是最優(yōu)解，如不是,則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再判斷此點(diǎn)是否是最優(yōu)解。直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。 通過例1的求解來介紹單純

15、形法: 在加上松弛變量之后我們可得到（增廣形式）標(biāo)準(zhǔn)型如下： 目標(biāo)函數(shù)：max z 50 x1+100 x2 max z 50 x1+100 x2 約束條件：x1+x 300 x1+x2 + x3 300， 2x1+x2400 2x1+ x2 +x4 400， +x2 250. x2 +x5 250. x1，x20 xj0 （j=1，2, 5）,31,一. 基本概念,上例線性規(guī)劃的系數(shù)矩陣, 其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個(gè)數(shù)n，為了找到一個(gè)初始基本可行解，先介紹以下幾個(gè)線性規(guī)劃的基本概念。 基： 已知A是約束條件的mn系數(shù)矩陣，其秩為m。若B是A中

16、mm階非 奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問題中的一個(gè)基。 基向量：基B中的一列即稱為一個(gè)基向量?；鵅中共有m個(gè)基向量。p2、 p4、p5 非基向量：在A中除了基B之外的一列則稱之為基B的非基向量。 p1、 p3 基變量：與基向量pi相應(yīng)的變量xi叫基變量，基變量有m個(gè)。 x2、x4、x5 非基變量：與非基向量pj相應(yīng)的變量 xj 叫非基變量，非基變量有n-m個(gè)。 x1、 x3,為基,由線性代數(shù)的知識(shí)知道，如果我們?cè)诩s束方程組系數(shù)矩陣中找到一個(gè)基，令這個(gè)基的非基變量為零，再求解這個(gè)m元線性方程組就可得到唯一的解了，這個(gè)解我們稱之為線性規(guī)劃的基本解。不同的基有不同的基解 對(duì)于A的一個(gè)基

17、， 令非基變量x，x3 0。這時(shí)約束方程就變?yōu)榛兞康募s束方程： x2 300， 求解得到此線性規(guī)劃的一個(gè)基本解： x2 + x4 400，x1=0，x2 = 300，x3 =0，x4=100，x5 =50 x2 +x5 = 250. X1=(x1, x2, x3 , x4, x5 ) T =(0, 300, 0,100, 50 ) T 不滿足該線性規(guī)劃x40，x50的約束條件，顯然不是此線性規(guī)劃的可行解， 若取基 則令非基變量x2，x3 0，得到一個(gè)解：x1=300，x2=0，x3 =0，x4=100，x5=130 D點(diǎn) 我們把滿足非負(fù)條件的一個(gè)基本解叫做基本可行解，并把這樣的基叫做可行基。

18、線性規(guī)劃的每一個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn),20,29,二. 初始基可行解 單位矩陣為初始基,我們能否找到的一個(gè)基能保證在求解之后得到的解一定是基本可行解呢？由于在線性規(guī)劃的標(biāo)準(zhǔn)型中要求bj都大于等于零，如果我們能找到一個(gè)基是單位矩陣，或者說一個(gè)基是由單位矩陣的各列向量所組成（至于各列向量的前后順序是無關(guān)緊要的事）例如， 那么顯然所求得的基本解一定是基本可行解，這個(gè)單位矩陣或由單位矩陣各列向量組成的基一定是可行基。實(shí)際上這個(gè)基本可行解中的各個(gè)變量或等于某個(gè)bj或等于零。,在本例題中我們就找到了一個(gè)基是單位矩陣。 在第一次找可行基時(shí)，所找到的基或?yàn)閱挝痪仃嚮驗(yàn)橛蓡挝痪仃嚨母髁邢蛄克M成，稱之為

19、初始可行基，其相應(yīng)的基本可行解叫初始基本可行解。如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將通過填加人工變量構(gòu)造初始可行基，具體做法在以后詳細(xì)講述。,三、 最優(yōu)性檢驗(yàn),所謂最優(yōu)性檢驗(yàn)就是判斷已求得的基本可行解是否是最優(yōu)解。 1. 最優(yōu)性檢驗(yàn)的依據(jù)檢驗(yàn)數(shù)j 一般來說目標(biāo)函數(shù)中既包括基變量，又包括非基變量?，F(xiàn)在我們要求只用非基變量來表示目標(biāo)函數(shù)， 這只要在約束等式中通過移項(xiàng)等處理就可以用非基變量來表示基變量，然后用非基變量的表示式代替目標(biāo)函數(shù)中基變量，這樣目標(biāo)函數(shù)中只含有非基變量了，或者說目標(biāo)函數(shù)中基變量的系數(shù)都為零了。此時(shí)目標(biāo)函數(shù)中所有變量的系數(shù)即為各變量的檢驗(yàn)數(shù)，把變

20、量xi的檢驗(yàn)數(shù)記為i。顯然所有基變量的檢驗(yàn)數(shù)必為零。 在本例題中目標(biāo)函數(shù)為50 x1+100 x2。由于初始可行解中x1，x2為非基變量，所以此目標(biāo)函數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知1=50，2=100，3=0，4= 0，5=0。,2.最優(yōu)解判別定理,對(duì)于求最大目標(biāo)函數(shù)的問題中，對(duì)于某個(gè)基本可行解，如果所有檢驗(yàn)數(shù) 0，則這個(gè)基本可行解是最優(yōu)解。下面我們用通俗的說法來解釋最優(yōu)解判別定理。設(shè)用非基變量表示的目標(biāo)函數(shù)為如下形式： 由于所有的xj的取值范圍為大于等于零，當(dāng)所有的 都小 于等于零時(shí)，可知 是一個(gè)小于等于零的數(shù)，要使 z 的值最大，顯然 只有為零。我們把這些xj

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

22、，一般選其中的j最大者的非基變量為入基變量，即按最大法則選入基變量： 在本例題中2=100是檢驗(yàn)數(shù)中最大的正數(shù)，故選x2為入基變量。,2. 出基變量的確定 我們把確定出基變量的方法概括如下：把已確定的入基變量在各約束方程中的正的系數(shù)除以其所在約束方程中的常數(shù)項(xiàng)的值，把這一值記為i,把其中最小比值所在的約束方程中的原基變量確定為出基變量。這樣在下一步迭代的矩陣變換中可以確保新得到的bj值都大于等于零。即按最小法則確定出基變量: 以基變量xk代替出基變量xr,得到一個(gè)新的基可行解。以上過程可以通過單純型表來實(shí)現(xiàn)。,五單純形法的表格形式,在講解單純形法的表格形式之前，先從一般數(shù)學(xué)模型里推導(dǎo)出檢驗(yàn) 數(shù)

23、 的表達(dá)式。 可行基為m階單位矩陣的線性規(guī)劃模型如下（假設(shè)其系數(shù)矩陣的前m 列是單位矩陣）： 以下用 表示基變量，用 表示非基變量。,把第i個(gè)約束方程移項(xiàng)，就可以用非基變量來表示基變量xi， 把以上的表達(dá)式帶入目標(biāo)函數(shù)，就有 其中：,單純型表,單純形法的計(jì)算步驟 (表格方式),第一步:求出線性規(guī)劃的初始基本可行解 通過加松弛變量，剩余變量，人工變量方式將線性規(guī)劃化成標(biāo)準(zhǔn)型，其中約束方程的系數(shù)矩陣包含一個(gè)單位矩陣，以這個(gè)單位矩陣作為基，得到問題的一個(gè)初始基可行解 以求解例1為例,Max z 50 x1+100 x2 s.t. x1+ x2 300 2x1+x2 400 x2 250 xj0 （j

24、=1, 2）,Max z 50 x1+100 x2 s.t. x1 + x2 + x3 300 2x1+ x2 +x4 400 x2 +x5 250 xj0 （j = 1,2,3,4,5）,單純形表格求解例2,在上表中第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=25000。可行域A點(diǎn)坐標(biāo),19,從上表可以看出，第一次迭代的 ，

25、因此不是最優(yōu)解。設(shè)x1為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此， x3為出基變量，a11為主元，繼續(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è)單純形表，不必一次迭代重畫一個(gè)表頭。,單純形表格求解例2,在zj行中填入第j列與CB列中對(duì)應(yīng)的元素相乘相加所得的值，如z2=01+01+01=0，所在zi行中的第2位數(shù)填入0； 在 行中填入cj-zj 所得的值，如 ；

26、z表示把初始基本可行解代入目標(biāo)函數(shù)求得的目標(biāo)函數(shù)值，即z =bCB； 初始基本可行解為x3=300, x4= 400,x5 = 250, x1=0, x2= 0; 確定x3為出基變量；由于 ， 因此確定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=

27、0, z=25000。可行域A點(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)解， z=27500為最優(yōu)目標(biāo)函數(shù)值。實(shí)際上，我們可以連續(xù)地使用一個(gè)單純形表，不必一次迭代重畫一個(gè)表頭。,求解例,用單純形法求解線性規(guī)劃 Max z 4x1+3 x2 s.t. x1+ 6 2x2 8 2 x1+3 x2 18 xj0 （j=1, 2）,Max z 4x1+3x2 s.t. x1 + x3 6 2 x2 +x4 8 2x1+ 3x2 +x5 18 xj0 （j = 1,2,3,4,5）,最優(yōu)解為x1=6, x2=2, x3=0, x4=4, x5= 0，這時(shí)z =30,六、大M法,一、大M法 以第二章的例2來講解如何用單純形表的方法求解目標(biāo)函數(shù)值最小的線性規(guī)劃問題。 目標(biāo)函數(shù)： 約束條件： 加入松弛變量和剩余變量變?yōu)闃?biāo)準(zhǔn)型，得到新的約束條件如下：,max z = 2x