嘉兴学院学报
嘉興學院學報
가흥학원학보
JOURNAL OF JIAXING COLLEGE
2013年
3期
24-28
,共5页
线性规划%初始基%单纯形算法%对偶单纯形算法%计算效率
線性規劃%初始基%單純形算法%對偶單純形算法%計算效率
선성규화%초시기%단순형산법%대우단순형산법%계산효솔
从一个既不是原始可行也不是对偶可行的初始基出发,提出了求解线性规划问题的原始—对偶单纯形算法.首先,将等式约束右手边向量取负值的项置为零,用原始单纯形算法求解相应的线性规划问题,如果存在最优解,则是原问题的一个正则解.在原始单纯形迭代过程中,一旦原问题右手边向量取负值的项转化为非负项,则恢复其原来的约束条件参与迭代计算,可使获得的正则解距原问题的最优解(如果存在)更近.接着,从所获得的正则解出发,用对偶单纯形算法求解原问题,直到获得原问题的最优解或无可行解的结论.最后,为了验证该算法的计算性能,通过MATLAB编程在计算机上进行大规模数值试验,结果表明,与经典单纯形算法相比,该算法在大部分问题上使用更少的迭代次数和执行时间,具有更高的计算效率.
從一箇既不是原始可行也不是對偶可行的初始基齣髮,提齣瞭求解線性規劃問題的原始—對偶單純形算法.首先,將等式約束右手邊嚮量取負值的項置為零,用原始單純形算法求解相應的線性規劃問題,如果存在最優解,則是原問題的一箇正則解.在原始單純形迭代過程中,一旦原問題右手邊嚮量取負值的項轉化為非負項,則恢複其原來的約束條件參與迭代計算,可使穫得的正則解距原問題的最優解(如果存在)更近.接著,從所穫得的正則解齣髮,用對偶單純形算法求解原問題,直到穫得原問題的最優解或無可行解的結論.最後,為瞭驗證該算法的計算性能,通過MATLAB編程在計算機上進行大規模數值試驗,結果錶明,與經典單純形算法相比,該算法在大部分問題上使用更少的迭代次數和執行時間,具有更高的計算效率.
종일개기불시원시가행야불시대우가행적초시기출발,제출료구해선성규화문제적원시—대우단순형산법.수선,장등식약속우수변향량취부치적항치위령,용원시단순형산법구해상응적선성규화문제,여과존재최우해,칙시원문제적일개정칙해.재원시단순형질대과정중,일단원문제우수변향량취부치적항전화위비부항,칙회복기원래적약속조건삼여질대계산,가사획득적정칙해거원문제적최우해(여과존재)경근.접착,종소획득적정칙해출발,용대우단순형산법구해원문제,직도획득원문제적최우해혹무가행해적결론.최후,위료험증해산법적계산성능,통과MATLAB편정재계산궤상진행대규모수치시험,결과표명,여경전단순형산법상비,해산법재대부분문제상사용경소적질대차수화집행시간,구유경고적계산효솔.