حل مسائل برنامه ريزي خطي در مقياس بزرگ با استفاده از روش هاي بهينه سازي عددي

چكيده انگليسي :

Solving Large Scale Linear Programming Problems Using Numerical Optimization Methods Mohammad Akbari Jeiranbolaghi Mohammad Akbari@hotmail com Date of Submission 2012 04 24 Department of Industrial Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor Naser Mollaverdi naserm@cc iut ac irAbstract In general large scale linear programming LP solving algorithms are not efficient So manyresearches have been done for developing special algorithms for this group of problems Using of differentmethods researcher have introduced variety of algorithms each of which have their own special trait Thereare mainly three approaches to solving linear programmings 1 Searching basic feasible solutions 2 Interior point methods and 3 Exterior penalty functions In this thesis referring to the previous researches an exterior penalty function an unconstraint optimization problem is developed This function is apiecewise quadratic convex function which is equivalent to our primal problem and solving thisoptimization problem leads to solving primal problem In previous research a fast newton algorithm isutilized to solve this function Newton method is able to solve linear programming problems which theirdifference between number of constraints and number of variables are very large In other words newtonmethod solves linear programming problems with large number of constraints and moderate number ofvariables This method acquires solution of least 2 norm of linear programming For improving theefficiency of newton method we used a new accelerated conjugate gradient method with finitehessian vector approximation with fixed step size for solving large scale linear programming problems Direction of this new algorithm is approximating newton s direction and does not need to compute step sizein its iterations In other word Wolfe conditions for determining step size which have very expensivecomputational cost are not used For comparing our proposed algorithm with other algorithms over 1 000random linear programming problems with their optimal point and objective function are generated Efficiency of this algorithm is compared with several other algorithms like newton method and CPLEX Dual software For having comprehensive conclution of efficiency of proposed algorithm Dolan and Moreperformance profile is used It is shown that this new algorithm can solve linear programming problemswhich have close number of variables and constraints Performance of this algorithm compared to newtonalgorithm and CPLEX Dual software for solving large scale linear problems with different structures isshown to be more efficient In moderate scale performance of the proposed algorithm is near the CPLEXmethod while Newton method in many problems fails to solve the linear programming problem In largescale problems It is shown that propsed algorithm is versy efficient Over the 90 percent of the large scalelinear programming problems was solved quiker than other algortihms Difference between run times ofproposed algorithm and CPLEX Dual software is very high In conclution a new conjugate gradient method is proposed In this algorithm fixed step size is used inall the iterations in all the problems Accelerated scheme proved to be very effective in the proposedalgorithm Keywords Linear Programming Large scale Conjugate gradient method Exterior penalty function

اكبري جيران بلاغي، محمد

حل مسائل برنامه ريزي خطي در مقياس بزرگ با استفاده از روش هاي بهينه سازي عددي

گراديان مزدوج , تابع جريمه بيروني