El sitio web de la UCLM utiliza cookies propias y de terceros con fines técnicos y de análisis, pero no recaba ni cede datos de carácter personal de los usuarios. Sin embargo, puede haber enlaces a sitios web de terceros, con políticas de cookies distintas a la de la UCLM, que usted podrá aceptar o no cuando acceda a ellos.

Puede obtener más información en la Política de cookies. Aceptar

# Optimization

Curso de fuentes OpenUCLM

In this course we introduce this course on optimization. The optimization paradigm is a new model to solve many problems of real practice. The main ingredients are that they include constraints that must be imposed to the feasible solutions, so that it is guaranteed that they satisfy a minimum set of conditions, and also that they optimize the solutions using an objective function that permit comparing different solutions and decide which one is the best. We end with an enumeration of the topics to be studied in the course: linear programming, mon-linear pprogramming, mixed-integer programming, how to use of GAMS software, duality, sensiivity analysis and examples of applications.

Autores Enrique Castillo 17/09/2019

Me Gusta

In this block we introduce a course on optimization. The optimization paradigm is a new model to solve many problems of real practice. The main ingredients are that they include constraints that must be imposed to the feasible solutions, so that it is guaranteed that they satisfy a minimum set of conditions, and also that they optimize the solutions using an objective function that permits to compare different solutions and decide which one is the best. We enumerate the topics to be studied in the course: linear programming, mon-linear pprogramming, mixed-integer programming, how to use of GAMS software, duality, sensitivity analysis and examples of applications. The course is practically oriented with many examples and its most original part is the sensitivity analysis, in which closed formulas for evaluating the sensitivity of the objective function and primal and dual variables with respect to the parameters are given.”

Presentation of a course on mathematical programming with applications. It includes sensitivity analysis and examples of engineering applications.

Optimization Motivation

Enrique Castillo

This lesson is dedicated to motivate the course on optimization. We start with a detailed description of the objectives of the course, continue with a description of the four main elements of an optimization program, and end with an enumeration of the topics to be studied in the course. Engineers must give solutions that must satisfy constraints, but also that are optimal with respect some criterion.

In this lesson we introduce the reader with linear programming problems by means of three examples: the transportation problem, the production scheduling problem and the diet problems. Since they involve linear objective functions and linear constraints, they are cases of linear programming problems. The GAMS code for solving these problems are given and discussed, so that the introduction of the Gams language becomes smooth.

Linear Programming

Enrique Castillo

In this lesson we introduce the reader with linear programming problems by means of three examples: the transportation, the production scheduling and the diet problems. Since they involve linear objective functions and linear constraints, they are cases of linear programming problems. The GAMS codes for solving these problems are given and discussed, so that the introduction to the Gams language becomes smooth.

In this lesson we present the different types of linear programming problems we can face. We refer to problems with unique solution, with multiple solutions, with unbounded solution and those with no feasible solution. We also introduce the standard form of a linear programming problem, which will reveal its important role when explaining the simplex method in a future lesson. Though it is defined for a particular problem, the definiton is valid for any problem.

We present the different types of linear programming problems we can face. We refer to problems with unique solution, with multiple solutions, with unbounded solution and those with no feasible solution. We also introduce the standard form of a linear programming problem, which will reveal its important role when explaining the simplex method in a future lesson.

In this lesson we describe how to use the GAMS software to solve some mathematical programming problems. One example with some typical errors has been generated to illustrate how the errors are detected by the GAMS software and how GAMS tells us about these eroors. Using the red lines procided by the software, we have immediate access to the lines where the eroors are made. This facilitates the identification of errors and the correction process. Once errors have been corrected, GAMS executes the code and gives the results. We show how the variable values can be accessed by means of the automatically file with the lst extension.

How to Use GAMS

Enrique Castillo

In this lesson we describe how to use the GAMS software to solve mathematical programming problems. One example illustrates how the errors can be corrected and the results obtained.

In this lesson we describe the simplex method which is the most common and well known method for solving linear programming problems. The method is described in great detail and several examples of applications are used to illustrate the different steps of the simplex algorithm. A given linear programming problem having a particular structure is presented that allows solving the problem immediately. The idea of the simplex is to obtain this very convenient structure by exchanging sequentially basic and non-basic variables. This means moving from an extreme point of the feasible region to another extreme point in each step until an optimum is obtained.

The Simplex Method

Enrique Castillo

We describe the simplex method, which is the most well known method for solving LPP. The idea of the simplex is to convert the given problem into another one such that it can immediately solved. The method is described in great detail and several examples of applications are used to illustrate the different steps of the simplex algorithm.

In this lesson we deal with nonlinear programming problems, denoted NLPP. We start with some illustrative and simple examples to motivate the reader and demonstrate that there are many problems that can be stated as NLPP. Thus, knowledge of the optimization methods is very relevant, because apart from incorporating constraints and obtain solutions that satisfy them, we optimize the solutions, that is, we obtain the best ones of all feasible. At the end of the lesson we review the main concepts of nonlinear programming, such as what a NLPP is, the concepts of local and global solution, differentiability, continuous differentiability, etc.

Non Linear Programming

Enrique Castillo

We deal with nonlinear programming problems, denoted NLPP. We start with some illustrative and simple examples of NLPP. Knowledge of the optimization methods is very relevant, because apart from incorporating constraints, we optimize the solutions, that is, we obtain the best ones of all feasible. We also review the main concepts of nonlinear programming problems.

In this lesson we explain the GAMS commands in some detail. We have assumed that the reader has some practice with GAMS programs, because this lesson has been written under that assumption. In fact, this contains some material that must be consulted after some time has been dedicated to previous lessons, in which the students are assumed to be developed several examples of GAMS programs. All commands are explained in detail and some examples are given. We complete the lesson dealing with the conditional operator and the use of dynamic sets, including its capability to work with unions, intersections, differences and complements.

GAMS Commands

Enrique Castillo

In this lesson we explain the GAMS commands in some detail. We have assumed that the reader has some practice with GAMS programs, because this lesson has been written under that assumption. In fact, this contains some material that must be consulted after some time has been dedicated to previous lessons, in which the students are assumed to have developed several examples of GAMS programs.

In this lesson is dedicated to the Karush-Kuhn-Tucker conditions. The reader probably will be familiar with the necessary conditions for unconstraint optimization problems and perhaps with the case of equality constraints. In this lesson we deal with the general case, that includes also inequality constraints. I invite the reader to follow this lesson because the general case is very powerful and arises very frequently in practice, much more than other cases. We use several examples, which are solved graphically and using the KKT conditions, to illustrate the methods.

In this lesson is dedicated to the Karush-Kuhn-Tucker conditions. The reader probably will be familiar with the necessary conditions for unconstraint optimization or equality constrained problems but not with inequalities. Here we also include inequality constraints. We invite the reader to follow this lesson because the general case is very powerful and arises very frequently in practice, much more than other cases.

In this lesson we present several examples of mixed-integer programming problems. The aim is to convince the reader about the power of these methods and invite him/her to think in optimization problem when faced with real life problems. The possibility of using binary variables is very attractive and useful. Here we describe The knapsack, the ship owner, the relevant symptoms, the academy selection, the school timetable and the discrete location problems. They are very simple problems, but will suggest the reader a wide variety of applications.

Mixed Integer Programming

Enrique Castillo

In this lesson we present several examples of mixed-integer programming problems. The possibility of using binary variables is very attractive and useful. Here we describe the knapsack, the ship owner, the relevant symptoms, the academy selection, the school timetable and the discrete location problems. They are very simple problems, but will suggest the reader a wide variety of applications

In this lesson we discuss how the algebraic structure of the set of all solutions of the systems of linear equations and inequalities is. We start by linear systems of equations homogeneous and complete, and continue with the case of inequalities, which is the most interesting. We show that the most general solution of a complete linear system of inequalities is the sum of a linear space plus a cone plus a polytope. To illustrate the different cases we give some examples. Finally, we use the knowledge of this general solution to obtain very easily all the solutions of LPP and use a truncated cube example for illustration purposes.";

The algebraic structure of the set of solutions of a system of linear equations and inequalities, including linear systems of equations or inequalities, homogeneous and complete is shown to be the sum of a linear space, a cone and a polytope. Several examples are given. Finally, we use this knowledge to obtain very easily all the solutions of linear progrmming problems.

In this lesson we introduce the important concept of duality in mathematical programming, which will be the basic material for the sensitivity analysis of a later lesson. First we define dual program and show that any optimization problem has a dual and that the dual of the dual is the primal. Next, we show how to obtain the dual of a given problem and provide rules to do it. This rules are summarized graphically using the graphical scheme shown above this paragraph. We end with some illustrative examples that include the table manufacturing problem and the support vector machines problem.

Duality

Enrique Castillo

In this lesson we introduce the concept of duality in mathematical programming. First we define dual program and show that any optimization problem has a dual and that the dual of the dual is the primal. Next, we show how to obtain the dual of a given problem and provide rules to do it. We end with some illustrative examples that include the mill problem and the support vector machine problem.

As a very interesting practical example of dual problems, in this lesson we deal with the case of an electric market. We state the problem as a primal problem first, and later as its dual problem. The primal is a dictatorial procedure, in which the market operator, ask the private information to the producers, and decides the optimal production for the system imposing the producers the quota of production. In the dual problem, the operator just control the prices and the producers decide the amount of production without the need of informing the operator about private information. An iterative process of change of prices leads to satisfaction of the demand. The surprising result is that both results are identical. An iterative method is used to solve the dual problem, which is based on adjusting the prices until convergence.

Electric Market

Enrique Castillo

In this problem we deal with an electric market. We state the problem as a primal, which is a dictatorial procedure handled by the operator, and its dual problem, in which the operator just control the prices and the producers decide the amount of production. An iterative process of change of prices leads to satisfaction of the demand. The interesting and surprising result is that both results are identical.

This lesson is dedicated to sensitivity analysis. After a brief motivation of sensitivity analysis in civil engineering, we introduce local sensitivity analysis, as determining how the objective function and the variables, primal or dual, change when the data change. We provide formulas for determining all these sensitivities. First an important theorem is given that says that the sensitivity of the objective function with respect to any parameter is the partial derivative of the Lagrangian function with respect to the parameter. Next, matrix formulas are given for determining all sensitivities in the regular case. Explicit formulas for the linear programming case are obtained. Finally, some examples of applications in civil engineering are given. The lesson ends with some conclusions and a discussion of some related bibliography.

We deal with sensitivity analysis. After a motivation in civil engineering, we provide closed formulas for determining all sensitivities, including objective function and primal and dual variables, with respect to any parameter in the regular case. Explicit formulas for the linear programming case are obtained. Some examples of applications in civil engineering are given.

In this lesson we apply the optimization methods to solve several problems of neural and functional networks. We propose workg with the inverse of the neural function instead of working with the neural function directly. We use five different models, some of which include learning the neural functions and using its inverse instead of the neural function, what has some important advantages. The corresponding GAMS code is given. Finally, the results obtained using the different methods are compared.

In this lesson we apply the optimization methods to solve several problems of neural and functional networks. We use five different models, some of which include learning the neural functions and using its inverse instead of the neural function, that has some important advantages. The corresponding GAMS code is given.

This example is dedicated to explain regression models and some duality concepts. First the three most common methods, least squares, minimax and least absolute values are described and the last two stated as linear programming problems. The dual of the minimax problem is obtained and its mathematical interpretation is given. Finally, an example of simulated data with three outliers is given and the three methods used to fit the data. The lesson ends with the interpretation of the results of the example.

Regression

Enrique Castillo

This example is dedicated to explain regression models and some duality concepts. First the three most common methods, least squares, minimax and least absolute values are described and the last two stated as linear programming problems. The dual of the minimax is obtained and its mathematical interpretation is given. Finally, an example of simulated data with three outliers is given.

In order to facilitate the use of the methods described in this course and students can work not only the exercises and problems raised, but other applications, we give the GAMS code used in the exmples. Finally, a list of bibliographic references is given.

Examples of data files

Enrique Castillo

Bibliography

Enrique Castillo

Here are all the slideshow from Optimization

Slideshow

Enrique Castillo