Clase6_metodo simplex

Universidad Nacional de Colombia
Sede Medellín

Clase # 6

EL MÉTODO SIMPLEX
1.Restricciones de Desigualdad
2.Procedimiento algebraico
.

6-1

1. Restricciones de Desigualdad
El método
algebraico:
resolver un
conformado
funcionales.

simplex es un procedimiento
las soluciones se obtienen al
sistema de ecuaciones lineales
a partir de las restricciones

El sistema de ecuaciones lineales se
obtieneal convertir cada desigualdad de
la forma original, en una igualdad
equivalente.
6-2

1.1 Restricciones del tipo <=

Variable de holgura:
Es una variable, no negativa, que se
adiciona al lado izquierdo de una
restricción funcional de desigualdad del
tipo , para convertirla en una igualdad
equivalente.
Veamos un ejemplo
6-3

En el ejemplo de la Wyndor.
Primera restricción:

Sea X3

X1  4

loque le falta a X1 para ser igual a 4

De ahí que X1  4 es equivalente a:

X1 + X 3 = 4

Donde X3  0
6-4

Características de las Variables de
Holgura
• Coeficientes de costo iguales a cero.
• Coeficientes Tecnológicos:
1 - En su restricción correspondiente
0 - En todas las otras restricciones
• Conforman una columna de la matriz
Identidad
• Sirven para completar la base
• Tienen un significadoreal
• Pueden aparecer en la solución óptima
6-5

1.2 Forma Aumentada del modelo
Forma original
Max Z = 3X1 + 5X2
Sujeto a

X1

Forma aumentada
Max Z = 3X1 + 5X2
Sujeto a

4
2X2  12

3X1 + 2X2  18
X1 , X 2  0

X1

+ X3
2X2

3X1 + 2X2

=4
+X4

= 12

+X5= 18

X1 , X2, X3, X4, X5  0
6-6

Solución aumentada:
Es una solución para las variables originales
(variables de decisión), que se haaumentado
con los valores correspondientes de las
variables de holgura

Ejemplo
Solución sistema
original

(3,2)

Solución sistema
aumentado

(3,2,1,8,5)
X3, X4, X5
6-7

Solución básica: (en un vértice)
Es una solución aumentada localizada en un
vértice.

Ejemplo

Solución en el vértice
Sistema Original
(4,6)

Sistema Aumentado
(4,6,0,0,-6)
X3=0, la solución está sobre la restricción frontera R1
X4=0, lasolución está sobre la restricción frontera R2

 El punto está en la intersección entre las Restricciones
frontera R1 y R2.
6-8

Solución Básica:
Un sistema que posea, por ejemplo,
m = 3 ecuaciones con n = 5 variables
(incluyendo las de decisión y de
holgura)

tiene 2 grados de libertad:
Por lo que se puede dar valores
arbitrarios a 2 de las variables y
luego resolver el sistema para las
otras3.
6-9

Si se asigna el valor de 0, arbitrariamente,
a 2 de las variables y se resuelve el
sistema para las otras 3,
a estas 3 variables se les denominará
variables básicas.
Esto corresponde a una solución en un
vértice, o una solución básica .

6-10

1.3 Clasificación de variables:
Básicas y No básicas
1. Cada variable (de decisión o de
holgura) puede clasificarse en básica o
no básica.

2. Enun sistema con
n variables y
m restricciones, donde n > m,
habrá:

m:

variables básicas

n - m: variables no básicas,
(iguales a cero, por definición)
sigue

6-11

3. Las variables básicas obtienen su valor
al solucionar el sistema de m ecuaciones.
4. Si los valores de las variables básicas
satisfacen la condición de no negatividad
se les denomina soluciones básicas
factibles.

Ejemplo:
SistemaOriginal

(4,3)

Sistema Aumentado

(4,3,0,6,0)
Solución Básica Factible

veamos
6-12

Ejemplo
sistema original

Sistema aumentado

(0,6,4,0,6)

(0,6)

Variables no básicas
R1

10 x

Variables básicas

2

9
8
(0,6)

7
6
5
4

R2

3
2

1
0

R3
1

2

3

4

5

6

7

8

9

10
x1

6-13

¿Cuántas soluciones en un vértice existen?

n
m

=

(n)!
m! (n –m)!

n: número de variables
m: número derestricciones funcionales
Ejemplo de la Wyndor: n = 5 y m = 3
existirán:
5!
2!3!

= 10 soluciones en el
vértice
6-14

Teorema
Dos soluciones básicas factibles son
adyacentes entre sí, si tienen todas las
V.N.B menos 1 comunes.

Ejemplo
(0,0)
(0,0,4,12,18)

(0,6)
(0,6,4,0,6)

Comparten todas las variables no básicas menos una.
6-15

EL MÉTODO SIMPLEX

2. Procedimiento algebráico
1. Hallar una solución...