CAJ | 학술논문

Curet原始‐对偶单纯形算法的实质是在保持对偶可行性的前提下求解一系列原始松驰子问题，因此它必须有一个初始对偶可行解来启动。对于原问题目标函数存在负的价值系数的情形，提出引入人工约束通过简单的初等行变换产生新的目标函数，获得相应的对偶可行解，然后应用Curet原始‐对偶单纯形算法获得问题的一个原始可行解。为了使这个原始可行解更接近最优解，在每次迭代中都对新的目标函数进行修正以逐步逼近原目标函数。在该基础上，通过实现互补松弛条件来取得问题的最优解。大规模数值试验结果表明，与经典两阶段单纯形算法相比，提出的算法在大部分问题上使用更少的迭代次数和执行时间，因而这种推广是有价值的。
Curet원시‐대우단순형산법적실질시재보지대우가행성적전제하구해일계렬원시송치자문제，인차타필수유일개초시대우가행해래계동。대우원문제목표함수존재부적개치계수적정형，제출인입인공약속통과간단적초등행변환산생신적목표함수，획득상응적대우가행해，연후응용Curet원시‐대우단순형산법획득문제적일개원시가행해。위료사저개원시가행해경접근최우해，재매차질대중도대신적목표함수진행수정이축보핍근원목표함수。재해기출상，통과실현호보송이조건래취득문제적최우해。대규모수치시험결과표명，여경전량계단단순형산법상비，제출적산법재대부분문제상사용경소적질대차수화집행시간，인이저충추엄시유개치적。
Curet's primal‐dual approach is essentially to solve a series of primal relaxed linear program‐ming sub‐problems w hile keeping the dual feasibility .So it must be started by an initial dual feasible solu‐tion .For the case of negative coefficients in the objective function ,this paper makes a generalization of Cu‐ret's primal‐dual algorithm .First ,the artificial constraint is introduced to achieve a new objective function with all the nonnegative coefficients by a simple elementary row operation .Then ,Curet's algorithm is ap‐plied to obtain a primal feasible solution closer to the optimality by updating the new objective function at each iteration .Finally ,the complementary slackness condition is achieved to arrive at the optimality .Com‐paring to the classical two‐phase simplex algorithm ,the computational results show that our algorithm u‐ses fewer iterations and spends less executive time on most instances ,and therefore such generalization is valuable .