正文

運(yùn)籌學(xué)單純形法(單純形法各個(gè)步驟詳解)

shiyingbao

運(yùn)籌學(xué)單純形法(單純形法各個(gè)步驟詳解)

R帷幄』原創(chuàng)

作者:臧永森

作者:臧永森,清華大學(xué)工業(yè)工程系在讀博士,研究方向:運(yùn)籌優(yōu)化算法的設(shè)計(jì)與應(yīng)用、數(shù)據(jù)統(tǒng)計(jì)分析、大數(shù)據(jù)技術(shù)與應(yīng)用,戚銘堯老師團(tuán)隊(duì)


編者按

此文屬于電子書線性規(guī)劃專題第三章單純形法的內(nèi)容。在前面的文章中,我們?yōu)橐雴渭冃畏ń榻B了可行域、最優(yōu)解、可行解、基解、基可行解等基礎(chǔ)概念,也闡述了它們之間的關(guān)系(具體可見文章《在單純形法之前》)。在明確了這些基本概念之后,這一節(jié)我們來(lái)探討單純形法的思想邏輯和求解步驟。

我們已經(jīng)知道,優(yōu)化問題的最優(yōu)解一定是基可行解,那么如何找到最優(yōu)的基可行解就是最優(yōu)化問題的求解思路。因此,單純形法在求解過程,就是不斷地尋求變量出入基的循環(huán)迭代過程,每次迭代都達(dá)到降低目標(biāo)函數(shù)值(或增大目標(biāo)函數(shù)值)的目的,最終得到最優(yōu)解。那么在迭代過程中,如何使解在改善過程中向著最優(yōu)解的方向盡快地收斂呢?我們下面用比較直觀的方式來(lái)解析這個(gè)過程。

單純形法的基本思想與邏輯

本文采用的思路參考Dimitris Bertsimas和 John N. Tsitsiklis在 Introduction to Linear Optimization一書中提出的方法[1]。考慮如下標(biāo)準(zhǔn)線性規(guī)劃問題:

優(yōu)化 |運(yùn)籌學(xué)線性規(guī)劃單純形法之求解


我們將矩陣A拆分為n個(gè)列元素:A1, A2, A3,, An,那么我們可以將問題看成是滿足非負(fù)約束(4)、凸約束(3)以及約束(5)的最小化問題。

優(yōu)化 |運(yùn)籌學(xué)線性規(guī)劃單純形法之求解


結(jié)合式(3)和(5)我們可以看出,原優(yōu)化問題轉(zhuǎn)化為求解能夠構(gòu)造出(b, z)的使得z值最小的關(guān)于(Ai, ci)的凸組合。為了更好地理解它們之間的幾何關(guān)系,我們將一個(gè)平面視作包含A的一個(gè)m維空間,將與ci相關(guān)的成本項(xiàng)看作是一維垂直數(shù)軸,這時(shí)每一個(gè)點(diǎn)(Ai, ci)都可以唯一在該三維坐標(biāo)系中表示出來(lái),如圖1所示:

優(yōu)化 |運(yùn)籌學(xué)線性規(guī)劃單純形法之求解


圖1 線性規(guī)劃問題1—4的“列幾何”圖示


我們將(b, z)同樣視為一條垂直線表示在圖1中,這條垂直線叫做需求線,其與平面的交點(diǎn)是(b, 0)點(diǎn)。需求線與(Ai, ci)的凸組合在幾何上有一定的關(guān)系,它們或相交或相離,這取決于我們對(duì)(Ai, ci)凸組合的選取,選取的凸組合不一樣,幾何關(guān)系就不同。很容易能理解,如果需求線和凸組合相交,說(shuō)明(b, z)可以用相應(yīng)的凸組合表示出來(lái),也就表明這個(gè)凸組合就是原問題的一個(gè)可行解;而如果相離,則說(shuō)明這個(gè)凸組合不滿足能夠表達(dá)(b, z)的條件,也就不是原問題的可行解。所有的凸組合構(gòu)成了一個(gè)凸包,如果需求線能夠與凸包相交,那么原問題就存在可行解,如果需求線不能與凸包相交,說(shuō)明原問題無(wú)解。進(jìn)一步將圖1抽象,得到圖2,從圖中我們可以看出,點(diǎn)I、H、G就是三個(gè)不同的凸組合與需求線的交點(diǎn),也就是原問題的三個(gè)可行解。

優(yōu)化 |運(yùn)籌學(xué)線性規(guī)劃單純形法之求解


圖2 可行解的“列幾何”圖示


經(jīng)過上面的分析我們得知,要找到最優(yōu)解,就是找到與需求線相交的使得z值最小的凸組合。那么如何找這樣的凸組合呢?首先引入兩個(gè)定義:

  1. 如果向量

優(yōu)化 |運(yùn)籌學(xué)線性規(guī)劃單純形法之求解


  1. 是線性獨(dú)立的,那么向量

優(yōu)化 |運(yùn)籌學(xué)線性規(guī)劃單純形法之求解


  1. 被稱為Rn空間中的仿射獨(dú)立或者仿射無(wú)關(guān),其中k<=n。

  2. 在Rn空間中由k+1個(gè)仿射無(wú)關(guān)向量組成的凸包被稱為k維單純形。


對(duì)模型(1—4)來(lái)說(shuō),總共有m+1個(gè)等式約束,假定約束系數(shù)矩陣是滿秩的,那么一個(gè)基可行解將對(duì)應(yīng)m+1個(gè)線性獨(dú)立的列向量,也就意味著有m+1個(gè)基點(diǎn),根據(jù)上述定義,由基點(diǎn)之間的差向量線性獨(dú)立可以得到其仿射獨(dú)立,由此可以知道它們組成的凸包是m維單純形。

假設(shè)m維單純形與需求線相交于點(diǎn)(b, z),由(5)知用來(lái)表示(b, z)的線性組合的權(quán)重向量是xi ,該向量就是一個(gè)基可行解,也就對(duì)應(yīng)我們上節(jié)所分析的基變量的內(nèi)容,當(dāng)然z就是相應(yīng)的目標(biāo)函數(shù)值。我們用圖2做一個(gè)解釋,陰影區(qū)域的三角形CDF,就是一個(gè)2維單純形,其與需求線的交點(diǎn)H點(diǎn)就是基可行解,點(diǎn)C、D、F是基點(diǎn)。

我們對(duì)二維單純形CDF做一些改變,會(huì)發(fā)現(xiàn)相應(yīng)的z值(與需求線的交點(diǎn))也會(huì)變化,比如我們令基點(diǎn)B取代基點(diǎn)F,單純形變?yōu)锽CD,這時(shí)可行解變?yōu)镮點(diǎn),相應(yīng)的z值較之前有所增長(zhǎng)。類似地,若點(diǎn)E取代點(diǎn)C成為基點(diǎn),單純形由CDF變?yōu)镋DF,可行解就出現(xiàn)在G點(diǎn),此時(shí)z值有所減小。從這些變化中我們找出這樣一個(gè)規(guī)律,當(dāng)且僅當(dāng)新加入基的點(diǎn)在當(dāng)前單純形平面上方(下方)時(shí),所得的交點(diǎn)(即可行解)對(duì)應(yīng)的z值會(huì)增大(減小)。

如果我們更加形象地描述這個(gè)基點(diǎn)變化的過程,就如同用手抓住單純形CDF的基點(diǎn)C,保持D點(diǎn)和F點(diǎn)固定不變,用力向上拉(向下拉),將C點(diǎn)拉到B點(diǎn)(E點(diǎn)),也就產(chǎn)生了新的單純形BCD(EDF)。單純形法的旋轉(zhuǎn)迭代過程,就是不斷找到基點(diǎn)向上拉(向下拉)到新基點(diǎn)形成新單純形的過程。

單純形法的求解過程

簡(jiǎn)單總結(jié)一下單純形法的求解原理。先找到一個(gè)基可行解,然后從非基解中找一個(gè)比較有前途的點(diǎn)入基,替換掉基可行解中有待改善的基點(diǎn),從而達(dá)到改善目標(biāo)函數(shù)的目的,如此重復(fù)迭代,直至無(wú)法找到可以入基的點(diǎn)。