第一章線性規(guī)劃與單純形法

1、 運籌學(xué)C陳克東上海工程技術(shù)大學(xué)上海工程技術(shù)大學(xué)管理學(xué)院管理學(xué)院 “ 一門科學(xué)只有成功的應(yīng)用數(shù)學(xué)時，才算達(dá)到了完善的地步 ” - 馬克思運籌學(xué)的發(fā)展：三個來源 v 軍 事v 管 理v 經(jīng) 濟(jì) 運籌學(xué)思想方法的起源可追溯到古代u我國先秦時期諸子著作中就存在許多樸素的運籌思想. u孫子兵法中有豐富的運籌思想. 軍事起源u在國外, 運籌學(xué)思想也可追溯到很早以前. 如阿基米德、達(dá)芬奇、伽利略等都研究過作戰(zhàn)問題軍事起源 二戰(zhàn)期間u1939年, 由英國曼徹斯特大學(xué)物理學(xué)家、英國戰(zhàn)斗機(jī)司令部科學(xué)顧問、戰(zhàn)后獲得諾貝爾獎的布萊凱特(P.M.S.Blackett)為首, 組建了一個代號為“Blackett馬戲團(tuán)”

2、的研究小組, 專門就改進(jìn)防空系統(tǒng)進(jìn)行研究u二戰(zhàn)中, 除英國外, 美國、加拿大等國也相繼成立了軍事運籌研究小組,解決戰(zhàn)爭中提出的運籌學(xué)課題. 其中最著名的工作之一是改進(jìn)深水炸彈的起爆深度.軍事起源資料 當(dāng)時德國的潛水艇嚴(yán)重威脅盟軍的運輸船, 1942年, 美國大西洋艦隊主持反潛戰(zhàn)的官員貝克(W.D.Baker)請求成立反潛戰(zhàn)運籌組, 麻省理工學(xué)院的物理學(xué)家莫爾斯(P. W.Morse)被請來擔(dān)任計劃與監(jiān)督. 莫爾斯領(lǐng)導(dǎo)的小組經(jīng)過多方實地調(diào)查, 提出兩條重要建議： 1. 將反潛攻擊由反潛艦艇投擲水雷改為由飛機(jī)投擲深水炸彈; 僅當(dāng)潛艇浮出水面或剛下潛時, 方投擲深水炸彈; 深水炸彈的定深(指起爆深度

3、)由100-200英尺, 修正為20-50英尺.2. 改進(jìn)運送物資的船隊及護(hù)航艦艇編隊的方式, 由小規(guī)模多批次, 改進(jìn)為加大規(guī)模、減少批次, 可使損失減少，軍方采用了上述建議, 重創(chuàng)德國潛艇艦隊, 最終成功地打破了德國的海上封鎖. 軍事起源戰(zhàn)爭結(jié)束時, 英美及加拿大軍隊中工作的運籌學(xué)工作者已超過了700人. 正是由于戰(zhàn)爭需要的促進(jìn), 以及大批著名科學(xué)家的參與, 運籌學(xué)得到迅速發(fā)展. 之后, 運籌學(xué)從單純軍事和戰(zhàn)爭中的應(yīng)用研究, 擴(kuò)展到經(jīng)濟(jì)和管理領(lǐng)域, 并形成了自己的理論與方法. 1948年, 美國麻省理工學(xué)院（MIT）率先開設(shè)了運籌學(xué)課程, 許多大學(xué)群起效法, 內(nèi)容也日益豐富。軍事起源1951

4、年, 莫爾斯和金博爾出版了(1946年內(nèi)部出版, 1951年公開出版)第一本運籌學(xué)專著:運籌學(xué)的方法(The Methods of Operations Research). 書中總結(jié)了第二次世界大戰(zhàn)中運籌學(xué)的軍事應(yīng)用, 并給出了運籌學(xué)的一個著名定義運籌學(xué) 是為執(zhí)行部門對它們控制下的“業(yè)務(wù)”活 動采取決策提供定量依據(jù)的科學(xué)方法.管理起源第一次世界大戰(zhàn)前就已經(jīng)發(fā)展成熟的古典管理學(xué)派, 對運籌學(xué)的產(chǎn)生和發(fā)展影響很大。1911年, 泰勒出版了著名的科學(xué)管理原理一書. 書中, 泰勒的管理思想和理論, 概括起來主要有以下三個觀點：科學(xué)管理的根本目的是謀求最高工作效率。 達(dá)到最高工作效率的重要手段是科學(xué)的

5、管理方法。 實施科學(xué)管理要求精神上的徹底變革。根據(jù)以上觀點泰勒提出管理制度: 最佳動作原理; 合理的日工作量或恰當(dāng)?shù)墓ぷ鞫~原理; 刺激性付酬制度等.與泰勒同時代的, 對管理改革作出貢獻(xiàn)的還有一些學(xué)者亨利甘特 甘特的貢獻(xiàn)主要有以下幾點：p提出了一種“工資任務(wù)加獎金”的工資制度p1903年, 發(fā)明了“甘特圖”. 至今還在實踐中使用, 并發(fā)展為統(tǒng)籌方法p強(qiáng)調(diào)管理民主和重視人的領(lǐng)導(dǎo)方式管理起源管理起源弗蘭克杰爾布雷斯夫婦.有影響的著作有:動作研究(1911年)、科學(xué)管理入門(1912年)以及疲勞研究(1916年)等. 他們的研究比泰勒的研究更為細(xì)致和廣泛, 其重要貢獻(xiàn)在以下幾方面：p 提出動作研究和

6、動作經(jīng)濟(jì)原理p疲勞研究. p注意到了工作、工人和環(huán)境之間的相互影響.愛爾朗（Erlong）的排隊論公式19091920年間，丹麥哥本哈根電話公司工程師愛爾朗陸續(xù)發(fā)表了關(guān)于電話通路數(shù)量等方面的分析與計算公式。尤其是1909年的論文“概率與電話通話理論”，開創(chuàng)了運籌學(xué)的重要分支排隊論。管理起源帶有擁擠效應(yīng)的服務(wù)行業(yè)如通訊業(yè)、交通運輸業(yè)等都隱含排隊論的問題。經(jīng)濟(jì)起源經(jīng)濟(jì)學(xué)理論對運籌學(xué)的影響是和數(shù)理經(jīng)濟(jì)學(xué)學(xué)派緊密聯(lián)系的數(shù)理經(jīng)濟(jì)學(xué)對運籌學(xué), 特別是對線性規(guī)劃的影響可以從魁奈(Qusnay)1758年發(fā)表的經(jīng)濟(jì)表算起. 最著名的經(jīng)濟(jì)學(xué)家沃爾拉斯(Walras)研究了經(jīng)濟(jì)平衡問題, 后來的經(jīng)濟(jì)學(xué)家對其數(shù)學(xué)形

7、式繼續(xù)研究并得到深入發(fā)展. 1928年 馮.諾伊曼以研究二人零和對策的一系列論文為“對策論”奠基. 1932年, 又提出了廣義經(jīng)濟(jì)平衡模型. 1939年, 蘇聯(lián)的康托洛維奇發(fā)表生產(chǎn)組織和計劃中的數(shù)學(xué)方法.這些工作都可以看作是運籌學(xué)的先驅(qū)工作發(fā)展二戰(zhàn)結(jié)束后, 運籌學(xué)很快深入到工業(yè)、商業(yè)、政府部門等, 并得到了迅速發(fā)展；運籌學(xué)在中國研究及應(yīng)用從20世紀(jì)50年代中期開始。1957年, 我國在建筑業(yè)和紡織業(yè)中首先應(yīng)用運籌學(xué). 1958年, 開始在交通運輸、工業(yè)、農(nóng)業(yè)、水利建設(shè)、郵電等方面陸續(xù)得到推廣應(yīng)用20世紀(jì)60年代起, 在鋼鐵和石油部門得到了比較全面、深入的應(yīng)用1965年起統(tǒng)籌法在建筑業(yè)、大型設(shè)備

8、維修計劃等方面的應(yīng)用取得可喜的進(jìn)展. 1970年在全國大部分省、市和部門推廣優(yōu)選法70年代中期, 最優(yōu)化方法在工程設(shè)計界受到了廣泛的重視, 并在許多方面取得成果; 排隊論開始應(yīng)用于礦山、港口、電信及計算機(jī)設(shè)計等方面; 圖論用于線路布置、計算機(jī)設(shè)計、化學(xué)物品的存放等70年代后期, 存儲論在應(yīng)用汽車工業(yè)等方面獲得成功近年來, 運籌學(xué)已趨向研究和解決規(guī)模更大、更復(fù)雜的問題, 并與系統(tǒng)工程緊密結(jié)合.來歷及定義 二戰(zhàn)期間, 英國為了研究“如何最好地運用空軍及新發(fā)明的雷達(dá)保護(hù)國家”, 成立了一個由各方面專家組成的交叉學(xué)科小組.這就是最早的運籌學(xué)小組, 它的任務(wù)是進(jìn)行“作戰(zhàn)研究”(Operational R

9、esearch). 后來, 美國從事這方面研究的科學(xué)家又稱之為“ Operations Research”, 簡稱為 O.R. O.R.的中文譯名“運籌學(xué)”取自成語“運籌帷幄之中，決勝千里之外”，具有運用籌劃，出謀獻(xiàn)策，以策略取勝等內(nèi)涵。目前國外的管理科學(xué)（Management Science）與運籌學(xué)的內(nèi)容基本相同運籌學(xué)是一門應(yīng)用科學(xué), 它廣泛地應(yīng)用現(xiàn)有科學(xué)技術(shù)知識 和數(shù)學(xué)方法, 解決實際中提出的專門問題, 為決策者選擇最優(yōu)決策提供定量的依據(jù).運籌學(xué)發(fā)展三階段：運籌學(xué)發(fā)展三階段：創(chuàng)建時期（創(chuàng)建時期（45年至年至50年代初）年代初）1948年年 英國成立英國成立“運籌學(xué)運籌學(xué)”俱樂部俱樂部19

10、48年年 麻省理工學(xué)院麻省理工學(xué)院 介紹運籌學(xué)介紹運籌學(xué)1950年年 伯明翰大學(xué)開設(shè)運籌學(xué)課程伯明翰大學(xué)開設(shè)運籌學(xué)課程1952年年 卡斯大學(xué)卡斯大學(xué) 設(shè)立運籌學(xué)碩士和博士學(xué)位設(shè)立運籌學(xué)碩士和博士學(xué)位1947年年 丹捷格丹捷格 提出單純形法提出單純形法50年代初年代初 計算機(jī)求解線性規(guī)劃獲得成功計算機(jī)求解線性規(guī)劃獲得成功成長時期（成長時期（50年代初至年代初至50年代末）年代末）多個國家成立運籌學(xué)會，多種運籌學(xué)刊物問世多個國家成立運籌學(xué)會，多種運籌學(xué)刊物問世1957年年 在牛津大學(xué)召開第一次國際運籌學(xué)會議在牛津大學(xué)召開第一次國際運籌學(xué)會議1959年年 成立國際運籌學(xué)聯(lián)合會成立國際運籌學(xué)聯(lián)合會迅速

11、發(fā)展時期（迅速發(fā)展時期（60年代以來）年代以來）運籌學(xué)進(jìn)一步分為各個分支，更多運籌學(xué)出版物運籌學(xué)進(jìn)一步分為各個分支，更多運籌學(xué)出版物運籌學(xué)課程納入教學(xué)計劃運籌學(xué)課程納入教學(xué)計劃我國運籌學(xué)發(fā)展歷程：我國運籌學(xué)發(fā)展歷程：1956年年 運籌學(xué)小組運籌學(xué)小組1958年年 運籌學(xué)研究室運籌學(xué)研究室1960年年 應(yīng)用運籌學(xué)經(jīng)驗交流會議應(yīng)用運籌學(xué)經(jīng)驗交流會議1962年年 全國運籌學(xué)專業(yè)學(xué)術(shù)會議全國運籌學(xué)專業(yè)學(xué)術(shù)會議1978年年 全國運籌學(xué)專業(yè)學(xué)術(shù)會議全國運籌學(xué)專業(yè)學(xué)術(shù)會議1980年年 成立中國運籌學(xué)學(xué)會成立中國運籌學(xué)學(xué)會運籌學(xué)分支運籌學(xué)是一門以決策支持為目標(biāo)的學(xué)科，運籌學(xué)的內(nèi)容豐富，應(yīng)用范圍非常之廣，從軍事

12、、政治到管理、經(jīng)濟(jì)及工程技術(shù)等許多領(lǐng)域都能應(yīng)用到運籌學(xué)的思想和方法。經(jīng)過半個世紀(jì)左右的發(fā)展，運籌學(xué)形成了下面主要幾個分支在這過程中，科學(xué)家，學(xué)者和工程師 都起了很大的作用，在其它很多領(lǐng)域也是這樣的！運籌學(xué)的分支:線性規(guī)劃（線性規(guī)劃（linear programminglinear programming）整數(shù)規(guī)劃（整數(shù)規(guī)劃（integer programming integer programming ）運輸問題運輸問題 （ transportation Problems transportation Problems ）多目標(biāo)規(guī)劃（多目標(biāo)規(guī)劃（multiobjective programmi

13、ng multiobjective programming ）圖論與網(wǎng)絡(luò)分析（圖論與網(wǎng)絡(luò)分析（graph theory and network analysisgraph theory and network analysis）非線性規(guī)劃（非線性規(guī)劃（nonlinear programmingnonlinear programming）動態(tài)規(guī)劃（動態(tài)規(guī)劃（dynamic programmingdynamic programming）對策論（對策論（game theorygame theory）決策論（決策論（decision theorydecision theory）排隊論（排隊論（queu

14、eing theoryqueueing theory）存貯論（存貯論（inventory theoryinventory theory）運籌學(xué)的作用運營管理：生產(chǎn)計劃，項目進(jìn)度和物資供應(yīng)計劃物流管理：倉貯控制，配送中心選址，配送運輸調(diào)度財務(wù)和投資管理：資金流分析，債務(wù)鏈清償，證券組合選擇，商品套利和套期，資產(chǎn)定價人力資源管理：調(diào)薪方案，人力資源分配質(zhì)量管理：服務(wù)系統(tǒng)分析市場分析：市場占有率轉(zhuǎn)移分析和模擬社會系統(tǒng)分析：交通管理，社會保障系統(tǒng)分析，人口發(fā)展分析.隨著科學(xué)技術(shù)和生產(chǎn)的發(fā)展，運籌學(xué)已滲入很多領(lǐng)域里，發(fā)揮了越來越重要的作用。運籌學(xué)本身也在不斷發(fā)展，現(xiàn)在已經(jīng)是一個包括好幾個分支的數(shù)學(xué)部門了

15、。比如：數(shù)學(xué)規(guī)劃（又包含線性規(guī)劃；非線性規(guī)劃；整數(shù)規(guī)劃；組合規(guī)劃等）、圖論、網(wǎng)絡(luò)流、決策分析、排隊論、可靠性數(shù)學(xué)理論、庫存論、對策論、搜索論、模擬等等。 運籌學(xué)有廣闊的應(yīng)用領(lǐng)域，它已滲透到諸如服務(wù)、庫存、搜索、人口、對抗、控制、時間表、資源分配、廠址定位、能源、設(shè)計、生產(chǎn)、可靠性、等各個方面。 運籌學(xué)是軟科學(xué)中“硬度”較大的一門學(xué)科，兼有邏輯的數(shù)學(xué)和數(shù)學(xué)的邏輯的性質(zhì)，是系統(tǒng)工程學(xué)和現(xiàn)代管理科學(xué)中的一種基礎(chǔ)理論和不可缺少的方法、手段和工具。運籌學(xué)已被應(yīng)用到各種管理工程中，在現(xiàn)代化建設(shè)中發(fā)揮著重要作用。 本課程的要求和說明目目 的：的：通過學(xué)習(xí)該課程，應(yīng)了解管理運籌學(xué)對優(yōu)化決策問題進(jìn)行定量研究通過

16、學(xué)習(xí)該課程，應(yīng)了解管理運籌學(xué)對優(yōu)化決策問題進(jìn)行定量研究的特點的特點, ,理解理解 線性規(guī)劃、整數(shù)規(guī)劃、運輸問題線性規(guī)劃、整數(shù)規(guī)劃、運輸問題 、目標(biāo)規(guī)劃，圖與網(wǎng)絡(luò)等分支、目標(biāo)規(guī)劃，圖與網(wǎng)絡(luò)等分支的基本優(yōu)化原理，掌握其中常用的模型和算法的基本優(yōu)化原理，掌握其中常用的模型和算法, ,具有一定的建模能力。具有一定的建模能力。先修課程先修課程: : 線性代數(shù)，高等數(shù)學(xué)線性代數(shù)，高等數(shù)學(xué) 等等. .要要 求求：課前預(yù)習(xí)，課后要復(fù)習(xí)課前預(yù)習(xí)，課后要復(fù)習(xí) 課堂認(rèn)真聽講（不能曠課）課堂認(rèn)真聽講（不能曠課）( (每曠課一次平時成績扣每曠課一次平時成績扣1010分分) ) 認(rèn)真完成作業(yè)認(rèn)真完成作業(yè)成成 績：績： 平

17、時成績平時成績 30% 30% （作業(yè)、出勤、課堂紀(jì)律、實驗報告）（作業(yè)、出勤、課堂紀(jì)律、實驗報告） + +考試成績考試成績 70%70%答疑時間：答疑時間：每次課后時間，周五下午（行政樓每次課后時間，周五下午（行政樓619 619 ）參考書目：參考書目：運籌學(xué)教程（第二版胡運權(quán) 清華大學(xué)出版社 運籌學(xué)運籌學(xué)趙可培趙可培, ,上海財經(jīng)大學(xué)出版社上海財經(jīng)大學(xué)出版社 管理運籌學(xué)管理運籌學(xué)謝家平謝家平, , 中國人民大學(xué)出版社中國人民大學(xué)出版社 復(fù)習(xí)線性代數(shù)內(nèi)容復(fù)習(xí)線性代數(shù)內(nèi)容: :列向量列向量 x=(x1，x2，xn）T為n維列向量。xRn行向量行向量 x=(x1，x2，xn）為n維列向量。xRn

18、矩陣矩陣( (向量向量) )運算規(guī)則運算規(guī)則 加減乘、求逆運算 結(jié)合律 分配律 交換律 乘法無交換律乘法無交換律線性相關(guān)線性相關(guān) 一組向量v1,vn,如果有一組不全為零的 系數(shù)1, ,n,使得: 1 v1+nvn=0 則稱v1,vn 是線性相關(guān)的.線性無關(guān)線性無關(guān) 一組向量v1,vn,如果對于任何數(shù)1,n, 若要滿足: 1 v1+nvn=0 ,則必有系數(shù) 1=n=0,(全為零)則稱v1,vn線性無關(guān). 矩陣矩陣A A的秩的秩 設(shè)A為一個mn階矩陣(mn)若矩陣中最大線性 無關(guān)列向量個數(shù)為k,則稱矩陣A的秩為k,記 為rank(A)=k.Chapter 1線性規(guī)劃與單純形法 Linear pro

19、gramming and the simplex method上海工程技術(shù)大學(xué)上海工程技術(shù)大學(xué)管理學(xué)院管理學(xué)院Chapter 1 線性規(guī)劃與單純形法 線性規(guī)劃線性規(guī)劃是用線性數(shù)學(xué)模型表示不同的生產(chǎn)活動、營銷活動、是用線性數(shù)學(xué)模型表示不同的生產(chǎn)活動、營銷活動、金融活動或其他活動的計劃。金融活動或其他活動的計劃。 本章重點1、根據(jù)實際問題寫出線性規(guī)劃模型2、掌握線性規(guī)劃化標(biāo)準(zhǔn)型的方法3、理解并掌握線性規(guī)劃解的概念4、能夠用圖解法求解線性規(guī)劃問題5、熟練掌握線性規(guī)劃單純形法的基本思想和 步驟難點難點線性規(guī)劃（Linear Programming,縮寫為LP）是運籌學(xué)的重要分支之一，在實際中應(yīng)用得較廣

20、泛，其方法也較成熟，借助計算機(jī)，使得計算更方便，應(yīng)用領(lǐng)域更廣泛和深入。 線性規(guī)劃通常研究資源的最優(yōu)利用、設(shè)備最佳運行等問題。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源 （如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多 、利潤最大）。Chapter 1 線性規(guī)劃與單純形法 1 1 線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃數(shù)學(xué)模型1.11.1問題的提出問題的提出 線性規(guī)劃應(yīng)用的問題種類繁多，形式各線性規(guī)劃應(yīng)用的問題種類繁多，形式各異，主要分為四類線性規(guī)劃問題。前三類問題分異，主要分為四類線性規(guī)劃問題。前

21、三類問題分別是資源分配問題，成本效益問題以及網(wǎng)絡(luò)配送別是資源分配問題，成本效益問題以及網(wǎng)絡(luò)配送問題。第四類具有兩種以上的約束的線性規(guī)劃問問題。第四類具有兩種以上的約束的線性規(guī)劃問題。題。 Chapter 1 線性規(guī)劃與單純形法 某工廠近期要安排生產(chǎn)甲、乙兩種產(chǎn)品，某工廠近期要安排生產(chǎn)甲、乙兩種產(chǎn)品，產(chǎn)品甲需要用原料產(chǎn)品甲需要用原料A A，產(chǎn)品乙需要用原料，產(chǎn)品乙需要用原料B B，由于兩種產(chǎn)品都在一個設(shè)備上生產(chǎn)，由于兩種產(chǎn)品都在一個設(shè)備上生產(chǎn)， 且設(shè)且設(shè)備使用時間有限，管理者必須合理安排兩備使用時間有限，管理者必須合理安排兩種產(chǎn)品的產(chǎn)量，使得在資源有限的條件下種產(chǎn)品的產(chǎn)量，使得在資源有限的條件下

22、獲得最大的利潤。獲得最大的利潤。舉例因此這個問題的決策目標(biāo)是收益的最大化，因此這個問題的決策目標(biāo)是收益的最大化， 研究者根據(jù)這個目標(biāo)需要收集以下相關(guān)數(shù)研究者根據(jù)這個目標(biāo)需要收集以下相關(guān)數(shù)據(jù)：據(jù)： 1)1)工廠兩種原料存量以及可用設(shè)備工時工廠兩種原料存量以及可用設(shè)備工時數(shù)；數(shù)； 2)2)甲、乙兩種產(chǎn)品的單位產(chǎn)品需要的原甲、乙兩種產(chǎn)品的單位產(chǎn)品需要的原料和設(shè)備工時數(shù)；料和設(shè)備工時數(shù)； 3) 3)甲、乙兩種產(chǎn)品的單位產(chǎn)品利潤。甲、乙兩種產(chǎn)品的單位產(chǎn)品利潤。Chapter 1 線性規(guī)劃與單純形法 甲甲 乙乙資源限資源限制制原料原料A106原料原料B028設(shè)備設(shè)備2318單位利潤單位利潤(百萬百萬)43

23、舉例這些數(shù)據(jù)可以通過調(diào)研或估算得出，這些數(shù)據(jù)可以通過調(diào)研或估算得出，如表如表1.1所示：所示：建立數(shù)學(xué)模型為建立模型，引入變量如下：為建立模型，引入變量如下：x x1 1-產(chǎn)品甲的數(shù)量產(chǎn)品甲的數(shù)量x x2 2-產(chǎn)品乙的數(shù)量產(chǎn)品乙的數(shù)量Z -Z -利潤利潤由表由表1.11.1最后一行知最后一行知Z Z4x4x1 1+3x+3x2 2建立數(shù)學(xué)模型目標(biāo)是如何確定目標(biāo)是如何確定x x1 1和和x x2 2，使得利潤，使得利潤Z Z最大最大, ,同同時需要滿足資源約束。對于原料時需要滿足資源約束。對于原料A A和原料和原料B B，有：有：x x1 166，2x2x2 288對于設(shè)備工時，有：對于設(shè)備工時

24、，有：2x2x1 1+3x+3x2 21818此外，甲、乙兩種產(chǎn)品數(shù)量不可能是負(fù)值，此外，甲、乙兩種產(chǎn)品數(shù)量不可能是負(fù)值，因此，有如下對變量的非負(fù)約束：因此，有如下對變量的非負(fù)約束：x x1 1 0 , x 0 , x2 200于是，問題的數(shù)學(xué)模型現(xiàn)在可以用代數(shù)式表述如下：于是，問題的數(shù)學(xué)模型現(xiàn)在可以用代數(shù)式表述如下：滿足：滿足：12121212maxZ43x6 (1.1)28(1.2)2318(1.3),0(1.4)xxxxxx x原材料限制原材料限制設(shè)備限制實際上這是求一個線性函數(shù)在一組線性約實際上這是求一個線性函數(shù)在一組線性約束條件下的最大值問題，稱之為線性規(guī)劃束條件下的最大值問題，稱之

25、為線性規(guī)劃問題模型。問題模型。以上模型中，將以上模型中，將x x1 1、x x2 2稱為稱為決策變量決策變量； Z Z4x4x1 1+3x+3x2 2為為目標(biāo)函數(shù)目標(biāo)函數(shù)；約束；約束(1.1)(1.1)(1.3)(1.3) 為為函數(shù)約束函數(shù)約束；(1.4)(1.4)為為非負(fù)約束非負(fù)約束。 Chapter 1 線性規(guī)劃與單純形法 從以上過程我們可以歸納出根據(jù)實際從以上過程我們可以歸納出根據(jù)實際 問題建立線性規(guī)劃模型的步驟：問題建立線性規(guī)劃模型的步驟：1) 1) 根據(jù)管理層的要求確定決策目標(biāo)和收集根據(jù)管理層的要求確定決策目標(biāo)和收集相關(guān)數(shù)據(jù)。相關(guān)數(shù)據(jù)。2) 2) 確定要做出的決策，引入決策變量。確定

26、要做出的決策，引入決策變量。3) 3) 確定對這些決策的約束條件和目標(biāo)函數(shù)。確定對這些決策的約束條件和目標(biāo)函數(shù)。Chapter 1 線性規(guī)劃與單純形法 例例1.21.2 成本效益平衡問題成本效益平衡問題某飼料公司希望用玉米、紅薯作原料配制某飼料公司希望用玉米、紅薯作原料配制一種混合飼料，各種原料包含的營養(yǎng)成分一種混合飼料，各種原料包含的營養(yǎng)成分和采購成本都不同，公司管理層希望能夠和采購成本都不同，公司管理層希望能夠確定混合飼料中的各種原料數(shù)量，使得飼確定混合飼料中的各種原料數(shù)量，使得飼料能夠以最低成本達(dá)到一定的營養(yǎng)要求。料能夠以最低成本達(dá)到一定的營養(yǎng)要求。研究者根據(jù)這一目標(biāo)收集到的有關(guān)數(shù)據(jù)如研

27、究者根據(jù)這一目標(biāo)收集到的有關(guān)數(shù)據(jù)如下（見表下（見表1.21.2）舉例表1.2 營養(yǎng)成分營養(yǎng)成分每公斤玉每公斤玉米米每公斤每公斤紅薯紅薯每公斤最每公斤最低要求低要求碳水化合物碳水化合物8420蛋白質(zhì)蛋白質(zhì)3618維他命維他命1516采購成本采購成本（元（元/公斤）公斤）0.80.5舉例為建立線性規(guī)劃模型，我們引入變量如下：為建立線性規(guī)劃模型，我們引入變量如下：x x1 1= =混合飼料中的玉米數(shù)量；混合飼料中的玉米數(shù)量；x x2 2= =混合飼料中紅薯的數(shù)量；混合飼料中紅薯的數(shù)量；目標(biāo)函數(shù)目標(biāo)函數(shù) Z=0.8xZ=0.8x1 1+0.5x+0.5x2 2，表示產(chǎn)量的成本，表示產(chǎn)量的成本函數(shù)函數(shù).

28、 . 即如何確定即如何確定x x1 1， x x2 2 使得成本使得成本Z=0.8xZ=0.8x1 1+0.5x+0.5x2 2 最低且滿足最低營養(yǎng)要求最低且滿足最低營養(yǎng)要求的約束，的約束，Chapter 1 線性規(guī)劃與單純形法 因此這個問題的線性規(guī)劃模型為：因此這個問題的線性規(guī)劃模型為：其中其中“s.t.”是是“subject to”的縮寫，意思的縮寫，意思是是“受約束于受約束于”。12121212min0.80.58x4203x618s.tx51601,2iZxxxxxxi碳水化合物要求蛋白質(zhì)物要求維他命物要求Chapter 1 線性規(guī)劃與單純形法 某物流公司需要將甲、乙、丙三個工廠某物流

29、公司需要將甲、乙、丙三個工廠生產(chǎn)的一種新產(chǎn)品送到生產(chǎn)的一種新產(chǎn)品送到 A A、B B 兩個倉庫，甲、兩個倉庫，甲、乙兩個工廠的產(chǎn)品可以通過鐵路運送到倉庫乙兩個工廠的產(chǎn)品可以通過鐵路運送到倉庫A A，數(shù)量不限；丙工廠的產(chǎn)品可以通過鐵路運送到數(shù)量不限；丙工廠的產(chǎn)品可以通過鐵路運送到倉庫倉庫B B，同樣，產(chǎn)品數(shù)量不限。，同樣，產(chǎn)品數(shù)量不限。 由于鐵路運輸由于鐵路運輸成本較高，公司也可以考慮由獨立的卡車來運成本較高，公司也可以考慮由獨立的卡車來運輸，可將多達(dá)輸，可將多達(dá)8080個單位的產(chǎn)品由甲、乙、丙三個單位的產(chǎn)品由甲、乙、丙三個工廠運到一個配送中心，再從配送中心以最個工廠運到一個配送中心，再從配送中

30、心以最多多9090單位的載貨量運到各個倉庫。公司管理層單位的載貨量運到各個倉庫。公司管理層希望以最小的成本運送所需的貨物。希望以最小的成本運送所需的貨物。 舉例Chapter 1 線性規(guī)劃與單純形法 配送配送中心中心倉庫倉庫A倉庫倉庫B運輸量運輸量工廠甲工廠甲$3.0$7.5- 100工廠乙工廠乙$3.5$8.2- 80工廠丙工廠丙$3.4-$9.2 70配送中配送中心心-$2.3$2.3 需求量需求量-120130 250舉例首先，需要收集每條線路上的單位運輸成本和各工廠首先，需要收集每條線路上的單位運輸成本和各工廠產(chǎn)品的產(chǎn)量以及各倉庫分配量等數(shù)據(jù)，如表產(chǎn)品的產(chǎn)量以及各倉庫分配量等數(shù)據(jù)，如表

31、1.3所示。所示。為了更清楚地說明問題，我們用網(wǎng)絡(luò)圖來為了更清楚地說明問題，我們用網(wǎng)絡(luò)圖來直觀表示該配送問題。見圖直觀表示該配送問題。見圖1.11.1 其中其中 ，v v1 1、v v2 2、v v3 3 表示甲、乙、丙三個表示甲、乙、丙三個工廠，節(jié)點工廠，節(jié)點v v4 4表示配送中心，節(jié)點表示配送中心，節(jié)點v v5 5、v v6 6表表示兩個倉庫；每一條箭線表示一條可能的示兩個倉庫；每一條箭線表示一條可能的運輸線路，并給出了相應(yīng)的單位運輸成本，運輸線路，并給出了相應(yīng)的單位運輸成本，對運輸量有限制的路線的最大運輸能力也對運輸量有限制的路線的最大運輸能力也同時給出。同時給出。$8.2$2.390

32、$2.390$9.280$3.480$3.5生產(chǎn)10080$3$7.5v1v5v2v3 v4 v6生產(chǎn)80生產(chǎn)70130倉庫B120倉庫A圖圖1.1配送中心 我們要解決的是各條線路最大運輸量，引我們要解決的是各條線路最大運輸量，引入變量入變量 x xij ij 表示由表示由 v vi i 經(jīng)過路線經(jīng)過路線 (v(vi i， v vj j ) ) 運輸?shù)竭\輸?shù)?v vj j 的產(chǎn)品數(shù)。的產(chǎn)品數(shù)。 問題的目標(biāo)是總運問題的目標(biāo)是總運輸成本最小化，總運輸成本可以表示為：輸成本最小化，總運輸成本可以表示為： 總運輸成本總運輸成本 = 7.5x= 7.5x1515+3 x+3 x1414+8.2x+8.2

33、x2525+3.5 +3.5 x x2424+2.3 x+2.3 x4545+3.4 x+3.4 x3434+2.3x+2.3x4646+9.2 x+9.2 x3636 數(shù)學(xué)模型1514252445244636151425243436142434454615254546361424344546min7.538.23.52.33.42.39.21008070s.t.12013080,80,80,90,900ijZxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx從以上的幾個例子可以看出，線性規(guī)劃問題有從以上的幾個例子可以看出，線性規(guī)劃問題有如下共同如下共同特征特征： （模型的三要素）（

34、模型的三要素） 每一個問題都用一組決策變量每一個問題都用一組決策變量( (x x1 1，x x2 2，x xn n) ) 表示某一表示某一方案；這組決策變量的值就代表一個具體方案。一般這些方案；這組決策變量的值就代表一個具體方案。一般這些變量取值都是非負(fù)的。變量取值都是非負(fù)的。 存在一定的約束條件，這些約束條件可以用一組線性等式存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示?；蚓€性不等式來表示。 都有一個要求達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)（都有一個要求達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)（稱為目標(biāo)函數(shù)）來表示。按問題的不同，要求目標(biāo)函數(shù)實稱為目標(biāo)函數(shù)）來表示。按問題

35、的不同，要求目標(biāo)函數(shù)實現(xiàn)最大化或最小化?，F(xiàn)最大化或最小化。例2 某工廠用鋼與橡膠生產(chǎn)3種產(chǎn)品A、B、C，有關(guān)資料如下表404524332231 A B C單位產(chǎn)品利潤單位產(chǎn)品橡膠量單位產(chǎn)品鋼消耗量產(chǎn)品已知每天可獲得100單位的鋼和120單位橡膠，問每天生產(chǎn)A、B、C各多少使總利潤最大？練習(xí)解解：設(shè)x1，x2， x3分別為A、B、C日產(chǎn)量，則有 約束條件 2 x1 + 3x2 + x3 100 3x1 + 3x2 + 2x3 120 x10，x20， x30因此，線性規(guī)劃模型為 目標(biāo)函數(shù)： max z=40 x1+45x2 +24x3123123123max40452423100s.t. 332

36、1200, 1,2,3iZxxxxxxxxxxiChapter 1 線性規(guī)劃與單純形法 根據(jù)上節(jié)分析，線性規(guī)劃的一般形式為：根據(jù)上節(jié)分析，線性規(guī)劃的一般形式為：1 12211 11221121 1222221 12212max(min) Z= + +,s.t. ,0nnnnnnmmmnnmnc xc xc xa xa xa xba xa xa xba xaxaxbx xx 決策變量向量：決策變量向量：X X=(=(x x1 1，x x2 2，x xn n) )T T價值向量：價值向量：C C=(=(c c1 1，c c2 2，c cn n) )T T資源向量：資源向量：b b=(=(b b1

37、1，b b2 2，b bm m) )T T系數(shù)矩陣系數(shù)矩陣A=（aij）mn =mnmmnnaaaaaaaaa 212222111211為了討論和制定統(tǒng)一的算法，引入線性規(guī)劃的標(biāo)準(zhǔn)形式本教材規(guī)定的標(biāo)準(zhǔn)形式為本教材規(guī)定的標(biāo)準(zhǔn)形式為：(1) 目標(biāo)函數(shù)要求是目標(biāo)函數(shù)要求是max; (有的要求有的要求min) (2) 約束條件的要求是等式約束條件的要求是等式; (3) 決策變量的要求是非負(fù)約束決策變量的要求是非負(fù)約束; (4) 在標(biāo)準(zhǔn)型式中規(guī)定各約束條件的右端項在標(biāo)準(zhǔn)型式中規(guī)定各約束條件的右端項bi0，否則等式兩端乘以否則等式兩端乘以“-1”。 即標(biāo)準(zhǔn)形式為：1 12211 11221121 1222

38、221 12212max Z= + +,0nnnnnnmmmnnmnc xc xc xa xa xa xba xa xa xba xaxaxbx xxChapter 1 線性規(guī)劃與單純形法 用向量和矩陣符號表述時為：用向量和矩陣符號表述時為：1max z=CXs.t.0,1,2,njjjjP xbxjn),(21ncccC12nxxXx12jjjmjaaPa12mbbbb用矩陣描述時為：用矩陣描述時為：其中：其中：11121121200,;00nnmmmnaaaAP PPaaa maxb 0ZCXAXXChapter 1 線性規(guī)劃與單純形法稱稱A A為約束條件的為約束條件的m mn n維系數(shù)矩

39、陣，維系數(shù)矩陣，一般一般m0;m0;b b為資源向量；為資源向量；C C為價值向量；為價值向量；X X為決策變量向量。為決策變量向量。下面討論化標(biāo)準(zhǔn)型的方法：下面討論化標(biāo)準(zhǔn)型的方法：如何把一般的線如何把一般的線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)型性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)型（1 1）若要求目標(biāo)函數(shù)實現(xiàn)最小化，即）若要求目標(biāo)函數(shù)實現(xiàn)最小化，即min min z=CXz=CX。這時只需將目標(biāo)函數(shù)最小化變換求目。這時只需將目標(biāo)函數(shù)最小化變換求目標(biāo)函數(shù)最大化，即令標(biāo)函數(shù)最大化，即令 z=-zz=-z，于是得到，于是得到max max z= z= CXCX。這就同標(biāo)準(zhǔn)型的目標(biāo)函數(shù)的形。這就同標(biāo)準(zhǔn)型的目標(biāo)函數(shù)的形式一致了。式一致了。

40、MinZ=CXZ=-Z（2 2）約束方程為不等式。這里有兩種情況：）約束方程為不等式。這里有兩種情況：一種是約束方程為一種是約束方程為不等式，則可在不等式，則可在不等式的左端加入不等式的左端加入非負(fù)非負(fù)松弛變量松弛變量 x xj j，把原把原不等式變?yōu)榈仁剑徊坏仁阶優(yōu)榈仁剑?另一種是約束方程為另一種是約束方程為不等式，則可不等式，則可在在不等式的左端減去一個非負(fù)剩余不等式的左端減去一個非負(fù)剩余變量變量x xk k（也可稱松弛變量），把不等式約束（也可稱松弛變量），把不等式約束條件變?yōu)榈仁郊s束條件。條件變?yōu)榈仁郊s束條件。（3 3）若變量約束中：）若變量約束中： x xi i 0,0,則令則令x

41、xi i= = x xi i 得到得到 x xi i00； 若若x xj j取值無約束取值無約束, ,則令則令 x xj j = x= xj j x xj j, ,得得 x xj j, x, xj j0, 0, 用用 x xj j，x xj j代替代替 x xj j后得到線性規(guī)劃的變量約束為非負(fù)約束。后得到線性規(guī)劃的變量約束為非負(fù)約束。（4 4）目標(biāo)函數(shù)中加上）目標(biāo)函數(shù)中加上 0 x0 xi i ( (松弛變量松弛變量) )Chapter 1 線性規(guī)劃與單純形法 加入松弛變量12121212max2328416s.t.412,0Zxxxxxxxx：12345123142512345max230

42、0028416s.t.412,0Zxxxxxxxxxxxxx x x x xChapter 1 線性規(guī)劃與單純形法 123123123123123min2372s.t.325,0, zxxxxxxxxxxxxx xx取值無約束用筆算算看Chapter 1 線性規(guī)劃與單純形法 ：(1) (1) 用用x x4 4 - x- x5 5 替換替換 x x3 3, , 其中其中 ，(2) (2) 在第一個約束不等式在第一個約束不等式 號的左端加入松弛變號的左端加入松弛變量量 x x6 6(3) (3) 在第二個約束不等式在第二個約束不等式 號的左端減去松弛變號的左端減去松弛變量量 x x7 7(4) (

43、4) 令令 ，把，把 改改為為 , , 即可得到該問題的標(biāo)準(zhǔn)型即可得到該問題的標(biāo)準(zhǔn)型舉例45, 0 xx ZZ min ZmaxZ12456712456124571245124567max 23()00()7()2s.t.32()5,0zxxxxxxxxxxxxxxxxxxxxx x x x x x把例1.5 第三個約束為下面的形式，化標(biāo)準(zhǔn)型。：123123123123123min2372s.t.325,0, zxxxxxxxxxxxxx xx 取值無約束12456781245612457124581245678max 23()000()7()2s.t.32()5,0zxxxxxxxxxxxx

44、xxxxxxxxxxx x x x x x xChapter 1 線性規(guī)劃與單純形法 一般線性規(guī)劃問題的標(biāo)準(zhǔn)型為：一般線性規(guī)劃問題的標(biāo)準(zhǔn)型為：maxZ=CX|AX=b,X0 u 可行解：可行解： 滿足上式約束滿足上式約束 條件條件 的解的解x=(x1,x2,x3,xn)T ，稱為線性，稱為線性規(guī)劃問題的可行解。全部可行解的規(guī)劃問題的可行解。全部可行解的集合稱為可行域。集合稱為可行域。Chapter 1 線性規(guī)劃與單純形法 u 最優(yōu)解：最優(yōu)解： 使目標(biāo)函數(shù)達(dá)到最大值的可行解稱使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解，對應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值。為最優(yōu)解，對應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值。u 基：基： 設(shè)

45、設(shè) A Am mn n(mn) (mn) 為約束方程組的系數(shù)矩陣，為約束方程組的系數(shù)矩陣，其秩為其秩為m m。 B Bm mm m 是矩陣是矩陣 A A 中的子矩陣且是滿秩中的子矩陣且是滿秩陣，陣， 則稱則稱 B B 是線性規(guī)劃問題的一個基（基矩是線性規(guī)劃問題的一個基（基矩陣）。不妨設(shè)陣）。不妨設(shè) B=B=（a aijij）m mm m 中的每一個列向量中的每一個列向量 p pj j (j=1,2,m)(j=1,2,m)為基向量。與基向量為基向量。與基向量 p pj j 對對應(yīng)的變量應(yīng)的變量 x xj j 稱為基變量，其它的變量稱為非基稱為基變量，其它的變量稱為非基變量。變量。 注注：當(dāng)：當(dāng)

46、m=n m=n 時，基矩陣唯一，當(dāng)時，基矩陣唯一，當(dāng)mn, m12, 12, 我們有我們有邊界方程邊界方程 L4: xL4: x1 1+x+x2 2=12, =12, 約束條件為約束條件為 L4 L4 的上方，則該問題的可行域為空集，即沒的上方，則該問題的可行域為空集，即沒有一個點滿足所有的約束條件，問題無可有一個點滿足所有的約束條件，問題無可行解，也不存在最優(yōu)解。行解，也不存在最優(yōu)解。 （可行域為空集可行域為空集）圖解法適用于求解只有兩個決策變量的線性圖解法適用于求解只有兩個決策變量的線性規(guī)劃問題，具體步驟如下：規(guī)劃問題，具體步驟如下： 1.1.畫出每個函數(shù)約束的約束邊界，用原點畫出每個函數(shù)

47、約束的約束邊界，用原點（或其它不在邊界上的點）判斷直線的哪（或其它不在邊界上的點）判斷直線的哪一邊是約束條件所允許的。一邊是約束條件所允許的。2.2.找出所有約束條件都同時滿足的區(qū)域，找出所有約束條件都同時滿足的區(qū)域，即可行域。即可行域。圖解法的步驟3.3.給目標(biāo)函數(shù)一個特定的值給目標(biāo)函數(shù)一個特定的值 k, k, 畫出目標(biāo)畫出目標(biāo)函數(shù)等值線，當(dāng)函數(shù)等值線，當(dāng) k k 變化時，目標(biāo)函數(shù)等值變化時，目標(biāo)函數(shù)等值線平行移動；線平行移動； 對于目標(biāo)函數(shù)最小化的問題，對于目標(biāo)函數(shù)最小化的問題，找出目標(biāo)函數(shù)減少的方向，目標(biāo)函數(shù)最后找出目標(biāo)函數(shù)減少的方向，目標(biāo)函數(shù)最后離開可行域的點是最優(yōu)解。離開可行域的點是

48、最優(yōu)解。 4. 4. 從圖解法可以看出，線性規(guī)劃問題的可從圖解法可以看出，線性規(guī)劃問題的可行域非空時它是一個凸多邊形，若線性規(guī)劃行域非空時它是一個凸多邊形，若線性規(guī)劃問題存在最優(yōu)解，它一定在可行域的邊界得問題存在最優(yōu)解，它一定在可行域的邊界得到；到； 若有唯一最優(yōu)解，則一定在可行域的頂點若有唯一最優(yōu)解，則一定在可行域的頂點處得到；若兩個頂點同時達(dá)到最優(yōu)解，則兩處得到；若兩個頂點同時達(dá)到最優(yōu)解，則兩個頂點之間線段上的任意一點都是最優(yōu)解。個頂點之間線段上的任意一點都是最優(yōu)解。9621基本概念基本概念)(X)(XX10121 凸組合凸組合 設(shè)設(shè) ，若存在若存在 ，0 0 10 0 1，且，且 ，使使

49、則稱則稱X 為為 的凸組合。的凸組合。 k, 1kkXXX 11i nKEX,X 1KX,X 111 Kii 兩點連線上的任何一點都是這兩點的凸組合兩點連線上的任何一點都是這兩點的凸組合 基本概念基本概念97設(shè)設(shè) nEK ，若任意兩點，若任意兩點KX,KX 21的凸組合屬的凸組合屬于于 K，即，即 )(KX)(XX10121 則稱則稱 K 為凸集。為凸集。 aab(c)ccdd凸集凸集98圖中粗線和圓點是頂點。圖中粗線和圓點是頂點。aabb(c)cdLP問題解的性質(zhì)（1 1）若）若(LP)(LP)問題有可行解，則可行解集問題有可行解，則可行解集( (可可行域行域) )是凸集是凸集( (可能有界

50、，也可能無界可能有界，也可能無界) )，有，有有限個頂點。有限個頂點。99（2 2）(LP)(LP)問題的基本可行解問題的基本可行解 可行可行域的頂點。域的頂點。 （3）若若(LP)(LP)問題有最優(yōu)解，必可以在問題有最優(yōu)解，必可以在基本可行解基本可行解( (頂點頂點) )達(dá)到。達(dá)到。定理定理1 1 若線性規(guī)劃問題存在可行解，則所若線性規(guī)劃問題存在可行解，則所有可行解的集合有可行解的集合可行域可行域 D D = = X| AX= X| AX= b b，X X 0 0 是凸集。是凸集。定理定理2 2 線性規(guī)劃問題的基可行解線性規(guī)劃問題的基可行解X X對應(yīng)于對應(yīng)于可行域可行域 D D 的頂點的頂點

51、（極點）（極點）。定理定理3 3 若可行域有界，線性規(guī)劃問題的目若可行域有界，線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在頂點上達(dá)到最優(yōu)。標(biāo)函數(shù)一定可以在頂點上達(dá)到最優(yōu)。線性規(guī)劃的基本定理101Cnm = n!m!(n-m)!(m n)基本可行解個數(shù)有限，當(dāng)約束條件為m個，n個變量時，基本可行解個數(shù)不超過:定理2 刻畫了可行解集的極點與基本可行解的對應(yīng)關(guān)系：極點是基本可行解，反之，基本可行解一定是極點，但它們并非一一 對應(yīng) ，有可能兩個或幾個基本可行解對應(yīng)于同一極點（退化基本可行解時）。 定理 2及 3 給了我們一個啟示，尋求最優(yōu)解不是在無限個可行解中去找，而是在有限個基本可行解中去尋求。下一節(jié)將介紹一種

52、有效地尋找最優(yōu)解的方法。 若線性規(guī)劃的可行解集非空且有界，則一定有最優(yōu)解；若可行解集無界，則線性規(guī)劃可能有最優(yōu)解，也可能沒有最優(yōu)解。Chapter 1 線性規(guī)劃與單純形法 2 2 單純形法單純形法從上一節(jié)中我們看到，若線性規(guī)劃有最優(yōu)解，從上一節(jié)中我們看到，若線性規(guī)劃有最優(yōu)解，必在可行域的某個頂點達(dá)到。最可能想到的必在可行域的某個頂點達(dá)到。最可能想到的是把所有頂點都找出來，然后逐個比較，求是把所有頂點都找出來，然后逐個比較，求出最優(yōu)解，這種方法事實上是行不通的，因出最優(yōu)解，這種方法事實上是行不通的，因為頂點的個數(shù)非常大。例如為頂點的個數(shù)非常大。例如m=20m=20，n=40n=40，頂，頂點的個

53、數(shù)有點的個數(shù)有 個，個，要計算這么多頂點對象目標(biāo)函數(shù)值，顯然是要計算這么多頂點對象目標(biāo)函數(shù)值，顯然是不可能的。不可能的。112040103 . 1C換一種思考方法，從某一個基可行解出發(fā)，每換一種思考方法，從某一個基可行解出發(fā)，每次總是尋找比上一個更好的基可行解，如果不次總是尋找比上一個更好的基可行解，如果不比上一個好就不去計算，這樣做就大大減少計比上一個好就不去計算，這樣做就大大減少計算量。其基本想法是判別當(dāng)前解是否最優(yōu)，提算量。其基本想法是判別當(dāng)前解是否最優(yōu)，提出問題的標(biāo)準(zhǔn)，從可行域中某個基可行解（一出問題的標(biāo)準(zhǔn)，從可行域中某個基可行解（一個頂點）開始，轉(zhuǎn)換到另一個基可行解（頂個頂點）開始，

54、轉(zhuǎn)換到另一個基可行解（頂點），并且使目標(biāo)函數(shù)逐步增大，最后就得到點），并且使目標(biāo)函數(shù)逐步增大，最后就得到了最優(yōu)解。美國數(shù)學(xué)家丹捷格（了最優(yōu)解。美國數(shù)學(xué)家丹捷格（G.B.DantzigG.B.Dantzig）提出的單純形方法解決了此問題，單純形方法提出的單純形方法解決了此問題，單純形方法到目前為止是求解線性規(guī)劃的最普遍最有效的到目前為止是求解線性規(guī)劃的最普遍最有效的方法。方法。單純性方法基本思想單純性方法基本思想 對于一個對于一個標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型LPLP問題，從一個初始問題，從一個初始基可行解基可行解出出發(fā)，判斷其是否為最優(yōu)解，若是則結(jié)束；否則求一發(fā)，判斷其是否為最優(yōu)解，若是則結(jié)束；否則求一個與其個

55、與其“相鄰相鄰”的、改進(jìn)的的、改進(jìn)的基可行解基可行解。再判斷這個。再判斷這個解是否最優(yōu)，若是則結(jié)束，否則再求一個解是否最優(yōu)，若是則結(jié)束，否則再求一個“相鄰相鄰”的、改進(jìn)的的、改進(jìn)的基可行解基可行解直至得到一個基直至得到一個基最優(yōu)解最優(yōu)解。利用下面的例子說明幾何意義121231425max2328416s.t.41201,5jzxxxxxxxxxxjx1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2 O Q1 Q2或或 O Q4 Q3 Q2Chapter 1 線性規(guī)劃與單純形法 2.12.1初始基可行解的確定初始基可行解的確定為了確定初始基可行

56、解，要首先找出初始可行基，為了確定初始基可行解，要首先找出初始可行基，其方法如下：其方法如下：若線性規(guī)劃問題：若線性規(guī)劃問題： 11max. .(6.1)0;1,2,njjjnjjjjzc xP xbs txjn從從 P Pj j (j=1,2,n) (j=1,2,n) 中一般能直接觀察到一個中一般能直接觀察到一個初始可行基初始可行基：100010001BChapter 1 線性規(guī)劃與單純形法 2 2）對約束條件是）對約束條件是“”形式的不等式，在形式的不等式，在每個約束條件的左端加上一個松弛變量。每個約束條件的左端加上一個松弛變量。經(jīng)整理，重新對經(jīng)整理，重新對 x xj j 及進(jìn)行編號，可得

57、到下及進(jìn)行編號，可得到下列方程組：列方程組：11,111122,1122,11(6.2).mmnnmmnnmm mmmnnmxaxa xbxaxa xbxaxaxb顯然可以得到一個單位矩陣：顯然可以得到一個單位矩陣：以以B B 作為可行基，將每個等式移項：作為可行基，將每個等式移項：100010001Bq令令x xm+1m+1= =x xm+2m+2= = =x xn n=0,=0,由上式可得由上式可得: : x xi i= =b bi i （i=1i=1，2 2，m m）X=(xX=(x1 1,x,x2 2,x,xm m,0,0),0,0)T T=(b=(b1 1,b,b2 2,b,bm m

58、,0,0,0)0)T T111,111222,112,11.(6.3)mmnnmmnnmmm mmmnnxbaxa xxbaxa xxbaxaxChapter 1 線性規(guī)劃與單純形法 q3 3）對所有約束條件是）對所有約束條件是“”形式的不等式形式的不等式及等式約束情況，及等式約束情況，化為標(biāo)準(zhǔn)型后若不存在單化為標(biāo)準(zhǔn)型后若不存在單位矩陣式，就采用人造基方法位矩陣式，就采用人造基方法。 即對不等即對不等式約束減去一個非負(fù)剩余變量，再加上一個式約束減去一個非負(fù)剩余變量，再加上一個非負(fù)人工變量；對于等式約束再加上一個非非負(fù)人工變量；對于等式約束再加上一個非負(fù)的人工變量，總能得到一個單位矩陣。負(fù)的人工

59、變量，總能得到一個單位矩陣。（有關(guān)加上人工變量的線性規(guī)劃問題，以后（有關(guān)加上人工變量的線性規(guī)劃問題，以后再討論。）再討論。）Chapter 1 線性規(guī)劃與單純形法 由兩個變量的線性規(guī)劃圖解方法我們得到啟示，線由兩個變量的線性規(guī)劃圖解方法我們得到啟示，線性規(guī)劃問題的求解結(jié)果可能出現(xiàn)性規(guī)劃問題的求解結(jié)果可能出現(xiàn) n唯一最優(yōu)解、唯一最優(yōu)解、n無窮多最優(yōu)解、無窮多最優(yōu)解、n無界解無界解n和無可行解四種情況，和無可行解四種情況， 為此需要建立對解的判別準(zhǔn)則。為此需要建立對解的判別準(zhǔn)則。我們以下面的線性我們以下面的線性規(guī)劃模型為例說明解的判別準(zhǔn)則規(guī)劃模型為例說明解的判別準(zhǔn)則1 12 211,111122,

60、1122,11max Z= + +(6.2).n nmmn nmmn nmm mmmn nmcx c xc xxaxa xbxaxa xbxaxa xb化標(biāo)準(zhǔn)型后，對于約束矩陣中含有單位基矩陣的情況，化標(biāo)準(zhǔn)型后，對于約束矩陣中含有單位基矩陣的情況，我們重新對我們重新對 xj 進(jìn)行編號，總可以得到下面的形式：進(jìn)行編號，總可以得到下面的形式：111,111222,112,11.(6.3)mmnnmmnnmmm mmmnnxbaxa xxbaxa xxbaxax1(1,2,)niiijjj mxba x im即：根據(jù)上節(jié)得到的基解計算公式可歸納如下：根據(jù)上節(jié)得到的基解計算公式可歸納如下：注注 ： 初