線性規(guī)劃問題的解第一頁，共二十八頁，2022年，8月28日最優(yōu)解：若基本可行解又是最優(yōu)解（也稱基本最優(yōu)解），這個基就稱為最優(yōu)基（optimalbasis）。基本解：對于基,令非基變量為零,求得滿足（1-13）的解，稱為基對應(yīng)的基本解（basicsolution）。基本可行解：滿足（1-14）的基本解稱為基本可行解（basicfeasiblesolution）；基本可行解所對應(yīng)的基稱為可行基（feasiblebasis）。第二頁，共二十八頁，2022年，8月28日

二.解的性質(zhì)

在右圖中設(shè)線段長度與之比為，由此得

o第三頁，共二十八頁，2022年，8月28日第四頁，共二十八頁，2022年，8月28日線性規(guī)劃問題的幾個定理定理1-4線性規(guī)劃問題有可行解,必有基本可行解；有最優(yōu)解,必有基本最優(yōu)解。定理1-1線性規(guī)劃問題的可行域是凸集。定理1-2A為線性規(guī)劃問題可行域的極點的充要條件是的A正分量對應(yīng)的系數(shù)列向量線性無關(guān)。（證明從略）。

定理1-3A是可行域的極點的充要條件是它為基本可行解。（證明從略。）第五頁，共二十八頁，2022年，8月28日綜上所述,我們在理論上得到了線性規(guī)劃問題的以下結(jié)論：線性規(guī)劃問題的可行域是一凸集（包括有界凸集和無界凸集）；線性規(guī)劃問題的每個基本可行解對應(yīng)著可行域的一個極點（頂點）；若線性規(guī)劃問題有最優(yōu)解,必在可行域的某一極點上得到。由此可見,我們只需在基本可行解中尋求最優(yōu)解。如何有效地尋求最優(yōu)解,這就是下節(jié)要介紹的單純形法。

第六頁，共二十八頁，2022年，8月28日§1-5單純形法一、單純形法的基本思路如果線性規(guī)劃問題存在最優(yōu)解，一定有一個基本可行解是最優(yōu)解。因此單純形法迭代的基本思路是：先找出一個基本可行解，判斷其是否為最優(yōu)解，如為否，則轉(zhuǎn)換到相鄰的基本可行解，并使目標函數(shù)值不斷增大，一直找到最優(yōu)解為止。

第七頁，共二十八頁，2022年，8月28日1、確定初始基可行解

max(1-17)

在約束條件（1-18）式的變量的系數(shù)矩陣中總會存在一個單位矩陣，不妨設(shè)為

(1-20)第八頁，共二十八頁，2022年，8月28日式中稱為基向量,同其對應(yīng)的決策變量稱為基變量,模型中的其它變量稱為非基變量。在(1-18)式中令所有非基變量等于零,即可找到一個解

X=(，)T=(b1,…,bm,0,…,0)T因有b≥0,故X滿足約束(1-19),是一個基本可行解記為又稱初始基本可行解。2、從一個基本可行解轉(zhuǎn)換為相鄰的基本可行解設(shè)初始基本可行解中的前m個為基變量,即第九頁，共二十八頁，2022年，8月28日經(jīng)一系列變換得第十頁，共二十八頁，2022年，8月28日3、最優(yōu)性檢驗和解的判別第十一頁，共二十八頁，2022年，8月28日（1-24）式中因,所以只要,就有。通常簡寫為或,它是對線性規(guī)劃問題的解進行最優(yōu)性檢驗的標志第十二頁，共二十八頁，2022年，8月28日第十三頁，共二十八頁，2022年，8月28日二、單純形法的矩陣描述在線性規(guī)劃問題的標準型：Max

第十四頁，共二十八頁，2022年，8月28日中，不妨設(shè)是一個可行基，則系數(shù)矩陣Ａ可分塊為（Ｂ，Ｎ）。對應(yīng)于Ｂ的基變量為，，非基變量為，Ｎ＝。并令，其中為基變量的系數(shù)列向量，N為非基變量的系數(shù)列向量。于是原問題可化為第十五頁，共二十八頁，2022年，8月28日即對約束方程兩邊同左乘以，得 =，并代入目標函數(shù)，得第十六頁，共二十八頁，2022年，8月28日令非基變量=0得=,從而相應(yīng)的基本可行解為目標函數(shù)取值為又由于,故有第十七頁，共二十八頁，2022年，8月28日將及Z的表達式又可寫成令，，則又有+=+第十八頁，共二十八頁，2022年，8月28日第四步：重復(fù)第二、三兩步，一直到計算結(jié)束為止。

三、單純形法的計算步驟根據(jù)上節(jié)中講述的原理,單純形法的計算步驟如下：第一步：求初始基本可行解,列出初始單純形表。第二步：最優(yōu)性檢驗。第三步：從一個基本可行解轉(zhuǎn)換到相鄰的目標函數(shù)值更大的基本可行解，列出新的單純形表。

第十九頁，共二十八頁，2022年，8月28日一、大M法

在上一節(jié)例1-9中，化為標準形式后約束條件的系數(shù)矩陣中含有單位矩陣，以此作初始基，使求初始基可行解和建立初始單純形表都十分方便。但時常化為標準形后的約束條件的系數(shù)矩陣中不存在單位矩例1-10用單純形法求解線性規(guī)劃問題

§1-6.初始可行基的求法

第二十頁，共二十八頁，2022年，8月28日解先將其化成標準形有MaxMax第二十一頁，共二十八頁，2022年，8月28日 這種情況下，可以通過添加兩列單位向量，使連同約束條件中的向量構(gòu)成單位矩陣。

是人為添加上去的，它相當于在上述問題的約束條件（1-34）中添加變量，約束條件(1-35)中添加變量，變量相應(yīng)稱為人工變量。由于約束條件（1-34）（1-35）在添加人工變量前已是等式為使這些等式得到滿足，因此在最優(yōu)解中人工變量取值必須為零。為此，令目標函數(shù)中人工變量的系數(shù)為任意大的負值，用“-M”代表。7p第二十二頁，共二十八頁，2022年，8月28日“-M”稱為“罰因子”，即只要人工變量取值大于零，目標函數(shù)就不可能實現(xiàn)最優(yōu)。因而添加人工變量后，例1-10的數(shù)學模型的標準形式就變?yōu)閙ax 該模型中與對應(yīng)的變量為基變量，令非基變量等于零，即得到初始基可行解,并列出初始單純形表。在單純形法迭代運算中，M可當作一個數(shù)學符號一起參加運算。檢驗數(shù)中含M符號的項，當M的系數(shù)為正時，該檢驗數(shù)為正，當M的系數(shù)為負時，該項檢驗數(shù)為負。第二十三頁，共二十八頁，2022年，8月28日

例1-10添加人工變量后，用單純形法求解的過程見下頁表1-8。最優(yōu)解為：

二、

兩階段法 用大M法處理人工變量，在用手工計算求解時不會碰到麻煩。但用電子計算機求解時，對M就只能在計算機內(nèi)輸入一個機器最大字長的數(shù)字。如果線性規(guī)劃問題中的或等參數(shù)值與這個代表M的數(shù)相對比較接近，或遠遠小于這個數(shù)字，由于計算機計算時取值上的誤差，有可能使計算結(jié)果發(fā)生錯誤。為了克服這個困難，可以對添加人工變量后的線性規(guī)劃問題分兩個階段來計算，稱為兩階段法。第二十四頁，共二十八頁，2022年，8月28日表1-8-30100-M-M0-M-M4191111000001[1]1-1-11-200003-3-2M4M10-M004130211-10313-21-10-1106[6]0403-3100-M-3+6M04M+103M-4M01-1/21第二十五頁，共二十八頁，2022年，8月28日入基出基原則首先是檢驗數(shù)即單純形表中系數(shù)矩陣的第列的價值系數(shù)減去第列元素乘以對應(yīng)行所在的基的價值系數(shù)的和的差。當目標函數(shù)是求max時，大者對應(yīng)的列所在的變量為入基變量，如果有幾個檢驗數(shù)一樣大，且是最大者，取腳標小的變量為入基變量；當目標函數(shù)是求min時，小者為入基變量。由于第二十六頁，共二十八頁，2022年，8月28日續(xù)表

-3110[2/3]01/2-1/21/63/203011/30001/39000001-1/21/2-1/2-00303/2-M-3/2-M+1/213/23/20103/4-3/41/4000001-1/21/2-1/205/2-1/2100-1/41/41/4-9/2000-3/4-M+3/4-M-1/4第二十七頁，共二十八頁，2022年，8月28日兩階段法的第一階段是先求解一個目標函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個正的常數(shù)（一般取1），夠成新的目標函數(shù)，在保持原問題約束條件不變的情況下求這個目標