Método gráfico
Método Simplex
Solución de problemas en donde la solución continua no sea aplicable
Uso de paquetes computacionales en la solución e interpretación de los resultados
  Tutorial WinQsb+  

  Introducción.
La PL es una técnica mediante la cual se toman decisiones, reduciendo el problema bajo estudio a un modelo matemático general, el cual debe ser resuelto por métodos cuantitativos.

En desarrollo de este capítulo se aplicarán la solución de dichos modelos aplicando diversas técnicas como: el método gráfico, método simplex, método matricial, técnica de la gran M.

Además se desarrollara la aplicación de variables artificiales y obtención de soluciones para identificar a que tipo de clasificación pertenecen. Por medio de dichos modelos de solución se podrá obtener las solución adecuada para cada problema y facilitar la toma de decisiones.

Método gráfico. 

El método gráfico se utiliza para la solución de problemas de PL, representando geométricamente a las restricciones, condiciones técnicas y el objetivo.

El modelo se puede resolver en forma gráfica si sólo tiene dos variables. Para modelos con tres o más variables, el método gráfico es impráctico o imposible.

Cuando los ejes son relacionados con las variables del problema, el método es llamado método gráfico en actividad. Cuando se relacionan las restricciones tecnológicas se denomina método gráfico en recursos.

Los pasos necesarios para realizar el método son nueve:
1.  graficar las soluciones factibles, o el espacio de  soluciones (factible), que satisfagan todas las restricciones en forma simultánea.
2.  Las restricciones de no negatividad  Xi>= 0 confían todos los valores posibles.
3. El espacio encerrado por las restricciones restantes se determinan sustituyendo en primer término <= por (=) para cada restricción, con lo cual se produce la ecuación de una línea recta.
4.  trazar cada línea recta en el plano y la región en cual se encuentra cada restricción cuando se considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta asociada.
5.  Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible.
6.  Aunque hay un número infinito de puntos factibles en el espacio de soluciones, la solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo.
7.  Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de valores arbitrarios a fin de determinar la pendiente y la dirección en la cual crece o decrece el valor de la función objetivo.

Ejemplo.
Maximizar    Z  =  3X1 + 2X2
 restricciones :            X1   + 2X2   <=6       (1)
                                 2X1  +  X2    <=8       (2)
                                  -X1  + X2    <=1       (3)
                                              X2   <= 2       (4)
                                    X1              >= 0       (5)
                                               X2   >= 0       (6)

Convirtiendo las restricciones a igualdad y representandolas gráficamente se tiene:

  X1 + 2X2  = 6       (1)
2X1  +  X2  = 8       (2)
-X1  +  X2  = 1       (3)
            X2  = 2       (4)
 X1             = 0       (5)
            X2  = 0       (6)
 

Figura 1  Espacio de solución presentada con WinQsb
 
 

Figura 2 Determinación de solución
 

Maximizar    Z  =  3X1 + 2X2                             Punto           (X1, X2)                   Z                                A                 (0, 0)                      0                                B                 (4, 0)                     12                                C              (3.3, 1.3)              12.6  ( óptima )                                D                (2, 3)                      12                                E                (1, 3)                       9                                F                (0, 2)                       4

                                     Tabla 2.  Solución Método Gráfico

Para obtener la solución gráfica, después de haber obtenido el espacio de solución y graficada la función objetivo el factor clave consiste en decidir la dirección de mejora de la función objetivo.
 

En la solución gráfica observamos que la solución óptima está asociada siempre con un punto extremo del espacio de soluciones. El método simplex está basado fundamentalmente en este concepto.

Careciendo de la ventaja visual asociada con la representación gráfica del espacio de soluciones, el método simplex emplea un proceso iterativo que principia en un punto extremo factible, normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible a otro, hasta que se llega por último al punto óptimo.

Existen reglas que rigen la selección del siguiente punto extremo del método simplex:
1.  El siguiente punto extremo debe ser adyacente al actual.
2. La solución no puede regresar nunca a un punto extremo considerado con la anterioridad.

El algoritmo simplex da inicio en el origen, que suele llamarse solución inicial. Después se desplaza a un punto extremo adyacente. La elección específica de uno a otro punto depende de los coeficientes de la función objetivo hasta encontrar el punto óptimo.
Al aplicar la condición de optimidad a la tabla inicial  seleccionamos a Xi como la variable que entra. En este punto la variable que sale debe ser una de las variables artificiales.

Los pasos del algoritmo simplex son ( 10 ) :

1. Determinar una solución básica factible inicial.
2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima y sólo si todos los coeficientes de la ecuación son no negativos ( >= 0 ). Si es así, el proceso termina; de otra manera se lleva a cabo otra interacción para obtener la nueva solución básica factible inicial.
3.  Condición de factibilidad.- Para todos los problemas de maximización y minimización, variable que sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente.
4.  Seleccionar las variables de holgura como las variables básicas de inicio.
5.  Selecciona una variable que entra de entre las variables no básicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Si no existe la solución básica es la óptima, si existe pasar al paso siguiente.
6.  Realizar el paso iterativo.
a) Se determina la variable básica entrante mediante la elección de la variable con el coeficiente negativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarca la columna correspondiente a este coeficiente y se le da el nombre de columna pivote.
b)  Se determina la variable básica que sale; para esta, se toma cada coeficiente  positivo (>0) de la columna enmarcada, se divide el lado derecho de cada renglón entre estos coeficientes, se identifica la ecuación con el menor cociente y se selecciona la variable básica para esta ecuación.
c)  Se determina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces

renglón pivote nuevo  = renglón pivote antiguo
                                       número pivote

para completar la primera iteración es necesario seguir usando la eliminación de Gauss para obtener coeficientes de 0 para la nueva variable básica Xj en los otros renglones, para realizar este cambio se utiliza la siguiente fórmula:

renglón nuevo = renglón antiguo - ( coeficiente de la columna pivote X renglón pivote  nuevo)

cuando el coeficiente es negativo se utiliza la fórmula:

renglón nuevo = renglón antiguo + (coeficiente de la columna pivote X renglón pivote nuevo)
 

  TABLA SIMPLEX
como se capturaría la solución básica factible inicial en el siguiente ejemplo:

sea:

Maximizar Z = 2X1+4X2
sujeto a:

2X1+   X2<= 230
  X1+ 2X2<= 250
            X2<= 120
todas las X1,X2>=0
 
 

BASE	Z	X1	X2	S1	S2	S3	SOLUCIÓN	RAZÓN
Z	0	-2	-4	0	0	0	0	0
S1	0	2	1	1	0	0	230	230/1
S2	0	1	2	0	1	0	250	250/2
S3	0	0	1	0	0	1	120	120/1

Seleccione la variable que entra y la variable que sale de la base:

Entra X2  y sale S3, se desarrolla la nueva tabla solución y se continua el proceso iterativo hasta encontrar la solución optima si es que está existe.

Tabla Optima:
 

BASE	Z	X1	X2	S1	S2	S3	SOLUCIÓN	RAZÓN
Z	0	0	0	0	2	0	500
S1	0	0	0	1	-2	3	90
X1	0	1	0	0	1	-2	10
X2	0	0	1	0	0	1	120

Solución:  Z = $500
fabricando
X1=10
X2=120
Sobrante de
S1 = 90
Tipo de solución: Optima Múltiple  

Puedes bajar el tutorial de WinQsb+

Tutorial WinQsb+ 

regresar    

WinQsb+: Debe bajar el Software de apoyo para resolver los modelos de programación lineal.

Interpretación de los resultados: Veamos la salida de un modelo que involucra la planeación de la producción, en donde se desean construir mesas y sillas el recurso disponible es 30 m² de madera por semana, 48 horas por semana; la demanda de las sillas es de 5 unidades y la de mesas de 10 unidades, la utilidad que se obtiene por las mesas es de $10 y por las sillas de $8, ademas para construir la mesa se ocupa lo siguiente: 4.5 m² de madera  por unidad, 6 horas por unidad. Para la silla se ocupan: 1.5 m² de madera por unidad y 3 horas por cada unidad fabricada.
Con esta información se desarrolla el modelo siguiente:

Max Z = 10X₁+8X₂
s.a.
4.5X₁+1.5X₂ <= 30
6.0X₁+3.0X₂  <= 48
toda X_1,X₂  >=0

El reporte final de este modelo es el siguiente (por WinQsb)

Decision  Variable	Solution Value	Unit Cost or Profit cj	Total Contribution	Reduced  Cost	Basis Status	Allowable Min cj	Allowable  Max cj
X1	0	10.0000	0	-6.0000	at bound	-M	16.0000
X2	16.0000	8.0000	128.0000	0	basic	5.0000	M
Objetive	Function	(Max) =	128.0000
Constraint	Left Hand Side	Direction	Rigth Hand Side	Slack or Surplas	Shadow Price	Allowable  Min. RHS	Allowable  Max. RHS
C1	24.0000	<=	30.0000	6.0000	0	24.0000	M
C2	48.0000	<=	48.0000	0	2.6667	0	60.0000

INTERPRETACIÓN DE LA SALIDA:

Información de la Función Objetivo:

Decision Variable  (Variable de Decisión): Son las variables que se han definido en la formulación del problema en este caso representan al producto X1 =  mesas y X2= sillas.

Solution Value (Valor de la solución): Cantidad de mesas y sillas a fabricar, el problema se resuelve y nos indica que para obtener la mejor solución en términos de la utilidad, se necesitan fabricar 16 sillas y no fabricar mesas.

Unit Cost or Profit (costo por unidad, Utilidad por unidad): Cantidad de pesos que vamos a ganar por cada mesa y por cada silla ($10 y $8 respectivamente.

Total Contribution (contribución total): Es la cantidad en pesos que resulta al multiplicar la utilidad de cada producto por la cantidad que se va a fabricar, ejemplo al fabricar 16 sillas y multiplicarlo por $/silla 8,  la contribución es de $128.0000, así al sumar la contribución por concepto de las mesas nos arroja una aportación de $0.0000, esto resulta de hacer la operación de ($/mesa10) (0mesas)= $0.0000, finalmente la suma de 128.0000+0.0000 = $128.0000, esto es lo que se conoce como el valor de Objetive Function Max.

Reduced Cost (Costo reducido): esto nos indica el dinero que hemos dejado de ganar por cada unidad no fabricada. en este caso debemos de aumentar a mas de $6.0000 la utilidad de la mesa para que sea atractiva la fabricación de mesas.

Basis Status (estado de la base): Indica si la variable es básica o no básica, en este ejemplo la variable X1 (mesas) resulta ser no básica, esto es que no forma parte de la solución óptima, la variable X2 (sillas) es una variable básica, ya que forma parte de la solución.

Allowed Min cj (rango mínimo del cj): esta es la mínima utilidad que puedo obtener sin que la base actual cambie. (-M)

Allowed Max cj (rango mínimo del cj): esta es la máxima utilidad que puedo obtener sin que la base actual cambie. (16.0000)

los valores que aparecen son para el producto Mesa.

Interpretación de  las Restricciones:

Constraint (Restricción): Son las restricciones que forman parte del problema, se tienen dos restricciones (C1 y C2) la restricción de la madera y la de horas hombre.

Left hand side (valor al lado izquierdo): esto nos indica el consumo de recurso, de 30.000 m² de madera se consumieron 24.000 m².

Direction (dirección): es la dirección de la restricción (<=,>= o =)

Rigth hand side (valor lado derecho): es el recurso disponible actualmente 30 m²

Slack or Surplas (holguras): nos indican un faltante o bien un sobrante

Shadow Price (precio sombra): nos indica la solución Dual, esto es que el 2.6667 indica que cada hra-hombre se debe ofrecer como mínimo en $/hr 2.6667.

Allowed Min RHS (rango mínimo del bj): esta es la mínima cantidad de recurso que se debe de mantener  sin que la base actual cambie. (0 hrs-hombre)

Allowed Max RHS (rango mínimo del bj): esta es la máxima cantidad de recurso que se debe de mantener  sin que la base actual cambie (60.0000 hrs-hombre)