Programação linear, linear inteira e os algoritmos Simplex e Branch and Bound: Problemas e aplicações em otimização

Abstract

Optimization problems are those in which the objective is to maximize or minimize a function, called an objective function. In the optimization process, restrictions on decision variables are determined, according to which continuous values can be accepted, which constitute a linear programming problem. In a general problem of integer linear programming, we seek to minimize a linear cost function over all n-dimensional vectors x subject to a set of linear restrictions of equality and inequality, as well as integrality restrictions in some or all variables in x. If only some of the variables are restricted to take integer values, and others can take real values, then the problem is called a mixed integer linear programming problem (MILP). If the objective function and/or the constraints are nonlinear functions, the problem is called a mixed integer nonlinear programming problem (MINLP). If all variables are restricted to assume integer values, then the problem is called a pure integer linear programming problem. If all variables are restricted to assuming binary values ​ (0 or 1), then the problem is called a binary optimization problem, which is a special case of a problem of pure integer linear programming. The branch and bound method is not a solution technique specifically limited to integer programming problems. It is a solution approach that can be applied to many different types of problems. The branch and boundary approach is based on the principle that the total set of viable solutions can be divided into smaller subsets of solutions. These smaller subsets can then be evaluated systematically until the best solution is found.