Visualização de poliedros em algoritmos de programação linear e inteira

Abstract

Neste trabalho ser´a apresentado o programa POLIEDRO V1 que tem como objetivo visualizar poliedros limitados (em R2 e R3), para auxiliar na compreens#ao da evoluc¸#ao dos algoritmos Simplex e Branch-and-Bound. Primeiramente, ser#ao estudados alguns conceitos fundamentais de otimizac¸ #ao irrestrita e restrita, as condic¸ #oes de otimalidade e o problema dual em Programac¸ #ao Linear (PL). A segunda fase do texto concentra-se no estudo te´orico de poliedros, formas de representar poliedros e caracterizac¸ #ao de faces. Ap´os, ´e apresentado o programa POLIEDRO V1 em linguagem Matlab, que consiste em visualizar politopos, gerando faces atrav´es da selec¸ #ao e ordenac¸ #ao de v´ertices. A ´ultima fase do trabalho concentra-se no estudo e desenvolvimento dos algoritmos Simplex e Branch-and-Bound. Aplica-se o programa POLIEDRO V1 em Programac¸ #ao Linear visualizando a regi#ao vi´avel como politopo e apresentase a evoluc¸ #ao, passo a passo, do m´etodo Simplex. J´a em Programac¸ #ao Inteira (PI) visualiza-se graficamente o m´etodo Branch-and-Bound, resolvendo o problema de Programac¸ #ao Linear Inteira (PLI) atrav´es de subproblemas gerados por planos de corte. Os subproblemas s#ao resolvidos recursivamente pelo m´etodo Simplex. This work presents the program POLIEDRO V1, whose objective is to visualize bounded polyhedra in R2 and R3, to help the understanding of the evolution of the simplex and branch and bound algorithms. Initially some fundamental concepts in unconstrained and constrained optimization are studied, including the optimality conditions and the dual problem in Linear Programming. The second part of the text is dedicated to the theoretical study of polyhedra, ways of representing polyhedra and the characterization of faces. The program POLIEDRO V1 is then presented in the languageMatlab, consisting in the visualization of polytopes by generating facets through the selection and ordering of vertices. The last phase of the work concentrates on the study and development of the Simplex and Branch-and-Bound algorithms. The program POLIEDRO V1 is applied to visualize the feasible region of a linear programming problem, on which the step by step evolution of the simplex method is drawn. In Integer Programming, the branch-and-bound algorithm is graphically represented by solving recursively the linear programming subproblems generated by adding cutting planes. These subproblems are solved by the simplex method and visualized.