線性規(guī)劃最優(yōu)解研究

林慧杰

摘要：線性規(guī)劃是一門(mén)研究如何使用最少的人力、物力和財(cái)力去最優(yōu)地完成科學(xué)研究、工業(yè)設(shè)計(jì)、經(jīng)濟(jì)管理中實(shí)際問(wèn)題的專(zhuān)門(mén)科學(xué)。本文在通過(guò)實(shí)際問(wèn)題引出并介紹了線性規(guī)劃問(wèn)題的基本概念后，基于MATLAB軟件詳細(xì)研究了單純形法求解線性規(guī)劃問(wèn)題。最后通過(guò)實(shí)際問(wèn)題提到了線性規(guī)劃的不完備之處，以上理論對(duì)于很多實(shí)際問(wèn)題都有著一定的幫助，所以本文具有一定的實(shí)用性。

關(guān)鍵詞：線性規(guī)劃；單純形法； MATLAB軟件

1引言

在現(xiàn)實(shí)經(jīng)濟(jì)活動(dòng)中我們不斷碰到諸如此類(lèi)的問(wèn)題，什么是最好的決策或者最佳的方案。例如企業(yè)在外在條件不變的情況下，如何通過(guò)改進(jìn)生產(chǎn)計(jì)劃，合理安排人、物和資源，使得成本最低或者收益最大。這些相關(guān)問(wèn)題都可以建立一些數(shù)學(xué)模型，轉(zhuǎn)化為運(yùn)籌學(xué)相關(guān)問(wèn)題，通過(guò)數(shù)學(xué)運(yùn)算得到最佳解決方案。

本篇文章將著重于介紹運(yùn)籌學(xué)方法中的線性規(guī)劃問(wèn)題理論以及基于MATLAB軟件的求解。線性規(guī)劃作為運(yùn)籌學(xué)的一個(gè)重要分支，是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法，也是研究線性約束條件下線性目標(biāo)函數(shù)的極值問(wèn)題的數(shù)學(xué)理論和方法。它是運(yùn)籌學(xué)的一個(gè)重要分支，廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營(yíng)管理和工程技術(shù)等方面。為合理地利用有限的人力、物力、財(cái)力等資源作出的最優(yōu)決策，提供科學(xué)的依據(jù)。

2線性規(guī)劃問(wèn)題及其基本概念

2.1 線性規(guī)劃標(biāo)準(zhǔn)形式

3純形法求解線性規(guī)劃問(wèn)題

高中時(shí)期便接觸過(guò)圖解法解簡(jiǎn)單的線性規(guī)劃問(wèn)題，但是圖解法雖然直觀、簡(jiǎn)便，但當(dāng)變量數(shù)多余三個(gè)以上時(shí)則無(wú)能為力。所以將線性規(guī)劃的求解在軟件上實(shí)現(xiàn)就顯得尤為重要。本文將會(huì)重點(diǎn)介紹其中之一的單純形法以及其在實(shí)際中的應(yīng)用。

3.1單純形法的基本思想

單純形法的基本思想是先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解，再鑒別；若仍不是，則再轉(zhuǎn)換，按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問(wèn)題的最優(yōu)解。如果問(wèn)題無(wú)最優(yōu)解也可用此法判別。

3.2單純形法的MATLAB實(shí)現(xiàn)

3.2.1常規(guī)線性規(guī)劃問(wèn)題

線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號(hào)可以是小于號(hào)也可以是大于號(hào)。為了避免這種形式多樣性帶來(lái)的不便，MATLAB中規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)形式為

其中為列向量，稱(chēng)為價(jià)值向量，稱(chēng)為資源向量，A，Aeq為矩陣。

MATLAB中求解線性規(guī)劃的命令為[x，fval] = linprog（f，A，b）；[x，fval] = linprog（f，A，b，aeq，beq）；[x，fval] = linprog（f，A，b，Aeq，beq，lb，ub）；其中x返回的是決策向量的取值；fval返回的是目標(biāo)函數(shù)的最優(yōu)值；f為價(jià)值向量；A，b對(duì)應(yīng)的是線性不等式約束；Aeq，beq對(duì)應(yīng)的是線性等式約束；lb和ub分別對(duì)應(yīng)的是決策向量的下界向量和上界向量。

3.2.2可轉(zhuǎn)化為線性規(guī)劃的問(wèn)題

4結(jié)論

線性規(guī)劃在實(shí)際生活中是不可或缺的應(yīng)用理論，其在管理決策、資源的優(yōu)化配置等諸多方面顯示了強(qiáng)大的實(shí)用性。本文研究了基于MATLAB軟件環(huán)境下求解線性規(guī)劃的單純形方法并對(duì)其在MATLAB環(huán)境下求解進(jìn)行了實(shí)例應(yīng)用。通過(guò)本文運(yùn)算結(jié)果我們可以得到如下結(jié)論：?jiǎn)渭冃畏ㄟm用于含有三個(gè)及三個(gè)以上決策變量的線性規(guī)劃問(wèn)題，雖然應(yīng)用單純形法時(shí)，涉及的計(jì)算量大，操作起來(lái)比較繁瑣，但單純形法在線性規(guī)劃問(wèn)題的求解上應(yīng)用范圍最廣。

總的來(lái)說(shuō)，MATLAB對(duì)于各種類(lèi)型線性規(guī)劃及整數(shù)線性規(guī)劃的求解都是極其有利的，可以幫助我們大大的縮小計(jì)算量的幅度，并避免很多因?yàn)槿藶樵蛟斐傻恼`差。由于本人水平有限，此類(lèi)問(wèn)題的重要性還有很多地方闡述的不夠，也存在著許多有待改正與提高的空間。

參考文獻(xiàn)

[1] 錢(qián)頌迪.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2005.

[2] 張洪斌.運(yùn)籌學(xué)方法[M].北京：清華大學(xué)出版社，2006.

[3] 曾梅清，田大鋼.線性規(guī)劃問(wèn)題的算法綜述[J].科學(xué)技術(shù)與工程，2010.

[4] 熊義杰.運(yùn)籌學(xué)教程[J].科技信息報(bào)，2010.

[5] 黃雍檢.Matlab語(yǔ)言在運(yùn)籌學(xué)中的應(yīng)用[J].四川大學(xué)學(xué)報(bào)科學(xué)版，2011.