METODO DEL COSTO MINIMO 23 DE MARZO 2024

 METODO DEL COSTO MINIMO

El Método del Costo Mínimo determina una mejor solución básica factible inicial que el Método de la Esquina Noroeste debido a que se concentra en las rutas menos costosas.

De esta forma el Método del Costo Mínimo se inicia asignando lo máximo posible a la celda que tenga el mínimo costo unitario (en caso de empates, éstos se rompen de forma arbitraria). A continuación, la fila o columna ya satisfechos de tacha, y las cantidades de oferta y demanda se ajustan en consecuencia. Si se satisfacen de forma simultánea una fila y una columna, sólo se tacha uno de los dos (de forma idéntica que el Método de la Esquina Noroeste). Luego se busca la celda no tachada con el costo unitario mínimo y se repite el proceso hasta que queda sin tachar exactamente una fila o una columna.

Consideremos nuevamente el Problema de Transporte donde se desea satisfacer la demanda de 4 molinos a través de los envíos de 3 silos, donde los valores en la esquina superior derecha de cada cuadro  representan los costos unitarios de transporte desde el silo i al molino j.

En la imagen dice Molino 1, 2, 3 y 5 (columnas). Debería decir: Molino 1, 2, 3 y 4.

La aplicación del Método de Costo Mínimo al problema de transporte anterior da origen a la siguiente solución factible de inicio:

Los pasos aplicados para llegar a dichos resultados se resumen a continuación:

• La celda  tiene el menor costo unitario, por tanto se asigna lo máximo posible (15 unidades correspondiente a la oferta del silo 1). Con  se satisface tanto la demanda del molino 2 como la oferta del silo 1. Se tacha de forma arbitraria la columna 2.

• Ahora la celda  tiene el mínimo costo unitario sin tachar. Se asigna  y se tacha la columna 1 porque quedó satisfecha (lo cual deja una capacidad remanente del silo 3 de 5 unidades).

• Al continuar de este modo, se asignan en forma sucesiva 15 unidades a la celda , 0 unidades a la celda  (la capacidad del silo 1 ya fue asignada), 5 unidades a la celda  y 10 unidades a la celda .

La solución básica factible de inicio resultante con 6 variables básicas es:  la cual reporta un valor en la función objetivo (costo) de Z=15(2)+0(11)+15(9)+10(20)+5(4)+5(18)=Q475 que efectivamente es una mejor solución inicial que la obtenida por el Método de la Esquina Noroeste (que provee un valor de Q520 al ser evaluado en la función objetivo) pero por cierto no es la solución óptima según se aprecia en la siguiente imagen que resume la implementación computacional del problema.

METODO DE TRANSPORTE 16 DE MARZO 2024

 

ESQUINA NOROESTE

  El método de la esquina noroeste o regla de la esquina noroeste sirve para encontrar una solución factible inicial, pero no la solución óptima (programa de embarques óptimo), es decir, para establecer una asignación de embarques inicial que cumple con las restricciones de capacidad y de demanda y, que será el punto de partida para otros métodos que proporcionan la solución óptima, como por ejemplo, el método de salto de piedra en piedra o el método de distribución modificada (MODI).

El requisito para aplicar el método de la esquina noroeste es que los datos estén dispuestos en forma tabular.

El procedimiento se describe a continuación:

• Se inicia asignando envíos en la esquina superior izquierda de la tabla (esquina noroeste en rojo en la imagen anterior)
• Solamente se asignan embarques en la siguiente fila cuando se ha agotado la capacidad de producción de la primera fila y, así sucesivamente.
• Solamente se asignan embarques en la siguiente columna cuando se ha satisfecho la demanda de la primera columna y, así sucesivamente.
• Finalmente, debemos comprobar que se cumplen las restricciones de capacidad y demanda.

El número máximo de unidades que podemos enviar de la planta A al almacén D son 500 unidades, el almacén D no requiere más. De este modo, se satisface la demanda del almacén D y lo que resta de la capacidad de la planta A equivale a 100 unidades. La columna correspondiente al almacén D se cancela puesto que no se necesita enviar más unidades al almacén D.

En la misma fila, observamos que nos ha quedado una capacidad de 100 unidades para la planta A y que la demanda del almacén E es de 100 unidades, entonces, asignamos 100 unidades a la ruta que va de la planta A hasta el almacén E. Como consecuencia de esta asignación se ha agotado la capacidad de la planta A y se ha satisfecho la demanda del almacén E y, se cancelan la fila correspondiente a la planta A y la columna del almacén E.

Se puede decir que nuestra nueva esquina noroeste es la que corresponde a la ruta que va de la planta B al almacén F. En este caso, la capacidad de la planta B y la demanda del almacén F son iguales: 600 unidades. Se realiza la asignación por las 600 unidades y se cancela la fila correspondiente de la planta B y la columna que corresponde al almacén F. Esto es porque se ha agotado la capacidad de la planta B y satisfecho la demanda del almacén F.

Ahora, tenemos que realizar una asignación a la ruta que va de la planta C al almacén G. Asignamos 300 unidades puesto que es el requerimiento total de demanda del almacén y, con ello, se cancela la columna correspondiente al almacén G.

Solamente resta realizar una asignación en la ruta planta C – almacén H. La capacidad de la planta C y la demanda del almacén H son iguales: 200 unidades. Se realiza la asignación y se ha terminado el procedimiento.

Al revisar la siguiente tabla podemos ver que con la asignación propuesta se satisfacen todas las restricciones de capacidad y de demanda.

Para verificar que se cumplen las restricciones de capacidad sumamos las asignaciones de cada una de las filas, estas no deben ser mayores que la capacidad de cada planta.

En el caso de las restricciones de demanda sumamos las asignaciones de cada columna, estas deben ser iguales a las demandas de cada almacén.

La principal desventaja de este método es que no considera los costos unitarios de transporte para realizar la asignación, como se mencionó, es un método para encontrar una solución factible inicial y no la solución óptima.

Para calcular el costo total asociado a esta solución factible inicial se multiplica el costo de transporte unitario por el número de unidades enviadas en cada ruta y, al final, se suman estos productos.

 

 

METODO SIMPLEX 02 DE MARZO 2024

 El método simplex

es un algoritmo utilizado para resolver problemas de programación lineal. Aquí Hay un ejemplo resuelto paso a paso:

Problema: Maximizar $�=3{�}_1+2{�}_2$ sujeto a:

$$\begin{array}{rl}{\displaystyle \mathrm{<span\; style="background-color:\; white;">2</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">+</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}}& {\displaystyle <span\; style="background-color:\; white;">\le </span>\mathrm{<span\; style="background-color:\; white;">20</span>}}\\ {\displaystyle <span\; style="background-color:\; white;">-</span>\mathrm{<span\; style="background-color:\; white;">4</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">+</span>\mathrm{<span\; style="background-color:\; white;">5</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}}& {\displaystyle <span\; style="background-color:\; white;">\le </span>\mathrm{<span\; style="background-color:\; white;">10</span>}}\\ {\displaystyle {\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">,</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}}& {\displaystyle <span\; style="background-color:\; white;">\ge </span>\mathrm{<span\; style="background-color:\; white;">0</span>}}\end{array}$$

Paso 1: Convertir el problema a una forma estándar:

El primer paso en el método simplex es convertir el problema en una forma estándar. Esto implica agregar variables de holgura o exceso para convertir todas las desigualdades en ecuaciones, y asegurar que todas las variables sean no negativas.

Entonces, el problema se convierte en:

Maximizar $�=3{�}_1+2{�}_2$ sujeto a:

$$\begin{array}{rl}{\displaystyle \mathrm{<span\; style="background-color:\; white;">2</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">+</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}<span\; style="background-color:\; white;">+</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">3</span>}}}& {\displaystyle <span\; style="background-color:\; white;">=</span>\mathrm{<span\; style="background-color:\; white;">20</span>}}\\ {\displaystyle <span\; style="background-color:\; white;">-</span>\mathrm{<span\; style="background-color:\; white;">4</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">+</span>\mathrm{<span\; style="background-color:\; white;">5</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}<span\; style="background-color:\; white;">+</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">4</span>}}}& {\displaystyle <span\; style="background-color:\; white;">=</span>\mathrm{<span\; style="background-color:\; white;">10</span>}}\\ {\displaystyle {\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">,</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}<span\; style="background-color:\; white;">,</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">3</span>}}<span\; style="background-color:\; white;">,</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">4</span>}}}& {\displaystyle <span\; style="background-color:\; white;">\ge </span>\mathrm{<span\; style="background-color:\; white;">0</span>}}\end{array}$$

Paso 2: Construir la tabla simplex inicial:

Iteración	${�}_1$	${�}_2$	${�}_3$	${�}_4$	zmax
${�}_3$	2	1	1	0	20
${�}_4$	-4	5	0	1	10
$�$	3	2	0	0	0

Paso 3: Determinar la variable de entrada y salida:

Para determinar la variable de entrada, seleccionamos la columna con el coeficiente más negativo en la fila $�$, que en este caso es ${�}_1$. Para determinar la variable de salida, calculamos el cociente de los valores en la columna de resultados (RHS) dividido por los valores correspondientes en la columna ${�}_1$, y seleccionamos la fila con el cociente más pequeño, que es la primera fila.

Paso 4: Realizar operaciones de pivote:

En este paso, realizamos operaciones de fila para hacer que el elemento ${�}_1$ en la fila ${�}_3$ sea igual a 0 y convertirlo en un 1.

Multiplicamos la fila ${�}_3$ por $1\mathrm{/}2$ y la suma con la fila ${�}_4$ para hacer 0 en ${�}_1$ en la fila ${�}_4$. Luego, multiplicamos la fila ${�}_3$ por $-1$ y la suma con la fila $�$ para hacer 0 en ${�}_1$ en la fila $�$.

La tabla después del pivote será:

Iteración	${�}_1$	${�}_2$	${�}_3$	${�}_4$	zmax
${�}_3$	1	0.5	0.5	0	10
${�}_1$	0	1.5	-0.5	0.25	5
$�$	0	-1	1.5	-1.5	30

Paso 5: Determinar la variable de entrada y salida (nueva iteración):

La variable de entrada será ${�}_2$ y la variable de salida será ${�}_3$.

Paso 6: Realizar operaciones de pivote (nueva iteración):

Multiplicamos la fila ${�}_2$ por $2\mathrm{/}3$ y la suma con la fila ${�}_3$ para hacer 0 en ${�}_2$ en la fila ${�}_3$. Luego, multiplicamos la fila ${�}_2$ por $-1$ y la suma con la fila $�$ para hacer 0 en ${�}_2$ en la fila $�$.

La tabla después del pivote será:

Iteración	${�}_1$	${�}_2$	${�}_3$	${�}_4$	c
${�}_3$	1	0	1	-0.25	5
${�}_2$	0	1	-0.333	0.167	3.333
$�$	0	0	2	-2	24

Como no hay coeficientes negativos en la fila $�$, hemos alcanzado la solución óptima.

Entonces, la solución óptima es $�=24$ cuando ${�}_1=5$, ${�}_2=3.333$, ${�}_3=0$ y ${�}_4=0$.