INVESTIGACIN OPERATIVA.Teora, Ejercicios y Prcticas con OrdenadorRosa Rodrguez Huertas Antonio Gmez Mellado10 de Septiembre de 20022ndice GeneralIntroduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9I TEORA 111 Introduccin a la teora de optimizacin 131.1 Orgenes y desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.1.1 Orgenes de la Investigacin operativa . . . . . . . . . . . . . 141.1.2 La Teora de Juegos . . . . . . . . . . . . . . . . . . . . . . . 161.1.3 La Programacin Lineal . . . . . . . . . . . . . . . . . . . . . 161.1.4 La Investigacin Operativa . . . . . . . . . . . . . . . . . . . 171.2 Modelizacin de un problema de P. L. . . . . . . . . . . . . . . . . . 181.2.1 Formulacin de los modelos. . . . . . . . . . . . . . . . . . . 191.3 Modelizacin de diversos problemas de I.O. . . . . . . . . . . . . . . 201.4 Modelos de programacin matemtica . . . . . . . . . . . . . . . . . 251.5 El mtodo geomtrico . . . . . . . . . . . . . . . . . . . . . . . . . . 261.5.1 Descripcin del mtodo geomtrico . . . . . . . . . . . . . . . 281.5.2 Resumen del mtodo geomtrico . . . . . . . . . . . . . . . . 322 Programacin Lineal 332.1 Modelo general de programacin lineal . . . . . . . . . . . . . . . . . 332.2 Nociones previas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.3 Deniciones sobre las soluciones de un problema . . . . . . . . . . . 392.4 Algunos resultados sobre las soluciones . . . . . . . . . . . . . . . . . 432.5 El algoritmo del Simplex . . . . . . . . . . . . . . . . . . . . . . . . . 482.6 Algoritmo del Simplex en forma de tabla (max) . . . . . . . . . . . . 512.7 Algoritmo del Simplex en forma de tabla (min) . . . . . . . . . . . . 552.8 Bsqueda de soluciones iniciales . . . . . . . . . . . . . . . . . . . . . 572.8.1 Mtodo de las Penalizaciones . . . . . . . . . . . . . . . . . . 622.9 Algoritmo del Simplex en forma matricial . . . . . . . . . . . . . . . 642.9.1 Mtodo del Simplex en forma matricial (caso maximizante) . 662.10 Adaptacin algebraica del algoritmo del Simplex . . . . . . . . . . . 672.10.1Algoritmo del Simplex (enfoque algebraico) . . . . . . . . . . 682.10.2Mtodo del Simplex en forma de tabla (Usando zj cj en laltima la) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 722.11 Otros algoritmos de programacin lineal . . . . . . . . . . . . . . . . 762.11.1Mtodo de las dos fases . . . . . . . . . . . . . . . . . . . . . 7734 NDICE GENERAL2.11.2Algoritmo revisado del Simplex (Caso maximizante) . . . . . 793 Dualidad en programacin lineal 853.1 Formas de la dualidad. . . . . . . . . . . . . . . . . . . . . . . . . . 853.1.1 Forma cannica maximizante de la dualidad . . . . . . . . . . 853.1.2 Forma estndar maximizante de la dualidad . . . . . . . . . . 883.1.3 Reglas para escribir el problema dual . . . . . . . . . . . . . . 913.1.4 Forma cannica minimizante de la dualidad . . . . . . . . . . 923.2 Propiedades de la relacin de dualidad . . . . . . . . . . . . . . . . . 943.3 Interpretacin econmica de la dualidad. . . . . . . . . . . . . . . . 1053.4 Algoritmo Dual del Simplex. (Caso maximizante) . . . . . . . . . . . 1074 Anlisis de sensibilidad 1114.1 Introduccin grca . . . . . . . . . . . . . . . . . . . . . . . . . . . 1114.2 Cambios discretos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1124.2.1 Variacin en un coste de una variable no bsica . . . . . . . . 1124.2.2 Variacin en un coste de una variable bsica . . . . . . . . . . 1144.2.3 Cambios en los recursos . . . . . . . . . . . . . . . . . . . . . 1164.2.4 Cambios en los coecientes tecnolgicos . . . . . . . . . . . . 1164.3 Incorporacin de una nueva actividad . . . . . . . . . . . . . . . . . 1174.4 Incorporacin de nuevas restricciones . . . . . . . . . . . . . . . . . . 1184.5 Programacin Paramtrica . . . . . . . . . . . . . . . . . . . . . . . . 1194.5.1 Parametrizacin de los coecientes de coste . . . . . . . . . . 1194.5.2 Parametrizacin de los recursos . . . . . . . . . . . . . . . . . 1245 El problema de transporte 1275.1 Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1275.2 Planteamiento como un problema de programacin lineal . . . . . . 1285.3 Problema no equilibrado . . . . . . . . . . . . . . . . . . . . . . . . . 1295.4 Propiedades del problema de transporte . . . . . . . . . . . . . . . . 1295.5 Determinacin de una solucin inicial . . . . . . . . . . . . . . . . . 1295.5.1 Mtodo de la esquina Noroeste . . . . . . . . . . . . . . . . . 1305.5.2 Mtodo de costo mnimo . . . . . . . . . . . . . . . . . . . . . 1325.5.3 Mtodo de Vogel . . . . . . . . . . . . . . . . . . . . . . . . . 1345.6 Denicin de Ciclo. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1375.7 Algoritmo de transporte (forma minimizante) . . . . . . . . . . . . . 1375.8 Soluciones degeneradas . . . . . . . . . . . . . . . . . . . . . . . . . . 1415.9 Otras variaciones del problema de transporte . . . . . . . . . . . . . 1435.10 El problema de transbordo . . . . . . . . . . . . . . . . . . . . . . . 1445.11 El problema de asignacin . . . . . . . . . . . . . . . . . . . . . . . . 1465.11.1El algoritmo Hngaro (Forma minimizante) . . . . . . . . . . 1465.11.2Ejemplo de aplicacin del algoritmo Hngaro. . . . . . . . . 1475.12 Problema de emparejamiento . . . . . . . . . . . . . . . . . . . . . . 1495.13 Problema de planicacin de la produccin . . . . . . . . . . . . . . 150NDICE GENERAL 56 Modelos de Redes 1556.1 Redes. Conceptos bsicos . . . . . . . . . . . . . . . . . . . . . . . . 1556.2 Caminos de longitud mnima . . . . . . . . . . . . . . . . . . . . . . 1576.3 Algoritmos de ordenacin y de etiquetacin . . . . . . . . . . . . . . 1586.4 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . 1616.5 Problema del ujo mximo . . . . . . . . . . . . . . . . . . . . . . . 1636.6 Algoritmo de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . 1656.6.1 Flujo de un corte . . . . . . . . . . . . . . . . . . . . . . . . . 1656.6.2 Algoritmo de Ford-Fulkerson . . . . . . . . . . . . . . . . . . 1666.7 CPM y PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1696.7.1 Algoritmo CPM . . . . . . . . . . . . . . . . . . . . . . . . . 1716.7.2 El mtodo PERT . . . . . . . . . . . . . . . . . . . . . . . . . 1737 Programacin Entera 1777.1 Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1777.2 Algunos problemas de programacin entera . . . . . . . . . . . . . . 1787.2.1 El problema de la mochila . . . . . . . . . . . . . . . . . . . . 1787.2.2 Problema del viajante . . . . . . . . . . . . . . . . . . . . . . 1797.2.3 Problema de costo jo . . . . . . . . . . . . . . . . . . . . . . 1807.3 El algoritmo de ramicacin y acotacin . . . . . . . . . . . . . . . . 1817.3.1 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1837.3.2 Programacin entera mixta . . . . . . . . . . . . . . . . . . . 1857.4 Algoritmo de corte o de Gomory . . . . . . . . . . . . . . . . . . . . 1857.4.1 Resumen del algoritmo de Gomory . . . . . . . . . . . . . . . 1887.5 Programacin 0-1. Algoritmo de enumeracin . . . . . . . . . . . . . 1898 Teora de Colas 1958.1 Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1958.1.1 Costos de los sistemas de colas . . . . . . . . . . . . . . . . . 1978.1.2 Estructuras tpicas. . . . . . . . . . . . . . . . . . . . . . . . . 1988.2 Terminologa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1988.2.1 Caractersticas fsicas . . . . . . . . . . . . . . . . . . . . . . 1988.2.2 Caractersticas de funcionalidad . . . . . . . . . . . . . . . . . 2008.2.3 Parmetros de los sistemas de colas . . . . . . . . . . . . . . 2018.3 Modelos de llegadas y de tiempo de servicio . . . . . . . . . . . . . . 2018.3.1 Relacin entre la distribucin de Poisson y la exponencial . . 2038.3.2 Otra distribucin de las llegadas. La distribucin de Erlang . 2048.3.3 Modelos de duracin de los servicios . . . . . . . . . . . . . . 2058.4 La notacin de Kendall . . . . . . . . . . . . . . . . . . . . . . . . . 2058.5 Estudio de una cola M/M/1 . . . . . . . . . . . . . . . . . . . . . . . 2068.5.1 Probabilidad de que el sistema est en cierto estado . . . . . 2068.5.2 Nmero medio de elementos en el sistema. . . . . . . . . . . 2098.5.3 Nmero medio de elementos en cola . . . . . . . . . . . . . . 2098.6 Teorema de Little . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2098.7 Sistemas con capacidad limitada . . . . . . . . . . . . . . . . . . . . 2108.8 Modelo con s servidores . . . . . . . . . . . . . . . . . . . . . . . . . 2138.8.1 Clculo de la probabilidad de los diferentes estados del sistema 2136 NDICE GENERAL8.8.2 Clculo de P0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2148.8.3 Clculo de los parmetros . . . . . . . . . . . . . . . . . . . . 2158.8.4 Sistemas de colas de tipo M/M/s/FCFS//. Expresionespara el caso de s servidores . . . . . . . . . . . . . . . . . . . 2158.9 El coste de un sistema de colas . . . . . . . . . . . . . . . . . . . . . 2169 Introduccin a la Simulacin 2199.1 Simulacin. Generalidades . . . . . . . . . . . . . . . . . . . . . . . . 2199.2 Un ejemplo muy sencillo . . . . . . . . . . . . . . . . . . . . . . . . . 2209.3 Mtodo Montecarlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2239.4 Notas histricas sobre el Mtodo Montecarlo . . . . . . . . . . . . . 2249.5 Generacin de nmeros aleatorios . . . . . . . . . . . . . . . . . . . . 2259.5.1 Propiedades de un buen generador de nmeros aleatorios . . 2269.5.2 Mtodo del centro del cuadrado . . . . . . . . . . . . . . . . . 2269.5.3 Mtodo de las congruencias . . . . . . . . . . . . . . . . . . . 2269.6 Mtodo de la transformacin inversa. . . . . . . . . . . . . . . . . . 2299.6.1 Mtodo de la transformacin inversa aplicado a la distribucinexponencial. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2299.7 Simulacin de una cola M/M/1 . . . . . . . . . . . . . . . . . . . . . 2309.7.1 Programa FORTRAN. . . . . . . . . . . . . . . . . . . . . . 2339.8 Integracin Montecarlo. Mtodo de xito-fracaso . . . . . . . . . . . 2409.9 Ejemplos de programas de simulacin . . . . . . . . . . . . . . . . . 242II EJERCICIOS 2491 Introduccin a la optimizacin 2511.1 Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2511.2 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 2661.3 Soluciones de los Ejercicios Propuestos . . . . . . . . . . . . . . . . . 2752 Programacin lineal 2832.1 Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2832.2 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 3052.3 Soluciones de los Ejercicios Propuestos . . . . . . . . . . . . . . . . . 3103 Dualidad en programacin lineal 3153.1 Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3153.2 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 3303.3 Soluciones de los Ejercicios Propuestos . . . . . . . . . . . . . . . . . 3324 Anlisis de sensibilidad 3354.1 Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3354.2 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 3624.3 Soluciones de los Ejercicios Propuestos . . . . . . . . . . . . . . . . . 367NDICE GENERAL 75 El Problema de transporte 3715.1 Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3715.2 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 3835.3 Soluciones de los Ejercicios Propuestos . . . . . . . . . . . . . . . . . 3886 Problemas de redes 3916.1 Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3916.2 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 3966.3 Soluciones de los Ejercicios Propuestos . . . . . . . . . . . . . . . . . 4017 Programacin entera 4037.1 Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4037.2 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 4147.3 Soluciones de los Ejercicios Propuestos . . . . . . . . . . . . . . . . . 4168 Teora de colas 4198.1 Ejercicios Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4198.2 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 4248.3 Soluciones de los Ejercicios Propuestos . . . . . . . . . . . . . . . . . 4269 Introduccin a la Simulacin 4279.1 Ejercicios resueltos. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4279.2 Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . 428III PRCTICAS CON ORDENADOR 4311 Programacin lineal I 4331.1 Problema de programacin lineal con LINGO. . . . . . . . . . . . . 4331.2 Anlisis de sensibilidad con LINGO . . . . . . . . . . . . . . . . . . . 4361.3 Otros problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4372 Programacin lineal II 4452.1 Comandos de salida de cheros . . . . . . . . . . . . . . . . . . . . . 4452.2 Formato abreviado de LINGO . . . . . . . . . . . . . . . . . . . . . . 4482.3 Recapitulacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4493 El problema de transporte 4533.1 Problema de transporte . . . . . . . . . . . . . . . . . . . . . . . . . 4533.2 Problema de asignacin . . . . . . . . . . . . . . . . . . . . . . . . . 4553.3 Problema de emparejamiento . . . . . . . . . . . . . . . . . . . . . . 4573.4 Problema de planicacin de la produccin . . . . . . . . . . . . . . 4593.5 Otros problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4608 NDICE GENERAL4 Problemas de redes 4634.1 Camino mnimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4634.2 Flujo mximo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4684.3 CPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4704.4 Otros problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4725 Variable entera, acotada y libre 4755.1 Variable entera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4755.2 Variable acotada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4765.3 Variable libre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4775.4 Variable binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4785.5 Otros problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480BIBLIOGRAFA 499INTRODUCCINEste libro est concebido con el propsito de cubrir los conceptos y tcnicasbsicas de la Investigacin Operativa y pone el mayor nfasis en sus aplicacionesa problemas reales.Los destinatarios de este texto son las personas, estudiantes oprofesionales, que se inicien en el estudio de las distintas tcnicas que la InvestigacinOperativa nos suministra para el estudio de los problemas de optimizacin que surgena diario en el mundo de la empresa y de la administracin, problemas que pretendendar el mximo rendimiento a los recursos disponibles y, por lo general, limitados.Est especialmente diseado para alumnos de las Escuelas de Ingeniera o paraestudios de Ciencias Econmicas y Empresariales y es fruto de la experiencia delos autores, ambos profesores de Estadstica e Investigacin Operativa de la EscuelaSuperior de Ingeniera de la Universidad de Cdiz.El libro est organizado en tres secciones:Una primera parte terica donde se recogen sobre todo los conceptos fundamen-tales y los algoritmos ms usuales en la resolucin de problemas de optimizacin,ilustrando todos los aspectos mencionados con abundantes ejemplos. En los cuatroprimeros temas se trata la Programacin Lineal, la Dualidad en Programacin Li-neal y los problemas de Sensibilidad del algoritmo de Simplex. Los siguientes temasestn dedicados a algoritmos especiales de optimizacin, incluyndose el problemade transporte, problemas de redes y programacin con variable entera o binaria. Ellibro contiene tambin un captulo de Teora de Colas, as como otro que trata lostemas ms bsicos de las Tcnicas de Simulacin, incluyendo programas en Fortrany en otros lenguajes de Programacin.La segunda parte, dedicada a problemas sobre los temas tratados en la teora,contiene una seccin de ejercicios totalmente resueltos y otra de ejercicios propuestoscon su solucin.La tercera parte contiene diversos problemas realizados con el Programa LINGOpublicado por LINDO SYSTEMS. INC., incluyendo instrucciones de uso de los co-mandos de este programa.Esperamos que los lectores encuentren til este manual para el estudio y lasaplicaciones de la Investigacin Operativa y sean capaces de resolver los problemasque se les planteen en este campo. De esta forma, veremos cumplido nuestro objetivo.LOS AUTORES9Parte ITEORA11Tema 1Introduccin a la teora deoptimizacin1.1 Orgenes y desarrolloEn los siglos XVII y XVIII, grandes matemticos como Newton, Leibnitz, Bernoulliy, sobre todo, Lagrange, que tanto haban contribuido al desarrollo del clculo inni-tesimal, se ocuparon de obtener mximos y mnimos condicionados de determinadasfunciones.Posteriormente el matemtico francs Jean Baptiste-Joseph Fourier (1768-1830)fue el primero en intuir, aunque de forma imprecisa, los mtodos de lo que actual-mente llamamos programacin lineal y la potencialidad que de ellos se deriva.Si exceptuamos al matemtico Gaspar Monge (1746-1818), quien en 1776 se in-teres por problemas de este gnero, debemos remontarnos al ao 1939 para encon-trar nuevos estudios relacionados con los mtodos de la actual programacin lineal.En este ao, el matemtico ruso Leonodas Vitalyevich Kantarovitch publica unaextensa monografa titulada Mtodos matemticos de organizacin y planicacinde la produccin en la que por primera vez se hace corresponder a una extensa gamade problemas una teora matemtica precisa y bien denida llamada, hoy en da,programacin lineal.En 1941-1942 se formula por primera vez el problema de transporte, estudiado in-dependientemente por Koopmans y Kantarovitch, razn por la cual se suele conocercon el nombre de problema de Koopmans-Kantarovitch.Tres aos ms tarde, G. Stigler plantea otro problema particular conocido con elnombre de rgimen alimenticio optimal.1314 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACIN1.1.1 Orgenes de la Investigacin operativaLa Investigacin Operativa (I.O.) es una ciencia relativamente joven.Los pri-meros resultados importantes se consiguieron durante la II Guerra Mundial. En labatalla de Inglaterra el ejrcito alemn someti a los britnicos a un duro ataqueareo.El gobierno estaba explorando cualquier mtodo para defender el pas.Losingleses tenan una fuerza area hbil, aunque pequea, pero dispona de radares.Se plantearon sacarle al radar el mximo rendimiento. El gobierno convoc a mediadocena de cientcos de diversas disciplinas para resolver este problema. As dise-aron una nueva tcnica, la Investigacin Operativa, que duplic la efectividad delsistema de defensa area mediante una localizacin ptima para las antenas y unamejor distribucin de las seales.Alentados por este xito, Inglaterra organiz equipos similares para resolver otrosproblemas militares. EE.UU. hizo lo mismo cuando entr en guerra, crendose elproyecto (SCOOP Scientic Computation of Optimum Programs) que desarroll elalgoritmo Simplex (George B. Dantzing, 1947).Una de las primeras aplicaciones de los estudios del grupo SCOOP fue el puenteareo de Berln.Se continu con innidad de aplicaciones de tipo preferentementemilitar.En 1946 comienza el largo perodo de la guerra fra entre la antigua Unin So-vitica (URSS) y las potencias aliadas (principalmente, Inglaterra y Estados Unidos).Uno de los episodios ms llamativos de esa guerra fra se produjo a mediados de 1948cuando la URSS bloque las comunicaciones terrestres desde las zonas alemanas enpoder de los aliados con la ciudad de Berln, iniciando el bloqueo de Berln. A los alia-dos se les plantearon dos posibilidades: o romper el bloqueo terrestre por la fuerza, ollegar a Berln por el aire. Se adopt la decisin de programar una demostracin tc-nica del poder areo norteamericano; a tal efecto, se organiz un gigantesco puenteareo para abastecer la ciudad: en diciembre de 1948 se estaban transportando 4500toneladas diarias; en marzo de 1949, se lleg a las 8000 toneladas, tantas como setransportaban por carretera y ferrocarril antes del corte de las comunicaciones. Enla planicacin de los suministros se utiliz la programacin lineal. (El 12 de mayode 1949, los soviticos levantaron el bloqueo).En estos aos posteriores a la Segunda Guerra Mundial, en Estados Unidos seasumi que la ecaz coordinacin de todas las energas y recursos de la nacin eraun problema de tal complejidad, que su resolucin y simplicacin pasaba necesa-riamente por los modelos de optimizacin que resuelve la programacin lineal.Paralelamente a los hechos descritos se desarrollan las tcnicas de computaciny los ordenadores, instrumentos que haran posible la resolucin y simplicacin delos problemas que se estaban gestando.En 1952 un ordenador SEAC del National Bureau of Standars proporcion laprimera solucin de un problema de programacin lineal, que es el tema del que nosocuparemos al principio del libro. Se obtuvieron soluciones para los problemas dedeterminar la altura ptima a la que deberan volar los aviones para localizar los1.1. ORGENES Y DESARROLLO 15submarinos enemigos, adems resolvieron el problema del reparto de fondos entrecombustible, armamento, instrumentos, equipos, etc. . . Tambin se determin laprofundidad a la que haba que enviar las cargas para alcanzar a los submarinosenemigos con mayor efectividad. En este aspecto los resultados de la InvestigacinOperativa multiplicaron por cinco la ecacia de la fuerza area.Los fundamentos matemticos de la programacin lineal se deben al matemticonorteamericano de origen hngaro Janos von Neuman (1903-1957), quien en 1928public su famoso trabajo Teora de Juegos.En 1947 conjetura la equivalencia delos problemas de programacin lineal y la teora de matrices desarrollada en sustrabajos. La inuencia de este respetado matemtico, discpulo de David Hilberten Gotinga y, desde 1930, catedrtico de la Universidad de Princenton de EstadosUnidos, hace que otros investigadores se interesaran paulatinamente por el desarrolloriguroso de esta disciplina.En 1958 se aplicaron los mtodos de la programacin lineal a un problema con-creto: el clculo del plan ptimo de transporte de arena de construccin a las obrasde edicacin de la ciudad de Mosc. En este problema haba 10 puntos de partiday 230 de llegada. El plan ptimo de transporte, calculado con el ordenador Strenaen 10 das del mes de junio, rebaj un 11% los gastos respecto a los costes previstos.Estos mtodos se aplicaron posteriormente a problemas comerciales y de la in-dustria, lo que contribuy a que la Investigacin Operativa se desarrollara extraor-dinariamente entre los aos 50 y 60.En la sociedad civil ya se haban planteado anteriormente diversos problemas pro-pios de la Investigacin Operativa en un disciplina que se conoci como Investigacinde Empresas o Anlisis de Empresas, pero lo que aport la II Guerra Mundial fueel desarrollo de mtodos sistemticos para afrontar estos problemas, principalmenteel mtodo Simplex.El campo de las aplicaciones no blicas de la Investigacin Operativa es muy am-plio. sta resuelve problemas tales como el uso adecuado de los equipos de trabajoy de personal, localizacin y volumen de sucursales, campaas de publicidad, trans-porte de mercancas, problemas de grafos y redes, problemas de colas, etc. Tambintiene aplicaciones en agricultura y ganadera dando respuestas que permitan la mejordistribucin de los cultivos o la alimentacin ms econmica para el ganado.Como ya hemos comentado anteriormente, otro motor importantsimo del de-sarrollo de la Investigacin Operativa ha sido el ordenador que permite resolverproblemas reales en que intervienen un gran nmero de variables en un tiempo ra-zonable.En Espaa el Instituto de Estadstica de Madrid comenz sus cursos en 1950con una conferencia sobre aplicaciones de la Investigacin Operativa, justo cuandoapareci el libro de Morse-Kimbal en el que se exponan los trabajos de los equiposcientcos que se constituyeron en la guerra. Se public a partir de 1950 una revistaespecializada: Trabajos de Estadstica en Investigacin Operativa con un nivelsimilar al de otros pases europeos, a pesar de que nuestra industria estaba muyatrasada. Adelantndose a otros paises se cre un Instituto de Investigacin Opera-16 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACINtiva que colabor con las empresas espaolas a introducir la Investigacin Operativaen la resolucin de sus problemas. De esta forma, se reconoci la importancia deesta materia, y como consecuencia se incorpor a los planes de estudio de facultadesy escuelas universitarias.Destacamos asimismo a Sixto Ros que ha jugado un papel fundamental en elcampo de la Estadstica y la Investigacin Operativa en Espaa. Tambin se puededestacar el gran nmero de discpulos de este profesor, incluidos sus propios hijos,que han contribuido y contribuyen al desarrollo de la Estadstica y la InvestigacinOperativa en las universidades espaolas, aportando un gran nmero de trabajos ypublicaciones.En el siglo XX se produce la aparicin de nuevas ramas de las matemticas, porlo que es preciso resaltar algunos aspectos que la caracterizan: Teora de Juegos. La Programacin Lineal. La Investigacin Operativa. lgebra Computacional.1.1.2 La Teora de JuegosAs como la Teora de la Probabilidad surgi del estudio de los juegos de azar y deldeseo de los jugadores profesionales de encontrar formas de mejorar sus ventajas,la teora de juegos nace al intentar dar precisin a la nocin de comportamientoracional". El estudio matemtico de los juegos ofrece la posibilidad de nuevas formasde comprensin y precisin en el estudio de la Economa.La Teora de Juegos utiliza herramientas bsicas de las matemticas, el Algebra,en concreto las matrices, la probabilidad e incluso el teorema del punto jo deBrouwer para demostrar que existe un nico plan de accin estable" o racionalque representa la estrategia ptima. Actualmente se aplica en Economa y en laEstrategia Militar.1.1.3 La Programacin LinealLa Programacin Lineal es una tcnica reciente de la Matemtica Aplicada quepermite considerar un cierto nmero de variables simultneamente y calcular lasolucin ptima de un problema dado considerando ciertas restricciones.Su nombre se debe a que en un principio trataba de resolver problemas que seplanteaban en trminos matemticos con funciones lineales. En la actualidad seaplica tambin a problemas no lineales.1.1. ORGENES Y DESARROLLO 17La teora de la Programacin Lineal ha sido desarrollada por Gohn, Von Neu-mann, Dantzig, Koopmans, W. Cooper y Charnes entre otros matemticos, estads-ticos y economistas.El proceso para encontrar la solucin ptima es el siguiente: Se plantea el pro-blema, se traduce a un modo algebraico, se analizan las restricciones y se buscael ptimo dependiendo del criterio que se quiera aplicar. La respuesta se puedeencontrar por varios mtodos. El ms general es el diseado por Dantzig, que sedenomina mtodo del Simplex.Estos mtodos emplean un teorema dual" mediante el cual un problema demaximizacin lleva emparejado uno de minimizacin.Se utiliza en problemas de transportes, negocios, en logstica militar y en laactualidad las aplicaciones tambin se dirigen hacia el rea industrial, a la resolucinde problemas de produccin, etc.La Programacin Lineal se ha convertido en una herramienta de las Matemticastanto tericas como aplicadas que utiliza el Algebra, la Teora de Matrices y estrelacionada con la Estadstica y la Teora de Juegos.1.1.4 La Investigacin OperativaUna caracterstica importante del siglo XX es el desarrollo de las distintas ramasde las Matemticas y el descubrimiento de los vnculos entre ellas. Pero tambin elresurgir de nuevas ramas como es la Investigacin Operativa.Aunque debe su nombre a su aplicacin a las operaciones militares, y empieza adesarrollarse en la II Guerra Mundial, sus orgenes se remontan al siglo XVII. Pascaly Fermat, que haban inventado el concepto de esperanza matemtica, inician losestudios de Investigacin Operativa junto con Jacques Bernoulli y Waldegrave alintentar resolver problemas de decisin en el campo de la incertidumbre.Posteriormente, Monge (1746-1818) se propuso y logr resolver un problemaeconmico de naturaleza combinatoria: el de los desmontes y rellenos. Borel (1871-1956) present la Teora matemtica de los Juegos en la Academia de Ciencias dePars, mientras que Erlang estableca la de las lneas de espera, que utiliz para laconcepcin de redes telefnicas. En vsperas de la II Guerra Mundial, Kantorovitchconceba y aplicaba la programacin lineal a la planicacin. Por ello cuando el fsicoingls Blackett, en 1938, fue llamado para reunir el primer equipo de investigadoresoperativos, ya le haban precedido personalidades en dicho campo.Blackett tuvo el mrito de encontrar la frmula que le permiti tratar de formarpida y con xito la difcil cuestin de la implantacin ptima de los radares devigilancia britnicos, que desempearon un papel tan decisivo en la Batalla deInglaterra. Desde que naliz la guerra se ha utilizado con xito para resolverproblemas de mbito empresarial, industrial, etc.Es justo sealar que el desarrollo de la investigacin operativa ha sido posible18 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACINgracias al desarrollo de los medios informticos que son los que posibilitan resolverlos problemas en la prctica, como gestin de grandes conjuntos econmicos, orga-nizacin sistemtica de tareas complejas o controlar toda una red elctrica nacional.Debido al xito de la Investigacin Operativa en el campo militar, los industria-les recurrieron a sta para solucionar los problemas generados por la complejidad yespecializacin que iba en aumento dentro de sus organizaciones. En 1951, la Inves-tigacin Operativa ya se haba introducido por completo en la industria britnicay estaba en proceso de hacerlo en la estadounidense. Desde entonces, su desarrolloha sido muy rpido, en gran medida gracias a la ayuda del ordenador que, desdeel momento de su aparicin, queda irremediablemente unido a la Teora de la Pro-babilidad, a la Estadstica y especialmente a la propia Investigacin Operativa yaument enormemente las posibilidades de la Ciencia.Segn Hillier y Lieberman (1991), en esencia la contribucin del enfoque de laInvestigacin Operativa proviene principalmente de: La estructuracin de una situacin de la vida real como un modelo matemtico,logrando una abstraccin de los elementos esenciales para que pueda buscarseuna solucin que concuerde con los objetivos del que toma decisiones. El anlisis de la estructura de tales soluciones y el desarrollo de procedimientossistemticos para obtenerlas. El desarrollo de una solucin, incluyendo la teora matemtica si es necesario,que lleva el valor ptimo de la medida de lo que se espera del sistema.Actualmente la Investigacin Operativa incluye gran cantidad de ramas como laProgramacin Lineal y No Lineal, Programacin Dinmica, Simulacin, Teora deColas, Teora de Inventarios, Teora de Grafos, etc. y se encuentra muy difundida,con aplicaciones en campos muy variados y en particular muy unida a la Economay a la Informtica y por supuesto a la Estadstica y Teora de Probabilidad, consti-tuyendo una materia universitaria con entidad propia.1.2 Modelizacin de un problema de P. L.Introduciremos las lneas generales del modelo de Programacin Lineal (P.L.) ilus-trndolo con el siguiente ejemplo:Ejemplo 1 Alimentacin del ganadoNos proponemos alimentar el ganado de una granja de la forma que sea la mseconmica posible. La alimentacin debe contener cuatro tipos de nutrientes quellamamos A,B,C,D. Estos componentes se encuentran en dos tipos de piensos M yN. La cantidad, en gramos, de cada componente por kilo de estos piensos viene dada1.2. MODELIZACIN DE UN PROBLEMA DE P. L. 19en la tabla siguiente:A B C DM 100 100 200N 100 200 100Un animal debe consumir diariamente al menos 0,4 Kg del componente A, 0,6 Kg delcomponente B, 2 Kg. del componente C y 1,7 Kg. del componente D. El compuestoM cuesta 20 pts/kg y el N 8 pts/kg. Qu cantidades de piensos M y N debenadquirirse para que el gasto de comida sea el menor posible?Para resolver el problema construimos un modelo matemtico del mismo. Laconstruccin de este modelo puede hacerse siguiendo el proceso que se describe acontinuacin:1.2.1 Formulacin de los modelosPaso 1: Determinar las variables de decisin o de entrada y representarlas alge-braicamente. Tomamos en este caso las variables:x1 = cantidad de pienso M(en Kg)x2 = cantidad de pienso N(en Kg).Paso 2: Determinar las restricciones expresndolas como ecuaciones o inecuacionesde las variables de decisin.Las restricciones se deducen de la composicin requerida para la dieta (en Kg.):En componente A 0, 1x1+ 0x2 0, 4En componente B 0x1+ 0, 1x2 0, 6En componente C 0, 1x1+ 0, 2x2 2En componente D 0, 2x1+ 0, 1x2 1, 7Paso 3: Expresar todas las condiciones implcitamente establecidas por la natu-raleza de las variables (que no puedan ser negativas, que sean enteras, que slopueden tomar determinados valores, etc.)En este ejemplo los cantidades de pienso no pueden tomar valores negativospor lo tanto, deberamos imponer que sean x1 0; x2 0. No imponemosotras restricciones al tipo de variables.Paso 4: Determinar la funcin objetivo.El objetivo de este problema es:Minimizar gasto= Min Z = 20x1 + 8x2.El modelo por tanto es el siguiente:Min Z= 20x1 + 8x2s.a.: 0, 1x1 + 0x2 0, 40x1 + 0, 1x2 0, 60, 1x1 + 0, 2x2 20, 2x1 + 0, 1x2 1, 7x1, x2 020 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACIN1.3 Modelizacin de diversos problemas de I.O.Vamos a modelizar ahora diversos problemas que se pueden plantear en la Investi-gacin Operativa (I.O.) que enunciamos a continuacin:Ejemplo 2 Transporte de tropa.Un destacamento militar formado por 40 soldados de Ingenieros, 36 especia-listas dinamiteros, 88 antiguerrilleros y 120 infantes como tropa de apoyo, ha detransportarse hasta una posicin estratgica importante. En el parque de la basese dispone de 4 tipos de vehculos A,B,C,D, acondicionados para el transporte detropas. El nmero de personas que cada vehculo puede transportar es 10,7,6,9 de laforma en que se detalla en la siguiente tabla:Ingenieros Dinamiteros Antiguerrillas InfantesA 3 2 1 4B 1 1 2 3C 2 1 2 1D 3 2 3 1Los gastos de gasolina de cada vehculo hasta el punto de destino se estiman en160, 80, 40 y 120 litros respectivamente.Si queremos ahorrar gasolina.Cuntosvehculos de cada tipo habr que utilizar para que el gasto de gasolina sea el menorposible?P1) xi = novehculos de cada tipo que se usen.P2)3x1 +x2 + 2x3 + 3x4 402x1 +x2 +x3 + 2x4 36x1 + 2x2 + 2x3 + 3x4 884x1 + 3x2 +x3 +x4 120P3) xi 0; xi son enteros.P4) Minimizar gasto gasolina = 160x1 + 80x2 + 40x3 + 120x4Min Z= 160x1 + 80x2 + 40x3 + 120x4s.a.: 3x1 +x2 + 2x3 + 3x4 402x1 +x2 +x3 + 2x4 36x1 + 2x2 + 2x3 + 3x4 884x1 + 3x2 +x3 +x4 120xi 0 ; enteros.Ejemplo 3 Transporte de mercancas.Un fabricante desea despachar varias unidades de un artculo a tres tiendas T1,T2, T3. Dispone de dos almacenes desde donde realizar el envo, A y B. En el1.3. MODELIZACIN DE DIVERSOS PROBLEMAS DE I.O. 21primero dispone de 5 unidades de este artculo y el segundo 10. La demanda de cadatienda es 8, 5 y 2 unidades respectivamente. Los gastos de transporte de un artculodesde cada almacn a cada tienda estn expresados en la tabla:T1 T2 T3A 1 2 4B 3 2 1Cmo ha de realizar el transporte para que sea lo ms econmico posible?xi = node unidades transportadas.Problema equilibrado (Oferta=Demanda):T1 T2 T3 DisponibilidadA x1x2x35B x4x5x610Demanda 8 5 2Min Z= x1 + 2x2 + 4x3 + 3x4 + 2x5 +x6s.a.: x1 +x2 +x3 = 5x4 +x5 +x6 = 10x1 +x4 = 8x2 +x5 = 5x3 +x6 = 2xienteros y no negativos.Ejemplo 4 rboles frutales.Un agricultor tiene una parcela de 640 m2para dedicarla al cultivo de rbolesfrutales:naranjos, perales y manzanos. Se pregunta de qu forma repartir la su-percie de la parcela entre las tres variedades para conseguir el mximo beneciosabiendo que:Cada naranjo necesita un mnimo de 16 m2, cada peral 4 m2y cada manzano 8m2.Dispone de 900 horas de trabajo al ao, necesitando cada naranjo de 30 horas alao, cada peral 5 y cada manzano 10.Los benecios unitarios son de 50, 25 y 20 unidades monetarias respectivamentepor cada naranjo, peral y manzano respectivamente.x1 = nmero de naranjos.x2 = nmero de perales.x3 = nmero de manzanos.22 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACINMax Z = 50x1 + 25x2 + 20x3s.a.: 16x1 + 4x2 + 8x3 64030x1 + 5x2 + 10x3 900xi 0 ; enteros.Ejemplo 5 rboles frutales (II).1. Si se produce un incremento del precio de los naranjos que hace elevar el be-necio de cada naranjo a 120. Sigue siendo vlida la solucin?2. Si desciende el benecio de los perales hasta situarse en 10. Se modicar lasolucin del problema?3. Al agricultor se le plantea la posibilidad de cultivar limoneros que necesitan12m2de tierra, 20 horas anuales de mano de obra, proporcionando un beneciode 30 u.m. Cul ser ahora la situacin?4. A causa de la sequa, el agricultor tiene restricciones para el riego: Le hanasignado 200m3de agua anuales. Las necesidades son de 2m3por naranjo,1m3por peral y 1m3por manzano cada ao. Cmo repercute esta nuevasituacin en la solucin inicial?5. Se compra una parcela contigua de 160m2.Cul ser en este caso la nuevasolucin?6. De acuerdo con un estudio tcnico, para el tratamiento ptimo de los peralesse necesitan 10m2y 15 horas de mano de obra anuales. Sigue siendo vlidala solucin?1. Z = 120x1 + 25x2 + 20x32. Z = 50x1 + 10x2 + 20x33. x4 = nmero de limoneros.Max Z = 50x1 + 25x2 + 20x3 + 30x4s.a.: 16x1 + 4x2 + 8x3 + 12x4 64030x1 + 5x2 + 10x3 + 20x4 900xi 0 ; enteros.4. Nueva restriccin: 2x1 +x2 +x3 2005. 16x1 + 4x2 + 8x3 8006. El programa lineal se escribir:Z = 50x1 + 25x2 + 20x3s.a.: 16x1 + 10x2 + 8x3 64030x1 + 15x2 + 10x3 900xi 0 ; enteros.1.3. MODELIZACIN DE DIVERSOS PROBLEMAS DE I.O. 23Ejemplo 6 Asignacin de personal.Una empresa ha preseleccionado 5 candidatos para ocupar 4 puestos de trabajo enla empresa. Los puestos de trabajo consisten en manejar 4 mquinas diferentes (untrabajador para cada mquina). La empresa ha probado a los cinco trabajadores enlas 4 mquinas, realizando el mismo trabajo todos ellos en cada una de las mquinas,se obtuvieron los siguientes tiempos:Trabajo Mquina 1 Mquina 2 Mquina 3 Mquina 41 10 6 6 52 8 7 6 63 8 6 5 64 9 7 7 65 8 7 6 5Determinar qu trabajadores debe seleccionar la empresa y a qu mquinas debeasignarlos.La variable xij representa la accin el trabajador i se asigna a la mquina j.Los dos estados de esta accin son 0 (si no se asigna) y 1 (si se asigna).Min Z = 10x11 + 8x21 + 8x31 + 9x41 + 8x51++ 6x12 + 7x22 + 6x32 + 7x42 + 7x52++ 6x13 + 3x23 + 5x33 + 7x42 + 6x53++ 5x14 + 6x24 + 6x34 + 6x44 + 5x54s.a.: x11 +x21 +x31 +x41 1x21 +x22 +x23 +x24 1x31 +x32 +x33 +x34 1x41 +x42 +x43 +x44 1x51 +x52 +x53 +x54 1x11 +x21 +x31 +x41 +x51= 1x21 +x22 +x23 +x24 +x52= 1x31 +x32 +x33 +x34 +x53= 1x41 +x42 +x43 +x44 +x54= 1xij 0; xij{0, 1}Ejemplo 7 Camino mnimo.Una persona tiene que desplazarse a diario de un pueblo 1 a otro 7. Est es-tudiando usando el mapa de carreteras cul debe ser el trayecto ms corto. Lascarreteras y sus distancias estn en la gura 1.1.24 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACINFigura 1.1 Mapa de carreteras de los pueblos 1 al 7.La variable xij representa la accin desplazarse del pueblo i al j, indicando eluno que se produce tal desplazamiento, y el cero que no se produce.Min Z = 12x12 + 4x13 + 5x24 + 3x25 + 2x34 + 10x36+ 5x42 + 2x43 + 10x45 + 3x52 + 10x54++ 2x57 + 10x63 + 4x67s.a.: x12 +x13= 1x24 +x25x12x42x52= 0x34 +x36x13x43x63= 0x42 +x43 +x45x24x34x54= 0x52 +x54 +x57x25x45= 0x63 +x67x36= 0x57x67= 1xij 0 ; xij {0, 1}.Ejemplo 8 Localizacin.Una empresa tiene la exclusiva para la distribucin de un producto en 4 pobla-ciones. En un estudio de mercado se ha determinado la demanda potencial:Poblacin 1 Poblacin 2 Poblacin 3 Poblacin 43000 unidades 2000 unidades 2500 unidades 2700 unidadesSe sabe que los costes de transporte son de dos pesetas por Km y unidad transportada.La distancia entre los pueblos es la que gura en la tabla siguiente:1 2 3 41 - 25 35 402 - - 20 403 - - - 304 - - - -Para abaratar los costes de transporte se decide instalar un almacn con capacidadpara 6000 unidades en dos de estas cuatro ciudades.1.4. MODELOS DE PROGRAMACIN MATEMTICA 25Determinar en qu poblaciones deben instalarse los almacenes para que el costede distribucin sea mnimo.La variable xij representa la cantidad enviada del almacn i a la poblacin j, eyi toma el valor 1 si se selecciona la ciudad i para localizar el almacn. Toma elvalor 0 en caso contrario.Min Z = 50x12 + 70x13 + 60x14 + 50x21 + 40x23++ 80x24 + 70x31 + 40x32 + 60x34 + 60x41++ 80x42 + 60x43s.a.: x11 +x21 +x31 +x41 3000x12 +x22 +x32 +x42 2000x13 +x23 +x33 +x43 2500x14 +x24 +x34 +x44 2700y1 +y2 +y3 +y4= 2x11 +x12 +x13 +x146000y1 0x21 +x22 +x23 +x236000y2 0x31 +x32 +x33 +x346000y3 0x41 +x42 +x43 +x446000y4 0xij 0 ; yi {0, 1}.1.4 Modelos de programacin matemticaLa modelizacin general de un problema de programacin lineal es:Max(Min): Z = c1x1 +c2x2 +cnxnsujeto a: a11x1 +a12x2 + +a1nxn(=) b1. . . . . . . . . . . . . . . . . . . . . . . . . . .am1x1 +am2x2 + +amnxn(=) bmx1 0; x2 0; . . . xn 0.donde tanto la funcin objetivo como las restricciones son funciones lineales.Si la funcin objetivo y/o las restricciones no fueran funciones lineales diremosque el problema es de programacin no lineal.En la programacin cuadrtica la funcin objetivo es de segundo grado y lasrestricciones si existen son lineales.En el caso particular de un problema de programacin lineal en el que las variablesde decisin tomen valores enteros, se llama programacin entera.Cuando las variables slo toman valores 0,1 se llama programacin booleana.Los modelos de programacin lineal se incluyen en una clase ms amplia, la clasede modelos de optimizacin en los que se optimiza una funcin de las variablesde decisin, denominada funcin objetivo, sujeta a un conjunto de limitaciones orestricciones sobre las variables de decisin.26 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACINLa formulacin general de un problema de optimizacin es:Opt Z= f(x1, x2, . . . , xn)sujeto a gj(x1, . . . , xn) 0; j = 1, . . . , m donde,f es la funcin objetivo, (x1, x2, . . . , xn) son las variables de decisin, y tenemosunas restricciones caracterizadas por las desigualdades sobre (g1, g2, . . . , gm).En el caso de la programacin lineal la funcin objetivo y las restricciones sonlineales en las variables de decisin:f(x1, x2, . . . , xn) = c1x1 + +cnxn = CtXgj(x1, . . . , xn) = aj1x1 + +ajnxnbjA X b en notacion matricial, donde,C es el vector coecientes del objetivo, A es la matriz de coecientes tecnolgicos,b es el vector de trminos constantes y X el vector de variables de decisin.1.5 El mtodo geomtricoEn algunos casos sencillos vamos a poder resolver problemas de programacin linealusando el mtodo geomtrico. La nica restriccin que tendremos que considerar esque tenga dos variables de decisin. Ilustramos este mtodo con el ejemplo siguiente:Ejemplo 9Max Z= 2x1 +x2s.a.: 5x1 + 2x2 103x1 + 5x2 15x1, x2 0.Paso 1: Representamos en un sistema de coordenadas adecuadas las rectas quecorresponden a las restricciones.5x1 + 2x2 = 10 x1 = 0 x2 = 5x1 = 2 x2 = 03x1 + 5x2 = 15 x1 = 0 x2 = 3x1 = 5 x2 = 0Paso 2. Se representa la regin del plano que verica simultneamente todas lasrestricciones. Esta regin se conoce con el nombre de regin factible. La reginfactible est marcada en la gura siguiente:1.5. EL MTODO GEOMTRICO 27Figura 1.2 Dibujo de la Regin Factible. Ejemplo 9.Paso 3.Representamos la recta correspondiente al valor 0 de la funcin objetivo:Z = 2x1 +x2 = 0; 2x1 +x2 = 0 x1 = 0 x2 = 0x1 = 1 x2 = 2Si desplazamos la recta paralelamente hacia arriba el valor de Z va aumentando.As la paralela a 2x1 +x2 = 0 que pasa por (1, 0) es 2x1 +x2 = 2 y nos da un valordel objetivo Z = 2 1 + 0 = 2.Lo ms alto que podemos desplazar la recta sin dejar la regin factible es hastael punto A, que es el punto de corte de las dos rectas:5x1 + 2x2= 103x1 + 5x2= 15_15x1 + 6x2= 3015x125x2= 75_Si sumamos ambas, obtenemos el punto A, con coordenadas:19x2 = 45 x2= 45/19x1= 20/19.28 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACINEn el punto A se obtiene el ptimo, cuyo valor en la funcin objetivo valeZ = 2 2019 + 4519 = 8519 = 4. 473 7.1.5.1 Descripcin del mtodo geomtrico1) Dibujar un sistema de coordenadas cartesianas en el que las variables de decisincorresponden a los ejes. Se elegir una escala adecuada (no necesariamente lamisma en ambos ejes). Representar las rectas correspondientes a las distintasrestricciones.2) Representar las regiones del plano que cumplen cada una de las restricciones,incluidas las de no negatividad. La interseccin de estas regiones nos dara laregin de soluciones o regin factible (si la interseccin es el problema notiene solucin).3) Si la funcin objetivo es Z = c1x1 + c2x2, tendremos que representar la rectar c1x1 + c2x2 = 0 y estudiar la variacin de Z al desplazarnos dentro dela regin factible mediante rectas paralelas a r c1x1 + c2x2 = 0. En losproblemas de maximizacin la solucin ser el punto de la regin factible quenos de un Z mayor, en los de minimizacin el que nos proporcione un Z menor.Ejemplo 10Max Z= 6x1 + 10x2s.a.: 5x1 + 2x2 103x1 + 5x2 15x1, x2 0.Paso 1.5x1 + 2x2 = 10 x1 = 0 x2 = 5x1 = 2 x2 = 03x1 + 5x2 = 15 x1 = 0 x2 = 3x1 = 5 x2 = 06x1 + 10x2 = 0 x1 = 0 x2 = 0x1 = 1 x2 = 35Paso 2. Ver gura 1.3.1.5. EL MTODO GEOMTRICO 29Figura 1.3 Dibujo de la Regin Factible. Ejemplo 10.Paso 3.La recta paralela a 6x1 + 10x2 = 0 que pasa por (1, 0) es 6x1 + 10x2 = 6 convalor del objetivo Z = 6 1 + 10 0 = 6.Tiene soluciones mltiples pues, las dos rectas:_ 3x1 + 5x2= 156x1 + 10x2= 0tienen la misma pendiente, son paralelas y, en todos los puntos desde A hastaB se obtiene el mismo valor para la funcin objetivo.A_2019, 4519_ y B(0, 3)El valor del objetivo en el segmento ABes Z = 6 0 + 10 3 = 30.Ejemplo 11Min Z= x14x2s.a.: x1 +x2 6x12x2 24x1 + 3x2 12x1, x2 030 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACINPaso 1.x1 +x2 = 6 x1 = 0 x2 = 6x1 = 6 x2 = 0x12x2 = 2 x1 = 0 x2 = 1x1 = 2 x2 = 04x1 + 3x2 = 12 x1 = 0 x2 = 4x1 = 3 x2 = 0x14x2 = 0 x1 = 0 x2 = 0x1 = 4 x2 = 1Paso 2. Ver gura 1.4.Figura 1.4 Dibujo de la regin factible. Ejemplo 11.Paso 3.La recta paralela a x1 4x2 = 0 que pasa por (1,0) sera x1 4x2 = 1 conZ = x14x2 = 1 1 4 0 = 1.1.5. EL MTODO GEOMTRICO 31Tengo que ir hacia arriba porque el trmino independiente ha aumentado y loque tengo que hacer es minimizar. El punto donde se obtiene el ptimo es elpunto A, con coordenadas:A _ x1 +x2 = 64x1 + 3x2 = 12 donde,x1 = 67, x2 = 367 .Y la solucin ptima es: Z = x14x2 = 1387 .Nota: Si el programa hubiese estado escrito en forma maximizante, el ptimose obtendra en el punto B(2, 0), como puede verse en la gura 1.4.Ejemplo 12Max Z= 2x1x2s.a.: x1x2 25x12x2 16x1, x2 0Paso 1.x1x2 = 2 x1 = 0 x2 = 2x1 = 2 x2 = 05x12x2 = 16 x1 = 2 x2 = 3x1 = 165x2 = 02x1x2 = 0 x1 = 0 x2 = 0x1 = 1 x2 = 2Paso 2. Ver gura 1.5.32 TEMA 1. INTRODUCCIN A LA TEORA DE OPTIMIZACINFigura 1.5Dibujo de la Regin factible. Ejemplo 12.Paso 3.La recta paralela a 2x1x2 = 0 que pasa por (1, 0) toma el valor Z = 210 =2. Luego la solucin ptima es el punto A, que se obtiene como:A _ x1x2 = 25x12x2 = 16donde, x1 = 4, x2 = 2.Y la funcin objetivo vale Z = 2x1 x2, y por tanto la solucin ptima valeZ = 8 2 = 6. Si en el problema hubisemos tenido que minimizar la solucinsera ilimitada.1.5.2 Resumen del mtodo geomtrico Si la regin factible es el programa lineal no tiene solucin factible. Si la regin factible es acotada entonces siempre hay solucin nita, que puedeser nica o mltiple. Si la regin factible es no acotada entonces puede ocurrir que haya: Solucin nita (nica o mltiple). Solucin ilimitada.Tema 2Programacin Lineal2.1 Modelo general de programacin linealUn programa lineal consiste en encontrar un vector X = (x1, x2, . . . , xn) que opti-mice una funcin lineal Z. Las coordenadas de este vector estn sujetas a ciertasrestricciones que se expresan en ecuaciones o inecuaciones lineales.Opt. Z = c1x1 +c2x2 + +cnxns.a.: a11x1 +a12x2 + +a1nxn(=) b1a21x1 +a22x2 + +a2nxn(=) b2. . . . . . . . . . . .am1x1 +am2x2 + +amnxn(=) bmxi 0 i = 1, 2, . . . , n.___Todos los cj son conocidos, tambin los aij y los bi.A los coecientes cj se les denomina coecientes de coste, a los aij coecientestecnolgicos y a los bi coecientes de recursos.Programa lineal en forma estndar. Decimos que un programa lineal esten forma estndar si todas las restricciones son de igualdad y todos los biconi = 1, 2, . . . , m son positivos o nulos.Veamos un ejemplo de un programa lineal en forma estndar:Ejemplo 13 Problema en forma estndarMax Z = 3x1 + 2x2x3s.a.:2x1 +x23x3= 43x12x2x3= 2x1, x2, x3 0___3334 TEMA 2. PROGRAMACIN LINEALA veces puede aparecer en forma matricial:Opt. Z = ctXs.a.: AX = bX 0___donde c =_____c1c2...cn_____, X =_____x1x2...xn_____, b =_____b1b2...bm_____yA =___a11. . . a1n.........am1. . . amn___.Tambin puede aparecer en forma vectorial:Opt. Z = ctXs.a.: a1x1 +a2x2 + +anxn = bX 0___donde aj es la j sima columna de la matriz A.Ejemplo 14 El modelo anterior en forma vectorial sera:Opt. Z = (3, 2, 1)__ x1x2x3__s.a.: _ 23_x1 +_12_x2 +_ 31_x3 =_ 42_X 0Programa lineal en forma cannica maximizante. Decimos que un programalineal est en forma cannica maximizante si todas las restricciones son de desigual-dad del tipo y el programa es de maximizar.Ejemplo 15 Forma cannica maximizanteMax Z = 3x1 + 2x2x3s.a.:2x1 +x23x3 43x12x2x3 2x1, x2, x3 0___2.1. MODELO GENERAL DE PROGRAMACIN LINEAL 35Programa lineal en forma cannica minimizante. Decimos que un programalineal est en forma cannica minimizante si todas las restricciones son en desigual-dad () y el programa es de minimizar.Ejemplo 16 Forma cannica minimizanteMin Z = 3x1 + 2x2x3s.a.:2x1 +x23x3 43x12x2x3 2x1, x2, x3 0___Cmo pasar cualquier modelo a forma estndar? Paso 1:Si algn bj esnegativo se multiplica la restriccin por 1.Paso 2: Si la variable xr no tiene condicin de no negatividad, expresarla comodiferencia de dos variables positivas de la forma:xr = xrxr; xr 0; xr 0Paso 3: Las desigualdades se convierten en igualdades mediante la introduccin devariables de holgura positivas de la forma:n

aijxj bi=n

aijxj +si = bi; si 0n

aijxj bi=n

aijxjti = bi; ti 0Ejemplo 17 Pasar a forma estndar el programa lineal:Max Z = 3x1 +x2s.a.:x1 +x2 82x1 + 5x2 20x1, x2 0___Los pasos 1 y 2 no son necesarios en este caso.Paso 3:Max Z = 3x1 +x2s.a.:x1 + 2x2 +x3= 82x1 + 5x2 +x4= 20x1, x2, x3, x4 0___36 TEMA 2. PROGRAMACIN LINEALEjemplo 18 Pasar a forma estndar el programa lineal:Max Z = x1 +x2s.a.:x1 + 5x2 52x1x2 4x1, x2 0___Paso 1: 2x1x2 4 2x1 +x2 4Paso 2: Son mayores que cero.Paso 3:Max Z = x1 +x2s.a.:x1 + 5x2 +x3= 52x1 +x2x4= 4x1, x2, x3, x4 0___Ejemplo 19 Pasar a forma estndar el programa lineal:Min Z = 5x1 + 2x2s.a.:6x1 +x2 64x1 + 3x2 5x1 0x2 sin restriccion___Paso 1: No es necesario.Paso 2: x2 = x2x2; x2, x2 0Paso 3:Min Z = 5x1 + 2x22x2s.a.:6x1 +x2x2 x3= 64x1 + 3x23x2 +x4= 5x1, x2, x2, x3, x4 0___Cambiar el sentido de optimizacin. Un problema de maximizacin puedepasarse a otro de minimizacin y viceversa:Max z =n

cjxj Min z =n

(cj)xj; z = zMin z =n

cjxj Max z =n

(cj)xj; z = z2.1. MODELO GENERAL DE PROGRAMACIN LINEAL 37Cambiar el sentido de una desigualdad.n

aijxj bi=n

(aij)xj bin

aijxj bi=n

(aij)xj biConvertir igualdades en desigualdades.n

aijxj= bi _ naijxj bi

naijxj bi _ naijxj bi

n(aij)xj bi _ n(aij)xj bi

naijxj biEjemplo 20 Dado el programa lineal:Min Z = 3x1 + 2x2x3s.a.:x12x2= 43x1 +x3= 3x1 0, x2, x3 0___pasarlo a forma cannica maximizante, y forma cannica minimizante.Como la variable primera no cumple la condicin de no negatividad se realizarel cambio de variable x1 = x1 0.Forma cannica maximizante:Max Z = 3x12x2 +x3x12x2 = 4 _ x12x2 4x12x2 4 _ x12x2 4x1 + 2x2 43x1 +x3 = 3 _ 3x1 +x3 33x1 +x3 3 _ 3x1 +x3 33x1x3 3Max Z = 3x12x2 +x3s.a.:x12x2 4x1 + 2x2 43x1 +x3 33x1x3 3x1 0, x2, x3 0___38 TEMA 2. PROGRAMACIN LINEALForma cannica minimizante:Min Z = 3x1 + 2x2x3s.a.:x1 + 2x2 4x12x2 43x1x3 33x1 +x3 3x1 0, x2, x3 0___2.2 Nociones previasDecimos que {a1, a2, ..., an} es un conjunto de vectores linealmente depen-diente si existen 1, 2, ....n constantes no todas nulas de forma que se cumple1a1 +2a2 +3a3 +... +nan =

0. Son vectores linealmente independientessi la igualdad anterior slo se cumple para 1 = 2 = ... = n = 0.Decimos que el vector v se puede expresar como combinacin lineal convexade los vectores {a1, a2, ..., an} si existen constantes positivas 1, 2, ...n de formaque se verique:v = 1a1 +2a2 +... +nan y 1 +2 +... +n = 1.Sean A1 y A2 dos puntos de IRn; se llama segmento lineal cerrado de extremosA1 y A2 al conjunto:{A IRn/A = A1 + (1 )A2; 0 1}Un conjunto C IRnes un conjunto convexo cuando dados dos puntos cua-lesquiera de C el segmento lineal cerrado determinado por esos puntos est contenidoen C.Decimos que un punto x de un conjunto convexo C es un punto extremoo vrtice de C si no existen dos puntos x1, x2 C , x1 = x2, de forma quex = x1 + (1 )x2 para algn / 0 < < 1.Se llama semiespacio cerrado al conjunto de puntos de IRnque cumple1x1 +2x2 +... +nxn Se llama poliedro al conjunto interseccin de una cantidad nita de semiespacioscerrados.Teorema 1 Todo semiespacio cerrado es un conjunto convexo.Demostracin:Sea S = {(x1, x2, ...xn) IRn/ 1x1 +2x2 +... +nxn }. Sean Y y Z dospuntos de S, entonces se cumple:2.3. DEFINICIONES SOBRE LAS SOLUCIONES DE UN PROBLEMA 39Y = (y1, y2, ...yn) S 1y1 +2y2 +... +nyn .Z = (z1, z2, ...zn) S 1z1 +2z2 +... +nzn .Demostraremos que cualquier punto del segmento Y Z verica la condicin:Y + (1 )Z S ; 0 1PeroY + (1 )Z = (y1, y2, . . . , yn) + (1 )(z1, z2, . . . , zn) == (y1 + (1 )z1, y2 + (1 )z2, . . . , yn + (1 )zn)Ahora sustituimos y comprobamos que sea menor o igual a .1[y1 + (1 )z1] +2[y2 + (1 )z2] + +n[yn + (1 )zn] == 1y1 +1(1 )z1 +2y2 +2(1 )z2 + +nyn +n(1 )zn == (1y1 +2y2 + +nyn) + (1 )(1z1 +2z2 + +nzn) + (1 ) = + = LuegoY + (1 )Z S.Corolario 1 Un poliedro es un conjunto convexo.Teorema 2 Si C es un conjunto convexo acotado con un nmero nito de puntosextremos, entonces cualquier punto de C puede expresarse como combinacin linealconvexa de los puntos extremos. Esto es:A1, A2, . . . , Akpuntos extremos de C , A C =A = 1A1 +2A2 + +kAksiendo 1 +2 + +k = 1.2.3 Deniciones sobre las soluciones de un proble-maVamos a dar a continuacin algunas deniciones sobre las soluciones de un problemade programacin lineal.40 TEMA 2. PROGRAMACIN LINEALSe llama solucin factible a cualquier vector x que veriqueAx = b; x 0Se llama regin factible al conjunto de todas las soluciones factiblesF = {x IRn/ Ax = b; x 0}Decimos que X es una solucin factible ptima si optimiza en el sentidodeseado a la funcin objetivo. Esto es:CasodeMaximizacin Z=CtXcualquier otro X F =Z = CtX CtX = ZCaso de Minimizacin Z = CtXcualquier otro X F =Z = CtX CtX = ZSea X la solucin ptima del programa lineal, a la cantidad Z = CtX se lellama valor ptimo del programa lineal.Decimos que un programa lineal es no acotado cuando no tiene valor ptimonito: Max Z + o Min Z .Decimos que un programa lineal no tiene solucin, o que es infactiblecuando no existen valores para las variables xi que veriquen las restricciones.Esdecir, la regin factible es vaca, F = .Matriz bsica: Supongamos un sistema de ecuaciones del tipo:___11x1 +... +1nxn= b121x1 +... +2nxn= b2... ... .m1x1 +... +mnxn= bnDenotamos por A la matriz de los coecientes, A = (ij) . Si suponemos quer(A) = m, tomamos cualquier submatriz B de A, que sea cuadrada y rango m(determinante no nulo). La matriz B se llama matriz bsica.Si hacemos igual a cero las n m variables asociadas a los vectores columnasde A que no estn en B, la solucin del sistema formado por estas variables nulasy la solucin del sistema resultante BXB = b de m ecuaciones con m variables sedenomina solucin bsica asociada a la matriz bsica B.Se denominan variables bsicas a las variables del vector XB formado por lasm variables del sistema BXB = b. Las nm variables que se han igualado a cerose denominan variables no bsicas.Llamamos Base asociada a la matriz bsica B a los vectores cuyas coordenadasson cada una de las columnas de B.2.3. DEFINICIONES SOBRE LAS SOLUCIONES DE UN PROBLEMA 41Ejemplo 21 Encontrar las soluciones bsicas de:x1 + 2x2 +x3= 42x1 +x2 + 5x3= 5_A =_ 1 2 12 1 5_; r(A) = 2.Escogemos como matriz bsicaB =_ 12 _=_ 1 22 1_En este caso las variables bsicas son x1 y x2. La base est formada por losvectores _ 12_y _ 21_.Para calcular la solucin bsica correspondiente a la matriz B igualamos a 0 lavariable no bsica, x3 = 0.BXB = b ; = _ 1 22 1__ x1x2_=_ 45_=x1 + 2x2= 42x1 +x2= 5_XB = B1b _ x1x2_=_ 1 22 1_1_ 45_=_ 21_Una solucin bsica del sistema sera:x1 = 2; x2 = 1; x3 = 0.Podramos haber escogido como submatrizB =_ 1, 3 _=_ 1 12 5_y por tanto x2 = 0_ 1 12 5__ x1x2_=_ 45_=x1 +x3= 42x1 + 5x3= 5_42 TEMA 2. PROGRAMACIN LINEALXB = B1b = _ x1x3_=_ 1 12 5_1_ 45_=_51_Una solucin bsica del sistema sera:x1 = 5; x2 = 0; x3 = 1.Otra submatrizB =_ 2, 3 _=_ 2 11 5_y por tanto x1 = 0XB = B1b = _ x2x3_=_ 2 11 5_1_ 45_=_ 5/32/3_.Una solucin bsica del sistema sera:x1 = 0; x2 = 53; x3 = 23.Resumiendo, las soluciones bsicas de este ejemplo son:Variables bsicas Variables no bsicasx1 = 2; x2 = 1 x3 = 0x1 = 5; x3 = 1 x2 = 0x2 = 53; x3 = 23x1 = 0Si A es una matriz de dimensin m n y n > m, tendr _nm_ solucionesbsicas como mximo. En el ejemplo anterior _ 32_ = 3, y como hemos vistoanteriormente, hay 3 soluciones bsicas exactamente. A veces este nmero mxi-mo de soluciones bsicas no se alcanza porque algunas de las submatrices tienendeterminante nulo.Si XB es una solucin bsica y se cumple que los valores de las variables bsicasson mayores o iguales que cero, decimos que la solucin es bsica factible y quela base B es una base factible.Si en una solucin factible bsica, alguna de las variables bsicas vale cero, deci-mos que la solucin es factible bsica degenerada.Soluciones bsicas factibles adyacentes son dos soluciones bsicas factiblesque tienen en comn m1 variables bsicas.2.4. ALGUNOS RESULTADOS SOBRE LAS SOLUCIONES 43Ejemplo 22 Con referencia al ejemplo anterior:Variables bsicas Variables no bsicasx1 = 2; x2 = 1 x3 = 0 Solucin bsica factiblex1 = 5; x3 = 1 x2 = 0 Solucin bsica no factiblex2 = 53; x3 = 23x1 = 0 Solucin bsica factible2.4 Algunos resultados sobre las solucionesVamos a estudiar ahora algunos resultados relacionados con las soluciones de unproblema de programacin lineal.Teorema 3 El conjunto F de las soluciones factibles es convexo.DemostracinSuponemos F = {x IRn/ Ax = b; x 0}x1, x2 F probaremos que x = x1 + (1 )x2 F; 0 1x1 F Ax1 = b; x1 0x2 F Ax2 = b; x2 0Como x = x1 + (1 )x2 F si cumple que AX = b; esto es:A[x1 + (1 )x2] = Ax1 +A(1 )x2 = Ax1 + (1 )Ax2 == b + (1 )b = b +b b = b.Veamos que x 0x1 + (1 )x2 0 son sumas de dos productos 0; por tanto es 0.Luego se verica que x1 + (1 )x2 F. Luego F es convexo.Teorema 4 Sea A una matriz mn con r(A) = m y sea b un vector m1. SeaF el conjunto convexo formado por los vectores X que cumplen AX = b con X 0.Un vector X es una solucin bsica factible si y solo si X es punto extremo de F.Demostracin=Supongamos, sin prdida de generalidad, que X = (x1, x2, . . . , xm; 0, 0, . . . , 0)es una solucin bsica factible, y B = {a1, a2, . . . , am} la base asociada a esta solu-cin.44 TEMA 2. PROGRAMACIN LINEALSupongamos que X no es punto extremo, y razonaremos por reduccin al ab-surdo.Si X no es punto extremo, existen dos puntos y, z F que verican:X = y + (1 )z para algn (0, 1) con y = z.Adems y, z son de la forma:y = (y1, y2, . . . , ym; ym+1, . . . , yn) z = (z1, z2, . . . , zm; zm+1, . . . , zn).De esta forma tenemos:(x1, x2, . . . , xm; 0, . . . , 0) == (y1, y2, . . . , ym; ym+1, . . . , yn) + (1 )(z1, z2, . . . , zm; zm+1, . . . , zn).Si operamos tenemos:(x1, x2, . . . , xm; 0, . . . , 0) == (y1 + (1 )z1, y2 + (1 )z2, . . . , ym + (1 )zm, ym+1 ++(1 )zm+1, . . . , yn + (1 )zn).Luego___ym+1 + (1 )zm+1 = 0 yn + (1 )zn = 0==___ym+1 = 0 yn = 0y___zm+1 = 0 zn = 0puesto que no puede haber soluciones negativas.Adems tenemos, como y, z F se cumpley1a1 +y2a2 + +ymam= bz1a1 +z2a2 + +zmam= b_Si restamos ambas expresiones nos queda:(y1z1)a1 + (y2z2)a2 + + (ymzm)am =

0.Por denicin sabemos que los escalares tienen que ser cero, pues {a1, a2, . . . , am}forman una base, y por tanto son linealmente independientes, por lo que se deduce:2.4. ALGUNOS RESULTADOS SOBRE LAS SOLUCIONES 45y1z1= 0y2z2= 0 ymzm= 0___=y1= z1y2= z2 ym= zm___= y = z.Pero esto es absurdo pues habamos supuesto que y = z. Y por tanto hemos llegadoa una contradiccin, esto implica que X es punto extremo.=Supongamos que X es un punto extremo de F que tiene k componentes es-trictamente mayores que 0. Suponemos sin prdida de generalidad que son las kprimeras X = (x1, x2, . . . , xk; 0, . . . , 0).Como tiene que vericar el sistema tendremos:x1a1 +x2a2 + +xkak = b (2.1)Vamos a probar que {a1, a2, . . . , ak} son linealmente independientes. Vamos a ra-zonar por reduccin al absurdo.Supongamos que no son linealmente independientes, entonces existen 1, 2, . . . , kno todos nulos tal que:1a1 +2a2 + +kak =

0Si multiplicamos por > 0, entonces:1a1 +2a2 + +kak =

0 (2.2)Si sumamos (2.1) y (2.2) tenemos:(x1 +1)a1 + (x2 +2)a2 + + (xk +k)ak = bSi restamos (2.1) y (2.2) tenemos:(x11)a1 + (x22)a2 + + (xkk)ak = bSi llamamos y, z a los vectores:y = (x1 +1, x2 +2, . . . , xk +k, 0, . . . , 0)z = (x11, x22, . . . , xkk, 0, . . . , 0)Ambos son solucin de AX = b. Si tomamos sucientemente pequeo:xi +i 0 y 0xii 0 z 0Por tanto y, z verican el sistema y adems son mayores o iguales a cero, entoncesy, z F.46 TEMA 2. PROGRAMACIN LINEALPero si calculamos 12y + 12z tenemos:12y + 12z = _12x1 + 121, 12x2 + 122, . . . , 12xk + 12k, 0, . . . , 0_+ (2.3)+ _12x1 121, 12x2 122, . . . , 12xk 12k, 0, . . . , 0_== (x1, x2, . . . , xk, 0, . . . , 0) = XPero esto contradice que X sea punto extremo de F. Luego {a1, a2, . . . , ak} sonvectores linealmente independientes y k m.Pueden ocurrir dos cosas: Si k = m forman base, y entonces X es solucin bsica factible. Si k < m se completan las columnas que faltan formando una base, entoncesser solucin bsica factible degenerada.Teorema 5 Dado un programa lineal en forma estndar factible acotado, el valorptimo del programa lineal se obtiene en un punto extremo de la regin factible.DemostracinSea el programa linealMax z = ctXs.a. AX = bX 0___y sean {E1, E2, . . . , Ek} puntos extremos.Si llamamos M = max{ctE1, ctE2, . . . , ctEk}.Sea ahora X F un punto cualquiera de la regin factible, usando el teoremaanterior tendremos:X = 1E1 +2E2 + +kEk/ 1 +2 + +k = 1.Entonces:Z = ctX = ct(1E1 +2E2 + +kEk) == 1ctE1 +2ctE2 + +kctEk 1M +2M + +kM= (1 +2 + +k) M = 1 M = M.2.4. ALGUNOS RESULTADOS SOBRE LAS SOLUCIONES 47As tenemos que M es el valor de la funcin objetivo en algn punto extremo.x F el valor de la funcin objetivo Z M, entonces el punto de la regin factibleque me da el mayor valor es el valor extremo.La demostracin para el caso minimizante es idntica, slo que hay que buscarel mnimo y tendremos que Z m, siendo m = min{ctE1, ctE2, . . . , ctEk}.Ejemplo 23 Hallar la solucin ptima del programa lineal:Max Z = 2x13x2 + 10x3s.a.:x1 + 2x2 +x3= 42x1 +x2 + 5x3= 5x1, x2, x3 0___Variables bsicas Variables no bsicas Objetivox1 = 2; x2 = 1 x3 = 0 z=1x1 = 5; x3 = 1 x2 = 0 No factiblex2 = 5/3; x3 = 2/3 x1 = 0 z=5/3El valor mximo de Z es Z = 5/3, eso implica que la solucin ptima es:x1 = 0 x2 = 5/3 x3 = 2/3.Teorema 6 Sean x1, x2, . . . , xk soluciones ptimas de un programa lineal en formaestndar, entonces las combinaciones lineales convexas de x1, x2, . . . , xk tambin sonsoluciones ptimas.Si llamamos X = 1x1 +2x2 + +kxk, y evaluamos Z, obtenemos:Z = ctX = ct(1x1 +2x2 + +kxk) == 1ctx1 +2ctx2 + +kctxk == 1M +2M + +kM == (1 +2 + +k) M = 1 M = M.Luego X tambin es ptima.Ejemplo 24 Resolver el siguiente P.L.Max z = 3x1 + 3x2s.a.:x1 4x1 +x2 6x2 3x1, x2 0___48 TEMA 2. PROGRAMACIN LINEALLos puntos extremos son A(4, 0), B(4, 2), C(3, 3), D(0, 3), E(0, 0) que aparecenen la siguiente gura.Figura 2.1: Soluciones ptimas multiplesVariables bsicas Objetivox1 = 0; x2 = 0 z = 0 Solucin bsica factiblex1 = 0; x2 = 3 z = 9 Solucin bsica no factiblex1 = 3; x2 = 3 z = 18 Solucin ptimax1 = 4; x2 = 2 z = 18 Solucin ptimax1 = 4; x2 = 0 z = 12 Solucin bsica factibleLuego B y C son soluciones ptimas, y por tanto todos los puntos del segmentolineal BC tambin son soluciones ptimas.2.5 El algoritmo del SimplexEl algoritmo del Simplex es una tcnica general de resolucin de problemas de pro-gramacin lineal. Los pasos bsicos del algoritmo son los siguientes:1. Partir de una solucin bsica factible (un vrtice de la regin factible).2. Comprobar si esta solucin es ptima.Si es as, parar.En caso contrario, iral paso 3.2.5. EL ALGORITMO DEL SIMPLEX 493. Hallar una nueva solucin bsica adyacente a la anterior que mejore el valorde la funcin objetivo. Ir al paso 2.Explicaremos la forma en que se realizan estos pasos con el siguiente ejemplo,dejando para ms adelante una exposicin ms detallada del algoritmo.Ejemplo 25 Resolver el siguiente P.L.Max z = x1 +x2s.a.:x1 +x2 2x1 + 2x2 62x1 +x2 6x1, x2 0___Como el problema tiene slo dos variables podra resolverse por el procedimientogeomtrico. Se puede comprobar que la regin factible es el polgono de vrtices O,A, B, C, D. Las coordenadas de los vrtices y los valores de la funcin objetivo decada uno de ellos son:Vrtice Coordenadas Valor de la funcin objetivoO (0, 0) 0A (0,2) 2B (23, 83)103C (2, 2) 4D (3, 0) 3Por lo tanto el valor ptimo va a ser C con un valor ptimo de 4 para la funcinobjetivo.Ahora queremos resolver este problema por un procedimiento analtico.Lo primero que vamos a hacer es formular el problema en forma estndar, intro-duciendo variables de holgura:Max z = x1 +x2s.a.:___x1+x2+h1= 2x1+2x2+h2= 62x1+x2+h3= 6x1 0 x2 0 h1 0 h2 0 h3 0Paso 1 Partir de una solucin bsica factible.(Un vrtice de la regin factible).Eneste caso es muy fcil partir de una solucin bsica factible. Si tomamos comovariables bsicas las variables de holgura, y damos a las no bsicas x1 y x2 elvalor cero tenemos la solucin bsica factible de partida (x1, x2, h1, h2, h3) =(0, 0, 2, 6, 6) con un valor para z = x1+x2 = 0. Los valores anteriores cumplen50 TEMA 2. PROGRAMACIN LINEALel siguiente sistema que se ha conseguido aadiendo al anterior una ltimaecuacin conseguida trasponiendo trminos en la funcin objetivo.x1+x2+h1= 2x1+2x2+h2= 62x1+x2+h3= 6z x1x2= 0x1 0 x2 0 h1 0 h2 0 h3 0Puede observarse que todos los valores de las variables bsicas, y tambin elvalor de z, aparecen en los trminos independientes de este sistema.Paso 2 Comprobar si esta solucin es ptima. Puesto que z = x1 +x2 = 0. Podremosmejorarla si logramos introducir en la base la variable x1 x2. Supongamosque introducimos x1 en la base aumentando su valor dentro de las condicionesde factibilidad y manteniendo x2 como variable no bsica (x2 = 0). Se deberpues cumplir:x1+h1= 2x1+h2= 62x1+h3= 6x1 0 h1 0 h2 0 h3 0es decirh1= 2 + x1 0h2= 6 x1 0h3= 6 2x1 0Como x1 0 la primera restriccin se cumple siempre. Para que se cumplanlas otras dos ha de ser x1 6 y x1 62 = 3 Por lo tanto el mejor valorpara x1 cumpliendo todas las condiciones de factibilidad es 3. As que lasolucin actual no es ptima, puesto que puede mejorarse aumentando el valorde x1.Paso 3 Hallar una nueva solucin bsica adyacente a la actual que mejore el valor dela funcin objetivo.Si tomamos x1 = 3, h3= 6 2x1 = 0 . Por lo tanto la variable h3 sal-dr de la base entrando en su lugar x1. La nueva solucin es (x1, x2, h1, h2, h3) =(3, 0, 5, 3, 0) con un valor para z = x1+x2 = 3 +0 = 3, mejorndose por tantoel valor de z. Con el objeto de que la actual solucin aparezca de nuevo enel lugar de los trminos independientes del sistema realizamos las transforma-ciones adecuadas para que los coecientes de x1 del sistema sean 0, 0, 1, 0, queeran los coecientes que antes tena h3. Para ello dividimos la tercera ecuacinpor el coeciente de x1, que es 2 (pivote), y realizamos las transformacionesdel mtodo de Gauss a las restantes ecuaciones, de modo que los restantescoecientes de x1 sean nulos. De esta forma se obtiene el sistema siguiente:2.6. ALGORITMO DEL SIMPLEX EN FORMA DE TABLA (MAX) 5132x2+h1+12h3= 532x2+h212h3= 3x1+12x2+12h3= 3z 12x2+12h3= 3x1 0 x2 0 h1 0 h2 0 h3 0Ir paso 2 La solucin actual es (x1, x2, h1, h2, h3) = (3, 0, 5, 3, 0) Es ptima? Despe-jamos z de la ltima ecuacin obteniendose z = 3 + 12x2 12h3. El valor dez puede mejorar si podemos aumentar el valor de x2 que toma en la solucinbsica actual el valor 0. Conviene mantener para h3 el valor 0. Impondremoslas condiciones de factibilidad:h1 = 5 32x2 0, h2 = 3 32x2 0, x1 = 3 12x2 0Por lo tanto532 x2,332 x2,312 x2;103 x2, 2 x2, 6 x2Estas condiciones se cumplen para x2 2Paso 3 Dando a x2 el valor 2 se mejora lo ms posible el valor de z. Esta variable entraen la base. Sustituyendo este valor para x2 y h3 por 0, se obtiene h2 = 0 quees la variable que entra en la base. Si denominamos pivote al elemento alksiendo xl la variable que deja de ser bsica, y xk la variable que pasa a serbsica, el pivote es ahora el coeciente de x2 de la segunda ecuacin, que es32. Dividiendo esta segunda ecuacin por 32 y haciendo las transformaciones deGauss adecuadas para anular el resto de los coecientes de x2 el sistema tomael siguiente aspecto.h1h2+h3= 2x2+23h213h3= 2x113h2+23h3= 2z +13h2+13h3= 4x1 0 x2 0 h1 0 h2 0 h3 0La nueva solucin bsica es (x1, x2, h1, h2, h3) = (2, 2, 2, 0, 0) . Esta solucinya es ptima. En efecto, si despejamos z de la ltima ecuacin del sistemaobtenemos z = 413h213h3. Como h2 y h3 no pueden tomar valores negativosel mejor valor para estas variables es cero. Por lo tanto la solucin actual(2, 2, 2, 0, 0) no puede mejorarse.2.6 Algoritmo del Simplex en forma de tabla (max)Vamos a describir el Algoritmo del simplex en forma de tabla aplicable al caso deque el problema sea de maximizacin, todas las restriciones del tipo , y todos los52 TEMA 2. PROGRAMACIN LINEALrecursos no negativos. Para aplicar el algoritmo en otras situaciones se harn lastransformaciones necesarias para poner el problema en esta forma (ver epgrafe 2.8).Consideremos el problema (o programa) lineal que consiste en encontrar un vectorX = (x1, x2, . . . , xn) que optimice una funcin lineal.Opt. Z = c1x1 +c2x2 + +cnxns.a.: a11x1 +a12x2 + +a1nxn b1a21x1 +a22x2 + +a2nxn b2 : : . . . : . . .am1x1 +am2x2 + +amnxn bmxi 0, bi 0, i = 1, 2, . . . , n.___Pasamos en primer lugar el problema a forma estndar aadiendo m variables deholgura xn+1, xn+2, . . . , xn+m. De esta forma el problema tomar la forma:Opt. Z = c1x1 +c2x2 + +cnxns.a.: a11x1 +a12x2 + +a1nxn+xn+1= b1a21x1 +a22x2 + +a2nxn+xn+2= b2 : : . . . : . . .am1x1 +am2x2 + +amnxn +xn+m= bmxi 0 i = 1, 2, . . . , n.0. Construir la tabla inicial: Esta tabla se construye tomando en cada la loscoecientes de cada restriccin seguido del correspondiente trmino indepen-diente de la forma estndar. Aadimos una ltima la con los coecientes queresultan si se trasponen los trminos de la funcin objetivo hasta igualarlosa cero. En la parte superior de la tabla aparecen los costes y las variables.En la parte izquierda de la tabla aparecen estos mismos datos referentes a lasvariables bsicas. La tabla inicial presentara el siguiente aspecto:Opt. c1c2. . . cn0 0 0 coef. objetivox1x2. . . xnxn+1xn+2xn+mvariablesxn+10 a11a12. . . a1n1 0 0 b1xn+20 a21a22. . . a2n0 1 0 b2.................. . . ....xn+m0 am1am2. . . amn0 0 1 bmc1 c2. . . cn0 0 0 0Tomamos la solucin inicial que corresponde a una base cannica ( La cor-respondiente matriz bsica es la identidad). est solucin es.(x1, x2, . . . xn, xn+1, xn+2, . . . , xn+m) = (0, 0, . . . 0, b1, b2, . . . , bm)1. Partir de una solucin bsica factible: Considerar la solucin inicial.2.6. ALGORITMO DEL SIMPLEX EN FORMA DE TABLA (MAX) 532. Comprobar si esta solucin es ptima. La solucin actual es ptimasi todos los costes reducidos, coecientes de la ltima la, son no negativos(positivos o nulos). Si es as, parar. En otro caso ir al paso 3.3. Hallar una nueva solucin bsica adyacente a la actual que mejoreel valor de la funcin objetivo (leer nota a pie de pgina1):3a. Regla de la variable de entradaSeleccionar para entrar en la base la variable xj con rj ms negativo. Seasta la xk.Cuando hay varias variables que tienen este mismo valor, seselecciona arbitrariamente una cualquiera de stas.3 b. Regla de la variable de salidaSeleccionar para salir de la base la variable de la la i que haga mnimoel cocientexbiyik para los yik > 0. Sea la la l. (Si todos los yik 0, elproblema es no acotado) Fin . En caso contrario ir al paso 4.4. Realizar transformaciones en la tabla para conseguir una nueva matriz unitariatomando ylk como pivote. Se realizan transformaciones lineales similares alas que se usan en el mtodo de Gauss, hasta conseguir que la columna k tengael valor 1 en el lugar del elemento pivote y 0 en los restantes. De esta formaobtenemos una nueva solucin bsica factible adyacente a la anterior (para laltima la se puede optar por usar la relacin 2.4 de la pgina 53). Con estanueva solucin y esta nueva tabla ir al paso 2.Ejemplo 26 Resolver ahora el problema anterior:Max z = x1 +x2s.a.:x1 +x2 2x1 + 2x2 62x1 +x2 6x1, x2 0___1Como se ver la tabla va evolucionando durante el algoritmo. En general usaremos la siguientenotacin:Opt. c1c2. . . cn 0 0 0 coef. objetivox1x2. . . xn xn+1xn+2xn+mvariablesxb1cb1y11y12. . . y1ny1 n+1y1 n+2. . . y1 n+mxb1xb2cb2y21y22. . . y2ny2 n+1y2 n+2. . . y2 n+mxb2...........................xbmcbmym1ym2. . . ymnym n+1ym n+2. . . ym n+mxbmr1r2. . . rn rn+1rn+2rn+m Z0Los trminos de la matriz de los coecientes se designan en generalpor yijy los trminosindependientes por xbi.Los coecientes ri que aparecen en la ltima la se suelen llamar costes reducidos de la variablecorrespondiente. Estos costes reducidos cumplen la siguiente relacin:rj = cb1y1j + cb2y2j + . . . cbmymj cj = zjcj(2.4)54 TEMA 2. PROGRAMACIN LINEALempleando el algoritmo de Simplex en forma de tablaPaso 0 La tabla inicial es (introduciendo variables de holgura):1 1 0 0 0x1x2h1h2h30 h1-1 1 1 0 0 20 h21 2 0 1 0 60 h32 1 0 0 1 6-1 -1 0 0 0 0Paso 1 Partimos de una base cannica. La solucin bsica factible inicial es:(x1, x2, h1, h2, h3) = (0, 0, 2, 6, 6)con un valor para z = x1 +x2 = 0 + 0 = 0.Puede observarse que todos los valores de las variables bsicas, y tambin elvalor de z, aparecen en los trminos independientes de este sistema.Paso 2 Comprobar si esta solucin es ptima. No es ptima puesto que hay valoresno negativos de los costes reducidos (los que corresponden a las variables x1 yx2 ambos con valor 1.Paso 3 a Seleccionamos la primera como variable de entrada k = 1.Paso 3 b Seleccionamos como variable de salida la que aparezca en la la correspondien-te al mnimo cociente xBiyik para los yik > 0. En este caso el valor mnimo sealcanza cuando: min_61, 62_= min(6, 3) = 3. Corresponde a la tercera la. Asque l = 3. Por lo tanto el elemento pivote es y31 = 2. La variable de salida esh3.Paso 4 Hallar una nueva solucin bsica adyacente a la actual que mejore el valor dela funcin objetivo.Pivoteando se obtiene la siguiente tabla:1 1 0 0 0x1x2h1h2h30 h10321 01250 h20320 1 1231 x11120 01230 120 0123La nueva solucin es (x1, x2, h1, h2, h3) = (3, 0, 5, 3, 0) con un valor para z = 3.Ir paso 2 Es ptima? No porque algn coste reducido es negativo (el que correspondea la variable x2 que vale 12.Paso 3 a Seleccionamos x2 como variable de entrada, por lo tanto k = 2.2.7. ALGORITMO DEL SIMPLEX EN FORMA DE TABLA (MIN) 55Paso 3 b Seleccionamos como variable de salida la que aparezca en la la correspondi-ente al mnimo cocientex0iyik para los yik > 0. En este caso min_532 , 332 , 312_ =min_103 , 2, 6_ = 2. Corresponde a la segunda la. As que l = 2. Por lo tantoel elemento pivote es y22 = 32. La variable de salida es h2.Paso 4 Hallar una nueva solucin bsica adyacente a la actual que mejore el valor dela funcin objetivo.Pivoteando se obtiene la siguiente tabla:1 1 0 0 0x1x2h1h2h30 h10 0 1 -1 1 20 x20 1 0231321 x11 0 0 -132320 0 013134La nueva solucin es (x1, x2, h1, h2, h3) = (2, 2, 2, 0, 0) con un valor para z =4.Ir paso 2 Es ptima? S, porque ningn coste reducido es negativo. Por lo tanto lasolucin ptima de este problema es x1 = 2, x2 = 2.Los valores de las variables de holgura (h1 = 2, h2 = 0, h3 = 0) sirven para saberqu restricciones estn saturadas (se cumple la igualdad sustituyendo la solucinhallada en la restriccin primitiva). En este caso las dos ltimas restricciones estnsaturadas por lo que los recursos segundo y tercero se agotan y, en cambio, sobran2 unidades del primer recurso, pues h1 = 2.2.7 Algoritmo del Simplex en forma de tabla (min)Si el problema es de minimizacin un procedimiento que puede seguirse es transfor-mar la funcin objetivo de maximizacin en otra de minimizacin tal como se haindicado anteriormente:Min z =n

cjxj Max z =n

(cj)xj; z = zDe esta forma ya se podra aplicar el algoritmo en la forma maximizante.Tambin cabe la posibilidad de usar un algoritmo especco para este caso, que seconsigue con ligeras modicaciones del anterior. Estas variaciones se reducen a cam-bios de signo en los costes reducidos.A continuacin indicamos las modicacionesque habra que hacer en el algoritmo de la forma de maximizacin para obtener unalgoritmo minimizante de Simplex.56 TEMA 2. PROGRAMACIN LINEALEl paso 2 sera: Comprobar si esta solucin es ptima. La solucin actual es ptima sitodos los costes reducidos son no positivos (todos son negativos o nulos). Si esas, parar. En otro caso ir al paso 3.El paso 3a quedara: Regla de la variable de entrada. Seleccionar para entrar en la base lavariable con rj ms positivo. Sea sta la xk. Cuando hay varias variablesque tienen este mismo valor, se selecciona arbitrariamente una cualquierade stas.El resto del algoritmo permanecera inalterado.Ejemplo 27 Dado el programa lineal:Min Z = x23x3 + 2x5s.a.:x1 + 3x2x3 + 2x5= 72x2 + 4x3 +x4= 124x2 + 3x3 + 8x5 +x6= 10x1, x2, x3, x4, x5, x6 0___resolverlo usando el algoritmo del Simplex en forma minimizante.Tomamos como variables bsicas: (x1, x4, x6)Construimos la tabla del Simplex:Tabla I 0 1 3 0 2 0 sol. bsicax1x2x3x4x5x6factiblex10 1 3 1 0 2 0 7x40 0 2 4 1 0 0 12x60 0 4 3 0 8 1 100 1 3 0 2 0 Z0 = 0La variable que pasa a ser bsica es x3 por ser r3 el ms positivo de los rj.Ydeja de ser bsica x4 pues min_124 ; 103_= 124= 3.Si hacemos las transformaciones:Multiplico la la 2 por 1/4.Sumo a la la 1 la la 2.Resto a la la 3 la la 2 multiplicada por 3.Obtenemos la siguiente tabla:2.8. BSQUEDA DE SOLUCIONES INICIALES 57Tabla II 0 1 3 0 2 0 sol. bsicax1x2x3x4x5x6factiblex10 15/20 1/4 2 0 10x33 0 1/2 1 1/4 0 0 3x60 0 5/2 0 3/4 8 1 101/20 3/42 0Z = 9Entra en la base x2 por ser el ms positivo de los rj. Y sale x1 pues es el nicoyi2 que es positivo.Si hacemos las transformaciones:Multiplico la la 1 por 2/5.Sumo a la la 2 la la 1 multiplicada por 1/5.Sumo a la la 3 la la 1.Obtenemos la siguiente tabla:Tabla III 0 1 3 0 2 0 sol. bsicax1x2x3x4x5x6factiblex21 2/5 1 0 1/10 4/5 0 4x33 1/5 0 1 3/10 2/5 0 5x60 1 0 0 1/2 10 1 111/5 0 0 4/512/5 0Z = 11La solucin asociada a esta base es ptima pues todos los rj 0, la solucin es:x1 = 0 x2 = 4 x3 = 5 x4 = 0 x5 = 0 x6 = 11 ;Z = 11.2.8 Bsqueda de soluciones inicialesVamos a considerar varios casos. Los tres primeros corresponden a recursos nonegativos. En los tres ltimos los recursos pueden ser negativos.: Primer caso: Hay desigualdades () y bi 0. Segundo caso: Hay igualdades y bi 0. Tercer caso: Hay desigualdades () y bi 0 Cuarto caso: Hay desigualdades () y bi 0. Quinto caso: Hay igualdades y bi 0. Sexto caso: Hay desigualdades () y bi 058 TEMA 2. PROGRAMACIN LINEALPrimer caso (Desigualdades y bi 0.).En este caso, las desigualdades se convierten en igualdades introduciendo varia-bles de holgura positivas que tienen coeciente nulo en la funcin objetivo. Estecaso ya se ha tratado en la presentacin del algoritmo de simplex.Segundo caso (Igualdades y bi 0).En el caso de que aparezca un signo de igualdad en alguna restriccin, sumamosuna nueva variable positiva que llamamos variable articial:n

j=1aijxj = bi=n

j=1aijxj +ri = bidonde ri son las variables articialesA la funcin objetivo le aadimos un nuevo trmino formado por esta variablearticial que tendr coeciente negativo y valor absoluto "muy grande" si el prob-lema es de maximizacin y con coeciente coeciente positivo y valor absoluto "muygrande" si el problema es de minimizacin. Con ello se consigue que la variablearticial salga de la base y sea nula, lo que permite eliminarla.Tercer caso (Desigualdades () y bi 0)Si el signo de la restriccin es de () restamos en primer lugar una variablede holgura positiva para transformarla en una igualdad. Cuando ya tenemos unaigualdad sumamos una variable articial tal como hemos explicado en el prrafoanterior. Es decir ahora tenemos dos variables nuevas, una articial que se aadira ala funcin objetivo con un coeciente "muy grande" si el problema es de minimizacin(o "muy pequeo" si es de maximizacin), y una de holgura que se suma a la funcinobjetivo con coeciente nulo.n

j=1aijxj bi=n

j=1aijxjti +ri = bidonde ri son las variables articiales, y ti son las variables de holgura.Cuarto, quinto y sexto caso. (Se reducen a los tres primeros casos).Cambiando el signo de las restricciones el cuarto caso se transforma en el tercero,el quinto se transforma en el segundo y el sexto en el primero.A continuacin aplicamos algunas de estas reglas en varios ejemplos:2.8. BSQUEDA DE SOLUCIONES INICIALES 59Ejemplo 28 Dado el programa lineal:Max Z = 3x1 + 2x2 +x3s.a.:x1 + 2x2 +x3 10x1 +x2 + 2x3 92x1+ 3x3 12x1, x2, x3 0___Si introducimos las variables de holgura positivas tendremos el programa equi-valente:Max Z = 3x1 + 2x2 +x3s.a.:x1 + 2x2 +x3 +x4= 10x1 +x2 + 2x3+x5= 92x1+ 3x3+x6= 12x1, x2, x3, x4, x5, x6 0___Tomamos como variables bsicas las de holgura: x4, x5, x6. Por tanto una solucinbsica factible inicial es:x1 = 0 x2 = 0 x3 = 0 x4 = 10 x5 = 9 x6 = 12 ; Z0 = 0Construimos la tabla del Simplex:Tabla I 3 2 1 0 0 0 sol. bsicax1x2x3x4x5x6factiblex40 1 2 1 1 0 0 10x50 1 1 2 0 1 0 9x60 2 0 3 0 0 1 12-321 0 0 0 Z0 = 0Entra en la base x1 por ser el ms negativo de los rj.Y sale x6 pues: min_91; 101 ; 122_= 122= 6.Si hacemos las transformaciones:Multiplico la la 3 por 1/2.Sumo a la la 1 la la 3 multiplicada por (-1/2).sumo a la la 2 la la 3 multiplicada por (-1/2).Obtenemos la siguiente tabla:60 TEMA 2. PROGRAMACIN LINEALTabla II 3 2 1 0 0 0 sol. bsicax1x2x3x4x5x6factiblex40 0 2 1/2 1 0 1/2 4x50 0 1 1/2 0 1 1/2 3x13 1 0 3/2 0 0 1/2 60 -2 7/2 0 0 3/2 Z = 18Entra en la base x2 porque le corresponde el ms negativo de los rj. Y sale x4pues: min_31; 42_= 42 = 2.Si hacemos las transformaciones:Multiplico la la 1 por 1/2.Sumo a la la 2 la la 1 multiplicada por (-1/2).Obtenemos la siguiente tabla:Tabla III 3 2 1 0 0 0 sol. b sicax1x2x3x4x5x6factiblex22 0 1 1/4 1/2 0 1/4 2x50 0 0 3/4 1/2 1 1/4 1x13 1 0 3/2 0 0 1/2 60 0 3 1 0 1Z = 22La solucin asociada a esta base es ptima pues todos los rj 0, la solucin es:x1 = 6 x2 = 2 x3 = 0 ;Z = 22.Las variables de holgura no se han incluido en la solucin ptima.El valor para la variable de holgura x5 = 1 signica que una unidad del segundorecurso no se ha gastado.Ejemplo 29 Dado el programa lineal:Max Z = x1 + 2x2s.a.:x12x2 4x15x2 8x1, x2 0___Si introducimos las variables de holgura positivas tendremos el programa equi-valente:Max Z = x1 + 2x2s.a.:x12x2 +x3= 4x15x2 +x4= 8x1, x2, x3, x4 0___2.8. BSQUEDA DE SOLUCIONES INICIALES 61Y por tanto una solucin bsica factible inicial es:x1 = 0 x2 = 0 x3 = 4 x4 = 8; Z0 = 0Construimos la tabla del Simplex:Tabla I 1 2 0 0 sol. bsicax1x2x3x4factiblex30 1 2 1 0 4x40 1 5 0 1 81 -2 0 0La solucin es no acotada o ilimitada pues todos los yi2 < 0 ya que y11 = 2 < 0,y12 = 5 < 0. Podemos hallar una direccin (Rayo ptimo) cuyos puntos sontodos soluciones factibles y la funcin objetivo mejora cuando aumenta el valor delas variables. Sustituyendo en el sistema el valor x1 = 0 obtenemos una de estasdirecciones:___x1= 0x2= x2x3= 4 + 2x2x4= 8 + 5x2Nota: Este programa lineal puede resolverse usando el mtodo geomtrico estudiadoen el Tema 1.Puede observarse entonces que la regin factible es no acotada y elvalor de la z puede mejorar tanto como queramos.Ejemplo 30 Dado el programa lineal:Min Z = 3x1 + 5x2s.a.:x1 4x2 63x1 + 2x2 18x1, x2 0___Si introducimos las variables de holgura positivas, y una variable articial x6tendremos el programa no equivalente:Min Z = 3x1 + 5x2 +mx6s.a.:x1 +x3= 4x2 +x4= 63x1 + 2x2x5 +x6= 18x1, x2, x3, x4, x5, x6 0___De esta forma hemos construido un programa no equivalente, con una variablearticial. En el caso en que todas las variables articiales que se tengan que intro-ducir sean nulas el programa equivalente al inicial. El problema se resuelve usando62 TEMA 2. PROGRAMACIN LINEALel mtodo de las penalizaciones (o de la m grande), que estudiamos en el siguienteepgrafe.2.8.1 Mtodo de las PenalizacionesCaso Maximizante. A las variables articiales se les pone costo muy bajo (m) en la funcin objetivo (Z), para que salgan rpidamente de la base.Caso Minimizante. A las variables articiales se les pone costo muy alto (m) + en la funcin objetivo (Z), para que salgan rpidamente de la base.Teorema 7 Dado un programa lineal con variables articiales y dada la solucinbsica factible ptima XB = B1 b, si alguna de las variables articiales es bsica,y con valor positivo, entonces el problema original es no factible.Para ilustrar este mtodo y este teorema realizamos dos ejemplos. En el primero,continuamos con el ejemplo 30.Ejemplo 31 Resolver el problema dado en el ejemplo 30 .Construimo la tabla inicial del Simplex, usando el mtodo de las penalizaciones:La solucin bsica factible inicial era:x1 = 0 x2 = 0 x3 = 4 x4 = 6 x5 = 0 x6 = 18; Z0 = 18mLa tabla inicial del Simplex es:Tabla I 3 5 0 0 0 m sol. bsicaMin x1x2x3x4x5x6factiblex30 1 0 1 0 0 0 4x40 0 1 0 1 0 0 6x6m 3 2 0 0 1 1 18rj35 0 0 0 m 0Para que x6 pueda actuar como variable bsica tendra que tener un cero en sucoste reducido. Para conseguirlo podemos sumar a la ltima la la tercera multipli-cada por m, obtenindose:Tabla I 3 5 0 0 0 m sol. bsicaMin x1x2x3x4x5x6factiblex30 1 0 1 0 0 0 4x40 0 1 0 1 0 0 6x6m 3 2 0 0 1 1 18rj3m3 2m5 0 0 m 0 Z0 = 18m2.8. BSQUEDA DE SOLUCIONES INICIALES 63Esta tabla puede escribirse tambin directamente si calculamos la ltima lausando la expresin de los costes reducidos dada en 2.4 de la pgina 53.As, entra en la base x1 por ser r1 el mayor coste reducido y sale de la base x3,pues hace mnimo el cociente 4/1 y 18/3. Si construimos la nueva tabla del Simplexobtenemos:Tabla II 3 5 0 0 0 m sol. bsicaMin x1x2x3x4x5x6factiblex13 1 0 1 0 0 0 4x40 0 1 0 1 0 0 6x6m 0 2 3 0 1 1 6rj0 2m53m+ 3 0 m 0 Z = 6m+ 12Entra en la base x2 por ser r2 el mayor, y sale de la base x6 pues es el que hacemnimo el cociente 6/1 y 6/2. Si construimos la nueva tabla del Simplex:Tabla III 3 5 0 0 0 m sol. bsicaMin x1x2x3x4x5x6factiblex13 1 0 1 0 0 0 4x40 0 0 3/2 1 1/2 1/2 3x25 0 1 3/2 0 1/2 1/2 3rj0 0 9/2 0 5/2 5/2 mZ = 27La solucin ptima es x1 = 4, x2 = 3 , con z = 27.La variable de holgura x4 = 3 se interpreta como que el segundo recurso no segasta, y quedan 3 unidades.Ejemplo 32 Dado el programa lineal:Min Z = x12x2 + 3x3s.a.:2x1 +x2 + 3x3= 22x1 + 3x2 + 4x3= 1x1, x2, x3 0___Si introducimos las variables articiales x4, x5 tendremos el programa no equi-valente:Min Z = x12x2 + 3x3 +mx4 +mx5s.a.:2x1 +x2 + 3x3 +x4= 22x1 + 3x2 + 4x3 +x5= 1x1, x2, x3, x4, x5 0___As hemos construido un programa no equivalente con variables articiales, queen el caso en que todas las variables articiales sean nulas, ser un programa equi-valente al inicial.64 TEMA 2. PROGRAMACIN LINEALEl sistema es equivalente al inicial si las variables articiales son nulas: x4 =x5 = 0.La solucin bsica factible inicial es:x1 = 0 x2 = 0 x3 = 0 x4 = 2 x5 = 1; Z0 = 3mConstruimos la tabla del Simplex:Tabla I 1 2 3 m m sol. bsicaMin x1x2x3x4x5factiblex4m 2 1 3 1 0 2x5m 2 3 4 0 1 1rj1 4m+ 2 7m3 0 0 Z0 = 3mAs, entra en la base x3 por ser r3 el mayor y sale de la base a5, pues hace mnimoel cociente 2/3 y 1/4. Si construimos la nueva tabla del Simplex obtenemos:Tabla II 1 2 3 m m sol. bsicaMin x1x2x3x4x5factiblex4m 7/2 5/4 0 1 3/4 5/4x33 1/2 3/4 1 0 1/4 1/4rj72m+ 1254m+ 1740 0 74m+ 34Z = 5m+ 34As, el problema original es no factible, porque he llegado a la tabla ptima, y lavariable articial x4 no ha salido de la base, y tiene un valor positivo x4 = 5/4.2.9 Algoritmo del Simplex en forma matricialSi partimos de la forma matricialOpt. Z = cXs.a.: AX = bX 0___siendoc =_____c1c2...cn_____, X =_____x1x2...xn_____, b =_____b1b2...bm_____y A =___a11. . . a1n.........am1. . . amn___.y considerando, sin prdida de generalidad, que las n primeras columnas de A co-rresponden a la matriz bsica B asociada a una solucin bsica factible, que N es2.9. ALGORITMO DEL SIMPLEX EN FORMA MATRICIAL 65la matriz formada por las restantes columnas y que XB, XN, cB, cN son, respecti-vamente, las matrices formadas por las variables bsicas, las no bsicas, los costesde las variables bsicas y los costes de la variables no bsicas, entonces el problemapuede expresarse en la forma:Max Z = (cB, cN)_XBXN_= cBXB +cNXNs.a.: _ B N _ _XBXN_= BXB +NXN = bX 0___Multiplicando por B1el sistema formado por las restricciones, se obtiene:B1BXB +B1NXN = B1by por tantoXB = B1b B1NXNSustituyendo en la funcin objetivo este valor de XB tenemos:Z = (cB, cN)_XBXN_= cBXB +cNXN = cB_B1b B1NXN_+cNXN == cBB1b +_cN cBB1N_XN.En el caso particular de la solucin bsica asociada a esta matriz B, XN = 0,por lo que las dos ltimas expresiones tomarn la forma:XB = B1b =X0By Z = cBB1b = Z0que son los valores de las variables bsicas y