高师理科学刊
高師理科學刊
고사이과학간
JOURNAL OF SCIENCE OF TEACHERS＇ COLLEGE AND UNIVERSITY
2015年
7期
10-13
,共4页
线性规划%基本可行解%单纯形法%对偶单纯形法%松弛
線性規劃%基本可行解%單純形法%對偶單純形法%鬆弛
선성규화%기본가행해%단순형법%대우단순형법%송이
linear programming%basic feasible solution%simplex algorithm%dual simplex algorithm%relaxation
针对线性规划的单纯形算法中出现不可行基的情形，提出了一种原有松弛-对偶单纯形算法。忽略不可行基变量相应的约束构造一个原有可行的松弛子问题，根据最钝角原理作了进一步松弛，用原有单纯形法求解该子问题，然后用对偶单纯形法求解原问题。通过大规模数值试验对这种算法进行计算检验。结果表明，与经典单纯形算法相比，提出的算法简便且具有更高的计算效率。
針對線性規劃的單純形算法中齣現不可行基的情形，提齣瞭一種原有鬆弛-對偶單純形算法。忽略不可行基變量相應的約束構造一箇原有可行的鬆弛子問題，根據最鈍角原理作瞭進一步鬆弛，用原有單純形法求解該子問題，然後用對偶單純形法求解原問題。通過大規模數值試驗對這種算法進行計算檢驗。結果錶明，與經典單純形算法相比，提齣的算法簡便且具有更高的計算效率。
침대선성규화적단순형산법중출현불가행기적정형，제출료일충원유송이-대우단순형산법。홀략불가행기변량상응적약속구조일개원유가행적송이자문제，근거최둔각원리작료진일보송이，용원유단순형법구해해자문제，연후용대우단순형법구해원문제。통과대규모수치시험대저충산법진행계산검험。결과표명，여경전단순형산법상비，제출적산법간편차구유경고적계산효솔。
For the situation that an infeasible basis is generated in the simplex pivotal process,proposes a primal relaxation-dual simplex algorithm.The constraints with feasible basic variables are selected to construct a primal feasible relaxation subproblem.On this basis,the subproblem is further relaxed in terms of the most-obtuse-angle principle,and solved with the primal simplex algorithm.Then the dual simplex algorithm is applied to find the solution to the original problem.It is found that the algorithm presented is convenient and efficient in computation, compared with the classical primal simplex method by the numerical test on some large-scale examples.
