Método vogel

El método de Vogel, o aproximación de Vogel, es un método que permite llegar a una solución inicial factible del problema de transporte.

El procedimiento de este método es el siguiente:

1. Tener los valores de costos de envíos desde cada origen a cada destino tabulados (matriz de costos). En caso de que la matriz no este equilibrada (el numero de filas es diferentes del numero de columnas), agregar una fila o columna de ceros según corresponda. Esto quiere decir que según sea el caso se creara un origen o un destino ficticio.
2. Realizar el cálculo de las penalizaciones para cada fila y columna. Las penalizaciones se calculan restando los dos valores más pequeños de cada fila y cada columna. Las penalizaciones tienen valor absoluto.
3. Identificar la fila o columna con la mayor penalización (en caso de que exista un empate en las penalizaciones, se puede elegir cualquiera de las que tiene el mayor valor), y asignar la mayor cantidad de material posible a la casilla con el menor costo en esa fila o columna.
4. Se sombrean (eliminan) las filas o columnas que hayan sido satisfechas, reduciendo así la matriz.
5. Se repite el procedimiento desde en paso 2.
6. Una vez satisfechos todos los orígenes y destinos (sombreadas todas las filas y columnas) se puede proceder a calcular el costo del programa de envió encontrado mediante este método (cabe resaltar que la solución factible encontrada con este método no es necesariamente la optima).

Método de transporte 

El problema general del transporte se refiere a la distribución de mercancía desde cualquier conjunto de centro de suministro, denominados orígenes (fuentes), hasta cualquier conjunto de centros de recepción, llamados destinos, de tal forma que se minimicen los costos totales de distribución. Cada origen tiene que distribuir ciertas unidades a los destinos y cada destino tiene cierta demanda de unidades que deben recibir de los orígenes.

Representación de una red de transporte

Como se puede observar cualquier modelo de transporte se compone de unidades de un bien a distribuir, m orígenes, n destinos, recursos en el origen, demandas en los destinos y costos de distribución por unidad. Adicionalmente, se tienen varios supuestos:

1. Supuesto de requerimientos: cada origen tiene un suministro fijo de unidades que se deben distribuir por completo entre los destinos.
2. Supuesto de costo: el costo de distribuir unidades de un origen a un destino cualquiera es directamente proporcional al número de unidades distribuidas. 
3. Propiedad de soluciones factibles: un problema de transporte tiene soluciones factible si y sólo si la sumatoria de recursos en lo m orígenes es igual a la sumatoria de demandas en los destinos. 
4. Propiedad de soluciones enteras: En los casos en los que tanto los recursos como las demandas toman un valor entero, todas las variables básicas (asignaciones), de cualquiera de las soluciones básicas factibles (inclusive la solución optima), asumen también valores enteros. 

Debido a la particularidad del modelo de transporte la forma tabular Símplex adquiere una estructura que facilita el proceso de asignación a las variables básicas, tal se muestra a continuación:

Forma Tabular Símplex Transporte

En los renglones se ubican los orígenes indicando en la columna de la derecha los recursos (oferta disponible). En las columnas se ubican los distintos destinos indicando en el último renglón los totales  demandados. En el pequeño recuadro ubicado en la margen superior derecha se indica el costo de distribuir una unidad desde el origen hasta ese destino y en la parte inferior de cada recuadro se registran las asignaciones Xi para cada variable. En los casos donde la sumatoria de los recursos y las demanda no sean las mismas, se agrega un origen o destino ficticio con la cantidad que permita cumplir la propiedad de soluciones factibles.

Después de planteado el modelo de transporte, el siguiente paso es obtener una solución básica factible, la cual se puede obtener a partir de cualquiera de los 3 criterios siguientes:

1. Regla de la esquina noroeste.
2. Método de la ruta preferente.
3. Método de aproximación de Vogel 

Antes de explicar el procedimiento para cada uno de estos criterios de asignación para encontrar la solución inicial BF, se debe conocer el número de variables básicas, el cual se determina con la expresión: m + n - 1. En el modelo anterior 3 + 2 - 1 = 4 variables básicas.

• Regla de la esquina noroeste: la primera elección X11, es decir, se inicia la asignación por la esquina noroeste de tabla. Luego se desplaza a la columna de la derecha si todavía quedan recursos en ese origen. De lo contrario se mueve al reglo debajo hasta realizar todas las asignaciones.
• Método de la ruta preferente: se fundamenta en la asignación a partir del costo mínimo de distribuir una unidad. Primero se identifica este costo se realiza la asignación de recursos máxima posible y luego se identifica el siguiente costo menor realizando el mismo procedimiento hasta realizar todas las asignaciones. 
• Método de asignación de Vogel:  para cada reglón y columna, se calcula su diferencia, que se define como la diferencia aritmética entre el costo  unitario más pequeño y el costo menor que le sigue en ese renglón o columna. En el renglón o columna con la mayor diferencia, se le asigna al menor costo unitario. Los empates se pueden romper de manera arbitraria. 

De estos 3 modelos para encontrar la solución inicial BF, el método de Vogel ha sido el más utilizado. Considerando que este criterio toma en cuenta los costos de distribución de forma más eficaz, ya que la diferencia representa el mínimo costo adicional que se incurre por no hacer una asignación en la celda que tiene el menor costo ya sea columna o renglón.

Posterior a esta asignación inicial se requiere un procedimiento que permita las siguientes iteraciones y se obtenga la solución óptima.

Prueba de optimalidad: un solución BF es óptima si y sólo si Cij - Uij -Vij >= 0 para todo (i,j) tal que Xij es no básica. Primeramente para todo variable básica de la solución actual se tiene que Cij - Uij -Vij = 0, por lo que se deduce Cij = Uij -Vij para todo (i,j) tal que Xij es básica. Para los fines de facilitar los diferentes de las diferente ecuaciones resultantes se asume el valor de U1 como cero. 

En cada iteración se determina una variable básica entrante, una variable básica saliente y luego la nueva solución básica factible. 

Paso 1: la variable de entrada se determina a partir de la relación  Cij - Uij -Vij, donde la variable Xij con el resultado más negativo es la que contribuye en una mejor medida a disminuir el costo total, se debe tener en cuenta que esta disminución va en proporción a la asignación resultante. Paso 2: la variable básica saliente es aquella variable básica que disminuya su valor a cero, es decir, es aquella variable de menor asignación y que participa en la reacción en cadena que se establece para compensar los cambios de asignar valor a la variable entrante que permitan satisfacer las restricciones de recursos y demandas. En este punto, se definen dos tipos variables para receptoras y donadoras, de acuerdo a la variación de signo que se produzca en el polígono que permite la transferencia desde la variable de salida a  la variable entrante. Paso 3: se encuentra la nueva solución BF, sumando el valor de la variable básica saliente a las asignaciones de las celdas receptoras y se resta a las asignaciones de las celdas donadoras. 


Para los fines de ejemplo, se selecciona el problema 8.2-8 ubicado en la página 325 del libro de texto. La Cost-Less Corp., surte sus cuatro (4) tiendas desde sus cuatro (4) plantas y desea minimizar los costos de distribución. A continuación se muestra la tabla con las informaciones de los costos de distribución:

Planteando este problema a través de Solver Excel (ver página relacionada en este blog) y utilizando la primera asignación con el método de la esquina noroeste, se obtiene:

Solución Básica Inicial

Solución Optima

Utilizando el programa TORA se puede visualizar cada una de las iteraciones, se asume el valor de U1 como cero en cada una de las iteraciones. 


En la primera iteración, la variable de entrada es X14 y la variable de salida es X11, con una transferencia de 10 unidades, con un resultado de -800 por lo que la reducción al costo total es de 8,000. 

Iteración 1

En la segunda iteración, la variable de entrada es X23 y la variable de salida es X22, con una transferencia de 0 unidades, con un resultado de -600 por lo que la reducción al costo total es de 0.  

Iteración 2

En la tercera iteración, la variable de entrada es X42 y la variable de salida es X32, con una transferencia de 10 unidades, con un resultado de -600 por lo que la reducción al costo total es de 6,000.

Iteración 3

En la cuarta iteración, la variable de entrada es X42 y la variable de salida es X32, con una transferencia de 0 unidades, con un resultado de -400 por lo que la reducción al costo total es de 0.

Iteración 4

La solución óptima presenta un costo total de 11,000 y la distribución de las diferentes plantas hacia las diferentes tiendas es como sigue:

X14, Planta 1 - Tienda 4 = 10 unidades

X21, Planta 2 - Tienda 1 = 20 unidades

X23, Planta 2 - Tienda 3 =  0  unidades

X33, Planta 3 - Tienda 3 = 10 unidades

X34, Planta 3 - Tienda 4 = 10 unidades

X23, Planta 4 - Tienda 1 =  0  unidades

X42, Planta 4 - Tienda 2 = 10 unidades

 

Aplicaciones Diversas De Programación Lineal 

Problema de Inversión: Considere que usted dispone de un capital de 21.000 dólares para invertir en la bolsa de valores. Un amigo le recomienda 2 acciones que en el último tiempo han estado al alza: Acción A y Acción B. La Acción A tiene una rentabilidad del 10% anual y la Acción B del 8% anual. Su amigo le aconseja tener una cartera equilibrada y diversa y por tanto le recomienda invertir un máximo de 13.000 dólares en la Acción A y como mínimo 6.000 dólares en la Acción B. Además la inversión en la Acción A debe ser menor o igual que el doble de la inversión destinada a la Acción B. Usted quiere formular y resolver un modelo de Programación Lineal que permita obtener la política de inversión que permita obtener la máxima rentabilidad (interés) anual.

Variables de Decisión: 
x = dólares invertidos en Acción A.
y = dólares invertidos en Acción B.

Función Objetivo: Se busca maximizar la rentabilidad anual que resulta de invertir en los 2 tipos de acciones.
Maximizar   0.1x  +  0.08y

Restricciones: Considera las recomendaciones de su amigo.

x  +   y   ≤  21.000	Se puede invertir como máximo 21.000 dólares en total
x             ≤  13.000	Invertir como máximo 13.000 dólares en Acción A
y   ≥   6.000	Invertir como mínimo 6.000 dólares en Acción B
x   -  2y   ≤  0	Inversión en A debe ser menor o igual que el doble de la inversión en B
x≥0, y≥0	No Negatividad

Problema de Proceso Productivo: Una empresa produce tres tipos de muebles (A, B y C), cada uno de los cuales se vende a $200, $150 y $120 respectivamente. Para la producción de estos muebles la empresa cuenta con 315 horas disponibles en un taller de corte de madera, 110 horas disponibles en un taller de lijado y 50 horas en un taller de pintado. Se ha estimado que el mueble A requiere por unidad 15 horas de trabajo en el taller de corte, 2 horas en el taller de lijado y 1 hora en el taller de pintado (estos mismos valores para los muebles B y C son 7,5:3:1 y 5:2:1, respectivamente). Se requiere formular y resolver un modelo de Programación Lineal que permita encontrar la cantidad a elaborar y vender de estos muebles de modo que la empresa obtenga el mayor beneficio.Sólución Óptima: X = 13.000 Y = 8.000. Valor Óptimo V(P) = 1.940 dólares.

Variables de Decisión: 
X = Unidades a elaborar y vender del mueble A.
Y = Unidades a elaborar y vender del mueble B.
Z = Unidades a elaborar y vender del mueble C.

De esta forma el modelo de optimización que permite encontrar el plan óptimo de producción es el siguiente:

Problema de Mezcla de Productos: Se dispone de 2 ingredientes para fabricar caramelos, cuyo sabor variará dependiendo de la proporción en que intervengan cada uno de los ingredientes. El primer ingrediente se compra a $10 por kg. y el segundo a $20 por kg. El proceso de elaboración supone un costo de $5 por kg. fabricado, cuya cantidad total corresponde simplemente a la suma de los kg. empleados en la mezcla. La demanda máxima para un mes se cifra en 100 kg y el precio de venta $50 kg. A la empresa no le interesa producir más de los que puede vender en el mes. Por último, la composición de la masa debe contener una proporción que no supere el 50% del primer ingrediente y el 80% del segundo ingrediente. Se requiere determinar cuántos kg. de caramelos se tiene que fabricar al mes y las proporciones en las que deben ser utilizados los ingredientes para obtener un máximo beneficio.

Variables de Decisión:
X1: Kg a usar del ingrediente 1 en un mes 
X2: Kg a usar del ingrediente 2 en un mes

Función Objetivo: Obtener la maxima utilidad de la venta de los caramelos descontando los costos de producción
Maximizar 50*(X1 + X2) – 10*X1 – 20*X2 - 5*(X1 + X2) = 35*X1 + 25*X2   

Restricciones: 
Demanda Máxima:     X1 + X2 <= 100
Composición:             X1/(X1 + X2) <= 50%    o     0,5*X1 – 0,5*X2 <= 0
Composición:             X2/(X1 + X2) <= 80%    o     -0,8*X1 + 0,2*X2 <= 0
No Negatividad:        X1,X2>=0

Sólución Óptima: X1 = 50 X2 = 50. Valor Óptimo V(P) = $3.000.

La programación lineal es un método eficiente para determinar una decisión óptima entre un gran número de decisiones posibles

Es impresionante el número y la diversidad de problemas en los que se puede aplicar

Método Simplex

 Método Simplex

El método simplex es un algoritmo de resolución para modelos de Programación Lineal desarrollado por George Dantzig en el año 1947. Como todo algoritmo cuenta con un proceso iterativo que secuencialmente a través de pasos o iteraciones va aproximando el valor óptimo del problema lineal en caso de existir este último.

Para aplicar el Método Simplex a un modelo de Programación Lineal se requiere que éste último se encuentre en una forma estándar. Para verificar las condiciones del formato estándar se recomienda visitar el siguiente enlace: Programación Lineal - Método Simplex.

El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.

El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.

Ejemplo del Método Simplex

• x1: Número de cinturones tipo A a fabricar por semana.

• x2: Número de cinturones tipo B a fabricar por semana.

A un grupo de artesanos se le presenta la oportunidad exportar cinturones de piel de salmón al mercado europeo. Clasifican los cinturones en dos tipos A y B: A por alta calidad y B por baja calidad. De acuerdo a sus estimaciones tendrían una utilidad de 4 euros por cinturón tipo A y 3 euros por el tipo B. La confección de un cinturón tipo A les requiere el doble de tiempo que uno tipo B. Si confeccionaran sólo cinturones tipo B podrían hacer 1.000 diarios. En todo caso, el abastecimiento de piel es suficiente para confeccionar un total combinado de 800 cinturones diarios. Los cinturones usan un diferente tipo de hebilla según su calidad. Se pueden abastecer de 800 hebillas elegantes al día para los cinturones tipo A y 700 hebillas corrientes al día para los cinturones tipo B. Se desea formular y resolver un modelo de Programación Lineal que permita a los artesanos decidir cuántos cinturones de cada tipo fabricar de modo de maximizar sus ganancias.

1.-Variables de Decisión

2.- Función Objetivo

Cada cinturón tipo A reporta una utilidad de 4 euros y cada cinturón tipo B reporta una utilidad de 3 euros. Se desea maximizar la utilidad total dada por: Max 4x1+3x2

3.-Restricciones

• No se puede fabricar más cinturones tipo A que la cantidad de hebillas disponibles: x1≤800
• No se puede fabricar más cinturones tipo B que la cantidad de hebillas disponibles: x2≤ 700
• Como máximo se puede confeccionar diariamente 800 cinturones del tipo A y del tipo B en conjunto: x1+x2≤800
• La capacidad de producción  permite fabricar 1.000 cinturones tipo B a la semana si se fabricara sólo cinturones de este tipo. Los cinturones tipo A ocupan el doble de recursos que uno B, esto es se pueden fabricar 500 cinturones a la semana si sólo se fabrican cinturones tipo A: 2x1+x2≤1.000
• No negatividad de las variables de decisión: x1, x2 ≥ 0

En términos compactos el modelo de Programación Lineal queda definido por:

Previo a la aplicación del Método Simplex será necesario llevar el modelo a su forma estándar. Para ello llevamos la función objetivo a minimización y agregamos las variables de holgura no negativas x3, x4, x5,  y x6, para las restricciones 1, 2, 3 y 4, respectivamente.

Con ello construimos la tabla inicial del Método Simplex donde las variables de holgura previamente identificadas definen una solución básica factible inicial (no óptima):

Por el criterio del costo reducido más negativo la variable que ingresa a la base es x1. Luego calculamos en dicha columna el mínimo cuociente que esta dado por: .

En consecuencia el pivote se encuentra en la fila 4 y por tanto la variable x6deja la base. (Notar que para el cálculo del mínimo cuociente o criterio de factibilidad sólo se consideran denominadores que sean estrictamente mayores a cero).

Ahora la variable no básica que ingresa a la base es x2. Calculamos nuevamente el mínimo cuociente sobre dicha columna obteniendo: .

Por tanto x5 abandona la base. Con ello realizamos una nueva iteración del Método Simplex:

La solución óptima es x1=200 y x2=600, donde el valor de las holguras x3 y x4 corresponde a 600 y 100, respectivamente. Notar adicionalmente que las variables x5 y x6 son no básicas en el óptimo, por tanto su valor es cero, lo que indica que las restricciones 3 y 4 son activas. El valor óptimo del problema es V(P)=2.600.

Para complementar el análisis anterior, se puede apreciar la convergencia del Método Simplex a través de una representación gráfica, realizada en este caso con el software Geogebra. La tabla inicial del Método Simplex corresponde al vértice A (solución básica factible no óptima) del gráfico a continuación, luego al ingresar en primera instancia la variable x1 al cabo de una iteración se alcanza el vértice E (solución básica factible no óptima). Finalmente en la segunda iteración se pasa del vértice E al vértice D, el cual corresponde a la solución básica factible óptima, dado que el costo reducido de las variables no básicas es mayor o igual a cero.

Importante: Una forma de corroborar que el criterio de seleccionar la variable no básica que ingresa a la base como aquella con el costo reducido más negativo se basa en la rapidez de convergencia del Método Simplex y no afecta en su efectividad, consiste en ingresar inicialmente a la base la variable x2. En este caso se puede constatar que se puede alcanzar la solución óptima del problema con un número mayor de iteraciones en comparación al procedimiento detallado en este artículo.

MÉTODO GRÁFICO

MÉTODO GRÁFICO

El método gráfico es un procedimiento de solución de problemas de programación lineal, muy limitado en cuanto al número de variables (2 si es un gráfico 2D y 3 si es 3D) pero muy rico en materia de interpretación de resultados e incluso análisis de sensibilidad. Este consiste en representar cada una de las restricciones y encontrar en la medida de lo posible el polígono (poliedro) factible, comúnmente llamado el conjunto solución o región factible, en el cual por razones trigonométricas en uno de sus vértices se encuentra la mejor respuesta (solución óptima).

SOLUCIÓN MEDIANTE MÉTODO GRÁFICO

GRAFICAR LAS RESTRICCIONES: 

Para iniciar con el trazado de las restricciones es indispensable igualar las restricciones a 0, de esta manera podemos mediante despeje de ecuaciones iniciar con la tabulación que nos otorgará las coordenadas para esbozar cada una de las gráficas. Además dado que se trabajará en el plano cartesiano sería prudente renombrar las variables

XT = x

XT' = y

Igualamos las restricciones,

0,12X + 0,2y = 500            

0,15X + 0,1y = 300      

0,072X + 0,027y = 108

Acto seguido iniciamos con la primera restricción, hallamos las primeras dos coordenadas. Para hallar las coordenadas regularmente llevamos una de las variables a cero, para de esta manera despejar más fácilmente la segunda.

Por ejemplo, para un x = 0

0,12(0) + 0,2y = 500

0,2y =  500

500/0,2 = y

2500 = y

y para un y = 0

0,12x + 0,2(0) = 500

0,12x = 500

x = 500/0,12

x = 4167

EJEMPLO 1:

Una compañía de auditores se especializa en preparar liquidaciones y auditorías de empresas pequeñas. Tienen interés en saber cuantas auditorías y liquidaciones pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800 horas de trabajo directo y 320 horas para revisión. Una auditoría en promedio requiere de 40 horas de trabajo directo y 10 horas de revisión, además aporta un ingreso de 300 dls. Una liquidación de impuesto requiere de 8 horas de trabajo directo y de 5 horas de revisión, produce un ingreso de 100 dls. El máximo de liquidaciones mensuales disponibles es de 60.

OBJETIVO : Maximizar el ingreso total.

VARIABLE DE DECISION: Cantidad de auditorías (X₁).

Cantidad de liquidaciones (X_2).

RESTRICCIONES : Tiempo disponible de trabajo directo

Tiempo disponible de revisión

Número máximo de liquidaciones.

Maximizar 

Sujeto a:

La solución óptima siempre se encuentra en uno de los vértices del conjunto de soluciones factibles. Se analizan estos valores en la función objetivo. El vértice que representa el mejor valor de la función objetivo será la solución óptima.