Introdución á programación lineal: resolución de problemas de programación lineal mediante "software" libre

I. NOCIÓNS BÁSICAS DE PROGRAMACIÓN MATEMÁTICA Un problema de optimización vén dado por un par (F, c), onde F é o conxunto de puntos factibles e c é a función de custo. O problema consiste en atopar un punto factible x ∈ F tal que, para todo y ∈ F , se cumpra que c(x) ≤ c(y). Dise que o punto x nestas condicións é unha solución óptima do problema. Nese contexto, un problema de programación matemática consiste en atopar unha solución ao problema: Minimizarx ∈ Rn c(x) suxeito a gi(x) ≤ 0, para cada i = 1, . . . , m hj(x) = 0, para cada j = 1, . . . , l, onde: • x = (x1, . . . , xn) ∈ Rn son as variables de decisión para as que buscamos unha configuración de valores óptima. • A función c representa a función de custo a minimizar (ou beneficio a maximizar) asociado a cada combinación das variables de decisión. • As restricións son funcións que representan que configuracións de valores das variables x1, . . . , xn son factibles. O conxunto de puntos x que as cumpren denomínase rexión factible. Distínguense dous tipos de restricións: o Restricións de desigualdade, gi(x) ≤ 0, para cada i = 1, . . . , m. o Restricións de igualdade, hj(x) = 0, para cada j = 1, . . . , l. A PROGRAMACIÓN LINEAL Un problema de programación lineal é un caso particular de problema de programación matemática no que as funcións usadas como función obxectivo a minimizar e as restricións son lineais. Os elementos que o compoñen son: • Vector de custos, c ∈ Rn. • Matriz de restricións, A ∈ Rm×n, cos seus elementos da forma aij. • Vector de lados dereitos, b ∈ Rm. minimizar c1x1 + c2x2 + · · · + cnxn suxeito a a11x1 + a12x2 + · · · + a1nxn ≤ b1 a21x1 + a22x2 + · · · + a2nxn ≤ b2 e, equivalentemente minimizar c·x . . . . . . . . . . . . . . . en forma matricial, suxeito a Ax ≤ b am1x1 + am2x2 + · · · + amnxn ≤ bm x ≥0. xi ≥ 0, i ∈ {1, . . . , n}. Cómpre destacar que aínda que se formulou o problema de programación lineal en termos da minimización de custos, a maximización de beneficios tamén admite unha modelización análoga ao considerar o vector c como un vector de ganancias asociadas a cada unha das variables de decisión. A PROGRAMACIÓN LINEAL NA HISTORIA Os problemas de programación lineal formúlanse como modelos matemáticos e xorden durante a Segunda Guerra Mundial, no século XX, co obxectivo de planificar os problemas loxísticos e estratéxicos do exército americano. Por exemplo, usáronse para a planificación do traslado de tropas dos Estados Unidos a Europa ou deseñar a dieta dos soldados nunha contorna de escaseza de recursos a mínimo custo ou para determinar o tamaño dos convois americanos. A PROGRAMACIÓN LINEAL NA ACTUALIDADE A programación lineal recibiu un gran pulo grazas ao desenvolvemento de ordenadores, o que permitiu resolver problemas nesta clase cada vez máis grandes e usalos en contextos moi diferentes. Entre as súas aplicacións, destaca o seu emprego en eidos como o da enxeñaría, o da economía, ou o da bioloxía, para deseñar rutas de vehículos, optimizar fluxos en redes, deseñar sistemas de control de tráfico, manexar de maneira óptima carteiras financeiras, optimizar o uso da información en bioinformática ou o seu emprego como técnica de aprendizaxe automática no eido da intelixencia artificial. INTRODUCIÓN Á PROGRAMACIÓN LINEAL Resolución de problemas de programación lineal mediante software libre Laura Davila Pena, Alejandro Saavedra Nieves e Balbina Casas Méndez Departamento de Estatística, Análise Matemática e Optimización II. FORMULACIÓN E RESOLUCIÓN DUN PROBLEMA DE PROGRAMACIÓN LINEAL Nesta sección propoñeremos un caso realista que pode ser modelado usando técnicas de programación lineal. O obxectivo é dobre, xa que ademais de ilustrar o exposto na sección anterior, abordarase a súa resolución. Dado que se trata dun problema con dúas únicas variables de decisión, será fácil observar a súa resolución dende o punto de vista gráfico. Ademais, ilustrarase o emprego de software libre na resolución desta clase de problemas. O PROBLEMA DA EMPRESA DE PINTURAS Unha empresa fabrica pintura para exteriores e pintura para interiores. A empresa debe decidir a cantidade (en toneladas) que vai fabricar de cada tipo de pintura, sabendo que por cada tonelada de pintura de exteriores gañará 5.000 euros, e por cada tonelada de pintura para interiores gañará 4.000 euros. Non obstante, debe respectar certas restricións: • Hai dúas materias primas A e B, das que só se dispón de 24 e 6 toneladas, respectivamente. • Cada tonelada de pintura de exteriores require de 6 toneladas da materia prima A e 1 tonelada da materia prima B. • Cada tonelada de pintura de interiores require de 4 toneladas da materia prima A e 2 toneladas da materia prima B. • Ademais, unha enquisa de mercado indica que a demanda de pintura para interiores non pode ser maior que 1 tonelada máis que a de pintura para exteriores. • Por último, sábese que a demanda máxima de pintura para interiores é de 2 toneladas. OBXECTIVO: Cal é a cantidade óptima que se debe producir de cada tipo de pinturas? FORMULACIÓN DO PROBLEMA: Se denotamos por x a cantidade de toneladas para producir de pintura de exteriores e por y a cantidade de toneladas de pintura de interiores, a ganancia pola produción é 5x + 4y, de maneira que hai que determinar os valores de x e y que maximicen a devandita ganancia. Á vez, as restricións tamén se poden expresar en termos de x e y, de maneira que a formulación completa se poida representar como segue. maximizar 5x + 4y suxeito a 6x + 4y ≤ 24 x + 2y ≤ 6 −x + y ≤ 1 y ≤ 2 x ≥ 0, y ≥ 0. II. i. RESOLUCIÓN MEDIANTE O PROGRAMA R Nesta sección mostramos os pasos a seguir para resolver un problema de programación lineal no software , que pode obterse libremente dende https://cloud.r-project.org/. Unha vez instalado, necesitamos dispoñer do paquete lpSolveAPI, que será o que nos permita tratar tales problemas. Para iso, abrimos e escribimos a orde install.packages(“lpSolveAPI”). Este paquete só necesita instalarse a primeira vez que o imos empregar. Paso 1: carga da libraría e construción do problema Paso 2: coeficientes da función obxectivo e das restricións En primeiro lugar cargamos a libraría lpSolveAPI. Logo construímos un problema de programación lineal con 4 restricións e 2 variables, mediante a función make.lp(). Introducimos os coeficientes das variables na función obxectivo e nas restricións utilizando as funcións set.objfn() e set.row(), respectivamente. Paso 3: signo das restricións e lados dereitos Paso 4: tipo de problema de optimización Mediante a función set.constr.type(), indicamos que as restricións son de “≤”. Logo, introducimos os valores dos lados dereitos das restricións utilizando set.rhs(). A continuación, debemos indicar que o obxectivo é maximizar, para o cal empregamos a función lp.control(). Paso 5: resolución do problema Paso 6: valores das variables, función obxectivo e lados esquerdos das restricións no óptimo Empregamos a función solve() para resolver o noso problema de optimización. Que a saída sexa 0 significa que se atopou unha solución factible óptima ao noso problema. Mediante as funcións get.variables(), get.objective() e get.constraints(), podemos obter os valores das variables, a función obxectivo e os lados esquerdos das restricións, respectivamente, no óptimo. Representación gráfica Para representar o conxunto factible debemos empregar a función plot.lpExtPtr(). Unha vez construído o conxunto factible, definimos as curvas de nivel da función obxectivo e representámolas sobre a gráfica que contén o conxunto factible mediante a función contour. Finalmente, engadimos sobre esta gráfica o punto onde se alcanza a solución óptima, (3, 1.5), para o cal empregamos a función points. II. ii. RESOLUCIÓN MEDIANTE A FOLLA DE CÁLCULO DE LIBREOFFICE Nesta sección mostramos os pasos a seguir para resolver un problema de programación lineal mediante a folla de cálculo da ferramenta LibreOffice , que pode obterse libremente dende https://es.libreoffice.org/. Paso 1: novo ficheiro e introdución dos datos do problema En primeiro lugar, abrimos unha folla de cálculo nova en LibreOffice e introducimos os datos do problema: coeficientes das restricións e da función obxectivo. É útil titular as celas da folla e mesmo usar cores. Paso 2: inicialización das variables e función obxectivo Inicializamos as variables do noso problema a 0. Na cela B9, por exemplo, introducimos a función obxectivo por medio do comando SUMARPRODUTO. Paso 3a: a función dunha restrición Na cela D4 introducimos a función que define a primeira restrición novamente por medio do comando SUMARPRODUTO. Paso 3b: as funcións das restantes restricións De forma análoga introdúcense as funcións que definen as restantes restricións. Paso 4: ferramenta solucionador e identificación de variables, tipo de obxectivo e restricións A continuación, no botón “Ferramentas” do menú superior seleccionamos “Solucionador” e aparece un cadro de diálogo. No cadro, indícase que a cela de destino (obxectivo) atópase na cela B9, que o tipo de obxectivo é de Máximo e que as celas cambiantes (variables) son B2 e C2. En canto ás Condicións limitadoras (restricións), indicamos que as referencias de celas (funcións) están entre as celas D4 e D7, todas as restricións son de tipo “≤” e os valores (lados dereitos das restricións) atópanse entre as celas E4 e E7. Paso 5: opcións da ferramenta solver Xa só nos queda entrar en Opcións (parte inferior do cadro de diálogo), marcar en Supoñer variábeis non negativas e seleccionar un Solucionador linear. Paso 6: visualización da solución óptima Unha vez aceptadas as opcións seleccionadas e tras pulsar no botón de Solucionar e Manter o resultado, nas celas correspondentes ás variables do problema podemos ver a súa solución óptima (3 e 1,5), a cela da función obxectivo mostrará o seu valor óptimo (21) e nas celas dos lados esquerdos das restricións, os seus valores no óptimo. Referencias: [1] Hillier, F. & Lieberman, G. (2010). Introducción a la investigación de operaciones. McGraw-Hill.