Modelaci+on ybSimulación

UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE INGENIERA
ESCUELA SISTEMAS Y COMPUTACIÓN

MODELACIÓN Y SIMULACIÓN
INTEGRANTES:
Janneth Guamán
Mayra Villacres

Quinto Sistemas y Computación

UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE INGENIERIA
ESCUELA SISTEMAS Y COMPUTACION

OBJETIVOS
OBJETIVO GENERAL
 Analizar la aplicación on-line Simplex Algorithm Calculator.
OBJETIVOESPECIFICO
 Realizar un ejercicio práctico para conocer el funcionamiento del algoritmo Simplex.
 Conocer ciertas ventajas del programa.
 Analizar el tiempo de ejecución para resolver el problema en la aplicación on line.

Modelación y Simulación

2

UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE INGENIERIA
ESCUELA SISTEMAS Y COMPUTACION

DESARROLLO
ALGORITMO SIMPLEX
Conceptos yPrincipios Básicos
El Algoritmo del Simplex cuya invención se debe a George Dantzig en 1947 y le valió en 1975 la
Medalla Nacional de la ciencia es el principal método para resolver problemas de
programación lineal.

Dado un problema de programación lineal en forma estándar que llamaremos P:
Min Ctx
Sujeto a
Ax = b
x≥0
Donde
A∈ Mmxn, con rango(A)=m, b∈Rm, C∈Rn
La idea básica delalgoritmo del Simplex es realizar iteraciones entre los puntos extremos del
conjunto factible x1, x2, ...,xs hasta que se cumpla una cierta condición que se llama "criterio de
optimalidad", si se cumple en digamos, xk entonces esa será la solución que estamos buscando.
Esto es debido a que si el problema P tiene solución optima finita en x de la Teoría de la
k
Programación Lineal sabemos que xkestará entre los puntos extremos del conjunto factible, S.
Modelación y Simulación

3

UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE INGENIERIA
ESCUELA SISTEMAS Y COMPUTACION

TEORÍA EN EXTENSIÓN
Dado el problema P, supongamos que tenemos x, punto extremo de S. Sabemos por la
teoría este punto extremo será una solución de la forma
x = [B-1b, 0]t, con B submatriz de A rango m.
Sea ahoraw otro punto de la región factible, S. Entonces
Aw = b, es decir
BwB + NwN = b
Como B es invertible se tiene
wB = B-1b - B-1NwN
Aplicando Ct a w
t
t
t
t -1
-1
t
C w = CB wB + CN wN = CB (B b - B NwN) + CN wN
Por ser w, punto de la región factible, sabemos que
w ≥ 0, esto implica que si x fuera la solución óptima, se tendría que
N
CNt - CBtB-1N > 0

(1)

Esta es la idea básicadel algoritmo del simplex a la que nos referíamos antes, también
se llamacriterio de optimalidad.
CRITERIO DE OPTIMALIDAD DEL ALGORITMO DEL SIMPLEX
CNt - CBt B-1 N > 0
Si se cumple esta condición entonces x será la solución óptima.
La ecuación del criterio de optimalidad tiene como coordenadas
cj - CBtB-1 aj = cj - CBtyj = cj - zj
Siendo a , columna de N.
j
En Resumen, el criterio deoptimalidad es

Modelación y Simulación

4

UNIVERSIDAD NACIONAL DE CHIMBORAZO
FACULTAD DE INGENIERIA
ESCUELA SISTEMAS Y COMPUTACION

zj - cj < 0, con zj = CBt B-1 aj
Supongamos ahora que (1) no se cumple, es decir
CNt - CBt B-1 N ≥ 0

(2)

Entonces hay dos posibilidades.
1)yj = B-1aj ≤ ∀j , entonces podemos construir
x = w + λ dj, siendo dj = (-B-1aj, ej)t
Sabemos que dj es unadirección extrema del conjunto factible S, en particular
Ad = 0
j
por tanto
x = w + λ dj es también solución factible ∀ λ ≥ 0.
Por otro lado
t
t
t
t -1
t
C x = C w + λdj = C w + λ(-C B aj) dj = C w - λ(zj - cj) → -∞ cuando λ → ∞
Esto quiere decir que podemos hacer la solución tan pequeña como queramos sin salirnos del
conjunto factible S, por tanto estamos en el caso de solución es noacotada.
-1
2) El vector y = B a tiene alguna componente positiva. Entonces podemos construir otra
j
j
solución factible (la cual estará también dentro del conjunto de puntos extremos de S) en la
que la función es más pequeña. La nueva solución se construye así
x = w + λdj
siendo dj = (-B-1aj ej)t
-1
y siendo λ = min{β/yij : yij > 0}, β = B b.
Con este valor λ, x es solución factible y...