Raúl Urbán Ruiz

Notas de clase. Método Simplex.

La programación lineal es una herramienta de la investigación de operaciones y muy útil para la toma de decisiones. Esta es una herramienta genérica que sirve para resolver problemas lineales. De acuerdo a los valores que pueden tomar las variables que intervienen en un problema de programación lineal, se utiliza, la programación lineal propiamente dicha, cuando los valores están en los números reales y la programación entera, en donde la variable asume solamente números enteros. La solución de un problema con variables enteras es mucho más complicada que un problema de números reales y no es nuestro objeto de estudio. En las empresa, muchas de las decisiones que se toman tienen están dirigidas a optimizar sus recursos, como puede ser el uso de la maquinaria, capital, materias primas, etc. Estos recursos son utilizados en la producción de bienes que a final de cuentas representan ingresos para la empresa. La Programación Lineal es una técnica matemática diseñada para asistir y a los tomadores de decisión de la empresa en la planificación y uso racional de los recursos con que cuenta. Existen muchos ejemplos exitosos en la literatura de aplicaciones de programación lineal, los ejemplos clásicos son, el problema de la dieta y el de transporte. El problema de la dieta, fue uno de los primeros problemas sobre optimización, motivado por el deseo del ejército americano de asegurar unos requerimientos nutricionales al menor coste. El problema fue analizado y resuelto por George Stigler usando la programación lineal en 1947. La formulación general de este problema es: Para que una dieta sea equilibrada deben ingerirse n elementos nutritivos básicos en cantidades mínimas b1, b2,..., bs. Estos elementos se encuentran en m alimentos. Conocemos cuál es la cantidad de cada elemento en cada unidad de cada uno de los alimentos y el coste de la unidad de cada alimento. Se debe minimizar el coste de la dieta pero cubriendo las necesidades nutritivas mínimas. Por ejemplo; Un especialista en nutrición, elabora un plan para determinado tipo de pacientes basado en tres grupos de alimentos; verduras, carne y pescado y harinas, trigo y maíz. Estos se deben combinar para que cumplan con ciertos requisitos nutritivos mínimos de proteínas y calorías de 2600 calorías y 60 g de proteína por día. El contenido de cada alimento por cada 100gr es el siguiente. Las verduras tienen 100 calorías y 2 gr de proteína, la carne y el pescado en promedio 500 calorías y 35 gr de proteína; las harinas combinadas ofrecen en promedio 120 calorías y 8 gr de proteína. Si los precios por cada 100 gr de verdura, proteína y harinas son de $ 8.0, $25.0 y $3.0 respectivamente ¿Cuál debe ser la combinación de alimentos de manera que el costo sea mínimo y se satisfagan las condiciones de nutrición por día?

1

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Podemos resumir el problema en el siguiente cuadro: Verduras Calorías Proteínas Precios por 100 gramos

100 cal 2 gr $ 8.0

Carne y pescado 500 cal 35 gr $ 25.0

Harinas 120 cal 8 gr $ 3.0

Requisitos mínimos 2600 cal 60 gr

La formulación general del Problema del transporte es que un cierto producto se elabora en varios centros, n, y en su producción intervienen los productos a1,a2,...,as. Este producto debe ser enviado a m destinos cuyo coste por envío desde cada planta a cada destino son conocidos. Además se deben enviar en cantidades b1,b2,...,bs. El objetivo es minimizar el coste total del transporte. Por ejemplo, Una empresa tiene dos plantas de producción en la ciudad de México, una en el norte y otra en el sur. El nivel de producción de la planta del sur es de 1500 unidades y la del norte de 3500. Las ventas de la empresa se distribuyen en las ciudades de Cuernavaca 850 unidades, Guadalajara 4000 unidades, Monterrey 3500 unidades. El costo de transporte se por unidad se muestra en la siguiente tabla. Planta Sur Planta Norte

Cuernavaca 30 32

Guadalajara 240 235

Monterrey 320 315

La pregunta es ¿determinar el número de unidades que debe enviar desde cada planta a cada ciudad para que los costos sean mínimos?

La programación lineal. Los problemas de programación tienen como objetivo principal la asignación óptima de los recursos con que cuenta una empresa, la mayoría de las veces muy limitados, para alcanzar objetivos específicos. Por esta razón los recursos, definidos en forma de restricciones, pueden ser de distintos orígenes. Estas van desde las restricciones de producción como las impuestas por el mercado. También, pueden ser resultado de las limitaciones de material en almacén o en reserva. Al final, el objetivo es maximizar o minimizar una función de beneficio, como podrían ser el la máxima utilidad ó el mínimo costo. Trataremos de determinar la mejor solución posible bajo ciertas restricciones, tales como el trabajo, maquinaria y la existencia de insumos necesarios para la fabricación de los productos de la empresa.

2

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

La primera fase para emprender la solución a un problema de Programación Lineal es formular y obtener el modelo. Considerada esta etapa la más importante del proceso de aplicación, en la cual se necesita definir claramente el problema y conceptualizar de una manera correcta el problema que presente el sistema sobre el cual se pretende realizar la aplicación. La etapa siguiente en el proceso es alcanzar la solución del modelo. Modelado de un programa lineal. La formulación del programa lineal es fundamental para obtener una buena solución a nuestros problemas. Este proceso comprende los siguientes pasos, 1. La formulación del problema y la identificación de las variables de decisión, las que representan el interés fundamental del problema a resolver. 2. Formular la función económica, o función objetivo. 3. Formular en forma de inecuaciones las restricciones del modelo, pueden ser de producción, de presupuesto, etc. Ejemplos. Problema de la dieta, propuesto al inicio. El especialista en nutrición desea formular una dieta basado en tres tipos de alimentos; verduras, carne y pescado, y harinas. El objetivo es encontrar la

combinación de alimentos de manera que el costo sea mínimo y se satisfagan las condiciones de nutrición por día. La formulación del programa lineal sería el siguiente Las variables de decisión son; 𝑥1 verdura, 𝑥2 proteína, 𝑥3 harinas. programa de minimización de los costos.

Se trata de un

a) Función objetivo. Donde Z es una función económica a minimizar 𝑀𝑖𝑛 𝑍 = 8𝑥1 + 25𝑥2 + 3𝑥3

b) Sujeta a las restricciones. Hipótesis de linealidad del modelo; es decir para obtener 2600 calorías diarias se requiere una combinación 100𝑥1 de verdura, 500𝑥2 calorías obtenidas de carne y pescado y 12𝑥3 de harinas de trigo y maíz. La misma consideración se hace para las proteínas. 100𝑥1 + 500𝑥2 + 12𝑥3 ≥ 2600 2𝑥1 + 35𝑥2 + 8𝑥3 ≥ 60

Restricción de calorías Restricción de proteínas

c) No negatividad de las variables 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

3

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Una organización cafetalera indígena desea comercializar 2 tipos de productos orgánicos; café y pimienta. El café orgánico cuesta $80 pesos/kilo y la pimienta $160 pesos/kilo. Para transportar los productos a la ciudad más cercana cuenta con un camión que solo puede transportar 20,000 kg y un volumen de 1200 𝑚3 . Si el café ocupa 0.025 𝑚3 y la pimienta 0.01 𝑚3 por cada kg, ¿cuántos kilos de cada producto debe cargar en el camión para maximizar su ganancia? Las variables de decisión son; 𝑥1 café y 𝑥2 pimienta. Se trata de un programa de maximizar las utilidades de la organización. De esta manera la función a maximizar es. 𝑀𝑎𝑥 𝑍 = 80𝑥1 + 160𝑥2

a) Sujeta a las restricciones. Hipótesis de linealidad del modelo; por un lado el camión solo puede transportar una combinación de 𝑥1 de café y 𝑥2 de pimienta que no deben rebasar un peso de 20,000 kg. Por otro lado, el volumen de 0.025𝑥1 de café y 0.01𝑥2 de pimienta pueden ocupar un volumen no mayor a 1200 𝑚3 . 𝑥1 + 𝑥2 ≤ 20,000 0.025𝑥1 + 0.01𝑥2 ≤ 1200

Restricción de capacidad Restricción de volumen

b) No negatividad de las variables 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Como hemos visto, un programa lineal pone en juego cuatro categorías de elementos; las actividades, las constantes económicas, las restricciones y los coeficientes técnicos. a) Las actividades son las variables de decisión del modelo en estudio. Se trata de seleccionar aquellas que correspondan a la función a optimizar. Usualmente utilizamos letras como 𝑥1 , 𝑥2 , 𝑥3 , …. O bien 𝑥, 𝑦, 𝑧, 𝑡, … b) Las constantes económicas miden el nivel de realización asociado al beneficio de cada recurso de la organización, o de la empresa. De esta manera a cada 𝑥𝑗 le asociamos un beneficio 𝑐𝑗 . c) Las restricciones del problema. Estas pueden ser de naturaleza muy diversa, dependen del problema. Son los elementos que limitan el problema, las restricciones. Estas pueden ser las limitaciones de producción, de presupuesto, etc. d) Los coeficientes técnicos, son las cantidades de cada recurso que son necesarios para producir una unidad de producto. Al recurso i y a la actividad j le corresponderá el coeficiente técnico 𝑎𝑖𝑗

4

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Si las variables son continuas y los coeficientes técnicos y económicos son independientes de los valores de las variables, el problema de programación lineal se puede presentar de la siguiente manera. Un programa lineal en la forma canónica se escribe de la siguiente manera, Maximizar sujeto a:

𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ ⋯ + 𝑐𝑛 𝑥𝑛

≤ 𝑎𝑖1 𝑥1 + 𝑎𝑖2 2𝑥2 + ⋯ ⋯ + 𝑎𝑖𝑛 𝑥𝑛 � 𝑏𝑖 ≥ 𝑥𝑗 ≥ 0

𝑖 = 1,2,3, … . , 𝑛

En términos económicos, 𝑥𝑗 𝑐𝑗

𝑎𝑖𝑗 𝑏𝑖 Z

Cantidad de producto j a producir. Beneficio asociado a una unidad de producción del producto j Cantidad del recurso i requerido para producir una unidad del producto j Cantidad del recurso i disponible. Beneficio total o función económica

Para resolver el programa lineal, deberemos buscar los valores de las variables de decisión como 𝑥1 , 𝑥2 , 𝑥3 , …., que optimizan la función económica 𝑍, o si así fuera el caso demostrar que el modelo no tiene solución. Para establecer un lenguaje común damos las siguientes definiciones; • • •

Llamaremos solución factible, cualquier grupo de valores de las variables de decisión como 𝑥1 , 𝑥2 , 𝑥3 , …. Que verifican el sistema de inecuaciones anterior. Solución óptima toda solución que optimiza la función Z. El conjunto de todas las soluciones factibles de un programa lineal le llamaremos dominio de soluciones factibles

Todo problema de programación lineal debe cumplir con lo siguiente; a) Las soluciones del problema serán, en general, números reales. Para aquellos problemas en los cuales sólo tenga sentido obtener soluciones enteras, se tendrá que aplicar los métodos de solución de la Programación Lineal Entera. b) No negatividad. Las variables de nuestro modelo tomarán siempre valores positivos, esto es muy útil para las aplicaciones económicas ya que no tiene sentido hablar de cantidades negativas de objetos físicos. c) Todas las restricciones deben formularse como ecuaciones.

5

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

d) La parte derecha de una restricción no puede ser negativa Desde el momento en que George Dantzig desarrolla el método simplex para obtener la solución a un modelo de programación lineal, éste método ha sido considerado el único método útil y aplicable a la gran mayoría de problemas de programación lineal. Sin embargo para poder alcanzar una fuerte comprensión del método simplex se hace necesario estudiar inicialmente el método de solución gráfica. Resolución gráfica de un problema de Programación Lineal

El método gráfico de resolución es útil cuando trabajamos programas lineales de dos variables. Para aquellos casos en que el número de variables del problema sea superior a dos, es complicado encontrar la solución a partir de un gráfico bidimensional y, por tanto, tendremos que usar métodos de resolución más complejos. Aun así, el método gráfico es de un gran valor pedagógico dado que nos permite vislumbrar de una forma intuitiva las ideas básicas de la Programación Lineal. Ejemplo. Una empresa electrónica fabrica dos tipos de memoria para computadora, 𝑚1 y 𝑚2 . En el proceso de producción se requiere pasar por dos máquinas distintas, A y B. La máquina A requiere de 75 minutos para la memoria 𝑚1 y 25 para la memoria 𝑚2 . La máquina B necesita de 20 y 12 minutos respectivamente. Además, por razones de mantenimiento, la máquina A solo puede trabajar 30 horas por semana y la B 13 horas. Si el beneficio por unidad de la memoria 𝑚1 es de $60 pesos y el de la memoria 𝑚2 es de $45. ¿Cuánto debemos producir de cada tipo de memoria para obtener el máximo beneficio? Para simplificar nuestro problema denotamos por 𝑥1 : el número de unidades producidas por semana de la memoria 𝑚1 y por 𝑥2 al número de memorias producidas de 𝑚2

El programa lineal será entonces; 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑧 = 60𝑥1 + 45𝑥2 Sujeto a: 75𝑥1 + 25𝑥2 ≤ 1800 20𝑥1 + 12𝑥2 ≤ 780 𝑥1, 𝑥2 ≥ 0

(30 ∗ 60) 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐴 (13 ∗ 60) 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑚á𝑞𝑢𝑖𝑛𝑎 𝐵 𝑛𝑜 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑 𝑑𝑒 𝑙𝑎𝑠 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠

Si graficamos estas dos restricciones lineales en el plano real, la intersección de estas líneas forman lo que se conoce como región factible, o poliedro convexo 1. La teoría matemática establece que, dado un problema de Programación Lineal que tenga solución, ésta vendrá dada por uno de los vértices (o puntos extremos) del polígono que 1

Un poliedro convexo es una figura geométrica en la que al trazar un segmento que une dos puntos, estos puntos están contenidos dentro del poliedro.

6

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

configura la región factible. Por tanto, será suficiente hallar las coordenadas de dichos vértices (intersecciones de rectas) y determinar (sustituyendo en la función objetivo) cuál de ellos es la solución óptima. En nuestro ejemplo, tendríamos sólo cuatro puntos candidatos a ser solución del problema (los cuatro vértices del polígono), sustituyendo sus coordenadas en la función objetivo obtenemos:

𝑍(0,0) = 0;

21 225

𝑍(24,0) = 1440; 𝑍 � 4 ,

4

� = 2846.25; 𝑍(0, 65) = 2925

Como en este caso buscábamos maximizar 𝑍(𝑋, 𝑌), concluiremos que el punto óptimo es el (0,65), dado que con él obtenemos el valor máximo de la función objetivo. Ejemplo. Una cooperativa rural produce tres tipos de muebles de madera; bancos, mesas y sillas. Cuenta con dos talleres ubicados en el norte y en el sur de la localidad donde se encuentran. En cada una de ellas produce los muebles en las siguientes cantidades por hora, Bancos Mesas Sillas

Taller norte 1 1 6

Taller sur 2 4 3

La cooperativa recibe un pedido de 90 bancos, 120 mesas y 180 trompos. El costo de operación del taller sur es de $450 pesos y del taller norte $600 pesos por hora. ¿Cuál es el programa de producción para minimizar los costos del pedido? Solución. Sean 𝑥1 y 𝑥2 el numero de horas que funcionan los talleres Norte y Sur para surtir el pedido. El programa lineal es,

7

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Minimizar sujeto a:

Solución gráfica del programa lineal.

𝑍 = 450𝑥1 + 600𝑥2 𝑥1 + 2𝑥2 ≥ 90 𝑥1 + 4𝑥2 ≥ 120 6𝑥1 + 3𝑥2 ≥ 180 𝑥1 , 𝑥2 ≥ 0

Este ejemplo de producción puede ser representado gráficamente porque no tiene más de dos variables. Antes de buscar la solución del problema, definamos en la gráfica la región y los puntos que satisfacen las cuatro restricciones. La restricción de no negatividad de las variables nos indica que esta región solo incluirá aquellos valores que sean positivos.

El beneficio para cada punto extremo, A, B y C es el siguiente; 𝐴(0,60) Los costos son 𝑍 = 450(0) + 600(60) = $36,000 𝐵(10,40) Este punto se obtiene al resolver el sistema de ecuaciones siguiente 𝑥1 + 2𝑥2 = 90 ⇒ 6𝑥1 + 3𝑥2 = 180 ⇒

𝑥1 = 90 − 2𝑥2 𝑥1 = 180 − 3𝑥2

90 − 2𝑥2 = 180 − 3𝑥2 𝑥2 = 40 y 𝑥1 = 10

Los costos son de 𝑍 = 450(10) + 600(40) = $28,500

𝐶(60,15) Para obtener este punto resolvemos el siguiente sistema de ecuaciones, 𝑥1 + 2𝑥2 = 90 ⇒ 𝑥1 + 4𝑥2 = 120 ⇒

𝑥1 = 90 − 2𝑥2 𝑥1 = 120 − 4𝑥2

90 − 2𝑥2 = 120 − 4𝑥2 𝑥2 = 15 y 𝑥1 = 60

8

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Los costos son de 𝑍 = 450(60) + 600(15) = $36,000

𝐷(120,0) 𝑍 = 450(120) = $54,000

La solución óptima es 𝒙𝟏 = 𝟏𝟎 y 𝒙𝟐 = 𝟒𝟎. El costo de producción es de $28,500

Casos especiales

Hasta ahora, los problemas resueltos gráficamente tienen una solución óptima, lo que no siempre sucede. A la hora de resolver un problema de Programación Lineal, nos podríamos encontrar con cualquiera de estas tres situaciones especiales que conviene conocer: •

•

•

•

No Factibilidad: Podría ocurrir que el problema propuesto no tuviese solución. Éste sería el caso en que las restricciones fuesen incompatibles, i.e., que ningún punto del plano (o, en general, del espacio real n-dimensional) puede cumplir simultáneamente todas las limitaciones a las que estamos sometidos, es decir, la región factible es un conjunto vacío. No Acotación: En ocasiones, podemos encontrarnos con problemas que no tengan una solución finita; así por ejemplo, en un problema de maximización podríamos tener alguna variable que pudiese incrementarse indefinidamente sin violar ninguna de las restricciones, permitiendo a la función objetivo tomar valores tan grandes como se desee. Gráficamente, tendríamos una región factible no acotada. Redundancia: Algunas restricciones pueden “estar de más” por no aportar nada nuevo a la “forma” de la región factible, ya que hay otras que resultan ser más restrictivas (esto suele ocurrir en problemas extensos, donde resulta difícil reconocer restricciones redundantes). Soluciones Múltiples: Un problema de Programación Lineal puede tener más de una solución óptima (e incluso infinita). En el caso gráfico de dos variables, si dos vértices consecutivos de la región factible son solución óptima del problema, entonces todos los puntos del segmento comprendido entre ellos también serán óptimos.

Método SIMPLEX

El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables. La base del método es el álgebra matricial y el proceso de eliminación de Gauss-Jordan. Un programa lineal es un sistema de ecuaciones o de inecuaciones llamadas “restricciones” que son lineales (es decir, que las variables no están elevadas a una potencia superior a uno y no están multiplicadas entre ellas). Es a partir de estas restricciones que debemos optimizar una función lineal llamada función objetivo.

9

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Formulación del problema.

Este método, debido a George B. Dantzing, es un procedimiento iterativo que permite realizar una exploración dirigida del conjunto de puntos extremos de la región factible. El proceso concluye cuando no es posible seguir mejorando más dicha solución. El método Simplex, tiene como punto de partida el origen siendo este la solución inicial del sistema. De esta manera, el valor de la función objetivo es de cero al inicio. El método consiste en buscar sucesivamente otro punto extremo que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de puntos extremos es finito, siempre se podrá encontrar la solución. El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el punto extremo A, entonces hay una arista que parte de A, a lo largo de la cual 𝑍 aumenta. Forma canónica y forma estándar

Cualquier programa lineal se puede representar 2 dos formas equivalentes llamadas forma estándar y canónica. La forma canónica es de utilidad principalmente para explorar el programa dual, es la forma inicial de representación de nuestro problema. En forma matricial, Maximizar ( o Minimizar) sujeto a:

𝑍 = 𝑐𝑥

≤ 𝐴𝑥 �≥� 𝑏 = 𝑥≥0

Donde 𝑥 𝑦 𝑐, son vectores columna con 𝑛 componentes, 𝑏 es un vector columna de 𝑚 componentes y 𝐴 es una matriz de 𝑚 𝑥 𝑛

Un programa lineal esta en forma canónica, si las variables son no negativas y las restricciones son ≤ para la maximización ó ≥ para la minimización.

Sin embargo, el método Simplex esta diseñado para ser utilizado únicamente con problemas en la forma estándar. Es decir, a) Todas las restricciones son igualdades. b) Todas las variables son no negativas c) Los componentes del vector 𝑏 de las restricciones son todos positivos.

Para transformar un programa lineal en forma canónica a la forma estándar, las inecuaciones deben ser transformadas a ecuaciones mediante la incorporación de las siguientes variables.

10

Raúl Urbán Ruiz

•

Si la desigualdad es del tipo≤, agregamos una variable de holgura positiva del lado izquierdo de la inecuación. Para igualar el lado izquierdo con el derecho.

� 𝑎𝑖𝑗 ≤ 𝑏𝑖 •

Se agrega una variable con signo positivo 𝑠𝑖 , donde 𝑖, representa el número de restricción.

� 𝑎𝑖𝑗 + 𝑠𝑖 ≤ 𝑏𝑖 𝑠𝑖 ≥ 0

En el caso de que la inecuación tenga signo ≥ se agrega una variable de holgura negativa del lado izquierdo de la restricción. � 𝑎𝑖𝑗 ≥ 𝑏𝑖

•

Notas de clase. Método Simplex.

Se agrega una variable con signo positivo 𝑠𝑖 , donde 𝑖, representa el número de restricción.

� 𝑎𝑖𝑗 − 𝑠𝑖 ≥ 𝑏𝑖 𝑠𝑖 ≥ 0

Asimismo, las igualdades pueden ser transformadas en dos desigualdades. � 𝑎𝑖𝑗 = 𝑏𝑖

∑ 𝑎𝑖𝑗 ≤ 𝑏𝑖 ∑ 𝑎𝑖𝑗 ≥ 𝑏𝑖

y

El método Simplex se basa en dos teoremas fundamentales − Si un programa lineal tiene una solución factible, entonces existe al menos una solución básica. − Si el programa lineal tiene una solución óptima, entonces existe al menos una solución básica que es óptima. La solución óptima es una solución básica, el método Simplex consiste en: 1. Determinar una solución básica. Es decir, que variables deben entrar a la base. 2. Probar si esta solución de las variables que están en la base es, o no, una solución óptima

a. Si la solución es óptima el problema se termina b. En caso contrario pasamos al siguiente punto. 3. Cambiar la solución de la base y retomar el proceso a partir del punto 1 hasta encontrar la solución óptima. Cada cambio de base es una iteración diferente del método En muchos problemas prácticos, las restricciones pueden ser una combinación de los tipos anteriores por lo que es necesario explicar la metodología del Simplex con la ayuda de algunos ejemplos.

11

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Ejemplos de Maximización. Sea el programa lineal siguiente: Maximizar 𝑍 = 3𝑥 + 4𝑦 sujeto a:

2𝑥 + 3𝑦 2𝑥 + 𝑦 𝑥 + 3𝑦

180

𝑥 0 ,𝑦

120 150 0

Los pasos a seguir para resolver un programa lineal por el método Simplex son los siguientes; 1. Pasar el programa lineal a la forma estándar. Se trata de convertir las desigualdades en igualdades. Para cada restricción, se incluye una variable de holgura, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales: 2x + 3y + S1 2x + y + x + 3y +

= 180 S2 = 120 S3 = 150

𝑥, 𝑦, 𝑆1 , 𝑆2 , 𝑆3 ≥ 0

2. Igualar la función objetivo a cero, e incluimos las variables de holgura anteriores −3𝑥 − 4𝑦 − 0𝑆1 − 0𝑆2 − 0𝑆3 + 𝑍 = 0

3. Escribir la tabla inicial simplex. El proceso de cálculo iterativo del algoritmo del simplex es más ordenado si el modelo lineal se rescribe en una arreglo de datos que llamaremos Tabla del Simplex. En esta tabla se muestran con mucha claridad y en forma estructurada las variables y coeficientes del modelo. Además, cada tabla muestra una solución para un punto extremo del modelo lineal. En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo: Tabla inicial del simplex Variables Base

Variable de decisión Variable de holgura

Valor

x

Y

S1

S2

S3

S1

2

3

1

0

0

180

S2

2

1

0

1

0

120

S3

1

3

0

0

1

150

Z

-3

-4

0

0

0

0

12

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

4. Elegir la variable básica y la variable de holgura que sale de la base, elección del pivote. Para escoger la variable de decisión que entra en la base, realizamos los siguientes pasos, a) Escogemos la variable con el coeficiente negativo mayor (en valor absoluto) de la función objetivo, última línea del arreglo del simplex. En nuestro ejemplo, la columna de la variable y que tiene el coeficiente – 4, segunda columna. i. ii.

Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos. Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.

La columna de la variable que entra en la base se llama columna pivote b) Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la columna resultado por el coeficiente correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso: 180 120 150 = 60, 1 = 120 𝑦 3 = 50. El menor cociente positivo, indicará la fila de la 3 variable de holgura que sale de la base. En nuestro caso es S3, ya que es el menor cociente, 50. Esta fila se llama fila pivote, y el valor 3 es entonces el pivote. i.

ii.

Si algún valor, de la última columna, es menor o igual que cero no se considera. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y el proceso de cálculo se detiene. Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes puede salir de la base.

c) En la intersección de la fila pivote y columna pivote tenemos el pivote, para nuestro ejercicio esta en el renglón 3 y columna 2; el valor del pivote es 3. 5. Encontrar los coeficientes de la nueva tabla. En primer lugar cambiamos la variable de la base del renglón pivote por la variable de decisión que corresponda a la columna pivote. En nuestro ejercicio, sale la variable S3 y entra a la base la variable de decisión y. Los nuevos coeficientes del renglón y se obtienen dividiendo todos los coeficientes de la fila pivote S3 por el pivote, 3, que es el que hay que convertir en 1. Por reducción gaussiana el resto de coeficientes de la columna son cero, incluso los de la función objetivo.

13

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

1ª. Iteración del simplex Variables Base

Variable de decisión X

Y

S1

0

S2

0

y Z

Variable de holgura S1

S2

S3

0

0

1⁄3

1

1⁄3

Valor

0

50

El siguiente paso es completar la nueva tabla. Para el recalculo vamos a utilizar la tabla anterior. Los valores de las celdas vacías se obtienen de la siguiente forma: Si 𝑎𝑖𝑗 es el coeficiente del renglón 𝑖 y la columna 𝑗. 𝑎𝑖𝑗 = 𝑎𝑖𝑗 −

𝑎𝑖𝑘 𝑎 𝑖≠𝑟 𝑎𝑟𝑘 𝑟𝑗

Donde 𝑎𝑟𝑘 es la posición del pivote; es decir, el renglón pivote r y la columna pivote k.

En nuestro ejemplo, para calcular el coeficiente 𝑎11 , primer renglón de la primera columna. El pivote está en 𝑎𝑟𝑘 = 𝑎32 = 3. 𝑎11 = 𝑎11 −

𝑎12 3 𝑎31 = 2 − (1) = 1 𝑎32 3

1ª. Iteración del simplex

Variables Base

Variable de decisión X

S1

𝑎11 = 𝑎11 −

S2

𝑎21 = 𝑎21 −

Y Z

𝑎41 = 𝑎41 −

𝑎12 3 𝑎 = 2 − (1) = 𝟏 𝑎32 31 3

𝑎22 1 𝟓 𝑎31 = 2 − (1) = 𝑎32 3 𝟑

1⁄3

𝑎42 −4 𝟓 (1) = − 𝑎31 = −3 − 𝑎32 3 𝟑

Variable de holgura Y

S1

S2

S3

0

0

1⁄3

Valor

0 0 1 0

50

El resto de los coeficientes se recalculan de la misma manera.

14

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

2ª. Iteración del simplex Variables Base

Variable de decisión

Variable de holgura

Valor

x

Y

S1

S2

S3

S1

1

0

1

0

-1

30

S2

5⁄3

0

0

1

70

1

0

0

−1/3 1/3

50

−5⁄3

0

0

0

4/3

200

𝑦 Z

1⁄3

30

� 1 = 30� 70

�5⁄3 = 42� 50

�1⁄3 = 150�

Como en la fila Z, aún tenemos coeficientes negativos, −5⁄3, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso: a) La variable que entra en la base es x, por ser la variable que corresponde al coeficiente −5⁄3 b) Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote y como el menor cociente positivo es 30, la variable de holgura que sale de la base es S1. c) El elemento pivote, ya tiene el valor de 1. Operando de forma análoga a la anterior obtenemos la nueva tabla: 3ª. Iteración del simplex Variables Variable de Base decisión

Variable de holgura

Valor

X

Y

S1

S2

S3

𝑥

1

0

1

0

-1

S2

0

0

1

𝑦

0

1

−5⁄3

4⁄3

0

0

5⁄3

0

Z

−1⁄3

0

2⁄3

−1⁄3

30

30 �−1 = −30� 20

20 �4⁄3 = 15� 40

40 �2⁄3 = 60� 250

Nuevamente tenemos un valor negativo, en la fila de Z, por lo tanto continuamos el proceso de búsqueda de solución óptima. a) La variable que entra en la base es S3, por ser la variable que corresponde al coeficiente −1⁄3 15

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

b) Dividimos los coeficientes de la última columna entre los términos correspondientes de la nueva columna pivote y como el menor cociente positivo es 15, tenemos que la variable de holgura que sale es S2. c) El elemento pivote, que ahora hay que hacer 1, es −1⁄3.

Obtenemos la tabla:

Solución óptima Variables Variable de decisión Base

Variable de holgura

Valores solución

X

Y

S1

S2

S3

1

0

45

0

0

1

15

𝑦

0

1

3⁄4

0

S2

−1⁄4

0

30

0

0

1⁄4

0

255

𝑥 Z

−5⁄4 1⁄2 5⁄4

3⁄4

− 1⁄2

Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima. La solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 255. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: 𝒙 = 𝟒𝟓, 𝒚 = 𝟑𝟎 Interpretación geométrica del método simplex.

El proceso iterativo del simplex nos ha llevado a construir diferentes tablas de datos. En cada una de ellas calculamos el valor de la función objetivo en los distintos vértices, puntos extremos, en cada caso se realizó un procedimiento de prueba para saber si se encontró el óptimo. El proceso iterativo del Simplex inicia en el punto 𝐼(0,0) con un valor de la función objetivo 𝑍 = 0.

Posteriormente, el simplex nos lleva a probar el punto 𝐴(0,50). En esta iteración la función objetivo se recalcula al valor de 𝑍 = 200.

16

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

El tercer paso, nos lleva al punto 𝐵(30,40), los datos se pueden verificar en la tabla que corresponde a la esta tercera iteración. El valor de la función objetivo nuevamente se calcula y nos entrega el valor de 𝑍 = 250.

El proceso iterativo termina al llegar al punto C(45,30) que es el punto óptimo. El valor que corresponde a la función objetivo es el máximo Z=255. Aún tendríamos un último punto en D(60,0). Su valor no supera el encontrado en el punto anterior. En el ejercicio anterior el Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un punto extremo del dominio de puntos factible, por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como forma canónica. Entonces un programa lineal esta en forma canónica si todas sus restricciones son del tipo ‘menor o igual’, como en el siguiente ejemplo. Maximizar 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + 𝑐3 𝑥3 sujeto a: 𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 ≤ 𝑏1 𝑎21 𝑥1 + 𝑎22 𝑥2 + 𝑎23 𝑥3 ≤ 𝑏2 𝑎31 𝑥1 + 𝑎32 𝑥2 + 𝑎33 𝑥3 ≤ 𝑏3 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Sin embargo no todos los problemas se presentan de esta forma, como el caso de la minimización o más aún cuando tenemos restricciones diferentes, como de igualdad o de mayor o igual. En estos casos tendremos que utilizar una transformación mediante la incorporación de variables artificiales.

Variables artificiales.

No siempre es posible en la tabla del Simplex disponer de un conjunto de vectores que, convenientemente ordenados, formen la matriz identidad. Una transformación adecuada es mediante la incorporación de nuevas variables al problema que se conocen como variables artificiales. En primer lugar pasamos nuestro programa lineal a su forma canónica, introduciendo de ser necesario variables de holgura; después, incluimos las variables artificiales a las restricciones necesarias para poder obtener una matriz básica igual a la identidad. Lógicamente para que estas variables introducidas no afecten a la solución del problema, lo deseable es que dejen de ser básicas rápidamente y de esta manera se anulen. La forma de conseguirlo es añadiéndolas a la función objetivo con un

17

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

coeficiente muy alto positivo, que lo representamos con la variable M. De esta manera, para minimizar la función objetivo deben anularse estas variables, con lo que en alguna de las iteraciones del método Simplex las variables artificiales dejan de ser básicas y a partir de ese momento puede prescindirse de ellas. El siguiente ejemplo ilustra la forma de utilizar las variables artificiales para obtener una solución óptima Encontrar la solución óptima para el siguiente programa lineal. Maximizar sujeto a:

𝑍 = 3𝑥1 + 2𝑥2 + 𝑥3 𝑥1 + 2𝑥2 + 3𝑥3 ≤ 6 2𝑥1 − 𝑥2 + 𝑥3 ≥ 5 𝑥1 + 2𝑥2 + 2𝑥3 ≥ 2 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

De acuerdo a las condiciones para resolver un programa lineal se requiere que, a) No negatividad. Las variables de nuestro modelo tomarán siempre valores positivos b) Todas las restricciones deben formularse como ecuaciones. c) La parte derecha de una restricción no puede ser negativa De esta manera, necesitamos pasar de un programa en forma canónica a un sistema de ecuaciones ordinarias. Así, i. ii. iii.

Como en el ejercicio anterior, para restricciones del tipo ≤ se añade una variable de holgura, en la restricción. Por cada restricción del tipo ≥, se resta una variable de holgura negativa A las restricciones de = y ≥, se les añade una variable artificial.

Para nuestro ejemplo, las restricciones se modifican 𝑥1 + 2𝑥2 + 3𝑥3 + 𝑆1 = 6

2𝑥1 − 𝑥2 + 𝑥3 − 𝑆2 + 𝑤2 = 5

𝑥1 + 2𝑥2 + 2𝑥3 − 𝑆3 + 𝑤3 = 2

𝑥1 , 𝑥2 , 𝑥3 , 𝑆1 , 𝑆2 , 𝑆3 , 𝑤1 , 𝑤2 ≥ 0

En primer lugar introducimos variables de holgura positivas, para las restricciones ≤ (𝑆1 ) y negativas para las restricciones ≥ (−𝑆2 𝑦 −𝑆3 ). Finalmente incorporamos variables artificiales para compensar estas variables negativas (𝑤2 𝑦 𝑤3 .

Finalmente, tendremos que incluir las variables artificiales en la función de beneficio, para esto utilizaremos el método de la M grande. El método de la M grande permite la eliminación de las variables negativas, hasta donde sea posible. El método utiliza la letra

18

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

M para representar un número muy grande, requiere de un valor de M suficientemente grande para que todas las variables artificiales salgan de la base. Si la función es de maximizar la función objetivo original se transforma así: Maximizar 𝑆 = 3𝑥1 + 2𝑥2 + 𝑥3 + 0𝑆1 + 0𝑆2 + 0𝑆3 − 𝑀𝑤2 − 𝑀𝑤3

La transformación de la función que se incluirá en la tabla requiere que se despejen las variables artificiales de las restricciones y sustituir y agrupar términos en la función objetivo. 𝑤2 = 5 − 2𝑥1 + 𝑥2 − 𝑥3 + 𝑆2

𝑦 𝑤3 = 2 − 𝑥1 − 2𝑥2 − 2𝑥3 + 𝑆3

Sustituimos en la función objetivo y tendremos,

𝑍 = 3𝑥1 + 2𝑥2 + 𝑥3 − 𝑀(5 − 2𝑥1 + 𝑥2 − 𝑥3 + 𝑆2 ) − 𝑀(2 − 𝑥1 − 2𝑥2 − 2𝑥3 + 𝑆3 ) Agrupando términos nos queda la transformación.

𝑍 = (3 + 3𝑀)𝑥1 + (2 + 𝑀)𝑥2 + (1 + 3𝑀)𝑥3 − 𝑀𝑆2 − 𝑀𝑆3 − 7𝑀

La tabla inicial del simplex queda entonces, Base 𝑆1 𝑤2 𝑤3 Z

𝑥1 1 2 1 -3-3M

𝑥2 2 -1 2 -2-M

𝑥3 3 1 2 -1-3M

𝑆1 1 0 0 0

𝑤2 0 1 0 0

𝑤3 0 0 1 0

𝑆2 0 -1 0 M

𝑆3 0 0 -1 M

Valores 6 5 2 -7M

La columna pivote, es la primera columna, el coeficiente mas negativo de Z y para 5 encontrar el renglón pivote obtenemos los cocientes, 6, 2 , 2; corresponde a el tercer renglón; por lo tanto el pivote es el elemento 𝑎1,3 = 1. La variable de decisión 𝑥1 , entra a la base Base 𝑆1 𝑤2 𝑥1 Z

𝑥1 0 0 1 0

𝑥2 0 -5 2 4+5M

𝑥3 1 -3 2 5+3M

𝑆1 1 0 0 0

𝑤2 0 1 0 0

𝑤3 -1 -2 1 3+3M

𝑆2 0 -1 0 M

𝑆3 1 2 -1 -3-2M

Valores 4 1 2 6-M

Entra a la base la variable 𝑆3 , que es la columna pivote, y el renglón pivote de acuerdo a los cocientes, 4, 1⁄2; por lo tanto, sale de la base la variable artificial 𝑊2 , que corresponde 19

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

al segundo renglón. El pivote es el elemento 𝑎2,6 = 2. En este caso entra a la base una variable de holgura. Base 𝑆1 𝑆3 𝑥1 Z

𝑥1 0 0 1 0

𝑥2

𝑥3 5⁄2

5⁄2

−5⁄2 −1⁄2

−3⁄2 1⁄2

−7

1 2

2

𝑆1 1

𝑤2 −1⁄2 1⁄2 1⁄2

0 0 0

3 2

+𝑀

𝑤3 0

𝑆2 1� 2 ⁄ −1 2 −1⁄2

-1 0 M

3

−2

𝑆3 0 1 0 0

Valores 7⁄2 1⁄2 5⁄2 15 2

Ahora el pivote es el elemento 𝑎1,2 = 2.5. La variable de decisión 𝑥2 entra a la base. Base 𝑥2 𝑆3 𝑥1 Z

𝑥1 0 0 1 0

𝑥2 1 0 0 0

𝑥3 1 1 1 4

𝑆1 2⁄5 1 1⁄5 7 5

𝑤2 −1⁄5 0 2⁄5

4 5

𝑤3 0 -1 0 M

+𝑀

𝑆2 1⁄5 0 −2⁄5 −

Valores 7⁄5 4 16⁄5

𝑆3 0 1 0 0

4 5

62 5

Ahora el pivote es el elemento 𝑎1,4 = 0.2. Deja la base la variable de decisión 𝑥2 y entra la variable de holgura 𝑆2 . Base 𝑆2 𝑆3 𝑥1 Z

𝑥1 0 0 1 0

𝑥2 5 0 2 4

𝑥3 5 1 3 8

𝑆1 2 1 1 3

𝑤2 -1 0 0 M

𝑤3 0 -1 0 M

𝑆2 1 0 0 0

𝑆3 0 1 0 0

Valores 7 4 6 18

Finalmente el algoritmo del Simplex se detiene, no tenemos coeficientes negativos en la función objetivo el máximo beneficio y la solución es 𝑥1 = 6; 𝑥2 = 0; 𝑥3 = 0, para 𝑍 = 18

Una consideración final sobre las variables artificiales. Si en la tabla final del simplex; en la base, tenemos al menos una variable artificial no negativa, el problema no tiene solución. No existe un área de soluciones factible. Caso Minimización

En un problema de minimización, a diferencia de la maximización, para que una variable entre a la base, se elige la variable cuyo valor, en la función objetivo, es la que tiene el coeficiente positivo más grande, la consideración del renglón pivote no cambia. Tenemos una solución óptima cuando todos los coeficientes del renglón Z son todos menores o iguales a cero.

20

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Ejemplo. Sea el siguiente programa lineal; Minimizar 𝑍 = 3𝑥1 + 4𝑥2 + 5𝑥3 sujeto a: 𝑥1 + 2𝑥2 + 3𝑥3 ≥ 5 2𝑥1 + 𝑥2 + 2𝑥3 ≥ 6 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Las restricciones del tipo ≥ nos obliga a trasformar el problema para utilizar variables artificiales. De esta forma el programa lineal trasformado será el siguiente: Minimizar sujeto a:

𝑍 = 3𝑥1 + 4𝑥2 + 5𝑥3

𝑥1 + 2𝑥2 + 3𝑥3 − 𝑆1 + 𝑤1 = 5

2𝑥1 + 𝑥2 + 2𝑥3 − 𝑆2 + 𝑤2 = 6 Minimizar sujeto a:

𝑥1 , 𝑥2 , 𝑥3 , 𝑆1 , 𝑆2 , 𝑤1 , 𝑤2 ≥ 0

𝑍 = 3𝑥1 + 4𝑥2 + 5𝑥3 + 𝑀𝑤1 + 𝑀𝑤2 𝑥1 + 2𝑥2 + 3𝑥3 − 𝑆1 + 𝑤1 = 5

2𝑥1 + 𝑥2 + 2𝑥3 − 𝑆2 + 𝑤2 = 6 𝑥1 , 𝑥2 , 𝑥3 , 𝑆1 , 𝑆2 , 𝑤1 , 𝑤2 ≥ 0

agrupan términos en la función objetivo. 𝑤1 = 5 − 𝑥1 − 2𝑥2 − 3𝑥3 + 𝑆1

Sustituir en la función objetivo

Ajustamos el modelo, con la incorporación de variables de holgura negativa y para compensar variables artificiales.

Se incluyen con signo positivo la constante M en la función objetivo.

Se despejan las variables artificiales de las restricciones y se sustituyen y

𝑦 𝑤2 = 6 − 2𝑥1 − 𝑥2 − 2𝑥3 + 𝑆2

𝑍 = 3𝑥1 + 4𝑥2 + 5𝑥3 + 𝑀(5 − 𝑥1 − 2𝑥2 − 3𝑥3 + 𝑆1 ) + 𝑀(6 − 2𝑥1 − 𝑥2 − 2𝑥3 + 𝑆2 ) Agrupando términos y finalmente

𝑍 = (3 − 3𝑀)𝑥1 + (4 − 3𝑀)𝑥2 + (5 − 5𝑀)𝑥3 + 𝑀𝑆1 + 𝑀𝑆2 + 11𝑀

El arreglo Simplex será el siguiente: Base 𝑤1 𝑤2 Z

𝑥1 1 2 -3+3M

𝑥2 2 1 -4+3M

𝑥3 3 2 -5+5M

𝑠1 -1 0 -M

𝑠2 0 -1 -M

𝑤1 1 0 0

𝑤2 0 1 0

Valores 5 6 11M

21

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Para elegir la columna pivote, seleccionamos el coeficiente de 𝑍 más grande. Partiendo de que M tiene un valor positivo suficientemente grande, entonces la columna de 𝑥2 es la que entra a la base. Por otro lado, para elegir la variable que sale de la base, dividimos la columna de valores por su correspondiente coeficiente de la columna pivote. En nuestro 5 6 caso tenemos los valores de: 3 = 1.66 𝑦 𝑑𝑒 2 = 3. Por lo tanto el pivote será el primer elemento de la columna base, 3. Así, entra a la base la variable 𝑥3 y sale la variable artificial 𝐴1 . El nuevo arreglo del simplex, de acuerdo al procedimiento de cálculo anteriormente expuesto, es el siguiente: Base 𝑥3 𝑤2 Z

𝑥1 1� 3 4/3

−4 4 + 𝑀 3 3

𝑥2 2/3

-1/3 −2 𝑀 − 3 3

1ª, Iteración del simplex 𝑥3 𝑆1 𝑆2 -1/3 0 1

𝑤1 1⁄3

0

2/3

-1

-2/3

0

−5 2 + 𝑀 3 3

-M

5 5 − 𝑀 3 3

𝑤2 0

Valores 5/3

0

25 8 + 𝑀 3 3

1

8/3

Para la elección del nuevo pivote repetimos el procedimiento, el más positivo del coeficiente de Z. La variable 𝑥1 es candidata a entrar a la base y sale la variable artificial 𝐴2 . Finalmente tendremos un nuevo arreglo. Base 𝑥3 𝑥1 Z

𝑥1 0 1 0

𝑥2 ¾ -1/4 -1

𝑥3 1 0 0

2ª, Iteración del simplex 𝑆1 𝑆2 𝑤1 -1/2 1/4 ½ 1/2 -3/4 -1/2 -1 -1 1-M

𝑤2 1/4 3/4 1-M

Valores 1 2 11

Hemos encontrado el óptimo, todos los coeficientes del renglón Z son negativos. Los valores para este punto óptimo son 𝑍 = 11 y 𝑥1 = 2, 𝑥2 = 0 𝑦 𝑥3 = 1.

Un último ejercicio nos muestra cómo utilizar variables artificiales, cuando tenemos restricciones de diferentes tipos. El procedimiento es similar ya sea se trata de un programa de maximización o de minimización. Ejemplo. Una empresa que fabrica alimento para aves, produce y empaca dos tipos de comida para patos y pollos, en empaques de 20 kilos. El costo semanal de fabricar un saco de comida para pollos es de $5 pesos y de $7 para patos. La empresa va a comercializar un alimento mixto que sirva para los dos tipos de aves. Al alimento para pollos se le añade un máximo de 200 unidades de vitaminas mientras que la comida para patos deberá tener un mínimo de 100 unidades. El total de unidades de vitaminas para la mezcla deberá ser exactamente 800 unidades. La formulación del programa es el siguiente.

22

Raúl Urbán Ruiz

𝑀𝑖𝑛 𝑍 = 5𝑥1 + 7𝑥2 𝑆. 𝐴. 𝑥1 ≤ 200 𝑥2 ≥ 100 𝑥1 + 𝑥2 = 800 𝑥1 , 𝑥2 ≥ 0

Notas de clase. Método Simplex.

(Vitaminas para pollos) (Vitaminas para patos) (Total de vitaminas)

Donde 𝑥1 = Vitaminas para pollos. 𝑥2 = Vitaminas para patos.

Al igual que en el caso de maximización, se comienza aumentando las restricciones y luego la función objetivo. La primera restricción, 𝑥1 ≤ 200 tiene un signo ≤ por lo tanto se le asigna una variable de holgura positiva. La segunda restricción, 𝑥2 ≥ 100 tiene un signo mayor e igual. Para igualar la restricción habrá que restar una variable de holgura. Esta variable se conoce como una variable de holgura negativa o de excedente o superflua. 𝑥2 − 𝑆2 = 100

Como el método simplex comienza en el origen, esto significa desafortunadamente que en el punto inicial (0,0) el valor de la variable 𝑆2 será de -100.

No es permitido un valor negativo para la variable de holgura. Este valor negativo representa la falta de recurso. No se puede asignar una cantidad negativa de vitaminas. Para remediar esta situación se le asignará una variable “artificial” a la restricción al lado izquierdo en adición a la variable de holgura negativa. La variable artificial absorberá la negatividad de la variable de holgura. 𝑥2 − 𝑆2 + 𝑤2 = 100

La variable artificial posee un subíndice de 2 porque pertenece a la segunda restricción. Su interpretación, es de una variable de holgura negativa que demuestra por cuántas unidades la solución final violenta la segunda restricción. Cuando se encuentra una solución que no violente la restricción, w2 será cero y se quedará con ese valor. Su único propósito es el proveer una solución inicial con valores no negativos. La tercera restricción, 𝑥1 + 𝑥2 = 800 (total de unidades de vitaminas), se le añadirá una variable artificial para no violentar la restricción. A menos que la restricción pase por el origen, de lo contrario existirá una diferencia entre el origen y la igualad de la restricción. La variable artificial absorberá esta diferencia. 𝑥1 + 𝑥2 = 800

Siempre que se incorpore una variable de holgura o artificial a una restricción, habrá que agregarlas en las demás restricciones y en la función objetivo. En una solución óptima, las

23

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

variables artificiales no pueden ser variables básicas. La razón para que estas se excluyan en la solución óptima es que estas absorben la negatividad de la variable de holgura. También representan por cuantas unidades no se ha cumplido con la restricción. Para eliminar estas variables artificiales se le asigna un costo extremadamente alto para los casos de minimización y una reducción grande en las ganancias para los casos de maximización. En problemas de minimización las variables con costos bajos son deseables y son las primeras en entrar a la solución y las variables con costos altos serán rápidamente eliminadas. Para lograr esto utilizaremos el método de la M grande. El método utiliza la letra M en vez de unidades monetarias para representar un número muy grande. Le asigna un coeficiente de M, costo muy alto en casos de minimización y -M, reducción de ganancias para maximización. Las variables de holgura negativa tienen un costo de cero. Acomodamos las restricciones y la función objetivo con sus nuevas variables de holgura y artificiales. 𝑀𝑖𝑛 𝑍 = 5𝑥1 + 7𝑥2 + 0𝑆1 + 0𝑆2 𝑆. 𝐴.

𝑥1

Función de costos

+ 𝑆1

= 200 𝑥2 − 𝑆2 = 100 = 800 𝑥1 + 𝑥2 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 ≥ 0

Al incorporar las variables artificiales el programa lineal queda: 𝑀𝑖𝑛 𝑍 = 5𝑥1 + 7𝑥2 + 0𝑆1 + 0𝑆2 + 𝑀𝑤2 + 𝑀𝑤3 𝑆. 𝐴.

Función de costos

𝑥1

+ 𝑆1 = 200 − 𝑆2 + 𝑤2 = 100 𝑥2 𝑥1 + 𝑥2 + 𝑤3 = 800 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 , 𝑤1 , 𝑤2 ≥ 0

Despejamos las variables artificiales. 𝑤2 = 100 − 𝑥2 + 𝑆2

𝑦 𝑤3 = 800 − 𝑥1 − 𝑥2

Sustituimos en la función objetivo y tendremos, 𝑍 = 5𝑥1 + 7𝑥2 + 𝑀(100 − 𝑥2 + 𝑆2 ) + 𝑀(800 − 𝑥1 − 𝑥2 ) ) Agrupando términos nos queda la transformación. 𝑍 = (5 − 𝑀)𝑥1 + (7 − 2𝑀)𝑥2 + 𝑀𝑆2 + 900𝑀 24

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

El arreglo Simplex será el siguiente: Base 𝑆1 𝑤2 𝑤3 Z

𝑥1 1 0

𝑥2 0 1

𝑆1 1 0

𝑆2 0 -1

𝑤2 0 1

𝑤3 0 0

Valores 200 100

1

1

0

0

0

1

800

-5+M

-7+2M

0

-M

0

0

900M

Las variables básicas son 𝑆1 , 𝑤2 𝑦 𝑤3 , mientras que 𝑥1 , 𝑥2 𝑦 𝑆2 son variables no básicas, porque tienen cambios positivos y sus valores son cero. El valor de la variable básica 𝑆1 es de 200 lo que indica la existencia de 200 unidades de vitaminas para pollos. Las variables artificiales significan que no se ha cumplido con la restricción. El valor de 𝑤2 = 100, indique que se agreguen por lo menos 100 unidades a la restricción de alimento para patos y su incumplimiento se debe a que la solución inicial está en el punto (0,0). Lo mismo sucede con la variable 𝑤3 .

La variable que entra a la base es 𝑥2 , es la más positiva de 𝑍. La elección de la variable que sale de la base es 𝑤2 , la que tiene el menor cociente. El nuevo arreglo del simplex, es el siguiente: Base 𝑆1 𝑋2 𝑤3 Z

𝑥1 1 0

𝑥2 0 1

𝑆1 1 0

𝑆2 0 -1

𝑤2 0 1

𝑤3 0 0

Valores 200 100

1

0

0

1

-1

1

700

-5+M

0

0

-7+M

7-2M

0

700+700M

El análisis del cuadro anterior nos indica que el costo para la mezcla es de 700 + 700𝑀, que es alto. El punto extremo (0,100) indica una combinación de 0 unidades de vitaminas para pollos y 100 para patos. La variable de holgura 𝑠1 =200. Esto indica una disponibilidad de 200 unidades. En el caso de la variable básica 𝑤3 , el valor de 700, al sustituir en la restricción aumentada incumple la condición ya que 𝑥1 + 𝑥2 + 700 = 800 Base 𝑥1 𝑥2 𝑤3 Z

𝑥1 1 0

𝑥2 0 1

𝑆1 1 0

𝑆2 0 -1

𝑤2 0 1

𝑤3 0 0

Valores 200 100

0

0

-1

1

-1

1

500

0

0

5-M

-7+M

7-2M

0

1700+500M

En esta tercera iteración del simplex, las variables básicas son 𝑥1 con valor de 200, 𝑥2 que vale 100 y 𝑤3 con 500. El costo para esta solución sigue siendo muy alto, $1700 + $500M, 25

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

esto se debe a que la variable artificial 𝑤3 está en la base. No se detiene el proceso iterativo hasta que en el renglón de Z todos los coeficientes sean negativos. De esta manera, la variable que entra a la base es 𝑆2 ya que es la única con un coeficiente positivo, −7 + 𝑀, y el único cociente que está definido es el de 𝑤3 . Así el nuevo programa lineal es, Base 𝑋1 𝑋2 𝑆2 Z

𝑥1 1 0

𝑥2 0 1

𝑆1 1 -1

𝑆2 0 0

𝑤2 0 0

𝑤3 0 1

Valores 200 600

0

0

-1

1

-1

1

500

0

0

-2

0

-M

7-M

5200

Los valores de los 𝑍𝑗 , de 0 y negativos indican que la solución es óptima. Las variables básicas son: 𝑥1 con un valor de 200 unidades, 𝑥2 con 600 y 𝑆2 con 500 unidades. La variable 𝑆1 al igual que las artificiales, son variables no básicas. Se puede apreciar en el arreglo anterior, que la matriz identidad pasó al lado izquierdo de la tabla. El costo para la solución final es de 𝑍 = $5,200. De esta manera se utilizarán 200 unidades de vitaminas para pollos y 600 para patos a un costo semanal de $5,200. La variable 𝑆2 = 500 representa un exceso de 500 unidades de las vitaminas para patos sobre el mínimo necesario de 100 unidades.

Método Dual

El concepto de dualidad fue desarrollado por Von Neumann en 1947. Tiene una interpretación económica muy importante en tanto que nos introduce al concepto de precios sombra. También llamados precios de referencia. Los precios sombra vienen dados por los valores de las variables en el óptimo del programa dual de un problema de programación lineal. Son precios de equilibrio que responden al aprovechamiento más eficiente de los recursos productivos; una especie de precios naturales o precios justos; los precios que deberían regir en el mercado si el modelo de competencia funcionara correctamente. Vamos a explicar este procedimiento mediante un ejercicio. Una sociedad agrícola produce 2 cultivos, frijol y maíz, representados por las variables 𝑥1 𝑦 𝑥2 . Estos cultivos tienen un precio de venta de $4 y $8 pesos por kilo. En la producción utilizan entre otros 2 insumos; fertilizante y semilla. Las cantidades de cada insumo necesarias para obtener un kilo de cada cultivo son las siguientes:

26

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Entradas

𝑥1

Fertilizante Semilla

𝑥2

1 1

1 4

Cantidad disponible 10 20

a) Encontrar el plan de producción que maximiza la utilidad b) Se desea asegurar los cultivos contra una pérdida eventual, helada, baja en producción, etc. Por lo tanto, se desea encontrar el pago de prima de seguro mínimo para cada cultivo, conservando la utilidad y nivel de producción. c) Una interpretación económica de b) Regresando a nuestro ejercicio, el programa lineal es; Maximizar sujeto a:

Para dibujar las restricciones,

𝑥1 , 𝑥2 ≥ 0

𝑍 = 4𝑥1 + 8𝑥2 𝑥1 + 𝑥2 ≤ 10 𝑥1 + 4𝑥2 ≤ 20

𝑥2 = 10 − 𝑥1 ; si 𝑥1 = 0, 𝑥2 = 10 𝑥1 = 10, 𝑥2 = 0 𝑥2 = 5 − 14𝑥1 ; si 𝑥1 = 0, 𝑥2 = 5 𝑥1 = 20, 𝑥2 = 0

Si sustituimos los puntos extremos en Z.

𝑍(0,0) = 0; 𝑍(10,0) = 40; 𝑍(0, 5) = 40

El beneficio óptimo ocurre cuando 20 10

𝑍 � 3 , 3 � = 53.33

Para encontrar las primas de seguro más bajas, para cubrir completamente las pérdidas; es decir, remplazar el ingreso por ventas en caso de siniestro. Hagamos 𝑢1 y 𝑢2 las primas de seguro para el fertilizante y la semilla de manera que la prima total para cada insumo es 𝑏1 𝑢1 y 𝑏2 𝑢2 respectivamente. Además, la prima asegurada no puede ser negativa. 𝑢1 , 𝑢2 ≥ 0

27

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Si el costo del aseguramiento es la suma de las primas por la fertilización y la semilla, 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 ∗ = 𝑏1 𝑢1 + 𝑏2 𝑢2

No importa cuales sean los valores individuales de los diferentes insumos es evidente que el aseguro combinado de todos los insumos necesarios para producir una unidad del primer cultivo deben ser iguales a 𝑐1; esta condición se puede representar así, 𝑎11 𝑢1 + 𝑎12 𝑢2 ≥ 𝑐1 𝑎21 𝑢1 + 𝑎22 𝑢2 ≥ 𝑐2

Por lo tanto, para obtener la prima de seguro más adecuada, es necesario asegurar que la prima total de todos los insumos requeridos para producir un kg de cada cultivo sea igual a los kg de cultivo vendidos. De acuerdo a lo anterior, para nuestro ejemplo, obtenemos el programa lineal siguiente: 𝑀𝑖𝑛 𝑍 ∗ = 10𝑢1 + 20𝑢2 𝑢1 + 𝑢2 ≥ 4 𝑢1 + 4𝑢2 ≥ 8 𝑢1 , 𝑢2 ≥ 0

Utilizamos el método gráfico para encontrar su solución.

𝑢1 + 𝑢2 = 4 ; 𝑢1 + 4𝑢2 = 8 ;

si 𝑢1 = 0, 𝑢2 = 4 𝑢1 = 4, 𝑢2 = 0 si 𝑢1 = 0, 𝑢2 = 2 𝑢1 = 8, 𝑢2 = 0

Los valores de 𝑍 ∗ para los puntos extremos son los siguientes;

𝑍 ∗ (8,0) = 80; 8 4

𝑍 ∗ �3 , 3� = 53.33; 𝑍 ∗ (0, 4) = 80

El beneficio óptimo, costo de la prima menor, ocurre cuando 8 4

𝑍 �3 , 3� = 53.33

A fin de darle sentido económico a las variables duales, aumentamos el recurso 2 en una unidad. El programa lineal primal, maximización, se modifica en la restricción 2. 𝑀𝑎𝑥 𝑍 = 4𝑥1 + 8𝑥2 28

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

𝑥1 + 𝑥2 ≤ 10 𝑥1 + 4𝑥2 ≤ 21 𝑥1 , 𝑥2 ≥ 0

Resolvemos las restricciones como un sistema de ecuaciones. 𝑥1 + 𝑥2 = 10 (-1) 𝑥1 + 4𝑥2 = 21 _____________________ 11 3𝑥2 = 11 → 𝑥2 = 3 ;

𝑥1 = 10 −

La variación en el beneficio es 19

11

𝑍 = 4�3� + 8�3� =

76 3

+

88 3

=

164 3

Como puede verificarse, la cantidad programa dual.

= 4 3

160 3

11 3

=

19 3

4

+3

representa el valor de 𝑢2 en la solución óptima del

Es evidente que el sentido económico de las variables duales varía en función del sentido económico del vector 𝐶, que es el beneficio asociado a una unidad de producción del producto. Así, si 𝐶 expresa los beneficios unitarios, entonces 𝑢 representa los beneficios marginales imputables al aumento de la cantidad disponible de un recurso. Método Simplex-Dual Como hemos visto antes, un programa lineal se puede presentar de dos formas diferentes: en la forma canónica y en la estándar. Forma canónica:

Forma dual:

Maximizar 𝑍 = 𝑐𝑥 Sujeto a: 𝐴𝑥 ≤ 𝑏 𝑥≥0

Minimizar 𝑧 ∗ = 𝑏𝑢 Sujeto a: 𝐴𝑢 ≥ 𝑐 𝑢≥0

Estos dos programas lineales se denominan comúnmente el primal y el dual. El problema consiste en encontrar el programa dual a partir del primal, Como se muestra en el esquema anterior. Se trata de pasar de un problema de maximización a uno de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero.

29

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Las variables no son las mismas, pasamos de la variables 𝑥`𝑠 a 𝑢´𝑠. Los precios o valores de estas nuevas variables en la función objetivo a minimizar son las constantes de las restricciones del programa primal. A cada restricción del primal corresponde una variable dual. Las nuevas constantes de las restricciones del programa dual corresponden a los valores de la función objetivo del primal. Finalmente se cambia el sentido de las inecuaciones de las restricciones. El cuadro siguiente resume la forma de encontrar el programa dual a partir del primal. Primal

Dual

Variable Restricción Max Beneficio unitario Término de la derecha Línea Columna Restricción ≤

Restricción Variable Min Término de la derecha Costo unitario Columna Línea Restricción ≥

Ejemplo: Sea el programa lineal siguiente, considerado como el primal. 𝑀𝑎𝑥 𝑧 = 4𝑥1 + 3𝑥2 + 5𝑥3 𝑠. 𝑎 2𝑥1 + 4𝑥2 + 𝑥3 ≤ 8 𝑥1 − 5𝑥3 ≤ 4 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

El programa dual que corresponde es el siguiente,

𝑀𝑖𝑛 𝑧 ∗ = 8𝑢1 + 4𝑢2 𝑠. 𝑎 2𝑢1 + 𝑢2 ≥ 4 4𝑢1 ≥ 3 𝑢1 − 5𝑢2 ≥ 5 𝑢1 , 𝑢2 , 𝑢3 ≥ 0

Si representamos es primal en forma matricial, el dual correspondería a la transpuesta de esta matriz, 2 4 �1 0 4 3

1 8 −5 4� 5 0

y su transpuesta

2 4 � 1 8

1 0 −5 4

4 3 � 5 0

Que corresponde al programa dual anterior

El método simplex-dual es útil para resolver problemas en los que la forma estándar es compleja, restricciones negativas o la aplicación del método simplex no es inmediata. Es decir, si en un problema lineal, después de igualar a cero la función objetivo y pasar a su

30

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

forma estándar, utilizando las variables de holgura, al menos una restricción, cualquiera de las constantes del vector de disponibilidades 𝑏 es negativa y se asegura que se tiene solución óptima. Si tenemos el problema de programación lineal siguiente, 𝑀𝑎𝑥 𝑧 = 𝑥1 + 4𝑥2 𝑠. 𝑎 3𝑥1 − 𝑥2 ≤ 12 𝑥1 − 3𝑥2 ≤ 6 𝑥1 , 𝑥2 ≥ 0

Si hacemos 𝑥1 = 0, el valor de 𝑥2 puede crecer sin limite y las restricciones se satisfacen, entonces tenemos una solución óptima infinita. Su programa dual es, 𝑀𝑖𝑛 𝑧 ∗ = 12𝑢1 + 6𝑢2 𝑠. 𝑎 3𝑢1 + 𝑢2 ≥ 1 −𝑢1 − 3𝑢2 ≥ 4 𝑢1 , 𝑢2 ≥ 0

En el caso del dual, la segunda inecuación no satisface el criterio de no negatividad, ni el primal ni el dual tienen soluciones realizables. Teorema. Si en un programa lineal, primal o dual, tiene óptimo finito, también lo tiene el otro y los valores óptimos de la función objetivo son iguales; es decir la solución en uno de los programas es la misma en el otro. Si un problema no tiene una solución limitada, entonces el otro no tiene solución factible. De lo anterior nos lleva a los siguientes teoremas a) Si uno de los dos problemas tiene solución optima finita, entonces el otro también la tiene. b) Si el problema primal tiene solución no acotada, entonces el dual no tiene solución óptima factible (el recíproco no es cierto).

Algoritmo Simplex-Dual. Este algoritmo inicia, de la misma manera que el simplex, eligiendo una primera base que es el origen. La única diferencia entre ellos es el criterio para elegir las variables que entran y salen y la regla para detener el algoritmo. El primer paso es pasar el programa primal al programa dual. Se introducen las variables de holgura necesarias. Si al menos uno de los valores de la parte derecha es negativo y se

31

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

satisface la condición de optimalidad, el problema puede resolverse por el algoritmo del simplex-dual. Se construye la tabla del simplex y para seleccionar las variables que entran y salen de la base seguimos el siguiente procedimiento, a) La variable que sale de la base es aquella variable básica que tiene el valor más negativo. Si todas las variables básicas son positivas, todos los elementos del vector de las 𝑏𝑗 son positivos, el proceso se detiene y se cuanta con una solución final óptima. Criterio de factibilidad. b) La variable que entra a la base se elige entre las variables no básicas como sigue; dividir los coeficientes de la función objetivo entre los coeficientes correspondientes de la ecuación asociada con la variable que sale de la base, se ignoran los cocientes asociados a denominadores cero y/o positivos. La variable entrante es la del menor cociente, si el caso es de minimización y el de menor valor absoluto en caso de maximización. Si todos los denominadores son ceros o positivos, no hay solución factible. Criterio de optimalidad. Ejemplo: Una organización de productores produce tres productos artesanales, collares y aretes que indicaremos como 𝑥1, , 𝑥2 . Estos productos tienen un precio de venta de 14 y 12 pesos, respectivamente. Para la elaboración de estos productos se utilizan los siguientes ingredientes, madera, hilo y semillas, que indicaremos como 𝑏1, , 𝑏2 , 𝑏3 en kilogramos. Estas relaciones se representan en la siguiente tabla. Insumos

𝑥1 2 3 1

𝑏1 𝑏2 𝑏3

Disponible

𝑥2 3 2 1

20 25 15

a) Encontrar el plan de producción que maximiza las utilidades, utilizando el

programa dual.

b) ¿Cuál es el máximo beneficio? ¿Cuánto aumentaría este beneficio si se dispusiera de un kilogramo adicional de semillas? El programa siguiente:

Programa dual

de

maximización

es

el

𝑀𝑎𝑥 𝑧 = 14𝑥1 + 12𝑥2 𝑠. 𝑎 2𝑥1 + 3𝑥2 ≤ 20 3𝑥1 + 2𝑥2 ≤ 25 𝑥1 + 𝑥2 ≤ 15 𝑥1 , 𝑥2 ≥ 0

𝑀𝑖𝑛 𝑧 ∗ = 20𝑢1 + 25𝑢2 + 15𝑢3 𝑠. 𝑎 2𝑢1 + 3𝑢2 + 𝑢3 ≥ 14 3𝑢1 + 2𝑢2 + 𝑢3 ≥ 12 𝑢1 , 𝑢2 , 𝑢3 ≥ 0

32

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Primera tabla del Simplex. Variables básicas 𝑠1 𝑠2 𝑧∗

𝑢1

𝑢2

-2 -3 20

𝑢3

-3 -2 25

-1 -1 15

𝑠1 1 0 0

𝑠2 0 1 0

Valor -14 -12 0

La columna del lado derecho de las restricciones tiene valores negativos; por lo tanto aplicamos el algoritmo dual del Simplex. El valor más negativo es −14; por lo tanto la variable que sale de la base es 𝑠1 . Para encontrar la que sale de la base obtenemos los cocientes Mínimo �−

20 2

,−

25 3

15

,− 1� = −

Luego la tabla queda; Variables básicas 𝑢2 𝑠2 𝑧∗

25 3

𝑢1

Entra la variable 𝑢2 a la base, el pivote se ubica en -2 𝑢2

2/3 -5/3 10/3

𝑢3

1 0 0

1/3 -1/3 20/3

𝑠1

-1/3 -2/3 25/3

𝑠2 0 1 0

Valor 14/3 -8/3 -350/3

8

El valor más negativo es − 3; por lo tanto la variable que sale de la base es 𝑠2 . Para encontrar la que sale de la base obtenemos los cocientes Mínimo �−

-2

10⁄3 20⁄3 25⁄3 , − 1⁄3 , − 2⁄3 � 5⁄3

= −2 Entra la variable 𝑢1 a la base, el pivote se ubica en

La nueva tabla queda; Variables básicas 𝑢2 𝑢1 𝑧∗

𝑢1 0 1 0

𝑢2

𝑢3

1 0 0

1/5 1/5 6 8

𝑠1

-3/5 2/5 7

𝑠2

2/5 -3/5 2

Valor 18/15 8/5 -122

18

a) La solución es óptima con 𝑢1 = 5 , 𝑢2 = 15 y 𝑢3 = 0. Estos valores corresponden al beneficio marginal que se obtendría al aumentar un kilogramo de madera, de hilo y de semilla respectivamente. El óptimo es 122. b) Los valores de 𝑧 ∗ (𝑠1 , 𝑠2 ) = (7,2) corresponden a los valores de 𝑥1 = 7 𝑦 𝑥2 = 2 del programa primal. El máximo beneficio es de 122,

33

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Si sustituimos en la función objetivo, del primal tendremos. 𝑀𝑎𝑥 𝑧 = 14(7) + 12(2) = 122

Otro ejercicio Minimizar Sujeto a:

Minimizar Sujeto a:

V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

-2000

-1000

0

0

0

S1

0

-3

-1

1

1

-40

S2

0

-2

-2

0

0

-60

V. Básica

Z

X1

X2

S1

S2

Solución

Z

1

-1000

0

0

-500

30000

S1

0

-2

0

1

-1/2

-10

X2

0

1

1

0

-1/2

30

V. Básica

Z

X1

X2

S1

S2

Solución

34

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

Z

1

0

-1000

-500

-250

35000

S1

0

1

-1

-1/2

1/ 4

5

S2

0

0

-2

1/ 2

-5/4

25

Resumen del método simplex para problemas de maximización.

Para solucionar un problema de maximización estándar por el método simplex, seguimos los siguientes pasos: 1. Podemos convertir un problema de minimización, se multiplicamos la función objetivo por menos uno. Es decir, 𝑀𝑖𝑛 𝑍 = 3𝑥 + 4𝑦 − 8𝑡

→

2. Convierta las desigualdades en igualdades.

𝑀𝑎𝑥 𝑍 = −3𝑥 − 4𝑦 + 8𝑡

• Cada restricción del tipo = puede ser llevada a una ecuación de igualdad usando una variable de exceso no negativa, con coeficiente nulo en la función objetivo, para compensar el efecto de la variable de holgura negativa en la restricción completamos con una variable artificial. • Las restricciones del tipo “=”, Se les añade una variable artificial para no violentar la restricción. A menos que la restricción pase por el origen, de lo contrario existirá una diferencia entre el origen y la igualad de la restricción. La variable artificial absorberá esta diferencia. En una solución óptima, las variables artificiales no pueden ser variables básicas. La razón para que estas se excluyan en la solución óptima es que estas absorben la negatividad de la variable de holgura. 3𝑥 − 4𝑦 ≤ 12 𝑥 + 2𝑦 + 𝑡 ≥ 4 4𝑥 − 2𝑦 + 5𝑡 = 12

3𝑥 − 4𝑦 + 𝑆1 = 12 𝑥 + 2𝑦 − 𝑆2 + 𝐴2 = 4 4𝑥 − 2𝑦 + 5𝑡 + 𝐴3 = 12 35

Raúl Urbán Ruiz

Notas de clase. Método Simplex.

3. Escriba la tabla inicial simplex. 4. Elegir la columna pivote. Encuentre el número negativo mayor (en valor absoluto) en el último renglón, Z. Su columna es la columna pivote. (Si hay más que una candidata, escoja alguna.) Si no hay números negativo en último renglón, solo existen valores positivos o cero, entonces hemos encontrado el punto óptimo. Es decir, la solución básica que maximiza la función objetivo. 5. Escoja el pivote en la columna pivote: El pivote debe ser una entrada positiva. Para cada entrada positiva b en la columna pivote, calcule la razón a/b, donde a es la entrada de la última columna (valores solución) del renglón. De estos cocientes, elegir el valor positivo menor. La entrada correspondiente b es el pivote. 6. Use el pivote para recalcular la tabla del simplex, de acuerdo al método descrito antes. Sustituya la variable que sale de la base por la nueva variable básica. 𝑎𝑖𝑘 𝑎 𝑖≠𝑟 𝑎𝑟𝑘 𝑟𝑗 Donde 𝑎𝑟𝑘 es la posición del pivote; k es la columna pivote y r el renglón pivote. 7. Repetir pasos 3 al 5 hasta encontrar el óptimo. 𝑎𝑖𝑗 = 𝑎𝑖𝑗 −

Referencias Bibliográficas Alpha C. Chiang Métodos Fundamentales de Economía Matemática. Ed. McGraw-Hill, 1987.USA Hillier, F.S. y Liebermann, G.J. Introducción a la Investigación de Operaciones. Ed. McGraw-Hill. 2001. Hammond P.J. y Sydsaeter Knut. Matemáticas para el Análisis Económico. ED. Prentice Hall, 1998. México. Simonnard M. Programation Linéaire. Ed Dunond, 1972. Francia.

36