運(yùn)籌學(xué)第2講線性規(guī)劃1

1、線性規(guī)劃線性規(guī)劃 線性規(guī)劃(Linear Programming)是運(yùn)籌學(xué)的一個重 要分支。 線性規(guī)劃在理論上比較成熟，在實(shí)用中的應(yīng)用日益廣 泛與深入。它已是現(xiàn)代科學(xué)管理的重要手段之一。 線性規(guī)劃最常用的求解方法 單純形法(Simplex Method) 由丹捷格(G B Dantzig)提出(1947年)。線性規(guī)劃線性規(guī)劃 線性規(guī)劃的數(shù)學(xué)模型 圖解法 單純形法 單純形法的進(jìn)一步討論 線性模型的應(yīng)用、編程及軟件實(shí)現(xiàn) 本章主要內(nèi)容 線性規(guī)劃線性規(guī)劃 生產(chǎn)和經(jīng)營管理中經(jīng)常提出如何合理安排，使人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。規(guī)劃問題： 線性規(guī)劃通常解決下列兩類問題：

2、 當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)。 在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤最大）。線性規(guī)劃線性規(guī)劃例1.1 下料問題 如圖所示，如何截取x使鐵皮所圍成的容積最大？ x xa axxav220 dxdv0)2()2()2(22 xaxxa6ax 線性規(guī)劃線性規(guī)劃例1.2 生產(chǎn)計(jì)劃問題 某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，如下表所示。III資源限制設(shè) 備128臺時原料A4016千克原料B0412千克單位產(chǎn)品利潤

3、2元3元問題:工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工廠獲利最多？ 線性規(guī)劃線性規(guī)劃如何用數(shù)學(xué)關(guān)系式描述這個問題？ step1 設(shè)x1 ，x2 分別表示計(jì)劃生產(chǎn) I，II 產(chǎn)品的數(shù)量，稱它們?yōu)闆Q策變量。step2 生產(chǎn)x1 ，x2 的多少，受到資源擁有量的限制，即存在約束條件。 x1 + 2x2 8 4 x1 16 4x2 12生產(chǎn)的產(chǎn)品不能是負(fù)值： x1 ，x2 0。step3 如何安排生產(chǎn)，使得利潤最大，這是目標(biāo)函數(shù)。max z = 2 x1 + 3 x2 線性規(guī)劃線性規(guī)劃因此該問題的數(shù)學(xué)模型為： 設(shè)生產(chǎn)甲產(chǎn)品 x1 個單位、生產(chǎn)乙產(chǎn)品 x2 個單位: 目標(biāo)函數(shù): max z = 2 x1 +

4、 3 x2 約束條件: x1 +2x2 8 4 x1 16 4x2 12 x1 ，x2 0 這種模型實(shí)際上是一種約束限制下的最優(yōu)線性數(shù)學(xué) 模型， 稱為線性規(guī)劃。 線性規(guī)劃線性規(guī)劃例1.3 簡化的環(huán)境保護(hù)問題 靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天500萬立方米，在兩個工廠之間有一條流量為每天200萬立方米的支流。 線性規(guī)劃線性規(guī)劃1.第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，第二化工廠每天排放這種工業(yè)污水1.4萬立方米。2.從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。這兩個工廠都需各自處理一

5、部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是1000元/萬立方米。第二化工廠處理工業(yè)污水的成本是800元/萬立方米。假設(shè)： 線性規(guī)劃線性規(guī)劃設(shè)：第一化工廠每天處理工業(yè)污水量為x1 萬立方米，第二化工廠每天處理工業(yè)污水量為x2 萬立方米?，F(xiàn)在問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個工廠總的處理工業(yè)污水費(fèi)用最小。建模型之前的分析和計(jì)算：(2)2150010000.8(2) (1.4)2127001000 xxx經(jīng)第二工廠前的水質(zhì)要求：經(jīng)第二工廠后的水質(zhì)要求：此問題的線性規(guī)劃模型此問題的線性規(guī)劃模型： 目標(biāo)函數(shù)目標(biāo)函數(shù)：min z = 1000 x1 + 800 x2 約束條件約

6、束條件：s.t. x1 1 0.8x1 + x2 1.6 x1 2 x2 1.4 x1 , x2 0 線性規(guī)劃線性規(guī)劃怎樣辨別一個模型是線性規(guī)劃模型？線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成：其特征是：（1）問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)， 通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性 不等式或等式。 線性規(guī)劃線性規(guī)劃(1) 每一個線性規(guī)劃問題都用一組決策變量 表示某一方案，這組決策變量的值就代表一個具體方案，一般這些變量取值是非負(fù)且連續(xù)的；(2) 存在有關(guān)的數(shù)據(jù)，同決策變量構(gòu)成互不矛盾的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示； (3) 存在一個要求

7、達(dá)到的目標(biāo)，它可用決策變量及其有關(guān)的價值系數(shù)構(gòu)成的的線性函數(shù)(稱為目標(biāo)函數(shù))來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。滿足以上三個條件的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。nx,x ,x21 線性規(guī)劃模型的形式線性規(guī)劃模型的形式數(shù)學(xué)規(guī)劃的一般形式：00)()(. .(min)max12211112121112211nmnmnmmnnnnxx bxaxaxa b xaxaxatsxcxcxcz )21(j 0 )21(i )( Z(min)max 11nxmbxaxcjnjijijnjjj簡寫為： 線性規(guī)劃模型的形式線性規(guī)劃模型的形式數(shù)學(xué)規(guī)劃的一般形式：矩陣形式：) (21ncccC n

8、xxX1 mbbB1其中： 0 )( (min) maxXBAXCXZ mnmnaaaaA1111 線性規(guī)劃模型的形式線性規(guī)劃模型的形式數(shù)學(xué)規(guī)劃的一般形式：向量形式： 0 )( (min) maxXBxpCXzjj) (21ncccC nxxX1 mjjjaaP1 mbbB1其中：線性規(guī)劃模型的形式線性規(guī)劃模型的形式 對于含有兩個決策變量的線性規(guī)劃模型，可以利用圖解法(Graph Method)求解。圖解法是解線性規(guī)劃的一種簡便、直觀的方法，對于理解線性規(guī)劃的基本概念和基本原理也是很有幫助的。定義：可行解：滿足所有約束條件的向量稱為線性規(guī)劃問題的可行解?？尚杏颍喝w可行解的集合稱為線性規(guī)劃問題

9、的可行域。最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解，稱為線性規(guī)劃的最優(yōu)解。圖解法圖解法采用圖解法求解例題1.1：例1.1中，所有約束條件作為半平面所圍成的范圍如圖中陰影部分所示。陰影部分中的每一個點(diǎn)(包括邊界點(diǎn))都是這個線性規(guī)劃問題的可行解。0,1241642232max21212121xxxxxxxxz可行域可行域圖解法圖解法 考察目標(biāo)函數(shù)： max z = 2 x1 + 3 x2 將目標(biāo)函數(shù)化為點(diǎn)斜式坐標(biāo)： x2=-(2/3) x1 +z/3表示一簇平行線33212zxx最優(yōu)解最優(yōu)解q由于在同一條直線上的所有點(diǎn)的目標(biāo)函數(shù)取同樣的值，故稱為等值線。圖解法圖解法 解聯(lián)立方程組: x1 + 2x2

10、= 8 4x1 = 16 得最優(yōu)解為： x1 = 4， x2 = 2， 記為: (x1 , x2)T =(4，2)T或者最優(yōu)目標(biāo)值為： z = 14。 以上最優(yōu)解和最優(yōu)值說明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是：生產(chǎn)4件產(chǎn)品I，生產(chǎn)2件產(chǎn)品II，可得到最大利潤為14元。圖解法圖解法 用圖解法求解線性規(guī)劃的基本步驟：畫可行域：分別取決策變量 x1 ，x2 為坐標(biāo)向量建立直角坐標(biāo)系?；繕?biāo)函數(shù)等值線：對每個不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。 若各半平面交出來的公共區(qū)域存在，顯然，其中的點(diǎn)滿足所有的約束條件，稱這樣的點(diǎn)為此線性規(guī)劃的可行解，全體可行解的集合稱為可行集或

11、可行域。若這樣的公共區(qū)域不存在，則該線性規(guī)劃問題無可行解。找最優(yōu)解：任意給定目標(biāo)函數(shù)一個確定的值，作出對應(yīng)的目標(biāo)函數(shù)等值線，并確定該族等值線平行移動時目標(biāo)函數(shù)值增加的方向。然后平移目標(biāo)函數(shù)的等值線，使其達(dá)到既與可行域有交點(diǎn)又不可能使值再增加的位置(有時交于無窮遠(yuǎn)處，此時稱無有限最優(yōu)解）。此時，目標(biāo)函數(shù)等值線與可行域的交點(diǎn)即此線性規(guī)劃的最優(yōu)解（一個或多個），此目標(biāo)函數(shù)的值即最優(yōu)值。圖解法圖解法 線性規(guī)劃問題的解可能出現(xiàn)的幾種情況：- 有唯一的最優(yōu)解；- 存在無窮多最優(yōu)解(多重最優(yōu)解)；目標(biāo)函數(shù) max z=2 x1 +4 x2 q其最優(yōu)解為線段Q2Q3上的所有點(diǎn)，即(x1 , x2)T| x1

12、+2 x2=8，2 x1 4圖解法圖解法 線性規(guī)劃問題的解可能出現(xiàn)的幾種情況：- 無界解：可行域無邊界，目標(biāo)函數(shù)值可增大(減小)到無窮大(無窮小)，實(shí)際上這類問題無最優(yōu)解；12121212max242,0zxxxxxxx xq 在目標(biāo)函數(shù)等值線向右上方移動的過程中，上端無邊界，取不到最大值，即無界解。圖解法圖解法 線性規(guī)劃問題的解可能出現(xiàn)的幾種情況：- 無可行解：當(dāng)存在矛盾的約束條件時，可行域?yàn)榭占?，無可行解，故無最優(yōu)解。 如果在例1的數(shù)學(xué)模型中 增加一個約束條件: - 2 x1 + x2=4q 可行域的交集為空集，故無可行解。圖解法圖解法 注： 當(dāng)線性規(guī)劃問題的可行域非空時，它是有界的或無界

13、的凸多邊形； 若線性規(guī)劃問題存在最優(yōu)解，則一定在有界可行域的某個頂點(diǎn)得到； 若在兩個頂點(diǎn)同時得到最優(yōu)解，則它們連線上的任意一點(diǎn)都是最優(yōu)解，即有無窮多個最優(yōu)解。圖解法圖解法學(xué)習(xí)要點(diǎn)：1. 通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）2. 作圖的關(guān)鍵有三點(diǎn)：(1) 可行解區(qū)域要畫正確(2) 目標(biāo)函數(shù)增加的方向不能畫錯(3) 目標(biāo)函數(shù)的直線怎樣平行移動數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 以下形式的線性規(guī)劃模型稱為標(biāo)準(zhǔn)形以下形式的線性規(guī)劃模型稱為標(biāo)準(zhǔn)形(M1)： 目標(biāo)函數(shù)目標(biāo)函數(shù)： max z = c1 x1 + c2 x2 + + cn xn 約束條件

14、約束條件： 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.均為均為求最求最大值大值均為等均為等式約束式約束右端常數(shù)右端常數(shù)項(xiàng)項(xiàng)bi 0均為非負(fù)均為非負(fù)決策變量決策變量數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個要求： 目標(biāo)最大化 約束方程為等式 決策變量為非負(fù) 右端項(xiàng)為非負(fù)數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式線性規(guī)劃問題的幾種表示形式： M1: M1(向量表示向量表示):

15、0 maxXBxpCXzjj)21(j 0 )21(i max Z 11nxmbxaxcjnjijijnjjj數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式線性規(guī)劃問題的幾種表示形式： M1: 0 maxXBAXCXZ數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法： 對于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變 換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式: 1.極小化目標(biāo)函數(shù)的問題： 設(shè)目標(biāo)函數(shù)為 min f = c1x1 + c2x2 + + cnxn 令令 z - f ， 則該極小化問題與下面的極大化問題有相同的最優(yōu)解，即 max z = - c1x1 -

16、 c2x2 - - cnxn 。 但必須注意，盡管以上兩個問題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即 min f - max z 。數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法： 2. 約束條件不是等式的問題： 設(shè)約束條件為 ai1 x1 + ai2 x2 + + ain xn bi 可以引進(jìn)一個新的變量 s ，使它等于約束右邊與左邊之差 s = bi (ai1 x1 + ai2 x2 + + ain xn ) 。 顯然，s 也具有非負(fù)約束，即 s0 ，這時新的約束條件成為 ai1 x1 + ai2 x2 + + ain xn

17、+ s = bi 。數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法： 2. 約束條件不是等式的問題： 當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi 時，類似地令 s = (ai1 x1+ai2 x2+ +ain xn) - bi 。 顯然，s 也具有非負(fù)約束，即s0，這時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn - s = bi 。數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法： 2. 約束條件不是等式的問題： 為了使約束由不等式成為等式而引進(jìn)的變量s： 當(dāng)不等

18、式為“小于等于”時稱為“松弛變量松弛變量”； 當(dāng)不等式為“大于等于”時稱為“剩余變量剩余變量”； 如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的變量，有時也將它們統(tǒng)稱為松弛變量。 數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法： 2. 約束條件不是等式的問題： 例1.4 將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式 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

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

20、 x1，x2，x3，x4，x5 0 。數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法： 3. 變量無符號限制的問題： 在標(biāo)準(zhǔn)形式中，必須每一個變量均有非負(fù)約束。當(dāng)某一個變量 xj 沒有非負(fù)約束時，可以令 xj = xj - xj” 其中 xj0， xj”0 即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)然 xj 的符號取決于xj 和 xj” 的大小。數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法： 4.右端項(xiàng)有負(fù)值的問題： 在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個分量非負(fù)。當(dāng)某一個右端項(xiàng)系數(shù)為負(fù)時，如 b

21、i0，則把該等式約束兩端同時乘以-1，得到： - ai1 x1 - ai2 x2 - - ain xn = -bi 數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法： 例1.5 將以下線性規(guī)劃問題轉(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 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1，x3，x4 0數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)

22、劃標(biāo)準(zhǔn)型的方法： 解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換成極大化： 令 z = -f = 3x15x28x3+7x4 ；其次考慮約束，有 3 個不等式約束，引進(jìn) 2 個松弛變量和 1 個剩余變量 x5 , x6 , x7 0 ；由于 x2 無非負(fù)限制，引入兩個非負(fù)變量，可令 x2= x2- x2”, 其中其中 x20，x2”0 ；由于第 3 個約束右端項(xiàng)系數(shù)為 -58，于是把該式兩端乘以 -1 。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題：數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式數(shù)學(xué)規(guī)劃模型的標(biāo)準(zhǔn)形式 化線性規(guī)劃標(biāo)準(zhǔn)型的方法：化線性規(guī)劃標(biāo)準(zhǔn)型的方法： 標(biāo)準(zhǔn)型： max z = 3x1 5x2 + 5x2” 8x3 + 7x

23、4 s. t. 2x1 3x2 + 3x2” + 5x3 + 6x4 + x5 = 28 4x1 + 2x2 - 2x2” + 3x3 - 9x4 - x6 = 39 -6x2+ 6x2” - 2x3 - 3x4 - x7 = 5 x1，x2，x2”，x3，x4，x5，x6，x7 0 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 課堂練習(xí)： 某公司由于生產(chǎn)需要，共需要 A，B 兩種原料至少 350 噸 ( A, B 兩種材料有一定替代性)，其中 A 原料至少購進(jìn) 125 噸。但由于 A，B 兩種原料的規(guī)格不同，各自所需的加工時間也是不同的，加工每噸 A 原料需要 2 個小時，加工每噸 B 原料需要 1 小時，而公

24、司總共有 600 個加工小時。又知道每噸 A 原料的價格為 2 萬元，每噸 B 原料的價格為 3 萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買 A，B 兩種原料，使得購進(jìn)成本最低？數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 課堂練習(xí)： AB總 量加工時間21600原料單價23所需原料數(shù)x1125x2350數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 課堂練習(xí)： 求使購進(jìn)成本最低的 x1 和 x2。 解：問題的線性規(guī)劃模型為 目標(biāo)函數(shù)： min f = 2 x1+3 x2 約束條件： x1+ x2 350 x1 125 2 x1+ x2 600 x1 0 ， x2 0 。數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 用圖解法解此題

25、x1x2600600100100300300 x1 =1252 x1+ x2 = 600 x1+ x2 =350解線性方程組解線性方程組 x1+ x2 =350 2 x1+ x2 = 600得最優(yōu)解得最優(yōu)解 x1 = 250 x2 = 100最優(yōu)值最優(yōu)值 f = 800可行域可行域 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 此例 中的線性規(guī)劃標(biāo)準(zhǔn)型為： 目標(biāo)函數(shù)： 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 。 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃

26、模型 約束條件松弛變量及剩余變量的值原料 A 與原料 B 的總量s1= 0 原料 A 的數(shù)量s2 =125加工時間s3 = 0 線性規(guī)劃解的概念線性規(guī)劃解的概念 考察線性規(guī)劃的標(biāo)準(zhǔn)型： 滿足約束條件(1-2)，(1-3)式的解X=(x1, x2，xn)T，稱為線性規(guī)劃問題的可行解，其中使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解。 11max(1 1),1,2,(1 2)0,1,2,(1 3)njjjnijjijjzc xa xb imxjn 線性規(guī)劃解的概念線性規(guī)劃解的概念 基(矩陣)： 假設(shè)A為m*n階矩陣，A的秩為m（即A為行滿秩矩陣） 等價定義：B為A的m個線性無關(guān)的列向量構(gòu)成的m階方陣，則

27、稱B是線性規(guī)劃問題的一個基，也稱基矩陣。11121212221212A0,(1,2,)(1,2,)mmmmmmmjjBm mBBBaaaaaaBP PPaaaBP jmxjmnm是系數(shù)矩陣 中的階子矩陣，若 非奇異，稱 為線性規(guī)劃問題的基?；仃?中所對應(yīng)的向量，為基向量，為基變量，其余個向量稱為非基變量。 線性規(guī)劃解的概念線性規(guī)劃解的概念 基本解：對于取定的一個基B，在約束方程組中令非基變量取零值，可以得到方程組的一個確定的解，稱這個解為基本解。 基本可行解：當(dāng)基本解的所有分量均非負(fù)時，稱之為基本可行集。 注：基本可行解的幾何意義是可行域的頂點(diǎn)。 可行基：基本可行解對應(yīng)的基稱為可行基。 最優(yōu)基：最優(yōu)解對應(yīng)的基稱為最優(yōu)基。 退化的基本可行解：如果一個基本可行解的某些基變量的值為零，則稱之為退化的基本可行解。 線性規(guī)劃解的概念線性規(guī)劃解的概念