前言

關(guān)于線性規(guī)劃，在高中剛接觸時就感覺，好像最優(yōu)解都是在頂點取到，但是又不敢確定，畢竟這只是種感覺，并非通過數(shù)學(xué)證出，然后在接觸到運籌學(xué)中的單純形法之后，這一感覺才被確定下來，最優(yōu)解就是在頂點取到的，而且改法同時提出可行域的所有頂點可以由基可行解表示出來，這也就是說，我們只要討論所有基可行解就可以得到最優(yōu)解了。

相關(guān)概念

線性規(guī)劃的標(biāo)準(zhǔn)形式 特點：等式，大于等于0

可行解

可行域

基（討論對象是系數(shù)矩陣，下面對應(yīng)的四個定義都是對于未知量的取值的定義）

基變量 ：

非基變量：

基解：非基向量全部取0

基可行解：所有元素取值滿足大于零的基解

凸集

頂點：個人覺得這里結(jié)合線代進(jìn)行理解比較好，因為這里頂點其實本身就是一個向量，而頂點的意思就是說在可行域中不存在兩個點（可以當(dāng)成向量）的連線穿過該點，換成線性代數(shù)中話就是，頂點向量不能有可行域除了該點的其他向量線性表示。這種理解的好處就是你會發(fā)現(xiàn)這會與基可行解的正分量的系數(shù)列向量是線性無關(guān)的相呼應(yīng)（也有可能是我在扯淡）。你試想下，由系數(shù)矩陣組成的基剛好可以唯一確定一個點，而這個點剛好就是可行域的頂點。

單純形法的計算

確定初始基可行解

確定相鄰的基可行解

驗證最優(yōu)值

計算總思路：這種方法將求最優(yōu)值直接轉(zhuǎn)換為對系數(shù)的討論，通過對系數(shù)的討論來得到最優(yōu)值。在第二步進(jìn)行迭代時候，由于要通過矩陣變換來得到單位矩陣，這個過程就是將找最優(yōu)解的過程，改變?yōu)榫仃囎儞Q。從第二步到第三步的所有計算過程，無非就是想通過代數(shù)的運算將最優(yōu)值直接和系數(shù)掛上鉤（P25~P26），可以看到最終通過更換單位矩陣中對應(yīng)的變量，可以通過計算

來直接判斷最優(yōu)值（解釋的不是很清楚，但是要知道這么長的兩頁的意圖是是什么）

所代表的是替換變量后減去替換目標(biāo)前（這前代表的就是我們當(dāng)前要檢驗的）

關(guān)鍵的點：第二步怎么換，換哪個

由

決定，取所有正的中最大的一個對應(yīng)的變量（設(shè)為第k列），之后就要確定被替換的變量了，這時需要用等式 中的右邊除以左邊變量的正系數(shù)，并取這一系列比值中的最小值對應(yīng)的元素為主元素，由此主元素的位置可以確定被替換變量的列數(shù)（就是單位矩陣中非零元素和此元素同行的那一列變量）

從兩階段法中，加深了對于單純形法的理解，在單純形法的第一個計算步驟中可以知道，只要可以得到初始基可行解就可以進(jìn)一步往下推到，而之前提到的單位基只不過這個方法中的一種而已，基變量在單純形法中對應(yīng)的基都是單位矩陣。

松弛變量在目標(biāo)函數(shù)中的系數(shù)為0

相當(dāng)于一面一面切

總結(jié)

以上是生活随笔為你收集整理的单纯形法求最小值的检验数_【运筹学】单纯形法（笔记和思考）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。