华中科技大学学报（自然科学版）
華中科技大學學報（自然科學版）
화중과기대학학보（자연과학판）
JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY(NATURE SCIENCE)
2008年
1期
82-84,128
,共4页
周康%彭颖君%王防修%同小军
週康%彭穎君%王防脩%同小軍
주강%팽영군%왕방수%동소군
线性规划问题%部分基变量算法%"两看一算"算法
線性規劃問題%部分基變量算法%"兩看一算"算法
선성규화문제%부분기변량산법%"량간일산"산법
一般形式的线性规划问题在找不到基本可行解或对偶问题的基本可行解时,无法用传统的单纯形法或对偶单纯形法求解,即"两看一算"算法.为了解决这个问题,结合两种"两看一算"算法,提出了一种新的算法--部分基变量算法.该算法首先从部分基变量出发,由初等行变换将LP问题转化为准典式,然后由初等行变换找到全部可行基变量,最后用对偶单纯形法得到最优解.对算法的正确性和可行性进行了严格证明,提出算法的实现方式并举例进行了说明,对算法的特点进行了讨论.分析表明所提出的算法是实现线性规划问题求解的较为理想的算法.
一般形式的線性規劃問題在找不到基本可行解或對偶問題的基本可行解時,無法用傳統的單純形法或對偶單純形法求解,即"兩看一算"算法.為瞭解決這箇問題,結閤兩種"兩看一算"算法,提齣瞭一種新的算法--部分基變量算法.該算法首先從部分基變量齣髮,由初等行變換將LP問題轉化為準典式,然後由初等行變換找到全部可行基變量,最後用對偶單純形法得到最優解.對算法的正確性和可行性進行瞭嚴格證明,提齣算法的實現方式併舉例進行瞭說明,對算法的特點進行瞭討論.分析錶明所提齣的算法是實現線性規劃問題求解的較為理想的算法.
일반형식적선성규화문제재조불도기본가행해혹대우문제적기본가행해시,무법용전통적단순형법혹대우단순형법구해,즉"량간일산"산법.위료해결저개문제,결합량충"량간일산"산법,제출료일충신적산법--부분기변량산법.해산법수선종부분기변량출발,유초등행변환장LP문제전화위준전식,연후유초등행변환조도전부가행기변량,최후용대우단순형법득도최우해.대산법적정학성화가행성진행료엄격증명,제출산법적실현방식병거례진행료설명,대산법적특점진행료토론.분석표명소제출적산법시실현선성규화문제구해적교위이상적산법.
