胡云權(quán)運(yùn)籌學(xué)課件第一部分

運(yùn)籌學(xué)基礎(chǔ)第一講主講教師：鄭黎黎學(xué)時(shí)：48運(yùn)籌學(xué)的產(chǎn)生和發(fā)展運(yùn)籌學(xué)的定義與特點(diǎn)運(yùn)籌學(xué)解決問(wèn)題的過(guò)程運(yùn)籌學(xué)的主要研究?jī)?nèi)容參考文獻(xiàn)緒論運(yùn)籌學(xué)在英國(guó)被稱(chēng)為

運(yùn)籌學(xué)的產(chǎn)生和發(fā)展運(yùn)籌學(xué)在美國(guó)被稱(chēng)為1957年我國(guó)operationalresearchoperationsresearch，縮寫(xiě)為O.R.“夫運(yùn)籌帷幄之中，決勝于千里之外”《漢書(shū)》1957年我國(guó)將O.R.譯為“運(yùn)籌學(xué)”運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早以前—“田忌齊王賽馬”（對(duì)策論）、“丁謂修宮”（網(wǎng)絡(luò)計(jì)劃）等都體現(xiàn)了優(yōu)化的思想。運(yùn)籌學(xué)的產(chǎn)生和發(fā)展田忌賽馬齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對(duì)局三次，每次勝負(fù)1000金。田忌在好友、著名的軍事謀略家孫臏的指導(dǎo)下，以以下安排：齊王 上 中 下 田忌 下 上 中

最終凈勝一局，贏得1000金。運(yùn)籌學(xué)思想的出現(xiàn)可以追溯到很早以前—“田忌齊王賽馬”（對(duì)策論）、“丁謂修宮”（網(wǎng)絡(luò)計(jì)劃）等都體現(xiàn)了優(yōu)化的思想。“運(yùn)籌學(xué)”作為科學(xué)概念最早出現(xiàn)在第二次世界大戰(zhàn)期間——美、英等國(guó)家的作戰(zhàn)研究小組為了解決作戰(zhàn)中所遇到的許多錯(cuò)綜復(fù)雜的戰(zhàn)略、戰(zhàn)術(shù)問(wèn)題而提出的，如水雷的布置、對(duì)深水潛艇的襲擊、商船護(hù)航的規(guī)模等等。運(yùn)籌學(xué)的產(chǎn)生和發(fā)展戰(zhàn)后這些研究成果被應(yīng)用到生產(chǎn)、經(jīng)濟(jì)領(lǐng)域，其發(fā)展可以分為三個(gè)階段：1945至50年代初期—?jiǎng)?chuàng)建時(shí)期運(yùn)籌學(xué)的產(chǎn)生和發(fā)展1948年英國(guó)成立“運(yùn)籌學(xué)俱樂(lè)部”在煤力、電力等部門(mén)推廣應(yīng)用運(yùn)籌學(xué)相繼一些大學(xué)開(kāi)設(shè)運(yùn)籌學(xué)課程

1948年美國(guó)麻省理工學(xué)院

1950年英國(guó)伯明翰大學(xué)1950年第一本運(yùn)籌學(xué)雜志《運(yùn)籌學(xué)季刊》在英國(guó)創(chuàng)刊1952年第一個(gè)運(yùn)籌學(xué)學(xué)會(huì)在美國(guó)成立1947年丹齊克在研究美國(guó)空軍資源優(yōu)化配置時(shí)提出線性規(guī)劃及其通用解法——單純形法

戰(zhàn)后這些研究成果被應(yīng)用到生產(chǎn)、經(jīng)濟(jì)領(lǐng)域，其發(fā)展可以分為三個(gè)階段：1945至50年代初期—?jiǎng)?chuàng)建時(shí)期50年代初期至50年代末期——成長(zhǎng)時(shí)期運(yùn)籌學(xué)的產(chǎn)生和發(fā)展戰(zhàn)后這些研究成果被應(yīng)用到生產(chǎn)、經(jīng)濟(jì)領(lǐng)域，其發(fā)展可以分為三個(gè)階段：1945至50年代初期—?jiǎng)?chuàng)建時(shí)期50年代初期至50年代末期——成長(zhǎng)時(shí)期運(yùn)籌學(xué)的產(chǎn)生和發(fā)展此階段的一個(gè)特點(diǎn)是電子計(jì)算機(jī)技術(shù)的迅速發(fā)展，使得運(yùn)籌學(xué)中一些方法如單純形法、動(dòng)態(tài)規(guī)劃方法等，得以用來(lái)解決實(shí)際管理統(tǒng)中的優(yōu)化問(wèn)題，促進(jìn)了運(yùn)籌學(xué)的推廣應(yīng)用。50年代未，美國(guó)大約有半數(shù)的公司在自己的經(jīng)營(yíng)管理中應(yīng)用運(yùn)籌學(xué)，如用于制訂生產(chǎn)計(jì)劃、資源分配、設(shè)備更新等方面的決策。另一個(gè)特點(diǎn)是有更多刊物、學(xué)會(huì)出現(xiàn)。戰(zhàn)后這些研究成果被應(yīng)用到生產(chǎn)、經(jīng)濟(jì)領(lǐng)域，其發(fā)展可以分為三個(gè)階段：1945至50年代初期—?jiǎng)?chuàng)建時(shí)期50年代初期至50年代末期——成長(zhǎng)時(shí)期自60年代來(lái)，運(yùn)籌學(xué)迅速普及和迅速發(fā)展時(shí)期。運(yùn)籌學(xué)的產(chǎn)生和發(fā)展此階段的特點(diǎn)是運(yùn)籌學(xué)進(jìn)一步細(xì)分為各個(gè)分支，專(zhuān)業(yè)學(xué)術(shù)團(tuán)體的迅速增多，更多期刊的創(chuàng)辦，運(yùn)籌學(xué)書(shū)籍的大量出版以及更多學(xué)校將運(yùn)籌學(xué)課程納入教學(xué)計(jì)劃之中。第三代電子數(shù)字計(jì)算機(jī)的出現(xiàn)，促使運(yùn)籌學(xué)得以用來(lái)研究一些大的復(fù)雜的系統(tǒng)．如城市交通、環(huán)境污染、回民經(jīng)濟(jì)計(jì)劃等。戰(zhàn)后這些研究成果被應(yīng)用到生產(chǎn)、經(jīng)濟(jì)領(lǐng)域，其發(fā)展可以分為三個(gè)階段：1945至50年代初期—?jiǎng)?chuàng)建時(shí)期50年代初期至50年代末期——成長(zhǎng)時(shí)期自60年代來(lái)，運(yùn)籌學(xué)迅速普及和迅速發(fā)展時(shí)期。運(yùn)籌學(xué)在我國(guó)的發(fā)展運(yùn)籌學(xué)的產(chǎn)生和發(fā)展運(yùn)籌學(xué)的定義與特點(diǎn)

運(yùn)籌學(xué)(OperationsResearch)直譯為“運(yùn)作研究”。美國(guó)運(yùn)籌學(xué)會(huì)認(rèn)為：運(yùn)籌學(xué)所研究的問(wèn)題，通常是在要求有限資源的條件下科學(xué)地決定如何最好地設(shè)計(jì)和運(yùn)營(yíng)人機(jī)系統(tǒng)。中國(guó)大百科全書(shū)釋義：它用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和國(guó)防等部門(mén)在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財(cái)力等資源，使實(shí)際系統(tǒng)有效運(yùn)行的技術(shù)科學(xué)，它可以用來(lái)預(yù)測(cè)發(fā)展趨勢(shì)，制定行動(dòng)規(guī)劃或優(yōu)選可行方案。

運(yùn)籌學(xué)的定義與特點(diǎn)還有人：運(yùn)籌學(xué)是一門(mén)應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識(shí)和數(shù)學(xué)方法，解決實(shí)際問(wèn)題中提出的專(zhuān)門(mén)問(wèn)題，為決策者選擇最優(yōu)決策提供定量依據(jù)。特點(diǎn)：系統(tǒng)尋優(yōu)、多學(xué)科綜合、輔助決策運(yùn)籌學(xué)解決問(wèn)題的過(guò)程運(yùn)籌學(xué)解決問(wèn)題的過(guò)程主要包括以下幾個(gè)步驟：分析和表述問(wèn)題，這是對(duì)問(wèn)題的定性分析過(guò)程。建立模型。運(yùn)籌學(xué)模型大都包括兩個(gè)部分：目標(biāo)和約束，建立模型的過(guò)程就是用參數(shù)、決策變量表達(dá)目標(biāo)函數(shù)、約束條件。運(yùn)籌學(xué)解決問(wèn)題的過(guò)程模型求解。用各種手段求解模型，解的精度要求可由決策者提出。模型的測(cè)試：首先檢查解的求解步驟和程序有無(wú)錯(cuò)誤，然后檢查解是否反映現(xiàn)實(shí)問(wèn)題。建立對(duì)解的有效控制。方案實(shí)施：將方案應(yīng)用的實(shí)踐中，并檢驗(yàn)方案的可行性，若不可行重新進(jìn)行上述過(guò)程。運(yùn)籌學(xué)解決問(wèn)題的過(guò)程例1.某工廠生產(chǎn)Ⅰ和Ⅱ兩種型號(hào)計(jì)算機(jī)，生產(chǎn)Ⅰ型和Ⅱ型計(jì)算機(jī)所需要原料分別為2和3個(gè)單位，需要的工時(shí)分別是4和2個(gè)單位。在計(jì)劃期內(nèi)可以使用的原料的100個(gè)單位，工時(shí)為120個(gè)單位。已知生產(chǎn)每臺(tái)Ⅰ、Ⅱ型計(jì)算機(jī)可獲利潤(rùn)分別為6個(gè)單位和4個(gè)單位，試確定獲得最大利潤(rùn)的生產(chǎn)方案。運(yùn)籌學(xué)解決問(wèn)題的過(guò)程目標(biāo)函數(shù)：

約束條件：

設(shè)z為獲得的利潤(rùn)，和分別為生產(chǎn)Ⅰ型和Ⅱ型計(jì)算機(jī)臺(tái)數(shù)線性規(guī)劃運(yùn)籌學(xué)的主要研究?jī)?nèi)容運(yùn)籌學(xué)的主要研究?jī)?nèi)容運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題線性規(guī)劃非線性規(guī)劃動(dòng)態(tài)規(guī)劃運(yùn)籌學(xué)的主要研究?jī)?nèi)容

某廠新購(gòu)某種機(jī)床125臺(tái)。據(jù)估計(jì)，這種設(shè)備5年后將被其它設(shè)備所取代。此機(jī)床如在高負(fù)荷狀態(tài)下工作，年損壞率為1/2，年利潤(rùn)為10萬(wàn)元；如在低負(fù)荷狀態(tài)下工作，年損壞率為1/5，年利潤(rùn)為6萬(wàn)元。問(wèn)應(yīng)如何安排這些機(jī)床的生產(chǎn)負(fù)荷，才能使5年內(nèi)獲得最大利潤(rùn)。線性規(guī)劃非線性規(guī)劃動(dòng)態(tài)規(guī)劃圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)的主要研究?jī)?nèi)容運(yùn)籌學(xué)基礎(chǔ)第二講主講教師：鄭黎黎學(xué)時(shí)：48線性規(guī)劃非線性規(guī)劃動(dòng)態(tài)規(guī)劃圖與網(wǎng)絡(luò)分析存貯論排隊(duì)論決策論對(duì)策論運(yùn)籌學(xué)的主要研究?jī)?nèi)容參考文獻(xiàn)

胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].北京,清華大學(xué)出版社,2002年。錢(qián)頌迪.運(yùn)籌學(xué)[M].北京,清華大學(xué)出版社,1990年。郭立夫.運(yùn)籌學(xué)[M].長(zhǎng)春,吉林大學(xué)出版社,2002年。胡運(yùn)權(quán).運(yùn)籌學(xué)習(xí)題集[M].北京,清華大學(xué)出版社,1985年。劉滿(mǎn)鳳、付波、聶高飛.運(yùn)籌學(xué)模型與方法教程例題分析與題解[M].北京,清華大學(xué)出版社,2001年。線性規(guī)劃與單純形法

線性規(guī)劃（Linearprogramming）是運(yùn)籌學(xué)的重要分支，是研究在一組線性等式或者不等式約束下，使得某一線性目標(biāo)函數(shù)取得最大（最小）的極值問(wèn)題。

1947年美國(guó)人丹齊克提出了用于求解線性規(guī)劃的單純形法。例1.美佳公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。各制造一件時(shí)分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)試時(shí)間及每天這兩種家電可用能力、各售出一件時(shí)獲利情況如表所示：項(xiàng)目ⅠⅡ每天可用能力設(shè)備A(h)0515設(shè)備B(h)6224調(diào)試時(shí)間(h)115利潤(rùn)（元）21問(wèn)公司應(yīng)制造兩種家電各多少臺(tái)，使獲取的利潤(rùn)最大。線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型(1.1c)目標(biāo)函數(shù)約束條件(1.1a)(1.1b)(1.1d)max:maximize的縮寫(xiě)，“最大化”，s.t.subjectto的縮寫(xiě)，“受限制于……”運(yùn)籌學(xué)基礎(chǔ)第三講主講教師：鄭黎黎學(xué)時(shí)：48線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型例2捷運(yùn)公司在下一年度的1~4月的4個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知各月份所需倉(cāng)庫(kù)面積列于表1-2。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見(jiàn)表1-3。租借倉(cāng)庫(kù)的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。表1-2單位：100m2表1-3單位：元/100m2月

份

1

2

3

4

所需倉(cāng)庫(kù)面積

15

10

20

12

合同租賃期限

1個(gè)月

2個(gè)月

3個(gè)月

4個(gè)月

合同期內(nèi)的租費(fèi)

2800

4500

6000

7300

線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型用變量xij表示捷運(yùn)公司在第i(i=1,…,4)個(gè)月初簽訂的租借期為j(j=1,…,4)個(gè)月的倉(cāng)庫(kù)面積的合同。因5月份起該公司不需要租借倉(cāng)庫(kù)，故x24，x33，x34，x42，x43，x44均為零。該公司希望總的租借費(fèi)用為最小，故有如下數(shù)學(xué)模型：目標(biāo)函數(shù)約束條件s.t.min：minimize，“最小化”線性規(guī)劃問(wèn)題的特征：每個(gè)問(wèn)題都用一組未知變量表示目標(biāo)函數(shù)和約束條件，并且這些變量都是非負(fù)的。有一個(gè)目標(biāo)函數(shù)，并且這個(gè)目標(biāo)可表示為一組未知量的線性函數(shù)，目標(biāo)函數(shù)可以是求最大也可以求最小。存在一組約束條件，這些約束條件都可以用一組未知量線性等式或不等式表示。線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型目標(biāo)函數(shù)：

約束條件：線性規(guī)劃問(wèn)題數(shù)學(xué)模型的一般形式：其中：為價(jià)值系數(shù)；為資源系數(shù)；為技術(shù)系數(shù)，或約束系數(shù)；線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型若設(shè)：,，1.矩陣式線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型，2.向量式3.和式在后面的公式推導(dǎo)中矩陣式和向量式用的比較多。線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型線性規(guī)劃問(wèn)題數(shù)學(xué)模型的標(biāo)準(zhǔn)型：目標(biāo)函數(shù)：

約束條件：其中：為價(jià)值系數(shù)；為資源系數(shù)；為技術(shù)系數(shù)，或約束系數(shù)；線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型運(yùn)籌學(xué)基礎(chǔ)第四講主講教師：鄭黎黎學(xué)時(shí)：48線性規(guī)劃的標(biāo)準(zhǔn)形式有四個(gè)特點(diǎn)：目標(biāo)最大化、約束為等式、右端項(xiàng)非負(fù)、決策變量均非負(fù)。對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，我們總可以通過(guò)以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式。線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型1.極小化目標(biāo)函數(shù)的問(wèn)題設(shè)目標(biāo)函數(shù)為：則可以令：，該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解：線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型2.約束條件不是等式的問(wèn)題設(shè)約束條件為：則可在約束的左端加上一個(gè)非負(fù)變量使上面的約束這個(gè)不等式約束變?yōu)榈仁郊s束：——松弛變量

線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型同理，對(duì)于不等式約束：

則可在約束的左端減去一個(gè)非負(fù)變量，則這個(gè)不等式約束變?yōu)椋哼@個(gè)非負(fù)變量稱(chēng)為松弛變量或剩余變量。線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型3.變量無(wú)符號(hào)限制的問(wèn)題在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量均有非負(fù)約束。當(dāng)某一個(gè)變量沒(méi)有非負(fù)約束時(shí)，可以令：其中，即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然的符號(hào)取決于和的大小。4.對(duì)于可以令：顯然

5.右端項(xiàng)有負(fù)值的問(wèn)題在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非負(fù)。當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如，則把該等式約束兩端同時(shí)乘以-1，得到：

線性規(guī)劃問(wèn)題及其

數(shù)學(xué)模型線性規(guī)劃問(wèn)題的數(shù)學(xué)模型和圖解法圖解法求解線性規(guī)劃問(wèn)題的步驟:分別取決策變量x1,x2

為坐標(biāo)向量建立直角坐標(biāo)系。確定可行域：對(duì)每個(gè)不等式約束（包括非負(fù)約束）條件，先畫(huà)出其等式在直角坐標(biāo)系中的直線，然后確定約束不等式所決定的半平面，各約束半平面交出來(lái)的區(qū)域即為可行域。圖示目標(biāo)函數(shù)。最優(yōu)解的確定。線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念例1的可行域表示(1.1c)(1.1a)(1.1b)(1.1d)利用圖解法求解例1的最優(yōu)解：線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念例1的可行域表示(1.1c)(1.1a)(1.1b)(1.1d)利用圖解法求解例1的最優(yōu)解：線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念圖示目標(biāo)函數(shù)和最優(yōu)解的確定(1.1d)查看目標(biāo)函數(shù)和可行域的關(guān)系，尋找線性規(guī)劃問(wèn)題的最優(yōu)解。

先將目標(biāo)函數(shù)變?yōu)椋呵蠼釷2，得到問(wèn)題最優(yōu)值線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念因此，美佳公司每天制造家電Ⅰ3.5件，家電Ⅱ1.5件，能獲得的最大利潤(rùn)是8.5元。線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念①無(wú)窮多個(gè)最優(yōu)解情況

將例1的目標(biāo)函數(shù)變?yōu)椋?1.1d)線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念②無(wú)界解例1只包含約束1.1a(1.1d)線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念③無(wú)可行解情況如果約束條件中存在相互矛盾的約束時(shí)，可行域?yàn)榭?，?wèn)題無(wú)可行解。線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念從圖解法可以看到：當(dāng)線性規(guī)劃問(wèn)題的可行域非空時(shí)，它的可行域是有界或無(wú)界凸多邊形。若線性規(guī)劃存在最優(yōu)解，它一定是在可行域的某個(gè)頂點(diǎn)得到；若在兩個(gè)頂點(diǎn)同時(shí)得到，則它們連線上的任意一點(diǎn)都是最優(yōu)解，即無(wú)窮多最優(yōu)解。線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念從圖解法可以看到：解題思路：

先找出凸集的任一頂點(diǎn)，計(jì)算在頂點(diǎn)處的目標(biāo)函數(shù)值。比較周?chē)噜忢旤c(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值大，如果為否，則該頂點(diǎn)就是最優(yōu)解的點(diǎn)或最優(yōu)解的點(diǎn)之一，否則轉(zhuǎn)到比這個(gè)點(diǎn)的目標(biāo)函數(shù)值更大的另一頂點(diǎn)，重復(fù)上述過(guò)程，一直到找出使目標(biāo)函數(shù)值達(dá)到最大的頂點(diǎn)為止。復(fù)習(xí)線性代數(shù)內(nèi)容:列向量x=(x1，x2，…，xn）T為n維列向量。xRn行向量x=(x1，x2，…，xn）為n維列向量。xRn矩陣(向量)運(yùn)算規(guī)則加減乘、求逆運(yùn)算

線性相關(guān)一組向量v1,…,vn,如果有一組不全為零的系數(shù)α1,…,αn,使得:α1v1+…+αnvn=0

則稱(chēng)v1,…,vn是線性相關(guān)的.線性無(wú)關(guān)一組向量v1,…,vn,如果對(duì)于任何數(shù)α1,…,αn,

若要滿(mǎn)足:α1v1+…+αnvn=0,則必有系數(shù)

α1=…=αn=0,(全為零)則稱(chēng)v1,…,vn線性無(wú)關(guān).矩陣A的秩設(shè)A為一個(gè)m×n階矩陣(m<n)若矩陣中最大線性無(wú)關(guān)列向量個(gè)數(shù)為k,則稱(chēng)矩陣A的秩為k,記為rank(A)=k.線性規(guī)劃解的概念線性規(guī)劃數(shù)學(xué)模型標(biāo)準(zhǔn)型矩陣式：

(1.6)(1.7)(1.8)，可行解：滿(mǎn)足約束條件(1.7)和非負(fù)條件(1.8)的解稱(chēng)為可行解?？尚杏颍嚎尚薪獾募稀Ｗ顑?yōu)解：滿(mǎn)足條件(1.6)的可行解。(L)運(yùn)籌學(xué)基礎(chǔ)第五講主講教師：鄭黎黎學(xué)時(shí)：48線性規(guī)劃解的概念基：設(shè)A是階系數(shù)矩陣()，秩A=m，則A中一定存在m個(gè)線性無(wú)關(guān)的列向量，稱(chēng)由m個(gè)線性無(wú)關(guān)的列向量構(gòu)成的可逆矩陣為問(wèn)題L的一個(gè)基，L最多有個(gè)基?；兞浚悍Q(chēng)與基B中的列向量對(duì)應(yīng)的變量為基變量，記為其余變量為非基變量，記為。，，線性規(guī)劃解的概念基解：在約束方程組(1.7）中令所有的非基變量，又因?yàn)閨B|，根據(jù)克來(lái)姆規(guī)則，由m個(gè)約束方程可解出m個(gè)基變量的唯一解。將這個(gè)解加上非基變量取0的值有稱(chēng)X為線性規(guī)劃問(wèn)題L的基本解?；窘獾姆橇惴至總€(gè)數(shù)小于等于

m，當(dāng)小于m時(shí)，則此基解是退化解，這種現(xiàn)象不多。，，線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型

和解的概念約束方程的解空間基本解可行解非可行解基可行解退化解

線性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系基可行解：若B對(duì)應(yīng)的基本解則稱(chēng)該解為基本可行解，稱(chēng)B為可行基。凸集及其頂點(diǎn)凸集：設(shè)C是n維歐式空間的一個(gè)點(diǎn)集，若任意兩點(diǎn)的連線上的一切點(diǎn)

(

),則稱(chēng)C為凸集。凸集的特征是：連接任意兩點(diǎn)的線段整個(gè)都在集合之中。凸集及其頂點(diǎn)頂點(diǎn)：設(shè)K是凸集，,若不能表示成任何兩點(diǎn)連線的內(nèi)點(diǎn)，則稱(chēng)為K的一個(gè)頂點(diǎn)?；径ɡ矶ɡ?：線性規(guī)劃問(wèn)題的可行域是一個(gè)凸集.設(shè)：則（1.9）因?yàn)椋?1.10)

所以：又因?yàn)椋核裕阂虼司€性規(guī)劃問(wèn)題的可行域是凸集。

基本定理引理1：線性規(guī)劃的可行解是基可行解的充要條件是的正分量所對(duì)應(yīng)的系數(shù)列向量線性獨(dú)立。證明：必要性：根據(jù)定義即可證得。充分性：設(shè)的k個(gè)正分量的系數(shù)列向量線性獨(dú)立，若，剛好構(gòu)成一個(gè)基，從而X就是相應(yīng)的基可行解；若，則當(dāng)秩A=m時(shí)，一定可以從A的剩余系數(shù)列向量中找到m-k個(gè)線性無(wú)關(guān)的列與構(gòu)成最大線性無(wú)關(guān)向量組，構(gòu)成線性規(guī)劃問(wèn)題的一個(gè)基，其對(duì)應(yīng)的基本可行解恰為。

基本定理定理2：線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)線性規(guī)劃問(wèn)題的可行域（凸集）頂點(diǎn)。證明：采用反證法

基本定理定理2：線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)線性規(guī)劃問(wèn)題的可行域（凸集）頂點(diǎn)。證明：采用反證法基本定理定理2：線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)線性規(guī)劃問(wèn)題的可行域（凸集）頂點(diǎn)。證明：采用反證法必要性：不失一般性，假設(shè)可行解前k個(gè)分量為正，故

(1.11)設(shè)是可行域的頂點(diǎn)，若不是基可行解則根據(jù)引理1，其正分量對(duì)應(yīng)的系數(shù)列向量線性相關(guān)，即存在一組不全為0的數(shù)，使得：

(1.12)

基本定理定理2：線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)線性規(guī)劃問(wèn)題的可行域（凸集）頂點(diǎn)。證明：采用反證法必要性：不失一般性，假設(shè)可行解前k個(gè)分量為正，故

(1.11)若不是基可行解則根據(jù)引理1，其正分量對(duì)應(yīng)的系數(shù)列向量線性相關(guān)，即存在一組不全為0的數(shù)，使得：

(1.12)

基本定理用一個(gè)非常小的正數(shù)乘（1.12）再分別與(1.11)相加減，這樣得到：令：因?yàn)槭且粋€(gè)非常小的正數(shù)，因此可以保證，即和是可行解。由和可以得到，即是和連線的中點(diǎn)，即不是可行域的頂點(diǎn)?；径ɡ沓浞中裕涸O(shè)X是基可行解，則必線性無(wú)關(guān)，若X不是可行域D的頂點(diǎn)，則存在，且，及有：

于是，對(duì)有則另外：由于線性無(wú)關(guān)故則，與相矛盾，因此X必是可行域的頂點(diǎn)。

基本定理充分性：若X不是可行域D的頂點(diǎn)，則存在，且，及有：

于是，對(duì)有則另外：則因，所以故線性相關(guān)，即X不是基可行解。

基本定理定理3：若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解（可行域頂點(diǎn)）是最優(yōu)解。證明：設(shè)X是最優(yōu)解，是可行域的k個(gè)頂點(diǎn)，若X不是頂點(diǎn)，則X可以表示為可行域k個(gè)頂點(diǎn)的凸組合，表示為：因此：基本定理另外，在所有頂點(diǎn)上必然會(huì)找到一個(gè)頂點(diǎn)，使CX(s)是所有CX(j)

中最大的，則，由此得到根據(jù)假設(shè)是最大值，所以只能是即目標(biāo)函數(shù)在頂點(diǎn)X(s)也取得最大值。，基本定理綜上，得到結(jié)論：線性規(guī)劃問(wèn)題的可行域?yàn)橥辜ǘɡ?）；凸集的每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)基可行解（定理2），基可行解的個(gè)數(shù)是有限的，當(dāng)然凸集的頂點(diǎn)個(gè)數(shù)也是有限的；若線性規(guī)劃有最優(yōu)解，必在可行域某頂點(diǎn)上達(dá)到，（定理3）亦即在有限個(gè)基可行解中間存在最優(yōu)解。單純形法迭代原理單純形法求解思路：

，初始基可行解是否是最優(yōu)解結(jié)束找一個(gè)較好基可行解NY由于基可行解數(shù)目有限（小于等于）因此，經(jīng)過(guò)有限次迭代即可找到最優(yōu)解。

，

確定下面線性規(guī)劃問(wèn)題的初始基可行解運(yùn)籌學(xué)基礎(chǔ)第六講主講教師：鄭黎黎學(xué)時(shí)：48，

確定下面線性規(guī)劃問(wèn)題的初始基可行解確定初始基可行解大M法：若給定問(wèn)題標(biāo)準(zhǔn)化后，系數(shù)矩陣中不存在m個(gè)線性無(wú)關(guān)的單位列向量，則在某些約束的左端加入非負(fù)變量（人工變量），使得變化后的系數(shù)矩陣中恰有m個(gè)線性無(wú)關(guān)的單位列向量，并且在目標(biāo)函數(shù)中減去這些人工變量與M的乘積（M是相當(dāng)大的一個(gè)正數(shù)）。對(duì)于變化后的問(wèn)題，取這m個(gè)單位列向量構(gòu)成的單位矩陣為初始基，該基對(duì)應(yīng)的解一定是基可行解。確定初始基可行解關(guān)于大M法的幾點(diǎn)結(jié)論:若原問(wèn)題存在最優(yōu)解X*，則變化后的問(wèn)題也存在最優(yōu)解（X*，0）且后者的最優(yōu)解就是原問(wèn)題的最優(yōu)解。若經(jīng)過(guò)單純形法迭代后變化后問(wèn)題的最優(yōu)解中含有不等于零的人工變量，則原問(wèn)題無(wú)可行解。

用M法確定下面線性規(guī)劃問(wèn)題的初始基可行解從一個(gè)基可行解轉(zhuǎn)換為

相鄰基可行解定義：兩個(gè)基可行解稱(chēng)為相鄰的，如果它們之間變換且僅變換一個(gè)基變量。設(shè)初始基可行解中的前m個(gè)為基變量，即：

（1.19）

帶入等式約束中

因是一個(gè)基，其他向量可用這個(gè)基的線形組合來(lái)表示，有

（1.２０）

+

（１.２２）從一個(gè)基可行解轉(zhuǎn)換為

相鄰基可行解乘

由式（1.22）找到滿(mǎn)足約束方程組

時(shí)是非負(fù)的。

從一個(gè)基可行解轉(zhuǎn)換為

相鄰基可行解

因，故由上述矩陣元素組成的行列式不為零，是一個(gè)基在上述增廣矩陣中進(jìn)行行的初等變換，將第行乘上（），再分別乘以（）加到各行上去，則增廣矩陣左半部變成為單位矩陣，又因故

從一個(gè)基可行解轉(zhuǎn)換為

相鄰基可行解

最優(yōu)性檢驗(yàn)和解的判別

將和分別帶入目標(biāo)函數(shù)得：（１．２５）

或

最優(yōu)性檢驗(yàn)和解的判別

（1）當(dāng)所有的時(shí)，表明現(xiàn)有頂點(diǎn)（基可行解）的目標(biāo)函數(shù)值比起相鄰各頂點(diǎn)（基可行解）的目標(biāo)函數(shù)值都大，根據(jù)線性規(guī)劃問(wèn)題的可行域是凸集的證明及凸集的性質(zhì)，可以判定現(xiàn)有頂點(diǎn)的基可行解即為最優(yōu)解。（2）當(dāng)所有的，又對(duì)某個(gè)非基變量有，且按式（1.24）可以找到，這表明可以找到另一個(gè)頂點(diǎn)（基可行解）目標(biāo)函數(shù)值也達(dá)到最大。由于該兩點(diǎn)連續(xù)的點(diǎn)也屬可行域內(nèi)的點(diǎn)，且目標(biāo)函數(shù)值相等，即該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。最優(yōu)性檢驗(yàn)和解的判別

（3）如果存在某個(gè)，又，由式（1.23）看出對(duì)任意的，均有，因而取值可為無(wú)限增大不受限制。由式（1.25）看到也可無(wú)限增大，表明線性規(guī)劃有無(wú)界解。（１．２５）

定理4（最優(yōu)性）對(duì)某基可行解其余，若所有，則該解為最優(yōu)解。定理5（無(wú)界解）若對(duì)某可行基B，若存在，則該線性規(guī)劃問(wèn)題無(wú)有限最優(yōu)解（或稱(chēng)無(wú)最優(yōu)解）。最優(yōu)性檢驗(yàn)和解的判別求解例1的一個(gè)基可行解和相應(yīng)的檢驗(yàn)數(shù)，并判斷其是否最優(yōu)解。(1.1c)目標(biāo)函數(shù)約束條件(1.1a)(1.1b)(1.1d)最優(yōu)性檢驗(yàn)和解的判別單純形表將式子（1.7a）和（1.6a）變化為，

增廣矩陣cjc1c2…cmcm+1…cnCBXBB-1bx1x2…xmxm+1…xnc1…cmx1…xma10…am00…0a1m+1

…

a1n

…1……………001amm+1…

amn00…0σm+1…

σnσj=cj-CBB-1PjB-1Pj≠Pj基變量值基變量基變量?jī)r(jià)值系數(shù)決策變量?jī)r(jià)值系數(shù)CB

XB

21000

B-1b

x1x2x3x4x50x315051000x424620100x551100121000解：表1-7c基的變換︱旋轉(zhuǎn)變換就是對(duì)單純形表中的元素做如下初等行變換，將一個(gè)非基變量xk旋入基變量中，同時(shí)將基變量xBl旋出，用xk取代xBl。設(shè)可行基B對(duì)應(yīng)的單純形表為{}表中，xk是非基變量，xBl是基變量運(yùn)籌學(xué)基礎(chǔ)第七講主講教師：鄭黎黎學(xué)時(shí)：48基的變換︱旋轉(zhuǎn)變換表中第l行都除以，即表中第i行（）元素減第l行對(duì)應(yīng)新元素的倍，即單純形表{}在上述初等行變換下變?yōu)閧}基的變換︱旋轉(zhuǎn)變換上述旋轉(zhuǎn)變換中：

——旋轉(zhuǎn)主元l——為旋轉(zhuǎn)行，k為旋轉(zhuǎn)列，旋轉(zhuǎn)行對(duì)應(yīng)的基變量xBl——旋出變量旋轉(zhuǎn)列對(duì)應(yīng)的非基變量xk——旋入變量CB

XB

21000B-1b

x1x2x3x4x50x315051000x424620100x551100121000表1-7cjCB

XB

21000B-1b

x1x2x3x4x5cj基的變換︱旋轉(zhuǎn)變換上述旋轉(zhuǎn)變換中：

——旋轉(zhuǎn)主元l——為旋轉(zhuǎn)行，k為旋轉(zhuǎn)列，旋轉(zhuǎn)行對(duì)應(yīng)的基變量xBl——旋出變量旋轉(zhuǎn)列對(duì)應(yīng)的非基變量xk——旋入變量由上面的例子可以看出，旋轉(zhuǎn)變換的實(shí)質(zhì)就是用一系列的初等行變換將主元列變?yōu)閱挝涣邢蛄?，其中主元變?yōu)?，主元列的其余元素都為零?；淖儞Q︱旋轉(zhuǎn)變換引理2若{}是以為基的單純形表，則在旋轉(zhuǎn)變換下得到的{}是以為基的單純形表。由引理2可知，對(duì)單純形表進(jìn)行旋轉(zhuǎn)變換就是實(shí)現(xiàn)基的變換，因而能從一個(gè)基本解求出另外一個(gè)基本解。如果按照一定規(guī)則選取旋入變量及旋出變量，就能保證基的變換始終在基可行解間進(jìn)行，而且目標(biāo)函數(shù)值不斷改善。單純形算法步驟1.確定初始基B和初始基可行解建立初始單純形表；2.檢查非基變量的檢驗(yàn)數(shù)，若所有的，則已經(jīng)得到最優(yōu)解計(jì)算停；否則求確定xk為旋入變量；3.若對(duì)于，則此問(wèn)題無(wú)有限最優(yōu)解，計(jì)算停；否則轉(zhuǎn)入步驟4；單純形算法步驟4.計(jì)算確定xBl為旋出變量。5.以為主元做旋轉(zhuǎn)變換得新的單純形表，轉(zhuǎn)步驟2。CB

XB

21000

B-1b

x1x2x3x4x50x315051000x424620100x551100121000解：表1-7cj

例5用單純形法求解下面的線性規(guī)劃問(wèn)題CB

XB

21000B-1b

x1x2x3x4x50x315051000x424620100x551100121000表1-7cjCB

XB

21000B-1b

x1x2x3x4x5cj01/602/614x120-1/301/301-1/604/601x500015015x30x5x4x3x2x1B-1b

00012

XBCB表1-8cjx5x4x3x2x1B-1b

00012

XBCBcj表1-9中所有j<=0,

最優(yōu)解X=(7/2,3/2,15/2,0,0);

最優(yōu)值Z=17/2.運(yùn)籌學(xué)基礎(chǔ)第八講主講教師：鄭黎黎學(xué)時(shí)：48單純形算法步驟

習(xí)題1計(jì)算下列線性規(guī)劃取為初始基為初始基可行解Ⅰcj6

400CBXBB-1bx1x2x3x400x3x41001202310[4]2016400Ⅰcj6

400CBXBB-1bx1x2x3x400x3x4100120231042016400Ⅱcjc1c2c3c4CBXBB-1bx1x2x3x406x3x14030021-1/211/201/4010-3/2Ⅱcjc1c2c3c4CBXBB-1bx1x2x3x406x3x140300[2]1-1/211/201/4010-3/2ⅢCc1c2c3c4CBXBB-1bx1x2x3x446x2x12020011/2-1/410-1/43/800-1/2-5/4

例6用單純形法求解下面的線性規(guī)劃問(wèn)題-M0-10x500010x6-M00-11-21x6-M0014M-2M-3101309x7-M011114x40x7x4x3x2x1

B-1b

-M010-3cjXBCB表1-10cj-M0-10x500010x6-M00-1[1]-21x6-M0014M-2M-3101309x7-M011114x40x7x4x3x2x1

B-1b

-M010-3cjXBCB表1-10cjx50x6-M

x7x4x3x2x1

B-1b

-M010-3cjXBCBcj運(yùn)籌學(xué)基礎(chǔ)第九講主講教師：鄭黎黎學(xué)時(shí)：48CBXBcj-30100-M-MB-1bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx76[6]0403-316M-304M+103M-4M0cj0x400011-1/2-1/2-1/20x2-3x11102/301/2-1/21/60x400011-1/2-1/2-1/20x23011/30001/3-3x11102/301/2-1/21/600303/2-M-3/2-M+1/2單純形法的進(jìn)一步討論

如果線性規(guī)劃問(wèn)題中的aij、bi或cj等參數(shù)值與這個(gè)代表M的數(shù)相對(duì)比較接近，或遠(yuǎn)遠(yuǎn)小于這個(gè)數(shù)字，由于計(jì)算機(jī)計(jì)算時(shí)取值上的誤差，有可能使計(jì)算結(jié)果發(fā)生錯(cuò)誤。為了克服這個(gè)困難，可以對(duì)添加人工變量后的線性規(guī)劃問(wèn)題分兩個(gè)階段來(lái)計(jì)算，稱(chēng)兩階段法。單純形法的進(jìn)一步討論兩階段法：第一階段（目的是求解該問(wèn)題的一個(gè)初始基可行解）：

求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問(wèn)題，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù)(一般取1)，在保持原問(wèn)題約束條件不變的情況下求這個(gè)目標(biāo)函數(shù)極小化時(shí)的解。顯然在第一階段中，當(dāng)人工變量取值為0時(shí)，目標(biāo)函數(shù)值也為0。這時(shí)候的最優(yōu)解就是原線性規(guī)劃問(wèn)題的一個(gè)基可行解。單純形法的進(jìn)一步討論兩階段法：如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原線性規(guī)劃問(wèn)題無(wú)可行解。第二階段：將第一階段得到的基可行解作為原問(wèn)題的初始基可行解，然后按照單純形法求解原問(wèn)題的最優(yōu)解。例6兩階段法第一階段：-10-10x500010x6-100-1[1]-21x6-10004-21013-19x7-1011114x40x7x4x3x2x1B-1b-10000

XBCB表1-11cj33-11x50-4-31-1x6-100-11-21x20004061040[6]6x7-1012033x40x7x4x3x2x1B-1b-10000XBCB表1-11請(qǐng)注意:第一階段的最優(yōu)解不是唯一的01/20-1/2x50-1-1/201/2x6-11/301/3103x20-100001/602/3011x10-1/210000x40x7x4x3x2x1B-1b-10000

XBCBcjcj3/203001/20-1/2x5001/3103x2002/3011x1-310000x40x4x3x2x1B-1b010-3

XBCB表1-12第二階段01/20-1/2x50-1-1/201/2x6-11/301/3103x20-100001/602/3011x10-1/210000x40x7x4x3x2x1B-1b-10000

XBCBcjcj3/203001/20-1/2x5001/3103x200[2/3]011x1-312000x40x4x3x2x1B-1b010-3

XBCB表1-12第二階段-3/43/4-1/4-1/2x50001-1/25/2x20000-9/20103/23/2x3110000x40x4x3x2x1B-1b0000