最優(yōu)化問題 例題

1、第二章 線性規(guī)劃關于用單純形法解線性規(guī)劃：1. 單純形法涉及兩個規(guī)則：(1)進基規(guī)則判別數(shù)大于零，保證函數(shù)值不升；(2)退基規(guī)則最小比值，保證新解的容許性.2. 書面通常采用表上作業(yè)單純形表形式解題.3. 單純形法解線性規(guī)劃(書面)實質(zhì)上是單純形表的轉(zhuǎn)換過程.4. 單純形法本質(zhì)上是求解具有標準容許基且右端項非負的典范線性規(guī)劃的算法.典范線性規(guī)劃因其含有標準容許基，所以由它的準備表（原始數(shù)據(jù)表）容易得到第一張單純形表，單純形法于是可以啟動. 過程如下：5. 一般來說，解線性規(guī)劃主要分兩大步： 第一步，將線性規(guī)劃化為標準形式（當線性規(guī)劃為標準形式時不需要這一步）；這里所說的標準形式是指極小化問題，

2、主約束是右端項非負的等式約束，且變量非負.第二步，對線性規(guī)劃的標準形式啟動兩階段單純形法(當線性規(guī)劃的標準形式是典范線性規(guī)劃時不需要第一階段，直接進入第二階段). 第一階段的目的是變換出與主約束等價的G-J方程組，第二階段是解與原線性規(guī)劃等價的標準線性規(guī)劃，即解原線性規(guī)劃.6. 單純形法的基本理論定理2.9(最優(yōu)性準則) 在標準線性規(guī)劃中, 若所有變量關于容許基的判別數(shù)皆非正，則關于基的基本容許解是最優(yōu)解.定理2.11（單純形法基本定理） 對于標準線性規(guī)劃 (1)假設：）是容許基，關于的基本容許解是非退化的，即；）非基變量的判別數(shù)；），是用公式（2.36）確定的一個行標；）用替換中的，而其余基

3、向量不變，構成矩陣.那么，是容許基，且關于的基本容許解的目標函數(shù)值小于關于的基本容許解的目標函數(shù)值.定理2.12 在標準線性規(guī)劃(1)中，假設：）是容許基；）非基本變量的判別數(shù)； ）.那么線性規(guī)劃(1)存在可以使目標函數(shù)值任意減小的容許解.推論2.14 典范線性規(guī)劃或者存在最優(yōu)基本容許解，或者解無界.7. 注意事項. 在例題中說明.例 求解線性規(guī)劃解 引入變量，將其化為標準形(* 這里所說線性規(guī)劃的標準形是指，求極小問題、右端項非負、變量非負)第一階段 增加人工變量，解輔助LP問題1 -1 6 -1 0 1 01 1 2 0 -1 0 1210 0 0 0 0 -1 -102* 0 8 -1

4、-1 0 030 -2 4 -1 1 1 -11 1 2 0 -1 0 1110 -2 4* -1 1 0 -210 1 1 2 0 0 0 0 0 0 -1 -10第一階段結束，得到輔助問題的最優(yōu)值為0，最優(yōu)解，從而得到與原問題等價的標準線性規(guī)劃的一個基本可行解. (*輔助LP問題是一個總有最優(yōu)解的典范線性規(guī)劃問題，即不會發(fā)生解無界. 若最優(yōu)值大于零，則表明原問題無解；若最優(yōu)值等于零，則最終一定會得到與標準形式的主約束等價的G-J方程組，即得到與標準形式等價的典范形式，于是可以啟動第二階段.)(*產(chǎn)生一張單純形表的原則是，主約束的系數(shù)矩陣中含有單位矩陣，所有基變量的判別數(shù)為零.)(*單純形表轉(zhuǎn)換必須施行行運算.)(解輔助LP，單純形表轉(zhuǎn)換的根本目標是讓人工變量全部退基. 所以在選進基變量與退基變量時，以讓人工變量退基為第一選擇，其次考慮計算的難易程度.)(*選判別數(shù)小于零的變量進基，可保證函數(shù)值不升；選比值最小元素所對應的變量退基，可保證新解的容許性.)第二階段 求解原問題 0 1 1 2 0 -5 0 -21 0 0 00