Metodo Simplex

Ingeniería Forestal
Taller de Introducción a la
Investigación de Operaciones

Método Simplex

Introducción
El Método Simplex es un método analítico de
solución de problemas de programación lineal
capaz de resolver modelos más complejos que
los resueltos mediante el método gráfico sin
restricción en el número de variables.
Es un método iterativo que permite ir mejorando
la solución en cada paso.11/09/2014

Ingeniería Forestal

2

Introducción (II)
El método consiste en “caminar” del vértice de un
poliedro a un vértice vecino de manera que
aumente o disminuya (según el contexto de la
función objetivo, sea maximizar o minimizar),
dado que el número de vértices que presenta un
poliedro solución es finito siempre se hallará
solución.

11/09/2014

Ingeniería Forestal

3

Historia
Métodofue creado en el año de 1947 por el
estadounidense George Bernard Dantzig y el
ruso Leonid Vitalievich Kantorovich[1], con el
ánimo de crear un algoritmo capaz de solucionar
problemas de m restricciones y n variables.

[1] Premio Nobel 1975

11/09/2014

Ingeniería Forestal

4

Variables de Holgura y Exceso
●

●

El Método Simplex trabaja basándose en
ecuaciones.
Hay que convertir las inecuacionesque
representan las restricciones iniciales en
ecuaciones
utilizando
unas
variables
denominadas de holgura y exceso .

11/09/2014

Ingeniería Forestal

5

Variables de Holgura y Exceso (II)

11/09/2014

Ingeniería Forestal

6

Variables de Holgura y Exceso
(III)

11/09/2014

Ingeniería Forestal

7

Variable Artificial
●

●

●

Una variable artificial es un truco matemático para
convertirinecuaciones ">=" en ecuaciones.
La característica principal de estas variables es que no
deben formar parte de la solución, dado que no
representan recursos.
El signo en la función objetivo de los coeficientes de
las variables artificiales va en contra del sentido de la
misma, es decir, en problemas de maximización su
signo es menos (-) y en problemas de minimización su
signo es (+).

11/09/2014Ingeniería Forestal

8

El problema
●

●

●

Una empresa dedicada a la fabricación de muebles, ha ampliado
su producción en dos líneas más. Por lo tanto actualmente fabrica
mesas, sillas, camas y bibliotecas.
Cada mesa requiere de 2 piezas rectangulares de 8 pines, y 2
piezas cuadradas de 4 pines. Cada silla requiere de 1 pieza
rectangular de 8 pines y 2 piezas cuadradas de 4 pines, cada
cama requierede 1 pieza rectangular de 8 pines, 1 cuadrada de 4
pines y 2 bases trapezoidales de 2 pines y finalmente cada
biblioteca requiere de 2 piezas rectangulares de 8 pines, 2 bases
trapezoidales de 2 pines y 4 piezas rectangulares de 2 pines.
Cada mesa cuesta producirla $10000 y se vende en $ 30000, cada
silla cuesta producirla $ 8000 y se vende en $ 28000, cada cama
cuesta producirla $ 20000 y sevende en $ 40000, cada biblioteca
cuesta producirla $ 40000 y se vende en $ 60000. El objetivo de la
fábrica es maximizar las utilidades.

11/09/2014

Ingeniería Forestal

9

El problema (II)

11/09/2014

Ingeniería Forestal

10

Paso 1: modelación mediante
programación lineal
Las variables:
●

X1 = Cantidad de mesas a producir (unidades)

●

X2 = Cantidad de sillas a producir (unidades)

●

X3 =Cantidad de camas a producir (unidades)

●

X4 = Cantidad de bibliotecas a producir
(unidades)

11/09/2014

Ingeniería Forestal

11

Paso 1: modelación mediante
programación lineal (II)
Las restricciones:
●

2X1 + 1X2 + 1X3 + 2X4 <= 24

●

2X1 + 2X2 + 1X3 <= 20

●

2X3 + 2X4 <= 20

●

4X4 <= 16

La función Objetivo:
●

ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4

11/09/2014

Ingeniería Forestal12

Paso 2: convertir las
inecuaciones en ecuaciones (II)
●

En este paso el objetivo es asignar a cada recurso
una variable de Holgura, dado que todas las
restricciones son "<=".

2X1 + 1X2 + 1X3 + 2X4 + 1S1 + 0S2 + 0S3 + 0S4 = 24
2X1 + 2X2 + 1X3 + 0X4 + 0S1 + 1S2 + 0S3 + 0S4 = 20
0X1 + 0X2 + 2X3 + 2X4 + 0S1 + 0S2 + 1S3 + 0S4 = 20
0X1 + 0X2 + 0X3 + 4X4 + 0S1 + 0S2 + 0S3 + 1S4 = 16

11/09/2014...