investigacion de operaciones

El Método Simplex
Investigación de Operaciones I
Universidad Industrial de Santander
R.J. Acosta-Amado
2015-1

Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS BASICOS
• 

Línea de frontera
de
una
restricción:
Son
los puntos () en
los
cuales
la
restricción es una
igualdad.
2

Material Elaborado por: Aura Lucia Ortiz Sanabria– Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS BASICOS
• 

Región
factible:
Sea el conjunto S
definido
como
Entonces S es la
región factible del
problema
de
programación
lineal.
3

Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS BASICOS

Soluciones en el
vértice: Son los
puntos
de
intersección
de
dosrestricciones.

4
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS BASICOS

Soluciones
factibles en el
vértice: Son los
puntos extremos
de
la
región
factible.
5
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS BASICOS

Variables
Básicas: Son las
variablesdistintas de cero,
en una solución
básica factible.
6
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS BASICOS

Variables
no
básicas: Son las
variables iguales
a
cero,
están
fuera de la base
(en una solución
básica factible)
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por:Rolando

7

 

EJEMPLO

 
FORMA ESTANDAR

FORMA AUMENTADA

8
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS DE SOLUCIÓN
CS1  El Método Simplex analiza
únicamente las soluciones factibles en el
vértice
CS2  El Método Simplex es un Algoritmo
Iterativo (Procedimiento sistemático que
repite una secuencia fija de pasos hasta
alcanzarun objetivo)
9
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS DE SOLUCIÓN
ALGORITMO ITERATIVO DEL MÉTODO SIMPLEX

• NO

10
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS DE SOLUCIÓN

CS3 Siempre que es posible, El Método
Simplex inicia en el origen.
•Las variables originales del modelos son = 0
• Las variables de holgura son iguales al lado
derecho de la correspondiente restricción.

11
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

CONCEPTOS DE SOLUCIÓN
CS4  Dada una solución factible en el
vértice (Computacionalmente) es mas fácil
reunir información de las soluciones
factiblesen el vértice adyacentes.
• El método simplex utiliza únicamente información
de las SFEV adyacentes a la solución FEV actual.

12
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

EJEMPLO
• 

 

 

 

SFEV

SBFEV

 
 
 

 
 

 

13
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: RolandoMETODO SIMPLEX EN FORMA
TABULAR
 

Es la implementación en tablas del método
algebraico visto hasta ahora.
1. Llevar el modelo a la Forma Aumentada
2. Llevar el modelo a la Forma Simplex
Adecuada
(0)
(1)
(2)
(3)
14
Material Elaborado por: Aura Lucia Ortiz Sanabria – Monitora Métodos de Optimización

Revisado por: Rolando

METODO SIMPLEX EN FORMA
TABULAR
3. Realizar la prueba de optimalidad:consiste en
revisar en el renglón cero que las variables no
básicas
no
tengan
coeficientes
negativos/positivos
cuando
se
maximiza/minimiza Si no se cumple esta
prueba de debe volver a iterar.
4. Elegir la variable básica saliente (La de menor
coeficiente cuando se maximiza y la de mayor
cuando se minimiza)
5. Elegir la variable básica entrante (según el
criterio de la razón mínima, el cual...