胡云權運籌學課件第一部分

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

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

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

1948年美國麻省理工學院

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

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

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

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

約束條件：

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

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

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

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

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

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

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

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

數(shù)學模型目標函數(shù)：

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

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

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

數(shù)學模型線性規(guī)劃問題數(shù)學模型的標準型：目標函數(shù)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(

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

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

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

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

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

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

(1.12)

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

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

(1.12)

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

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

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

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

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

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

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

，

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

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

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

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

（1.19）

帶入等式約束中

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

（1.２０）

+

（１.２２）從一個基可行解轉換為

相鄰基可行解乘

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

時是非負的。

從一個基可行解轉換為

相鄰基可行解

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

從一個基可行解轉換為

相鄰基可行解

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

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

或

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

（1）當所有的時，表明現(xiàn)有頂點（基可行解）的目標函數(shù)值比起相鄰各頂點（基可行解）的目標函數(shù)值都大，根據(jù)線性規(guī)劃問題的可行域是凸集的證明及凸集的性質(zhì)，可以判定現(xiàn)有頂點的基可行解即為最優(yōu)解。（2）當所有的，又對某個非基變量有，且按式（1.24）可以找到，這表明可以找到另一個頂點（基可行解）目標函數(shù)值也達到最大。由于該兩點連續(xù)的點也屬可行域內(nèi)的點，且目標函數(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的一個基可行解和相應的檢驗數(shù)，并判斷其是否最優(yōu)解。(1.1c)目標函數(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基的變換︱旋轉變換就是對單純形表中的元素做如下初等行變換，將一個非基變量xk旋入基變量中，同時將基變量xBl旋出，用xk取代xBl。設可行基B對應的單純形表為{}表中，xk是非基變量，xBl是基變量運籌學基礎第七講主講教師：鄭黎黎學時：48基的變換︱旋轉變換表中第l行都除以，即表中第i行（）元素減第l行對應新元素的倍，即單純形表{}在上述初等行變換下變?yōu)閧}基的變換︱旋轉變換上述旋轉變換中：

——旋轉主元l——為旋轉行，k為旋轉列，旋轉行對應的基變量xBl——旋出變量旋轉列對應的非基變量xk——旋入變量CB

XB

21000B-1b

x1x2x3x4x50x315051000x424620100x551100121000表1-7cjCB

XB

21000B-1b

x1x2x3x4x5cj基的變換︱旋轉變換上述旋轉變換中：

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

習題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運籌學基礎第九講主講教師：鄭黎黎學時：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單純形法的進一步討論

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

求解一個目標函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個正的常數(shù)(一般取1)，在保持原問題約束條件不變的情況下求這個目標函數(shù)極小化時的解。顯然在第一階段中，當人工變量取值為0時，目標函數(shù)值也為0。這時候的最優(yōu)解就是原線性規(guī)劃問題的一個基可行解。單純形法的進一步討論兩階段法：如果第一階段求解結果最優(yōu)解的目標函數(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