線性規(guī)劃的標(biāo)準(zhǔn)型

其主要特征為：(1)目標(biāo)函數(shù)為極大化類型；(2)所有的約束條件都是等式；(3)所數(shù)學(xué)規(guī)劃有約束方程右端的常數(shù)都是非負(fù)的；(4)所有決策變量都是非負(fù)的。 2100433B

描述線性規(guī)劃問題的常用和最直觀形式是標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)型包括以下三個部分：

一個需要極大化的線性函數(shù)，例如：

以下形式的問題約束，例如：

和非負(fù)變量，例如：

線性規(guī)劃問題通?？梢杂镁仃囆问奖磉_(dá)成：

maximize

subject to

其他類型的問題，例如極小化問題，不同形式的約束問題，和有負(fù)變量的問題，都可以改寫成其等價問題的標(biāo)準(zhǔn)型。

例子

以下是一個線性規(guī)劃的例子。假設(shè)一個農(nóng)夫有一塊 A平方千米的農(nóng)地，打算種植小麥或大麥，或是兩者依某一比例混合種植。該農(nóng)夫只可以使用有限數(shù)量的肥料 F 和農(nóng)藥 P，而單位面積的小麥和大麥都需要不同數(shù)量的肥料和農(nóng)藥，小麥以

max

全書共分八章，分別講解了線性規(guī)劃問題的建模方法、線性規(guī)劃問題模型的標(biāo)準(zhǔn)型、用單純形算法求解線性規(guī)劃問題、靈敏度分析等內(nèi)容。

線性規(guī)劃理論在工程設(shè)計、生產(chǎn)管理、交通運輸、國防等領(lǐng)域以及自然科學(xué)的很多學(xué)科中都有著廣泛的應(yīng)用。線性規(guī)劃問題雖然是一個古老的問題，但求解線性規(guī)劃問題的方法在不斷發(fā)展：從單純形法、對偶單純形法、橢圓方法到內(nèi)點方法等等。雖然線性規(guī)劃有這么多解法，但是單純形方法在其中的統(tǒng)治地位始終沒變。對于退化線性規(guī)劃問題，用單純形方法求解時有可能產(chǎn)生循環(huán)，因此，研究退化線性規(guī)劃問題成為人們研究線性規(guī)劃問題的一個重要方面。1952年A. Charnes和W. W. Cooper給出了求解退化線性規(guī)劃問題的攝動法，1954年G. B. Dantzig, A. Orden和P. Wolfe提出了求解退化線性規(guī)劃問題的字典序法，1976年G. G. Bland提出了求解退化線性規(guī)劃問題的Bland法則，這些方法都能避免循環(huán)發(fā)生。