Mathematics">
Modulo1 Algoritmo Símplex
Modulo1 Algoritmo Símplex
Modulo1 Algoritmo Símplex
1: Algoritmo Símplex
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑧 = 𝐶𝒙 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑧 = 𝐶𝒙
𝑠. 𝑎. 𝐴𝒙 ≤ 𝒃 𝑠. 𝑎. 𝐴𝒙 ≥ 𝒃
𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛 𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛
❑ Todo problema de Programación Lineal puede ser escrito en la forma canónica (o simétrica)
Formalización Programación Lineal: Forma Canónica o simétrica
𝑠. 𝑎. 2𝑥1 + 𝑥2 + 3𝑥3 ≤ 6 𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛
𝑥1 +4𝑥2 + 2𝑥3 ≥ 1
𝑥1 ≤ 0, 𝑥2 ≥ 0, 𝑥3 𝜖 ℝ
Formalización Programación Lineal: Forma Canónica o simétrica
𝑠. 𝑎. 2𝑥1 + 𝑥2 + 3𝑥3 ≤ 6 𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛
𝑥1 +4𝑥2 + 2𝑥3 ≥ 1
𝑥1 ≤ 0, 𝑥2 ≥ 0, 𝑥3 𝜖 ℝ
Cambios de variables:
𝑥1 = −𝑥1′
𝑥3 = 𝑥3+ − 𝑥3−
Formalización Programación Lineal: Forma Canónica o simétrica
𝑠. 𝑎. 2𝑥1 + 𝑥2 + 3𝑥3 ≤ 6 𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛
𝑥1 +4𝑥2 + 2𝑥3 ≥ 1
𝑥1 ≤ 0, 𝑥2 ≥ 0, 𝑥3 𝜖 ℝ
Cambios de variables:
𝑥1 = −𝑥1′
𝑥3 = 𝑥3+ − 𝑥3−
𝑠. 𝑎. 2𝑥1 + 𝑥2 + 3𝑥3 ≤ 6 𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛
𝑥1 +4𝑥2 + 2𝑥3 ≥ 1
𝑥1 ≤ 0, 𝑥2 ≥ 0, 𝑥3 𝜖 ℝ
Cambios de variables:
𝑥1 = −𝑥1′
𝑥3 = 𝑥3+ − 𝑥3−
𝑠. 𝑎. 2𝑥1 + 𝑥2 + 3𝑥3 ≤ 6 𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑛
𝑥1 +4𝑥2 + 2𝑥3 ≥ 1
𝑥1 ≤ 0, 𝑥2 ≥ 0, 𝑥3 𝜖 ℝ
Cambios de variables:
𝑥1 = −𝑥1′
𝑥3 = 𝑥3+ − 𝑥3−
𝑚𝑎𝑥 𝑧 = −5𝑥1′ + 2𝑥2 + 4(𝑥3+ −𝑥3− ) 𝑚𝑎𝑥 𝑧 = −5𝑥1′ + 2𝑥2 + 4𝑥3+ − 4𝑥3−
𝑠. 𝑎. −2𝑥1′ +𝑥2 + 3(𝑥3+ − 𝑥3− ) ≤ 6 𝑠. 𝑎. −2𝑥1′ +𝑥2 + 3𝑥3+ − 3𝑥3− ≤ 6
−𝑥1′ +4𝑥2 + 2(𝑥3+ −𝑥3− ) ≥ 1 𝑥1′ −4𝑥2 − 2𝑥3+ + 2𝑥3− ≤ −1
𝑥1′ ≥ 0, 𝑥2 ≥ 0, 𝑥3+ ≥ 0, 𝑥3− ≥ 0 𝑥1′ ≥ 0, 𝑥2 ≥ 0, 𝑥3+ ≥ 0, 𝑥3− ≥ 0
Formalización Programación Lineal: Estándar
❑Forma Estándar
❑ No hay ninguna desigualdad de tipo ≤ o ≥.
𝑂𝑝𝑡𝑖𝑚𝑖𝑧𝑎𝑟 𝑧 = 𝐶𝒙
❑ El vector de términos independientes debe ser
𝑠. 𝑎. 𝐴𝒙 = 𝒃
positivo 𝑏𝑖 ≥ 0.
𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑘
𝑏𝑖 ≥ 0 ∀ 𝑖 = 1, … , 𝑚 ❑ Todo problema de Programación Lineal puede
ser escrito en la forma estándar.
Formalización Programación Lineal: Estándar
❑Forma Estándar
❑ No hay ninguna desigualdad de tipo ≤ o ≥.
𝑂𝑝𝑡𝑖𝑚𝑖𝑧𝑎𝑟 𝑧 = 𝐶𝒙
❑ El vector de términos independientes debe ser
𝑠. 𝑎. 𝐴𝒙 = 𝒃
positivo 𝑏𝑖 ≥ 0.
𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑘
𝑏𝑖 ≥ 0 ∀ 𝑖 = 1, … , 𝑚 ❑ Todo problema de Programación Lineal puede
ser escrito en la forma estándar.
❑Variables de holgura
❑ Desigualdad de tipo ≤:
ℎ≥0
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 + ℎ = 𝑏
Formalización Programación Lineal: Estándar
❑Forma Estándar
❑ No hay ninguna desigualdad de tipo ≤ o ≥.
𝑂𝑝𝑡𝑖𝑚𝑖𝑧𝑎𝑟 𝑧 = 𝐶𝒙
❑ El vector de términos independientes debe ser
𝑠. 𝑎. 𝐴𝒙 = 𝒃
positivo 𝑏𝑖 ≥ 0.
𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑘
𝑏𝑖 ≥ 0 ∀ 𝑖 = 1, … , 𝑚 ❑ Todo problema de Programación Lineal puede
ser escrito en la forma estándar.
❑Variables de holgura
❑ Desigualdad de tipo ≤:
ℎ≥0
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 + ℎ = 𝑏
❑ Desigualdad de tipo ≥:
𝑒≥0
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≥ 𝑏2 𝑎1 𝑥1 + 𝑎2 𝑥2 + ⋯ + 𝑎𝑛 𝑥𝑛 − 𝑒 = 𝑏
Formalización Programación Lineal: Estándar
❑Forma Estándar
❑ No hay ninguna desigualdad de tipo ≤ o ≥.
𝑂𝑝𝑡𝑖𝑚𝑖𝑧𝑎𝑟 𝑧 = 𝐶𝒙
❑ El vector de términos independientes debe ser
𝑠. 𝑎. 𝐴𝒙 = 𝒃
positivo 𝑏𝑖 ≥ 0.
𝑥𝑗 ≥ 0 ∀ 𝑗 = 1, … , 𝑘
𝑏𝑖 ≥ 0 ∀ 𝑖 = 1, … , 𝑚 ❑ Todo problema de Programación Lineal puede
ser escrito en la forma estándar.
❑ Desigualdad de tipo ≤:
ℎ≥0
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 + ℎ = 𝑏
❑ Desigualdad de tipo ≥:
𝑒≥0
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≥ 𝑏2 𝑎1 𝑥1 + 𝑎2 𝑥2 + ⋯ + 𝑎𝑛 𝑥𝑛 − 𝑒 = 𝑏
Formalización Programación Lineal: Forma Estándar
❑Solución básica
❖ La forma estándar de un Programa Lineal:
𝑜𝑝𝑡 𝑧 = 𝐶𝒙
𝑠. 𝑎. 𝐴𝒙 = 𝑏
𝒙≥0
❖ En general:
En este ejemplo:
𝑚=2
m𝑎𝑥 𝑧 = 𝑥1 + 2𝑥2 − 3𝑥3 𝑛=5
𝑠. 𝑎. 2𝑥1 + 𝑥2 + 3𝑥3 + ℎ1 = 6
El número de variables es mayor que el número de ecuaciones, por tanto,
−𝑥1 + 2𝑥2 − 4𝑥3 − ℎ2 = 1
tendremos un sistema compatible indeterminado con infinitas soluciones.
𝑥𝑖 ≥ 0 ∀ 𝑖 = 1,2,3
ℎ𝑖 ≥ 0 ∀ 𝑖 = 1,2 𝑚<𝑛
Soluciones básicas
❖ Definamos:
𝑥 𝐵 como el vector de variables básicas: 𝑥 𝐵 𝜖 ℝ𝑚 .
𝑥 𝑆 como el vector de variables no básicas (o secundarias): 𝑥 𝑆 𝜖 ℝ𝑛−𝑚 .
𝐵 como la submatriz de 𝐴 que corresponde con las columnas de las variables básicas: 𝐵 𝜖 ℝ𝑚∗𝑚 .
Ejemplo
En Forma estándar:
max 𝑧 = 6𝑥1 + 8𝑥2 2𝑥1 + 𝑥2 = 6
min 𝑧 = 6𝑥1 + 8𝑥2
𝑠. 𝑎. 𝑥1 + 2𝑥2 ≤ 6
𝑠. 𝑎. 𝑥1 + 2𝑥2 + ℎ1 = 6
2𝑥1 + 𝑥2 ≤ 6 𝑥1 +2𝑥2 = 6
2𝑥1 + 𝑥2 + ℎ2 = 6
𝑥𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑥𝑖 ≥ 0, ℎ𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑛=4 Hay 𝑛 − 𝑚 variables no básicas.
𝑚=2 Hay 𝑚 variables básicas
Pasos para obtener una solución básica:
Ejemplo
En Forma estándar:
max 𝑧 = 6𝑥1 + 8𝑥2 2𝑥1 + 𝑥2 = 6
min 𝑧 = 6𝑥1 + 8𝑥2
𝑠. 𝑎. 𝑥1 + 2𝑥2 ≤ 6
𝑠. 𝑎. 𝒙𝟏 + 𝟐𝒙𝟐 + ℎ1 = 6
2𝑥1 + 𝑥2 ≤ 6 𝑥1 +2𝑥2 = 6
𝟐𝒙𝟏 + 𝒙𝟐 + ℎ2 = 6
𝑥𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑥𝑖 ≥ 0, ℎ𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑛=4 Hay 𝑛 − 𝑚 variables no básicas.
𝑚=2 Hay 𝑚 variables básicas
Pasos para obtener una solución básica:
Ejemplo
En Forma estándar:
max 𝑧 = 6𝑥1 + 8𝑥2 2𝑥1 + 𝑥2 = 6
min 𝑧 = 6𝑥1 + 8𝑥2
𝑠. 𝑎. 𝑥1 + 2𝑥2 ≤ 6
𝑠. 𝑎. 𝑥1 + 2𝑥2 + 𝒉𝟏 = 6
2𝑥1 + 𝑥2 ≤ 6 𝑥1 +2𝑥2 = 6
2𝑥1 + 𝑥2 + 𝒉𝟐 = 6
𝑥𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑥𝑖 ≥ 0, ℎ𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑛=4 Hay 𝑛 − 𝑚 variables no básicas.
𝑚=2 Hay 𝑚 variables básicas
Pasos para obtener una solución básica:
Ejemplo
En Forma estándar:
max 𝑧 = 6𝑥1 + 8𝑥2 2𝑥1 + 𝑥2 = 6
min 𝑧 = 6𝑥1 + 8𝑥2
𝑠. 𝑎. 𝑥1 + 2𝑥2 ≤ 6
𝑠. 𝑎. 𝑥1 + 2𝑥2 + ℎ1 = 6
2𝑥1 + 𝑥2 ≤ 6 𝑥1 +2𝑥2 = 6
2𝑥1 + 𝑥2 + ℎ2 = 6
𝑥𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑥𝑖 ≥ 0, ℎ𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑛=4 Hay 𝑛 − 𝑚 variables no básicas.
𝑚=2 Hay 𝑚 variables básicas
Pasos para obtener una solución básica:
Ejemplo
En Forma estándar:
max 𝑧 = 6𝑥1 + 8𝑥2 2𝑥1 + 𝑥2 = 6
min 𝑧 = 6𝑥1 + 8𝑥2
𝑠. 𝑎. 𝑥1 + 2𝑥2 ≤ 6
𝑠. 𝑎. 𝑥1 + 2𝑥2 + ℎ1 = 6
2𝑥1 + 𝑥2 ≤ 6 𝑥1 +2𝑥2 = 6
2𝑥1 + 𝑥2 + ℎ2 = 6
𝑥𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑥𝑖 ≥ 0, ℎ𝑖 ≥ 0 ∀ 𝑖 = 1,2
𝑛=4 Hay 𝑛 − 𝑚 variables no básicas.
𝑚=2 Hay 𝑚 variables básicas
Pasos para obtener una solución básica:
𝑥 𝐵 = 𝑥1 , ℎ2 𝑥 𝑆 = 𝑥2 , ℎ1 = (0,0)
𝑥1 +2𝑥2 + ℎ1 = 6
2𝑥1 + 𝑥2 + ℎ2 = 6 𝑥 = 𝑥1 , 𝑥2 , ℎ1 , ℎ2 = 6,0,0, −6 es una solución básica
Soluciones básicas
𝑥 𝐵 = 𝑥1 , ℎ2 𝑥 𝑆 = 𝑥2 , ℎ1 = (0,0)
No es una solución factible.
𝑥1 +2𝑥2 + ℎ1 = 6
2𝑥1 + 𝑥2 + ℎ2 = 6 𝑥 = 𝑥1 , 𝑥2 , ℎ1 , ℎ2 = 6,0,0, −6 es una solución básica
Soluciones básicas y factibles
F B
Soluciones básicas y factibles
F B
Soluciones básicas factibles
❖ Geométricamente, estaremos buscando entre los vértices de la región factible. Nos iremos moviendo
entre las soluciones básicas factibles adyacentes, en las direcciones que sean favorables.
1. Seleccionar una variable no básica (o secundaria) para entrar en el conjunto de variables básicas.
2. Seleccionar una variable básica para salir del conjunto de variables básicas.
Ejemplo: 𝑥 𝐵 = 𝑥2 , 𝑥3 , 𝑥4
𝑥 𝐵 = 𝑥1 , 𝑥2 , 𝑥3
𝑥 𝑆 = 𝑥4 , 𝑥5 𝑥 𝑆 = 𝑥1 , 𝑥5
Algoritmo Símplex
❖ Geométricamente, estaremos buscando entre los vértices de la región factible. Nos iremos moviendo
entre las soluciones básicas factibles adyacentes, en las direcciones que sean favorables.
1. Seleccionar una variable no básica (o secundaria) para entrar en el conjunto de variables básicas.
2. Seleccionar una variable básica para salir del conjunto de variables básicas.
Ejemplo: 𝑥 𝐵 = 𝑥2 , 𝑥3 , 𝑥4
𝑥 𝐵 = 𝑥1 , 𝑥2 , 𝑥3
𝑥 𝑆 = 𝑥4 , 𝑥5 𝑥 𝑆 = 𝑥1 , 𝑥5
❖ Preguntas pendientes:
➢ ¿Como podemos determinar las direcciones que sean favorables?
➢ ¿Cuándo sabré que mi solución es Óptima?
Algoritmo Símplex
❑ Algoritmo Símplex
❖ Podemos escribir una restricción en función de 𝑥 𝐵 y de 𝑥 𝑠 :
𝑛+𝑚
❑ Algoritmo Símplex
❖ Podemos escribir una restricción 𝑖 en función de 𝑥 𝐵 y de 𝑥 𝑠 :
𝑛+𝑚
❖ Podemos modificar las ecuaciones de tal manera que por cada restricción tengamos una
variable básica (misma lógica que la Eliminación Gaussiana).
❑ Algoritmo Símplex
❖ Podemos escribir una restricción en función de 𝑥 𝐵 y de 𝑥 𝑠 :
𝑛+𝑚
❖ Podemos modificar las ecuaciones de tal manera que por cada restricción tengamos una
variable básica (misma lógica que la Eliminación Gaussiana).
❑ Algoritmo Símplex
❖ Podemos escribir una restricción en función de 𝑥 𝐵 y de 𝑥 𝑠 :
𝑛+𝑚
❖ Podemos modificar las ecuaciones de tal manera que por cada restricción tengamos una
variable básica (misma lógica que la Eliminación Gaussiana).
❑ Algoritmo Símplex
❖ La función objetivo se puede definir solo en función de las variables secundarias:
❖ Definamos 𝑧0 y 𝑍𝑗 como:
𝑧 = 𝑧0 − (𝑍𝑗 − 𝐶𝑗 )𝑥𝑖𝑆
𝑖 ∈𝑥 𝑠
Algoritmo Símplex
❖ Nos puede dar una pista de cómo va a variar 𝑧 si una de estas variables entra como variable básica en la iteración 𝑘 + 1.
❖ Por definición: 𝑥𝑖𝑆 ≥ 0. Son los términos 𝑍𝑗 − 𝐶𝑗 los que van a determinar si existe una dirección más favorable:
𝑧 = 𝑧0 − 𝑍𝑗 − 𝐶𝑗 𝑥𝑖𝑆
𝑖 ∈𝑥 𝑠
Algoritmo Símplex
❖ Nos puede dar una pista de cómo va a variar 𝑧 si una de estas variables secundarias 𝑥𝑖𝑠 entra como variable básica.
❖ Por definición: 𝑥𝑖𝑆 ≥ 0. Son los términos 𝑍𝑗 − 𝐶𝑗𝑆 los que van a determinar si existe una dirección más favorable:
𝑧 = 𝑧0 − 𝑍𝑗 − 𝐶𝑗𝑆 𝑥𝑖𝑆
𝑖 ∈𝑥 𝑠
❖ Si al cabo de 𝐾 iteraciones todos los 𝑍𝑗 − 𝐶𝑗 cumplen : 𝑍𝑗 − 𝐶𝑗𝑆 ≥ 0:
❖ Nos puede dar una pista de cómo va a variar 𝑧 si una de estas variables secundarias 𝑥𝑖𝑠 entra como variable básica.
❖ Por definición: 𝑥𝑖𝑆 ≥ 0. Son los términos 𝑍𝑗 − 𝐶𝑗𝑆 los que van a determinar si existe una dirección más favorable:
𝑧 = 𝑧0 − 𝑍𝑗 − 𝐶𝑗𝑆 𝑥𝑖𝑆
𝑖 ∈𝑥 𝑠
❖ Si al cabo de 𝐾 iteraciones todos los 𝑍𝑗 − 𝐶𝑗 cumplen : 𝑍𝑗 − 𝐶𝑗𝑆 ≥ 0:
𝑧 tiene un máximo en 𝑧0𝐾 !
Criterio de Optimalidad:
❑ Objetivo Maximización: 𝑍𝑗 − 𝐶𝑗 ≥ 0 ∀𝑗
❑ Objetivo Minimización: 𝑍𝑗 − 𝐶𝑗 ≤ 0 ∀𝑗
Ejemplo:
𝐵 = 𝐼. * 𝑥 𝐵 = 𝐵 −1 𝑏 = 𝐼 𝑏 = 𝑏 = (6,8)
Tabla Inicial
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑧0 =
Algoritmo Símplex: Forma Tabular
Coeficientes de la restricción 1
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 1 2 1 0
ℎ2
𝑧0 =
Algoritmo Símplex: Forma Tabular
Coeficientes de la restricción 2
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 1 2 1 0
ℎ2 2 1 0 1
𝑧0 =
Algoritmo Símplex: Forma Tabular
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 1 2 1 0
ℎ2 0 2 1 0 1
𝑧0 =
Algoritmo Símplex: Forma Tabular
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0
ℎ2 0 8 2 1 0 1
𝑧0 =
Algoritmo Símplex: Forma Tabular
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0
ℎ2 0 8 2 1 0 1
𝑧0 = -2 -3 0 0
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0
ℎ2 0 8 2 1 0 1
𝑧 =0 -2 -3 0 0
Algoritmo Símplex
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0
ℎ2 0 8 2 1 0 1
𝑧 =0 -2 -3 0 0
Algoritmo Símplex
𝑏𝑠 𝑏𝑖
𝑥𝑠 𝑡𝑎𝑙 𝑞𝑢𝑒 = 𝑚𝑖𝑛 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎𝑖𝑒 > 0
𝑎𝑠𝑒 𝑎𝑖𝑒
Algoritmo Símplex
𝑏𝑠 𝑏𝑖
𝑥𝑠 𝑡𝑎𝑙 𝑞𝑢𝑒 = 𝑚𝑖𝑛 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎𝑖𝑒 > 0
𝑎𝑠𝑒 𝑎𝑖𝑒
𝑉𝐵𝑖
Tabla Inicial 2 3 0 0
𝑎𝑖𝑒
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0 6/2 = 3
ℎ2 0 8 2 1 0 1 8/1 = 8
𝑧 =0 -2 -3 0 0
Algoritmo Símplex
𝑏𝑠 𝑏𝑖
𝑥𝑠 𝑡𝑎𝑙 𝑞𝑢𝑒 = 𝑚𝑖𝑛 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎𝑖𝑒 > 0
𝑎𝑠𝑒 𝑎𝑖𝑒
𝑉𝐵𝑖
Tabla Inicial 2 3 0 0 𝑚𝑖𝑛 𝑎 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎𝑖𝑒 > 0
𝑖𝑒
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0 6/2 = 3 𝑺𝒂𝒍𝒆 𝒉𝟏
ℎ2 0 8 2 1 0 1 8/1 = 8
𝑧 =0 -2 -3 0 0
Algoritmo Símplex
𝑏𝑠 𝑏𝑖
𝑥𝑠 𝑡𝑎𝑙 𝑞𝑢𝑒 = 𝑚𝑖𝑛 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎𝑖𝑒 > 0
𝑎𝑠𝑒 𝑎𝑖𝑒
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2 𝑥𝑒 = 𝑥2 (𝑉𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝐸𝑛𝑡𝑟𝑎𝑛𝑡𝑒)
ℎ1 0 6 1 2 1 0 6/2 = 3 𝑥𝑠 = ℎ1 (𝑉𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝑆𝑎𝑙𝑖𝑒𝑛𝑡𝑒)
ℎ2 0 8 2 1 0 1 8/1 = 8
𝑧 =0 -2 -3 0 0
Algoritmo Símplex
𝑏𝑠 𝑏𝑖
𝑥𝑠 𝑡𝑎𝑙 𝑞𝑢𝑒 = 𝑚𝑖𝑛 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎𝑖𝑒 > 0
𝑎𝑠𝑒 𝑎𝑖𝑒
Tabla Inicial 2 3 0 0
𝑥𝑒 = 𝑥2 (𝑉𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝐸𝑛𝑡𝑟𝑎𝑛𝑡𝑒)
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0 6/2 = 3 𝑥𝑠 = ℎ1 (𝑉𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝑆𝑎𝑙𝑖𝑒𝑛𝑡𝑒)
ℎ2 0 8 2 1 0 1 8/1 = 8
𝑧 =0 -2 -3 0 0
Algoritmo Símplex
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0 𝐹1
ℎ2 0 8 2 1 0 1 𝐹2
𝑧 =0 -2 -3 0 0
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 ½ 1 ½ 0
ℎ2 0 8 2 1 0 1
Algoritmo Símplex
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0 𝐹1
ℎ2 0 8 2 1 0 1 𝐹2
𝑧 =0 -2 -3 0 0
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 ½ 1 ½ 0
ℎ2 0 8 2 1 0 1
Algoritmo Símplex
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0 𝐹1
ℎ2 0 8 2 1 0 1 𝐹2
𝑧 =0 -2 -3 0 0
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1
Algoritmo Símplex
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0 𝐹1
ℎ2 0 8 2 1 0 1 𝐹2
𝑧 =0 -2 -3 0 0
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1 𝐹2 → 𝐹2 − 1𝐹1
Algoritmo Símplex
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
Tabla Inicial 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
ℎ1 0 6 1 2 1 0 𝐹1
ℎ2 0 8 2 1 0 1 𝐹2
𝑧 =0 -2 -3 0 0
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1 𝐹2 → 𝐹2 − 1𝐹1
Algoritmo Símplex
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1 𝐹2 → 𝐹2 − 1𝐹1
𝑧0 = 9
Algoritmo Símplex
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
❑ Calculamos el valor de 𝑧0 para esta iteración.
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1 𝐹2 → 𝐹2 − 1𝐹1
𝑧0 = 9
𝑧0 = 𝐶𝑖𝐵 𝑏𝑖 = 3 ∗ 3 + 0 ∗ 5 = 9
𝑖𝜖𝑥 𝐵
Algoritmo Símplex
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
❑ Calculamos el valor de 𝑧0 para esta iteración.
❑ Calculamos los valores de los coeficientes 𝑍𝑗 − 𝐶𝑗 .
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1 𝐹2 → 𝐹2 − 1𝐹1
𝑧0 = 9
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
❑ Calculamos el valor de 𝑧0 para esta iteración.
❑ Calculamos los valores de los coeficientes 𝑍𝑗 − 𝐶𝑗 .
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1 𝐹2 → 𝐹2 − 1𝐹1
𝑧0 = 9 -1/2
𝑧0 = 𝐶𝑖𝐵 𝑏𝑖 1 3 1
𝑍𝑥1 − 𝐶𝑥1 = 𝐶𝑖𝐵 𝑎𝑖1 − 𝐶𝑥1 =3∗ +0∗ −2=−
𝑖𝜖𝑥 𝐵 2 2 2
𝑖𝜖𝑥 𝐵
Algoritmo Símplex
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
❑ Calculamos el valor de 𝑧0 para esta iteración.
❑ Calculamos los valores de los coeficientes 𝑍𝑗 − 𝐶𝑗 .
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1 𝐹2 → 𝐹2 − 1𝐹1
𝑧0 = 9 -1/2 0
𝑧0 = 𝐶𝑖𝐵 𝑏𝑖
𝑖𝜖𝑥 𝐵
𝑍𝑥2 − 𝐶𝑥2 = 𝐶𝑖𝐵 𝑎𝑖2 − 𝐶𝑥2 = 3 ∗ 1 + 0 ∗ 0 − 3 = 0
𝑖𝜖𝑥 𝐵
Algoritmo Símplex
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
❑ Calculamos el valor de 𝑧0 para esta iteración.
❑ Calculamos los valores de los coeficientes 𝑍𝑗 − 𝐶𝑗 .
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1 𝐹2 → 𝐹2 − 1𝐹1
𝑧0 = 9 -1/2 0 3/2
𝑧0 = 𝐶𝑖𝐵 𝑏𝑖 1
𝑍ℎ1 − 𝐶ℎ1 = 𝐶𝑖𝐵 𝑎𝑖3 − 𝐶ℎ1 = 3 ∗ + 0 ∗ −1/2 − 0 = 3/2
𝑖𝜖𝑥 𝐵 2
𝑖𝜖𝑥 𝐵
Algoritmo Símplex
❑ Debemos modificar el sistema de tal manera que todas las variables 𝑎𝑖𝑗 𝑥𝑗 = 𝑥𝑖𝐵
básicas de cada restricción tengan un coeficiente unitario.
𝑗 ∈𝑥 𝐵
❑ Calculamos el valor de 𝑧0 para esta iteración.
❑ Calculamos los valores de los coeficientes 𝑍𝑗 − 𝐶𝑗 .
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0 𝐹1 → 𝐹1 /2
ℎ2 0 5 3/2 0 -1/2 1 𝐹2 → 𝐹2 − 1𝐹1
𝑧0 = 9 -1/2 0 3/2 0
𝑧0 = 𝐶𝑖𝐵 𝑏𝑖
𝑍ℎ2 − 𝐶ℎ2 = 𝐶𝑖𝐵 𝑎𝑖4 − 𝐶ℎ2 = 3 ∗ 0 + 0 ∗ 1 − 0 = 0
𝑖𝜖𝑥 𝐵
𝑖𝜖𝑥 𝐵
Algoritmo Símplex
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0
ℎ2 0 5 3/2 0 -1/2 1
𝑧0 = 9 -1/2 0 3/2 0
Entra 𝒙𝟏 .
Algoritmo Símplex
𝑏𝑠 𝑏𝑖
𝑥𝑠 𝑡𝑎𝑙 𝑞𝑢𝑒 = 𝑚𝑖𝑛 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎𝑖𝑒 > 0
𝑎𝑠𝑒 𝑎𝑖𝑒
Iteración 1 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
3
𝑥2 3 3 1/2 1 1/2 0 1/2
=6 10 10
5
min 6, =
3 3
ℎ2 0 5 3/2 0 -1/2 1 3/2
= 10/3
𝑧0 = 9 -1/2 0 3/2 0
Sale 𝒉𝟐 .
Algoritmo Símplex
𝑧0 = 9 -1/2 0 3/2 0
Pivote
Iteración 2 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0
𝑥1 2 5 3/2 0 -1/2 1
Algoritmo Símplex
𝑧0 = 9 -1/2 0 3/2 0
Pivote 2
𝐹2 → 𝐹2
3
Iteración 2 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 3 1/2 1 1/2 0
𝑥1 2 10/3 1 0 -1/3 2/3
Algoritmo Símplex
𝑧0 = 9 -1/2 0 3/2 0
Pivote 2 1
𝐹2 → 𝐹2 𝐹1 → 𝐹1 − 𝐹2
3 2
Iteración 2 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 4/3 0 1 2/3 -1/3
𝑥1 2 10/3 1 0 -1/3 2/3
𝑧0 = 32/3
Algoritmo Símplex
Iteración 2 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 4/3 0 1 2/3 -1/3
𝑥1 2 10/3 1 0 -1/3 2/3
𝑧0 = 32/3
𝑧0 = 𝐶𝑖𝐵 𝑏𝑖
𝑖𝜖𝑥 𝐵
Algoritmo Símplex
Iteración 2 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 4/3 0 1 2/3 -1/3
𝑥1 2 10/3 1 0 -1/3 2/3
𝑧0 = 32/3 0 0 4/3 1/3
10 4
Para la segunda iteración 𝑥 (2) = 𝑥1 , 𝑥2 , ℎ1 , ℎ2 = , , 0,0 .
3 3
El valor de la función objetivo es 𝑧 = 32/3.
Criterio de Optimalidad:
❑ Objetivo Maximización: 𝑍𝑗 − 𝐶𝑗 ≥ 0 ∀𝑗
❑ Objetivo Minimización: 𝑍𝑗 − 𝐶𝑗 ≤ 0 ∀𝑗
Algoritmo Símplex
Iteración 2 2 3 0 0
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 4/3 0 1 2/3 -1/3
𝑥1 2 10/3 1 0 -1/3 2/3
𝑧0 = 32/3 0 0 4/3 1/3
10 4
Para la segunda iteración 𝑥 (1) = 𝑥1 , 𝑥2 , ℎ1 , ℎ2 = , , 0,0 .
3 3
El valor de la función objetivo es 𝑧 = 32/3.
Criterio de Optimalidad:
¡ 𝑧 ya no puede crecer más!
❑ Objetivo Maximización: 𝑍𝑗 − 𝐶𝑗 ≥ 0 ∀𝑗
Esta es la solución óptima del PL
❑ Objetivo Minimización: 𝑍𝑗 − 𝐶𝑗 ≤ 0 ∀𝑗
Algoritmo Símplex
Iteración 2 2 3 0 0 𝑥1
B 𝐶𝐵 𝑉𝐵 𝑥1 𝑥2 ℎ1 ℎ2
𝑥2 3 4/3 0 1 2/3 -1/3
𝑥1 2 10/3 1 0 -1/3 2/3
𝑧0 = 32/3 0 0 4/3 1/3 𝑥2
10 4
❑ La solución óptima es 𝑥 ∗ = 𝑥1 , 𝑥2 , ℎ1 , ℎ2 = , , 0,0
3 3 𝑥0
4 1 32
𝑧 + ℎ1 + ℎ2 =
3 3 3