《運(yùn)籌學(xué)》課件-第2講

1、2024/3/20,1,線性規(guī)劃與目標(biāo)規(guī)劃,2024/3/20,2,目 錄,1.線性規(guī)劃與單純形法,2.對(duì)偶理論和靈敏度分析,3.運(yùn)輸問(wèn)題,4.目標(biāo)規(guī)劃,2024/3/20,3,線性規(guī)劃(Linear Programming)是運(yùn)籌學(xué)的一個(gè)重要分支。線性規(guī)劃在理論上比較成熟，在實(shí)用中的應(yīng)用日益廣泛與深入。它已是現(xiàn)代科學(xué)管理的重要手段之一。線性規(guī)劃最常用的求解方法—— 單純形法(Simplex Method) 由丹捷格(G B Da

2、ntzig)提出(1947年)。,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,2024/3/20,4,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,1.1 問(wèn)題的提出例1 生產(chǎn)計(jì)劃 某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如表所示。,問(wèn)題：工廠應(yīng)分別生產(chǎn)多少單位甲、乙產(chǎn)品才能使工廠獲利最多？,如何用數(shù)學(xué)關(guān)系式描述這個(gè)問(wèn)題？,2024/3/20,5,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,設(shè)x1 ，x2 分別表示計(jì)劃生產(chǎn)I，II產(chǎn)

3、品的數(shù)量，稱它們?yōu)闆Q策變量。生產(chǎn)x1 ，x2 的多少，受到資源擁有量的限制，即存在約束條件。 x1 +2x2 ≤ 84 x1 ≤164 x2 ≤12生產(chǎn)的產(chǎn)品不能是負(fù)值： x1 ，x2 ≥ 0。如何安排生產(chǎn)，使得利潤(rùn)最大，這是目標(biāo)函數(shù)。,max z = 2 x1 + 3 x2,2024/3/20,6,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,因此該問(wèn)題的數(shù)學(xué)模型為：

4、 ( 設(shè)生產(chǎn)甲產(chǎn)品 x1 個(gè)單位、生產(chǎn)乙產(chǎn)品 x2 個(gè)單位)目標(biāo)函數(shù): max z = 2 x1 + 3 x2約束條件: x1 +2x2 ≤ 84 x1 ≤164 x2 ≤12 x1 ，x2 ≥0這種模型實(shí)際上是一種約束限制下的最優(yōu)線性數(shù)

5、學(xué)模型，稱為線性規(guī)劃。,2024/3/20,7,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,例2 簡(jiǎn)化的環(huán)境保護(hù)問(wèn)題 靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)立方米，在兩個(gè)工廠之間有一條流量為每天200萬(wàn)立方米的支流。第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬(wàn)立方米，第二化工廠每天排放這種工業(yè)污水1.4萬(wàn)立方米。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于

6、0.2%。這兩個(gè)工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是1000元/萬(wàn)立方米。第二化工廠處理工業(yè)污水的成本是800元/萬(wàn)立方米?，F(xiàn)在問(wèn)在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工廠總的處理工業(yè)污水費(fèi)用最小。,2024/3/20,8,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,建模型之前的分析和計(jì)算設(shè)：第一化工廠每天處理工業(yè)污水量為x1 萬(wàn)立方米，第二化工廠每天處理工業(yè)污水量為x2 萬(wàn)立方米。,此問(wèn)題的線性規(guī)劃模型

7、： 目標(biāo)函數(shù)：max z = 1000 x1 + 800 x2 約束條件：s.t. x1 ≥1 0.8x1 + x2 ≥1.6 x1

8、 ≤2 x2 ≤1.4 x1 , x2 ≥ 0,2024/3/20,9,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,從以上兩例可以看出，其共同特征：(1) 每一個(gè)線性規(guī)劃問(wèn)題都用一組決策變量 表示某一方案，這組決

9、策變量的值就代表一個(gè)具體方案，一般這些變量取值是非負(fù)且連續(xù)的；(2) 存在有關(guān)的數(shù)據(jù)，同決策變量構(gòu)成互不矛盾的約束條件，這些約束條件可以用一組線性等式或線性不等式來(lái)表示； (3) 存在一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量及其有關(guān)的價(jià)值系數(shù)構(gòu)成的的線性函數(shù)(稱為目標(biāo)函數(shù))來(lái)表示。按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。 滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。,2024/3/20,10,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,

10、線性規(guī)劃問(wèn)題是在一組線性等式或不等式的約束之下，求一個(gè)線性函數(shù)的最大值或最小值的問(wèn)題。它由以下部分組成： 目標(biāo)函數(shù) max z 或 min f 約束條件 s. t. (subject to) 滿足于 決策變量 用符號(hào) xj 等來(lái)表示可控制的因素。,2024/3/20,11,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,線性規(guī)劃模型的一般形式目標(biāo)函數(shù): max（min）z = c1 x1 + c2

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

12、 …… …… am1 x1 + am2 x2 + … + amn xn ≤（ =, ≥ ）bm x1 ，x2 ，… ，x

13、n ≥ 0 cj(j=1,2, …,n)稱為價(jià)值系數(shù)； aij稱為技術(shù)系數(shù)； bi稱為限額系數(shù)。,2024/3/20,12,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,1.2 圖解法對(duì)于含有兩個(gè)決策變量的線性規(guī)劃模型，可以利用圖解法(Graph Method)求解。圖解法是解線性規(guī)劃的一種簡(jiǎn)便、直觀的方法，對(duì)于理解線性規(guī)劃的基本概念和基本原理也是很有幫助的。定義：可行解：滿足所有約束條件的向量稱為線性規(guī)劃問(wèn)題的可行解?？尚杏颍喝w可行

14、解的集合稱為線性規(guī)劃問(wèn)題的可行域。最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解，稱為線性規(guī)劃的最優(yōu)解。,2024/3/20,13,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,例1中，所有約束條件作為半平面所圍成的范圍如圖中陰影部分所示。陰影部分中的每一個(gè)點(diǎn)(包括邊界點(diǎn))都是這個(gè)線性規(guī)劃問(wèn)題的可行解。,對(duì)于例1，考察其約束條件所圍成的范圍，作圖如下：,可行域,2024/3/20,14,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,考察目標(biāo)函數(shù) ma

15、x z = 2 x1 + 3 x2將目標(biāo)函數(shù)化為點(diǎn)斜式坐標(biāo)： x2=-(2/3) x1 +z/3,,最優(yōu)解,由于在同一條直線上的所有點(diǎn)的目標(biāo)函數(shù)取同樣的值，故稱為等值線。,2024/3/20,15,解聯(lián)立方程組: x1 + 2x2 = 8

16、 4x1 = 16 得最優(yōu)解為： x1 = 4， x2 = 2， 記為: (x1 , x2)T =(4，2)T或者最優(yōu)目標(biāo)值為： z = 14。 以上最優(yōu)解和最優(yōu)值說(shuō)明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是：生產(chǎn)4件產(chǎn)品I，生產(chǎn)2件產(chǎn)品II，可得到最大利潤(rùn)為14元。,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

17、,2024/3/20,16,用圖解法求解線性規(guī)劃的基本步驟：畫(huà)可行域：分別取決策變量 x1 ，x2 為坐標(biāo)向量建立直角坐標(biāo)系?；繕?biāo)函數(shù)等值線：對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。 若各半平面交出來(lái)的公共區(qū)域存在，顯然，其中的點(diǎn)滿足所有的約束條件，稱這樣的點(diǎn)為此線性規(guī)劃的可行解，全體可行解的集合稱為可行集或可行域。若這樣的公共區(qū)域不存在，則該線性規(guī)劃問(wèn)題無(wú)可行解。找最優(yōu)解：任意給定目

18、標(biāo)函數(shù)一個(gè)確定的值，作出對(duì)應(yīng)的目標(biāo)函數(shù)等值線，并確定該族等值線平行移動(dòng)時(shí)目標(biāo)函數(shù)值增加的方向。然后平移目標(biāo)函數(shù)的等值線，使其達(dá)到既與可行域有交點(diǎn)又不可能使值再增加的位置(有時(shí)交于無(wú)窮遠(yuǎn)處，此時(shí)稱無(wú)有限最優(yōu)解）。此時(shí)，目標(biāo)函數(shù)等值線與可行域的交點(diǎn)即此線性規(guī)劃的最優(yōu)解（一個(gè)或多個(gè)），此目標(biāo)函數(shù)的值即最優(yōu)值。,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,2024/3/20,17,線性規(guī)劃問(wèn)題的解可能出現(xiàn)的幾種情況：有唯一的最優(yōu)解；存在無(wú)窮多最優(yōu)解(多重最優(yōu)

19、解)；,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,目標(biāo)函數(shù) max z=2 x1 +4 x2,其最優(yōu)解為線段Q2Q3上的所有點(diǎn)，即{(x1 , x2)T| x1 +2 x2=8，2 ≤ x1 ≤4},2024/3/20,18,無(wú)界解：可行域無(wú)邊界，目標(biāo)函數(shù)值可增大(減小)到無(wú)窮大(無(wú)窮小)，實(shí)際上這類問(wèn)題無(wú)最優(yōu)解；無(wú)可行解。,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,,,,在目標(biāo)函數(shù)等值線向右上方移動(dòng)的過(guò)程中，上端無(wú)邊界，取不到最大值，即無(wú)界解。,20

20、24/3/20,19,無(wú)可行解：當(dāng)存在矛盾的約束條件時(shí)，可行域?yàn)榭占?，無(wú)可行解，故無(wú)最優(yōu)解。如果在例1的數(shù)學(xué)模型中增加一個(gè)約束條件: max z = 2

21、 x1 + 3 x2,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,可行域的交集為空集，故無(wú)可行解。,,2024/3/20,20,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,注：當(dāng)線性規(guī)劃問(wèn)題的可行域非空時(shí)，它是有界的或無(wú)界的凸多邊形；若線性規(guī)劃問(wèn)題存在最優(yōu)解，則一定在有界可行域的某個(gè)頂點(diǎn)得到；若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則它們連線上的任意一點(diǎn)都是最優(yōu)解，即有無(wú)窮多個(gè)最優(yōu)解。,2024/3/20,21,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,1.3 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式以下形

22、式的線性規(guī)劃模型稱為標(biāo)準(zhǔn)形(M1)：目標(biāo)函數(shù)： max z = c1 x1 + c2 x2 + … + cn xn 約束條件： s. t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2

23、 …… …… am1 x1 + am2 x2 + … + amn xn= bm x1 ，x2 ，… ，xn ≥ 0.,均為求最大值,均為等式約束,均為非負(fù)決策變量,右端常數(shù)項(xiàng)bi ≥ 0,2024/3/20,22,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)

24、要求： 目標(biāo)最大化 約束方程為等式 決策變量為非負(fù) 右端項(xiàng)為非負(fù),2024/3/20,23,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,線性規(guī)劃問(wèn)題的幾種表示形式：M1’:M1’’(向量和矩陣表示):,2024/3/20,24,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,線性規(guī)劃問(wèn)題的幾種表示形式：矩陣表示:,2024/3/20,25,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其

25、轉(zhuǎn)化為標(biāo)準(zhǔn)形式:1.極小化目標(biāo)函數(shù)的問(wèn)題：設(shè)目標(biāo)函數(shù)為 min f = c1x1 + c2x2 + … + cnxn (可以)令 z ＝ - f ， 則該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即 max z = - c1x1 - c2x2 - … - cnxn 。 但必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但他們最優(yōu)解

26、的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即 min f ＝ - max z 。,2024/3/20,26,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：2. 約束條件不是等式的問(wèn)題： 設(shè)約束條件為 ai1 x1 + ai2 x2 + … + ain xn ≤ bi 可以引進(jìn)一個(gè)新的變量 s ，使它等于約束右邊與左邊之差 s = bi – (ai1 x1 + a

27、i2 x2 + … + ain xn ) 。 顯然，s 也具有非負(fù)約束，即 s≥0 ，這時(shí)新的約束條件成為 ai1 x1 + ai2 x2 + … + ain xn + s = bi 。,2024/3/20,27,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：2. 約束條件不是等式的問(wèn)題： 當(dāng)約束條件為 ai1 x1+a

28、i2 x2+ … +ain xn ≥ bi 時(shí)，類似地令 s = (ai1 x1+ai2 x2+ … +ain xn) - bi 。 顯然，s 也具有非負(fù)約束，即s≥0，這時(shí)新的約束條件成為 ai1 x1+ai2 x2+ … +ain xn - s = bi 。,2024/3/20,28,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：

29、2. 約束條件不是等式的問(wèn)題：為了使約束由不等式成為等式而引進(jìn)的變量s： 當(dāng)不等式為“小于等于”時(shí)稱為“松弛變量”； 當(dāng)不等式為“大于等于”時(shí)稱為“剩余變量”； 如果原問(wèn)題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的變量，有時(shí)也將它們統(tǒng)稱為松弛變量。,2024/3/20,29,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：2. 約束條件不是等式的問(wèn)題：補(bǔ)例：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)

30、形式  min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38

31、 x1，x2，x3 ≥ 0 解：首先, 將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令 z = -f = -3.6x1 + 5.2x2 - 1.8x3,2024/3/20,30,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：2. 約束條件不是等式的問(wèn)題：其次考慮約束，有 2 個(gè)不等式約束，引進(jìn)松弛變量 x4，x5 ≥0。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)

32、劃問(wèn)題： max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s. t. 2.3x1 + 5.2x2- 6.1x3 + x4 = 15.7 4.1x1 + 3.3x3 - x5 = 8.9 x1 + x2 + x3 = 38

33、 x1，x2，x3，x4，x5 ≥ 0 。,2024/3/20,31,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：3. 變量無(wú)符號(hào)限制的問(wèn)題： 在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量 xj 沒(méi)有非負(fù)約束時(shí)，可以令 xj = xj’ - xj” 其中

34、 xj’≥0， xj”≥0即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然 xj 的符號(hào)取決于xj’ 和 xj” 的大小。,2024/3/20,32,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：4.右端項(xiàng)有負(fù)值的問(wèn)題： 在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如 bi<0，則把該等式約束兩端同時(shí)乘以-1，得到：

35、 - ai1 x1 - ai2 x2 - … - ain xn = -bi,2024/3/20,33,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：補(bǔ)例 將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 min f = -3 x1 + 5 x2 + 8 x3 - 7 x4 s. t. 2 x1 - 3 x2 + 5 x3 + 6 x4 ≤

36、28 4 x1 + 2 x2 + 3 x3 - 9 x4 ≥ 39 6 x2 + 2 x3 + 3 x4 ≤ - 58 x1，x3，x4 ≥ 0,2024/3/20,34,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：解：首先，將目標(biāo)函數(shù)轉(zhuǎn)

37、換成極大化： 令 z = -f = 3x1–5x2–8x3+7x4 ；其次考慮約束，有 3 個(gè)不等式約束，引進(jìn) 2 個(gè)松弛變量和 1 個(gè)剩余變量 x5 , x6 , x7 ≥0 ；由于 x2 無(wú)非負(fù)限制，引入兩個(gè)非負(fù)變量，可令 x2= x2’- x2”, 其中 x2’≥0，x2”≥0 ；由于第 3 個(gè)約束右端項(xiàng)系數(shù)為 -58，于是把該式兩端乘以 -1 。于是，我們可以得到以下標(biāo)準(zhǔn)形式

38、的線性規(guī)劃問(wèn)題：,2024/3/20,35,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,化線性規(guī)劃標(biāo)準(zhǔn)型的方法：max z = 3x1 – 5x2’ + 5x2” – 8x3 + 7x4 s. t. 2x1 – 3x2’ + 3x2” + 5x3 + 6x4 + x5 = 28 4x1 + 2x2’ - 2x2” + 3x3 - 9x4 -

39、 x6 = 39 -6x2’+ 6x2” - 2x3 - 3x4 - x7 = 5 x1，x2’，x2”，x3，x4，x5，x6，x7 ≥ 0,2024/3/20,36,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,課堂練習(xí)： 某公司由于生產(chǎn)需要，共需要 A，B 兩種原料至少 350 噸 ( A

40、, B 兩種材料有一定替代性)，其中 A 原料至少購(gòu)進(jìn) 125 噸。但由于 A，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)在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購(gòu)買(mǎi) A，B 兩種原料，使得購(gòu)進(jìn)成本最低？,2024/3/20,37,

41、線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,求使購(gòu)進(jìn)成本最低的 x1 和 x2。解：?jiǎn)栴}的線性規(guī)劃模型為 目標(biāo)函數(shù)： min f = 2 x1+3 x2 約束條件： x1+ x2 ≥350 x1 ≥125

42、 2 x1+ x2 ≤ 600 x1 ≥0 ， x2 ≥0 。,2024/3/20,38,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,,用圖解法解此題。,2024/3/20,39,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,,此例 的線性規(guī)劃標(biāo)準(zhǔn)型為 目標(biāo)函數(shù)：

43、max z = -2 x1 - 3 x2 - 0s1 - 0s2- 0s3 約束條件： x1+ x2 －s1 =350 x1 －s2 = 125 2 x1+ x2 + s3 = 600 x1 ， x2 ，s1， s2，s3 ≥0 。,2024/3

44、/20,40,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,1.4 線性規(guī)劃問(wèn)題解的概念：考察線性規(guī)劃的標(biāo)準(zhǔn)型： 滿足約束條件(1-5)，(1-6)式的解X=(x1, x2，…，xn)T，稱為線性規(guī)劃問(wèn)題的可行解，其中使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解。,2024/3/20,41,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,基(矩陣)：假設(shè)A為m*n階矩陣，A的秩為m（即A為行滿秩矩陣） 等價(jià)定義：B為A的m個(gè)線性無(wú)關(guān)的列向量構(gòu)成的m階方陣，

45、則稱B是線性規(guī)劃問(wèn)題的一個(gè)基，也稱基矩陣。,2024/3/20,42,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,基本解：對(duì)于取定的一個(gè)基B，在約束方程組中令非基變量取零值，可以得到方程組的一個(gè)確定的解，稱這個(gè)解為基本解?；究尚薪猓寒?dāng)基本解的所有分量均非負(fù)時(shí)，稱之為基本可行集。注：基本可行解的幾何意義是可行域的頂點(diǎn)?？尚谢夯究尚薪鈱?duì)應(yīng)的基稱為可行基。最優(yōu)基：最優(yōu)解對(duì)應(yīng)的基稱為最優(yōu)基。退化的基本可行解：如果一個(gè)基本可行解的某些基變量的值為零

46、，則稱之為退化的基本可行解。,2024/3/20,43,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,,2024/3/20,44,線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型,,下面來(lái)看看剛才得到的兩個(gè)基本可行解的集合意義。實(shí)際上，約束條件與下面的約束條件是等價(jià)的。其可行域如圖所示。其中a點(diǎn)對(duì)應(yīng)的基本可行解(0,10,30,0)T,b點(diǎn)對(duì)應(yīng)基本可行解(18,4, 0,0)T。a點(diǎn)和b點(diǎn)都是可行域的頂點(diǎn)。因此，基本可行解的幾何意義為可行域的頂點(diǎn)。,,,,,,,a,