Scribd
Cargar
26 vistas35 páginas

Método Simplex en Programación Lineal

El documento presenta el método simplex para resolver problemas de programación lineal de maximización. Explica cómo formular modelos matemáticos de PL en su forma estándar, expresarlos en una matriz y utilizar el método simplex para encontrar la solución óptima a través de un proceso iterativo que identifica variables de entrada y salida. También incluye ejemplos para ilustrar cómo construir el tablero simplex inicial y determinar la solución óptima.

Cargado por

ACERO CLAROS VALERY ALEXANDRA
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
26 vistas35 páginas

Método Simplex en Programación Lineal

El documento presenta el método simplex para resolver problemas de programación lineal de maximización. Explica cómo formular modelos matemáticos de PL en su forma estándar, expresarlos en una matriz y utilizar el método simplex para encontrar la solución óptima a través de un proceso iterativo que identifica variables de entrada y salida. También incluye ejemplos para ilustrar cómo construir el tablero simplex inicial y determinar la solución óptima.

Cargado por

ACERO CLAROS VALERY ALEXANDRA
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

MÉTODO SIMPLEX

Expositor: Dr. Hermes Pantoja Carhuavilca


Objetivos de la unidad

● Expresar modelos de programación lineal en su forma


estándar.
● Utilizar el método símplex para resolver modelos de PL de
maximización (con restricciones de la forma menor igual
que).
● Utilizar el método simplex para resolver casos prácticos
interpretando la solución como apoyo a la toma de
decisiones.
Formulación de modelos en PL

Horas disponibles en la planta 3, para producir lotes del


prod 1 y prod 2

Restricciones de no negatividad
Formulación del modelo matemático del PPL.

Max

s.a.
Continuación...
Conjunto convexo factible

(0,9)

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

(4,3)

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

X1
Procedimiento del Método
Simplex
Ejemplo
Considere el sistema:
Optimizar Z = CX
sa: AX=b
x >= 0
Donde A es una matriz mxn
Suponga que el rango (A,b) = rango(A) = m
Amxn=[B N], , m<n

B: Matriz básica m.m o base.


N: Matriz no básica m.(n-m). Es el resto de las columnas de A
Por un posible arreglo, el sistema puede presentarse
como sigue

XB
Z = (CB CN) XN

XB
s.a : (B N) XN =b
XB, XN >= 0
Donde
CB, CN: Coeficiente de las variables básicas y no básicas.
XB, XN: Variables básicas y no básicas (XN = 0)
XB
(B N) XN =b
Ejemplo
Dado el sistema de ecuaciones

Complete el siguiente cuadro


Solución
Operando el sistema anterior se tiene:
Z = CBXB + CNXN ……..…(1)
s.a:
BXB+NXN = b
XB, XN >= 0
B-1(2)
B-1 (BXB + NXN) = B-1 b
Luego
1XB=XB=B-1b - B-1NXN ………(2)

……(3)
De (4) y (5)

Z
1 0 (CBB-1 - CN) XB = CBB-1 b
0 I B-1 N XN B-1 b

Z XB XN LD
XB
Z
Otra forma de presentar el tablero simplex es:

Z XB XN LD
Z
XB
Ejemplo
Construir el Tablero Inicial Simplex
Solución
Continuación...
Continuación...
Continuación...
Ejercicio

Dada las variables básicas del tablero óptimo

Halle el tablero óptimo


Solución
Continuación...
Continuación...

Ubicando los resultados en el tablero óptimo


Ejm: Del problema de programación lineal
Max Z = 2X1 + 3X2 – X3
s.a
2X1 + X2 – X3 <=6
X1 + 3X2 + 2X3 <=5
X1, X2, X3 >=0

Se pide determinar la solución óptima para


la función objetivo.
Solución:
Adicionando las variables de holgura X4 y
X5 a cada restricción tendremos:
Max = 2X1 + 3X2 –X3
s.a.
2X1 + X2 + X3 + X4 + 0X5 = 6
X1 + 3X2 + 2X3 + 0X4 + X5 = 5

Entonces tendremos:
Z X1 X2 X3 X4 X5 LD
(1) Z
(2) X4
(3) X5

Analizando en tablero simplex tenemos como variable de


entrada al coeficiente con mayor signo negativo (-3) que
será X2 y como variable de salida:
X5 = min (6/1, 5/3); entonces tenemos como variable de
salida a X5; por lo tanto el tablero simplex será ahora:
(3.a)= (3)/3
(2.a)= (2) – (3.a)
(1.a)= (1)- 3 x (3.a)
Z X1 X2 X3 X4 X5 LD
(1.a) Z
(2.a) X4
(3.a) X2

Analizando el nuevo tablero, la variable de


entrada será ahora X1 y la variable de salida será:
X4 = min (13/3, 5/3) = 13/5
5/3 1/3
Entonces la variable de salida será X4; por lo
tanto el tablero simplex será ahora:
(2.b)= (2.a) x 3/5
(3.b)= (3.a) – 1/3(2.b)
(1.b)= (1.a) + (2.b)

Z X1 X2 X3 X4 X5 LD
(1.b) Z
(2.b) X1
(3.b) X2
Como en (1.b) no existen valores negativos se
dice que la solución es la óptima, por lo tanto:
X1 = 13/5 X4 = 0
X2 = 4/5 X5 = 0
X3 = 0
Y además:
Z = 2 (13) + 3 (4) - (0)
5 5

Z = 38/5
Universidad Nacional Mayor de San Marcos
Facultad de Ingeniería Industrial

También podría gustarte