Presentación Método Simplex Estándar

Ingeniería Civil
Universidad Central del Ecuador

INVESTIGACIÓN OPERATIVA

Ing. Marco Antonio Pineda (Msc.)

Ingeniería Civil
Universidad Central del Ecuador

CONTENIDO
Objetivos
Introducción
Método Simplex Estándar
Descripción general
Metodología
Proceso metodológico

Premisas, conclusiones y consideraciones
Ejemplos

Ingeniería Civil
Universidad Central del Ecuador

OBJETIVOS

IngenieríaCivil
Universidad Central del Ecuador

OBJETIVOS
General.
Utilizar el método simplex para la solución de problemas
de programación lineal.
Específicos.
Conocer detalladamente el procedimiento del algoritmo
simplex.
Conocer las premisas bajo las cuales funciona el algoritmo
simplex.

Ingeniería Civil
Universidad Central del Ecuador

INTRODUCCIÓN

Ingeniería Civil
Universidad Central del EcuadorINTRODUCCIÓN
Es un método analítico para la solución de problemas de
PL, 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.
Este algoritmo fue creado en el año de 1947 por el
estadounidense George Bernard Dantzig y el ruso
Leonid Vitalievich Kantorovich, a fin de solucionar
problemas de PL con m restricciones y nvariables.

Introducción
El método simplex utiliza ecuaciones en lugar de inecuaciones.
Algebra Lineal - Método de eliminación de Gauss-Jordan,
constituyen la base para la solución analítica del método simplex.
La primera aplicación importante, fue su utilización en un problema
de PL para la planeación de una dieta, que utiliza 9 restricciones y
27 variables (120 días-hombre).
El uso de la pc y software dePL, permite fácilmente resolver
problemas de PL con muchas variables y restricciones.

Ingeniería Civil
Universidad Central del Ecuador

MÉTODO SIMPLEX ESTÁNDAR

Ingeniería Civil
Universidad Central del Ecuador

DESCRIPCIÓN GENERAL
Utiliza un algoritmo iterativo, que permite ir mejorando la
solución en cada paso, al pasar por los diferentes vértices
que conforman (limitan) el conjunto desoluciones factibles
del «politopo», y dado que el número de vértices es finito,
siempre es posible encontrar la solución óptima.

Ingeniería Civil
Universidad Central del Ecuador

METODOLOGÍA

Metodología
Se inicia evaluando la función objetivo en un vértice cualquiera del
«politopo» y buscar sucesivamente otro vértice que mejore (o
deteriore) la solución anterior.
Se basa en la siguiente propiedad:si la función objetivo «f» no toma
su valor máximo en el vértice «A», entonces hay una arista que parte
de A, a lo largo de la cual f aumenta.

Metodología
En el caso de un sistema de dos variables, con un espacio de
soluciones factibles como el siguiente, se tendrá:
La solución optima (máxima), se
da en el punto D(3,12), donde
el valor de la función objetivo
alcanza su máximo (33)
D: (3,12)Z=33

Variables de Holgura
El Método Simplex trabaja basándose en ecuaciones, por tanto, será
necesario adecuar el modelo matemático (canónico) a un modelo
estándar.
Transformar las inecuaciones (restricciones) en ecuaciones, a través de
la utilización de unas variables denominadas de holgura (escases), que
están relacionadas con el recurso al cual hace referencia la restricción,
y que representan el"Slack".
Estas variables, juegan un rol fundamental en la creación de la
matriz identidad base del Simplex.
Estas variables, suelen estar representadas por la letra "S", que se
suman cuando la restricción es de signo "<=".

Ingeniería Civil
Universidad Central del Ecuador

PROCESO GENERAL
El proceso a seguir para la solución de problemas utilizando el
método simplex, es el siguiente:Procedimiento Matemático
Proceso:
1.

2.

3.

4.

5.

• Convertir las desigualdades en igualdades
• Igualar la función objetivo a cero
• Escribir la tabla inicial simplex
• Variable de decisión que entra y variable de holgura que sale
• Encontrar los coeficientes de la nueva tabla

Ejemplo:
Se desea resolver mediante el método del simplex el siguiente
problema:


;

3

:
2
2
3

3

18
42
24

0 ,

0...