【正文】 假定已求得 (LP)的一個(gè)基本可行解 X(0) ，假設(shè)： 目標(biāo)函數(shù)用非基變量表示的形式。, bm, 0, 1 0 00 1 00 0 1?????????????清華大學(xué)出版社 （ ）式中的 P1,P2, 現(xiàn)在需要解決的問題是： (1) 為了使目標(biāo)函數(shù)逐步變優(yōu)，應(yīng)如何從可行域的一個(gè)頂點(diǎn)轉(zhuǎn)移到可行域的另一個(gè)頂點(diǎn)？ （ 2）目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)值？判斷標(biāo)準(zhǔn)是什么？ 清華大學(xué)出版社 1．確定初始基可行解 從中一般可以直接觀察到存在一個(gè)初始可行基 B = ( P1, P2, 定理 若線性規(guī)劃問題在 k個(gè)頂點(diǎn)上達(dá)到最優(yōu)解 （ k?2），則在這些頂點(diǎn)的凸組合上也達(dá)到最優(yōu)解。 定理 線性規(guī)劃問題的基本可行解對(duì)應(yīng)于可行域的頂點(diǎn)。 清華大學(xué)出版社 定理 若線性規(guī)劃問題存在可行域，則其可行域： D = { X | AX = b , X ? 0 } ，是凸集。 3. 頂點(diǎn)： 假設(shè) K是凸集， X ?K； X若不能用不同的兩個(gè)點(diǎn) X X2 ?K的線性組合表示為： X = ?X1+(1?)X2 ， ( 0 ? 1) 則稱 X為凸集 K的一個(gè)頂點(diǎn)（或稱為極點(diǎn)）。 + ?kXk，則稱 X為由 X1，X2， ?k，且 0 ? ?i ? 1， i = 1,2, 2. 凸組合：設(shè) X1， X2， 清華大學(xué)出版社 三、基本定理 1. 凸集：假設(shè) K是 n維歐氏空間的一個(gè)點(diǎn)集，若對(duì)于 K中的任意兩點(diǎn) X X2，其連線上的所有點(diǎn) ?X1+(1?)X2， ( 0 ? ? ? 1)都在集合 K中，即： ?X1+(1?)X2 ?K ( 0 ? ? ? 1) 則稱K為凸集。 圖解法雖然具有直觀、簡(jiǎn)便等優(yōu)點(diǎn)，但在變量多的情況下，即在多維的情況下，它就無能為力了。 （ 4）若可行域無界，則可能發(fā)生最優(yōu)解無界的情況； （ 5）若可行域是空集，此時(shí)無最優(yōu)解。 若目標(biāo)函數(shù)由 max Z = 2x1 + 4x2 改為 min Z =2 x1 +4 x2 , 則可行解所在的范圍雖然無界，但有最優(yōu)解 x1 = 4， x2 = 0 ，即 (4,0)點(diǎn)。沿箭頭方向移動(dòng)目標(biāo)函數(shù)的等值線，平移等值線直至與可行域 OABCD相切或融合為一條直線，此時(shí)就得到最優(yōu)解為 B點(diǎn)，其坐標(biāo)可通過解方程組得到： 2x1+2x2=14 3x2=15 解得： x1=2 x2=5 這就是本線性規(guī)劃問題的最優(yōu)解。我們以例 1－ 1具體給出求解的方法。一般地講，基本可行解的數(shù)目要小于基本解的數(shù)目，至多相等。 5. 可行基 : 對(duì)應(yīng)于基本可行解的基稱為可行基。 11 1 1 1 1111111: ( )m m nm m nm m m m m m nmnj j j jj j ma a a ax x b x xa a a aP x b P x???? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?????或T 清華大學(xué)出版社 4. 基本可行解 : 滿足非負(fù)條件 ()的基本解稱為基本可行解。 ,xm,0, 假設(shè)前 m 個(gè)變量的系數(shù)列向量是線性無關(guān)的，這時(shí) ()式可改寫為： 現(xiàn)若令 ()式中的非基變量 xm+1= T 清華大學(xué)出版社 為了進(jìn)一步討論線性規(guī)劃問題的解，下面研究約束方程組 ()的求解問題。,m )稱為基向量，與基向量 Pj 相對(duì)應(yīng)的變量 xj ( j = 1,2, 3. 基 : 假設(shè) A 是約束方程組的系數(shù)矩陣，其秩數(shù)為 m ， B是矩陣 A 中由 m 列構(gòu)成的非奇異子矩陣 (B的行列式的值不為 0)，則稱 B 是線性規(guī)劃問題的一個(gè)基。, xn) 稱為線性規(guī)劃問題的可行解；所有可行解的集合稱為可行解集或可行域。現(xiàn)舉例如下： 清華大學(xué)出版社 例 1－ 4 試將如下線性規(guī)劃問題化成標(biāo)準(zhǔn)型 1 2 31 2 31 2 31 2 31 2 3m in 2 37 ( 1 )2 ( 2)3 2 5 ( 3 ), 0 ,Z x x xx x xx x xx x xx x x? ? ? ?? ? ???? ? ???? ? ? ??? ?? 無 限 制 解： 令 x3 = x4 x5 , x4 , x5 ? 0 , (1)式左端加上非負(fù)松弛變量 x6 ； (2)式左端減去非負(fù)剩余變量 x7 , 則可將上述線性規(guī)劃問題化成如下的標(biāo)準(zhǔn)型： 1 2 4 5 6 71 2 4 5 61 2 4 5 71 2 4 51 2 4 7m a x 2 3 3 0 0723 2 2 5, , , , 0Z x x x x x xx x x x xx x x x xx x x xx x x x? ? ? ? ? ? ?? ? ? ? ???? ? ? ? ???? ? ? ? ??? ??清華大學(xué)出版社 第二節(jié) 線性規(guī)劃問題的圖解法及幾何意義 一、線性規(guī)劃問題的解的概念 在討論線性規(guī)劃問題的求解之前，先要了解線性規(guī)劃問題的解的概念。為了便于今后討論，我們規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)型為： 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212m a x( ), , , 0nnnnnnm m m n n mnZ c x c x c xa x a x a x ba x a x a x ba x a x a x bx x x? ? ? ?? ? ? ???? ? ? ?????? ? ? ?????清華大學(xué)出版社 標(biāo)準(zhǔn)型具有如下特點(diǎn)： （ 1）目標(biāo)函數(shù)求最大值； （ 2）所求的變量都要求是非負(fù)的； （ 3）所有的約束條件都是等式； （ 4）常數(shù)項(xiàng)非負(fù)。決策變量有時(shí)有非負(fù)限制，有時(shí)沒有。 清華大學(xué)出版社 二、線性規(guī)劃問題的標(biāo)準(zhǔn)型 由前面所舉的例子可知，線性規(guī)劃問題可能有各種不同的形式。 我們把滿足上述三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型 。 表 1－ 2 A B 汽油 15% 50% 煤油 20％ 30％ 重油 50％ 15％ 其它 15％ 5％ 產(chǎn)品來源 成分 清華大學(xué)出版社 分析：很明顯，該廠可以有多種不同的方案從 A， B兩處采購原油，但最優(yōu)方案應(yīng)是使購買成本最小的一個(gè)，即在滿足供應(yīng)合同單位的前提下，使成本最小的一個(gè)采購方案。 該問題可用如下 數(shù)學(xué)模型表示為： 目標(biāo)函數(shù)： Max Z = 2x1 +3x2 約束條件： 2112123 1 54 1 22 2 1 4,0xxxxxx?????????? ??清華大學(xué)出版社 例 1－ 2 (成本問題 )某煉油廠根據(jù)每季度需供應(yīng)給合同單位汽油 15萬噸、煤油 12萬噸、重油 12萬噸。 在生產(chǎn)管理和經(jīng)濟(jì)活動(dòng)中，經(jīng)常會(huì)遇到線性規(guī)劃問題，如何利用線性規(guī)劃的方法來進(jìn)行分析，下面舉例來加以說明 。 它具有適應(yīng)性強(qiáng) 、 應(yīng)用廣泛 、 計(jì)算技術(shù)比較簡(jiǎn)單的特點(diǎn) ，是現(xiàn)代管理科學(xué)的重要基礎(chǔ)和手段之一 。 特別是在能用計(jì)算機(jī)來處理成千上萬個(gè)約束條件和變量的大規(guī)模線性規(guī)劃問題之后 ， 它的適用領(lǐng)域更加廣泛 。清華大學(xué)出版社 趙立強(qiáng) 清華大學(xué)出版社 第一章 線性規(guī)劃 線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分枝 。 自 1947年美國數(shù)學(xué)家丹捷格 （ ） 提出了求解線性規(guī)劃問題的方法 ——單純形法之后 ， 線性規(guī)劃在理論上趨于成熟 ， 在實(shí)際中的應(yīng)用日益廣泛與深入 。從解決技術(shù)問題中的最優(yōu)化設(shè)計(jì)到工業(yè) 、 農(nóng)業(yè) 、 商業(yè) 、 交通運(yùn)輸業(yè) 、 軍事 、 經(jīng)濟(jì)計(jì)劃與管理 、 決策等各個(gè)領(lǐng)域均可發(fā)揮重要作用；從范圍來看 ， 小到一個(gè)小組的日常工作和計(jì)劃安排 ， 大至整個(gè)部門以致國民經(jīng)濟(jì)計(jì)劃的最優(yōu)方案的提出 ， 都有用武之地 。 清華大學(xué)出版社 第 一 節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型 一、線性規(guī)劃問題的數(shù)學(xué)模型 線性規(guī)劃問題主要解決以下兩類問題： 任務(wù)確定后，如何統(tǒng)籌安排，做到應(yīng)用盡量少的人力和物力資源來完成任務(wù)； 在一定量的人力、物力資源的條件下，如何安排、使用他們，使完成的任務(wù)最多。 清華大學(xué)出版社 例 1－ 1：（計(jì)劃安排問題）某工廠在計(jì)劃期內(nèi)安排生產(chǎn) Ⅰ 、 Ⅱ 兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所占用的設(shè)備 A、 B的臺(tái)時(shí)、原材料的消耗及兩種產(chǎn)品每件可獲利潤見表所示： I II 資源總量 設(shè)備 A(h) 0 3 15 設(shè)備 B(h) 4 0 12 原材料 (公斤 ) 2 2 14 利潤 (元 ) 2 3 問如何安排計(jì)劃使該工廠獲利最多？ 清華大學(xué)出版社 解 : 假設(shè) x x2分別表示在計(jì)劃期內(nèi)生產(chǎn) 產(chǎn)品 I、 II的件數(shù)。該廠計(jì)劃從 A， B兩處運(yùn)回原油提煉，已知兩處的原油成分含量見表 1－ 2；又已知從 A處采購的原油價(jià)格為每噸（包括運(yùn)費(fèi)） 200元， B處采購的原油價(jià)格為每噸（包括運(yùn)費(fèi)）290元 , 問：該煉油廠該如何從 A， B兩處采購原油，在滿足供應(yīng)合同的條件下，使購買成本最小。 解：設(shè)分別表示從 A， B兩處采購的原油量（單位：萬噸），建立的數(shù)學(xué)模型為： 1212121212m in 200 290 5 0 15 0 0 12s . t 0 5 120 , 0S x xxxxxxxxx?????????????? ???清華大學(xué)出版社 以上兩個(gè)例子，從數(shù)學(xué)上來講，我們會(huì)發(fā)現(xiàn)此數(shù)學(xué)模型具有如下特點(diǎn)： (1)有一組非負(fù)的決策變量 (decision or control variable)； (2)有一組約束條件：含有決策變量的線性不等式 ( 或 等 式 ) 組 (linear function constraints)； (3)有一個(gè)含有決策變量的線性目標(biāo)函數(shù)(objective linear function)， 按研究問題的不同 ， 要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化 。 其一般形式如下： 清華大學(xué)出版社 1 1 2 21 1 1 1 2 2 1 12 1 1 2 2 2 2 21 1 2 212( m i n) m a x ( )( , )( , )( )( , ), , , 0 ( ) nnnnnnm m m n n mnZ c x c x c xa x a x a x ba x a x a x ba x a x a x bx x x? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ????? 在該數(shù)學(xué)模型中，方程 ()稱為目標(biāo)函數(shù)； ()稱為約束條件； ()稱為變量的非負(fù)約束條件。目標(biāo)函數(shù)有實(shí)現(xiàn)最大化也有實(shí)現(xiàn)最小化的；約束條件可以是 “ ?” 形式、 “ ?” 形式的不等式，也可以是等式。這種多樣性給討論問題帶來了不便。 綜合以上的討論可以說明任何形式的線性規(guī)劃問題都可以通過上述手段把非標(biāo)準(zhǔn)型的線性規(guī)劃問題化成標(biāo)準(zhǔn)型。由前面討論可知線性規(guī)劃問題的標(biāo)準(zhǔn)型為 ()、 ()、 ()式所示： 1m a x ( 1 . 6 )nj