線性規(guī)劃問題的單純形算法研究

【摘要】線性規(guī)劃（LP）是運(yùn)籌學(xué)中較早發(fā)展起來并已經(jīng)成熟廣泛地應(yīng)用于各個(gè)領(lǐng)域的一個(gè)重要數(shù)學(xué)理論和方法.線性規(guī)劃是研究在存在線性約束條件下目標(biāo)函數(shù)的最優(yōu)解或極值問題.單純形算法是線性規(guī)劃算法中發(fā)展最早、應(yīng)用最廣泛的算法，本文闡述了單純形算法的基本算法及其發(fā)展.

【關(guān)鍵詞】運(yùn)籌學(xué)；線性規(guī)劃；單純形算法

一、線性規(guī)劃簡(jiǎn)介

線性規(guī)劃研究的主要內(nèi)容為在一定的約束條件下，如何合理地安排人力、物力等各項(xiàng)資源以獲得最優(yōu)最好的經(jīng)濟(jì)效果.從數(shù)學(xué)層面來說即求解線性目標(biāo)函數(shù)在特定線性約束條件下的最大或最小值的極值問題.線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，早在1832年法國數(shù)學(xué)家傅里葉便提出了線性規(guī)劃的想法，經(jīng)過近200年的發(fā)展，已經(jīng)廣泛地運(yùn)用在軍事管理、經(jīng)濟(jì)運(yùn)營(yíng)和工程技術(shù)等領(lǐng)域＼[1＼].

二、單純形算法

單純形算法最早是在1947年由美國數(shù)學(xué)家G.B.Dantzig提出，一經(jīng)提出便成為了線性規(guī)劃問題的基本求解方法，為線性規(guī)劃的發(fā)展奠定了基礎(chǔ).單純形算法的基本思路是先求得一個(gè)初始基本可行解，并以這個(gè)初始基本可行解在可行域中對(duì)應(yīng)的頂點(diǎn)為出發(fā)點(diǎn)，根據(jù)最優(yōu)判別準(zhǔn)則判斷此基本可行解是否為最優(yōu)解，如果不是則沿著可行域的某個(gè)可行下降邊方向轉(zhuǎn)換到一個(gè)相鄰的“更好”極點(diǎn)，即得到一個(gè)新的基可行解，并使目標(biāo)函數(shù)值不增，如此反復(fù)迭代，直至找到原問題的最優(yōu)解或判斷原問題無界或判斷原問題不可行＼[2＼].針對(duì)于單純形算法，目前也出現(xiàn)了許多改進(jìn)的方法.

1.單純形的基本算法

對(duì)于標(biāo)準(zhǔn)型的線性規(guī)劃問題：minz=∑n1j=1CjXj

st∑n1j=1aijxj=bj（i=1，2，…，m）

xj≥0（j=1，2，…，n）

單純形算法的基本步驟為：

（1）找出初始可行基B，確定初始基可行解，建立初始單純形表（如表1-1）.

表1-1單純形表

1cj11c11…1cm1…1cj1…1cnCB1基1b1x11…1xm1…1xj1…1xnc1

c2

…

cm1x1

x2

…

xm1b1

b2

…

bm11

0

…

01…

…

…

…10

0

…

11…

…

…1a1j

a2j

…

amj1…

…

…

…1a1n

a2n

…

amn1cj-zj1101…101…1cj-∑m1i=1ciaij1…1cn-∑m1i=1ciaij（2）檢驗(yàn)各非基變量xj的檢驗(yàn)數(shù)為σj=cj-∑ni=1ciaij.若其中σj≤0，j=m+1，…，n則代表已經(jīng)得到最優(yōu)解，可停止計(jì)算，若σj>0，j=m+1，…，n，并且在其中有σk對(duì)應(yīng)的xk的數(shù)列向量pk≤0，則表示此問題無界，可停止計(jì)算.

（3）以θ規(guī)則θ=minbj1aikaik>0，i=1，2，…，m=b11aik確定換出向量.

（4）進(jìn)行迭代運(yùn)算，把所對(duì)應(yīng)的數(shù)列向量轉(zhuǎn)變?yōu)镻B1得到新的基，對(duì)應(yīng)這個(gè)基可以找出一個(gè)新的基可行解，并相應(yīng)地可以畫出一個(gè)新的單純形表（表1-2）.

（5）重復(fù)迭代運(yùn)算及判定過程，就能得到最優(yōu)解或判斷出無有限最優(yōu)解.

表1-2初始單純形表

1cj11c11…1cr1…1cm1…1cj1…1ck1…CB1基1b1x11…1xr1…1xm1…1xj1…1xk1…c1