Optimización lineal

Resumen Ejecutivo

La programación lineal es una técnica matemática que consiste en una serie de procedimientos que permiten la resolución de problemas de optimización que se encuentran sujetas a restricciones. Su importancia radica en que esta técnica puede ser aplicada en diversos aspectos de la vida, desde la racionalización de alimentos hasta el aumento de pérdidas del ejército enemigo enuna batalla. Sin embargo, su principal uso actualmente es como herramienta financiera (disminución de costos y aumento de ganancias) en cualquier organización.
En el presente informe se pretenden abordar dos problemas de programación lineal, el primero es el llamado “football pool”, el cual consiste en buscar cómo conseguir el segundo premio de la polla gol sin importar el resultado que seobtenga de los partidos, ya sea empatar, ganar o perder. El segundo es la versión lineal del problema “truss design”, el cual consiste en diseñar la estructura de menor peso que soporte una fuerza externa dada, por lo que busca encontrar el ancho de la barras de tal estructura.

Para resolver los problemas planteados anteriormente, se utilizó el programa llamado AMPL (A Mathematical ProgrammingLanguage) debido a que es el formato más popular para representar problemas de programación lineal, además de la gran cantidad de variables y restricciones de tales problemas. A su vez, se empleó el software CPLEX, modelo basado en el método simplex que puede ser aplicado como algoritmo en la resolución de los problemas de programación lineal. Conjuntamente se dio uso del programa Notepad++, con lafinalidad de utilizarlo como editor de los códigos que permiten modelar los problemas.

Los principales objetivos de este trabajo son familiarizarse con las características básicas del programa AMPL, junto con desarrollar habilidades lógicas en el planteamiento de modelos para la resolución de problemas de programación lineal. Además de dimensionar los tiempos de ejecución que puede tardar elprograma AMPL en resolver los problemas, considerando la cantidad de variables y restricciones que se le pueden otorgar al problema.

Las principales conclusiones obtenidas de los resultados, son la relación existente entre la cantidad de variables (y restricciones) y el tiempo de ejecución. A mayor número de variables, mayor será el tiempo que el solver tarda en resolver el problema. Además de larelación entre gap y tiempo de ejecución. Mientras menor sea el gap entregado al solver, más tiempo se tardará en entregar un resultado, debido a que el gap pide un “porcentaje de error” entre el valor obtenido y la solución objetivo.






Índice


RESUMEN EJECUTIVO……………………………………………………………………………………………………………….2

ÍNDICE………………………………………………………………………………………………………………………………………3

DESCRIPCIÓNDEL PROBLEMA…………………………………………………………………………………………………..4

ENFOQUE Y MODELOS UTILIZADOS…………………………………………………………………………………………..5

ANÁLISIS DE SOLUCIONES……..………………………………………………………………………………………………….7

DISCUSIÓN Y CONCLUSIONES.………………………………………………………………………………………………….13

ANEXOS………...………………………………………………………………………………………………………………………..14

















Descripción del Problema

Con elobjetivo de familiarizarse con el programa AMPL y desarrollar habilidades lógicas en la resolución de problemas, se desarrollaron dos preguntas de programación lineal, y una tercera compuesta de análisis y conclusiones.
La primera parte se conforma por el problema “football pool”, el cual plantea como ganar el segundo premio de la polla gol, sin importar cuales sean los resultados de n partidos, yasea Ganar, Empatar o Perder. La idea es que de las cartillas jugadas, al menos una acierte a n-1 resultados, minimizando la cantidad de cartillas a jugar. Para esto se entrega el número de partidos n, definido como n = {3,….,7}, además del archivo fp.mod con el planteamiento del ppl, los archivos fp.n2.data,…,fp.n7.data con las distintas combinaciones posibles a jugar y por último el archivo...