Ejemplo de Programacion Lineal - Método Simplex - Dos Fases
Datos del Problema
Se requiere Maximizar el siguiente problema:
- Función Objetivo
- Z = X1 + X2
- Sujeto a las siguientes restricciones
- X1 + X2 ≤ 4
- -X1 + X2 ≤ 1
X1, X2 ≥ 0
- Enunciado Original
- Ejercicio Simplex - Valor Óptimo con Infinitas Soluciones
Solución
Para resolver el problema se realizarán las iteraciones del método simplex hasta encontrar la solución óptima.
A continuación se adecuará el problema al modelo estándar de programación lineal, agregando las variables de holgura, exceso y/o artificiales en cada una de las restricciones y convirtiendo las inecuaciones en igualdades:
- Restricción 1: Tiene signo “≤” (menor igual), por lo tanto se agregará la variable de holgura S1. Esta variable se ubicará en la base en la matriz inicial.
- Restricción 2: Tiene signo “≤” (menor igual), por lo tanto se agregará la variable de holgura S2. Esta variable se ubicará en la base en la matriz inicial.
Ahora mostraremos el problema en la forma estándar. Se colocará el coeficiente 0 (cero) donde corresponda para crear nuestra matriz inicial:
Función Objetivo:
Maximizar Z = X1 + X2 + 0S1 + 0S2
Sujeto a:
- X1 + X2 + S1 + 0S2 = 4
- -X1 + X2 + 0S1 + S2 = 1
Matriz Inicial
Utilizaremos los coeficientes de las ecuaciones para elaborar nuestra primera tabla:
| Tabla 1 | Cj | 1 | 1 | 0 | 0 | |
|---|---|---|---|---|---|---|
| Cb | Base | X1 | X2 | S1 | S2 | R |
| 0 | S1 | 1 | 1 | 1 | 0 | 4 |
| 0 | S2 | -1 | 1 | 0 | 1 | 1 |
| Z | -1 | -1 | 0 | 0 | 0 |
a) Cálculo de Vector de Costes Reducidos (Z):
Los valores registrados en la fila Z se obtuvieron de la siguiente forma:
- Z1 = (Cb,1×X1,1) + (Cb,2×X1,2) - Cj,1 = (0×1) + (0×-1) - (1) = -1
- Z2 = (Cb,1×X2,1) + (Cb,2×X2,2) - Cj,2 = (0×1) + (0×1) - (1) = -1
- Z3 = (Cb,1×S1,1) + (Cb,2×S1,2) - Cj,3 = (0×1) + (0×0) - (0) = 0
- Z4 = (Cb,1×S2,1) + (Cb,2×S2,2) - Cj,4 = (0×0) + (0×1) - (0) = 0
- Z5 = (Cb,1×R1) + (Cb,2×R2) = (0×4) + (0×1) = 0
b) Condición de Optimalidad (Variable Entrante):
En el vector de costes reducidos (Z) tenemos valores negativos, por lo que debemos seleccionar el más negativo para la columna pivote (maximización).
En el vector Z (excluyendo el último valor), tenemos los siguientes números: [-1, -1, 0, 0]. El más negativo es = -1 que corresponde a la variable X1. Esta variable ingresará a la base y sus valores en la tabla conformarán nuestra columna pivote.
d) Condición de Factibilidad:
Se verificará la condición de factibilidad, dividiendo los valores de la columna R entre la columna pivote X1. Para procesar la división, el denominador debe ser estrictamente positivo (Si es cero o negativo se colocará N/A = No aplica). El menor valor definirá la variable que saldrá de la base:
- Fila S1 → R1 / X1,1 = 4 / 1 = 4 (Menor Valor)
- Fila S2 → R2 / X1,2 = 1 / -1 = NA
El menor valor corresponde a la fila de S1. Esta variable saldrá de la base. El elemento pivote corresponde al valor que cruza la columna X1 y la fila S1 = 1.
Ingresa la variable X1 y sale de la base la variable S1. El elemento pivote es 1
Aprende con explicaciones paso a paso
En Plan de Mejora nos esforzamos para ayudarte a superar esas materias complicadas de forma más fácil.
Membresía
Con el acceso a nuestra membresía tendrás acceso a 13 aplicativos para aprender proyectos, programación lineal, estadística entre otros.
¿Qué calculadoras incluyen?
Ruta Crítica PERT y CPM
Método Gráfico de Programación Lineal
Distribución Normal
Punto de Equilibrio y más
Adquiere nuestra suscripción mensual desde