【正文】 第一章 線性規(guī)劃 linear Programming 第一節(jié) 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 第二節(jié) 可行區(qū)域與基本可行解 第三節(jié) 單純形方法 第一節(jié) 線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型 線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用較廣、比較成熟的一個(gè)分支，它是一種合理利用和調(diào)配有限資源的數(shù)學(xué)方法。 線性規(guī)劃研究的問(wèn)題： ?極大化問(wèn)題： 面對(duì)一定的資源，要求充分利用，以獲得最大的經(jīng)濟(jì)效益。 ?極小化問(wèn)題： 給定一項(xiàng)任務(wù)，要求統(tǒng)籌安排，盡量做到用最少的人力、物力資源去完成這一任務(wù) 。 一、實(shí)例： 生產(chǎn)安排問(wèn)題 運(yùn)輸問(wèn)題 二、線性規(guī)劃問(wèn)題的結(jié)構(gòu)特征 線性規(guī)劃問(wèn)題的特征 線性規(guī)劃問(wèn)題的一般形式 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 一般形式向標(biāo)準(zhǔn)形式的轉(zhuǎn)化 本節(jié)內(nèi)容安排 一、實(shí)例 例 1 [生產(chǎn)安排問(wèn)題 ] 某工廠擁有 A、 B、 C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如下表所示： 產(chǎn)品甲 產(chǎn)品乙 設(shè)備時(shí)數(shù) 設(shè)備 A 3 2 65 設(shè)備 B 2 1 40 設(shè)備 C 0 3 75 利潤(rùn)（元 /件） 1500 2500 問(wèn)題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？ 可控因素：生產(chǎn)兩種產(chǎn)品的數(shù)量，設(shè)分別為 x1 , x2，目標(biāo)是生產(chǎn)利潤(rùn)最大，設(shè)生產(chǎn)利潤(rùn)為 z. 利潤(rùn)函數(shù)為 ： 121500 2500z x x??限制條件：三臺(tái)設(shè)備的使用時(shí)間不超過(guò)設(shè)備能力的限制 設(shè)備 A: 3x1+2x2≤65 設(shè)備 B: 2x1+ x2 ≤ 40 設(shè)備 C: 3x2 ≤ 75 蘊(yùn)涵約束：產(chǎn)量為非負(fù) x1?0, x2 ?0 目標(biāo)函數(shù) 約束條件 121212212m a x 1500 25003 2 652 403 750 , 0z x xxxxxxxx????????????? ???生產(chǎn)兩種產(chǎn)品的數(shù)量，設(shè)分別為為 x1,x2，總利潤(rùn)為 z. 在處理產(chǎn)、供、銷的經(jīng)濟(jì)活動(dòng)中，會(huì)經(jīng)常遇到物資調(diào)撥的運(yùn)輸問(wèn)題。如糧棉油、煤炭、鋼鐵、水泥、化肥、木材等物資要由若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷售地。問(wèn)題是，怎樣制定合理的調(diào)運(yùn)方案才能使總運(yùn)輸費(fèi)用最少？這類問(wèn)題稱為運(yùn)輸問(wèn)題 例 2 [運(yùn)輸問(wèn)題 ] 設(shè)要從甲地調(diào)出物資 2022噸，從乙地調(diào)出物資 600噸，從丙地調(diào)出物資 500噸，分別供應(yīng)給 A地 1700噸、 B地1100噸、 C地 200噸、 D地 100噸。已知每噸運(yùn)費(fèi)如下表所示。 假定運(yùn)費(fèi)與運(yùn)量成正比例，問(wèn)怎樣才能找到一個(gè)總運(yùn)費(fèi)最省的調(diào)撥計(jì)劃？ 丙 17 26 38 43 15 37 51 51 乙 15 7 25 21 甲 D C B A 銷地 產(chǎn)地 單位：元 / t x22 x11 x12 x13 x21 x23 x31 x32 x33 x14 x24 x34 問(wèn)題分析： 可控因素： 從三個(gè)產(chǎn)地到四個(gè)銷地的運(yùn)輸量； 目標(biāo)： 總運(yùn)費(fèi)最??； 限制條件：各個(gè)產(chǎn)地的產(chǎn)量和銷地的需求量的限制 。 用 （ i=1,2,3。 j=1,2,3,4） 分別表示從甲乙丙三個(gè)產(chǎn)地運(yùn)往A,B,C,D四個(gè)銷地的物資數(shù)量。 ijx則問(wèn)題歸結(jié)為尋求一組 xij的值，使函數(shù) 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 43 1 3 2 3 3 3 42 1 2 5 7 1 5 5 1 5 1 3 7 1 54 3 3 8 2 6 1 7Z x x x x x x x xx x x x? ? ? ? ? ? ?? ? ? ?達(dá)到最小。并且下面的每一個(gè)約束條件都被滿足 11 12 13 1421 22 23 2431 32 33 3411 21 3112 22 3213 23 3314 24 3420226005001700.11002001000 , 1 , 2 , 3 。 1 , 2 , 3 , 4ijx x x xx x x xx x x xx x xx x xx x xx x xx i j? ? ? ???? ? ? ??? ? ? ? ??? ? ???? ? ??? ? ? ??? ? ???? ? ??m in 3411i j i jijcx???? 1 2 3 4。 1 , 2 , 3i i i i ix x x x a i? ? ? ? ? . 1 2 3 。 1 , 2 , 3 , 4j j j jx x x b j? ? ? ? 0 。 1 , 2 , 3 。 1 , 2 , 3 , 4ijx i j? ? ? 簡(jiǎn)化表達(dá)式 例 某工廠制造 A,B兩種產(chǎn)品，它們的原材料單位消耗，單位利潤(rùn)以及資源現(xiàn)有量如下表 單位 產(chǎn)品 消耗 資源 A B 資源現(xiàn)有量 （噸） 鋼材 煤 2 3 2 1 600 400 單位利潤(rùn) （萬(wàn)元） 20 5 問(wèn)如何組織生產(chǎn)可使工廠獲得最大利潤(rùn)？ 如何建立數(shù)學(xué)模型？ ：設(shè) A， B兩種產(chǎn)品各生產(chǎn) 個(gè)單位； 21, xx：利潤(rùn)函數(shù)是 求它的最大值，即 21 520 xxS ??21 520m a x xxS ??： ???????4 0 026 0 0322121xxxx： 0,021 ?? xx綜合上述各點(diǎn)，該問(wèn)題的數(shù)學(xué)模型如下 ?????????????0,04 0 026 0 032.520m a x21212121xxxxxxtsxxS目標(biāo)函數(shù) 約束條件 非負(fù)限制 注意：目標(biāo)函數(shù)和約束條件中變量的次數(shù)都是一次的，這樣的模型稱為線性規(guī)劃數(shù)學(xué)模型。 二、線性規(guī)劃問(wèn)題的結(jié)構(gòu)特征： 1. 線性規(guī)劃問(wèn)題的特征 ； （ 1）都有一組決策變量。 （ 2）都有一組線性的約束條件，它們是線性等式或不等式。 （ 3）都有一個(gè)確定的目標(biāo)，這個(gè)目標(biāo)可以表示成決策變量的線性函數(shù)，根據(jù)問(wèn)題不同，有的要求實(shí)現(xiàn)極大化，有的要求實(shí)現(xiàn)極小化。 線性規(guī)劃問(wèn)題的本質(zhì)：研究在一組線性約束下，一個(gè)線性函數(shù)的極值問(wèn)題 。 2. 線性規(guī)劃問(wèn)題的一般形式 1 1 2 2m a x( m i n) ... nnz c x c x c x? ? ? ?11 1 12 2 1 121 1 22 2 2 21 1 2 212... ( , )... ( , ).......................................... ( , ), , ..., 0nnnnm m m n n mna x a x a x ba x a x a x ba x a x a x bx x x? ? ? ? ? ???? ? ? ? ? ????? ? ? ? ? ? ????? （ 1） （ 2） （ 3） 一般形式的簡(jiǎn)化表達(dá) 1( , )0nij j ijja x bx?? ? ? ???? ???1m a x ( m i n ) n jjjz c x?? ?m i n..0CXA X bstX????? m a x..0CXA X bstX????? 規(guī)范形式 極小化問(wèn)題 極大化問(wèn)題 3. 線性規(guī)劃的標(biāo)準(zhǔn)形式 1m a x n jjjz c x?? ?10nij j ijja x bx???? ( 1, 2 , ..., )im?( 1, 2,..., )jn?. 標(biāo)準(zhǔn)形式的矩陣表達(dá) m ax0Z CXA X bX???? ?? ???????????????mnmmnnaaaaaaaaaA. . .. . .. . .. . .. . .. . .. . .212222111211???????????????nxxxX?21???????????????mbbbb?21? ?ncccC ?21?標(biāo)準(zhǔn)形式的特點(diǎn) ： (1).目標(biāo)函數(shù)極大化 (2).約束條件全部是等式 (3).所有的變量都是非負(fù)的 (4).約束條件右端常數(shù)為非負(fù)的 4. 一般形式向標(biāo)準(zhǔn)形式的轉(zhuǎn)化 ： (1) 目標(biāo)函數(shù)極大化 對(duì)于極小化的目標(biāo)函數(shù) 可以等價(jià)地轉(zhuǎn)化成求 1njjjz c x???39。1()n jjjz z c x?? ? ? ?? 的極大化 。 (2) 不等式約束化等式約束 對(duì)于 形的不等式，可以在不等式的左邊加上（減去）一個(gè)非負(fù)的變量使不等式化成等式。這樣的變量稱為松弛（剩余）變量。 ()??例如： 1nij jja x b???1nij j ija x s b????1nij jja x b???1nij j ija x s b????(3) 自由變量化非負(fù)變量的 差 自由變量可以用兩個(gè)非負(fù)變量的差代替，例如對(duì)于一個(gè)符號(hào)無(wú)限制的變量 ，可以引進(jìn)兩個(gè)非負(fù)變量