Unidad 2 - Método simplex
El Método Simplex: Un Resumen Paso a Paso con Ejemplos
El método simplex es un algoritmo fundamental en la programación lineal, permitiendo encontrar la solución óptima (máxima o mínima) de un problema sujeto a restricciones. Su aplicación abarca diversos campos, desde la economía hasta la ingeniería. En este blog, exploraremos los pasos esenciales del método simplex, ilustrados con ejemplos prácticos.
a. Definición de Variables:
Antes de sumergirnos en el algoritmo, es crucial identificar los tipos de variables:
Variables de decisión: Representan las cantidades a determinar para optimizar la función objetivo.
Variables de exceso: Se introducen en problemas con restricciones de mayor que o igual, indicando la cantidad excedente del recurso.
Variables artificiales: Se emplean en problemas de minimización con restricciones de igualdad, convirtiéndolas en desigualdades de mayor que o igual.
Variables de holgura: Se incluyen en problemas con restricciones de menor que o igual, indicando la cantidad restante del recurso.
Ejemplo:
Una empresa fabrica dos productos A y B, con costos unitarios de $5 y $6 respectivamente. Las restricciones de disponibilidad de materia prima y tiempo de máquina son 100 y 80 unidades, respectivamente. Se desea maximizar la ganancia total, la cual es de $3 por unidad de A y $4 por unidad de B.
Variables de decisión: x (unidades de A) e y (unidades de B).
Restricciones:
Materia prima: 5x + 6y ≤ 100
Tiempo de máquina: 2x + 3y ≤ 80
b. Construcción de la Matriz Simplex:
Fila de la función objetivo: Colocar los coeficientes de las variables de decisión multiplicados por el valor negativo de la ganancia unitaria (en este caso, -3 y -4). Agregar una nueva variable artificial (z) con un coeficiente de 0 en la función objetivo y un valor de M (una constante grande) en la última columna.
c. Resolución del Problema:
Selección de la Columna Pivote: Identificar la variable de la función objetivo con el valor más negativo (-4 en este caso). Esta columna será la columna pivote.
Selección de la Fila Pivote: Dividir cada valor en la columna RHS por el coeficiente correspondiente en la columna pivote (excluyendo la fila de la función objetivo). Seleccionar la fila con el cociente mínimo positivo (fila 2 en este caso).
Cálculo de Nuevos Valores:
a. Fila pivote: Dividir cada valor en la fila pivote por el valor pivote (3 en este caso).
b. Demás filas: Para cada fila (excepto la pivote), realizar la siguiente operación para cada columna: (Nuevo valor en la fila i) = (Valor actual en la fila i) - (Coeficiente en la fila i de la columna pivote * Valor en la fila pivote).
Repetición: Repetir los pasos 1, 2 y 3 hasta que todas las variables de la función objetivo sean no negativas o hasta que se alcance la solución óptima.
Ejemplo de Iteraciones:
| Iteración | x | y | z | s1 | s2 | ≤ | RHS | |---|---|---|---|---|---|---| | 0 | 0 | 0 | M | 100 | 80 | 0 | | 1 | 0 | 20/3 | 0 | 20/3 | -20/3 | 40 | | 2 | 10/3 | 0 |
El método simplex es un algoritmo fundamental en la programación lineal, permitiendo encontrar la solución óptima (máxima o mínima) de un problema sujeto a restricciones. Su aplicación abarca diversos campos, desde la economía hasta la ingeniería. En este blog, exploraremos los pasos esenciales del método simplex, ilustrados con ejemplos prácticos.
a. Definición de Variables:
Antes de sumergirnos en el algoritmo, es crucial identificar los tipos de variables:
Variables de decisión: Representan las cantidades a determinar para optimizar la función objetivo.
Variables de exceso: Se introducen en problemas con restricciones de mayor que o igual, indicando la cantidad excedente del recurso.
Variables artificiales: Se emplean en problemas de minimización con restricciones de igualdad, convirtiéndolas en desigualdades de mayor que o igual.
Variables de holgura: Se incluyen en problemas con restricciones de menor que o igual, indicando la cantidad restante del recurso.
Ejemplo:
Una empresa fabrica dos productos A y B, con costos unitarios de $5 y $6 respectivamente. Las restricciones de disponibilidad de materia prima y tiempo de máquina son 100 y 80 unidades, respectivamente. Se desea maximizar la ganancia total, la cual es de $3 por unidad de A y $4 por unidad de B.
Variables de decisión: x (unidades de A) e y (unidades de B).
Restricciones:
Materia prima: 5x + 6y ≤ 100
Tiempo de máquina: 2x + 3y ≤ 80
b. Construcción de la Matriz Simplex:
Fila de la función objetivo: Colocar los coeficientes de las variables de decisión multiplicados por el valor negativo de la ganancia unitaria (en este caso, -3 y -4). Agregar una nueva variable artificial (z) con un coeficiente de 0 en la función objetivo y un valor de M (una constante grande) en la última columna.
| x | y | z | ≤ | RHS |
|---|---|---|---|---|
| -3 | -4 | 0 | 0 | M |Filas de las restricciones: Para cada restricción, escribir los coeficientes de las variables de decisión y agregar las variables de holgura (s1 y s2) con coeficientes 1 y -1, respectivamente. Completar con el valor del lado derecho (RHS) de la restricción.| x | y | z | s1 | s2 | ≤ | RHS |
|---|---|---|---|---|---|---|
| -3 | -4 | 0 | 1 | 0 | 100 |
| 2 | 3 | 0 | 0 | 1 | 80 |c. Resolución del Problema:
Selección de la Columna Pivote: Identificar la variable de la función objetivo con el valor más negativo (-4 en este caso). Esta columna será la columna pivote.
Selección de la Fila Pivote: Dividir cada valor en la columna RHS por el coeficiente correspondiente en la columna pivote (excluyendo la fila de la función objetivo). Seleccionar la fila con el cociente mínimo positivo (fila 2 en este caso).
Cálculo de Nuevos Valores:
a. Fila pivote: Dividir cada valor en la fila pivote por el valor pivote (3 en este caso).
b. Demás filas: Para cada fila (excepto la pivote), realizar la siguiente operación para cada columna: (Nuevo valor en la fila i) = (Valor actual en la fila i) - (Coeficiente en la fila i de la columna pivote * Valor en la fila pivote).
Repetición: Repetir los pasos 1, 2 y 3 hasta que todas las variables de la función objetivo sean no negativas o hasta que se alcance la solución óptima.
Ejemplo de Iteraciones:
| Iteración | x | y | z | s1 | s2 | ≤ | RHS | |---|---|---|---|---|---|---| | 0 | 0 | 0 | M | 100 | 80 | 0 | | 1 | 0 | 20/3 | 0 | 20/3 | -20/3 | 40 | | 2 | 10/3 | 0 |
Comentarios
Publicar un comentario