MÉTODOS DE SOLUCIÓN DE
PROGRAMACIÓN LINEAL
Ing. Danna Betancourt
MÉTODO SIMPLEX
La transición de la solución del punto esquina geométrico del método
gráfico hasta el método símplex implica un procedimiento de cómputo
que determina en forma algebraica los puntos esquina.
Esto se logra convirtiendo primero a todas las restricciones de
desigualdad en ecuaciones, para después manipular esas ecuaciones
en una forma sistemática.
Una propiedad general del método símplex es que resuelve la
programación lineal en iteraciones. Cada iteración desplaza la solución
a un nuevo punto esquina que tiene potencial de mejorar el valor de la
función objetivo.
MÉTODO SIMPLEX
El método Simplex se basa en la siguiente propiedad:
“Si la función objetivo, f, no toma su valor máximo en el vértice A,
entonces hay una arista que parte de A, a lo largo de la cual f aumenta”
Este método sólo trabaja para restricciones que tengan un
tipo de desigualdad "≤" y coeficientes independientes
mayores o iguales a 0, y habrá que estandarizar las
mismas para el algoritmo. En caso de que aparezcan (o no
varíen) restricciones del tipo "≥" o "=" habrá que emplear
otros métodos como el método de las Dos Fases o de la
gran M.
CONVERSIÓN DE DESIGUALDADES
Para convertir una desigualdad (≤) en ecuación, se agrega una variable de
holgura al lado izquierdo de la restricción. Por ejemplo, en el modelo de Reddy
Mikks:
6𝑥1 + 4𝑥2 ≤ 24 𝑅𝑒𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑 𝑚á𝑥𝑖𝑚𝑎 𝑝𝑎𝑟𝑎 𝑀1
Si se define 𝑆1 como la holgura, o cantidad no usada, de M1, la restricción se
puede convertir en la siguiente ecuación:
6𝑥1 + 4𝑥2 + 𝑆1 = 24, 𝑆1 ≥ 0
CONVERSIÓN DE DESIGUALDADES
Una restricción (≥) establece, normalmente, un límite inferior para las
actividades del modelo de programación lineal. Como tal, la cantidad por la
que el lado izquierdo es mayor que el límite mínimo (lado derecho) representa
un excedente.
La conversión de (≥) a (=) se logra restando una variable de excedencia, del lado
izquierdo de la desigualdad.
𝑥1 + 𝑥2 ≥ 800 𝑥1 + 𝑥2 − 𝑆1 = 800, 𝑆1 ≥ 0
CONVERSIÓN DE DESIGUALDADES
Las variables de holgura y de excedencia SIEMPRE son NO NEGATIVAS.
Ahora bien, el lado derecho de la ecuación debe ser NO NEGATIVO. Esta
condición se puede satisfacer siempre, si es necesario multiplicando ambos
lados de la ecuación resultante por –1.
−𝑥1 + 𝑥2 ≤ −3
−𝑥1 + 𝑥2 + 𝑆1 = −3, 𝑆1 ≥ 0
× (−𝟏) 𝑥1 − 𝑥2 − 𝑆1 = 3, 𝑆1 ≥ 0
ESTRUCTURA DEL MÉTODO SIMPLEX
Se deben cumplir las siguientes condiciones: 𝑍𝑚á𝑥 = 18.5𝑥1 + 20𝑥2
0.05𝑥1 + 0.05𝑥2 ≤ 1100
0.05𝑥1 + 0.10𝑥2 ≤ 1800
Desigualdad (≤) → Variable de holgura
0.10𝑥1 + 0.05𝑥2 ≤ 2000
𝑥1 , 𝑥2 ≥ 0
El modelo convertido a forma estándar:
𝑍𝑚á𝑥 = 18.5𝑥1 + 20𝑥2 + 𝑠1 + 𝑠2 + 𝑠3
0.05𝑥1 + 0.05𝑥2 + 0𝑠1 = 1100
0.05𝑥1 + 0.10𝑥2 + 0𝑠2 = 1800
0.10𝑥1 + 0.05𝑥2 + 0𝑠3 = 2000
ESTRUCTURA DEL MÉTODO SIMPLEX
Se deben cumplir las siguientes condiciones: 𝑍𝑚𝑖𝑛 = 50𝑥1 + 20𝑥2 + 30𝑥3 + 80𝑥4
400𝑥1 + 200𝑥2 + 150𝑥3 + 500𝑥4 ≥ 500
3𝑥1 + 2𝑥2 ≥6
Desigualdad (≥) → Variable de excedencia
2𝑥1 + 2𝑥2 + 4𝑥3 + 4𝑥4 ≥ 10
2𝑥1 + 4𝑥2 + 𝑥3 + 5𝑥4 ≥8
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 ≥0
El modelo convertido a
𝑍𝑚á𝑥 = 50𝑥1 + 20𝑥2 + 30𝑥3 + 80𝑥4 − 0𝑒1 − 0𝑒2 − 0𝑒3 − 0𝑒4
forma estándar:
400𝑥1 + 200𝑥2 + 150𝑥3 + 500𝑥4 − 𝑒1 = 500
3𝑥1 + 2𝑥2 −𝑒2 =6
2𝑥1 + 2𝑥2 + 4𝑥3 + 4𝑥4 − 𝑒3 = 10
2𝑥1 + 4𝑥2 + 𝑥3 + 5𝑥4 − 𝑒4 = 8
PROPIEDADES DEL MÉTODO SIMPLEX
Esta nueva forma “estándar” es mucho más conveniente para la manipulación
algebraica y la identificación de soluciones. Se le da el nombre de “forma
aumentada” del problema porque se aumentó con algunas variables
suplementarias para poder aplicar el método simplex. Para esto se cumple
que:
Condición Significado de la condición
Si una variable de holgura es = 0 La solución se encuentra sobre la
frontera de la restricción
correspondiente.
Si una variable de holgura es > 0 La solución se encuentra sobre el lado
factible la frontera de la restricción
correspondiente.
Si una variable de holgura es < 0 La solución se encuentra sobre el lado
no factible la frontera de la restricción
correspondiente.
EJEMPLO – APLICACIÓN DE PROPIEDADES DEL
MÉTODO SIMPLEX
EJEMPLO – APLICACIÓN DE PROPIEDADES DEL
MÉTODO SIMPLEX
(0, 0), (0, 6), (2, 6), (4, 3) y (4, 0) son las soluciones factibles
en los vértices = soluciones FEV
(0, 9), (4, 6) y (6, 0) se llaman soluciones no factibles en un
vértice.
(2, 6) es la solución óptima sólo porque su valor
correspondiente de Z=36
EJEMPLO – APLICACIÓN DE PROPIEDADES DEL
MÉTODO SIMPLEX
Dado el siguiente caso:
𝑍𝑚á𝑥 = 3𝑥1 + 5𝑥2 𝑍𝑚á𝑥 = 3𝑥1 + 5𝑥2 + 0𝑆1 + 0𝑆2 + 0𝑆3
𝑥1 ≤4 𝐹𝑜𝑟𝑚𝑎 𝑒𝑠𝑡á𝑛𝑑𝑎𝑟 𝑥1 + 𝑠1 =4
2𝑥2 ≤ 12 /𝑎𝑢𝑚𝑒𝑛𝑡𝑎𝑑𝑎 2𝑥2 + 𝑠2 = 12
3𝑥1 + 2𝑥2 ≤ 18
3𝑥1 + 2𝑥2 + 𝑠3 = 18
𝑥1 ≥ 0
𝑥1 ≥ 0
𝑥2 ≥ 0 𝑥2 ≥ 0
𝑠1 ≥ 0
𝑠2 ≥ 0
EJEMPLO – APLICACIÓN DE PROPIEDADES DEL
MÉTODO SIMPLEX 𝑍𝑚á𝑥 = 3𝑥 + 5𝑥 1 2
3 + 𝑠1 = 4
Una solución aumentada es una
𝑠1 = 4 − 3
solución de las variables originales 𝑠1 = 1
(las variables de decisión) que se
aumentó con los valores 2𝑥2 + 𝑠2 = 12
correspondientes de las variables de 2(2) + 𝑠2 = 12
holgura. 4 + 𝑠2 = 12
𝑠2 = 12 − 4
𝑠2 = 8
Si se aumenta la solución (3,2), 3𝑥1 + 2𝑥2 + 𝑠3 = 18
entonces se obtiene una solución 3 3 + 2(2) + 𝑠3 = 18
aumentada (3, 2, 1, 8, 5). 9 + 4 + 𝑠3 = 18
𝑠3 = 18 − 13
𝑠3 = 5
EJEMPLO – APLICACIÓN DE PROPIEDADES DEL
MÉTODO SIMPLEX
Una solución básica es una solución
en un vértice aumentada.
Considere la solución no factible del
vértice (4, 6). Al aumentarla con los
valores que se obtuvieron para las
variables de holgura 𝑠1 = 0, 𝑠2 = 0 y
𝑠3 = −6
Se obtiene la solución básica
correspondiente (4, 6, 0, 0, -6).
Verifíquelo.
EJEMPLO – APLICACIÓN DE PROPIEDADES DEL
MÉTODO SIMPLEX
Una solución básica factible (BF)
es una solución FEV aumentada.
Así, la solución FEV (0, 6) del
ejemplo es equivalente a la solución
BF (0, 6, 4, 0, 6) del problema en la
forma aumentada. Verifíquelo.
EJEMPLO – APLICACIÓN DE PROPIEDADES DEL
MÉTODO SIMPLEX
Una solución básica factible (BF)
es una solución FEV aumentada.
Así, la solución FEV (0, 6) del
ejemplo es equivalente a la solución
BF (0, 6, 4, 0, 6) del problema en la
forma aumentada. Verifíquelo.
NÚMERO DE SOLUCIONES
Si denotamos por n el número de variables en el modelo en forma estándar y
por m el número de restricciones, decimos que el modelo en forma estándar
es de dimensiones n por m.
Un sistema de ecuaciones lineales simultaneas de m por n puede tener
solución o no. En general puede ocurrir uno de tres situaciones:
1. Tener una única solución.
2. Tener infinitas soluciones.
3. No tener solución → Sistema inconsistente.
En un modelo de programación lineal en forma estándar siempre se cumple
que m < n.
NÚMERO DE SOLUCIONES
Si las m ecuaciones producen una solución única, entonces estas m variables
asociadas se llaman variables básicas y las n – m variables restantes se
conocen como variables no básicas.
Si todas las variables básicas toman valores mayores o iguales a cero,
entonces la solución es factible.
Número máximo de
soluciones básicas para m
ecuaciones con n incógnitas
EJEMPLO - NÚMERO DE SOLUCIONES
𝑍𝑚á𝑥 = 𝑥1 + 𝑥2 + 𝑥3 𝑍𝑚á𝑥 = 𝑥1 + 𝑥2 + 0𝑆1 + 0𝑆2 + 0𝑆3
𝑠. 𝑎 𝑠. 𝑎
𝑥1 ≤ 5 𝐹𝑜𝑟𝑚𝑎 𝑒𝑠𝑡á𝑛𝑑𝑎𝑟
/𝑎𝑢𝑚𝑒𝑛𝑡𝑎𝑑𝑎
𝑥1 + 𝑠1 =5
𝑥2 ≤ 5 𝑥2 +𝑠2 =5
𝑥3 ≤ 5 𝑥3 +𝑠3 = 5
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
1 0 0 1 0 0
𝐴= 0 1 0 0 1 0 ; 𝑛!
𝑛
0 0 1 0 0 1 𝑚
=
𝑚! 𝑛 − 𝑚 !
𝑥 𝑇 = 𝑥1 , 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3
𝑛 6!
𝑐 𝑇 = 1,1,1,0,0,0 𝑚 = = 20
3! 6 − 3 !
𝑏𝑇 = 5,5,5
MÉTODO SIMPLEX – FORMATO TABLEAU
Conceptos:
Resuelva según formato Tableau el siguiente ejercicio de maximización:
𝑍𝑚á𝑥 = 3𝑥1 + 5𝑥2
𝑠. 𝑎
𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0
MÉTODO SIMPLEX – FORMATO TABLEAU
Conceptos:
En forma automática se sabe que las variables (𝑥1 , 𝑥2 ) son variables no básicas.
Mientras que las variables (𝑥3 , 𝑥4 , 𝑥5 ) son variables básicas o lo que es lo mismo (𝑆1 , 𝑆2 , 𝑆3 ) .
MÉTODO SIMPLEX – FORMATO TABLEAU
Conceptos:
La forma tabular del método símplex utiliza una tabla símplex para desplegar de manera
compacta el sistema de ecuaciones que conduce a la solución Básica Factible (BF) actual.
De acuerdo con esta solución, cada variable de la columna de la izquierda es igual al número
correspondiente en la columna de la derecha (y las variables que no aparecen son iguales a
cero).
Cuando se realiza la prueba de optimalidad o una iteración, los únicos números relevantes
son los que están a la derecha de la columna Z.
El término renglón se refiere a una fila horizontal de números a la derecha de la columna
Z (que incluyen el número del lado derecho), donde el renglón i corresponde a la ecuación (i).
MÉTODO SIMPLEX – FORMATO TABLEAU
Pasos Enfoque Algebraico:
Paso Inicial: Se introducen las variables de holgura. Se seleccionan las variables de
decisión como las variables no básicas iniciales (es decir, iguales a cero) y las variables de
holgura como las variables básicas iniciales.
Ejemplo: la solución BF inicial es (0, 0, 4, 12, 18).
Prueba de optimalidad: La solución BF es óptima si y sólo si todos los coeficientes del
renglón 0 son no negativos (≥ 0). Si es así, el proceso se detiene; de otra manera, sigue a una
iteración para obtener la siguiente solución BF, que incluye cambiar una variable no básica a
básica.
Ejemplo: De acuerdo con la función objetivo, 𝑍 = 3𝑥1 + 5𝑥2 , si aumenta 𝑥1 y 𝑥2 el valor de Z
aumenta. Entonces la solución BF no es óptima. Estos coeficientes se muestran en el
renglón 0 de la tabla.
MÉTODO SIMPLEX – FORMATO TABLEAU
Pasos Enfoque Algebraico:
Paso 1: Se determina la variable básica entrante con la selección de la variable (que
de modo automático es no básica) con el coeficiente negativo que tiene el mayor valor
absoluto (es decir, el coeficiente “más negativo”)
Ejemplo:
El coeficiente más negativo es
-5 para 𝑥2 (-5 <- 3), de manera
que 𝑥2 debe convertirse
en variable básica.
NOTA: Recuerda que
inicialmente 𝑥2 es variable
NO BÁSICA.
MÉTODO SIMPLEX – FORMATO TABLEAU
Pasos Enfoque Algebraico:
Paso 2: Se determina la variable básica que sale con la prueba del cociente mínimo
Prueba del cociente mínimo:
1. Elije los coeficientes estrictamente positivos ( > 0) de la columna pivote.
2. Divide el elemento del lado derecho del mismo renglón entre dicho coeficiente.
3. Identifica el renglón que tiene el menor de estos cocientes.
4. La variable básica de ese renglón es la variable básica que sale; sustitúyela con la
variable básica entrante en la columna de la variable básica de la siguiente tabla.
MÉTODO SIMPLEX – FORMATO TABLEAU
Pasos Enfoque Algebraico:
Ejemplo:
Renglón pivote
Entonces 𝑥4 es la variable básica que Columna pivote
sale. Así 𝑥2 sustituye a 𝑥4 como la
variable básica del renglón 2.
MÉTODO SIMPLEX – FORMATO TABLEAU
Pasos Enfoque Algebraico:
Ejemplo:
Valores de la
nueva variable 𝑥2
Número pivote
MÉTODO SIMPLEX – FORMATO TABLEAU
Pasos Enfoque Algebraico:
Paso 3: Se despeja la nueva solución BF mediante operaciones elementales con
renglones
1. Divide el renglón pivote entre el número pivote. Use este nuevo renglón pivote en los
pasos 2 y 3 (paso que se visualizó anteriormente, donde se obtuvo el nuevo renglón).
2. En los renglones (incluso el renglón 0) que tienen un coeficiente negativo en la
columna pivote, se suma a este renglón el producto del valor absoluto de este
coeficiente por el nuevo renglón pivote.
3. En el caso de los renglones que tienen un coeficiente positivo en la columna pivote,
se les resta el producto de este coeficiente por el nuevo renglón pivote.
MÉTODO SIMPLEX – FORMATO TABLEAU
Pasos Enfoque Algebraico:
Encontrar el nuevo
Ejemplo: renglón (0):
El nuevo renglón 2:
(0 1 0 1/2 0 6)
se multiplica por 5:
(0 5 0 5/2 0 30)
Al renglón 1 (en donde se
encuentra el coeficiente -5 que
deseamos eliminar)se le resta el
nuevo renglón (sombreado en
color rojo):
(-3 -5 0 0 0 0)
(0 5 0 5/2 0 30)
-------------------------------
(-3 0 0 5/2 0 30)
MÉTODO SIMPLEX – FORMATO TABLEAU
Pasos Enfoque Algebraico:
Ejemplo:
Encontrar el nuevo
renglón (3):
El nuevo renglón 2:
(0 1 0 1/2 0 6)
se multiplica por 2:
(0 2 0 1 0 12)
Al renglón 3 se le resta el nuevo
renglón (sombreado en color rojo):
(3 2 0 0 1 18)
(0 2 0 1 0 12)
-------------------------------
(3 0 0 -1 1 6)
MÉTODO SIMPLEX – FORMATO TABLEAU
Pasos Enfoque Algebraico:
Ejemplo:
MÉTODO SIMPLEX – FORMATO TABLEAU
Conceptos:
MÉTODO SIMPLEX – FORMATO TABLEAU
Conceptos:
Condición de optimalidad (Columna Pivote):
La variable de entrada corresponde al costo reducido (Cj – Zj) más alejado del cero positivo
para problemas de maximización y negativo para problemas de minimización.
Condición de Factibilidad (fila pivote):
Tanto para los problemas de maximización como los problemas de minimización la variable de
salida es la variable básica asociada con la razón 𝜃𝑖 más pequeña. Los empates se rompen
arbitrariamente.
Prueba de Optimalidad:
El proceso termina cuando todos los Cj – Zj son cero o negativos en los problemas de
maximización y ceros o positivos en los problemas de minimización.
MÉTODO SIMPLEX – FORMATO TABLEAU
Conceptos:
¿Cuándo se
¿Qué valor buscar
Tipo de problema alcanza la Columna pivote
en Cj−Zj ?
óptima?
Mayor valor positivo Valor más positivo (más
Maximización Cuando todos ≤ 0
(mayor a 0) alejado de cero +)
Mayor valor negativo,
Valor más negativo (más
Minimización es decir, más Cuando todos ≥ 0
alejado de cero -)
negativo (menor a 0)
