Investigación de Operaciones
RESUMEN DEL MÉTODO SIMPLEX
Clase 1
En el método simplex es un procedimiento 3. Las variables no básicas se igualan a cero.
general para resolver problemas de programación 4. Si las variables básicas satisfacen las
lineal. restricciones de no negatividad, la
solución básica es una solución básica.
A continuación, se detallará con un ejemplo la
aplicación del método simplex en el caso más Paso 1
sencillo: todas las restricciones tienen la forma ≤.
Preparación para el método simplex: constuir el
Problema prototípico: modelo aumentado introduciendo variables
artificiales.
Una variable de holgura es una variable que se
introduce para convertir las desigualdades de la
forma ≤ en igualdades. Paso 2
El modelo de la derecha recibe el nombre de Construir la tabla simplex inicial:
modelo aumentado.
Una solución aumentada es la solución de las
variables originales (las variables de decisión) que
se aumentó con los valores correspondientes a la
variable de holgura.
Una solución básica es una solución en un vértice
aumentada. Paso 3
Una solución básica factible es una solución Se seleccionan las variables de decisión como las
factible en un vértice aumentada. variables no básicas iniciales y las variables de
holgura como las variables básicas iniciales.
Los grados de libertad cuando se quiere resolver
un problema se calcula como el número de Prueba de optimalidad
variables menos el número de ecuaciones:
La solución básica es óptima si y sólo si todos los
coeficientes del renglón cero son no negativos.
Una solución básica tiene las siguientes Paso 4. Iteración 1.
propiedades:
1. Se determina la variable básica entrante
1. Cada variable se designa ya sea como con la selección de la variable con el
variable básica o variable no básica. coeficiente negativo que tiene el mayor
2. El número de variables básicas es igual al valor absoluto (es decir, el “más
número de restricciones funcionales. negativo”).
Investigación de Operaciones
2. Se determina la variable básica que sale Paso 5. Iteración 2.
con la prueba del cociente mínimo.
Se repiten los pasos desde la selección de la
Prueba del cociente mínimo:
variable básica entrante:
i. Elija los coeficientes estrictamente
positivos del renglón pivote.
ii. Divida el elemento del lado derecho del
mismo renglón entre dicho coeficiente.
iii. Identifique el renglón que tiene el menor
de estos cocientes.
iv. La variable básica de ese renglón es la
variable básica que sale; sustitúyala con la
variable básica entrante en la columna de
la variable básica de la siguiente tabla. Se repiten los pasos hasta cumplir la prueba
de optimalidad:
das
3. Despeja la nueva solución básica factible
mediante operaciones elementales con
renglones.
La solución también da el estado de los recursos.
Un recurso se designa como escaso si la variable
de holgura asociada es cero, es decir, las
Las operaciones son: actividades del modelo consumieron el recurso
i. Divida el renglón pivote entre el número completo. De lo contrario, si la holgura es positiva,
pivote. Use este nuevo renglón pivote en entonces el recurso es abundante.
los pasos siguientes. Ejercicio de práctica
ii. En los renglones (incluso del renglón 0) que
tienen un coeficiente negativo en la 𝑀𝑎𝑥 𝑍 = 5𝑥 + 4𝑥
columna pivote, se suma a este el producto Sujeto a:
del valor absoluto de este coeficiente por el
nuevo renglón pivote. 6𝑥 + 4𝑥 ≤ 24
iii.En el caso de los renglones que tienen un
𝑥 + 2𝑥 ≤ 6
coeficiente positivo en la columna pivote,
se les resta el producto de este coeficiente −𝑥 + 𝑥 ≤ 1
por el nuevo renglón pivote.
𝑥 ≤2
Realice la prueba de optimalidad.
𝑥 ,𝑥 ≥ 0
