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

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

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

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

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

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

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

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

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

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

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

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

12、、政治到管理、經(jīng)濟(jì)及工程技術(shù)等許多領(lǐng)域都能應(yīng)用到運(yùn)籌學(xué)的思想和方法。經(jīng)過(guò)半個(gè)世紀(jì)左右的發(fā)展，運(yùn)籌學(xué)形成了下面主要幾個(gè)分支在這過(guò)程中，科學(xué)家，學(xué)者和工程師 都起了很大的作用，在其它很多領(lǐng)域也是這樣的！運(yùn)籌學(xué)的分支:線性規(guī)劃（線性規(guī)劃（linear programminglinear programming）整數(shù)規(guī)劃（整數(shù)規(guī)劃（integer programming integer programming ）運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 （ 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）動(dòng)態(tài)規(guī)劃（動(dòng)態(tài)規(guī)劃（dynamic programmingdynamic programming）對(duì)策論（對(duì)策論（game theorygame theory）決策論（決策論（decision theorydecision theory）排隊(duì)論（排隊(duì)論（queu

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

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

16、學(xué)習(xí)該課程，應(yīng)了解管理運(yùn)籌學(xué)對(duì)優(yōu)化決策問(wèn)題進(jìn)行定量研究的特點(diǎn)的特點(diǎn), ,理解理解 線性規(guī)劃、整數(shù)規(guī)劃、運(yùn)輸問(wèn)題線性規(guī)劃、整數(shù)規(guī)劃、運(yùn)輸問(wèn)題 、目標(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)真聽(tīng)講（不能曠課）課堂認(rèn)真聽(tīng)講（不能曠課）( (每曠課一次平時(shí)成績(jī)扣每曠課一次平時(shí)成績(jī)扣1010分分) ) 認(rèn)真完成作業(yè)認(rèn)真完成作業(yè)成成 績(jī)：績(jī)： 平

17、時(shí)成績(jī)平時(shí)成績(jī) 30% 30% （作業(yè)、出勤、課堂紀(jì)律、實(shí)驗(yàn)報(bào)告）（作業(yè)、出勤、課堂紀(jì)律、實(shí)驗(yàn)報(bào)告） + +考試成績(jī)考試成績(jī) 70%70%答疑時(shí)間：答疑時(shí)間：每次課后時(shí)間，周五下午（行政樓每次課后時(shí)間，周五下午（行政樓619 619 ）參考書(shū)目：參考書(shū)目：運(yùn)籌學(xué)教程（第二版胡運(yùn)權(quán) 清華大學(xué)出版社 運(yùn)籌學(xué)運(yùn)籌學(xué)趙可培趙可培, ,上海財(cái)經(jīng)大學(xué)出版社上海財(cái)經(jīng)大學(xué)出版社 管理運(yùn)籌學(xué)管理運(yùn)籌學(xué)謝家平謝家平, , 中國(guó)人民大學(xué)出版社中國(guó)人民大學(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、矩陣矩陣( (向量向量) )運(yùn)算規(guī)則運(yùn)算規(guī)則 加減乘、求逆運(yùn)算 結(jié)合律 分配律 交換律 乘法無(wú)交換律乘法無(wú)交換律線性相關(guān)線性相關(guān) 一組向量v1,vn,如果有一組不全為零的 系數(shù)1, ,n,使得: 1 v1+nvn=0 則稱v1,vn 是線性相關(guān)的.線性無(wú)關(guān)線性無(wú)關(guān) 一組向量v1,vn,如果對(duì)于任何數(shù)1,n, 若要滿足: 1 v1+nvn=0 ,則必有系數(shù) 1=n=0,(全為零)則稱v1,vn線性無(wú)關(guān). 矩陣矩陣A A的秩的秩 設(shè)A為一個(gè)mn階矩陣(mn)若矩陣中最大線性 無(wú)關(guān)列向量個(gè)數(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)活動(dòng)、營(yíng)銷活動(dòng)、是用線性數(shù)學(xué)模型表示不同的生產(chǎn)活動(dòng)、營(yíng)銷活動(dòng)、金融活動(dòng)或其他活動(dòng)的計(jì)劃。金融活動(dòng)或其他活動(dòng)的計(jì)劃。 本章重點(diǎn)1、根據(jù)實(shí)際問(wèn)題寫(xiě)出線性規(guī)劃模型2、掌握線性規(guī)劃化標(biāo)準(zhǔn)型的方法3、理解并掌握線性規(guī)劃解的概念4、能夠用圖解法求解線性規(guī)劃問(wèn)題5、熟練掌握線性規(guī)劃單純形法的基本思想和 步驟難點(diǎn)難點(diǎn)線性規(guī)劃（Linear Programming,縮寫(xiě)為L(zhǎng)P）是運(yùn)籌學(xué)的重要分支之一，在實(shí)際中應(yīng)用得較廣

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

21、三類問(wèn)題分別是資源分配問(wèn)題，成本效益問(wèn)題以及網(wǎng)絡(luò)配送別是資源分配問(wèn)題，成本效益問(wèn)題以及網(wǎng)絡(luò)配送問(wèn)題。第四類具有兩種以上的約束的線性規(guī)劃問(wèn)問(wèn)題。第四類具有兩種以上的約束的線性規(guī)劃問(wèn)題。題。 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)品都在一個(gè)設(shè)備上生產(chǎn)，由于兩種產(chǎn)品都在一個(gè)設(shè)備上生產(chǎn)， 且設(shè)且設(shè)備使用時(shí)間有限，管理者必須合理安排兩備使用時(shí)間有限，管理者必須合理安排兩種產(chǎn)品的產(chǎn)量，使得在資源有限的條件下種產(chǎn)品的產(chǎn)量，使得在資源有限的條件下

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

23、舉例這些數(shù)據(jù)可以通過(guò)調(diào)研或估算得出，這些數(shù)據(jù)可以通過(guò)調(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 -利潤(rùn)利潤(rùn)由表由表1.11.1最后一行知最后一行知Z Z4x4x1 1+3x+3x2 2建立數(shù)學(xué)模型目標(biāo)是如何確定目標(biāo)是如何確定x x1 1和和x x2 2，使得利潤(rùn)，使得利潤(rùn)Z Z最大最大, ,同同時(shí)需要滿足資源約束。對(duì)于原料時(shí)需要滿足資源約束。對(duì)于原料A A和原料和原料B B，有：有：x x1 166，2x2x2 288對(duì)于設(shè)備工時(shí)，有：對(duì)于設(shè)備工時(shí)

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

25、為線性規(guī)劃問(wèn)題模型。問(wèn)題模型。以上模型中，將以上模型中，將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ī)劃與單純形法 從以上過(guò)程我們可以歸納出根據(jù)實(shí)際從以上過(guò)程我們可以歸納出根據(jù)實(shí)際 問(wèn)題建立線性規(guī)劃模型的步驟：?jiǎn)栴}建立線性規(guī)劃模型的步驟：1) 1) 根據(jù)管理層的要求確定決策目標(biāo)和收集根據(jù)管理層的要求確定決策目標(biāo)和收集相關(guān)數(shù)據(jù)。相關(guān)數(shù)據(jù)。2) 2) 確定要做出的決策，引入決策變量。確定

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

27、究者根據(jù)這一目標(biāo)收集到的有關(guān)數(shù)據(jù)如下（見(jiàn)表下（見(jiàn)表1.21.2）舉例表1.2 營(yíng)養(yǎng)成分營(yíng)養(yǎng)成分每公斤玉每公斤玉米米每公斤每公斤紅薯紅薯每公斤最每公斤最低要求低要求碳水化合物碳水化合物8420蛋白質(zhì)蛋白質(zhì)3618維他命維他命1516采購(gòu)成本采購(gòu)成本（元（元/公斤）公斤）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)要求最低且滿足最低營(yíng)養(yǎng)要求的約束，的約束，Chapter 1 線性規(guī)劃與單純形法 因此這個(gè)問(wèn)題的線性規(guī)劃模型為：因此這個(gè)問(wèn)題的線性規(guī)劃模型為：其中其中“s.t.”是是“subject to”的縮寫(xiě)，意思的縮寫(xiě)，意思是是“受約束于受約束于”。12121212min0.80.58x4203x618s.tx51601,2iZxxxxxxi碳水化合物要求蛋白質(zhì)物要求維他命物要求Chapter 1 線性規(guī)劃與單純形法 某物流公司需要將甲、乙、丙三個(gè)工廠某物流

29、公司需要將甲、乙、丙三個(gè)工廠生產(chǎn)的一種新產(chǎn)品送到生產(chǎn)的一種新產(chǎn)品送到 A A、B B 兩個(gè)倉(cāng)庫(kù)，甲、兩個(gè)倉(cāng)庫(kù)，甲、乙兩個(gè)工廠的產(chǎn)品可以通過(guò)鐵路運(yùn)送到倉(cāng)庫(kù)乙兩個(gè)工廠的產(chǎn)品可以通過(guò)鐵路運(yùn)送到倉(cāng)庫(kù)A A，數(shù)量不限；丙工廠的產(chǎn)品可以通過(guò)鐵路運(yùn)送到數(shù)量不限；丙工廠的產(chǎn)品可以通過(guò)鐵路運(yùn)送到倉(cāng)庫(kù)倉(cāng)庫(kù)B B，同樣，產(chǎn)品數(shù)量不限。，同樣，產(chǎn)品數(shù)量不限。 由于鐵路運(yùn)輸由于鐵路運(yùn)輸成本較高，公司也可以考慮由獨(dú)立的卡車來(lái)運(yùn)成本較高，公司也可以考慮由獨(dú)立的卡車來(lái)運(yùn)輸，可將多達(dá)輸，可將多達(dá)8080個(gè)單位的產(chǎn)品由甲、乙、丙三個(gè)單位的產(chǎn)品由甲、乙、丙三個(gè)工廠運(yùn)到一個(gè)配送中心，再?gòu)呐渌椭行囊宰顐€(gè)工廠運(yùn)到一個(gè)配送中心，再?gòu)呐渌椭?/p>

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

31、1.3所示。所示。為了更清楚地說(shuō)明問(wèn)題，我們用網(wǎng)絡(luò)圖來(lái)為了更清楚地說(shuō)明問(wèn)題，我們用網(wǎng)絡(luò)圖來(lái)直觀表示該配送問(wèn)題。見(jiàn)圖直觀表示該配送問(wèn)題。見(jiàn)圖1.11.1 其中其中 ，v v1 1、v v2 2、v v3 3 表示甲、乙、丙三個(gè)表示甲、乙、丙三個(gè)工廠，節(jié)點(diǎn)工廠，節(jié)點(diǎn)v v4 4表示配送中心，節(jié)點(diǎn)表示配送中心，節(jié)點(diǎn)v v5 5、v v6 6表表示兩個(gè)倉(cāng)庫(kù)；每一條箭線表示一條可能的示兩個(gè)倉(cāng)庫(kù)；每一條箭線表示一條可能的運(yùn)輸線路，并給出了相應(yīng)的單位運(yùn)輸成本，運(yùn)輸線路，并給出了相應(yīng)的單位運(yùn)輸成本，對(duì)運(yùn)輸量有限制的路線的最大運(yùn)輸能力也對(duì)運(yùn)輸量有限制的路線的最大運(yùn)輸能力也同時(shí)給出。同時(shí)給出。$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倉(cāng)庫(kù)B120倉(cāng)庫(kù)A圖圖1.1配送中心 我們要解決的是各條線路最大運(yùn)輸量，引我們要解決的是各條線路最大運(yùn)輸量，引入變量入變量 x xij ij 表示由表示由 v vi i 經(jīng)過(guò)路線經(jīng)過(guò)路線 (v(vi i， v vj j ) ) 運(yùn)輸?shù)竭\(yùn)輸?shù)?v vj j 的產(chǎn)品數(shù)。的產(chǎn)品數(shù)。 問(wèn)題的目標(biāo)是總運(yùn)問(wèn)題的目標(biāo)是總運(yùn)輸成本最小化，總運(yùn)輸成本可以表示為：輸成本最小化，總運(yùn)輸成本可以表示為： 總運(yùn)輸成本總運(yùn)輸成本 = 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從以上的幾個(gè)例子可以看出，線性規(guī)劃問(wèn)題有從以上的幾個(gè)例子可以看出，線性規(guī)劃問(wèn)題有如下共同如下共同特征特征： （模型的三要素）（

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

35、的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。現(xiàn)最大化或最小化。例2 某工廠用鋼與橡膠生產(chǎn)3種產(chǎn)品A、B、C，有關(guān)資料如下表404524332231 A B C單位產(chǎn)品利潤(rùn)單位產(chǎn)品橡膠量單位產(chǎn)品鋼消耗量產(chǎn)品已知每天可獲得100單位的鋼和120單位橡膠，問(wèn)每天生產(chǎn)A、B、C各多少使總利潤(rùn)最大？練習(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價(jià)值向量：價(jià)值向量：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ī)定各約束條件的右端項(xiàng)在標(biāo)準(zhǔn)型式中規(guī)定各約束條件的右端項(xiàng)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ī)劃與單純形法 用向量和矩陣符號(hào)表述時(shí)為：用向量和矩陣符號(hào)表述時(shí)為：1max z=CXs.t.0,1,2,njjjjP xbxjn),(21ncccC12nxxXx12jjjmjaaPa12mbbbb用矩陣描述時(shí)為：用矩陣描述時(shí)為：其中：其中：11121121200,;00nnmmmnaaaAP PPaaa maxb 0ZCXAXXChapter 1 線性規(guī)劃與單純形法稱稱A A為約束條件的為約束條件的m mn n維系數(shù)矩

39、陣，維系數(shù)矩陣，一般一般m0;m0;b b為資源向量；為資源向量；C C為價(jià)值向量；為價(jià)值向量；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ù)實(shí)現(xiàn)最小化，即）若要求目標(biāo)函數(shù)實(shí)現(xiàn)最小化，即min min z=CXz=CX。這時(shí)只需將目標(biāo)函數(shù)最小化變換求目。這時(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)榈仁剑?另一種是約束方程為另一種是約束方程為不等式，則可不等式，則可在在不等式的左端減去一個(gè)非負(fù)剩余不等式的左端減去一個(gè)非負(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取值無(wú)約束取值無(wú)約束, ,則令則令 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取值無(wú)約束用筆算算看Chapter 1 線性規(guī)劃與單純形法 ：(1) (1) 用用x x4 4 - x- x5 5 替換替換 x x3 3, , 其中其中 ，(2) (2) 在第一個(gè)約束不等式在第一個(gè)約束不等式 號(hào)的左端加入松弛變號(hào)的左端加入松弛變量量 x x6 6(3) (3) 在第二個(gè)約束不等式在第二個(gè)約束不等式 號(hào)的左端減去松弛變號(hào)的左端減去松弛變量量 x x7 7(4) (

43、4) 令令 ，把，把 改改為為 , , 即可得到該問(wèn)題的標(biāo)準(zhǔn)型即可得到該問(wè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 第三個(gè)約束為下面的形式，化標(biāo)準(zhǔn)型。：123123123123123min2372s.t.325,0, zxxxxxxxxxxxxx xx 取值無(wú)約束12456781245612457124581245678max 23()000()7()2s.t.32()5,0zxxxxxxxxxxxx

44、xxxxxxxxxxx x x x x x xChapter 1 線性規(guī)劃與單純形法 一般線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為：一般線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為：maxZ=CX|AX=b,X0 u 可行解：可行解： 滿足上式約束滿足上式約束 條件條件 的解的解x=(x1,x2,x3,xn)T ，稱為線性，稱為線性規(guī)劃問(wèn)題的可行解。全部可行解的規(guī)劃問(wèn)題的可行解。全部可行解的集合稱為可行域。集合稱為可行域。Chapter 1 線性規(guī)劃與單純形法 u 最優(yōu)解：最優(yōu)解： 使目標(biāo)函數(shù)達(dá)到最大值的可行解稱使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解，對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)值。為最優(yōu)解，對(duì)應(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ī)劃問(wèn)題的一個(gè)基（基矩是線性規(guī)劃問(wèn)題的一個(gè)基（基矩陣）。不妨設(shè)陣）。不妨設(shè) B=B=（a aijij）m mm m 中的每一個(gè)列向量中的每一個(gè)列向量 p pj j (j=1,2,m)(j=1,2,m)為基向量。與基向量為基向量。與基向量 p pj j 對(duì)對(duì)應(yīng)的變量應(yīng)的變量 x xj j 稱為基變量，其它的變量稱為非基稱為基變量，其它的變量稱為非基變量。變量。 注注：當(dāng)：當(dāng)

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

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

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

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

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

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

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

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

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

55、與其“相鄰相鄰”的、改進(jìn)的的、改進(jìn)的基可行解基可行解。再判斷這個(gè)。再判斷這個(gè)解是否最優(yōu)，若是則結(jié)束，否則再求一個(gè)解是否最優(yōu)，若是則結(jié)束，否則再求一個(gè)“相鄰相鄰”的、改進(jìn)的的、改進(jìn)的基可行解基可行解直至得到一個(gè)基直至得到一個(gè)基最優(yōu)解最優(yōu)解。利用下面的例子說(shuō)明幾何意義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ī)劃問(wèn)題：若線性規(guī)劃問(wèn)題： 11max. .(6.1)0;1,2,njjjnjjjjzc xP xbs txjn從從 P Pj j (j=1,2,n) (j=1,2,n) 中一般能直接觀察到一個(gè)中一般能直接觀察到一個(gè)初始可行基初始可行基：100010001BChapter 1 線性規(guī)劃與單純形法 2 2）對(duì)約束條件是）對(duì)約束條件是“”形式的不等式，在形式的不等式，在每個(gè)約束條件的左端加上一個(gè)松弛變量。每個(gè)約束條件的左端加上一個(gè)松弛變量。經(jīng)整理，重新對(duì)經(jīng)整理，重新對(duì) x xj j 及進(jìn)行編號(hào)，可得

57、到下及進(jìn)行編號(hào)，可得到下列方程組：列方程組：11,111122,1122,11(6.2).mmnnmmnnmm mmmnnmxaxa xbxaxa xbxaxaxb顯然可以得到一個(gè)單位矩陣：顯然可以得到一個(gè)單位矩陣：以以B B 作為可行基，將每個(gè)等式移項(xiàng)：作為可行基，將每個(gè)等式移項(xiàng)：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）對(duì)所有約束條件是）對(duì)所有約束條件是“”形式的不等式形式的不等式及等式約束情況，及等式約束情況，化為標(biāo)準(zhǔn)型后若不存在單化為標(biāo)準(zhǔn)型后若不存在單位矩陣式，就采用人造基方法位矩陣式，就采用人造基方法。 即對(duì)不等即對(duì)不等式約束減去一個(gè)非負(fù)剩余變量，再加上一個(gè)式約束減去一個(gè)非負(fù)剩余變量，再加上一個(gè)非負(fù)人工變量；對(duì)于等式約束再加上一個(gè)非非負(fù)人工變量；對(duì)于等式約束再加上一個(gè)非負(fù)的人工變量，總能得到一個(gè)單位矩陣。負(fù)的人工

59、變量，總能得到一個(gè)單位矩陣。（有關(guān)加上人工變量的線性規(guī)劃問(wèn)題，以后（有關(guān)加上人工變量的線性規(guī)劃問(wèn)題，以后再討論。）再討論。）Chapter 1 線性規(guī)劃與單純形法 由兩個(gè)變量的線性規(guī)劃圖解方法我們得到啟示，線由兩個(gè)變量的線性規(guī)劃圖解方法我們得到啟示，線性規(guī)劃問(wèn)題的求解結(jié)果可能出現(xiàn)性規(guī)劃問(wèn)題的求解結(jié)果可能出現(xiàn) n唯一最優(yōu)解、唯一最優(yōu)解、n無(wú)窮多最優(yōu)解、無(wú)窮多最優(yōu)解、n無(wú)界解無(wú)界解n和無(wú)可行解四種情況，和無(wú)可行解四種情況， 為此需要建立對(duì)解的判別準(zhǔn)則。為此需要建立對(duì)解的判別準(zhǔn)則。我們以下面的線性我們以下面的線性規(guī)劃模型為例說(shuō)明解的判別準(zhǔn)則規(guī)劃模型為例說(shuō)明解的判別準(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)型后，對(duì)于約束矩陣中含有單位基矩陣的情況，化標(biāo)準(zhǔn)型后，對(duì)于約束矩陣中含有單位基矩陣的情況，我們重新對(duì)我們重新對(duì) xj 進(jìn)行編號(hào)，總可以得到下面的形式：進(jìn)行編號(hào)，總可以得到下面的形式：111,111222,112,11.(6.3)mmnnmmnnmmm mmmnnxbaxa xxbaxa xxbaxax1(1,2,)niiijjj mxba x im即：根據(jù)上節(jié)得到的基解計(jì)算公式可歸納如下：根據(jù)上節(jié)得到的基解計(jì)算公式可歸納如下：注注 ： 初