min型與max型線性規劃問題解法探析

趙云平

（臨滄師范高等專科學校數理系,臨滄 云南677099）

min型與max型線性規劃問題解法探析

趙云平

（臨滄師范高等專科學校數理系,臨滄 云南677099）

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

min型；max型；線性規劃問題；單純形法；檢驗數

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

1 min型線性規劃問題的求解

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

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

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

初始單純形表：

2 max型線性規劃問題的求解

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

初始單純形表：

用公式計算檢驗數，

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

3 小結

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

注釋及參考文獻：

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

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

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

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

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

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

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

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

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

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