【正文】 6005001700.11002001000 , 1 , 2 , 3 。 j=1,2,3,4） 分別表示從甲乙丙三個(gè)產(chǎn)地運(yùn)往A,B,C,D四個(gè)銷地的物資數(shù)量。 假定運(yùn)費(fèi)與運(yù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 問題分析： 可控因素： 從三個(gè)產(chǎn)地到四個(gè)銷地的運(yùn)輸量； 目標(biāo)： 總運(yùn)費(fèi)最?。? 限制條件：各個(gè)產(chǎn)地的產(chǎn)量和銷地的需求量的限制 。問題是，怎樣制定合理的調(diào)運(yùn)方案才能使總運(yùn)輸費(fèi)用最少？這類問題稱為運(yùn)輸問題 例 2 [運(yùn)輸問題 ] 設(shè)要從甲地調(diào)出物資 2022噸，從乙地調(diào)出物資 600噸，從丙地調(diào)出物資 500噸，分別供應(yīng)給 A地 1700噸、 B地1100噸、 C地 200噸、 D地 100噸。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎ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 利潤（元 /件） 1500 2500 問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？ 可控因素：生產(chǎn)兩種產(chǎn)品的數(shù)量，設(shè)分別為 x1 , x2，目標(biāo)是生產(chǎn)利潤最大，設(shè)生產(chǎn)利潤為 z. 利潤函數(shù)為 ： 121500 2500z x x??限制條件：三臺(tái)設(shè)備的使用時(shí)間不超過設(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，總利潤為 z. 在處理產(chǎn)、供、銷的經(jīng)濟(jì)活動(dòng)中，會(huì)經(jīng)常遇到物資調(diào)撥的運(yùn)輸問題。 ?極小化問題： 給定一項(xiàng)任務(wù)，要求統(tǒng)籌安排，盡量做到用最少的人力、物力資源去完成這一任務(wù) 。第一章 線性規(guī)劃 linear Programming 第一節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型 第二節(jié) 可行區(qū)域與基本可行解 第三節(jié) 單純形方法 第一節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型 線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用較廣、比較成熟的一個(gè)分支，它是一種合理利用和調(diào)配有限資源的數(shù)學(xué)方法。 線性規(guī)劃研究的問題： ?極大化問題： 面對(duì)一定的資源，要求充分利用，以獲得最大的經(jīng)濟(jì)效益。 一、實(shí)例： 生產(chǎn)安排問題 運(yùn)輸問題 二、線性規(guī)劃問題的結(jié)構(gòu)特征 線性規(guī)劃問題的特征 線性規(guī)劃問題的一般形式 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 一般形式向標(biāo)準(zhǔn)形式的轉(zhuǎn)化 本節(jié)內(nèi)容安排 一、實(shí)例 例 1 [生產(chǎn)安排問題 ] 某工廠擁有 A、 B、 C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。如糧棉油、煤炭、鋼鐵、水泥、化肥、木材等物資要由若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷售地。已知每噸運(yùn)費(fèi)如下表所示。 用 （ i=1,2,3。 ijx則問題歸結(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á)到最小。 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 , 3 , 4j j j jx x x b j? ? ? ? 0 。 1 , 2 , 3 , 4ijx i j? ? ? 簡化表達(dá)式 例 某工廠制造 A,B兩種產(chǎn)品，它們的原材料單位消耗，單位利潤以及資源現(xiàn)有量如下表 單位 產(chǎn)品 消耗 資源 A B 資源現(xiàn)有量 （噸） 鋼材 煤 2 3 2 1 600 400 單位利潤 （萬元） 20 5 問如何組織生產(chǎn)可使工廠獲得最大利潤？ 如何建立數(shù)學(xué)模型？ ：設(shè) A， B兩種產(chǎn)品各生產(chǎn) 個(gè)單位； 21, xx：利潤函數(shù)是 求它的最大值，即 21 520 xxS ??21 520m a x xxS ??： ???????4 0 026 0 0322121xxxx： 0,021 ?? xx綜合上述各點(diǎn)，該問題的數(shù)學(xué)模型如下 ?????????????0,04 0 026 0 032.520m a x21212121xxxxxxtsxxS目標(biāo)函數(shù) 約束條件 非負(fù)限制 注意：目標(biāo)函數(shù)和約束條件中變量的次數(shù)都是一次的，這樣的模型稱為線性規(guī)劃數(shù)學(xué)模型。 （ 2）都有一組線性的約束條件，它們是線性等式或不等式。 線性規(guī)劃問題的本質(zhì)：研究在一組線性約束下，一個(gè)線性函數(shù)的極值問題 。1()n jjjz z c x?? ? ? ?? 的極大化 。這樣的變量稱為松弛（剩余）變量。0 , 0jjxx??39。 例 將下列 LP問題化成標(biāo)準(zhǔn)形式 121212121m in222250z x xxxxxxxx? ? ?? ? ??????. 39。 1 2 239。1 2 2 439。1 2 2 3 4 5m a x ( )2 ( ) 22( ) 2( ) 5, , , , , 0z x x xx x x xx x x xx x x xx x x x x x? ? ?? ? ? ? ?? ? ? ?? ? ? ??. 先化變量和目標(biāo)函數(shù) 調(diào)整約束條件 調(diào)整目標(biāo)函數(shù) 作業(yè)： 、乙兩種產(chǎn)品，每件甲產(chǎn)品的利潤是 2元，乙產(chǎn)品的利潤是 4元。車間現(xiàn)有勞動(dòng)力總數(shù)是 32個(gè)。問應(yīng)該安排甲、乙兩種產(chǎn)品各生產(chǎn)多少件才能獲得最大總利潤？（列出數(shù)學(xué)模型并化成標(biāo)準(zhǔn)形式） 第二節(jié) 單純形法原理 一、幾個(gè)概念 二、兩變量 LP問題的圖解法 三、可行區(qū)域的幾何結(jié)構(gòu) 四、基可行解及線性規(guī)劃的基本定理 可行解： 任何一組滿足所有約束條件的決策變量值 稱為 LP問題的一個(gè)可行解。 最優(yōu)值： 最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值。 }0,{ ??? xbAxxD一、幾個(gè)概念 ： 二、兩變量 LP問題的圖解法 圖解法是根據(jù)平面直角坐標(biāo)系和二元一次方程（不等式）的特點(diǎn)設(shè)計(jì)的。 1x 2x（ 2） 將約束條件在直角坐標(biāo)系中表示，并找出可行域。 （ 4）確定出問題的最優(yōu)解。 例 1 用圖解法解下列線性規(guī)劃問題 1212122 4 8 03 2 6 000xxxxxx??????12m a x 60 50Z x x?? 40B(10,15)C(0,20)A(20,0)O(0,0)Z=0Z=1350x1x23x1+2x2=602x1+4x2=80最優(yōu)解 x*=(10,15)T, 最優(yōu)值 z*=60?10+50?15=1350. 例 2 用圖解法解線性規(guī)劃問題 Max z=x1+x2 . 2x1 x2 ≥ 2 x1 2x2 ≤ 2 x1+ x2 ≤ 5 x1 ≥0, x2 ≥0 2x1x2=2x12x2=2x1+x2=5Z=0Z=Z=3OA4A3A2A1最優(yōu)解 x*=(1,4)T, 最優(yōu)值 z*=1+4=3. 例 3 用圖解法求解線性規(guī)劃問題 Min z=4x12x2 . 2x1x2 ≥ 2 x1 2x2 ≤ 2 x1+x2 ≤ 5 x1 ≥0, x2 ≥0 最優(yōu)解不唯一（ A1A2連線上的所有點(diǎn)都是最優(yōu)解），最優(yōu)值 z*=4. Z=4x12x2=2x1+x2=5O A4A3A2A1Z=0Z=2例 4 用圖解法解線性規(guī)劃問題 Min z=2x1+x2 . x1+x2 ≥ 1 x1 3x2 ≥ 3 x1 ≥0， x2 ≥0 OX13x2=3X1+x2=1ABZ=0Z=3x1x2可行域無界， 原問題最優(yōu)解無界 。 ? 可行域存在 ， 則一定是一個(gè)凸多邊形 。 ?最優(yōu)解存在且唯一 ， 則一定在頂點(diǎn)上達(dá)到 。 X(1)?S, X(2)?S的連線可表示為： ?X(1)+ (1 ? )X(2)?S, (0? ? ?1)。 1. 凸集及性質(zhì) 頂點(diǎn) ： 設(shè) S是凸集， X?S；