【正文】 Tm in z c x A x b x b也可寫作 稱 A = (aij) m*n 是約束方程組的系數(shù)矩陣 線性規(guī)劃標(biāo)準(zhǔn)形的 向量形式 記 c = (c1, c2, , )T x = ( x1, x2, 為便于今后討論，我們規(guī)定線性規(guī)劃問題的 標(biāo)準(zhǔn)形 為： 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212..............., , ..., 0nnnnnnm m m n n mnm in z 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? ? ? ?? ? ? ???? ? ? ?????? ? ? ??? ??線性規(guī)劃問題的標(biāo)準(zhǔn)形 bi ? 0 ( i = 1,2, 約束條件可以是“ ? ” 、“ ?”、“ =” 。 怎樣辨別一個(gè)模型是線性規(guī)劃模型？ 從線性規(guī)劃數(shù)學(xué)模型的一般形式看 線性規(guī)劃問題可能有各種不同的形式。這些產(chǎn)品分別要在 A、 B、 C、 D四種不同的設(shè)備上加工。由于數(shù)字電 子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如 MPSX， OPHEIE， UMPIRE等，可以很方便地求解幾千個(gè)變量的線 性規(guī)劃問題。 現(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。 線性規(guī)劃的發(fā)展 1984年美國貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家 卡馬卡提出 解線 性規(guī)劃問題的 新的多項(xiàng)式時(shí)間算法 。 線性規(guī)劃的發(fā)展 50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大 批新的算法。 ? 1947年美國數(shù)學(xué)家 ,開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。 ? 1939年蘇聯(lián)數(shù)學(xué)家 康托羅維奇 在 《 生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法 》 一書中 提出線性規(guī)劃問題 ，也未引起重視。? 線性規(guī)劃的簡(jiǎn)介和應(yīng)用舉例 ? 線性規(guī)劃的數(shù)學(xué)模型和圖解法 ? 線性規(guī)劃的基本概念和基本性質(zhì) ? 單純形法 ? 關(guān)于單純形法的說明和補(bǔ)充 ? 線性規(guī)劃的對(duì)偶理論與對(duì)偶單純形法 第 5章 線性規(guī)劃 ? 線性規(guī)劃就是一個(gè)線性函數(shù)在線性等式或不等式約束條件下的極值問題， 是最簡(jiǎn)單的約束優(yōu)化問題 ? 理論最為成熟、應(yīng)用最為廣泛的一種數(shù)學(xué)規(guī)劃方法 ? 運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支 ? 廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營管理和工程技術(shù)等方面 ? 為合理地利用有限的人力、物力、財(cái)力等資源作出最優(yōu)決策，提供科學(xué)的依據(jù)。 線性規(guī)劃的概述 ? 法國數(shù)學(xué)家傅里葉和瓦萊 普森分別于 1832和 1911年獨(dú)立地提出線性規(guī)劃的想法，但未引起注意。 ? 1947年美國數(shù)學(xué)家 線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問題的通用方法 單純形法 ，為這門學(xué)科奠定了基礎(chǔ)。 ? 1951年美國經(jīng)濟(jì)學(xué)家 域 ，為此與康托羅維奇一起獲 1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。例如 ? 1954年， ? 1954年， 和 等人 解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題 ? 1956年， ? 1960年 和 等 1979年蘇聯(lián)數(shù)學(xué)家 哈奇揚(yáng)提出 解線性規(guī)劃問題的 橢球算 法 ，并證明它是多項(xiàng)式時(shí)間算法。用這種方法求解線性規(guī) 劃問題在變量個(gè)數(shù)為 5000時(shí)只要單純形法所用時(shí)間的 1/50。 線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問題包括 整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。 線性規(guī)劃的發(fā)展 線性規(guī)劃通常解決下列兩類問題： (1) 當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最 少的資源 (如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等 )去 完成確定的任務(wù)或目標(biāo) (2) 在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好 的經(jīng)濟(jì)效益 (如產(chǎn)品量最多 、利潤最大 ) 線性規(guī)劃問題的數(shù)學(xué)模型 例 某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品。按工藝資料規(guī)定，單件 產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示，企業(yè)決 策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤最大？ 設(shè) 備 產(chǎn) 品 A B C D 利潤 (元 ) 甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 臺(tái) 時(shí) 12 8 16 12 線性規(guī)劃問題的應(yīng)用 ? 解： 設(shè) x x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為： 線性規(guī)劃問題的應(yīng)用 121212121223. . 2 2 12284 164 12,0m ax z x xs t x xxxxxxx?????????目標(biāo)函數(shù)： 約束條件： 線性規(guī)劃數(shù)學(xué)模型的一般形式 ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ??? ??1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212( ) ... ( 1 )... ( , )... ( , )... ( 2 )... ( , ), , ..., 0nnnnnnm m m n n mnm in m ax z 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線性規(guī)劃問題的數(shù)學(xué)模型 目標(biāo)函數(shù)： 約束條件： ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ??? ??1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212( ) ... ( 1 )... ( , )... ( , )... ( 2 )... ( , ), , ..., 0nnnnnnm m m n n mnm in m ax z 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線性規(guī)劃問題的數(shù)學(xué)模型 線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成 決策變量 Decision variables 目標(biāo)函數(shù) Objective function 約束條件 Constraints 目標(biāo)函數(shù)： 約束條件： ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ??? ??1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212( ) ...... ( , )... ( , )...... ( , ), , ..., 0nnnnnnm m m n n mnm in m ax z 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線性規(guī)劃問題的數(shù)學(xué)模型 其特征是： (1) 問題的目標(biāo)函數(shù)是多個(gè)決策變量的 線性 函數(shù)，通常是求最大值或最小值； (2) 問題的約束條件是一組多個(gè)決策變量的 線性 不等式或等式。 目標(biāo)函數(shù)有實(shí)現(xiàn)最大化也有實(shí)現(xiàn)最小化的 。 決策變量有時(shí)有非負(fù)限制有時(shí)沒有。, m) 線性規(guī)劃標(biāo)準(zhǔn)形的 矩陣形式 記 c = (c1, c2, , xn )T b = (b1, b2, , )T, x = ( x1, x2, , bm )T Pj = ( a1j, a2j, , n 線性規(guī)劃的標(biāo)準(zhǔn)形的其它形式 ???????????1( 0 )..0Tnjjjm in z c xP x b bstx1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212..............., , ..., 0nnnnnnm m m n n mnm in z 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? ? ? ?? ? ? ???? ? ? ?????? ? ? ??? ??線性規(guī)劃標(biāo)準(zhǔn)形的 向量形式 記 c = (c1, c2, , xn )T b = (b1, b2, , ain ) i = 1, 2, , m 線性規(guī)劃的標(biāo)準(zhǔn)形的其它形式 ?? ? ?????, 1 , 2, ..., ( 0 )..0Ti i im in z c xA x b i m bstx1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212..............., , ..., 0nnnnnnm m m n n mnm in z 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ù) ,分別表示約束條件的個(gè)數(shù)和決策變量的個(gè)數(shù) , 具體問題的線性規(guī)劃數(shù)學(xué)模型是各式各樣的 ,需要把它們化 成標(biāo)準(zhǔn)型 ,并借助于標(biāo)準(zhǔn)型的求解方法進(jìn)行求解。 線性規(guī)劃的標(biāo)準(zhǔn)形 ???????( 0 )..0Tm in z c xA x b bstx為價(jià)值向量 , 為決策向量 , b為右端向量， 為已知常數(shù)。令 zˊ= z, 于是得到： min zˊ= cTx. 目標(biāo)函數(shù)的轉(zhuǎn)換 若約束方程組為不等式 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式 ? ?ijij bxa稱為松弛變量 相應(yīng)的松弛變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)取值為 0。 把原 “ ? ” 形的不等式變?yōu)榈仁?。 約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式 ? ?ijij bxa稱為剩余變量 相應(yīng)的剩余變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)取值為 0。現(xiàn)舉例如下： 如何化成標(biāo)準(zhǔn)形 1 2 4 5 6 71 2 4 5 61 2 4 5 71 2 4 51 2 72 3 3 0 0723 2 2 5, , ..., 0m in z x x x x x xx x x x xx x x x xx x x xx x x? ? ? ? ? ? ?? ? ? ? ???? ? ? ? ???? ? ? ? ??? ??解：令 x3= x4x5 , x4,x5?0 , (1)式左端加上非負(fù)松弛變量 x6 , (2)式左端減去非負(fù)剩余變量 x7 , 則可將上述線性規(guī)劃問題化成如下的標(biāo)準(zhǔn)形 : 如何化成標(biāo)準(zhǔn)形 例 2: 化為標(biāo)準(zhǔn)形。x3+0 x5+0 線性規(guī)劃的圖解法 線性規(guī)劃的基本概念 ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ??? ??1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 212( ) ... ( 1 )... ( , )... ( , )... ( 2 )... ( , ), , ..., 0nnnnnnm m m n n mnm in m ax z 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線性規(guī)劃的圖解法 線性規(guī)劃的基本概念 可行解 (Feasible Solution)任一滿足約束條件的一組決策變量的數(shù)值； 目標(biāo)函數(shù)等值線 (Objective functon line)位于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值。 ????????? ? ???121212121212m ax 2. . 0