線性規(guī)劃詳細(xì)

1、 線性規(guī)劃問(wèn)題及單純形法線性規(guī)劃問(wèn)題及單純形法n線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 n圖解法圖解法 n單純形法原理單純形法原理n單純形法計(jì)算步驟單純形法計(jì)算步驟nMatlabMatlab計(jì)算線性規(guī)劃問(wèn)題計(jì)算線性規(guī)劃問(wèn)題一、一、 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 線性規(guī)劃在經(jīng)營(yíng)管理中，常常用來(lái)解決線性規(guī)劃在經(jīng)營(yíng)管理中，常常用來(lái)解決有限資源（人、財(cái)、物）的合理分配問(wèn)題。有限資源（人、財(cái)、物）的合理分配問(wèn)題。在經(jīng)營(yíng)管理中，幾乎一切問(wèn)題都與有限資源在經(jīng)營(yíng)管理中，幾乎一切問(wèn)題都與有限資源的合理分配利用有關(guān)。線性規(guī)劃為解決有限的合理分配利用有關(guān)。線性規(guī)劃為解決有限資源的合理分

2、配利用提供了一個(gè)有效的數(shù)學(xué)資源的合理分配利用提供了一個(gè)有效的數(shù)學(xué)工具。工具。 建立線性規(guī)劃數(shù)學(xué)模型是解決線性規(guī)劃問(wèn)題的建立線性規(guī)劃數(shù)學(xué)模型是解決線性規(guī)劃問(wèn)題的一個(gè)重要步驟。一個(gè)重要步驟。 建立的線性規(guī)劃數(shù)學(xué)模型是否真正的反映客觀建立的線性規(guī)劃數(shù)學(xué)模型是否真正的反映客觀實(shí)際，數(shù)學(xué)模型本身是否正確，都直接影響求解結(jié)實(shí)際，數(shù)學(xué)模型本身是否正確，都直接影響求解結(jié)果，從而影響決策結(jié)果，所以，建立正確的線性規(guī)果，從而影響決策結(jié)果，所以，建立正確的線性規(guī)劃模型尤為重要。下面舉例說(shuō)明線性規(guī)劃數(shù)學(xué)模型劃模型尤為重要。下面舉例說(shuō)明線性規(guī)劃數(shù)學(xué)模型的建立。的建立。 一、線性規(guī)劃數(shù)學(xué)模型的建立一、線性規(guī)劃數(shù)學(xué)模型的建

3、立某廠利用某廠利用A A、B B兩種原料，生產(chǎn)甲、乙兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下：兩種原料，生產(chǎn)甲、乙兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下：例例1 1：（產(chǎn)品組合問(wèn)題）：（產(chǎn)品組合問(wèn)題）產(chǎn)品名稱產(chǎn)品名稱甲甲 乙乙單位產(chǎn)單位產(chǎn)品消耗品消耗原料原料原料名稱原料名稱可供利用的原料可供利用的原料數(shù)量（數(shù)量（T/T/日）日）6 68 81 21 22 12 1A AB B產(chǎn)品售價(jià)產(chǎn)品售價(jià) （千元（千元/ /T T） 3 2 3 2根據(jù)市場(chǎng)調(diào)查，有如下資料：根據(jù)市場(chǎng)調(diào)查，有如下資料：1.1.乙產(chǎn)品的需求量至多乙產(chǎn)品的需求量至多 2 2 T/T/日日; ;2.2.乙產(chǎn)品的需求量比甲產(chǎn)品的需求量至多大乙產(chǎn)品的需求量比甲產(chǎn)品的需求

4、量至多大 1 1 T/T/日。日。求該廠產(chǎn)值最大的求該廠產(chǎn)值最大的生產(chǎn)方案生產(chǎn)方案。提出三個(gè)問(wèn)題大家考慮：提出三個(gè)問(wèn)題大家考慮：1.1.問(wèn)題的未知數(shù)是什么？問(wèn)題的未知數(shù)是什么？ 設(shè)未知數(shù)設(shè)未知數(shù)2.2.以什么準(zhǔn)則進(jìn)行決策？以什么準(zhǔn)則進(jìn)行決策？ 目標(biāo)函數(shù)目標(biāo)函數(shù)3.3.約束條件是什么？約束條件是什么？ 約束方程約束方程 這里生產(chǎn)方案指的是如何安排甲、乙產(chǎn)品的產(chǎn)量。顯然，產(chǎn)量是未這里生產(chǎn)方案指的是如何安排甲、乙產(chǎn)品的產(chǎn)量。顯然，產(chǎn)量是未知數(shù)。知數(shù)。 設(shè)：甲產(chǎn)品的產(chǎn)量為設(shè)：甲產(chǎn)品的產(chǎn)量為 x x1 1 T/ T/日日 乙產(chǎn)品的產(chǎn)量為乙產(chǎn)品的產(chǎn)量為 x x2 2 T/ T/日日 決策準(zhǔn)則是產(chǎn)值最大，用

5、決策準(zhǔn)則是產(chǎn)值最大，用 Z Z 代表產(chǎn)值，則有：代表產(chǎn)值，則有： Z=3xZ=3x1 1+2x+2x2 2 Z Z 是是x x1 1、x x2 2 的函數(shù)，稱為目標(biāo)函數(shù)，目標(biāo)是求極大值，的函數(shù)，稱為目標(biāo)函數(shù)，目標(biāo)是求極大值， 即：即：max Z= 3xmax Z= 3x1 1+2x+2x2 2 約束條件（分三部分：資源限制、市場(chǎng)限制、非負(fù)限制）約束條件（分三部分：資源限制、市場(chǎng)限制、非負(fù)限制） x x1 1+2x+2x2 266 2x 2x1 1+x+x2 288 x x2 222 x x2 2 -x -x1 111 x x1 1，x x2 200約束條件資源限制資源限制市場(chǎng)限制市場(chǎng)限制非負(fù)限

6、制非負(fù)限制2萬(wàn)m31.4萬(wàn)m32萬(wàn)m31.4萬(wàn)m3整理得數(shù)學(xué)模型：整理得數(shù)學(xué)模型：目標(biāo)函數(shù)：目標(biāo)函數(shù)： min min z z = 1000 = 1000 x1 + 800 + 800 x2約束條件：約束條件： s.ts.t. . x1 1 1 0.8 0.8 x1 + + x2 1 1.6.6 x1 2 2 x2 1 1.4.4 x1 0 0， x2 0 0例例3、配料問(wèn)題（、配料問(wèn)題（min, ) )設(shè)設(shè) x1, x2分別代表每粒膠丸分別代表每粒膠丸中甲、乙兩種原料的用量中甲、乙兩種原料的用量0 x,x20.2x0.5x1.20.6x0.2x30.3x1.0 x20.5x0.5xs.t.0

7、.5x0.3xminZ(x)212121212121 某廠生產(chǎn)一種膠丸，某廠生產(chǎn)一種膠丸，已知如下資料：已知如下資料：例例4、合理下料問(wèn)題、合理下料問(wèn)題 用用7.4m長(zhǎng)的鋼筋，分別截取長(zhǎng)的鋼筋，分別截取2.9m、2.1m、1.5m各各至少至少100根，要求用料最少。根，要求用料最少。 設(shè)設(shè) xj 分別代表采用切割方案分別代表采用切割方案18所需所需7.4米的鋼米的鋼筋的數(shù)量。筋的數(shù)量。0,10043231002321002. .)(min,4 . 78765432187643176532432187654321xxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxZm則有鋼筋最少

8、若目標(biāo)函數(shù)為使購(gòu)買的0,10043231002321002. .4 . 18 . 02 . 01 . 109 . 03 . 01 . 0)(min,8765432187643176532432187654321xxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxZ余料則有最少若目標(biāo)函數(shù)為二、線性規(guī)劃問(wèn)題的共同特征二、線性規(guī)劃問(wèn)題的共同特征（模型的三要素）（模型的三要素） 每一個(gè)問(wèn)題都用一組決策變量每一個(gè)問(wèn)題都用一組決策變量( (x x1 1，x x2 2，x xn n) )表示某表示某一方案；這組決策變量的值就代表一個(gè)具體方案。一一方案；這組決策變量的值就代表一個(gè)具體方案。一般

9、這些變量取值都是非負(fù)的。般這些變量取值都是非負(fù)的。 存在一定的約束條件，這些約束條件可以用一組線性存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來(lái)表示。等式或線性不等式來(lái)表示。 都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量的線性函都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)（稱為目標(biāo)函數(shù)）來(lái)表示。按問(wèn)題的不同，要求目數(shù)（稱為目標(biāo)函數(shù)）來(lái)表示。按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。三、線性規(guī)劃數(shù)學(xué)模型的一般表示方式三、線性規(guī)劃數(shù)學(xué)模型的一般表示方式nn2211xcxcxcx)max(min)Z(0,),(),(),(.2122112222212111

10、212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats技術(shù)系數(shù)右端項(xiàng)價(jià)值系數(shù)線性規(guī)劃問(wèn)題的規(guī)模約束行數(shù)變量個(gè)數(shù): ;: ;: ;: ;:ijijabcmnmn 求解線性規(guī)劃問(wèn)題的任務(wù)是：在滿求解線性規(guī)劃問(wèn)題的任務(wù)是：在滿足約束條件的所有足約束條件的所有( (x x1 1，x x2 2，x xn n) )（可可行解）中求出使目標(biāo)函數(shù)達(dá)到最大行解）中求出使目標(biāo)函數(shù)達(dá)到最大( (小小) )z z 值的決策變量值值的決策變量值( (x x1 1* *，x x2 2* *，x xn n* *) )（最最優(yōu)解）。優(yōu)解）。 1.和式和式njxmixatsxcxZijinjji

11、jnjjj, 1, 1. .)(max110b，2.向量式向量式0XbPCXnjjjxtsxZ1.)(maxTnnxxxccc),( );,( 2121XC0000 21210bPmmjjjjbbbaaa3.矩陣式矩陣式0XbAXCX. .)(maxtsxZTmTnnmnmmnnbbbxxxcccaaaaaaaaa),(),();,(212121212222111211bXCA課堂作業(yè)：建立課堂作業(yè)：建立線性規(guī)劃模型線性規(guī)劃模型 某城市在一晝夜間，市內(nèi)交通需要車輛數(shù)如圖，對(duì)車輛某城市在一晝夜間，市內(nèi)交通需要車輛數(shù)如圖，對(duì)車輛的需求在晝夜間是變化的，車輛的工作制度是一天連續(xù)工作的需求在晝夜間是變

12、化的，車輛的工作制度是一天連續(xù)工作8 8小時(shí)，派車時(shí)間在各時(shí)間間隔的端點(diǎn)，一旦派出，就連續(xù)小時(shí)，派車時(shí)間在各時(shí)間間隔的端點(diǎn)，一旦派出，就連續(xù)工作工作8 8小時(shí)。求保證需要的最小車輛數(shù)。小時(shí)。求保證需要的最小車輛數(shù)。車輛數(shù)時(shí)間04712162024481248121084 派車時(shí)間在各時(shí)間間隔的端點(diǎn)，一旦派出，就連續(xù)工派車時(shí)間在各時(shí)間間隔的端點(diǎn)，一旦派出，就連續(xù)工作作8小時(shí)。小時(shí)。 設(shè)：各時(shí)間間隔所派車輛數(shù)為設(shè)：各時(shí)間間隔所派車輛數(shù)為xj j=1，2，6則有：則有： min Z=x1+x2+x3+x4+x5+x6 x1+x64 x1+x28 x2+x3 10 x3+x47 x4+x512 x5+

13、x6 4 x1，x2，x3，x4，x5，x6 0二、二、 線性規(guī)劃問(wèn)題及單純形法線性規(guī)劃問(wèn)題及單純形法n線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 n圖解法圖解法 n單純形法原理單純形法原理n單純形法計(jì)算步驟單純形法計(jì)算步驟nMatlab計(jì)算線性規(guī)劃問(wèn)題計(jì)算線性規(guī)劃問(wèn)題二、二、 圖解法圖解法 對(duì)模型中只含對(duì)模型中只含2 2個(gè)變量個(gè)變量的線性的線性規(guī)劃問(wèn)題，可以通過(guò)在平面上作規(guī)劃問(wèn)題，可以通過(guò)在平面上作圖的方法求解。圖的方法求解。 一、圖解法的步驟一、圖解法的步驟 1.1.等直線法等直線法 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03

14、Q21.1.建立平面直角坐標(biāo)系；建立平面直角坐標(biāo)系；4 4向著目標(biāo)函數(shù)的優(yōu)化方向平移等值線，直至得到等值線與可行域的最后向著目標(biāo)函數(shù)的優(yōu)化方向平移等值線，直至得到等值線與可行域的最后交點(diǎn)，這種點(diǎn)就對(duì)應(yīng)最優(yōu)解。交點(diǎn)，這種點(diǎn)就對(duì)應(yīng)最優(yōu)解。 2.2. 找出表示每個(gè)約束的找出表示每個(gè)約束的半平面半平面，所有半平面的交集是可行域（全體可行，所有半平面的交集是可行域（全體可行解的集合）；解的集合）；3.3. 畫出目標(biāo)函數(shù)的畫出目標(biāo)函數(shù)的等值線等值線 ；2.2.試算法試算法x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2最優(yōu)解在頂點(diǎn)達(dá)到：最優(yōu)解在頂點(diǎn)達(dá)到

15、：O點(diǎn)：點(diǎn)：X1=0, X2=0, Z=0Q1: X1=4, X2=0, Z=8Q2: X1=4, X2=2, Z=14Q3: X1=2, X2=3, Z=10Q4: X1=0, X2=3, Z=6二、線性規(guī)劃問(wèn)題解的存在情況二、線性規(guī)劃問(wèn)題解的存在情況1.1.存在唯一最優(yōu)解存在唯一最優(yōu)解x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例如例12.2.有無(wú)窮多最優(yōu)解有無(wú)窮多最優(yōu)解 若將例若將例1 1目標(biāo)函數(shù)變?yōu)槟繕?biāo)函數(shù)變?yōu)?max max z z = 2 = 2x x1 1+ 4+ 4x x2 2，則問(wèn)則問(wèn)題變?yōu)榇嬖跓o(wú)窮多最優(yōu)解。如圖題變

16、為存在無(wú)窮多最優(yōu)解。如圖: :x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q2 3. 有無(wú)界解有無(wú)界解z 可行域可伸展到無(wú)窮，由此目標(biāo)函數(shù)值也可增大可行域可伸展到無(wú)窮，由此目標(biāo)函數(shù)值也可增大至無(wú)窮。這種情況下問(wèn)題的最優(yōu)解無(wú)界。產(chǎn)生無(wú)界解至無(wú)窮。這種情況下問(wèn)題的最優(yōu)解無(wú)界。產(chǎn)生無(wú)界解的原因是由于在建立實(shí)際問(wèn)題的數(shù)學(xué)模型時(shí)的原因是由于在建立實(shí)際問(wèn)題的數(shù)學(xué)模型時(shí)遺漏了某遺漏了某些必要的資源約束條件些必要的資源約束條件。 例如：例如： max Z=2x1+2x2 s.t. -2x1+x24 x1-x2 2 x1，x2 00 x x1 1x x2 2

17、例如：例如：min Z=60 x1+50 x2 2x1+4x2 80 3x1+2x2 60 x1，x2 00 x x1 1x x2 2無(wú)界不一定無(wú)最優(yōu)解無(wú)界不一定無(wú)最優(yōu)解X X1 1=10, x=10, x2 2 =15 Z=1350=15 Z=1350模型的約束條件之間存在矛盾，建模時(shí)有錯(cuò)誤。模型的約束條件之間存在矛盾，建模時(shí)有錯(cuò)誤。 4. 無(wú)可行解（無(wú)可行解（可行域?yàn)榭占尚杏驗(yàn)榭占?例如：例如： max Z=x1+2x2 -x-x1 1-x-x2 22 2 2x 2x1 1+x+x2 24 4 x x1 1，x x2 2 000 x x1 1x x2 2 三、由圖解法得到的啟示三、由圖

18、解法得到的啟示 圖解法雖只能用來(lái)求解只具有兩個(gè)變量的線性規(guī)劃問(wèn)題，但它的解題思圖解法雖只能用來(lái)求解只具有兩個(gè)變量的線性規(guī)劃問(wèn)題，但它的解題思路和幾何上直觀得到的一些概念判斷，對(duì)下面要講的單純形法有很大啟示：路和幾何上直觀得到的一些概念判斷，對(duì)下面要講的單純形法有很大啟示： 1 1求解線性規(guī)劃問(wèn)題時(shí)，解的情況有求解線性規(guī)劃問(wèn)題時(shí)，解的情況有：唯一最優(yōu)解唯一最優(yōu)解；無(wú)窮多最優(yōu)解無(wú)窮多最優(yōu)解；無(wú)界解無(wú)界解；無(wú)可行解無(wú)可行解。（見下頁(yè)圖示所示）（見下頁(yè)圖示所示） 2 2若線性規(guī)劃問(wèn)題的可行域存在，則可行域是一個(gè)若線性規(guī)劃問(wèn)題的可行域存在，則可行域是一個(gè)凸集凸集。 3 3若線性規(guī)劃問(wèn)題的最優(yōu)解存在，則最

19、優(yōu)解或最優(yōu)解之一若線性規(guī)劃問(wèn)題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一( (如果有無(wú)窮如果有無(wú)窮多的話多的話) )一定是可行域的凸集的某個(gè)一定是可行域的凸集的某個(gè)頂點(diǎn)頂點(diǎn)。 4 4解題思路是，先找出凸集的解題思路是，先找出凸集的任一頂點(diǎn)任一頂點(diǎn)，計(jì)算在頂點(diǎn)處的目標(biāo)函數(shù)值。計(jì)算在頂點(diǎn)處的目標(biāo)函數(shù)值。比較周圍相鄰點(diǎn)的目標(biāo)函數(shù)值比較周圍相鄰點(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值大是否比這個(gè)值大，如果為如果為否否，則該頂點(diǎn)就是最則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則否則轉(zhuǎn)到比這個(gè)點(diǎn)的目標(biāo)函數(shù)值更大的另一頂轉(zhuǎn)到比這個(gè)點(diǎn)的目標(biāo)函數(shù)值更大的另一頂點(diǎn)，重復(fù)上述過(guò)程，一直到找出點(diǎn)，重復(fù)上述過(guò)程，一

20、直到找出使目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)使目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。為止。 (d)可行域無(wú)界可行域無(wú)界 (e)可行域無(wú)界可行域無(wú)界 (f)可行域?yàn)榭占尚杏驗(yàn)榭占?多個(gè)最優(yōu)解多個(gè)最優(yōu)解 目標(biāo)函數(shù)無(wú)界目標(biāo)函數(shù)無(wú)界 無(wú)可行解無(wú)可行解 (a)可行域有界可行域有界 (b)可行域有界可行域有界 (c)可行域無(wú)界可行域無(wú)界 唯一最優(yōu)解唯一最優(yōu)解 多個(gè)最優(yōu)解多個(gè)最優(yōu)解 唯一最優(yōu)解唯一最優(yōu)解四、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式四、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 （一）線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)形式（一）線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)形式 為了使線性規(guī)劃問(wèn)題的解法標(biāo)準(zhǔn)，就要把為了使線性規(guī)劃問(wèn)題的解法標(biāo)準(zhǔn)，就要把一般形式一般形式化化為為標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式。其

21、。其一般形式一般形式如下所示：如下所示：njxmibxatsxcxzjinjjijnjjj, 2 , 1 ), 0(0, 2 , 1 ,),(. .)(max(min)11不限線性代數(shù)基礎(chǔ)知識(shí)補(bǔ)充與回顧線性代數(shù)基礎(chǔ)知識(shí)補(bǔ)充與回顧一、克萊姆規(guī)則一、克萊姆規(guī)則 含有含有n n個(gè)未知數(shù)個(gè)未知數(shù)x x1 1,x,x2 2, ,x xn n的的n n個(gè)線性方程的方個(gè)線性方程的方程組如下式所示：程組如下式所示：nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 克萊姆法則克萊姆法則 如果上述線性方程組的系數(shù)行列式不等于零，即有：如果上述線性方程組的系數(shù)

22、行列式不等于零，即有：01111nnnnaaaaD那么，上述方程組有唯一解：那么，上述方程組有唯一解：DDxDDxDDxnn.,.,2211 其中其中DjDj（j=1j=1，2 2，n n）是把系數(shù)行列式）是把系數(shù)行列式D D中的第中的第j j列的元素用方程組的常數(shù)項(xiàng)代替后得到的列的元素用方程組的常數(shù)項(xiàng)代替后得到的n n階行列式階行列式. . 定理一定理一: 如果線性方程組得系數(shù)行列式如果線性方程組得系數(shù)行列式D D不等于零，則不等于零，則上述方程組一定有解，且解是唯一的。上述方程組一定有解，且解是唯一的。定理二定理二: 如果上述方程組無(wú)解或有兩個(gè)不同的解，則如果上述方程組無(wú)解或有兩個(gè)不同的解

23、，則它的系數(shù)行列式必為零。它的系數(shù)行列式必為零。二、矩陣的秩二、矩陣的秩定義定義1 1 在在矩陣矩陣A A中，任取中，任取k k行與行與k k列列(K=(K=m,km,k=n)=n)，位于這些行列交叉處的，位于這些行列交叉處的k k的的平方個(gè)元素，不改變他們?cè)谄椒絺€(gè)元素，不改變他們?cè)贏 A中所處的位置中所處的位置次序而得到的次序而得到的k k階行列式階行列式，稱為矩陣，稱為矩陣A A的的k k階階子式。子式。nm 定義二定義二: 設(shè)在矩陣中有一個(gè)不等于設(shè)在矩陣中有一個(gè)不等于0 0的的r r階子式階子式D D，并且所有的，并且所有的r+1r+1階子式（如果存在）全等于零，那么階子式（如果存在）全

24、等于零，那么D D稱為矩陣稱為矩陣A A的最的最高階非零子式，數(shù)高階非零子式，數(shù)r r稱為矩陣稱為矩陣A A的秩。的秩。 有了上述基本知識(shí)以后我們來(lái)看一下幾個(gè)有了上述基本知識(shí)以后我們來(lái)看一下幾個(gè)非常重要的概念非常重要的概念五、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念五、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念 線性規(guī)劃問(wèn)題線性規(guī)劃問(wèn)題 ：)1(0)1(bzmax 1i1njxmixaxcjnjjijnjjj，) 3 . 2()2 . 2() 1 . 2(可行解：可行解：滿足上述約束條件滿足上述約束條件(2.2)(2.2)，(2.3)(2.3)的解的解 ，稱為線性，稱為線性規(guī)劃問(wèn)題的可行解。全部可行解的集合稱為規(guī)劃問(wèn)題的可

25、行解。全部可行解的集合稱為可行域可行域。非可行解非可行解:滿足約束條件（滿足約束條件（2.22.2）但不滿足非負(fù)條件（）但不滿足非負(fù)條件（2.32.3）的解）的解 X X 稱為非稱為非可行解可行解最優(yōu)解：最優(yōu)解：使目標(biāo)函數(shù)使目標(biāo)函數(shù)(2.1)(2.1)達(dá)到最大值的可行解稱為最優(yōu)解。達(dá)到最大值的可行解稱為最優(yōu)解。 基：基：設(shè)設(shè) A A 為約束方程組為約束方程組(2.2)(2.2)的的 m mn n 階系數(shù)矩陣，階系數(shù)矩陣，( (設(shè)設(shè)n nm)m)，其秩其秩為為m m，B B是矩陣是矩陣A A中的一個(gè)中的一個(gè)m mm m階的滿秩子系數(shù)矩陣，稱階的滿秩子系數(shù)矩陣，稱B B是線性規(guī)劃問(wèn)題的是線性規(guī)劃問(wèn)

26、題的一個(gè)基。一個(gè)基。TnxxX),(1不失一般性，設(shè)不失一般性，設(shè) ：),(B11111mmmmmPPaaaa B B中的每一個(gè)列向量中的每一個(gè)列向量P Pj j ( j( j1,1,m ),m )稱為稱為基向量基向量，與基向量與基向量P Pj j對(duì)應(yīng)的對(duì)應(yīng)的變量變量x xj j稱為稱為基變量基變量。線性規(guī)劃中除基變量以外的變量稱為線性規(guī)劃中除基變量以外的變量稱為非基變量非基變量。 基解基解: : 在約束方程組在約束方程組(2.2)(2.2)中，令所有非基變量中，令所有非基變量 x xm+1m+1x xm+2m+2x xn n0 0，又因?yàn)橛杏忠驗(yàn)橛?，根據(jù)克萊姆規(guī)則，由，根據(jù)克萊姆規(guī)則，由m

27、 m個(gè)約個(gè)約束方程可解出束方程可解出m m個(gè)基變量的唯一解個(gè)基變量的唯一解 。將這個(gè)解加上非。將這個(gè)解加上非基變量取基變量取0 0的值有的值有 ，稱，稱X X為線性規(guī)劃問(wèn)題的為線性規(guī)劃問(wèn)題的基基解解。顯然在基解中變量取非零值的個(gè)數(shù)不大于方程數(shù)顯然在基解中變量取非零值的個(gè)數(shù)不大于方程數(shù)m m，故基解的總數(shù)不超故基解的總數(shù)不超過(guò)過(guò) 。 基可行解基可行解: : 滿足變量非負(fù)約束條件滿足變量非負(fù)約束條件(2.3)(2.3)的基解稱為基可行解。的基解稱為基可行解。 可行基可行基: : 對(duì)應(yīng)于基可行解的基稱為可行基。對(duì)應(yīng)于基可行解的基稱為可行基。退化退化解解: : 基礎(chǔ)可行解基礎(chǔ)可行解的非零分量個(gè)數(shù)的非零

28、分量個(gè)數(shù) m m 時(shí)，稱為退化時(shí)，稱為退化解解 0BTmxxxX) 0 , 0 ,(21TmBxxX),(1mnC例：找出下述線性規(guī)劃問(wèn)題的全部基解，指出其中例：找出下述線性規(guī)劃問(wèn)題的全部基解，指出其中的基可行解，并確定最優(yōu)解。的基可行解，并確定最優(yōu)解。04102532max515242131321xxxxxxxxxxxz解解: :該線性規(guī)劃問(wèn)題的全部基解見表該線性規(guī)劃問(wèn)題的全部基解見表l-4l-4中的中的 - -，打，打者為者為基可行解，注基可行解，注* *者為最優(yōu)解，者為最優(yōu)解，z z* * l9l9。 x1x2x3x4x5z是否基可行解是否基可行解00510450452017500541

29、005501201005041552.5001.517.554030222430019 六、線性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系六、線性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系約束方程的約束方程的解空間解空間基礎(chǔ)解基礎(chǔ)解可行解可行解非可行解非可行解基礎(chǔ)基礎(chǔ)可行解可行解退化解退化解如如: : max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t.s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4 x2 +x5 =12 x1，x2，x3，x4，x5 0 以以( (P P3 3、P P4 4、P P5 5) )作為基，令作為基，令x x1 1 = = x x2 2 =

30、0 =0，得到得到 X=X=(0(0，0 0，8 8，1616，12)12)T T為為一個(gè)基可行解，對(duì)應(yīng)圖中一個(gè)基可行解，對(duì)應(yīng)圖中O O點(diǎn)點(diǎn)；2 x2 = 8 x4 =164 x2 +x5 =12以以( (P P1 1、P P2 2、P P5 5) )為基，令為基，令x x3 3 = = x x4 4 =0 =0，可得可得X=X=(4(4，2 2，0 0，0 0，4)4)T T是基最優(yōu)是基最優(yōu)解，對(duì)應(yīng)圖中解，對(duì)應(yīng)圖中Q Q2 2點(diǎn)。點(diǎn)。x1x2O4 Q2(4,2)Q1Q3Q43A以以( (P P2 2、P P4 4、P P5 5) )作為基，令作為基，令x x1 1 = = x x3 3 =0

31、 =0，由由 得得X=X=(0(0，4 4，0 0，1616，- -4)4)T T是個(gè)基解，不是基可行解，對(duì)應(yīng)圖中是個(gè)基解，不是基可行解，對(duì)應(yīng)圖中A A點(diǎn)點(diǎn)某廠利用某廠利用A A、B B兩種原料，生產(chǎn)甲、乙兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下：兩種原料，生產(chǎn)甲、乙兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下：課堂作業(yè)：用圖解法求解下列問(wèn)題課堂作業(yè)：用圖解法求解下列問(wèn)題產(chǎn)品名稱產(chǎn)品名稱甲甲 乙乙單位產(chǎn)品單位產(chǎn)品消耗原料消耗原料原料名稱原料名稱可供利用的原料數(shù)可供利用的原料數(shù)量（量（T/日）日）681 22 1AB產(chǎn)品售價(jià)產(chǎn)品售價(jià) （千元（千元/T） 3 2根據(jù)市場(chǎng)調(diào)查，有如下資料：根據(jù)市場(chǎng)調(diào)查，有如下資料：1.1.乙產(chǎn)品的需求量至

32、多乙產(chǎn)品的需求量至多 2 2 T/T/日日; ;2.2.乙產(chǎn)品的需求量比甲產(chǎn)品的需求量至多大乙產(chǎn)品的需求量比甲產(chǎn)品的需求量至多大 1 1 T/T/日。日。求該廠產(chǎn)值最大的生產(chǎn)方案。求該廠產(chǎn)值最大的生產(chǎn)方案。 max Z= 3xmax Z= 3x1 1+2x+2x2 2 x x1 1+2x+2x2 266 2x 2x1 1+x+x2 288 x x2 222 x x2 2 -x -x1 111 x x1 1，x x2 2000 x x1 1x x2 2X X1 1=10/3,x=10/3,x2 2 =4/3=4/3Z=12.67Z=12.67線性規(guī)劃問(wèn)題及單純形法線性規(guī)劃問(wèn)題及單純形法n線性規(guī)劃

33、問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 n圖解法圖解法 n單純形法原理單純形法原理n單純形法計(jì)算步驟單純形法計(jì)算步驟nMatlab計(jì)算線性規(guī)劃問(wèn)題計(jì)算線性規(guī)劃問(wèn)題三三 單純形法原理單純形法原理本節(jié)重點(diǎn)：本節(jié)重點(diǎn)：凸集與頂點(diǎn)凸集與頂點(diǎn)線性規(guī)劃基本定理線性規(guī)劃基本定理檢驗(yàn)數(shù)的概念和計(jì)算檢驗(yàn)數(shù)的概念和計(jì)算最優(yōu)性判別最優(yōu)性判別基變換（換入變量和換出變量的確定）基變換（換入變量和換出變量的確定）一、線性規(guī)劃問(wèn)題的幾何意義一、線性規(guī)劃問(wèn)題的幾何意義凸組合的概念凸組合的概念凸集的概念凸集的概念頂點(diǎn)頂點(diǎn)線性規(guī)劃基本定理線性規(guī)劃基本定理)10()1 (21XXXm,1mmXXX11i 11mii二維空間二維空

34、間兩點(diǎn)連線上的任何一點(diǎn)都是這兩點(diǎn)的凸組合兩點(diǎn)連線上的任何一點(diǎn)都是這兩點(diǎn)的凸組合1.凸組合凸組合設(shè)設(shè) X1，X2，XmC，若存在若存在 ，0 1，且，且 ，使，使則稱則稱X 為為X1，X2，Xm 的凸組合。的凸組合。)10()1 (21XXXX2 X X1令令21221)1()(XXXXXXX1X -XX-X2 12 2 12 X -XX-X2. 凸集凸集 對(duì)簡(jiǎn)單的幾何形體可以直觀地判斷其凹凸性，但在高維對(duì)簡(jiǎn)單的幾何形體可以直觀地判斷其凹凸性，但在高維空間，只能給出點(diǎn)集的解析表達(dá)式，因此只能用數(shù)學(xué)解析式空間，只能給出點(diǎn)集的解析表達(dá)式，因此只能用數(shù)學(xué)解析式判斷。判斷。凸集的概念為：如果集合凸集的概

35、念為：如果集合C C中任意兩個(gè)點(diǎn)中任意兩個(gè)點(diǎn)X X1 1，X X2 2，其連其連線上的所有點(diǎn)也都是集合線上的所有點(diǎn)也都是集合C C中的點(diǎn)，稱中的點(diǎn)，稱C C為凸集。為凸集。由于由于X X1 1，X X2 2的連線可表示為的連線可表示為 )10()1 (21aXaaX 因此凸集定義用數(shù)學(xué)解析式可表為：對(duì)任何因此凸集定義用數(shù)學(xué)解析式可表為：對(duì)任何 ，有，有 則稱則稱C C為凸集為凸集. . CXCX21,) 10()1 (21aCXaaX(a)(b)(c)(d)(e)(a)(b)(c)(d)(e)圖中圖中紅粗線紅粗線和和紅點(diǎn)紅點(diǎn)是頂點(diǎn)。是頂點(diǎn)。 3.3.頂點(diǎn)頂點(diǎn) 凸集凸集C C中滿足下述條件的點(diǎn)中

36、滿足下述條件的點(diǎn)X X稱為頂點(diǎn)。稱為頂點(diǎn)。 如果如果C C中不存在任何兩個(gè)不同的點(diǎn)中不存在任何兩個(gè)不同的點(diǎn)X X1 1，X X2 2，使使X X成為這兩成為這兩個(gè)點(diǎn)連線上的一個(gè)點(diǎn)，或者：對(duì)任何個(gè)點(diǎn)連線上的一個(gè)點(diǎn)，或者：對(duì)任何 , ,不不存在存在 ，則稱，則稱X X是凸集是凸集C C的頂點(diǎn)。的頂點(diǎn)。 CXCX21,) 10()1 (21aCXaaX 4. 4. 線性規(guī)劃基本定理線性規(guī)劃基本定理定理定理1 1 若線性規(guī)劃問(wèn)題存在可若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行域是凸集。行解，則問(wèn)題的可行域是凸集。 證證 ( (方法方法1)1) 若若滿足線性規(guī)劃約束條件滿足線性規(guī)劃約束條件 的所有點(diǎn)組成的幾

37、的所有點(diǎn)組成的幾何圖形何圖形C C是凸集，根據(jù)凸集是凸集，根據(jù)凸集定義定義，C C內(nèi)任意兩點(diǎn)內(nèi)任意兩點(diǎn)X Xl l，X X2 2連線上的點(diǎn)也必然在連線上的點(diǎn)也必然在C C內(nèi)內(nèi)，下面給予證明。，下面給予證明。 njjjxp1b設(shè)設(shè) 為為C C內(nèi)任意兩點(diǎn)，內(nèi)任意兩點(diǎn)，即即 ，將，將X X1 1，X X2 2代入約束條件有代入約束條件有 TnxxxX),(112111TnxxxX),(222212CXCX21,;b11njjjxpnjjjxp12b(2.4)(2.4) X X1 1，X X2 2連線上任意一點(diǎn)可以表示為：連線上任意一點(diǎn)可以表示為： )10()1 (21aXaaXX(2.5)(2.5)

38、 將式（將式（2.4）代入式（）代入式（2.5）得：）得：babbabaxpxpaxpxaaxpxpnjnjnjjjjjjjnjnjjjjjj1112211121)1( 所以所以 。由于集合中任意兩點(diǎn)連線上的點(diǎn)均在集。由于集合中任意兩點(diǎn)連線上的點(diǎn)均在集合內(nèi)，所以合內(nèi)，所以C C為凸集。為凸集。 CXaaXX21)1 ( 線性規(guī)劃問(wèn)題的可行解線性規(guī)劃問(wèn)題的可行解X=(xX=(x1 1，x x2 2，x xn n）T T為基可為基可行解的充分必要行解的充分必要條件是條件是X X 的正的正分量所對(duì)應(yīng)的系數(shù)列向量是線分量所對(duì)應(yīng)的系數(shù)列向量是線性無(wú)關(guān)的。性無(wú)關(guān)的。證明：證明：(1)(1)必要性必要性 由

39、基可行解的定義可知，由基可行解的定義可知，X X為基可行解為基可行解 其正其正分量的系數(shù)列向量分量的系數(shù)列向量線性無(wú)關(guān)線性無(wú)關(guān)。 (2)(2)充分性充分性 若向量若向量 線性獨(dú)立，則必有線性獨(dú)立，則必有kmkm；當(dāng)當(dāng)k km m時(shí)，它們恰好構(gòu)成一個(gè)基，從而時(shí)，它們恰好構(gòu)成一個(gè)基，從而 為相應(yīng)的基可行解。當(dāng)是為相應(yīng)的基可行解。當(dāng)是kmk0 (m+1 0 (m+1 j j n)n) ，則有，則有x xj j 00，其它非其它非基變量仍為零的可行解基變量仍為零的可行解， 其目標(biāo)函數(shù)值其目標(biāo)函數(shù)值這說(shuō)明這說(shuō)明當(dāng)前解不是最優(yōu)解。若所有當(dāng)前解不是最優(yōu)解。若所有 0 0 (m+1 (m+1 j j n)n)

40、 ，則，則z z0 0為可行解為可行解所能取得的目標(biāo)函數(shù)最大值，說(shuō)明當(dāng)前解是最優(yōu)解。故稱所能取得的目標(biāo)函數(shù)最大值，說(shuō)明當(dāng)前解是最優(yōu)解。故稱 為為檢驗(yàn)數(shù)。將基變量的檢驗(yàn)數(shù)。將基變量的檢驗(yàn)檢驗(yàn)數(shù)數(shù)0 0也視為其檢驗(yàn)數(shù)，可得：也視為其檢驗(yàn)數(shù)，可得：,zxzzjj00 s sjs sjs s 注意：注意：x xj j 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) 是當(dāng)是當(dāng)z z 表示為非基變量的函數(shù)時(shí)目標(biāo)表示為非基變量的函數(shù)時(shí)目標(biāo)函數(shù)中函數(shù)中x xj j 的系數(shù)?；兞康臋z驗(yàn)數(shù)為零。的系數(shù)。基變量的檢驗(yàn)數(shù)為零。最優(yōu)性判別定理：最優(yōu)性判別定理： 若基可行解對(duì)應(yīng)的檢驗(yàn)數(shù)若基可行解對(duì)應(yīng)的檢驗(yàn)數(shù) 0 ( 0 ( j=1j=1，2 2，,

41、n),n)則此則此解是最優(yōu)解，否則不是最優(yōu)解。解是最優(yōu)解，否則不是最優(yōu)解。js s3.基變換基變換 求一個(gè)改進(jìn)的、求一個(gè)改進(jìn)的、“相鄰相鄰”的可行基，一個(gè)基變量的可行基，一個(gè)基變量將變成非基變量（換出），一個(gè)非基變量將變成基變將變成非基變量（換出），一個(gè)非基變量將變成基變量（換入）。量（換入）。 (1)(1) 換入變量的確定換入變量的確定 一般，當(dāng)一般，當(dāng)jmaxjs s|js s0=s sk，取，取xk為換入變量。為換入變量。 例例 10 中，中，s s2s s1，可取，可取x2為換入變量。為換入變量。 第第k列為主元列。列為主元列。 第第2列為主元列。列為主元列。 (2) 換出變量的確定換

42、出變量的確定)m,2, 1i (xabxn1mjjijii在在 中，中，令令xk0 ，而而xj =0(m+1 j n，j k)，要保持要保持xi 0 ( i=1，2，,m)，即即若所有若所有 則則xk 可取無(wú)窮大，問(wèn)題無(wú)最優(yōu)解?？扇o(wú)窮大，問(wèn)題無(wú)最優(yōu)解。, 0aiklklikikiiabaab 0min必須必須 Xk于是，當(dāng)于是，當(dāng) 為換出變量為換出變量。lllklkXXabX,0,L L行為主元行，行為主元行，alk lk為主元素為主元素 (1) 最優(yōu)性判別定理最優(yōu)性判別定理 若基可行解對(duì)應(yīng)的檢驗(yàn)數(shù)若基可行解對(duì)應(yīng)的檢驗(yàn)數(shù) 0 ( j=1，2，,n),n)，則此解是最優(yōu)解，否則不是最優(yōu)解。則此

43、解是最優(yōu)解，否則不是最優(yōu)解。js(2) 換換入入變變量量的的確確定定方方法法 一一般般，當(dāng)當(dāng) jmaxjs s|js s0=s sk，取取 xk為為換換入入變變量量。 (3) (3) 換出變量確定方法換出變量確定方法 一般，計(jì)算一般，計(jì)算 = = lklikikiiabaabmin 0 ，第，第 l 個(gè)約束個(gè)約束對(duì)應(yīng)的基變量為換出變量。對(duì)應(yīng)的基變量為換出變量。 (4)當(dāng)所有的當(dāng)所有的 0，又對(duì)某個(gè)非基變量，又對(duì)某個(gè)非基變量 ， 有有 這表明可以找到另一頂點(diǎn)這表明可以找到另一頂點(diǎn)(基可行解基可行解)目標(biāo)函數(shù)值也達(dá)到最大。由于該兩點(diǎn)連線上的點(diǎn)也目標(biāo)函數(shù)值也達(dá)到最大。由于該兩點(diǎn)連線上的點(diǎn)也屬可行域內(nèi)

44、的點(diǎn)，且目標(biāo)函數(shù)值相等，即該線性規(guī)屬可行域內(nèi)的點(diǎn)，且目標(biāo)函數(shù)值相等，即該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。反之，當(dāng)所有非基變量劃問(wèn)題有無(wú)窮多最優(yōu)解。反之，當(dāng)所有非基變量 的的 O，又又Pj0，表明線性規(guī)劃有無(wú)界解。表明線性規(guī)劃有無(wú)界解。 js1. 系統(tǒng)中有系統(tǒng)中有j種活動(dòng)，它們分享有限的資源種活動(dòng)，它們分享有限的資源bi；2. 進(jìn)行一個(gè)單位的第進(jìn)行一個(gè)單位的第j種活動(dòng)，需要第種活動(dòng)，需要第 i 種資源的量為種資源的量為aij；3. 一個(gè)單位的第一個(gè)單位的第j種活動(dòng)的產(chǎn)出以種活動(dòng)的產(chǎn)出以cj表示表示；4. 第第j項(xiàng)活動(dòng)的量用項(xiàng)活動(dòng)的量用xj表示。表示。5. 機(jī)會(huì)成本機(jī)會(huì)成本Zj：表示增加一個(gè)單位的表示

45、增加一個(gè)單位的xj所引起的目標(biāo)函數(shù)的下降值。所引起的目標(biāo)函數(shù)的下降值。6. 價(jià)值系數(shù)價(jià)值系數(shù)cj：表示增加一個(gè)單位的表示增加一個(gè)單位的xj所引起的目標(biāo)函數(shù)的增加值所引起的目標(biāo)函數(shù)的增加值。7. 判別數(shù)判別數(shù) =cj-zj ： 表示增加一個(gè)單位的表示增加一個(gè)單位的xj所引起的目標(biāo)函數(shù)的凈增值。所引起的目標(biāo)函數(shù)的凈增值。js四、線性規(guī)劃問(wèn)題的經(jīng)濟(jì)釋義四、線性規(guī)劃問(wèn)題的經(jīng)濟(jì)釋義課堂作業(yè)：課堂作業(yè)：0,12023310032.244540max321321321321xxxxxxxxxtsxxxz有如下線性規(guī)劃：有如下線性規(guī)劃：1.變成標(biāo)準(zhǔn)型；變成標(biāo)準(zhǔn)型；2.確定初始基可行解；確定初始基可行解；3.確

46、定換出變量；確定換出變量；4.確定換入變量；確定換入變量；5.說(shuō)出主元行、主元列、和主元素說(shuō)出主元行、主元列、和主元素。0,12023310032. .00244540max543215321432154321xxxxxxxxxxxxxtsxxxxxz1.標(biāo)準(zhǔn)型如下：標(biāo)準(zhǔn)型如下：2. 初始基可行解：初始基可行解：X(0)=(0，0，0，100，120)；3.換出變量：換出變量：x24.確定換入變量確定換入變量:x45.說(shuō)出主元行說(shuō)出主元行L L=1;主元列主元列k=2;主元素主元素a1212=3。 線性規(guī)劃問(wèn)題及單純形法線性規(guī)劃問(wèn)題及單純形法n線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

47、n圖解法圖解法 n單純形法原理單純形法原理n單純形法計(jì)算步驟單純形法計(jì)算步驟nMatlab計(jì)算線性規(guī)劃問(wèn)題計(jì)算線性規(guī)劃問(wèn)題第四節(jié)第四節(jié) 單純形法計(jì)算步驟單純形法計(jì)算步驟本節(jié)重點(diǎn)：本節(jié)重點(diǎn)：?jiǎn)渭冃伪恚ㄌ貏e是檢驗(yàn)數(shù)行）單純形表（特別是檢驗(yàn)數(shù)行）單純形法的計(jì)算步驟單純形法的計(jì)算步驟一、一、單純形表單純形表 用單純形法求解線性規(guī)劃時(shí)，設(shè)計(jì)了用單純形法求解線性規(guī)劃時(shí)，設(shè)計(jì)了一種專門表格，稱為單純形表。迭代計(jì)算一種專門表格，稱為單純形表。迭代計(jì)算中每找出一個(gè)新的基可行解時(shí)，就重畫一中每找出一個(gè)新的基可行解時(shí)，就重畫一張單純形表。含初始基可行解的單純形表張單純形表。含初始基可行解的單純形表稱為稱為初始單純形

48、表初始單純形表，含最優(yōu)解的單純形表含最優(yōu)解的單純形表稱為稱為最終單純形表最終單純形表。 )1(0)1(bzmax 11njxmixPxcjnjjjnjjj，考慮系數(shù)矩陣中有單位矩陣的情況：考慮系數(shù)矩陣中有單位矩陣的情況：?jiǎn)渭冃伪韱渭冃伪韈j c1 cm cm + 1 cn CB XB b x1 xm xm + 1 xn I c1 c2 cm x1 x2 xm b1 b2 bm 1 0 0 0 0 1 a1,m + 1 a2,m + 1 am ,m + 1 a1n a2n am n 1 2 m z z 值 0 0 sm + 1 sn X XB B列列基變量；基變量；C CB B列列基變量的價(jià)值系

49、數(shù)基變量的價(jià)值系數(shù)( (目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)) )； c cj j行行價(jià)值系數(shù)；價(jià)值系數(shù)； b b列列方程組右側(cè)常數(shù)；方程組右側(cè)常數(shù)； 列列確定換入變量時(shí)的比率計(jì)算值；確定換入變量時(shí)的比率計(jì)算值；底行底行檢驗(yàn)數(shù)；檢驗(yàn)數(shù)；中間中間約束方程系數(shù)。約束方程系數(shù)。lklikikiiabaab 0min | 0 = s sk jmaxjs smiijijmjmjjjjaccacacacc12211)(sjs sI =二、計(jì)算步驟二、計(jì)算步驟(1)(1)找出初始可行基找出初始可行基，確定初始基可行解確定初始基可行解，建立初始單純形表。建立初始單純形表。(2)(2)檢驗(yàn)檢驗(yàn)各非基變量各非基變量xj的檢驗(yàn)

50、數(shù)，若的檢驗(yàn)數(shù)，若s sj 0，j=m+1，n n；則則已得到已得到最優(yōu)解最優(yōu)解，可停止計(jì)算，否則轉(zhuǎn)入下一步。可停止計(jì)算，否則轉(zhuǎn)入下一步。(3)(3)在在s sj 0，j=m+1，n n中，若有某個(gè)中，若有某個(gè)s sk對(duì)應(yīng)對(duì)應(yīng)xk的系數(shù)列向量的系數(shù)列向量Pk 0，則則此問(wèn)題是此問(wèn)題是無(wú)界解無(wú)界解，停止計(jì)算。否則，轉(zhuǎn)入下一步。停止計(jì)算。否則，轉(zhuǎn)入下一步。(4)(4)根據(jù)根據(jù)max(max(s sj 0) =s sk，確定確定xk為換入變量為換入變量，按按 規(guī)則計(jì)算規(guī)則計(jì)算 = =minbminbi i/a/aikikaaikik00可可確定確定第第L行的基變量為行的基變量為換出變量換出變量。轉(zhuǎn)入

51、下一步。轉(zhuǎn)入下一步。cj CB XB b x1 x2 x3 x4 x5 z 2 3 0 0 0 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-3例例 1 10 0 的的初初始始單單純純形形表表： cj CB XB b x1 x2 x3 x4 x5 z 2 3 0 0 02 1 0 1 0 -1/2 9 2 0 0 0 -3/4003x3x4x224-( ) 3 0 1 0 0 1/4 16 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=0cj CB XB b

52、x1 x2 x3 x4 x5 z 2 3 0 0 0 2 1 0 1 0 -1/2 13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 9 2 0 0 0 -3/4003x3x4x224- 3 0 1 0 0 1/4 16 4 0 0 1 0( ) X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T， z z1 1 =9=9cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2( )cj CB XB b x1 x2 x3 x4 x5 z 2 3 0 0 0 4 1 0 0 1/4 0 14 0 0 -1