domingo, 20 de abril de 2008

Segundo Parcial

Minimización en el método simplex

La principal diferencia con la maximización radica en como elegir la columna pivote.
En la minimización se toma el numero mayor positivo y el ejercicio se termina cuando ya no quedan positivos en la función objetivo. Y viceversa con la maximización



Método de las dos Fases

Se usan variables de holgura y artificiales. Las de holgura se utilizan cuando se necesita un rango de “error”. Y se usan variables artificiales según el numero de inecuaciones que existan en el problema.

En la primera fase se minimiza y en la segunda se maximiza. La primera fase se resuelve como el método simplex en minimización. Hasta que se obtiene una SOLUCIÓN OPTIMA, y comienza la fase dos que es el método simplex en maximización.


MÉTODO DE LA GRAN “M” O PENALIZACION

Cuando se utiliza menor que se usa una variable de holgura
Cuando se utiliza igual que se usa una variable artificial
Cuando se utiliza mayor que se usa una variable excedente mas una variable artificial

Se agregan variables como se indica arriba y se penalizan las variables artificiales en la función objetivo asignando una “M”

Se utiliza el método simplex para quitar las “M” de la columna artificial y se logra una SOLUCION INICIAL. Y se continua con el método simplex.


MÉTODO DE TRANSPORTE O ESQUINA NO

Se comienza con el numero de la esquina superior izquierda y se asignan números con el fin de que cuadre con la columna de oferta y la fila de demanda y se continua hacia abajo y a la derecha hasta que cuadre y se multiplican los números asignados por el coeficiente y se logra una solución optima.


MÉTODO HÚNGARO

Se utiliza al hablar de establecer tareas. Como condición el numero de filas y le columnas debe ser igual.

Se toma el numero menor de cada fila y se resta a cada elemnto den la misma fila con la finalidad de hacer ceros.-
Cuando se terminan las filas se trabaja con las columnas y se asignan las tareas a las celdas que contengan los ceros junto con el coeficiente inicial de cada celda.



MÉTODO DUAL

Solo se necesita ordenar los coeficientes de la función objetivo, de las restricciones, de los limites de las restricciones (estas se convierten en la función objetivo).

Si los coeficientes están ordenados de manera horizontal, se colocan en forma vertical y viceversa, logrando la versión matemática traspuesta del problema.

Este método tiene la finalidad de reducir el numero de restricciones haciendo mas fácil el resolverlo por cualquier método.



MÉTODO MAV (DE VOGEL)

Encontrar la diferencia entre los costos mas pequeños de los renglones y las columnas.
A continuación se asignan números para lograr los resultados de la oferta y la demanda. Si no se logra cuadrar se agregan variables de holgura y se inicia la siguiente interacción con la diferencia mayor.

viernes, 14 de marzo de 2008

VARIABLE ARTIFICIAL

Harvey J. Greenberg
Definición: Es una variable, denominada v, sumada a la ecuación, h(x) = 0. El sistema resultante, h(x) + v = 0, es factible si se deja que v = -h(x) para un dado x. Luego, la función objetivo se modifica para penalizar valores no-nulos de v. Frecuentemente se requiere que v >= 0 , por lo cual se multiplica h por -1, si así fuese necesario, para poder inicializar.
Esto es un desarrollo de la programación lineal, donde existe una Fase I cuyo objetivo es encontrar una solución con v = 0 (o verificar que el sistema original carece de una solución factible) mediante la minimización de Suma_i{v_i} (ignorando así el objetivo original, cx)

jueves, 28 de febrero de 2008

Metodo simplex

El método símplex fue desarrollado en 1947 por el Dr. George Dantzig y conjuntamente con el desarrollo de la computadora hizo posible la solución de problemas grandes planteados con la técnica matemática de programación lineal.
El algorítmo denominado símplex es la parte medular de este método; el cual se basa en la solución de un sistema de ecuaciones lineales con el conocido procedimiento de Gauss-Jordan y apoyado con criterios para el cambio de la solución básica que se resuelve en forma iterativa hasta que la solución obtenida converge a lo que se conoce como óptimo.

Metodo grafico

Método de solución gráfica.
La gran limitación que se tiene con el método de solución gráfica con programación lineal es que su aplicación sólo puede hacerse a problemas con dos y cuando mucho tres variables, en este curso se ejemplifica para problemas solo con dos variables.
A pesar de tal inconveniente, el método gráfico resulta útil para exposición e ilustración de los conceptos de la programación lineal. Ejemplo:
Max. z = 3x1 + 5x2 ... sujeto a:
x1 " 4 .......... (1)
2x2 " 12 .......... (2)
3x1 + 2x2 " 18 .......... (3) x1 ; x2 " 0
Expresar geométricamente el sistema dentro del gráfico; rango de valores.
x1 " 4 2 x2 " 12 3 x1 + 2 x2 " 18
(1) (4,0) F (2) x2 " 6 (3) x1 x2
(0.6) A
0 9
0
(0,9) B
(6,0) J
Las desigualdades son fronteras o división del espacio plano. Si la recta no pasa por el origen, se toman en cuenta las coordenadas de O.
Espacio solución: Satisface al sistema (factible) posible. Conjunto de soluciones factibles.
Si se satisface la restricción, el origen pertenece al semiplano que satisface la restricción.
(1) (3) 3x1 = 12
H x1= 4 x1 = 4
3x1 + 2x2 = 18 H = (4,3)
2x2 = 6 ; x2 = 3
Trazo de la función económica
VALOR RELATIVO
z (5,0)
(0,3)
Múltiplo de los coeficientes que nos dan la pendiente de la función.
z = 15 supuesto
...trasladar a z en cualquier dirección respetando la pendiente (paralela a la obtenida).
Haciendo coincidir z con todos los vértices conocidos nos damos cuenta que a medida que se aleja del origen crece. El punto máximo es C.
... donde z = 3(2) + 5(6) = 36
Max z = 36
Los vértices son capaces de generar lo OPTIMO.

Programacion lineal

DEFINICION: Técnica que permite ayudar a decidir la combinación óptima más rentable de productos a producir con una maquinaria y plantas dadas.

HISTORIA: La Programación Lineal es una teoría matemática desarrollada en el siglo XX. Los matematicos que han intervenido en la creación y desarrollo de la Programación Lineal han sido:
Leonid Vitalevich Kantorovitch, que en 1939 publica una monografía titulada "Métodos matemáticos de organización y planificación de la producción".
Tjalling Charles Koopmans, que junto con el anterior estudiaron entre 1941 y 1942 el conocido ahora como problema del transporte. Ambos recibieron el premio Nobel de Economía en 1975.
George Joseph Stigler, que en 1945 planteó el problema del régimen alimenticio optimal, conocido ahora como problema de la dieta.
George Bernard Dantzig, que formuló en 1947 el enunciado general al que se reduce cualquier problema de Programación Lineal y autor del método del simplex para la resolución de problemas.
John von Neumann, que en 1947 relacionó los problemas de Programación Lineal con la teoría de Matrices.