趙云平

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

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

趙云平

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

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

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

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

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

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

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

分析：首先第一步將模型化為標準形式，通過添加松弛變量把約束變?yōu)榈仁?，觀察系數(shù)陣中是否含單位陣I，如果化為標準型后系數(shù)陣中仍然不含I，那就需要用人工變量法，人為的添加出一個I來，總之初始的系數(shù)陣中應該有一個，因為單純形法的第一個基取為I。化為標準型后，而且含I，就可以上單純形表進行計算了。

初始單純形表：

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

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

初始單純形表：

用公式計算檢驗數(shù)，

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

3 小結(jié)

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

注釋及參考文獻：

[1]《運籌學》教材編寫組．運籌學[M]．4版．北京：清華大學出版社,2012．

[2]何堅勇．運籌學基礎[M]．北京：清華大學出版社,2008．

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

[4]胡運權．運籌學基礎及應用[M]．4版．哈爾濱：哈爾濱工業(yè)大學出版社,2006．

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

[6]胡運權,郭耀煌．運籌學教程[M]．4版．北京：清華大學出版社,2012:12-27．

[7]楊民助．運籌學[M]．西安:西安交通大學出版社,2000:30-53．

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

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

[10]曾國斌．線性規(guī)劃問題的相關算法研究[J]．赤峰學院學報,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-），女，云南臨滄人，碩士，講師，研究方向:基礎數(shù)學數(shù)論應用，應用數(shù)學運籌學線性規(guī)劃，數(shù)值代數(shù)。