Este libro es un texto de nivel intermedio en la investigación de operaciones y de los métodos cuantitativos en los negocios, dirigido a estudiantes de ingeniería industrial e informática, matemáticas, economía y ciencias de la administración. Investigación de operaciones desarrolla los conceptos y aplicaciones de los denominados modelos determinísticos —que no dependen de condiciones aleatorias o estimaciones probabilísticas— de la investigación de operaciones y comprende los temas de programación lineal, problemas de transporte y análisis de redes. Asimismo, el libro expone numerosos ejemplos de manera detallada y completa e incluye un buen número de problemas con sus respectivas respuestas e indicaciones para su resolución. Otras publicaciones del Fondo Editorial Reglas y sostenibilidad de la política fi scal Lecciones de la experiencia peruana Félix Jiménez Un modelo para armar Teorías y conceptos de desarrollo Consuelo Uribe Mallarino Regulación y supervisión del sector eléctrico Alfredo Dammert / Raúl García Carpio / Fiorella Molinelli Guía práctica de los instrumentos fi nancieros derivados Jean Rona Szekely Física 1 Hugo Medina Guzmán Maynard Kong estudió en la Facultad de Ciencias Físicas y Matemáticas de la Universidad Nacional de Ingeniería. Obtuvo el grado PhD en la Universidad de Chicago. Es profesor principal del Departamento Académico de Ciencias de la Pontifi cia Universidad Católica del Perú en cursos de Matemáticas e Informática. Fue profesor visitante en la Universidad de Stuttgart y becario de la Fundación von Humboldt. Entre sus principales obras se encuentran Teoría de conjuntos (coautor), Cálculo Diferencial, Cálculo Integral, Basic, Lenguaje de Programación Pascal, Lenguaje de Programación C, Lenguaje Ensamblador Macro Assembler e Inteligencia Artifi cial. INVESTIGACIÓN DE OPERACIONES MAYNARD KONG Programación lineal | Problemas de transporte | Análisis de redes M AY NA RD K ON G IN VE ST IG AC IÓ N DE O PE RA CI ON ES Pr og ra m ac ión lin ea l | P ro ble m as de tr an sp or te | An áli sis de re de s Investigación de operaciones Programación lineal Problemas de transporte Análisis de redes Maynard Kong Investigación de operaciones Programación lineal Problemas de transporte Análisis de redes Investigación de operaciones Programación lineal - Problemas de transporte - Análisis de redes Maynard Kong © Maynard Kong, 2010 De esta edición: © Fondo Editorial de la Pontificia Universidad Católica del Perú, 2010 Av. Universitaria 1801, Lima 32, Perú Teléfono: (51 1) 626-2650 Fax: (51 1) 626-2913 feditor@pucp.edu.pe www.pucp.edu.pe/publicaciones Diseño, diagramación, corrección de estilo y cuidado de la edición: Fondo Editorial PUCP Primera edición: abril de 2010 Tiraje: 500 ejemplares Prohibida la reproducción de este libro por cualquier medio, total o parcialmente, sin permiso expreso de los editores. Hecho el Depósito Legal en la Biblioteca Nacional del Perú N° 2010-03265 ISBN: 978-9972-42-921-7 Registro del Proyecto Editorial: 31501361000223 Impreso en Tarea Asociación Gráfica Educativa Pasaje María Auxiliadora 156, Lima 5, Perú Índice Capítulo 1. Introducción 11 1.1. Aplicaciones 11 1.2. Problema de optimización 12 1.3. Propiedades y ejemplos 12 1.4. Programación matemática 17 1.5. Modelo de programación matemática 19 1.6. Problemas resueltos 22 Capítulo 2. Introducción a la Programación Lineal 31 2.1. Formulación del problema de Programación Lineal 31 2.2. Solución geométrica de problemas con dos variables de decisión 34 2.3. Problemas propuestos 37 2.4. Forma estándar del problema de Programación Lineal 41 2.5. Restricciones equivalentes de la forma estándar 46 2.6. Variables básicas y soluciones básicas factibles 48 2.7. Problemas propuestos 53 Capítulo 3. El método del símplex 57 3.1. Conceptos básicos del método del símplex 57 3.2. Forma tabular del problema estándar 64 3.3. Criterios del símplex. Caso máximo 66 3.4. Problema de minimización 67 3.5. Problemas propuestos 70 Capítulo 4. Método del símplex: variables artificiales. Convergencia del algoritmo 73 4.1. Variables artificiales 73 4.2. Problemas propuestos 80 4.3. Convergencia del algoritmo del símplex 83 4.4. Métodos para evitar ciclos: regla de Blands y perturbación 86 4.5. Problemas propuestos 93 Capítulo 5. Problema dual 95 5.1. Definición del problema dual 95 5.2. Formas típicas de problemas duales 100 5.3. Reglas para hallar el problema dual 102 5.4. Problemas propuestos 104 5.5. Propiedades del problema dual 106 5.6. Problemas propuestos 112 5.7. Vector dual de una solución básica factible 114 Capítulo 6. Análisis de sensibilidad post óptimo 123 6.1. Introducción 123 6.2. Pasos del análisis 123 6.3. Programa ejemplo 124 6.4. Variación de un costo fijando la solución óptima 125 6.5. Variación del lado derecho de una restricción fijando las variables básicas 127 6.6. Inclusión de variable 129 6.7. Inclusión de restricción 131 6.8. Dualidad y análisis de sensibilidad 133 6.9. Costos reducidos y asignación de valores a variables no básicas 136 6.10. Matriz de operaciones en la tabla final 137 6.11. Problemas resueltos 140 Capítulo 7. Problemas de transporte y asignación 153 7.1. Introducción 153 7.2. Problema de transporte balanceado 155 7.3. Método del símplex simplificado 156 7.4. Problemas propuestos 174 7.5. Problema de transbordo 177 7.6. Problema de asignación 181 7.7. Problemas propuestos 192 Capítulo 8. Análisis de redes 197 8.1. Introducción 197 8.2. Rutas en una red 199 8.3. Problema de ruta óptima 200 8.4. Problemas propuestos 203 8.5. Problema de flujo máximo 206 8.6. Problemas propuestos 213 8.7. Programación de proyectos 216 8.8. Problemas propuestos 235 Índice alfabético 241 Capítulo 1 Introducción En este capítulo se introducen los conceptos básicos de la investigación de operaciones. Se define el problema de optimización y se presenta el modelo matemático de la programación matemática. La investigación de operaciones trata el estudio y despliegue de métodos científicos para usar eficazmente los recursos. Tales métodos comprenden modelos matemáticos —y estadísticos— y diversos algoritmos que sirven para tomar decisiones en problemas relacionados con la planificación, coordinación y ejecución de operaciones en las organizaciones. 1.1 Aplicaciones Mencionamos algunas aplicaciones de la investigación de operaciones: • Problemas de asignación de recursos materiales y servicios: pro- ductos, mano de obra, tareas • Procesos de planificación de personal, etapas de producción • Administración de flujos de materias primas a través de cadenas de suministros • Planificación de rutas, redes de telecomunicación • Refinamiento y mezcla de sustancias o componentes, por ejem- plo, petróleo • Selección de portafolios de acciones y bonos 12 Maynard Kong 1.2 Problema de optimización El problema general de optimización consiste en determinar el valor óptimo (valor máximo o valor mínimo) que una función asume sobre los elementos de un conjunto dado. De modo preciso, dados un conjunto X y una función que asigna a cada x de X un valor numérico f (x), se desea, para el caso de máximo, encontrar x 0 de X que cumpla la condición: f (x) ≤ f (x0) para todo x de X y para el caso de mínimo: un x1 de X que cumpla f (x1) ≤ f (x) para todo x de X En forma abreviada se escribe f (x0) = Max f (x), f (x1) = Min f (x) Los elementos del conjunto X representan los recursos del problema y f (x) puede ser considerado como el valor del recurso x, por ejemplo, es un costo, un tiempo, una cantidad de producción, etc. A la función f (x) se le denomina función objetivo. Frecuentemente, el conjunto X se especifica mediante: • condiciones —a las que se llama restricciones— que determinan sus elementos • algoritmos o reglas que describen cómo obtener elementos de X. Véanse los ejemplos 1, 3 y 4. Es posible que el problema no tenga soluciones, porque el conjunto X no tiene elementos o porque la función f (x) no puede tomar un valor máximo o mínimo. 1.3 Propiedades y ejemplos Se cumplen las siguientes propiedades 1) Max (f (x) + c) = Max f (x) + c, c es una constante 2) Max (a f (x)) = a Max f (x), a es una constante positiva 13 Capítulo 1. Introducción 3) Min (b f (x)) = b Max f (x), b es una constante negativa 4) Min f (x) = - Max (- f (x)) 5) Max f (x) = - Min (- f (x)) si existen los valores óptimos de los segundos miembros. Las propiedades 4) y 5) se suelen aplicar a menudo para convertir un problema de minimización en uno de maximización y viceversa. Por ejem- plo, de manera explícita, según 4) para encontrar el valor mínimo de f (x): • se halla el valor máximo de la función - f (x), por ejemplo - f (x2) • luego se le cambia de signo, y resulta así que f (x2) es el valor mínimo buscado. A continuación se desarrollan algunos ejemplos sencillos relativos a problemas de optimización Ejemplo 1. Un problema de mezcla Se desea producir una bebida mezclando jugos o zumos de naranja, toronja y mandarina. Los costos de los jugos son 3, 6 y 5 por litro, respectivamente. Se requiere que la bebida tenga al menos el 30% de toronja y no más del 25% de naranja. Formule el problema de optimización para obtener una mezcla de bebida cuyo costo sea mínimo. Solución Sean n, t y m, las cantidades de naranja, toronja y mandarina, en litros, para obtener un litro de mezcla de bebida. Luego, los costos de cada componente son 3n, 6t y 5m, respectivamente, y el costo de la bebida es C = 3n + 6t + 5m. El problema consiste en obtener el valor mínimo de C. Falta precisar las condiciones sobre las cantidades de jugos. Estas son: 1) las tres cantidades suman un litro: n + t + m = 1 14 Maynard Kong 2) la cantidad de toronja al menos es 30% de un litro: t ≥ 0.30 3) la cantidad de naranja no excede el 25% de un litro: n ≤ 0.25 y 4) las tres cantidades son evidentemente no negativas: n, t y m ≥ 0 Así, el conjunto X sobre el cual C queda definida es X = todos los (n, t, m) tales que n + t + m = 1 t ≥ 0.30 n ≤ 0.25 n, t, m ≥ 0 Finalmente, el problema de optimización es Minimizar C = 3n + 6t + 5m sobre el conjunto X. Ejemplo 2. Solución óptima del ejemplo 1 por simple inspección Resuelva el problema de optimización del ejemplo 1, esto es, halle el costo mínimo de un litro de mezcla de bebida. Solución El problema es encontrar el valor mínimo de C = 3n + 6t + 5m en donde n, t y m cumplen las condiciones n + t + m = 1 n ≤ 0.25 t ≥ 0.30 n, t, m ≥ 0 Observamos que n, t y m son menores o iguales a 1.0. El costo C será menor si se toma la menor cantidad del jugo más caro, que corresponde al de toronja; así t, que varía entre 0.30 y 1.0, debe tomar su menor valor t = 0.30. Y también C será menor si se toma la mayor cantidad posible n del jugo de naranja, pues es el más barato, y como n se encuentra entre 0.0 y 0.25, ha de tomarse n = 0.25. 15 Capítulo 1. Introducción El valor de m, que se halla entre 0.0 y 1.0, es lo que falta para com- pletar el litro de mezcla, así m = 1.0 -0.30 - 0.25 = 0.45. Así, la bebida que da un litro de costo mínimo se obtiene mezclando 0.25 litros de naranja, 0.30 litros de toronja y 0.45 litros de mandarina, que tiene un costo de 3×0.25 + 6×0.30 + 5×0.45 = 3.90. Ejemplo 3 Sea la función f (x, y) = 2x + y definida en el conjunto de los puntos (x, y), x, y números reales, que cumplen las condiciones x + y = 4 x ≥ 0,  y ≥ 0 Determine los valores máximo y mínimo de f (x, y). Solución Reemplazando x + y = 4 en la función f (x, y) = 2x + y = x + (x + y) = 4 + x y de las relaciones dadas se observa que los valores de x varían desde 0 hasta 4 (y varía a la vez desde 4 hasta 0) de manera que el menor valor de x es 0, cuando y es 4, y por eso Max f (x, y) = 4 + 4 = 8 cuando x = 4, y = 0. Por el mismo razonamiento se obtiene Min f (x, y) = 4 + 0 = 4 cuando x = 0, y = 4. Ejemplo 4 Tres máquinas M1, M2 y M3 pueden realizar las tareas A, B y C. Los costos de ejecución son dados en la tabla siguiente: A B C M1 8 14 15 M2 7 15 10 M3 6 17 9 16 Maynard Kong ¿Cómo se deben hacer las asignaciones de las tareas de manera que cada máquina realice exactamente una de las tareas y el costo total sea el menor posible? Solución En este caso, el conjunto de recursos consiste de todas las posibles asig- naciones. Los recursos del problema con sus respectivos costos son dados por Asignaciones (una columna) M1 A A B B C C M2 B C A C A B M3 C B C A B A Costo 32 35 30 30 39 36 en donde cada columna indica la forma de asignar las tareas a las máquinas, por ejemplo, la tercera columna asigna las tareas B, A, C a las máquinas M1, M2 y M3, respectivamente, y el costo respectivo es 14 + 7 + 9 = 30, que, como puede observarse, es en verdad el mínimo. Ejemplo 5 Pruebe que Min f (x) = - Max (- f (x)) Solución Sea f (x1) = Min f (x). Entonces por definición de valor mínimo se tiene f (x1) ≤ f (x) para todo x de X o - f (x) ≤ - f (x1) para todo x de X de modo que f (x1) es el valor máximo de - f (x), esto es - f (x1) = Max (- f (x)) o Min f (x) = - Max (- f (x)) 17 Capítulo 1. Introducción 1.4 Programación matemática Los problemas de programación matemática constituyen una parte importante de los problemas de optimización. Un programa matemático tiene la forma Maximizar (o minimizar) y = f (x1, x2, ..., xn), sujeto a las condiciones o restricciones ( ) { } ( ) { } ( ) { } 1 1 1 2 1 2 1 , , , , o , , , , o , , , , o n n m n m g x x b g x x b g x x b ≤ = ≥ ≤ = ≥ ≤ = ≥     en donde f (x1, ..., xn), g1 (x1, ..., xn), ..., gn (x1, ..., xn), son funciones con valores numéricos que dependen de n variables numéricas, x1, x2, ..., xn, b1, ..., bm son constantes y en cada restricción se emplea uno de los signos ≤, =, o ≥, lo que se indica mediante la notación {≤, =, o ≥}. El conjunto X de definición del problema está formado por todos los x = (x1, ..., xn) que satisfacen todas las restricciones. A tales x se les llama soluciones factibles del programa o del problema, y a X, se le denomina el conjunto de soluciones factibles o región de factibi- lidad. Generalmente se asume que las variables x1, ..., xn son números reales. No obstante, también se consideran programas matemáticos —llamados de programación entera— en los que las variables toman solo valores enteros. Ejemplo 1 Maximizar  z = x + y sujeto a x2+y2 ≤ 4. 18 Maynard Kong En este caso: z = f (x, y) = x + y,  g1 (x, y) = x2 + y2, el signo es ≤ y la constante es b1 = 4. Ejemplo 2 Aplicando métodos geométricos, hallar la solución óptima del ejemplo anterior. Solución La restricción x2 + y2 ≤ 4 determina el disco D de radio 2 y centro en el origen. L0 L4 | | X Lv Y (a,b)● ● Sea v un valor dado y consideremos la recta Lv : v = x + y En la figura se grafican las rectas correspondientes a los valores de v = 0 y 4. Observemos que la función objetivo f (x, y) = x + y toma el valor v sobre el disco D, si y solo si la recta Lv interseca al disco. Esto implica que se debe considerar únicamente rectas Lv que intersequen al disco. Y por otro lado, cuando se aumenta los valores de v, como de v = 0 a v = 1, la recta Lv se desplaza en el primer cuadrante alejándose del ori- gen. En resumen, para hallar el valor de v, el valor máximo u óptimo, 19 Capítulo 1. Introducción hay que mover la recta hasta que sea tangente al círculo. El punto de tangencia P (a, b) tiene pendiente 1, pues el radio del origen al punto P es perpendicular a la recta, cuya pendiente es -1. Así, b = a y por estar en el círculo a2 + b2 = 4, de donde a = √ 2  Por tanto, la solución óptima es (√ 2 , √ 2 ) y el valor óptimo es f (√ 2 , √ 2 ) = 2√ 2. Ejemplo 3 Minimizar z = 5x1 +3x2 +8x3 - 5x4 +100 sujeto a x1 + x2 + x3 + x4 ≥ 25 5x1 + x2 ≤ 20 5x1 - x2 ≤ 8 x3 + x4 = 20 y todas las xi ≥ 0. Ejemplo 4 Maximizar w = 2x + xy + y2 + 5z2 sujeto a las condiciones 2x + y - z = 10 3y + 7x ≤ 25 x, y, z ≥ 0 1.5 Modelo de programación matemática Para resolver un problema de optimización: 1. Se formula un modelo del problema mediante un programa matemático. 2. Se resuelve el programa matemático. 20 Maynard Kong A partir de la definición o enunciado del problema, los pasos que usualmente se aplican para la formulación o propuesta del modelo son los siguientes: • Se identifican la cantidad o variable de salida que se desea opti- mizar y las variables de decisión o de entrada x1, x2, ..., xn, de las que depende y se expresa la primera como una función matemá- tica de las últimas. • Se determinan las condiciones, requisitos y limitaciones y se expresan mediante restricciones matemáticas que se imponen a las variables de decisión. • Se incluyen condiciones adicionales que no aparecen de manera explícita pero que deben cumplirse en el problema real, por ejemplo, si algunas variables de decisión han de tomar valores mayores que o iguales a cero, o si deben tener valores enteros. Una vez obtenido el modelo del programa matemático se procede a resolverlo aplicando los métodos y técnicas de optimización; esto es, hallar el valor óptimo, si existe, y una solución óptima, o algunos valores en los cuales las variables de decisión proporcionan el valor óptimo. Ejemplo Un establecimiento de ventas de combustible atiende las 24 horas y tiene los siguientes requerimientos mínimos de empleados para atender a los clientes: Horas 0-4 4-8 8-12 12-16 16-20 20-24 Número de empleados 2 4 8 6 9 4 Un empleado trabaja 8 horas consecutivas y puede ingresar al ini- ciarse cualquiera de los 6 períodos indicados. Formule el modelo matemático para minimizar el menor número de empleados que se necesitan en el establecimiento. 21 Capítulo 1. Introducción Solución Sea x1 = número de empleados que empiezan a las 0 horas (primer período) ... x6 = número de empleados que empiezan a las 20 horas (último período) Entonces n = total de empleados requeridos = x1 + x2 + ... + x6 y las restricciones para los respectivos períodos son: x6 + x1 ≥ 2; x1 + x2 ≥ 4; x2 + x3 ≥ 8; x3 + x4 ≥ 6; x4 + x5 ≥ 6; x5 + x6 ≥ 4; que toman en cuenta la suma de los empleados de dos períodos con- secutivos, por ejemplo, en el primer período 0-4 se tiene x6 empleados que empezaron a las 20 horas y x1 empleados que empiezan a las 0 horas. Además, hay que observar que las variables son enteras y mayores que o iguales a 0. Por tanto, el modelo de programación pedido es Minimizar n = x1 + x2 + ... + x6 sujeto a x6 + x1 ≥ 2, x1 + x2 ≥ 4; x2 + x3 ≥ 8; x3 + x4 ≥ 6; x4 + x5 ≥ 6; x5 + x6 ≥ 4; con todas las variables enteras y no negativas. 22 Maynard Kong 1.6 Problemas resueltos Problema 1 Si Max f (x) = 20 calcule a) Max (3 f (x) - 10) b) Min ( - 5 f (x)) Solución Se tiene a) Max (3 f (x) - 10) = 3 Max f (x) - 10 = 3×20 - 10 = 50 b) Min ( - 5 f (x)) = 5 Min ( -  f (x)) = 5 ( - Max f (x)) = 5 (- 20) = - 100 Problema 2 Resuelva el problema Maximizar z = 4y - 3x sujeto a x + y = 4 x ≥ 1,  y ≥ 2 Solución Despejando la variable y de la restricción x + y = 4 y reemplazándola en la función objetivo z = 4y - 3x = 4 (4 - x) - 3x = 16 - 7x Falta determinar el conjunto de valores de x: de x = 4 - y y usando la condición y ≥ 2 se obtiene x ≤ 4 - 2 = 2, por lo tanto, x varía desde 1 hasta 2, de donde resulta que z varía de 16 - 7 (1) a 16 - 7 (2). Luego, el mayor valor de z es 9 y se obtiene en x = 1, y = 3. 23 Capítulo 1. Introducción Problema 3. Problema de la dieta Se desea mezclar cuatro alimentos de modo que el producto resultante contenga al menos 80 unidades de proteínas, 100 unidades de carbohi- dratos y 25 unidades de grasa. La tabla siguiente contiene las cantidades nutricionales de los alimentos y el respectivo costo Alimento Proteínas Carbohidratos Grasas Costo 1 20 60 12 3 2 40 30 16 2 3 50 45 8 6 4 30 30 14 4 Formule el modelo de programación matemática para obtener una mezcla de costo mínimo. Solución Sean x1, x2, x3, y x4, las unidades que se toman de los alimentos, respec- tivamente, para formar una mezcla. Luego, el costo de la mezcla es C = 3x1 + 2x2 + 6x3 + 4x4. La cantidad de proteínas que contiene la mezcla es 20x1 + 40x2 + 50x3 + 30x4, que debe ser al menos 80, y por lo tanto se tiene la primera restricción: 20x1 + 40x2 + 50x3 + 30x4 ≥ 80. Similarmente, se establecen las restricciones para los carbohidratos y grasas: 60x1 + 30x2 + 45x3 + 30x4 ≥ 100 12x1 + 16x2 + 8x3 + 14x4 ≥ 25 y es obvio que todas las variables han de ser no negativas. Así, el modelo pedido es Minimizar C = 3x1 + 2x2 + 6x3 + 4x4 24 Maynard Kong sujeto a 20x1 + 40x2 + 50x3 + 30x4 ≥ 80 60x1 + 30x2 + 45x3 + 30x4 ≥ 100 12x1 + 16x2 +   8x3 + 14x4 ≥ 25 todos los xi ≥ 0. Problema 4 Se dispone de S/. 5000 para invertirlos según los dos planes de inver- sión A y B, que ofrecen ganancias o utilidades como se muestran en la tabla: Cantidad invertida 0 1000 2000 3000 Utilidad de A 0 200 650 800 Utilidad de B 0 250 600 900 Los depósitos deben hacerse en cantidades múltiplos de 1000 y se puede invertir usando una parte en cada plan. Desarrollar un modelo de programación matemático para obtener la mayor utilidad. Solución Sean a y b, en miles, las cantidades que se invierten en los planes A y B. Entonces a + b ≤ 5, a y b enteros no negativos. Las utilidades de los planes pueden expresarse mediante las funcio- nes U y V definidas por U(0) = 0.00, U(1) = 0.20, U(2) = 0.65, U(3) = 0.80 V(0) = 0.00, V(1) = 0.25, V(2) = 0.60, V(3) = 0.90 Por tanto, el modelo requerido es Maximizar G (a, b) = U (a) + V (b) sujeto a a + b ≤ 5 a y b enteros no negativos. 25 Capítulo 1. Introducción Problema 5 Resuelva, por simple inspección, el problema anterior. Solución Para cada valor de a = 0, 1, 2, 3 calculamos el valor máximo de la ganancia: G (a, b), por ejemplo, si a = 2, U(2) = 0.65, ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ } { } 2, 2 0 , 2 1 , 2 2 , 2 3 0.65 0, 0.65 0.25, 0.65 0.60, 0.65 0.90 1.55, Max G b Max U V U V U V U V Max = + + + + = + + + + = que se obtiene en b=3. Procediendo de esta manera se obtienen los siguientes resultados: Max G (0, b) = 0.90, en b = 3; Max G (1, b) = 1.10, en b = 3 Max G (2, b) = 1.55, en b = 3 Max G (3, b) = 1.40, en b = 2 La ganancia máxima es 1.55 en miles, o 1550, y se obtiene en a = 2 y b = 3, esto es, invirtiendo 2000 en el plan A y 3000 en el plan B. Problema 6. Problema de transporte Se desea transportar un producto de las fábricas A y B a los locales 1 y 2. Los costos de transporte por unidad de producto son: 1 2 A 2 6 B 3 5 y las cantidades disponibles en A y B son 1500 y 2000, respectivamente, y se requieren 1800 y 1700 unidades en 1 y 2, respectivamente. Determine un modelo de programación que minimice el costo total de transporte. 26 Maynard Kong Solución Sean a1 y a2 las cantidades que se envían desde A a los locales, y b1, b2, similarmente para B. Según las cantidades disponibles se tiene a1 + a2 = 1500 b1 + b2 = 2000 y para los locales a1 + b1 = 1800 a2 + b2 = 1700 siendo el costo de envío C = 2a1 +6a2 +3b1 + 5b2 Así, el modelo del problema es Minimizar C = 2a1 + 6a2 + 3b1 + 5b2 sujeto a a1 + a2 = 1500 b1 + b2 = 2000 a1 + b1 = 1800 a2 + b2 = 1700 y todas las variables enteras y no negativas. Problema 7. Problema del corte mínimo Una fábrica de papel que produce rollos de papel A y B de papel de 6 y 9 metros de ancho, respectivamente, recibe un pedido de rollos de papel, uno de 2 metros de ancho y 800 metros de longitud y otro de 5 metros de ancho y 900 metros de longitud. Suponiendo que los recortes de rollos del mismo ancho pueden ser pegados para satisfacer las longitudes requeridas, se desea determinar cómo deben recortarse los anchos de los rollos A y B para minimizar la cantidad de papel que se pierde. 27 Capítulo 1. Introducción Solución Hay que considerar las distintas maneras de cortar los anchos de 6 y 9 en anchos de 2 y 5. Para el rollo A, 6 = 2 + 2 + 2 = 3×2, que nos indica tres cortes de 2 sin sobrante 6 = 5 + 1, que da un corte de 5 y sobra 1 unidad de ancho Si a1 y a2 son las longitudes de los cortes de A, para cada caso, la cantidad sobrante es 0a1 + 1a2 metros cuadrados. Puesto que se trata de minimizar las cantidades sobrantes, se omiten los casos en los cuales los cortes originan partes sobrantes con valores mayores. Y para el rollo B, 9 = 4×2 + 1, cuatro cortes de 2 y sobra 1 9 = 2×2 + 5, dos cortes de 2, uno de cinco y sobra 0 de donde, designando por b1 y b2 las longitudes de los cortes en ambos casos, la cantidad sobrante es 1b1 + 0b2 La cantidad total de papel sobrante es S = a2 + b1 en metros cua- drados. Los datos se muestran en la tabla: A B clase a1 a2 b1 b2 Longitud total 1 (ancho 2) 3 0 4 2 800 2 (ancho 5) 0 1 0 1 900 sobrante 0 1 1 0 Las longitudes totales de los rollos producidos dan lugar a las res- tricciones 3a1 + 0a2 + 4b1 + 2b2 ≥ 800, para la clase 1 0a1 +   a2 + 0b1 +   b2 ≥ 900, para la clase 2 28 Maynard Kong Finalmente, el modelo requerido es Minimizar S = a2 +b1 sujeto a 3a1 + 4b1 +2b2 ≥ 800   a2 + b2 ≥ 900 y todas las variables son no negativas. Problema 8. Problema de programación de producción Un producto A requiere dos unidades del componente B y tres uni- dades del componente C. Los componentes se fabrican con materias primas 1 y 2, de las que se disponen 200 y 300 unidades, respectiva- mente. Se dispone de dos procesos de producción P y Q. Una ejecución del proceso P requiere 8 y 4 unidades de las materias primas 1 y 2, respectivamente, y produce 6 unidades de B y 5 unidades de C. Y cada corrida del proceso Q demanda 5 y 7 unidades de materias primas y da 4 y 8 unidades de B y C. Formule el modelo de programación que halle cuántas veces debe eje- cutarse cada proceso para obtener el máximo de unidades del producto A. Solución Se tiene la siguiente tabla por corrida de cada proceso Proceso Materia requerida (unidades) Componente producido (unidades) 1 2 B C P 8 5 6 9 Q 5 7 4 12 Si p y q los números de veces que se ejecutan los procesos P y Q, respectivamente, se tiene: cantidad requerida de materia 1  8p + 5q ≤ 200 cantidad requerida de materia 2  5p + 7q ≤ 300 y las cantidades de componentes producidos son: 29 Capítulo 1. Introducción de tipo B 6 p+4 q, con lo que se puede completar 6 4 3 2 2 p q p q+ = + productos A y de tipo C 9 p+12 q, que permite completar 9 12 3 4 3 p q p q+ = + pro- ductos A El número N de productos A resultante es el menor de estos, o sea N = 3p + 2q Así, el modelo es Maximizar N = 3q + 2p sujeto a 8p + 5q ≤ 200 5p + 7q ≤ 300 p y q enteros no negativos. Problema 9 En un terreno de 100 hectáreas se puede cultivar arroz y frijoles. En un año bueno, la ganancia por hectárea de arroz es 750 y la de frijoles 500; en cam- bio, en un año malo, las ganancias son de 210 y 360, respectivamente. Se dedica a cada planta no más de 4/5 de hectáreas del terreno y se requiere determinar cuántas hectáreas deben cultivarse de cada pro- ducto para maximizar la ganancia total en un año bueno y asegurar que la ganancia en un año malo sea al menos de 30.000. Formule el modelo del programa. Solución Sean a y f  las cantidades de hectáreas de arroz y frijoles a cultivar. Entonces a + f ≤ 100 a ≤ 80, los 4/5 de 100    f ≤ 80 La ganancia en un año bueno es Gb = 750a + 500f y la de un año malo es Gm = 210a + 360f, que debe ser al menos 30000. 30 Maynard Kong Por lo tanto, el modelo del problema es Max Gb = 750a +500f sujeto a a + f ≤ 100     a ≤ 80     f ≤ 80   210a + 360f  ≥ 30000   a y f  no negativas. Capítulo 2 Introducción a la Programación Lineal 2.1 Formulación del problema de Programación Lineal Se dice que una función numérica f (x1, ..., xn), que depende de varia- bles numéricas x1, x2, ..., xn, es lineal si se expresa como una suma de múltiplos de las variables f (x1, ..., xn) = m1 x1 + m2 x2 + ... + mn xn en donde m1, m2,..., mn son constantes. Por ejemplo, f (x1, x2, x3, x4) = 2x1 - x2 + 4x3 + 6.5x4 Un problema de programación lineal (PPL) tiene la forma: Maximizar (o Minimizar) z = c1 x1 + c2 x2 + ... + cn xn sujeto a las condiciones o restricciones { } { } { } { } 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1 1 2 2 , , , , , , , , n n n n i i in n i m m mn n m a x a x a x b a x a x a x b a x a x a x b a x a x a x b + + + ≤ = ≥ + + + ≤ = ≥ + + + ≤ = ≥ + + + ≤ = ≥       32 Maynard Kong en donde x1, x2, ..., xn  son variables, c1, c2, ..., cn, a11, a12, ..., am1, ...,amn, b1, b2, ..., bm , son constantes y en cada condición se asume uno de los signos ≤, = o ≥. Así, tanto la función objetivo z = z (x1, ..., xn  ) como las funciones que definen los miembros izquierdos de las condiciones o restricciones son funciones lineales de las variables de decisión x1, x2, ..., xn. En este caso, a las constantes c1, c2, ..., cn de la función objetivo se les suele denominar costos o coeficientes de costos. Se llama solución factible a cualquier colección de valores x1, x2, ..., xn que cumplan todas las restricciones. El problema consiste en determi- nar el mayor zmax (o menor zmin) de los valores de la función objetivo z (x1, x2, ..., xn), evaluada sobre todas las soluciones factibles y, desde luego, indicar una solución óptima, esto es, una solución factible que produzca ese valor. Ejemplos 1. Maximizar  z = 4x1 + 5x2 sujeto a    3x1 - 4x2 ≤ 30 - x1 + 6x2 ≥ 20     x1 ≥ 3; El valor máximo de z es 164 y se obtiene en la solución óptima x1 = 26, x2 = 12. 2. Maximizar  z = -13x1 + 8x2 + 20x3 sujeto a 2x1 + x2 + 4x3 = 80 x1 - 3x2 + 5x3 ≥ 100 x1 ≥ 0 x2 ≥ 0 En este caso zmax = 400 en x1=0, x2=0, x3=20. 33 Capítulo 2. Introducción a la Programación Lineal 3. Minimizar  z = 20x1 - x2 + 4x3 - 5x4 sujeto a x1 + x2 + x3 + x3 +x4 = 10 x2 + 2x4 ≤ 5; y todas las variables ≥ 0. El valor óptimo es zmin = 15 y se alcanza en x1 = 0, x2 = 5, x3 = 5, x4 = 0. 4. Minimizar  z = 6x1 - 10x2 + 4x3 - 6x4 sujeto a x1 + 3x3 ≤ 30 x2 -4x3 + 2x4 ≥ -4 todas las variables no negativas. En este problema el valor mínimo no existe, pues, si se asigna a las variables de decisión x1 = 0, x2 = t + 36, x3 = 10, x4 = 0, cualquier t ≥ 0, se comprueba que estas son soluciones factibles (cumplen todas las restricciones) en las que la función objetivo vale z = z(t) = -10t + 320 y, por lo tanto, adquiere un valor menor que cualquier número que se precise (en notación de límites: z(t) tiende a -∞ cuando t tiende a +∞). 5. Minimizar:  z = 6x1 - 10x2 + 4x3 - 6x4 sujeto a x1 + 3x3 ≤ 30 x2 - 4x3 + 2x4 ≥ -4 x3 ≥ 12 x1 ≥ 0 El problema no tiene soluciones factibles, pues las restricciones son incompatibles o inconsistentes. En efecto, de las dos últimas restric- ciones se obtiene la desigualdad x1 + 3x3 ≥ 0 + 3 × 12  ó  x1 + 3x3 ≥ 36 que contradice a la primera restricción x1 + 3x3 ≤ 0. 34 Maynard Kong 2.2 Solución geométrica de problemas con dos variables de decisión Los problemas de programación lineal con dos variables de decisión y un número reducido de restricciones pueden ser resueltos gráficamente por métodos geométricos sencillos utilizando un plano cartesiano cuyos ejes de coordenadas son las variables de decisión. Allí se trazan la región factible y algunas rectas asociadas a la función objetivo que permiten determinar en qué puntos esta obtiene su valor óptimo, cuando existe. Este método muestra gráficamente dos propiedades de los proble- mas de programación lineal: 1) el conjunto factible es un polígono, esto es, una región del plano limitada por rectas 2) si la función objetivo tiene óptimo, entonces este se alcanza en uno de los vértices del polígono. y por lo tanto para encontrar una solución óptima es suficiente calcular los vértices y evaluar la función objetivo en estos. Además, si el polígono es cerrado —sus lados forman una poligonal cerrada— la función objetivo siempre tiene valor óptimo. El siguiente ejemplo ilustra el procedimiento que se aplica en estos casos. Ejemplo 1 Resuelva geométricamente el problema Maximizar z = 2x+3y sujeto a las restricciones (1) -3x + 2y ≤ 6 (2) 2x + y ≤ 10 (3) 2x - y ≤ 6 (4) x ≥ 0 (5) y ≥ 0. 35 Capítulo 2. Introducción a la Programación Lineal Solución Trazamos la región factible R ( )0,3 A ( )2,6B ( )2,4C ( )3,0D yxz 333 +=−= zzz 3218 +== 623 =+− yx 102 =+ yx 62 =− yx R Y X R es el polígono cerrado con vértices los puntos A, B, C, D y el origen del sistema. Se hallan los conjuntos R1, ..., R5 de puntos que satisfacen las restricciones (1)-(5), respectivamente. Por ejemplo, para determinar R1 que corresponde a (1) - 3x + 2y ≤ 6 se traza la recta dada por la ecuación - 3x + 2y = 6, que resulta de sustituir el signo de des- igualdad por el de igualdad, y en la figura es la recta que pasa por los puntos A y B. Esta recta divide al plano en dos semiplanos, determina- dos por las desigualdades -3x +2y ≤ 6, semiplano inferior y -3x +2y ≥ 6, semiplano superior. Para saber cuál de los semiplanos es R1 basta seleccionar arbitra- riamente un punto fuera de la recta, y comprobar cuál de las dos desigualdades satisface. Por ejemplo, el punto (0,0) satisface la pri- mera desigualdad, que es la restricción tratada, y por lo tanto, R1 es el semiplano que contiene a (0,0), o el semiplano inferior o debajo de la recta. La región factible R es la intersección de los semiplanos obtenidos. 36 Maynard Kong A continuación se analiza cómo varía la función objetivo z = 2x +3y respecto del conjunto factible R. Con este propósito se fija un valor constante v y se considera la recta z = v = 2x + 3y, que es el conjunto de puntos (x, y) en los cuales la función z vale v. Todas las rectas así obtenidas son paralelas. Para apreciar el com- portamiento de la función objetivo se trazan las rectas (paralelas) correspondientes a dos valores distintos de v. En la figura, se muestran las rectas z = -3 = 2x + 3y  y  z = 18 = 3x + 3y. Ahora se observa que para que la función objetivo tome un valor v se requiere que la recta asociada interseque la región poligonal R y además cuando v aumenta, por ejemplo de -3 a 18, la recta z = v = 2x + 3y se desplaza paralelamente de izquierda a derecha. Así, por simple inspec- ción se concluye que el valor máximo de z se alcanza en el vértice B(2,6) y por lo tanto zmax = v = 2(2) +3(6) = 20. A veces es un tanto complicado apreciar directamente cuál es el vér- tice de valor óptimo y en estos casos simplemente se evalúa la función objetivo en los vértices vecinos y se comparan estos valores. Ejemplo 2 Determine los valores máximo y mínimo de la función z = z(x,y) = 10x-3y sujeta a las restricciones del ejemplo anterior. Solución Puesto que la región factible es un polígono cerrado es suficiente eva- luar la función en los vértices del polígono: z (0,0) = 0 z (0,3) = -3 z (2,6) = -18 z (4,2) = 34 z (3,0) = 30 de donde zmax = 34 en x = 4, y = 2, y zmin = -18 en x = 2, y = 6. 37 Capítulo 2. Introducción a la Programación Lineal 2.3 Problemas propuestos Problema 1 Resuelva por métodos geométricos el problema Maximizar z = 4x - 2y sujeto a   x + 6y ≤ 28 3x -4y ≤ 7   y ≥ 2 5x +2y ≥ 14 Halle todos los vértices del polígono de soluciones factibles. Respuesta zmax = 21  en  x = 7,  y = 3.5. Los vértices son (1, 4.5), (7, 3.5), (5, 2) y (2, 2) Problema 2 Resuelva gráficamente el problema Minimizar z = x +y sujeto a 4x + 3y ≥ 19    3x -2y ≥ -7     x-2y ≤ 2 Respuesta zmin = 5  en  x = 4,  y = 1. Problema 3 Resuelva el problema Minimizar  z = x -y sujeto a las restricciones del problema 3. 38 Maynard Kong Respuesta La función objetivo no tiene mínimo pues las rectas z = v = x - y, paralelas a la diagonal y = x, intersecan al polígono factible para cualquier valor negativo de v, que es lo que se observa cuando la diagonal se desplaza paralelamente de izquierda a derecha. Problema 4 El siguiente es el modelo de programación del problema 9, Capítulo 1, 1.6: Max Gb = 750a + 500f sujeto a a+f ≤ 100 a ≤ 80 f ≤ 80 210a + 360f ≥ 30000 a y f no negativas. Por métodos geométricos encuentre cuántas hectáreas del terreno deben dedicarse a cada cultivo para obtener la mayor ganancia en un buen año. Respuesta f = 60, a = 40, ganancia máxima = 60000 Problema 5 Resuelva el problema Maximizar  6x1 + 4x2 sujeto a -2x1 + x2 ≤ 1 x1 ≤ 2 x1 + x2 ≤ 3 x1, x2 ≥ 0. Respuesta Máximo = 16 en x1=2, x2=1. 39 Capítulo 2. Introducción a la Programación Lineal Problema 6 Determine el valor mínimo de z=10x1 +3x2 sujeto a x1+x2 ≥ c x1 ≤ 6 x1 ≥ 2 x2 ≤ 12 x2 ≥ 1 en cada caso siguiente: a) cuando c =10, b) cuando c =20. Respuesta a) c =10: mínimo = 44 en x1=2, x2=8 b) c =20: el problema no tiene soluciones Problema 7 Halle el valor máximo de z = -2x1 + x2 sujeto a x1 +x2 ≥ 10 -10x1 +x2 ≤ 10 -4x1 +x2 ≤ 20 x1 +4x2 ≥ 20 x1, x2 ≥ 0. Respuesta No existe valor máximo pues la función z toma valores arbitrariamente grandes. Problema 8 Resuelva el problema Max z=z(x,y) = mínimo {2x + y, x + 2y} sujeto a las condiciones 2x -5y ≥ -10 2x -y ≤ 6 x, y ≥ 0. 40 Maynard Kong Indicación Este problema no tiene la forma de un problema de programación lineal pues la función objetivo no es lineal. No obstante, de la defini- ción de la función se tiene z = z(x,y) = 2x +y si 2x+y ≤ x+2y, o x-y ≤ 0 y z = z(x,y) = x +2y si 2x+y ≤ x+2y, o x-y ≥ 0 y por lo tanto agregando sucesivamente las restricciones x - y ≤ 0, x - y ≥ 0 el problema se descompone en los subproblemas lineales: (P1) Max z1 = 2x + y sujeto a 2x -5y ≥ -10 2x -y ≤ 6 x, y ≥ 0 x -y ≤ 0 (P2) Max z2 = x+2y sujeto a 2x -5y ≥ -10 2x -y ≤ 6 x, y ≥ 0 x-y ≥ 0 El valor máximo del problema inicial es el máximo de los valores óptimos de estos subproblemas. Geométricamente, mediante la recta y=x, se ha dividido el polí- gono factible en dos subpolígonos sobre los cuales la función objetivo adquiere una expresión lineal. Respuesta (P1) tiene máximo 10 en  x = 10/3,  y = 10/3 (P2) tiene máximo 13 en  x = 5, y = 4 El valor máximo del problema es el de (P2), esto es, 13 en x = 5, y = 4. 41 Capítulo 2. Introducción a la Programación Lineal Problema 9 Resuelva el problema Max z = z(x,y) = máximo {2x + y, x + 2y} sujeto a las restricciones del problema 8. Respuesta El valor óptimo es 14 en x = 5, y = 4. 2.4 Forma estándar del problema de Programación Lineal Se dice que un problema de programación lineal tiene la forma están- dar si (1) todas las variables de decisión son no negativas, y (2) las (restantes) restricciones son de igualdad con constantes no negativas en el lado derecho. De manera explícita, el problema dado en forma estándar es Maximizar (o Minimizar) z= c1 x1 + c2 x2 ... + cn xn sujeto a 11 1 12 2 1 1 21 2 22 2 2 2 2 1 2 2 2 n n n m m mn m m a x a x a x b a x a x a x b a x a x a x b + + + = + + + = + + + =     x1, x2, ..., xn son no negativas y las constantes b1, b2, ..., bm son no negativas. 2.4.1 Ejemplos Tienen la forma estándar los siguientes problemas: 1) Maximizar  z= 3x+5y -z sujeto a -x + 2y + 6z = 20 4y - z = 0 x, y, z ≥ 0. 42 Maynard Kong 2) Minimizar  z= x1 + x2 - 3x3 + 2x4 sujeto a   x1 + x2 + x3 + x4 = 25 x1 + 3x2 - 2x3 + 7x4 = 6    x1 + 4x3 - 4x4 = 16 y todas las variables son no negativas. 2.4.2 Importancia de la forma estándar Cualquier problema de programación lineal expresado en forma están- dar puede ser resuelto por el método del símplex debido a George Dantzig. Como se verá a continuación, si un problema de programación lineal no es dado en la forma estándar, este puede transformarse en uno que tiene esta forma y el mismo valor óptimo y, además, cuyas soluciones óptimas dan lugar a soluciones óptimas del problema inicial. Así, para resolver un problema de programación lineal (1) si es necesario, se transforma en uno equivalente que tiene la forma estándar y (2) se resuelve en la forma estándar y se obtienen las soluciones del problema dado. PPL GENERAL → PPL ESTÁNDAR → SÍMPLEX → SOLUCIÓN 2.4.3 Conversión a la forma estándar Las operaciones para llevar un problema de programación lineal a la forma estándar son las siguientes: 1) Si es negativo el término constante del lado derecho de una restricción, se intercambian los dos miembros; esto equivale a cambiar de signo a todos los términos en ambos lados de la restricción y, adicionalmente, cuando la restricción es de des- igualdad, a invertir el sentido de la desigualdad. 43 Capítulo 2. Introducción a la Programación Lineal Es decir, si la restricción es si ai1 x1 + ... + ain xn {≤, =, o ≥} en donde bi es negativo entonces - (ai1 x1 + ... + ain xn) {≤, =, o ≥} - bi con -bi positivo y, cuando se aplique, con el signo de desigualdad invertido. Se indican algunos ejemplos: restricción restricción transformada con término constante no negativo 3x - y + 2z ≤ -5 3x - y + 2x ≤ -5 3x - y + 2z ≤ -5 -3x + y - 2z ≤ 5 -3x + y - 2x ≤ 5 -3x + y - 2z ≤ 5 2) Una restricción, de desigualdad con signo ≤, puede ser reempla- zada por una de igualdad si se suma una variable no negativa al lado izquierdo para convertirla en una de igualdad: si ai1 x1 + ... + ain xn ≤ bi entonces ai1 x1 + ... + ain xn + hi = bi , con hi no negativa Esta variable se llama variable de holgura (por defecto). Por ejemplo, la restricción - 3x + y - 2z ≤ 5 se reemplaza por - 3x + y - 2z + h1 = 5 h1 ≥ 0 3) Una restricción de desigualdad con signo ≥ puede ser reempla- zada por una de igualdad si se resta una variable no negativa al lado izquierdo para convertirla en una de igualdad: si ai1 x1 + ... + ain xn ≤ bi entonces ai1 x1 + ... + ain xn - hi = bi 44 Maynard Kong con hi no negativa. Esta variable se llama variable de holgura (por exceso o superávit) Por ejemplo, la restricción - 3x + y - 2z ≥ 5 se reemplaza por -3x + y - 2z + h2 = 5 h2 ≥ 0 Las operaciones (1), (2) y (3) no modifican la función objetivo. 4) Una variable irrestricta, lo cual significa que puede tomar valores negativos y positivos, puede ser reemplazada por la diferencia de dos variables no negativas. Si x2 es irrestricta, entonces se escribe x2= u-v con dos nuevas variables u y v no negativas. 5) Una variable x no positiva, esto es, menor que o igual a cero, puede ser reemplazada por una variable no negativa precedida del signo menos, es decir, se efectúa el cambio de variable x = -u, en donde u es no negativa. La sustitución de una variable irrestricta o una no positiva se realiza tanto en las restricciones como en la función objetivo. Ejemplo 1 Exprese en forma estándar el problema Minimizar  x + 2y - z + 4w sujeto a x + y ≤ 10 2x + y + 3z ≤ 18 z + w ≥ 14 x, y, z no negativas w irrestricta. 45 Capítulo 2. Introducción a la Programación Lineal Solución No es necesario cambiar de signo a ninguna restricción pues todas ya tienen términos constantes no negativos. Sumando las variables de holguras h1, h2 a las dos primeras restric- ciones y restando la variable de holgura h3 a la tercera restricción x + y + h1= 10 2x + y + 3z + h2 = 18 z + w - h3 = 14 Luego, reemplazando la variable irrestricta w por w = w1 - w2 en la función objetivo y en las restricciones, se obtiene la forma estándar Minimizar  x + 2y - z + 4w1- 4w2 sujeto a x + y + h1 = 10 2x + y + 3z + h2= 18 z + w1-w2 - h3 = 14 con todas las variables no negativas. Ejemplo 2 Escriba en forma estándar el problema Maximizar  z = 2x1 - 4x2 + 5x3 - 3x4 sujeto a las restricciones x1 - x2 + 5x3 ≥ -12 -3x1 + 4x2 +2x4 = -8 x1 + x2 -2x3 +x4 -5x5 ≥ 4 x1 es no positiva y las demás variables no negativas. Solución La primera restricción se convierte en -x1 +x2 -5x3 + h1 = 12 después de cambiar los signos de los términos y el signo de la desigual- dad y de sumar la variable de holgura h1. 46 Maynard Kong A la segunda restricción se le cambian los signos de los términos y a la tercera restricción se le resta la variable de holgura h3. Puesto que x1 es no positiva, se reemplaza x1= - u, en donde u es una variable no negativa. Así, la forma estándar es Maximizar  z = -2u - 4x2 + 5x3 - 3x4 sujeto a las restricciones -u + x2 - 5x3 + h1 = 12 -3u - 4x2 - 2x4 = 8 -u + x2 - 2x3 + x4 -5x5 - h3 = 4 con todas las variables no negativas. 2.5 Restricciones equivalentes de la forma estándar El conjunto de restricciones de igualdades de la forma estándar a11x1 + a12x2   + ... + a1n xn = b1 ai1 x2 + ai2 x2   + ... + ain x2 = b2 ... am1x2+ am2 x2 + ... + amn xm = bm es un sistema de ecuaciones lineales con m ecuaciones y n incógnitas x1, x2, ..., xn, y una solución factible es, en particular, una solución de este sistema. Una ventaja de esta representación se refiere a la posibilidad de modificar o reemplazar estas ecuaciones por otras de manera que las soluciones son las mismas y las nuevas restricciones son más adecuadas para resolver el problema. Las soluciones del sistema se preservan cuando (1) una ecuación se multiplica por una constante k distinta de cero; en efecto, son equivalentes las ecuaciones ai1 x1 + ... + ain xn = bi y kai1 x1+ ... + kain xn = kbi 47 Capítulo 2. Introducción a la Programación Lineal o (2) se suma, o resta, d veces una ecuación a otra, ya que, cuando i, j son distintos, las dos ecuaciones ai1 x1 + ... + ain xn = bi aj1 x1 + ... + ajn xn = bj son equivalentes a las ecuaciones ai1 x1 + ... + ain xn = bi (aj1 + dai1) x1 + ... + (ajn + dain)xn = bj + dbi Estas operaciones son las que se aplican para resolver sistemas de ecuaciones lineales por el método de eliminación de Gauss. Ejemplo Sea el problema Maximizar z = 3x + 4y sujeto a las restricciones -x + 2y + u = 6 2x + y + v = 8 x, y, u, v no negativas. (1) Mediante las operaciones indicadas obtenga restricciones equivalen- tes de manera que cada una contenga solo una de las variables x, y. (2) Determine la expresión de la función objetivo que resulta de reemplazar las variables x, y despejadas de las ecuaciones. (3) Encuentre el valor máximo de z. Solución (1) Se elimina la variable y de la primera ecuación restándole 2 veces la segunda ecuación: -5x +u -2v = -10 o x - 0.2u + 0.4v = 2 Similarmente, se elimina x de la segunda ecuación sumándole 2 veces la primera ecuación: 5y +2u + v = 20 o y + 0.4u + 0.2v = 4 48 Maynard Kong Luego, las nuevas ecuaciones o restricciones son x - 0.2u + 0.4v = 2 y + 0.4u + 0.2v = 4 y todas las variables no negativas. (2) Despejando las variables de las ecuaciones obtenidas y reempla- zando en la función objetivo z = 3x +4y se tiene z = 3(2 + 0.2u - 0.4v) + 4(4 -0.4u -0.2v) z = 22 - u - 0.4v (3) De z = z(x, y, u, v) = 22 - u - 0.4v se tiene z ≤ 22 pues u y v son no negativas. Luego, haciendo u=v=0 en las ecuaciones de la parte (1) se obtiene x=2, y=4, y por lo tanto se encuentra la solución factible x=2, y=4, u=0, v=0, en la que la función objetivo vale 22. Así, se cumple z(x, y, u, v) ≤ 22 = z(2,4,0,0) y esto demuestra analíticamente que 22 es el valor máximo. 2.6 Variables básicas y soluciones básicas factibles Sea el sistema de ecuaciones lineales a11 x1 + ... + a1n xn = b1 a21 x1 + ... + a2n xn = b2 ... am1 x1 + ... + amn xn = bm dadas por las restricciones de igualdad de la forma estándar. Si el sistema es compatible, esto es, tiene soluciones, se puede asu- mir que el número m de ecuaciones es menor que o igual al número n de variables, ya que si m>n aplicando las operaciones con las ecuacio- nes, descritas en la sección anterior, se encuentra que hay al menos m-n ecuaciones redundantes y por lo tanto pueden eliminarse del sistema. Así, en lo que sigue asumiremos m ≤ n. 49 Capítulo 2. Introducción a la Programación Lineal Se dice que m variables son básicas si el sistema puede ser escrito de manera que cada ecuación contiene solamente una de ellas. Las n-m varia- bles restantes se denominan no básicas, para distinguirlas de las anteriores. De modo explícito, renombrando las variables y reordenando las ecuaciones si es necesario, las variables x1, ..., xm, son básicas si el sistema de ecuaciones puede ser escrito, o convertido, en uno de la forma x1 + a1, m+1 xm+1 + ... + a1,n xn = b1 ... xm + am,m+1 xm+1 + ... + a1,n xn = bm de modo que tales variables aparecen (con coeficientes 1) exactamente una vez en las distintas m ecuaciones y dependen de las variables no básicas xm+1, ..., xn. Haciendo cero cada variable no básica en el sistema se obtiene la solución factible x1= b1, ..., xm= bm, xm+1 = 0, ..., xn = 0 que se denomina solución básica factible correspondiente a las variables básicas. 2.6.1 Cálculo de soluciones básicas factibles Una manera directa de determinar soluciones básicas factibles es hacer n-m variables iguales a cero y resolver el sistema resultante. Si este tiene una única solución con valores no negativos, entonces (1) estos valores juntos con los ceros de las variables anuladas for- man una solución básica factible y (2) son básicas las variables del sistema resuelto. Ejemplo 1 Halle las soluciones básicas factibles del conjunto de restricciones   x + 2y -3z = 10 2x + 5y -6z = 23. 50 Maynard Kong Solución En este caso m=2, n=3, de manera que hay que anular n-m =1 variable. (1) Si x=0 y se resuelve el sistema 2y -3z = 10 5y -6z = 23 se encuentra la solución única y = 3, z = -4/3 y por lo tanto x=0, y=3, z=-4/3 es una solución básica. Sin embargo, no es factible pues la variable z tiene un valor negativo. (2) Haciendo y = 0, el sistema resultante es   x - 3z = 10 2x - 6z = 23 que no tiene solución pues restando 2 veces la primera ecuación de la segunda se obtiene la contradicción 0 = 3. (3) Haciendo z = 0, se resuelve el sistema   x + 2y = 10 2x + 5y = 23 que tiene única solución x = 4, y = 3. Luego, x=4, y=3, z=0 es una solución básica factible con varia- bles básicas x, y. En resumen, para las restricciones dadas solamente hay una solu- ción básica factible: x=4, y=3, z=0 con variables básicas x, y. Ejemplo 2 Encuentre las soluciones básicas factibles de las restricciones 2x1 + x2 - x3 + x4 = 2 4x1 + 2x2 -2x3 + x4 = 4 Solución En este caso se deben anular 4-2 = 2 variables y resolver las ecuaciones para las variables restantes. 51 Capítulo 2. Introducción a la Programación Lineal Se analizan los casos posibles (1) x1 = 0, x2 = 0, el sistema es   -x3 + x4 = 2 -2x3 + x4 = 4 de donde   x3 = -2, x4 = 0 y la solución es básica pero no es factible. (2) x1 = 0, x3 = 0 para el sistema   x2 + x4 = 2 2x2 + x4 = 4 se halla x2 = 2, x4 = 0 y, por lo tanto, la solución x1=0, x 2=2, x 3=0, x 4=0 es básica fac- tible. (3) x1 = 0, x4 = 0 resolviendo el sistema   x2 - x3 = 2 2x2 -2 x3 = 4 se observa que tiene infinitas soluciones (la segunda ecuación se obtiene de la primera). Así, no se obtiene una solución básica. Los restantes casos (4) x2 = 0, x3 = 0 (5) x2 = 0, x4 = 0 (6) x3 = 0, x4 = 0 se tratan de modo similar; en (4) y (5) se hallan soluciones básicas fac- tibles y en (6) no, pues tiene infinitas soluciones. La siguiente tabla muestra los resultados de los cálculos. CASOS VAR. BÁSICAS SOLUCIÓN BÁSICA FACTIBLE x1=0, x3=0 x2, x4 x1=0, x2=2, x3=0, x4=0 x2=0, x3=0 x1, x4 x1=1, x2=0, x3=0, x4=0 x2=0, x4=0 x1, x3 x1=1, x2=0, x3=0, x4=0 52 Maynard Kong Así, este conjunto de restricciones tiene dos soluciones básicas fac- tibles. Ejemplo 3 Dado el conjunto de restricciones -x + 2y ≤ 6 2x + y ≤ 8 x,y no negativas (a) calcule los vértices del polígono que representa la región factible en el plano XY, (b) obtenga la forma estándar del conjunto de restricciones y deter- mine las soluciones básicas factibles, (c) muestre que a cada vértice del polígono le corresponde una solu- ción básica factible de la forma estándar. Solución (a) El polígono en cuestión es el cuadrilátero limitado por las rectas -x+2y = 6, 2x+y = 8, x = 0 y = 0. Los vértices son los puntos (0,0), (0,3), (2,4) y (4,0). (b) La forma estándar de las restricciones se obtiene sumando una variable de holgura a cada restricción de igualdad -x + 2y + h1 = 6 2x + y + h2 = 8 y las soluciones básicas son VARIABLES BÁSICAS SOLUCIÓN (1) x, y x = 2, y = 4, h1=0, h2=0 (2) x, h1 x = 4, y = 0, h1=10, h2=0 (3) y, h2 x = 0, y = 3, h1=0, h2=5 (4) h1, h2 x = 0, y = 0, h1=6, h2=8 53 Capítulo 2. Introducción a la Programación Lineal (c) Según (a) los vértices del polígono factible son x = 0, y = 0 x = 0, y = 3 x = 2, y = 4 x = 4, y = 0 y estos están en correspondencia con las soluciones básicas facti- bles indicadas por (4),(3),(1) y (2), respectivamente. 2.6.2 Importancia de las soluciones básicas factibles Se demuestra que el valor óptimo del problema lineal estándar se obtiene necesariamente en una solución básica factible. Por esta razón, la búsqueda del valor óptimo sobre la región facti- ble se restringe al conjunto de las soluciones básicas factibles, que es finito. Esta propiedad puede comprobarse cuando se resuelven gráfi- camente los problemas de programación lineal con dos variables de decisión, para los cuales, como se ha visto, las soluciones óptimas se ubican en algunos de los vértices del polígono factible. El ejemplo ante- rior muestra que los vértices son precisamente las soluciones básicas de la forma estándar del problema. Así, geométricamente, las soluciones básicas factibles son los vértices de la región factible, en el caso de dos variables. 2.7 Problemas propuestos Problema 1 Exprese en forma estándar el problema Maximizar  z = 2x1 + 8 x2 sujeto a x1 - 10x2 ≥ 8 9x1 + 15 x2 ≤ 80 y x1, x2 ≥ 0. 54 Maynard Kong Solución Las restricciones son x1 - 10 x2 - h1 = 8 9x1 + 15x2 + h2 = 80 con todas las variables no negativas. Problema 2 Halle la forma estándar de Minimizar  z = 2x + y - u + 4v sujeto a -x + y ≥ -6 y -u ≥ 4 x +y +v = 10 x, u, u ≥ 0 y la variable y irrestricta. Solución Maximizar  z = 2x + y1 -y2 - u + 4v sujeto a x - y + h1 = 6 y - u - h2 = 6 x + y1 - y2 + v = 10 y todas las variables no negativas en donde se ha reem- plazado y = y1 - y2, diferencia de variables no negativas. Problema 3 Considere el problema Maximizar  z = 2x1 + 4x2 + 6x3 - 2x4 sujeto a x1 + x2 ≤ 4 x1 ≥ -3 x1 ≤ 0 x2 ≥ 0 Exprese el problema en la forma estándar. 55 Capítulo 2. Introducción a la Programación Lineal Respuesta Maximizar  z = -2u + 2x2 +6x3 -2x4 sujeto a -u + x2 +h1= 4 u - h2 = 3 todas las variables no negativas. Puesto que x1 es no positiva se ha hecho el cambio de variable x1=-u, de modo que u es una variable no negativa. Problema 4 Sea el conjunto de restricciones x1 + 5x2 + 4x3 + 8x4 - x5 = 8 x1 + 6x2 + 2x3 + 4x4 - x5 = 4 halle todas las soluciones básicas factibles y las variables básicas corres- pondientes. Respuesta Soluciones básicas factibles variables básicas asociadasx1 x2 x3 x4 x5 0 0 2 0 0 x1, x3 0 0 0 1 0 x1, x4 0 0 2 0 0 x2, x3 0 0 0 1 0 x2, x4 0 0 2 0 0 x3, x5 0 0 0 1 0 x4, x5 Hay dos soluciones básicas factibles y seis pares de variables básicas. Problema 5 Sea el conjunto de restricciones    x - y + 2z - u = 5   2x + y - z - 2u = 1 4x + 3y + z - 3u = 13. 56 Maynard Kong Determine si las siguientes variables son básicas y halle la solución básica factible correspondiente en cada uno de los casos (1) x, y, z (2) y, z, u Respuesta (1) Haciendo u = 0 y resolviendo las ecuaciones se encuentra x = 1, y = 2, z = 3, u = 0, que es una solución básica factible, y las variables x, y, z son básicas. (2) Haciendo x = 0, el sistema tiene solución pero la variable u toma un valor negativo. Las variables no son básicas. Problema 6 Sea el problema Maximizar  z = 3x1 + 2x2 sujeto a 2x1 + x2 + x3 = 45 x1 + 8x2 + x4 = 150 y todas las variables no negativas. (1) Pruebe que las variables x1, x2 son básicas hallando la solución básica respectiva. (2) Exprese la función objetivo en términos de las variables no bási- cas x3, x4, y pruebe que la solución básica hallada es óptima. Respuesta (1) La solución básica es x1 =14, x2 =17, x3 = 0, x4 = 0; (2) 3 42276 15 x xz + = - Capítulo 3 El método del símplex 3.1 Conceptos básicos del método del símplex El método del símplex es un procedimiento para hallar una solución óptima de una programación lineal estándar en el conjunto de solucio- nes básicas factibles. El método se aplica a un problema estándar para el que ya se dis- pone de una solución básica factible y su correspondiente conjunto de variables básicas. A continuación se introducen los conceptos básicos del método del símplex por medio de ejemplos sencillos. Ejemplo 1. Criterio de máximo Sea el problema Maximizar  z = x1 - 9x2 - x3 + 5x4 sujeto a 3x1 - 3x2 + x3 = 15   x1 - 2x2 + x4 = 20 y todas las variables no negativas. El primer paso es determinar un conjunto de variables básicas del sistema de restricciones. En este problema, por simple inspección se observa que x3 y x4 son variables básicas, pues cada una está en una 58 Maynard Kong ecuación distinta y con coeficiente 1, y la solución básica factible es x1 = 0, x2 = 0, x3 = 15, x4 = 20 en la cual la función objetivo tiene el valor z0 = 85. El segundo paso es expresar el problema mediante una tabla para facilitar las operaciones con las ecuaciones. var. bás. x1 x2 x3 x4 = b x3 3 -3 1 0 15 fila 1 = ecuación 1 x4 1 -2 0 1 20 fila 2 = ecuación 2 c 1 -9 -1 5 0 fila c ecuación de z Las dos primeras filas representan las ecuaciones de restricciones, y la última fila representa la función z escrita mediante la ecuación x1 - 9x2 - x3 - 5x4 = z La columna de la izquierda indica las variables básicas seleccionadas. El propósito de disponer los datos de esta manera es expresar la función z de manera que no aparezcan las variables básicas, esto es, que estas tengan coeficientes nulos. Esto equivale a hacer cero los costos -1 y 5 de la fila c, para lo cual a la fila c: se suma la fila 1 y luego se resta 5 veces la fila 2, obteniéndose c' -1 -2 0 0 -85 fila c ecuación de z - 85 Los coeficientes de la fila c': c'1= -1, c'2= -2, c'3= 0 y c'4= 0 se denomi- nan costos reducidos, relativos a las variables básicas x3, x4. Así, la tabla, incluyendo los costos reducidos, es var. bás x1 x2 x3 x4 b x3 3 -3 1 0 15 x4 1 -2 0 1 20 c 1 -9 -1 5 0 c' -1 -2 0 0 -85 en donde la última fila da la expresión de la función objetivo z mediante la ecuación -x1 -2x2 + 0x3 + 0x4 = z - 85 59 Capítulo 3. El método del símplex de donde z = 85 - x1 - 2x2 + 0x3 + 0x4    = 85 - x1 - 2x2 El criterio de máximo indica que si todos los costos reducidos son ≤ 0, entonces la tabla actual proporciona el valor máximo y se alcanza en la solución básica de la misma. Esto puede demostrarse en este caso, ya que la representación de la función objetivo con los costos reducidos puede escribirse así z - 85 = -x1 - 2x2 ≤ 0 en donde la desigualdad ≤ 0 se cumple porque los costos reducidos son ≤ 0 y las variables son ≥ 0. Luego z ≤ 85 = valor en la solución básica factible y por lo tanto zMax = 85 en x1 = 0, x2 = 0, x3 = 15, x4 = 20. Según lo desarrollado se puede adelantar el criterio de máximo: Si todos los costos reducidos son <=0, entonces la función objetivo tiene valor máximo en la solución básica factible. Ejemplo 2. Criterio de divergencia Sea el problema Maximizar  z = x1 - 3x2 - x3 + 5x4 sujeto a 3x1 - 3x2 + x3 = 15      x1 - 2x2 + x4 = 20 y todas las variables no negativas. Como puede apreciarse, este problema tiene el mismo conjunto de restricciones del ejemplo anterior y la función objetivo se diferencia de la anterior solo en el término de la variable x2, que ahora tiene coefi- ciente -3. Escribiendo la tabla correspondiente con los costos de esta función objetivo y calculando los costos reducidos relativos a las variables bási- cas x3 y x4 60 Maynard Kong var. bás x1 x2 x3 x4 b x3 3 -3 1 0 15 x4 1 -2 0 1 20 c 1 -3 -1 5 0 c' -1 1 0 0 -85 Igual que antes para anular los costos -1 y 5 de las variables básicas, a la fila c se le suma la fila 1 y se le resta 5 veces la fila 2. La fila c' da la siguiente expresión de la función objetivo z: z = 85 - x1 + x2 en términos de costos reducidos. No se puede aplicar el criterio de máximo pues hay un costo redu- cido positivo, que es el coeficiente 1 de la variable x2. El siguiente criterio es el de divergencia, según el cual si existe un costo reducido > 0 y la variable asociada tiene coeficientes ≤ en todas las restricciones, entonces el problema no tiene valor máximo, porque se puede hallar soluciones factibles en las cuales la función objetivo toma valores arbitrariamente grandes. En este problema, el costo reducido positivo es el de la variable x2 y sus coeficientes en las restricciones son -2 y -3, que son ≤ 0. Para comprobar que la función objetivo toma valores muy grandes se generan las siguientes soluciones factibles: se hace x2 = t, donde el parámetro t es ≥ 0, se hace igual a cero la otra variable no básica x1 = 0 y se hallan los valores de las variables básicas resolviendo las ecuaciones (dadas por las filas), así finalmente se obtiene x1 = 0 x2 = t x3 = 15 + 3t x4 = 20 + 2t para cualquier t ≥ 0. 61 Capítulo 3. El método del símplex Puede comprobarse que estos valores dan soluciones factibles, esto es satisfacen las restricciones y son ≥ 0, en las que la función objetivo z vale z = 85 - 0 + 2t = 85 + 2t Puesto que t puede ser cualquier valor positivo, es claro que z no puede tomar un valor máximo. Se anota el criterio de divergencia Si algún costo reducido es > 0 y la variable asociada tiene coeficientes ≤ 0 en todas las restricciones, entonces la fun- ción objetivo no tiene valor máximo. Ejemplo 3. Cambio de base. Criterio de la razón mínima Sea el problema Maximizar  z = x + 30y - u + 5v con restricciones  z = x + 3y + u = 15 x + 5y + v = 20 En este ejemplo se verá que no se cumple ninguno de los criterios de máximo ni de divergencia. Entonces se elegirá una variable no básica para que reemplace a una variable básica, de modo que la función obje- tivo en la nueva solución básica factible tenga un valor mayor o igual que en la solución básica actual. Solución Usando las variables básicas u, v, la tabla del problema es var. bás x y u v b u 3 3 1 0 15 v 1 5 0 1 20 c 1 30 -1 5 0 c' -1 8 0 0 -115 No se cumple la condición de máximo porque hay un costo posi- tivo, el coeficiente 8 de la variable y; tampoco se cumple el criterio de 62 Maynard Kong divergencia pues no son ≤ 0 los elementos de la columna de la variable y, que es la única con costo reducido >0. El procedimiento para cambiar una variable no básica por una básica es el siguiente. Puede ingresar al conjunto de variables básicas cualquier variable (no básica) cuyo costo reducido es positivo; en este caso, la variable y. Y debe salir una de las variables básicas u o v. Si y se vuelve una variable básica la columna de sus coeficientes, debe ser una columna unitaria, con un elemento 1 y los otros iguales a cero. A fin de determinar cuál de las variables u o v es la adecuada para que salga del conjunto de variables básicas, se divide cada fila entre el respectivo coeficiente de y, para tener coeficientes iguales a 1: x y u v b u 1 1 1/3 0 15/3 = 5 ← dividiendo entre 3 v 1/5 1 0 1/5 20/5 = 4 ← dividiendo entre 5 y luego hay que restar una fila de la otra, para anular el otro elemento de la columna de y. No obstante, se ve inmediatamente que no se debe restar la fila 1 a la fila 2, pues de lo contrario resultaría el término constante 4-5 = -1, que sería el valor de una variable no negativa. Así, se debe seleccionar la fila 2 pues tiene el menor valor 4, o mínimo cociente, de manera que al restarla a la fila 1, todos los términos cons- tantes sigan siendo no negativos. La selección de la fila 2 indica que sale la variable básica actual v, y que en su lugar entra la variable y. Los cálculos son: var. bás x y u v b razón u 3 3 1 0 15 15/3 = 5 v 1 5 0 1 20 20/5 = 4 ← min, sale v c' -1 8 0 0 -115 ↑ entra variable y y expresando la tabla respecto de las variables básicas u, y 63 Capítulo 3. El método del símplex var. bás x y u v b u 12/5 0 1 -3/5 3 y 1/5 1 0 1/5 4 c' -17/5 0 0 -8/5 -115 -8(4) = -157 dividiendo entre 5 la fila 2, y anulando los otros elementos de la columna de y, se obtienen los nuevos costos reducidos, relativos al nuevo con- junto de variables, y el valor constante -157. La nueva tabla muestra todos los costos reducidos ≤ 0, y por lo tanto se cumple el criterio de máximo. Luego, el máximo de z es 157 y se obtiene en u = 3, y = 4, y las otras variables con valor cero. Ahora establecemos el Cambio de base y criterio de la razón mínima. Caso máximo Se aplica cuando todos los costos reducidos positivos tienen al menos un elemento positivo en la columna de estos. Sea c'j > 0 un costo reducido positivo y Criterio de la razón mínima mínimo de los valores , con 0i i j i j bR a a = > que se obtienen dividiendo cada término constante bi entre el elemento ai j > 0 de la columna de x en la fila i (se omiten los cocientes que corres- ponden a valores negativos o nulos de los ai j). Cambio de variable básica Si i' es la fila donde se obtienen la razón mínima R, entonces entra la variable xj al conjunto de variables básicas y sale la variable básica xj' . Además, el valor de z en la nueva solución básica factible es z0 + c'j R, esto tiene el incremento c'j R. 64 Maynard Kong 3.2 Forma tabular del problema estándar El método del símplex opera directamente con la tabla formada por los coeficientes y datos constantes del problema. Sea z = c1x1 + ... + cj  xj + ... + cn xn sujeto a las restricciones a11x1 + ... + a1 j + ... + a1n xn = b1 ... ai1x1 + ... + aij  xj + ... + ain xx = b1 ecuación i ... am1x1 + ... + amj  xj + ... + amn xx = bm y todas las variables no negativas y variables básicas x'1, ..., x'm que dan una solución factible. Este problema se representa mediante la tabla: ↓ columna de variable xj var. bás x1 ... xj ... xn b x'1 a11 ... a1j ... a1,n b1 ... x'i ai1 ... aij ... ai,n bi fila i (ecuación i) ... x'm am1 ... amj ... am,n bm c c1 ... cj ... cn 0 ← fila de costos ecuación de z-0 c' c'1 ... c'j ... c'n -z0 ← fila de costos reducidos ecuación de z-z0 en donde • la fila i se forma con los coeficientes y término constante de la ecuación i, 65 Capítulo 3. El método del símplex • la fila de costos corresponde a los coeficientes de la función z, • la columna de datos que corresponde a la variable básica x'i es unitaria, es decir, todos los valores son ceros excepto 1 en esa fila, • los costos reducidos, relativos a las variables básicas, se obtienen anulando los costos correspondientes a las columnas de cada variable básica: se suma -(costo de x'i) por la fila i a la fila de costos, i = 1, ..., m, • la solución básica factible es x'i = bi, para i = 1, ..., m y xj = 0, en las otras variables, • z0 es el valor de la función objetivo en la solución básica. La fila de costos reducidos representa la ecuación c'1x1 + c'2x2 + ... + c'nxn = z - z0 Expresión de la función objetivo mediante costos reducidos La función objetivo z es igual a la suma de los productos de los costos reducidos por las variables no básicas más el valor de la función en la solución básica factible: z = c'1x1 + c'2x2 + ... + cnx'n = z0 en donde c' son los costos reducidos y z es el valor en la solución básica factible. Nota 1. Debe tenerse presente que la representación dada depende del conjunto de variables básicas seleccionado, y por lo tanto, en general ha de ser distinta para otro conjunto de variables básicas. 2. Los costos reducidos asociados a las variables básicas tienen valor cero, por lo que la suma contiene solo los términos de las varia- bles no básicas. 66 Maynard Kong 3.3 Criterios del símplex. Caso máximo Criterio de máximo Si todos los costos reducidos, relativos a un conjunto de variables bási- cas, son no negativos: c'i ≤ 0, para  j = 1, 2, ..., n, entonces el valor máximo de la función objetivo es z0 y una solución óptima es la solución básica factible de las variables básicas. Prueba Se tiene z = c'1x1 + c'2x2 + ... + cnx'n = z0. De las condiciones c'1 ≤ 0, ..., c'n ≤ 0, y todas las variables x1 ≥ 0, ..., x'n ≥ 0 se concluye que la suma s = c'1x1 + ... + c'nxn es menor que o igual a cero y por lo tanto z = s + z0 ≤ z0 = valor de z en la solución básica. Esto demuestra que zMax = z0. Criterio de divergencia Si algún costo reducido es positivo y son no negativos todos los coefi- cientes de la columna de ese costo, entonces el problema no tiene valor máximo. De un modo más preciso, si existe c'i > 0, coeficiente reducido de la variable xj y aij ≤ 0, para todos los coeficientes de la variable xj entonces la función objetivo crece indefinidamente sobre la región fac- tible y por lo tanto no tiene máximo. Cambio de base y criterio de la razón mínima Se aplica cuando todos los costos reducidos positivos tienen al menos un elemento positivo en la columna de estos. 67 Capítulo 3. El método del símplex Sea c'i > 0 un costo reducido positivo. Entonces entra la variable xj al conjunto de variables básicas y sale la variable básica xi cuya razón i ij bR a = es mínima. Además, el valor de z en la nueva solución básica es z'0 = z0 + c'j R, esto es, tiene el incremento c'j R (≥ 0). 3.4 Problema de minimización El método del símplex se aplica de igual modo a problemas de mini- mización. Esto puede hacerse de dos maneras: 1) Convirtiendo el problema de minimización en uno de maximi- zación: Min z = - Max (- z) de modo que se resuelve el problema Maximizar (-z) con las res- tricciones dadas, y una vez que se obtiene el valor máximo, hay que cambiarle de signo para obtener el valor mínimo de z. En este caso, el mínimo es precisamente el valor de la esquina inferior izquierda de la tabla final. 2) Directamente con la función objetivo z, en cuyo caso se utilizan los criterios del símplex para problemas de minimización: Criterio de mínimo Si todos los costos reducidos son c'j ≥ 0, entonces se obtiene el valor mínimo de z . Criterio de divergencia (caso mínimo) Si existe un costo reducido negativo c'j < 0, y la columna de la variable xj tiene todos los elementos ≤ 0, entonces no existe valor mínimo, en efecto, en este caso la función z toma valores nega- tivos arbitrarios. 68 Maynard Kong Cambio de base Se aplica cuando todos los costos reducidos < 0 tienen al menos un elemento ≥ 0 en su respectiva columna. Sea c'j < 0. Entonces entra la variable xj y sale una variable xi cuya razón sea mínima como en el problema de maximización. Los siguientes ejemplos ilustran los dos métodos para resolver pro- blemas de minimización. Ejemplo 1 Minimizar  z = -4x + 2y sujeto a -x + 3y ≤ 14 4x - y ≤ 10 x,y no negativas transformando el problema en uno de maximización. Solución Agregando variables de holgura u, v a las restricciones para expresar el problema en forma estándar, las restricciones son: -x + 3y + u = 14 4x - y + v = 10 todas las variables no negativas. Usando Min z = -4x +2y = - Max z' = 4x - 2y se resuelve el pro- blema de maximizar la función objetivo z' y en donde u, v son variables básicas. La tabla inicial v.b x y u v b u -1 3 1 0 14 v 4 -1 0 1 10 razón = 10/4 = 2.5 ← sale v c' 4 -2 0 0 0 ← costos de z' ↑ entra x 69 Capítulo 3. El método del símplex Puesto que el costo reducido de x es 4 > 0, entra la variable x al con- junto de variables básicas, y por el criterio de la razón mínima sale v. Así, la fila pivote es la segunda fila y el elemento 4 es el pivote para actualizar la tabla. Dividiendo la fila 2 entre 4, sumando la fila 2 a la fila 1 y restando 4 veces la fila 2 a la fila de c', resulta v.b x y u v b u 0 3.25 1 0.25 12.5 x 1 -0.25 0 0.25 2.5 c' 0 -1 0 -1 -10 Puesto que todos los costos reducidos son ≤ 0, tiene valor máximo 10 y se obtiene en x = 2.50, y = 0. Por lo tanto, el valor mínimo de z es -10, en x = 2.5, y = 0. Ejemplo 2 Minimizar  z = -4x + 2y sujeto a -x +3y ≤ 14 4x - y ≤ 10 x, y no negativas usando los criterios del símplex para minimización. Solución La tabla inicial es v.b x y u v b u -1 3 1 0 14 v 4 -1 0 1 10 razón = 10/4 = 2.5 ← sale v c -4 2 0 0 0 ← costos de z ↑ entra x No se cumple el criterio de mínimo: todos los costos reducidos son ≥ 0; ni el criterio de divergencia para el caso mínimo: hay un costo reducido negativo con los elementos de su columna ≤ 0. Entonces se procede al cambio de variable básica. 70 Maynard Kong Puesto que el costo reducido de x es -4< 0, entra la variable x al conjunto de variables básicas, y por el criterio de la razón mínima sale v. Así, la fila pivote es la segunda fila y el elemento 4 es el pivote para actualizar la tabla. Dividiendo la fila 2 entre 4, sumando la fila 2 a la fila 1 y sumando 4 veces la fila 2 a la fila de c', resulta v.b x y u v b u 0 3.25 1 0.25 16.5 x 1 -0.25 0 0.25 2.5 c' 0 1 0 1 10 Puesto que todos los costos reducidos son ≥ 0 se cumple el criterio de mínimo, y por lo tanto, z tiene valor mínimo -10, en x =2.50, y=0. 3.5 Problemas propuestos Problema 1 Aplicando el método del símplex resuelva Max z = x1 + x2 - 6x3 + x4 + x5 sujeto a x1 + 2x2 - x3 + x4 = 80 -2x1 + 4x2 - 3x3 + x5 = 120 todas las variables no negativas. Observe que x4, x5 son variables básicas. Respuesta Max z = 360 Una solución óptima es x1 = 80, x5 = 280, x2 = x3 = x4 = 0. Problema 2 Resuelva Max z = x1 + x2 - 6x3 sujeto a 3x1 + 2x2 - x3 ≤ 80 -2x1 + 4x2 - 3x3 ≤ 120 71 Capítulo 3. El método del símplex Agregue variables de holgura a cada restricción y úselas como varia- bles básicas. Respuesta Max = 37.50 Una solución óptima es x1 = 5, x2 = 32.50, x3 = 0. Problema 3 Resuelva el problema Max z = x + 2y sujeto a   x - 2y ≤ 30     - x + y ≤ 20 2x + 4y ≤ 50 x,y no negativas. Respuesta Max z = 25. Una solución óptima es y = 12.50, x = 0. Problema 4 Resuelva el problema Min z = x - 2y + 100 sujeto a   x - 2y ≤ 30 - x + y ≤ 20    2x + y ≤ 50 x,y no negativas. Respuesta Min z = 50. Una solución óptima es x = 10, y = 30. 72 Maynard Kong Problema 5 Resuelva el problema Maximizar z = 2x + 3y + 4u + v sujeto a 2x + 2y + 3u + v = 100; todas las variables no negativas. Indicación: Use v como variable básica. Respuesta Max z = 150, en y = 50, y cero para las otras variables. Problema 6 Encuentre el valor máximo de la función z = 2x + 3y + 4u + v sujeto a las restricciones 2x + 2y + 8u + v = 100; x, u, v no negativas la variable y ≤ 0. Respuesta Max z = 100, en x = 50, las otras variables valen cero. Capítulo 4 Método del símplex: variables artificiales. Convergencia del algoritmo 4.1 Variables artificiales Para aplicar el método del símplex es preciso que el problema dado en forma estándar tenga un conjunto inicial de variables básicas, que por lo general no es posible determinar fácilmente. No obstante, el mismo método permite encontrar variables básicas del problema, cuando existan. En efecto, el problema se modifica mediante la incorporación de variables artificiales, que forman inmediatamente un conjunto de variables básicas, y luego por el método del símplex estas se reemplazan o cambian por variables básicas del problema original. Los dos ejemplos siguientes ilustran el uso de variables artificiales y muestran la resolución de los problemas de programación lineal por la técnica M y el método de dos fases. Ejemplo. Técnica M Aplicando la técnica M resuelva el problema Maximizar z = 4x + 2y - u + 3v sujeto a 2x + 5y + 4u + 5v = 240 -x + 5y - 3u + 2v = 60 todas las variables no negativas. 74 Maynard Kong Solución Paso 1. Se agregan variables artificiales A1, A2 a las restricciones 2x + 5y + 4u + 5v + A1 = 240 -x + 5y - 3u + 2v + A2 = 60 todas las variables no negativas, incluyendo las variables arti- ficiales. Paso 2. Se construye una nueva función objetivo z' restándole a z los términos M veces A1 y M veces A2, uno por cada variable artificial añadida: z' = 4x + 2y - u + 3v - MA1 - MA2 en donde M es una constante positiva muy grande. El problema ahora consiste en maximizar z' sujeto a las restricciones del paso 1, y se puede aplicar el método del sím- plex pues A1 y A2 son variables básicas, con valores A1=240 y A2=60. La elección del valor de M se hace a fin de lograr que las variables del problema original se vuelvan básicas en lugar de las variables artificiales. Paso 3. Se aplica el método del símplex utilizando a las variables arti- ficiales como variables básicas. La solución del problema modificado proporciona también la solución del problema inicial pues: 1) si existe máximo de z', y no contiene a la constante M, esto es, las variables artificiales han sido eliminadas del conjunto de variables básicas o anuladas, entonces máximo de z = máximo de z' 2) de lo contrario, la función z no tiene valor máximo 75 Capítulo 4. Método del símplex: variables artificiales Aplicando el método del símplex tenemos la tabla: var. bás x y u v A1 A2 b razón A1 2 5 4 5 1 0 240 240/2 = 120* A2 -1 5 -3 2 0 1 60 - c 4 2 -1 3 -M -M 0 c' (4 + M) (2 + 10M) (-1 + M) (3 + 7M) 0 0 300M ↑> 0, entra la variable x en donde los costos reducidos se obtienen sumando a la fila c de costos M veces la fila 1 y M veces la fila 2, para que las variables básicas A1 y A2 tengan costos reducidos nulos; por ejemplo, el costo reducido de la variable u es 1 + 4M -3M = -1 + M Se observa que no se cumple el criterio de máximo (todos los costos reducidos deben ser ≤ 0), ni tampoco se cumple el criterio de diver- gencia. El costo reducido de x es 4+M, que es positivo, por lo tanto entra la variable x al conjunto de variables básicas, y sale la variable A1, pues tiene la razón mínima 120. Para abreviar los cálculos, cada vez que sale una variable artificial —ya tiene valor cero— se suprime la columna de esta. La tabla resultante es: var.bás x y u v A2 b razón x 1 2.5 2 2.5 0 120 120/2.5 = 48 A2 0 7.5 -1 4.5 1 180 180/7.5 = 24* c' (4 + M) (2 + 10M) (-1 + M) (3 + 7M) 0 300M c'' 0 (-8 + 7.5M) (-9-M) (-7-4.5M) 0 -480 + 180M en donde la nueva fila de costos reducidos c'' se obtiene anulando el costo de la variable x: fila c''= fila c' menos (4+M) veces la fila 1; por ejemplo, el costo reducido de y es (2 + 10M) - (4 + M) por 2.5 = 2 + 10M - 10 - 2.5M = -8 + 7.5M. 76 Maynard Kong Puesto que la constante M puede hacerse tan grande como se desee, los costos reducidos (-8 +7.5M), (-9-M) y (-7+4.5M) son positivo, negativo y positivo, respectivamente. Elegimos el primer costo reducido positivo y por lo tanto entra la variable y, y sale la variable A2, que tiene la razón mínima. Luego eliminando la columna de A2 y simplificando resulta la siguiente tabla var.bás x y u v b x 1 0 7/3 4 60 y 0 1 -2/15 9/15 24 c' 0 (-8+7.5M) (-9-M) (-7+4.5M) -480+180M c'' 0 0 -151/15 -63/15 -288 en donde la c'' es la fila de costos reducidos respecto de las variables básicas x, y. Puesto que todos los costos reducidos son < = 0 se obtiene el valor máximo 288, y una solución óptima es x = 60, y = 24 variables artifi- ciales. Por lo tanto, se ha encontrado la solución óptima del problema dado. Ejemplo. Método de las dos fases Aplicando el método de las dos fases resuelva el problema Maximizar  z = 4x + 2y - u + 3v sujeto a 2x + 5y + 4u + 5v = 240 -x + 5y - 3u + 2v = 60 todas las variables no negativas. Solución Fase 1 Se agregan las variables artificiales A1 y A2 a cada restricción 2x + 5y + 4u + 5v + A1 = 240 -x + 5y - 3u + 2v + A2 = 60 77 Capítulo 4. Método del símplex: variables artificiales todas las variables no negativas, incluyendo las variables artificiales y se considera el problema de maximizar la función objetivo auxiliar z' = -A1 - A2 = 0x + 0y + 0u + 0v - A1 - A2 formada por la suma de los opuestos de las variables artificiales. De igual manera que en la técnica M, las variables artificiales pro- veen un conjunto inicial de variables básicas y por consiguiente se puede iniciar el método del símplex. La función z' toma valores < = 0, pues A1 y A2 son no negativas y satisface la siguiente propiedad: El valor máximo de z' es 0 si y solo sí el problema original tiene soluciones factibles. Así, cuando se aplica el método del símplex para maximizar z', si máximo de z' es cero, es decir, las variables artificiales resultan con valo- res nulos, y por lo tanto desaparecen de las restricciones. Entonces el problema tiene soluciones factibles, y con las variables básicas resul- tantes, se puede proceder a la siguiente fase para optimizar la función. De lo contrario, el problema no tiene valor máximo. Fase 2 Se aplica solo si en la fase 1 se obtiene el valor óptimo 0. Se halla el valor máximo de la función objetivo original usando la tabla de la fase 1, sin las columnas de las variables artificiales. Los cálculos correspondientes a cada fase son los siguientes Fase 1 var. bás x y u v A1 A2 b razón A1 2 5 4 5 1 0 240 240/2 = 120* A2 -1 5 -3 2 0 1 60 - c 0 0 0 0 -1 -1 0 c' 1 10 1 7 0 0 300 ↑entra x 78 Maynard Kong La fila de costos c representa la función objetivo auxiliar a maximizar z' = -A1 - A2 = 0x + 0y + 0u + 0v - A1 - A2 y la fila c' de costos reducidos resulta de anular los costos de las variables básicas A1 y A2. Puesto que el costo reducido de la variable x es positivo, entra esta variable al conjunto de variables básicas y sale la variable A1, pues tiene razón mínima. La tabla correspondiente es var. bás x y u v A1 A2 b razón x 1 2.5 2 2.5 0.5 0 120 48 A2 0 7.5 -1 4.5 0.5 1 180 24* c' 0 7.5 -1 4.5 -0.5 0 180 ↑entra y Similarmente entra la variable y y sale la variable A2 y resulta la tabla var. bás x y u v A1 A2 b x 1 0 7/3 1 1/3 -1/3 60 y 0 1 -2/15 9/15 1/15 2/15 24 c' 0 0 -2 0 -1 -1 0 En este paso, se obtiene el valor máximo 0, ya que todos los costos reducidos son ≤ 0, y por lo tanto, se procede a la fase 2. Se observa que las variables básicas son x, y. Fase 2 Se toma la tabla anterior, excluyendo las columnas de las variables artificiales y se procede a maximizar la función objetivo del problema inicial z = 4x + 2y - u + 3u var. bás x y u v b x 1 0 7/3 1 60 y 0 1 -2/5 9/15 24 c 4 2 -1 3 0 c' 0 0 -16/5 -8/5 -288 = -4*60 - 2*24 79 Capítulo 4. Método del símplex: variables artificiales en donde se han calculado los costos reducidos respecto de las variables básicas x,y. Puesto que todos los costos reducidos son < = 0, se cumple el crite- rio del máximo, y se obtiene zMax = 288, en x=60, y=24. Se reitera la condición del método de las dos fases. Si en la fase 1 se obtiene un valor máximo distinto de cero, o no existe, entonces el problema original no tiene valor máximo. Empleo de variables artificiales La técnica M se aplica solo cuando el método del símplex se lleva a cabo mediante cálculos manuales, pues por simple inspección se determina el signo de los costos reducidos. Cuando se implementa el método mediante programas por computadoras es preferible usar el método de las dos fases. No obstante que la inclusión de variables artificiales puede hacerse de un modo general, es decir simplemente agregar una variable artificial en cada restricción de igualdad, en los casos de cálculos manuales es conveniente añadir el menor número de ellas, teniendo presente que el propósito es disponer desde el comienzo de un conjunto de variables básicas. Así, se puede recomendar: a) usar como variable básica una variable que aparezca con coefi- ciente 1 en una restricción de igualdad y no se encuentre en ninguna de las otras restricciones; b) tomar como variable básica una variable de holgura por defecto, que corresponde a una restricción de desigualdad ≤; y c) agregar variables artificiales en las restantes restricciones. Por ejemplo, si el problema es maximizar z = 2x - 4y + 5u + 3v - 6w sujeto a     4x + 3y + v = 60     3x - 2y + u + 6w ≤ 30 - x + 2y - 3u + 2w = 50 80 Maynard Kong todas las variables no negativas entonces se puede tomar como variables básicas • en la primera restricción: la variable v, pues aparece solo en esta restricción y con coeficiente 1, • en la segunda restricción: la variable de holgura H2 • en la tercera restricción: la variable artificial A3 Y las restricciones se expresan mediante          4x + 3y + v = 60   3x - 2y + u + 6w + H2 = 30 - x + 2y - 3u + 2w + A3 = 50 con variables básicas v, H2 y A3. Si se aplica la técnica M, la función objetivo a maximizar es z' = 2x - 4y + 5u + 3v - 6w - MA3 en donde se resta el término MA3 que corresponde a la única variable artificial presente. Y si se sigue el método de las dos fases, en la fase 1 ha de maximi- zarse la función auxiliar z' = -A3 = 0x + 0y + 0u + 0v - 0w - 1A3 4.2 Problemas propuestos Problema 1 Usando la técnica M resuelva el problema: Maximizar z = 3x + y + u - 6v sujeto a x + 2y + 4u + 10v = 50;   3x - y + 5u - 3v = 10; todas las variables no negativas. 81 Capítulo 4. Método del símplex: variables artificiales Respuesta zMax = 50; una solución óptima es x = 20, y=10, u=v=0 Problema 2 Aplique la técnica M para resolver el problema Maximizar w = x + y - 2u + 5v sujeto a    u + 4v ≥ 68; 8x + 5y + 2v ≤ 30; todas las variables no negativas. Indicación El problema a resolver puede ser escrito así w = x + y - 2u + 5v - MA1 sujeto a   u + 4v - H1 + A1 = 68 8x + 5y + 2v + H2 = 30, en donde A1 y H2 son variables básicas, A1 es una variable artificial y H2 es una variable de holgura (por defecto). Respuesta ZMax =59. Una solución óptima es x=y=0, u=9, v=15. Problema 3 Resuelva el problema 1 usando el método de las dos fases. Problema 4 Aplique el método de las fases para resolver el problema 2. Problema 5 Resuelva el problema minimizar w = x1 + 2x2 - 3x3 + 4x4 sujeto a     4x1 + 6x2 - 4x3 ≥ 100 3x1 + x2 + 4x3 + x4 ≤ 40 todas las variables negativas 82 Maynard Kong a) Por la técnica M b) Aplicando el método de las dos fases. Indicación Convierta el problema en uno de maximización - maximizar w1 = -x1 - 2x2 + 3x3 - 4x4 y considere las restricciones     4x1 + 6x2 - 4x3 - H1 = 100 3x1 + x2 + 4x3 + x4 + H2 = 40 Puede tomarse como variables básicas iniciales: una variable artifi- cial A1 asociada a la primera restricción y la variable de holgura H2 (por defecto) de la segunda restricción. Respuesta El valor mínimo de w es 25. Una solución óptima es x2=20, x3=5, y cero las otras variables. Problema 6 Sea el problema Maximizar  z = 20x + 10y - u sujeto a   2x - 4y + u = 60 -3x + y - 3u = 20 todas las variables no negativas a) Sume miembro a miembro las restricciones y compruebe que no existen soluciones factibles (en particular, el problema no tiene máximo). b) Compruebe que el problema no tiene soluciones factibles calcu- lando el valor máximo de z' = - A1 - A2 (la función auxiliar de la fase 1) sujeta a las condiciones   2x - 4y + u + A1 = 60 -3x + y - 3u + A2 = 20 en donde A1 y A2 son variables artificiales. 83 Capítulo 4. Método del símplex: variables artificiales 4.3 Convergencia del algoritmo del símplex En esta sección se presenta un análisis simplificado de la propiedad de convergencia del algoritmo del símplex. Mediante esta propiedad se asegura que el algoritmo termina en un número finito de pasos cuando se aplica a cualquier problema de programación lineal estándar. Se han elaborado ejemplos en los cuales en la aplicación del método del símplex una tabla vuelve a aparecer después de algunos pasos, y por lo tanto hay un ciclo o grupo de tablas que se repiten indefinidamente, impidiendo que se obtenga la solución del problema. El concepto de ciclo se explica a través de un ejemplo algo extenso por los cálculos. Luego se mencionan las condiciones en las que pueden ocurrir los ciclos. Y finalmente se describen dos métodos que garanti- zan la convergencia del algoritmo del símplex: la regla de Blands y el método de perturbación. Uno de los primeros ejemplos de problemas de programación lineal con ciclos fue ofrecido por E. Beale. No obstante, a continuación se mos- trará más bien uno tomado de un curso de la universidad de Toronto (http://www.math.toronto.edu/mpugh/Teaching/APM236_04/bland). Ejemplo de un ciclo Resolver el problema maximizar z = -13.25x1 + 14.50x4 - 98x5 - 6.75x6 sujeto a   2.75x1 + x2 + 0.50x4 - 4x5 - 0.75x6 = 0   0.25x1 + x3 + 0.50x4 - 2x5 - 0.25x6 = 0 -2.75x1 - 0.50x4 + 4x5 + 0.75x6 + x7 = 0 todas las variables no negativas. x2, x3  y  x6 forman un conjunto inicial de variables básicas. A continuación se aplica el método del símplex, haciendo elecciones sobre las variables de entrada y salida, y se obtiene la sucesión de tablas T1, T2, T3, T4, T5, T6, T7 = T1, T2, T3, ..., 84 Maynard Kong y se encuentra que la tabla T7 es precisamente la tabla inicial T1, de modo que el grupo de tablas T1-T6 forma un ciclo, esto es se repite indefinidamente. Se empieza con la tabla: T1 variables básicas x2, x3, x7 v.b x1 x2 x3 x4 x5 x6 x7 b x2 2.75 1 0 0.50 -4 -0.75 0 0 x3 0.25 0 1 0.50 -2 -0.25 0 0 x7 -2.75 0 0 -0.50 4 0.75 1 1 c' -13.25 0 0 14.50 -98 -6.75 0 0 La única variable que puede entrar es x4. Y por la razón mínima pueden salir x2, x3. Se elige x2. La siguiente tabla es T2 variables básicas x4, x3, x7 v.b x1 x2 x3 x4 x5 x6 x7 b x4 5.50 2 0 1 -8 -1.50 0 0 x3 -2.50 -1 1 0 2 0.50 0 0 x7 0 1 0 0 0 0 1 1 c' -93 -29 0 0 18 15 0 0 Hay dos posibles variables que pueden entrar x5 o x6. Se elige x5. La única posible variable que puede salir es x3. La tabla resultante es T3 variables básicas x4, x5, x7 v.b x1 x2 x3 x4 x5 x6 x7 b x4 -4.5 -2 4 1 0 0.50 0 0 x5 -1.25 -0.5 0.5 0 1 0.25 0 0 x7 0 1 0 0 0 0 1 1 c' -70.50 -20 -9 0 18 10.50 0 0 La única variable que puede entrar es x6. Y pueden salir x4 o x5. Se elige x4. 85 Capítulo 4. Método del símplex: variables artificiales La siguiente tabla es T4 variables básicas x6, x5, x7 v.b x1 x2 x3 x4 x5 x6 x7 b x6 -9 -4 8 2 0 1 0 0 x5 1 0.5 -1.5 -0.5 1 0 0 0 x7 0 1 0 0 0 0 1 1 c' 24 22 -93 -21 0 0 0 0 Ahora pueden entrar x1 o x2. Se elige x1. Y puede salir solo la variable x5. La tabla resultante es T5 variables básicas x6, x1, x7 v.b x1 x2 x3 x4 x5 x6 x7 b x6 0 0.5 -0.5 -2.5 9 1 0 0 x1 1 0.5 -1.5 -0.5 1 0 0 0 x7 0 1 0 0 0 0 1 1 c' 0 10 -57 -9 -24 0 0 0 La única variable que puede entrar es x2. Y pueden salir x6 o x1. Se elige x6. La siguiente tabla es T6 variables básicas x2, x1, x7 v.b x1 x2 x3 x4 x5 x6 x7 b x2 0 1 -11 -5 18 2 0 0 x1 1 0 4 2 -8 -1 0 0 x7 0 0 11 5 -18 -2 1 1 c' 0 0 53 41 -204 -20 0 0 Hay dos variables que pueden ingresar x3 y x4. Se elige x3. Entonces solo puede salir la variable x1. Y la siguiente tabla es T7 variables básicas x2, x3, x7 86 Maynard Kong v.b x1 x2 x3 x4 x5 x6 x7 b x2 2.75 1 0 0.5 -4 0.75 0 0 x3 0.25 0 1 0.5 -2 -0.25 0 0 x7 -2.75 0 0 -0.5 4 0.75 1 1 c' -13.25 0 0 14.5 -98 -6.75 0 0 Pero T7 es la tabla inicial tabla T1 y por lo tanto el algoritmo no termina. 4.4 Métodos para evitar ciclos: regla de Blands y perturbación ¿Cuándo puede ocurrir un ciclo? Puede ocurrir un ciclo solo cuando son iguales a cero las razones míni- mas de cambio de las tablas o la función objetivo no cambia su valor -se dice que las soluciones básicas son degeneradas, pues algunas variables básicas valen cero. Dicho de otra manera, en un ciclo todas las tablas tienen razón de cambio igual a cero y la función objetivo permanece constante. Esto es una consecuencia del siguiente hecho: Si T es una tabla con razón de cambio mínima R>0, entonces la tabla T no puede repetirse o aparecer otra vez en los siguientes pasos del método del símplex. En efecto, recordando (Sección 3.1) y asumiendo el caso de maxi- mización, si z0 es el valor de la función objetivo z en la tabla actual T y se produce un cambio de variable básica, en la tabla siguiente T' el valor de la función objetivo es z'0 = z0 + c'j  R donde c' > 0 es el costo reducido de la variable entrante y R ≥ 0 es la razón mínima. De aquí se deduce que z0 = z'0, si R = 0, o z0 < z'0, si R > 0 87 Capítulo 4. Método del símplex: variables artificiales Esto significa que los valores de la función objetivo en las tablas siguientes se mantienen, cuando la razón mínima es cero, o crecen, cuando la razón mínima es mayor que cero. Y en consecuencia, si R>0, la tabla T (y las anteriores) no puede aparecer en las iteraciones siguientes. Si se evitan los ciclos, ¿el algoritmo necesariamente termina? Sí, porque el número posible de tablas distintas es un número finito determinado M, y si se obvian los ciclos, ninguna tabla puede repetirse. Por lo tanto, el proceso debe terminar a lo sumo en M pasos, cum- pliéndose necesariamente uno de los criterios: el de óptimo o el de divergencia. El valor de M es el número combinatorio ( ) ! ! ! n n m m n n   =   - en donde n = número de variables del problema y m= número de variables básicas. Para hacer evidente esto, basta observar que cada tabla está determi- nada por su respectivo conjunto de variables básicas, de manera que a lo sumo habrá tantas tablas como subconjuntos de m variables tomadas de n variables. En el ejemplo desarrollado en la sección 3.3 se tiene n=7 y m=3, de modo que las posibles tablas son: T1 variables básicas {x1, x2, x3} .... TM variables básicas {x6, x7, x8} 7 7 6 5 35 3 3 2 1 M   × × = = =   × × es decir, en este caso a lo sumo se obtienen 35 tablas distintas. 88 Maynard Kong ¿Cómo se evitan los ciclos en el método del símplex? Se describen dos métodos. Uno, bastante reciente debido a Blands, por su uso sencillo en programas por computadoras, y otro, de carácter más analítico, al que se llama método de perturbación. Regla de (los menores índices dobles de) Blands Se asume que el problema es de maximización y que las variables del problema estándar están referidas por subíndices; por ejemplo, los subíndices pueden ser los números de las posiciones de las columnas de las variables en la tabla inicial. Puesto que el propósito es evitar los ciclos, por razones prácticas se recomienda aplicar la regla cuando en una tabla, en la que el algoritmo no termina, todos los costos reducidos positivos c'j>0 tienen razón mínima igual a cero, En este caso: 1) se elige como variable de entrada -al conjunto de variables bási- cas- la variable xj que tiene el menor subíndice j de los c'j > 0 y 2) y si, respecto de la columna j, las variables básicas con razón mínima 0 son xi1, ..., xim entonces sale la variable xis que tiene el menor subíndice is Nótese que en 1) y 2) se eligen las variables según los dos subíndices menores. Solución del ejemplo 4.3 usando la regla de Blands Observando que en tablas calculadas las razones mínimas siempre son cero se revisan los cálculos efectuados, pero esta vez se aplica la regla de Blands. Las variables seleccionadas para entrar y salir se indican con un * 1) Tabla T1 variables básicas x2, x3, x7 variables entrantes: x4* entra x4, elección única variables de salida: x2*, x3 sale x2, tiene menor subíndice 2<3. 89 Capítulo 4. Método del símplex: variables artificiales 2) Tabla T2 variables básicas x4, x3, x7 variables entrantes: x5*, x6 entra x5, tiene menor subíndice variables de salida: x3* sale x3, elección única 3) Tabla T3 variables básicas x4, x5, x7 variables entrantes: x6* entra x6, elección única variables de salida: x4*, x5 sale x4, subíndice menor 4) Tabla T4 variables básicas x6, x5, x7 variables entrantes: x1*, x2 entra x1, subíndice menor variables de salida: x5* sale x5, elección única 5) Tabla T5 variables básicas x6, x1, x7 variables entrantes: x2* entra x2, elección única variables de salida: x6, x1* sale x1, menor subíndice Nótese que en las tablas T1-T4 las selecciones de las variables de entrada y salida aplicando la regla de Blands coinciden con las realiza- das antes cuando se encontró el ciclo. Estas selecciones corresponden a escoger de modo simple como variable de entrada con costo reducido positivo a la que está en la columna de más a la izquierda, y como varia- ble de salida, respecto de esta columna, a la variable básica con razón mínima igual a cero que se encuentra en la fila de más arriba Repetimos la tabla T5 T5 variables básicas x6, x1, x7 v.b x1 x2 x3 x4 x5 x6 x7 b x6 0 0.5 -0.5 -2.5 9 1 0 0 x1 1 0.5 -1.5 -0.5 1 0 0 0 x7 0 1 0 0 0 0 1 1 c' 0 10 -57 -9 -24 0 0 0 La única variable que puede entrar es x2. Y pueden salir x6 o x1. En el caso que condujo al ciclo, se eligió como variable de salida x6. No obstante, si se aplica la regla de Blands debe salir x1, pues es la variable que tiene menor subíndice 1<6. 90 Maynard Kong Se muestran las siguientes tablas. Tabla T'6 variables básicas x6, x2, x7 v.b x1 x2 x3 x4 x5 x6 x7 b x6 -1 0 -4 -2 8 1 0 0 x2 2 1 -3 -1 2 0 0 0 x7 -2 0 3 1 -2 0 1 1 c' -20 0 -27 1 -44 0 0 0 La única variable que puede entrar es x4. Y solo puede salir la varia- ble x7. Tabla T'7 variables básicas x6, x2, x4 v.b x1 x2 x3 x4 x5 x6 x7 b x6 -5 0 2 0 4 1 2 2 x2 0 1 0 0 0 0 1 1 x4 -2 0 3 1 -2 0 1 1 c' -18 0 -30 0 -42 0 -1 -1 =-z0 El algoritmo termina, pues todos los costos reducidos son ≤ 0. El valor máximo es z0 = 1, y se obtiene en x6=2, x2=1, x4=1, y las otras variables con valor igual a cero. Método de perturbación Este método consiste en «perturbar» o modificar los términos cons- tantes, lados derechos de las restricciones de igualdades, sumándoles potencias de un número positivo muy pequeño, de manera que cuando se aplica el algoritmo del símplex cualquier razón mínima resulta con valor positivo y por lo tanto la función objetivo siempre aumenta su valor (caso de maximización). Así, ninguna tabla puede repetirse y necesariamente se llega a una tabla terminal, en la cual la solución óptima se obtiene anulando o desapareciendo las cantidades añadidas. 91 Capítulo 4. Método del símplex: variables artificiales Solución del ejemplo 4.