06

MÉTODO SIMPLEX
Investigación Operativa I

El método simplex comienza con la siguiente
estructura:
Forma Canónica
Opt

 
Z C * X

(a )

s.a :
  
A * X b

x 0

(a) Función lineal llamada función objetivo,
donde el concepto de optimización puede ser
maximizar o minimizar

(b )

(b) Restricciones de desigualdad

(c )

(c) Restricciones de no negatividad

Notación:


A= Matriz decoeficientes de las variables en el sistema de ecuaciones


X = Vector solución


b


C

= Lado derecho de la restricción i. Corresponde a la cantidad de recurso disponible
= Vector de costo o utilidades .Corresponde a la contribución a Z por unidad de
actividad

Reglas de la Programación Lineal:
Regla Nº1:

max
Z 3 x1  8 x 2 
min
 Z  3 x1  8 x 2

Reglas de la Programación Lineal:
Regla Nº2:

3x1  8 x 2 20

 3 x1  8 x 2  20

Reglas de la Programación Lineal:
Regla Nº3:

10 x1  3 x2 7

10 x1  3 x2 7
10 x1  3 x2 7

Reglas de la Programación Lineal:
Regla Nº4:

10 x1
7 x1

 x2
 2 x2

 5
 1

x1 , x2 0

10 x1



7 x1

 2 x2

x1 , x2 0
y1 , y2 0

x2

 y1

 5


y2

 1

Reglas de la Programación Lineal:
Regla Nº4:

Reglas de la Programación Lineal:
Regla Nº5:
Unavariable no restringida, que toma toda clase de valores: negativos, ceros y
positivos, se puede escribir como la diferencia de dos variables no negativas.

x1 : variable no restrigida
x1  x2  x3

x2  x3  x1 0
x2  x3  x1  0
x2  x3  x1  0

Terminología Básica:
a.- Región de Soluciones Factibles (RSF): es el conjunto de valores, en el
cual se encuentran todas las soluciones factibles.b.- Solución del Problema: se llama solución a cualquier especificación de
valores para las variables de decisión (X1, X2,…, Xn) sin importar si es una
solución deseable o, incluso, admisible.
c.- Solución Factible: es el valor de las variables de decisión (X1, X2 ,…, Xn)
que satisface todas las restricciones.
d.- Solución Básica: es una solución que está en el vértice, la cual puede ser
factible ono.
e.- Solución Básica Factible: es una solución factible que se encuentra en un
vértice.
f.- Solución Óptima: es una solución básica factible que tiene el valor más
favorable de la función objetivo.

Por Ejemplo:

La solución básica factible (S.B.F) está en los vértices ABC.
Por lo tanto, una solución óptima a un problema de programación lineal (PPL)
estará contenida en el conjunto desoluciones básicas factibles.
Existe un número finito de S.B.F. y, por lo tanto, teóricamente es posible concebir
una solución óptima, entonces para obtener la solución habrá que ver en teoría
qué valor tiene la función objetivo y seleccionar la mejor. Esto puede convertirse
en una tarea bastante ardua, si se tiene en cuenta que una región factible con n
incógnitas y m restricciones puede tener un númeromáximo de:  n 
n!
  
puntos extremos
 m  m!(n  m)!

n 
n!
  
 m  m!(n  m)!
Dónde n > m, para que exista un espacio de soluciones factibles mayor que un
sólo punto, es decir, que las restricciones sean linealmente independientes (l.i.)
Por ejemplo: Si n = 50 y m = 30 =

4.7129 * 1013 puntos extremos a analizar.

Las técnicas más eficientes aplicadas para resolver conjunto deecuaciones
simultáneas son los procedimientos iterativos. El método simplex consiste en
examinar las soluciones básicas factibles. En cada iteración, el método simplex
pasa de una solución factible inicial a otra solución factible y, finalmente, en un
número finito de pasos (iteraciones) llega a una solución básica factible
óptima. Como la función objetivo (Z) debe ser mejorada (o por lo menos, noempeorada) en cada paso, el número de soluciones básicas factibles que debe
ser examinado antes de encontrar una solución óptima es mucho más reducido
que el número total de soluciones básicas factibles que existe.

Forma matricial del método simplex:
Cuando se inicia el método simplex, la forma matricial del conjunto de
ecuaciones es el siguiente:

1
0


-C
A

Z 
0    0
X   
...