martes, 24 de mayo de 2011
Problema de Transporte
Problema de Transporte: (Referencia: Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947).
El problema consiste en decidir cuántas unidades trasladar desde ciertos puntos de origen (platas, ciudades, etc) a ciertos puntos de destino (centros de distribución, ciudades, etc) de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos. Se suponen conocidos los costos unitarios de transporte, los requerimientos de demanda y la oferta disponible.
Por ejemplo, suponga que una empresa posee dos plantas que elaboran un determinado producto en cantidades de 250 y 400 unidades diarias, respectivamente. Dichas unidades deben ser trasladadas a tres centros de distribución con demandas diarias de 200, 200 y 250 unidades, respectivamente. Los costos de transporte (en $/unidad) son:
C.Dist. 1 | C.Dist.2 | C.Dist.3 | |
Planta 1 | 21 | 25 | 15 |
Planta 2 | 28 | 13 | 19 |
Se requiere formular un modelo de Programación Lineal que permita satisfacer los requerimientos de demanda al mínimo costo.
Solución:
Variables de Decisión: Xij : Unidades transportadas desde la planta i (i=1, 2) hasta el centro de distribución j (j=1, 2, 3)
Función Objetivo: Minimizar el costo de transporte dado por la función: 21X11 + 25X12 + 15X13 + 28X21 + 13X22 + 19X23
Restricciones:
Satisfacer los requerimientos de Demanda:
X11+ X21 = 200
X12 + X22 = 200
X13 + X23 = 250
Sujeto a la Oferta de las plantas::
X11+ X12 + X13 = 250
X21 + X22+ X23 = 400
No Negatividad: Xij >= 0
El siguiente diagrama permite una visualización de la situación anterior:
Resolución utilizando el complemento Solver de Microsoft Excel:
1. Abrir una Planilla de Cálculo de Excel. Asegurese de tener instalado el complemento Solver (OpciónHerramientas - Complementos)
Luego construya una planilla como la de la imagen de referencia. Se han marcado con amarillo las celdas cambiantes (variables de decisión) y función objetivo. Para facilitar el seguimiento se ha escrito en rojo las fórmulas asociadas a cada celda.
2. Ingrese la función objetivo, celdas cambiantes y restricciones en la ventana de "Parámetros de Solver". Si utiliza la mismas celdas de la imagen anterior, usted debería obtener lo siguiente:
3. Ingrese a "Opciones". Luego selecione "Adoptar modelo lineal" y "Asumir no negativos". Finalmente presione "Aceptar". Luego de esto usted volverá a la pantalla principal (Parámetros de Solver)
4. Seleccione "Resolver". Obtendrá la solución al problema y podrá requerir los Informes de Solver. Finalmente presione "Aceptar".
5. Se actualizarán los valores en la Planilla de Cálculo en las celdas marcadas en amarillo desplegando la solución óptima y valor óptimo. Adicionalmente se verifica el cumplimiento de las restricciones del problema.
6. Finalmente, se obtienen los informes de sensibilidad los cuales entregan información relevante en cuanto a los precios sombra asociados a las restricciones, intervalos de variación de garantizan la validez del precio sombra, intervalo de variación para los coeficientes de la función objetivo, etc.
sábado, 21 de mayo de 2011
método húngaro
EL METODO HUNGARO
Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación. Las fases para la aplicación del método Húngaro son:
Paso 1: Encontrar primero el elemento más pequeño en cada fila de la matriz de costos m*m; se debe construir una nueva matriz al restar de cada costo el costo mínimo de cada fila; encontrar para esta nueva matriz, el costo mínimo en cada columna. A continuación se debe construir una nueva matriz (denominada matriz de costos reducidos) al restar de cada costo el costo mínimo de su columna.
Paso 2: (En algunos pocos textos este paso se atribuye a Flood). Consiste en trazar el número mínimo de líneas (horizontales o verticales o ambas únicamente de esas maneras) que se requieren para cubrir todos los ceros en la matriz de costos reducidos; si se necesitan m líneas para cubrir todos los ceros, se tiene una solución óptima entre los ceros cubiertos de la matriz. Si se requieren menos de m líneas para cubrir todos los ceros, se debe continuar con el paso 3. El número de líneas para cubrir los ceros es igual a la cantidad de asignaciones que hasta ese momento se pueden realizar.
Paso 3: Encontrar el menor elemento diferente de cero (llamado k) en la matriz de costos reducidos, que no está cubierto por las líneas dibujadas en el paso 2; a continuación se debe restar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elemento de la matriz de costos reducidos cubierto por dos líneas (intersecciones). Por último se debe regresar al paso 2.
Notas:
1. Para resolver un problema de asignación en el cual la meta es maximizar la función objetivo, se debe multiplicar la matriz de ganancias por menos uno (−1) y resolver el problema como uno de minimización.
2. Si el número de filas y de columnas en la matriz de costos son diferentes, el problema de asignación está desbalanceado. El método Húngaro puede proporcionar una solución incorrecta si el problema no está balanceado; debido a lo anterior, se debe balancear primero cualquier problema de asignación (añadiendo filas o columnas ficticias) antes de resolverlo mediante el método Húngaro.
3. En un problema grande, puede resultar difícil obtener el mínimo número de filas necesarias para cubrir todos los ceros en la matriz de costos actual. Se puede demostrar que si se necesitan j líneas para cubrir todos los ceros, entonces se pueden asignar solamente j trabajos a un costo cero en la matriz actual; esto explica porqué termina cuando se necesitan m líneas.
Características de los problemas de transporte
Características de los problemas de transporte
En general los problemas de transporte se ocupan (en forma literal o imaginaria) de la Distribución desde cualquier grupo de centros de suministro, llamados orígenes, a Cualquier grupo de centros de recepción, llamados destinos, de modo que se minimice el costo total de distribución.
Suposición de requerimientos: cada origen tiene un suministro fijo de unidades, donde este suministro completo tiene que distribuirse entre los destinos. De manera similar, cada destino tiene una demanda fija de unidades, donde esta demanda completa tiene que recibirse desde los orígenes.
Propiedades de soluciones factibles: un problema de transporte tendrá soluciones factibles si y sólo la suma de sus recursos es igual a la suma de sus demandas (equilibrio entre suministro total de todos los orígenes y la demanda total de todos los destinos).En algunos problemas reales, los recursos en realidad representan cantidades máximas(y no cantidades fijas) para distribuir.
Suposición de costo : el costo de distribuir unidades de cualquier origen a cualquier destino dado es directamente proporcional al número de unidades distribuidas. Por lo tanto, este costo es justo el costo unitario de distribución por el número de unidades distribuidas.
Suposición de requerimientos: cada origen tiene un suministro fijo de unidades, donde este suministro completo tiene que distribuirse entre los destinos. De manera similar, cada destino tiene una demanda fija de unidades, donde esta demanda completa tiene que recibirse desde los orígenes.
Propiedades de soluciones factibles: un problema de transporte tendrá soluciones factibles si y sólo la suma de sus recursos es igual a la suma de sus demandas (equilibrio entre suministro total de todos los orígenes y la demanda total de todos los destinos).En algunos problemas reales, los recursos en realidad representan cantidades máximas(y no cantidades fijas) para distribuir.
Suposición de costo : el costo de distribuir unidades de cualquier origen a cualquier destino dado es directamente proporcional al número de unidades distribuidas. Por lo tanto, este costo es justo el costo unitario de distribución por el número de unidades distribuidas.
El modelo: cualquier problema (involucre o no transporte) se ajusta al modelo de un problema de transporte si se puede describir por completo en términos de una tabla de parámetros (origen-destino: costos, recursos, demanda) y satisface tanto la suposición de requerimientos como la suposición de costo. El objetivo es minimizar el costo total de distribuir las unidades. Todos los parámetros del modelo están incluidos en la tabla de parámetros.
¡ Se requiere solo llenar una tabla de parámetros para formular el problema de transporte. !
transporte
DEFINICIÓN Y APLICACIÓN DEL MODELO DE TRANSPORTE
El modelo del transporte en básicamente un programa lineal que se puede resolver a través del método simplex regular. Sin embargo, su estructura especial hace posible el desarrollo de un procedimiento de solución, conocido como técnica del transporte, que es más eficiente en términos de calculo.
La técnica de transporte puede presentarse, y a menudo se hace, en forma elemental que parezca completamente separada del método simplex. No obstante, debemos destacar que la nueva técnica sigue esencialmente los pasos exactos del método simplex.
El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Entre los datos del modelo se encuentran:
1) Nivel de oferta de cada fuente y la cantidad de la demanda en cada destino
2) El costo de transporte unitario de la mercancía, de cada fuente a cada destino.
Como solo hay una mercancía, un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.
La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al número de unidades transportadas. La definición de unidad de transporte varia dependiendo de la mercancía que se transporte.
La figura siguiente representa el modelo de transporte como una red con m fuentes yn destinos. Una fuente o un destino esta representado por un nodo. El arco que une una fuente y un destino representa la ruta por la cual se transporta la mercancía. La cantidad de la oferta es la fuente i que esta representada principalmente por ai y la demanda en el destinoj es bj. El costo de transporte unitario entre la fuente i y el destino j es Cij.
FUENTES | DESTINOS |
 | |
Método de las Dos Fases
Fase Uno:
Minimizar la suma de las variables artificiales del modelo. Si el valor de la Z óptima es cero, se puede proseguir a la Fase Dos, de lo contrario el problema no tiene solución.
Fase Dos:
Con base en la tabla óptima de la fase uno, se elimina de las restricciones las variables artificiales, y se reemplaza la función objetivo, por la función objetivo original y se resuelve a partir de ahí, con el método Simplex tradicional.
ejemplo
Considere el siguiente modelo de Programación Lineal:
FASE 1: Al agregar S1 como variable de exceso en la restricción 1 resulta evidente que no se dispone de una solución básica factible inicial, por tanto utilizaremos una variable auxiliar "y" que incluiremos en el lado izquierdo de la restricción y que servirá como variable básica inicial. Esto define el problema inicial de la Fase 1 junto a su tabla.
Luego la variable X2 entra a la base (costo reducido negativo) y claramente "y" deja la base. Se actualiza la tabla utilizando el método simplex:
Con esta tabla finaliza la Fase 1. Notar que el valor de la función objetivo al finalizar la Fase 1 es cero, por tanto podemos continuar la Fase 2.
FASE 2: Se elimina la columna asociada a la variable artificial "y" y se actualiza el vector de costos reducidos considerando la función objetivo original. De esta forma se obtiene la tabla inicial de la Fase 2.
Dado que X2 es variable básica al finalizar la Fase 1 buscamos dejar esta misma variable como básica al iniciar la Fase 2. Para ello multiplicamos por -3 la fila 1 y luego la sumamos a la fila 2.
En este sencillo ejemplo se llega inmediatamente a la tabla final de la Fase 2, con solución óptima X1=0 y X2=10. El valor óptimo V(P)=-30.
método gráfico
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
Tabla 2. Solución 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
EL METODO SIMPLEX PARA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL
1. Convertir las desigualdades en igualdades
Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1.
Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. 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: D(3,12)
Las sucesivas tablas que hemos construido van proporcionando el valor de la función objetivo en los distintos vértices, ajustándose, a la vez, los coeficientes de las variables iniciales y de holgura.
En la primera iteración (Tabla I) han permanecido todos los coeficientes iguales, se ha calculado el valor de la función objetivo en el vértice A(0,0), siendo este 0.
A continuación se desplaza por la arista AB, calculando el valor de f , hasta llegar a B.
Este paso aporta la Tabla II.
En esta segunda iteración se ha calculado el valor que corresponde al vértice B(8,0): Z=f(8,0) = 24
Sigue por la arista BC, hasta llegar a C, donde se para y despliega los datos de la Tabla III.
En esta tercera iteración se ha calculado el valor que corresponde al vértice C(6,6) : Z=f(6,6)=30.
Continua haciendo cálculos a través de la arista CD, hasta llegar al vértice D. Los datos que se reflejan son los de laTabla IV.
Concluye con esta tabla, advirtiendo que ha terminado (antes ha comprobado que la solución no mejora al desplazarse por la arista DE)
El valor máximo de la función objetivo es 33, y corresponde a x = 3 e y = 12 (vértice D).
| Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice 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 vértices (y de aristas) 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 vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta. | El método del simplex fue creado en 1947 por el matemático George Dantzig . 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. El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex. |
Con miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema:
| Maximizar | Z= f(x,y)= 3x + 2y |
| sujeto a: | 2x + y  18 |
| 2x + 3y 42 | |
| 3x + y 24 | |
x 0 , y 0 |
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
| 2x + y + h = 18 |
| 2x + 3y + s = 42 |
| 3x +y + d = 24 |
2. Igualar la función objetivo a cero
- 3x - 2y + Z = 0
3. Escribir la tabla inicial simplexEn 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 I . Iteración nº 1 | ||||||
| Base | Variable de decisión | Variable de holgura | Valores solución | |||
| x | y | h | s | d | ||
| h | 2 | 1 | 1 | 0 | 0 | 18 |
| s | 2 | 3 | 0 | 1 | 0 | 42 |
| d | 3 | 1 | 0 | 0 | 1 | 24 |
| Z | -3 | -2 | 0 | 0 | 0 | 0 |
- Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).
En nuestro caso, la variable x de coeficiente - 3.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 (En color azulado).
- Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso:
18/2 [=9] , 42/2 [=21] y 24/3 [=8]Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.
El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En color azulado).
Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes pueden salir de la base.
- En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1.
A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.
También se puede hacer utilizando el siguiente esquema:
Fila del pivote: Nueva fila del pivote= (Vieja fila del pivote) : (Pivote) Resto de las filas: Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable entrante) X (Nueva fila del pivote) Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x en la Tabla II):
|
| Tabla II . Iteración nº 2 | ||||||
| Base | Variable de decisión | Variable de holgura | Valores solución | |||
| x | y | h | s | d | ||
| h | 0 | 1/3 | 1 | 0 | -2/3 | 2 |
| s | 0 | 7/3 | 0 | 1 | -2/3 | 26 |
| x | 1 | 1/3 | 0 | 0 | 1/3 | 8 |
| Z | 0 | -1 | 0 | 0 | 1 | 24 |
- La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1
- Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8]
y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h. - El elemento pivote, que ahora hay que hacer 1, es 1/3.
Operando de forma análoga a la anterior obtenemos la tabla:
| Tabla III . Iteración nº 3 | ||||||
| Base | Variable de decisión | Variable de holgura | Valores solución | |||
| x | y | h | s | d | ||
| y | 0 | 1 | 3 | 0 | -2 | 6 |
| s | 0 | 0 | -7 | 0 | 4 | 12 |
| x | 1 | 0 | -1 | 0 | 1 | 6 |
| Z | 0 | 0 | 3 | 0 | -1 | 30 |
- La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1
- Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6]
y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s. - El elemento pivote, que ahora hay que hacer 1, es 4.
Obtenemos la tabla:
| Tabla IV . Final del proceso | ||||||
| Base | Variable de decisión | Variable de holgura | Valores solución | |||
| x | y | h | s | d | ||
| y | 0 | 1 | -1/2 | 0 | 0 | 12 |
| d | 0 | 0 | -7/4 | 0 | 1 | 3 |
| x | 1 | 0 | -3/4 | 0 | 0 | 3 |
| Z | 0 | 0 | 5/4 | 0 | 0 | 33 |
Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. 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: D(3,12)
| * Si en el problema de maximizar apareciesen como restricciones inecuaciones de la forma: ax + by c; multiplicándolas por - 1 se transforman en inecuaciones de la forma - ax - by - c y estamos en el caso anterior* Si en lugar de maximizar se trata de un problema de minimizar se sigue el mismo proceso, pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variable cuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalizan las iteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos |
| Interpretación geométrica del método del simplex |
En la primera iteración (Tabla I) han permanecido todos los coeficientes iguales, se ha calculado el valor de la función objetivo en el vértice A(0,0), siendo este 0.
A continuación se desplaza por la arista AB, calculando el valor de f , hasta llegar a B.
Este paso aporta la Tabla II.
En esta segunda iteración se ha calculado el valor que corresponde al vértice B(8,0): Z=f(8,0) = 24
Sigue por la arista BC, hasta llegar a C, donde se para y despliega los datos de la Tabla III.
En esta tercera iteración se ha calculado el valor que corresponde al vértice C(6,6) : Z=f(6,6)=30.
Continua haciendo cálculos a través de la arista CD, hasta llegar al vértice D. Los datos que se reflejan son los de laTabla IV.
Concluye con esta tabla, advirtiendo que ha terminado (antes ha comprobado que la solución no mejora al desplazarse por la arista DE)
El valor máximo de la función objetivo es 33, y corresponde a x = 3 e y = 12 (vértice D).
Si calculas el valor de la función objetivo en el vértice E(0,14), su valor no supera el valor 33.
programación lineal
Aplicaciones
La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal. Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas de optimización constituyen casos particulares de la más amplia técnica de la programación lineal. Históricamente, las ideas de programación lineal han inspirado muchos de los conceptos centrales de la teoría de optimización tales como la dualidad, la descomposición y la importancia de la convexidad y sus generalizaciones. Del mismo modo, la programación lineal es muy usada en la microeconomía y la administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de producción. Algunos ejemplos son la mezcla de alimentos, la gestión de inventarios, lacártela y la gestión de las finanzas, la asignación de recursos humanos y recursos de máquinas, la planificación de campañas de publicidad, etc.
Variables de decisión Es lo que se trata de determinar, y para lo cual se requiere una decisión.
Generalmente se designan con letras su indizadas. Cada variable debe representar una cantidad que corresponda con una misma unidad de medida.
Función Objetivo.
El objetivo es lo que se quiere maximizar o minimizar. En el caso de la programación lineal está expresado como una función lineal
Z = f (X1 , X2 )= a1X1 + a2X2
Restricciones.
Representan los límites del escenario de la situación planteada. Se muestran por medio de desigualdades de tipo lineal. El sistema completo muestra una región del plano.
Región Factible.
Es precisamente la región determinada por el sistema de restricciones de tiplineal. Es un conjunto de puntos cuyas coordenadas satisfacen las restricciones del problema.
La región está determinada por los ejes cartesianos y las rectas.
Región Factible no acotada.
No acotadas: Una región es no acotada si no se puede encerrar en un círculo. Generalmente se piensa que el problema está mal planteado.
Región Factible acotada.
Acotada: Una región esta acotada si se puede encerrar en un círculo.
Soluciones Factibles.
Cualquier solución dentro de la región factible se denomina solución factible, es decir cualquier punto dentro de la región factible determina valores numéricos para las variables que satisfacen las restricciones.
Suscribirse a:
Comentarios (Atom)