【正文】 解： 令 x3 = x4 x5 , x4 , x5 ? 0 , (1)式左端加上非負(fù)松 弛變量 x6 , (2)式左端減去非負(fù)剩余變量 x7 , 則可將上 述線性規(guī)劃問題化成如下的標(biāo)準(zhǔn)型 : ??????????????????????????????0,5223270033272154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxZM a x????????????)(),2,1(0)(),2,1(1njxnjbxajnjjjij??1. 可行解 : 滿足約束條件 (),()的解 X = ( x1, x2, x4+0 max Z=2x1+3x2 2x1+2x2 ≤12 x1+2x2≤8 4x2≤12 4x1 ≤16 x1, x2≥0 解：引進 4個新的非負(fù)變量x3,x4,x5,x6使不等式變?yōu)榈仁?，?biāo)準(zhǔn)型為： Max Z=2x1+3x2+0 上述的標(biāo)準(zhǔn)型具有如下特點： （ 1）目標(biāo)函數(shù)求最大值； （ 2）所求的變量都要求是非負(fù)的； （ 3）所有的約束條件都是等式； （ 4）常數(shù)項非負(fù) 綜合以上的討論可以說明任何形式的線性規(guī)劃問題都可以通過上述手續(xù)把非標(biāo)準(zhǔn)型式的線性規(guī)劃問題化成標(biāo)準(zhǔn)型。相應(yīng)的松弛變量或剩余變量在目標(biāo)函數(shù)中的價值系數(shù)取值為 0。把原 “ ? ” 形的不等式變?yōu)榈仁?。 2. 若約束方程組為不等式。 1. 若要求目標(biāo)函數(shù)實現(xiàn)最小化時 . 即此時的目標(biāo)函數(shù)是 : Min Z = CTX , 這時只需要將目標(biāo)函數(shù)的最小值變換為求目標(biāo)函數(shù)的最大值 ,即 Min Z = Max ( Z) 。, n ) 為已知常數(shù)。 我們稱 A 為約束方程組的系數(shù)矩陣 ( m n階 ),一般情況下 m n , m , n 為正整數(shù) ,分別表示約束條件的個數(shù)和決策變量的個數(shù) , C 為價值向量 , X 為決策向量 , 通常 aij , bi , cj ( i = 1, 2, , 0 )T , ( j = 1, 2, , Pn ) ， Pj = ( a1j, a2j, , xn )T ， b = ( b1, b2, 用矩陣向量描述就是： ??????0)(XbAXXCZM a x T 其中： C = ( c1, c2, 為了便于今后討論，我們規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)型為： ??????????????????????????0,)(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcZM ax??????? 這里我們假設(shè) bi ? 0 ( i = 1,2,決策變量有時有非負(fù)限制有時沒有。目標(biāo)函數(shù)有實現(xiàn)最大化也有實現(xiàn)最小化的 。因此，需要介紹一種代數(shù)方法 ——單純型法，為了以后介紹方便討論，需要研究一下線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)化問題。 上述理論具有普遍意義，對于兩個以上變量的線性規(guī)劃問題都成立。 X1 =159? X2 =+? (0? ? ? 1) X= = ? +(1? ) maxZ=1200 X1 6 15 X2 12 無界 無有限最優(yōu)解 若目標(biāo)函數(shù)由 Max Z = 2x1 + 4x2 改為 Min Z =2 x1 +4 x2 ,則可行解所在的范圍雖然無界 ,但有最優(yōu)解 x1 = 4，x2 = 0 ,即 (4,0)點 . 例 maxZ=2X1+ 4X2 2X1+X2 ?8 2X1+X2 ? 2 X1 , X2 ?0 Z=0 2X1+ X2=8 2X1+ X2=2 8 2 4 6 X2 4 0 X1 例 maxZ=3X1+2X2 X1 X2 ?1 X1 , X2 ?0 無解 無可行解 1 X2 1 X1 0 通過圖解法可以看出： （ 1）線性規(guī)劃的所有可行解構(gòu)成的可行域一般是凸多邊形，有些可行域是無界的； （ 2）若存在最優(yōu)解，則一定在可行域的某頂點得到； （ 3）若在兩個頂點上同時得到最優(yōu)解，則在這兩點的連線上的任一點都是最優(yōu)解。 最優(yōu)值等于 2600 0 Z= 40 X1 + 80X2 =0 X1 + 2X2 =30 D A B C X2 X1 求解最優(yōu)解： BC線段 B點 C點 X(1)=(6,12) X(2)=(15,) X=? X(1)+(1?) X(2) (0? ? ? 1) 例 maxZ=40X1+ 80X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 X1 =6?+ +(1 ? ) MAX Z=4x1+3x2 . 2x1+2x2 ≤1600 5 x1+ ≤ 2500 x1 ≤ 400 x1,x2≥0 由約束條件得到可行域 OABCD。紅虛線為目標(biāo)函數(shù) Z=2x1+3x2的 等值線。 MAX Z=2x1+3x2 . 2x1+2x2 ≤12 x1+2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1， x2≥0 x1+2x2=8 解得： x1=4 4x1=16 x2=2 這就是本線性規(guī)劃問題的最優(yōu)解。我們可以由例 1具體給出求解的方法。()稱為約束條件。 ????????????????????????????????0,),()(),(),()()(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcZM axM i n???????其一般形式為 ()和 ()形式。 (3) 都有一個目標(biāo)要求 ,并且這個目標(biāo)可表示為這組決策 變量的線性函數(shù) (稱為目標(biāo)函數(shù) ),按研究問題的不同 ,要 求目標(biāo)函數(shù)實現(xiàn)最大化或最小化。 , xn)表示某一 方案 ,這組未知數(shù)的值就代表一個具體的方案 ,通常要求這些未知數(shù)取值是非負(fù)的?，F(xiàn)采用套裁的辦法，設(shè)計五種方案，如表 。 例 1： 某工廠在計劃期內(nèi)安排生產(chǎn) Ⅰ 、 Ⅱ 兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時、 A、 B兩種原材料的消耗及兩種產(chǎn)品每件可獲利潤見如下表所示： 問如何安排計劃使該工廠獲利最多？ I II 資源總量 設(shè) 備 A 1臺時 2臺時 8 臺時 設(shè) 備 B 2臺時 2臺時 12 臺時 原材料 A 4公斤 0公斤 16公斤 原材料 B 0公斤 4公斤 12公斤 利 潤 2元 /件 3元 /件 解： 假設(shè) x x2分別表示在計劃期內(nèi)生產(chǎn)產(chǎn)品 I、 II的數(shù) 量，則該計劃問題可用如下數(shù)學(xué)模型表示為： 目標(biāo)函數(shù) Max Z = 2x1 +3x2 約束條件 ????????????????0,12416482122221212121xxxxxxxx例 2 某汽車廠生產(chǎn)大轎車和載重汽車 ， 所需資源 、資源可用量和產(chǎn)品價格如下表所示 : 大轎車 載重汽車 可用量 鋼材 （ 噸 ） 2 2 1600 工時 (小時 ) 5 2500 大轎車座椅 400（ 輛 ） 獲利 (千元 /輛 ) 4 3 問應(yīng)如何組織生產(chǎn)才能使工廠獲利最大？ 例 2的數(shù)學(xué)模型 21 34m a x xxz ??1 6 0 022 21 ?? xx2 5 0 21 ?? xx1x02 ?x. , 4 0 01 ?x例 3 下料問題 ? 某工廠要做 100套鋼架，每套有長 、 ，已知原料長 米，問應(yīng)如何下料使需用的原材料最省。 線性規(guī)劃研究的問題主要有兩類： 任務(wù)確定后，如何統(tǒng)籌安排，盡量做到用盡量少的人力和物力資源來完成任務(wù)； 有一定量的人力、物力資源，如何安排使用他們，使完成的任務(wù)（創(chuàng)造的利潤）最多。它具有適應(yīng)性強、應(yīng)用廣泛、計算技術(shù)比較簡單的特點，是現(xiàn)代管理科學(xué)的重要基礎(chǔ)和手段之一。特別是在能用計算機來處理成千上萬個約束條件和變量的大規(guī)模線性規(guī)劃問題之后，它的適用領(lǐng)域更廣泛了。,)()(0,2,1 ,2,1 . m i n ),(.,)4(111122111 1?????????????????????????? ???? ?最優(yōu)化的分類圖 離散規(guī)劃 整數(shù)規(guī)劃 非線性最小二乘 球面規(guī)劃 非線性等式 最優(yōu)化 連續(xù)優(yōu)化 離散優(yōu)化 有約束 無約束 線性規(guī)劃 不可微分規(guī)劃 非線性規(guī)劃 網(wǎng)絡(luò)規(guī)劃 隨機規(guī)劃 參考書 盧向華，等著 《 運籌學(xué)教程 》 ，高等教育出版社 錢頌迪， 《 運籌學(xué) 》 ，清華大學(xué)出版社 林同曾， 《 運籌學(xué) 》 ，機械工業(yè)出版社 胡運權(quán)， 《 運籌學(xué)教程 》 ，清華大學(xué)出版社 第 一章 線 性 規(guī) 劃 第 一 節(jié) 線性規(guī)劃模型及其圖解法 線性規(guī)劃是運籌學(xué)的一個重要分枝。各倉庫到市場的總加權(quán)試確定倉庫的位置，使個倉庫的容量為個倉庫，第現(xiàn)規(guī)劃對某種貨物的需求量為）個市場的位置為（個市場，第設(shè)有選址問題d i jwwyyxxbyaxddwnjqwmicwtsdwjiwjidiyxCimqbajnmnmmjijiijijijjmiijinjijminjijijijijiiijjj,。這時模型就是以的度量，可采用：關(guān)于則問題的模型為：的貨物單位數(shù)量。 題。這是一個多目標(biāo)規(guī)劃問?????????????????0. m i n ,4