min型與max型線性規(guī)劃問題解法探析

趙云平

（臨滄師范高等?？茖W(xué)校數(shù)理系,臨滄 云南677099）

min型與max型線性規(guī)劃問題解法探析

趙云平

（臨滄師范高等?？茖W(xué)校數(shù)理系,臨滄 云南677099）

min型（max型）線性規(guī)劃問題就是如何在有限的資源條件下，追求最小化（最大化）的問題。大量教材中多以max型為例向?qū)W者展示了線性規(guī)劃問題的求解。如何求解min型線性規(guī)劃問題？文章在給出max型解法的基礎(chǔ)上，給出了min型問題的解法，幫助學(xué)者更好的區(qū)分和認(rèn)識(shí)不同類型線性規(guī)劃問題的求解。

min型；max型；線性規(guī)劃問題；單純形法；檢驗(yàn)數(shù)

線性規(guī)劃是運(yùn)籌學(xué)最重要的分支，也是最成熟的一個(gè)分支，自從1947年美國(guó)人丹捷格提出求解線性規(guī)劃的比較規(guī)范的單純形法以來，它在理論上已趨向成熟，實(shí)際的應(yīng)用日益廣泛與深入。min型和max型是線性規(guī)劃模型的兩種形式，而單純形法又是求解線性規(guī)劃問題的主要的、有效的算法。單純形法是一種迭代的算法，迭代就是用一種模式反復(fù)進(jìn)行。單純形法的思想是在基本可行解中尋優(yōu)。單純形法的主體步驟有三步[1-7]：首先確定初始基本可行解；檢驗(yàn)其是否最優(yōu)，若是，計(jì)算停止；若不是，尋找更好的基本可行解。恒量?jī)蓚€(gè)解的優(yōu)劣用目標(biāo)衡量，誰使目標(biāo)最優(yōu)誰更好，2、3兩步為循環(huán)往復(fù)的過程，直到找到最優(yōu)。下面針對(duì)min型與max型線性規(guī)劃問題的求解，通過舉例給以詳細(xì)說明[5-7]。

1 min型線性規(guī)劃問題的求解

將模型化為標(biāo)準(zhǔn)形式是用單純形法求解線性規(guī)劃問題的初始步驟。標(biāo)準(zhǔn)形式的線性規(guī)劃模型中，目標(biāo)函數(shù)為求極小值（或極大值），約束條件全為等式，約束條件右端常數(shù)項(xiàng)全為非負(fù)值，變量的取值均非負(fù)。

例1用單純形法求解下列線性規(guī)劃問題[5]

分析：首先第一步將模型化為標(biāo)準(zhǔn)形式，通過添加松弛變量把約束變?yōu)榈仁剑^察系數(shù)陣中是否含單位陣I，如果化為標(biāo)準(zhǔn)型后系數(shù)陣中仍然不含I，那就需要用人工變量法，人為的添加出一個(gè)I來，總之初始的系數(shù)陣中應(yīng)該有一個(gè)，因?yàn)閱渭冃畏ǖ牡谝粋€(gè)基取為I?；癁闃?biāo)準(zhǔn)型后，而且含I，就可以上單純形表進(jìn)行計(jì)算了。

初始單純形表：

2 max型線性規(guī)劃問題的求解

下面我們?nèi)砸岳?為例，通過添加負(fù)號(hào)的形式將min型轉(zhuǎn)化為max型進(jìn)行求解[6，7]，即，因?yàn)橐粋€(gè)函數(shù)求極小點(diǎn)的問題可以化為求極大點(diǎn)的問題，這二者是同解的，它們的值互為相反數(shù)。選用同一題目目的為了更清楚的看到兩種類型的不同與相同之處。

初始單純形表：

用公式計(jì)算檢驗(yàn)數(shù)，

檢驗(yàn)數(shù)數(shù)中仍有大于0的，故當(dāng)前解X=(4，0，3，0)T不是最優(yōu)。正檢驗(yàn)數(shù)所對(duì)應(yīng)的變量就進(jìn)基，同樣的方法計(jì)算檢驗(yàn)比，B－1b與進(jìn)基列對(duì)應(yīng)元素之比，即3比4等于，4比等于12，檢驗(yàn)比中最小的所對(duì)應(yīng)的就出基，以進(jìn)基列與出基行的交叉元4為出發(fā)點(diǎn)遵循相同的原則進(jìn)行迭代，得到下一張單純形表。

3 小結(jié)

一個(gè)簡(jiǎn)單的例題,兩種不同的解法,min型與max型在解法上幾乎相同,區(qū)別僅在于檢驗(yàn)數(shù)反號(hào),即min型是令負(fù)檢驗(yàn)數(shù)中最小者對(duì)應(yīng)的變量進(jìn)基,當(dāng)檢驗(yàn)數(shù)均大于等于零時(shí)當(dāng)前解為最優(yōu);max型是令正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的變量進(jìn)基,當(dāng)檢驗(yàn)數(shù)均小于等于零時(shí)當(dāng)前解為最優(yōu)。相仿，對(duì)于max型線性規(guī)劃模型可以用max求解，也可轉(zhuǎn)化為min型求解。線性規(guī)劃問題中還有很多方面有待研究。

注釋及參考文獻(xiàn)：

[1]《運(yùn)籌學(xué)》教材編寫組．運(yùn)籌學(xué)[M]．4版．北京：清華大學(xué)出版社,2012．

[2]何堅(jiān)勇．運(yùn)籌學(xué)基礎(chǔ)[M]．北京：清華大學(xué)出版社,2008．

[3]鄧成梁．運(yùn)籌學(xué)的原理和方法[M]．北京：華中科技大學(xué)出版社,2014．

[4]胡運(yùn)權(quán)．運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用[M]．4版．哈爾濱：哈爾濱工業(yè)大學(xué)出版社,2006．

[5]《運(yùn)籌學(xué)》教材編寫組．運(yùn)籌學(xué)[M]．3版．北京：清華大學(xué)出版社,2005:20-28．

[6]胡運(yùn)權(quán),郭耀煌．運(yùn)籌學(xué)教程[M]．4版．北京：清華大學(xué)出版社,2012:12-27．

[7]楊民助．運(yùn)籌學(xué)[M]．西安:西安交通大學(xué)出版社,2000:30-53．

[8]曾梅清,田大剛．線性規(guī)劃問題的算法綜述[J]．科學(xué)技術(shù)與工程,2010(1):153-159．

[9]范國(guó)兵．線性規(guī)劃問題最優(yōu)解的討論[J]．懷化學(xué)院學(xué)報(bào),2012(11):81-83．

[10]曾國(guó)斌．線性規(guī)劃問題的相關(guān)算法研究[J]．赤峰學(xué)院學(xué)報(bào),2014(10):1-2．

AnAnalysis on the Solutions of MIN-MAX Type Linear Programming Problems

ZHAO Yun-ping
(Department of Mathematics and Science,Lincang Teachers’College,Lincang,Yunnan 677099)

Type Min(Max)linear programming problem is how to pursue the minimization(maximization)of problem under a condition with limited resources.Examples with type Max have been adopted to present the solutions of linear programming problems for scholars in majority of textbooks;but how about the solutions of type Min linear programming problems?Grounded on the type Max solutions,solutions of type Min problems will be figured out in the following essay,which aims at offering scholars a better distinction and clearer recognization of solutions for different linear programming problems.

type Min；type Max；linear programming problem;simplex method;check number

O221.4

A

1673-1891（2015）01-0019-03

2014-09-15

趙云平（1982-），女，云南臨滄人，碩士，講師，研究方向:基礎(chǔ)數(shù)學(xué)數(shù)論應(yīng)用，應(yīng)用數(shù)學(xué)運(yùn)籌學(xué)線性規(guī)劃，數(shù)值代數(shù)。