Metodo simplex
Clase 20-04-23
Método Simplex
El método simplex es un procedimiento iterativo para resolver problemas
de programación lineal, donde se busca obtener la solución óptima de la
función objetivo que logre cumplir el conjunto de restricciones.
Este algoritmo fue desarrollado en el año 1947 por el matemático
norteamericano George Dantzig.
Conceptos Básicos
Para comprender de mejor manera el método simplex vamos a revisar algunas
definiciones.
El método parte de dos afirmaciones importantes:
El conjunto de posibles soluciones o conjunto factible de cualquier problema de
programación lineal puede representarse mediante un poliedro convexo.
Si un problema de programación lineal tiene una solución óptima y finita, ésta
estará en un vértice del poliedro convexo que representa al problema.
El algoritmo simplex parte de uno de los vértices del poliedro, y verifica si es el
óptimo; si no lo es, busca un nuevo vértice adyacentes que va mejorando el valor de
la función objetivo. Se continúa iterando hasta llegar al vértice que representa la
solución óptima.
Conceptos Básicos
En la siguiente imágen vemos el poliedro que representa la solución factible y cómo
realiza el recorrido el algoritmo simplex:
Pasos del Método Simplex
Los pasos a seguir en el método simplex son:
1. Definir el problema en la forma estándar y generar nuestra matriz.
2. Determinar la solución básica inicial.
3. Seleccionar la variable de entrada utilizando la condición de optimalidad.
Si no se puede seleccionar una variable de entrada, quiere decir que
estamos en la condición óptima y finalizan las iteraciones. De otro modo
se continúa con el siguiente paso.
4. Seleccionar la variable de salida utilizando la condición de factibilidad.
5. Actualizar nuestra matriz realizando las operaciones de Gauss-Jordan.
Volver al paso número 3.
Paso inicial Preparación para iniciar iteraciones
Paso Iterativo Realización de iteraciones
Condición de detención ¿Es óptima la solución actual?
Si no Si sí
Fin
El método simplex es un procedimiento algebraíco en el que cada
iteración contiene la solución de un sistema de ecuaciones para obtener
una nueva solución a la que se le aplica la prueba de optimalidad.
No obstante, también tiene una interpretación geométrica muy útil
OBTENCIÓN DE LA SOLUCIÓN
Uso del computador absolutamente necesario
Los modelos buscan optimizar (maximizar o minimizar)
Herbert Simon introduce el termino satisfizar
“La diferencia entre optimizar y satisfizar refleja la
diferencia entre la teoría y la realidad”
PROGRAMACIÓN LINEAL
Es un método matemático que se emplea para resolver problemas de optimización. En
palabras simples la P.L. busca asignar recursos limitados, entre actividades que compiten,
de la forma mas óptima posible.
Supuestos de la P.L.
•Proporcionalidad
•Aditividad
•Divisibilidad
•Certidumbre
•Objetivo único
•No negatividad
Modelo General de PL
Definición de variables:
Sea xj> = 0. ; j = 1, 2, 3....n
Función objetivo:
Max. o Min. z = C1X1 + C2X2 + ... + CjXj + ... + CnXn
Sujeto a restricciones: i = 1, 2, 3, ... , m
a11X1 + a12X2 + ... + a1jXj + ... + a1nXn = b1
a21X1 + a22X2 + ... + a2jXj + ... + a2nXn = b2
· .
· .
ai1X1 + ai2X2 + ... + aijXj + ... + ainXn = bi
· .
· .
am1X1 + am2X2 + ... + amjXj + ... + amnXn = bm
Condiciones de signo para variables: toda xj 0
m = # total de restricciones,
n = # de variables de decisión (originales)
Cj, aij y bi son constantes (o parámetros) dados.
8
Métodos de Resolución
Método Gráfico
Empleado principalmente para PPL con dos variables de decisión. Este
método se basa en la idea de obtener regiones de soluciones factibles
(RSF), en las cuales se encontraría la combinación de variables de
decisión que optimizan el modelo.
Método Algebraico (SIMPLEX)
Empleado principalmente para PPL con más de dos variables de
decisión. Este método se desarrollo con base en el método gráfico y
corresponde a un sistema heurístico, por lo cual requiere de una solución
inicial factible para empezar a funcionar.
8
Introducción
Un propiedad general del método simplex es que resuelve
la PL en iteraciones
Cada iteración desplaza la solución a un nuevo vértice que
tiene el potencial de mejorar el valor de la función objetivo
El proceso continua hasta que ya no se pueden obtener
mejoras
Espacio de soluciones en forma de ecuación
Para estandarizar, la representación algebraica del espacio de
soluciones de Programación Lineal se forma bajo dos condiciones:
• Todas las restricciones (excepto las de no negatividad) son
ecuaciones con lado derecho no negativo
• Todas las variables son no negativas.
Conversión de desigualdades a ecuaciones
• En las restricciones de < el lado derecho se puede pensar
como representando el límite de disponibilidad y el lado
izquierdo representaría el uso de ese recurso limitado por
parte de las actividades (variables) del modelo, la diferencia
entre ambos representa la cantidad no usado u holgura del
recurso
Conversión de desigualdades a ecuaciones
• Dada la restricción
6X1 + 4X2 < 24
6X1 + 4X2 + X3 = 24
• O bien
X1 + X2 > 800
X1 + X2 – X3 = 800
Cada slack (holgura) toma significado diferente, el algoritmo necesita de una artificial para
iterar
X1 + X2 – X3 + u = 800
Método gráfico Método algebraico
Grafica todas las restricciones, incluyendo Representa el espacio de soluciones con m
las de no negatividad ecuaciones con n variables, y restringe a
todas las variables a valores no negativos;
m<n
El espacio de soluciones consiste en una El sistema tiene infinidad de soluciones
infinidad de puntos esquina factibles factibles
Identifica puntos factibles de esquina del Determina las soluciones básicas
espacio de soluciones factibles de las ecuaciones
Los candidatos a la solución óptima Las candidatas a solución óptima
corresponden a una cantidad finita de corresponden a una cantidad finita de
puntos de esquina soluciones básicas factibles
Se usa la función objetivo para determinar Se usa la función objetivo para determinar
el punto esquina óptimo entre todos los el solución básica factible óptimo entre
candidatos todas las candidas
PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX
Esta es la forma estándar del modelo:
Función objetivo: c1·x1 + c2·x2 + ... + cn·xn OPTIMIZAR
Sujeto a:
a11·x1 + a12·x2 + ... + a1n·xn = b1
a21·x1 + a22·x2 + ... + a2n·xn = b2
...
am1·x1 + am2·x2 + ... + amn·xn = bm
x1,..., xn ≥ 0
Para ello se deben cumplir las siguientes condiciones:
El objetivo es de la forma de maximización o de minimización.
Todas las restricciones son de igualdad.
Todas las variables son no negativas.
Las constantes a la derecha de las restricciones son no negativas.
Métodos de Resolución
ALGEBRAICO SIMPLEX
El método símplex fue desarrollado en 1947 por el Dr. George Dantzig y conjuntamente con el
desarrollo de la computadora hizo posible la solución de problemas grandes planteados con la
técnica matemática de programación lineal.
El algoritmo denominado símplex es la parte medular de este método; el cual se basa en la
solución de un sistema de ecuaciones lineales con el conocido procedimiento de Gauss-Jordan y
apoyado con criterios para el cambio de la solución básica que se resuelve en forma iterativa
hasta que la solución obtenida converge a lo que se conoce como óptimo..
•El conjunto de soluciones factibles para un problema de P.L. es un conjunto convexo.
•La solución óptima del problema de programación lineal , si existe, es un punto extremo
(vértice) del conjunto de soluciones factibles.
•El número máximo de puntos extremos (vértices) por revisar en la búsqueda de la solución
óptima del problema es finito. 8
Métodos de Resolución
ALGEBRAICO SIMPLEX
Restricción mayor o igual (<)
Las restricciones de este tipo comúnmente determinan requerimientos
máximo disponible de recursos. En este caso se debe incorporar una
variable de cantidad no usada que representa el sobrante del máximo del
lado izquierdo, respecto del disponible del lado derecho ( cuanto falta para
utilizar todo el recurso).
Ej.
X1 + X2 < 800
X1 + X2 + S1 = 800
s1 ≥ 0
8
Métodos de Resolución ALGEBRAICO
Se una vez obtenida la F.E se esta en condiciones de iniciar el Simplex que nos permitirá encontrar la (s)
solución (es) del PPL.
Como el algoritmo se mueve de punto en punto extremo requiere que variables basicas entren y salgan. Las
reglas para seleccionar las variables de entrada y salida se conocen como condiciones de optimalidad y
factibilidad. Resumiendo:
A. Optimalidad: la variable de entrada en un problema de maximización es la variable no básica que tiene el
coeficiente mas negativo en el reglon de la F.O. los empates se rompen arbritariamente. Se llega al optimo
en la iteración donde todos coeficientes del reglon de la F.O. de las variables básicas son positivos.
B. Factibilidad: tanto para los problemas de maximización como minimización, la variable de salida es la
variable básica asociada con la razón no negativa más pequeña entre los “lados derecho” y los coeficientes
de la columna entrante.
8
Maximizar Minimizar
Variable que La más NEGATIVA de La más POSITIVA de los
entra los Cj – Zj Cj - Zj
Variable que Siendo b los valores Siendo b los valores bajo
sale bajo la celda solución la celda solución y a el
y a el valor valor correspondiente a
correspondiente a la la intersección entre b y
intersección entre b y la variable que entra. La
la variable que entra. más positiva de los b/a.
La menos positiva de
los b/a.
Métodos de Resolución
ALGEBRAICO
Pasos del Simplex:
Paso 0 : determinar la solución factible inicial.
Paso 1 : seleccione la variable de entrada empleando la condición de optimalidad.
Deténgase si no hay variable de entrada.
Paso 2 : seleccione una variable de salida utilizando la condición de factibilidad.
Paso 3 : determine las nuevas soluciones básicas empleando los calculos apropiados de Gauss
– Jordan, luego vuelva al paso 1.
8
EL PROBLEMA
Se fabrican dos artículos, cada uno consume para su fabricación 1 litro de
determinada materia prima, cuya disponibilidad es 10 litros. De otra materia de
la cual se dispone de 24 kg el primer artículo necesita 2 kg. y el segundo 3 kg. El
segundo artículo necesita 1m2 de papel metálico para su conservación, del cual
se dispone de 6 m2.
Los beneficios son $1 y $2 respectivamente
Plantear el modelo y hallar la solución que maximice las ganancias.
Métodos de Resolución
ALGEBRAICO
EJEMPLO
Las variables:
X1 = Cantidad de artículo 1 a producir (unidades)
X2 = Cantidad de artículo 2 a producir (unidades)
Las restricciones:
X1 + X2 < 10
2X1 + 3 X2 < 24
X2 < 6
El objetivo:
Z = 1X1 + 2X2 MAXIMIZAR
8
Métodos de Resolución
ALGEBRAICO
Agregando las variables slack a las restricciones:
1X1 + 1X2 + 1X3 =10
2X1 + 3 X2 +X4 = 24
X2 + X5 = 6
X1, X2, X3, X4, X5 ≥ 0
El objetivo:
Z = 1X1 + 2X2 +0X3 + 0X4 + 0X5 MAXIMIZAR
8
X1 X2 X3 X4 X5
1 1 1 0 0
A= 2 3 0 1 0
0 1 0 0 1
Resolvemos GRAFICAMENTE
Armemos las matrices
Las restricciones con las slack son:
1X1 X2 1X3 0X4 0X5 = 10
2X1 + 3 X2 + 0X3 + 1X4 + 0X5 = 24
0X1 X2 0X3 0X4 1X5 = 6
X1, X2, X3, X4, X5 ≥ 0
1 1 1 0 0 10
A= 2 3 0 1 0 B= 24
0 1 0 0 1 6
Primera tabla de simplex
Tabla 1 Cj 1 2 0 0 0
Xk Cb BASE X1 X2 X3 X4 X5
X3 0 10 1 1 1 0 0
X4 0 24 2 3 0 1 0
X5 0 6 0 1 0 0 1
Primera tabla de simplex
Tabla 1 Cj 1 2 0 0 0
Xk Cb BASE X1 X2 X3 X4 X5
X3 0 10 1 1 1 0 0
X4 0 24 2 3 0 1 0
X5 0 6 0 1 0 0 1
Z 0 -1 -2 0 0 0
Z = Cb * BASE, Cb * columna Ai - Cj
Calculo de fila del Z
Cb * Base : 0* 10 + 0*24 + 0* 6 = 0
Cb * columna Ai – Cj
Columna A1 (X1) = 0*1 +0*2+0*0 -1 = -1
Columna A2 (X2) = 0*1 +0*3+0*1 -2 = -2
Columna A3 (X3) = 0*1 +0*0+0*0 -0 = 0
Columna A4 (X4) = 0*1 +0*0+0*0 -0 = 0
Columna A5 (X5) = 0*1 +0*0+0*0 -0 = 0
Primera tabla de simplex
Tabla 1 Cj 1 2 0 0 0
Xk Cb BASE X1 X2 X3 X4 X5
X3 0 10 1 1 1 0 0
X4 0 24 2 3 0 1 0
X5 0 6 0 1 0 0 1
Z 0 -1 -2 0 0 0
Selección de la variable que entra
Calcular Indicador de salida
• BASE /Columna Seleccionada
En nuestro caso
BASE / Columna A2 (X2)
10/1 = 10
24/3 = 8
6/1 = 6
Primera tabla de simplex
Tabla
Cj 1 2 0 0 0
1
Xk Cb BASE X1 X2 X3 X4 X5 Q
X3 0 10 1 1 1 0 0 10
Selección de la
X4 0 24 2 3 0 1 0 8
variable que sale
X5 0 6 0 1 0 0 1 6
Z 0 -1 -2 0 0 0
Selección de la variable que entra
Como calculamos
La fila del pivot se divide por el pivot
La tercer fila se divide por 1
La columna del pivot se completa con ceros
Como regla la variable que está en la base intersección su
columna lleva 1 en ese lugar, el resto de la columna asociado se
completa con ceros.
Como calculamos A3
Como regla la variable que está en la base intersección su columna lleva 1 en ese lugar, el
resto de la columna asociado se completa con ceros
Como calculamos A4
Como regla la variable que está en la base intersección su columna lleva 1 en ese lugar, el
resto de la columna asociado se completa con ceros
Tabla
Cj 1 2 0 0 0
1
Xk Cb BASE X1 X2 X3 X4 X5
X3 0
X4 1
X2 0
Como calculamos
Los demás elementos de la tabla se calculan con la regla de
Gauss-Jordan
aij (nuevo) = aij (anterior) - aip (anterior) * apj (anterior)
app (anterior)
Donde:
aij = es una posición en la tabla (i es la fila, j la columna)
app= es el elemento pivot
Primera tabla de simplex
Tabla 1 Cj 1 2 0 0 0
Xk Cb BASE X1 X2 X3 X4 X5
10 1 1 1 0 0
X3 0
(a1b) (a11) (a12) (a13) (a14) (a15)
24 2 3 0 1 0
X4 0
(a2b) (a21) (a22) (a23) (a24) (a25)
6 0 0 0 1
X5 0 1 (app)
(a3b) (a31) (a33) (a34) (a35)
Z 0 -1 -2 0 0 0
Como calculamos
a1b (nuevo) = a1b (anterior) – a1p (anterior) * apb (anterior)
app (anterior)
a1b (nuevo) = 10 – 1*6 = 4
1
BASE X2
10 1
(a1b) (a12)
6 1
(a3b) (app)
Como calculamos
a2b (nuevo) = a2b (anterior) – a2p (anterior) * apb (anterior)
app (anterior)
a2b (nuevo) = 24 – 3*6 = 6
BASE X2
1
24 3
(a2b) (a22)
6
1 (app)
(a3b)
Como calculamos columna A1
a11 (nuevo) = a11 (anterior) – a1p (anterior) * ap1 (anterior)
app (anterior) 1 1
(a11) (a12)
a11 (nuevo) = 1 – 0*1 = 1
0 1
1 (a31) (app)
a21 (nuevo) = a21 (anterior) – a2p (anterior) * ap1 (anterior)
app (anterior)
2 3
a21 (nuevo) = 2 – 0*3 = 2 (a21) (a22)
1
0
1 (app)
(a31)
Como calculamos columna A5
a15 (nuevo) = a15 (anterior) – a1p (anterior) * ap1 (anterior)
app (anterior) 0 1
(a12) (ap5)
a15 (nuevo) = 0 – 1*1 = -1
1 1
1 (a1p) (app)
a25 (nuevo) = a25 (anterior) – a2p (anterior) * ap5 (anterior)
app (anterior) 0 3
a25 (nuevo) = 0 – 1*3 = -3 (a25) (ap5)
1 1
1 (app)
(a2p)
Primera ITERACION de simplex
Tabla 2
1 2 0 0 0
Xk Cb Base X1 X2 X3 X4 X5
X3 0 4 1 0 1 0 -1
X4 0 6 2 0 0 1 -3
X2 2 6 0 1 0 0 1
Z 12 -1 0 0 0 2
Primera ITERACION de simplex
Tabla 2
1 2 0 0 0
Xk Cb Base X1 X2 X3 X4 X5
X3 0 4 1 0 1 0 -1
X4 0 6 2 0 0 1 -3
X2 2 6 0 1 0 0 1
Z 12 -1 0 0 0 2
Segunda ITERACION de simplex
Tabla 3
1 2 0 0 0
Xk Cb Base X1 X2 X3 X4 X5
X3 0 1 0 0 1 -1 / 2 1/2
X1 1 3 1 0 0 1/2 -3 / 2
X2 2 6 0 1 0 0 1
Z 15 0 0 0 1/2 1/2
Reforzamos lo desarrollado
[Link]
Cambio del tipo de optimización
• Si en nuestro modelo, deseamos minimizar, podemos dejarlo tal y como está, pero deberemos tener
en cuenta nuevos criterios para la condición de parada (deberemos parar de realizar iteraciones
cuando en la fila del valor de la función objetivo sean todos menores o iguales a 0), así como para la
condición de salida de la fila. Con objeto de no cambiar criterios, se puede convertir el objetivo de
minimizar la función F por el de maximizar F·(-1).
• Ventajas: No deberemos preocuparnos por los criterios de parada, o condición de salida de filas, ya
que se mantienen.
• Inconvenientes: En el caso de que la función tenga todas sus variables básicas positivas, y además
las restricciones sean de desigualdad "≤", al hacer el cambio se quedan negativas y en la fila del
valor de la función objetivo se quedan positivos, por lo que se cumple la condición de parada, y por
defecto el valor óptimo que se obtendría es 0.
• Solución: En la realidad no existen este tipo de problemas, ya que para que la solución quedara por
encima de 0, alguna restricción debería tener la condición "≥", y entonces entraríamos en un
modelo para el método de las Dos Fases.
Todas las restricciones son de igualdad.
• Si en nuestro modelo aparece una inecuación con una desigualdad
del tipo "≥", deberemos añadir una nueva variable, llamada
variable de exceso si, con la restricción si ≥ 0. La nueva variable
aparece con coeficiente cero en la función objetivo, y restando en
las inecuaciones.
• Surge ahora un problema, veamos como queda una de nuestras
inecuaciones que contenga una desigualdad "≥" :
a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs = b1
Todas las restricciones son de igualdad.
• Como todo nuestro modelo, está basado en que todas sus variables
sean mayores o iguales que cero, cuando hagamos la primera
iteración con el método Simplex, las variables básicas no estarán en
la base y tomarán valor cero, y el resto el valor que tengan. En este
caso nuestra variable xs, tras hacer cero a x1 y x2, tomará el valor -b1.
No cumpliría la condición de no negatividad, por lo que habrá que
añadir una nueva variable, xr, que aparecerá con coeficiente cero en
la función objetivo, y sumando en la inecuación de la restricción
correspondiente.
Todas las restricciones son de igualdad
• Quedaría entonces de la siguiente manera:
a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs + 1 ·xr = b1
• Este tipo de variables se les llama variables artificiales, y aparecerán cuando
haya inecuaciones con desigualdad ("=","≥"). Esto nos llevará obligadamente
a realizar el método de las Dos Fases
• Del mismo modo, si la inecuación tiene una desigualdad del tipo "≤",
deberemos añadir una nueva variable, llamada variable de holgura si, con la
restricción si "≥" 0 . La nueva variable aparece con coeficiente cero en la
función objetivo, y sumando en las inecuaciones.
• A modo resumen podemos dejar esta tabla, según la desigualdad
que aparezca, y con el valor que deben estar las nuevas variables.
Tipo de variable que
Tipo de desigualdad
aparece
≥ - exceso + artificial
= + artificial
≤ + holgura
DESARROLLANDO EL MÉTODO SIMPLEX
• Una vez que hemos estandarizado nuestro modelo,
puede ocurrir que necesitemos aplicar el método
Simplex o el método de las Dos Fases. Véase en la
figura como debemos actuar para llegar a la
solución de nuestro problema.
Lo reforzamos con este video:
[Link]
=21lkV3r8r-4
PASO 5: Resolver el modelo utilizando software:
Algunas aplicaciones
1. PHPSimplex:
[Link]
1. Graficador para dos variables:
[Link]
1. Geogebra: [Link]
2. Optimezer PL IO:
[Link]