jueves, 28 de febrero de 2008

METODO GRAFICO, METODO SIMPLEX Y OPTIMIZACION

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 restricciones :

Z = 3X1 + 2X2


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 representándolas 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



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.




MÉTODO SIMPLEX.
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




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:




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

Aplicación del método Gauss-Jordan (o de operaciones sobre renglones).
Mediante este procedimiento se elimina (en realidad se sustituye) la variable que entra, en todas las filas de la tabla. Es decir, se tiene que convertir la columna de la variable que entra en un vector columna unitario (un 1 y puros ceros). Esto se logra de la siguiente manera: 5.1. El primer paso en la eliminación de Gauss-Jordan es multiplicar la fila pivote por el inverso multiplicativo del elemento pivote (para formar la unidad) y reemplazar el nombre de la variable que sale por el nombre de la variable que entra. 5.2. La eliminación (o sustitución) se logra sumando un múltiplo adecuado de la fila pivote ( elemento pivote = 1) a cada una de las demás filas.
Es decir, se multiplica la fila pivote por el negativo del número que deseamos que se convierta en cero y el resultado de esta multiplicación se suma a la fila donde queremos que aparezca el cero.
1. Criterio para terminar el proceso.
Los pasos 2, 3, 4 y 5 se repiten hasta que todos los indicadores de la función objetivo sean no negativos (si es de maximización) o sean no positivos (si es de minimización).
Cuando esto ocurre se dice que se ha llegado a la solución óptima del problema.


Ejemplo de Método Simplex
Utilizando el método simplex resuelva el siguiente problema de programación lineal.
Max Z = 40X1 + 60X2 + 50X3
s.a. 10 X1 + 4 X2 + 2 X3 950£
2 X1 + 2 X2 410£+
X1 + + 2 X3 610£
X1 , X2 , X3 0³

Max Z -40X1 - 60X2 - 50X3
s.a. 10 X1 + 4 X2 + 2 X3 + X4 = 950
2 X1 + 2 X2 + + X5 = 410
X1 + + 2 X3 + X6 = 610
X1 , X2 , X3 , X4 , X5 , X6 ³ 0
· Solución básica actual:
X4 = 950 min í 950/4 , 410/2 , -ý
X5 = 410 min í 237.5 , 205 , -ý
X6 = 610
· Solución básica actual:
X4 = 130 min í 130/2 , - , 610/2ý
X2 = 205 min í 65 , - , 305ý
X6 = 610
· Solución básica actual:
X3 = 65 min í - , 205/0.5 , 480/2ý
X2 = 205 min í - , 410 , 240ý
X6 = 480
· Por lo tanto la solución óptima es:
Z* = 20350
X2* = 85
X3* = 305
X5* = 240
X1* = X4* = X6* = 0
· Comprobación en la función objetivo:
Max Z = 40X1 + 60X2 + 50X3
Z = 4 (0) + 3 (85) + 50(305)
Z = 20350
· Comprobación en las restricciones:
10 X1 + 4 X2 + 2 X3 + X4
10(0) + 4( 85) + 2(305) + 0 = 950
2 X1 + 2 X2 + X5
2(0) + 2(85) + 240 = 410
X1 + 2 X3 + X6
1. + 2(305) + 0 = 610

Optimización
La humanidad hace tiempo que busca, o profesa buscar, mejores maneras de realizar las tareas cotidianas de la vida. A lo largo de la historia de la humanidad, se puede observar la larga búsqueda de fuentes más efectivas de alimentos al comienzo y luego de materiales, energía y manejo del entorno físico. Sin embargo, relativamente tarde en la historia de la humanidad, comenzaron a formularse ciertas clases de preguntas generales de manera cuantitativa, primero en palabras y después en notaciones simbólicas. Un aspecto predominante de estas preguntas generales era la búsqueda de lo "mejor" o lo "óptimo". Generalmente, los gerentes buscan simplemente lograr alguna mejora en el nivel de rendimiento, es decir, un problema de "búsqueda de objetivo". Cabe destacar que estas palabras normalmente no tienen un significado preciso
Se han realizado grandes esfuerzos por describir complejas situaciones humanas y sociales. Para tener significado, esto debería escribirse en una expresión matemática que contenga una o más variables, cuyos valores deben determinarse. La pregunta que se formula, en términos generales, es qué valores deberían tener estas variables para que la expresión matemática tenga el mayor valor numérico posible (maximización) o el menor valor numérico posible (minimización). A este proceso general de maximización o minimización se lo denomina optimización.
La optimización, también denominada programación matemática, sirve para encontrar la respuesta que proporciona el mejor resultado, la que logra mayores ganancias, mayor producción o felicidad o la que logra el menor costo, desperdicio o malestar. Con frecuencia, estos problemas implican utilizar de la manera más eficiente los recursos, tales como dinero, tiempo, maquinaria, personal, existencias, etc. Los problemas de optimización generalmente se clasifican en lineales y no lineales, según las relaciones del problema sean lineales con respecto a las variables.
La Programación Matemática, en general, aborda el problema de determinar asignaciones óptimas de recursos limitados para cumplir un objetivo dado.. Los recursos pueden corresponder, por ejemplo, a personas, materiales, dinero o terrenos. Entre todas las asignaciones de recursos admisibles, queremos encontrar las que maximizan o minimizan alguna cantidad numérica tal como ganancias o costos.
El objetivo de la optimización global es encontrar la mejor solución de modelos de decisiones difíciles, frente a las múltiples soluciones locales.

EJEMPLO MAXIMIZACION Y SU SOLUCION GRAFICA
El granjero Lopez tiene 480 hectáreas en la que se puede sembrar ya sea trigo o maíz. El calcula que tiene 800 horas de trabajo disponible durante la estación crucial del verano. Dados márgenes de utilidad y los requerimientos laborales mostrados a la derecha, ¿Cuántas hectáreas de cada uno debe plantar para maximizar su utilidad?¿Cuál es ésta utilidad máxima?
Maiz:
Utilidad: $40 por hrs.
Trabajo: 2hs por hrs.
Trigo:
Utilidad: $30 por hrs.
Trabajo: 1hs por hrs.
Solución: Como primer paso para la formulación matemática de este problema, se tabula la información dada (Tabla 1). Si llamamos x a las hectáreas de maíz e y a las hectáreas de trigo. Entonces la ganancia total P, en dólares, está dada por:
P=40x+30y
Que es la función objetivo por maximizar.

..........................................Maíz........................Trigo............Elementos disponibles
Horas..................................2...............................1
Hectáreas..........................1...............................1..........................800
Utilidad por unidad.........$40..........................$30.........................480
La cantidad total de tiempo par hectáreas para sembrar maíz y trigo está dada por 2x+y horas que no debe exceder las 800 horas disponibles para el trabajo. Así se tiene la desigualdad:
2x+y<800
En forma análoga, la cantidad de hectáreas disponibles está dada por x+y, y ésta no puede exceder las hectáreas disponibles para el trabajo, lo que conduce a la desigualdad.
Por último, si no queremos tener pérdidas, x y y no pueden ser negativa, de modo que
x>0
y>0
En resumen, el problema en cuestión consiste en maximizar la función objetivo P=40x+30y
sujeta a las desigualdades
2x+y<800
x+y<480
x>0
y>0




Solución Gráfica
Los problemas de programación lineal en dos variables tienen interpretaciones geométricas relativamente sencillas; por ejemplo, el sistema de restricciones lineales asociado con un problema de programación lineal bidimensional- si no es inconsistente- define una región plana cuya frontera está formada por segmentos de recta o semirrectas, por lo tanto es posible analizar tales problemas en forma gráfica.
Si consideremos el problema del granjero López, es decir, de maximizar P = 40x+ 30y sujeta a
2x+y<800
x+y<480
x>0, y>0 (7)
El sistema de desigualdades (7) define la región plana S que aparece en la figura 5. Cada punto de S es un candidato para resolver este problema y se conocecomo solución factible. El conjunto S se conoce como conjunto factible. El objetivo es encontrar – entre todos los puntos del conjunto S- el punto o los puntos que optimicen la función objetivo P. Tal solución factible es una solución óptima y constituyen la solución del problema de programación lineal en cuestión.
Como ya se ha observado, cada punto P(x,y) en S es un candidato para la solución óptima del problema en cuestión, por ejemplo, es fácil ver que el punto (200, 150) está en S y, por lo tanto, entra en la competencia. El valor de la función objetivo P en el punto (200,150) está dado por P=40(200)+30(150)=12.500 . Ahora si se pudiera calcular el valor de P correspondiente a cada punto de S, entonces el punto (o los puntos) en S que proporcione el valor máximo de P formará el conjunto solución buscado. Por desgracia, en la mayoría de los problemas, la cantidad de candidatos es demasiado grande o, como en este problema, es infinita. Así este método no es adecuado.
Es mejor cambiar de punto de vista: en vez de buscar el valor de la función objetivo P en un punto factible, se asignará un valor a la función P y se buscarán los puntos factibles que correspondieran a un valor dado de P. Para esto supóngase que se asigna a P el valor 6000. Entonces la función objetivo se convierte en 40x+ 30y = 6.000,una ecuación lineal en x e y; por lo tanto, tiene como gráfica una línea recta L1 en el plano.


Está claro que a cada punto del segmento de recta dado por la intersección de la línea recta L1 y el conjunto factible S corresponde el valor dado 6000 de P. Al repetir el proceso, pero ahora asignando a P el valor de 12.000, se obtiene la ecuación 40x+ 30y =12.000 y la recta L2 lo cual sugiere que existen puntos factibles que corresponden a un valor mayor de P. Obsérvese que la recta L2 es paralela a L1, pues ambas tienen una pendiente igual a –4/3. Esto se comprueba con facilidad escribiendo las ecuaciones en explícita de la recta.
En general, al asignar diversos valores a la función objetivo, se obtiene una familia de rectas paralelas, cada una con pendiente igual a –4/3. Además, una recta correspondiente a un valor mayor de P está más alejada del origen que una recta con un valor menor de P. El significado es claro. Para obtener las soluciones óptimas de este problema, se encuentra la recta perteneciente a esta familia que se encuentra más lejos del origen y que interseque al conjunto factible S. La recta requerida es aquella que pasa por el punto P(320,160) (Fig. 6), de modo que la solución de este problema está dado por x=320, y=160 ( es decir que el granjero López deberá sembrar 320 hectáreas de maíz y 160 hectáreas de trigo), lo que produce el valor máximo P=40(320)+30(160)=17.600
EJEMPLO DE MINIMIZACION

Un nutricionista asesora a un individuo que sufre una deficiencia de hierro y vitamina B, y le indica que debe ingerir al menos 2400 mg de vitamina B-1 (tiamina) y 1500 mg de vitamina B-2 (riboflavina) durante cierto período de tiempo. Existen dos píldoras de vitaminas disponibles, la marca A y la marca B. Cada píldora de la marca A contiene 40 mg de hierro, 10 mg de vitamina B-1, 5 mg de vitamina B-2 y cuesta 6 centavos. Cada píldora de la marca B contiene 10 mg de hierro, 15 mg de vitamina B-1 y de vitamina B-2, y cuesta 8 centavos (tabla 2).
¿Cuáles combinaciones de píldoras debe comprar el paciente para cubrir sus requerimientos de hierro y vitamina al menor costo?


..........................Marca A..........Marca B.......Requerimientos mínimos
Hierro...............40 mg.............10 mg.....................2400 mg
Vitamina B-1....10 mg............15 mg.....................2100 mg
Vitamina B-2......5 mg.............15 mg...................1500 mg
Costo por píldora (US$)0,06 ...0,08
.
Solución: Sea x el número de píldoras de la marca A e y el número de píldoras de la marca B por comprar. El costo C, medido en centavos, está dado por
C = 6x+ 8y
que representa la función objetivo por minimizar.
La cantidad de hierro contenida en x píldoras de la marca A e y el número de píldoras de la marca B está dada por 40x+10y mg, y esto debe ser mayor o igual a 2400 mg. Esto se traduce en la desigualdad.
40x+10y>2400
Consideraciones similares con los requisitos mínimos de vitaminas B-1 y B-2 conducen a las desigualdades:
10x+15y>2100
5x+15y>1500
respectivamente. Así el problema en este caso consiste en minimizar C=6x+8y sujeta a
40x+10y>2400
10x+15y>2100
5x+15y>1500
x>0, y>0
El conjunto factible S definido por el sistema de restricciones aparece en la figura. Los vértices del conjunto factible S son A(0,240); B(30,120); C(120; 60) y D(300,0).
El método de las esquinas es de particular utilidad para resolver problemas de programación lineal en dos variables con un número pequeño de restricciones, como han demostrado los ejemplos anteriores, sin embargo su efectividad decrece con rapidez cuando el número de variables o de restricciones aumenta. Por ejemplo, se puede mostrar que un ejemplo de programación lineal en tres variables y cinco restricciones puede tener hasta diez esquinas factibles. La determinación de las esquinas factibles requiere resolver 10 sistemas 3x3 de ecuaciones lineales y luego comprobar que cada uno es un punto factible, sustituyendo cada una de estas soluciones en el sistema de restricciones. Cuando el número de variables y de restricciones aumenta a cinco y diez, respectivamente (que aún es un sistema pequeño desde el punto de vista de las aplicaciones en economía), la cantidad de vértice por hallar y comprobar como esquinas factibles aumenta hasta 252, y cada uno de estos vértices se encuentra resolviendo el sistema lineal ...¡de 5x5! Por esta razón, el método de las esquinas se utiliza con poca frecuencia para resolver problemas de programación lineal, su valor reside en que permite tener una mejor idea acerca de la naturaleza de las soluciones a los problemas de programación lineal a través de su uso en la solución de problemas de dos variables