Orientador: Prof. Dr. Jerônimo Cordoni Pellegrini / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2016. / O objetivo deste trabalho é apresentar alguns métodos para a resolução de problemas de programação linear. Iremos definir este tipo de problema e mostrar alguns casos onde pode-se obter uma solução ótima com a ajuda de gráficos. Outra preocupação é mostrar que existem várias aplicações para otimização linear, por esse motivo alguns problemas clássicos serão discutidos e modelados. Para uma melhor compreensão sobre restrições lineares e soluções viáveis, iremos definir
conjunto convexo, poliedro e politopo. Algumas situações especiais que podem surgir em otimização serão discutidas, especificamente os casos de problemas inviáveis, ilimitados e degenerados. O Método Simplex, que percorre os vértices do poliedro determinado pelas restrições lineares, será apresentado juntamente com o método das duas fases e alguns exemplos. Para resolver problemas de programação linear inteira, que são aqueles onde restringimos as variáveis de decisão a valores inteiros, o método Branch-and-Bound e Planos de Corte serão apresentados. O caso de matriz totalmente unimodular também será discutido. Finalizando, uma sequência de problemas de programação linear será sugerida, onde professor e aluno do ensino médio terão a oportunidade de discutir, modelar e encontrar a solução ótima destes problemas contando com auxílio de recursos computacionais se necessário. / The aim of this work is to present some methods for solving linear programming problems. We will define this kind of problem and show some cases where you can obtain an optimal solution with the help of graphics. Another concern is to show that there are several applications for linear optimization, therefore some classic problems will be discussed and modeled. For a better understanding about linear constraints and feasible solutions, we will define convex set, polyhedron and polytope. Some special situations that may arise in optimization will be discussed, specifically
the cases of unfeasible, unlimited and degenerate problems. The Simplex method, which runs through the vertices of the polyhedron determined
by linear constraints, will be presented along with the method of the two phases and some examples. To solve integer programming problems, which are those that restrict the decision variables to integer values, the Branch-and-Bound and Cutting-Plane method will be presented. The case of totally unimodular matrix will also be discussed. Finally, a sequence of linear programming problems is suggested, where teacher and high school student will have the opportunity to discuss, model and find the optimal solution of these problems with help of computer resources if necessary.
Identifer | oai:union.ndltd.org:IBICT/oai:BDTD:106247 |
Date | January 2016 |
Creators | Campos, Luiz Guilherme Franco Pires de |
Contributors | Pellegrini, Jerônimo Cordoni, Lima, Maurício Firmino Silva, Kassama, Paola Andrea Gaviria |
Source Sets | IBICT Brazilian ETDs |
Language | Portuguese |
Detected Language | Portuguese |
Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
Format | application/pdf, 140 f. : il. |
Source | reponame:Repositório Institucional da UFABC, instname:Universidade Federal do ABC, instacron:UFABC |
Rights | info:eu-repo/semantics/openAccess |
Relation | http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=106247&midiaext=74422, http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=106247&midiaext=74421, Cover: http://biblioteca.ufabc.edu.brphp/capa.php?obra=106247 |
Page generated in 0.1506 seconds