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

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

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

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

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

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

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

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

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

約束條件：

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

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

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

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

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

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

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

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

份

1

2

3

4

所需倉庫面積

15

10

20

12

合同租賃期限

1個月

2個月

3個月

4個月

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

2800

4500

6000

7300

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(

),則稱C為凸集。凸集的特征是：連接任意兩點的線段整個都在集合之中。凸集及其頂點頂點：設(shè)K是凸集，,若不能表示成任何兩點連線的內(nèi)點，則稱為K的一個頂點。基本定理定理1：線性規(guī)劃問題的可行域是一個凸集.設(shè)：則（1.9）因為：(1.10)

所以：又因為：所以：因此線性規(guī)劃問題的可行域是凸集。

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

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

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

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

(1.12)

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

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

(1.12)

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

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

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

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

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

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

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

，

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

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

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

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

（1.19）

帶入等式約束中

因是一個基，其他向量可用這個基的線形組合來表示，有

（1.２０）

+

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

相鄰基可行解乘

由式（1.22）找到滿足約束方程組

時是非負(fù)的。

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

相鄰基可行解

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

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

相鄰基可行解

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

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

或

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

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

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

定理4（最優(yōu)性）對某基可行解其余，若所有，則該解為最優(yōu)解。定理5（無界解）若對某可行基B，若存在，則該線性規(guī)劃問題無有限最優(yōu)解（或稱無最優(yōu)解）。最優(yōu)性檢驗和解的判別求解例1的一個基可行解和相應(yīng)的檢驗數(shù)，并判斷其是否最優(yōu)解。(1.1c)目標(biāo)函數(shù)約束條件(1.1a)(1.1b)(1.1d)最優(yōu)性檢驗和解的判別單純形表將式子（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基變量值基變量基變量價值系數(shù)決策變量價值系數(shù)CB

XB

21000

B-1b

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

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

XB

21000

B-1b

x1x2x3x4x50x315051000x424620100x551100121000解：表1-7cj

例5用單純形法求解下面的線性規(guī)劃問題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.運籌學(xué)基礎(chǔ)第八講主講教師：鄭黎黎學(xué)時：48單純形算法步驟

習(xí)題1計算下列線性規(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ī)劃問題-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運籌學(xué)基礎(chǔ)第九講主講教師：鄭黎黎學(xué)時：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ī)劃問題中的aij、bi或cj等參數(shù)值與這個代表M的數(shù)相對比較接近，或遠(yuǎn)遠(yuǎn)小于這個數(shù)字，由于計算機計算時取值上的誤差，有可能使計算結(jié)果發(fā)生錯誤。為了克服這個困難，可以對添加人工變量后的線性規(guī)劃問題分兩個階段來計算，稱兩階段法。單純形法的進(jìn)一步討論兩階段法：第一階段（目的是求解該問題的一個初始基可行解）：

求解一個目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個正的常數(shù)(一般取1)，在保持原問題約束條件不變的情況下求這個目標(biāo)函數(shù)極小化時的解。顯然在第一階段中，當(dāng)人工變量取值為0時，目標(biāo)函數(shù)值也為0。這時候的最優(yōu)解就是原線性規(guī)劃問題的一個基可行解。單純形法的進(jìn)一步討論兩階段法：如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有非零的人工變量，表明原線性規(guī)劃問題無可行解。第二階段：將第一階段得到的基可行解作為原問題的初始基可行解，然后按照單純形法求解原問題的最優(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請注意:第一階段的最優(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