Investigación de operaciones

EJEMPLO DE UTILIZACIÓN DEL MÉTODO ALGEBRÁICO
UN MODELO DE MAXIMIZACIÓN
Para comprender la lógica y el algoritmo del método simplex en forma algebraica vamos a resolver el modelo de mezcla productiva que ya resolvimos por el método gráfico. Se repite acá la información para mayor comodidad en las explicaciones.
Una compañía produce dos tipos de artículos, mediante un proceso que se compone detres actividades. Los datos importantes del proceso se dan en la tabla:
Actividad | Tiempo
(Minutos/Unidad ) | Capacidad
(Minutos/Día) |
| Artículo 1 | Artículo 2 | |
Formado
Corte
Ensamble | 4
4
6 | 8
3
2 | 800
600
600 |
Utilidad neta
($/unidad) | 10 | 6 | |
Resuelva el modelo de programación lineal para determinar el número de unidades de cada tipo de producto quedeben fabricarse para maximizar la utilidad neta total.
MODELO
Llamando XD al número de zapatos para dama y XC al número de zapatos para caballero, el problema tiene el siguiente modelo de P.L.:
Maximizar: | Z = 10 XD + 6 XC |
Sujeto a: |   |   |
  | 4 XD + 8 XC 800 | Formado (min./día) |
  | 4 XD + 3 XC 600 | Corte (min./día) |
  | 6 XD + 2 XC600 | Ensamble (min./día) |
  |   |   |  | con XD, XC 0 | condición de no negatividad |
SOLUCION
Para obtener la solución de un modelo de Programación Lineal, debemos expresarlo primero en formato estándar, que como se dijo antes es aquel en el cual todas las restricciones están expresadas como igualdades, con todos los términos del lado derecho mayores o iguales que cero, y además todas las variables del sistema de ecuacioneslineales están condicionadas a ser mayores o iguales que cero.
En nuestro modelo que por simplicidad en las explicaciones que siguen fue escogido de tal forma que todas las restricciones sean de la forma menor o igual, es necesario agregar a cada restricción una variable que represente la cantidad que le hace falta al lado izquierdo para ser igual al lado derecho. Haciendo lo dicho obtenemos elsiguiente
MODELO EN FORMATO ESTÁNDAR
Maximizar: | Z = 10 XD + 6 XC + 0 H1 + 0 H2 + 0 H3 |
Sujeto a: |   |
  | 4 XD + 8 XC + 1 H1                   800   (F) |
  | 4 XD + 3 XC          + 1 H2          600   (C) |
  | 6 XD + 2 XC                  + 1 H3600    (E) |
  |   |
  | con XD, XC 0
     Hi 0       |
Sistema inicial
 
 
A estas nuevas variables, que denotamos con Hi, lasllamaremos en lo sucesivo variables de holgura (slack, en ingles) o de sobrante del recurso i, porque como podemos observar representan la cantidad de recurso no utilizado en una solución cualquiera que estemos considerando.
Estamos enfrentados ahora a la tarea de obtener la solución de un sistema de tres ecuaciones lineales con cinco incógnitas (dos variables originales, que son XD y XC, cuyos valorescuantificarán las decisiones a tomar y tres incógnitas nuevas, que son las tres variables de holgura, que como ya se dijo cuantificarán la cantidad sobrante del recurso número i).
Según la teoría de la solución de sistemas de ecuaciones lineales, un sistema de este tipo, con más incógnitas que ecuaciones, tiene infinito número de soluciones. Este infinito número puede ser dividido en dossubconjuntos, ambos igualmente infinitos; el infinito número de soluciones factibles, cuyas variables toman todas valores mayores o iguales que cero, y el infinito número de soluciones infactibles que tienen al menos una variable con valor negativo.
La conclusión anterior coincide con la que habíamos obtenido en el método gráfico, cuando observamos que la región de factibilidad es un polígono (convexo)que tiene infinito número de puntos, cada uno de los cuales representa una solución factible, ya que cumple todas las restricciones y la condición de no negatividad de las variables.
Paso inicial: Hallar una solución básica factible inicial:
Si seleccionamos como variables básicas a las variables de holgura (H1, H2, H3), las no básicas serán entonces las variables originales (XD,XC).
De...