metodo grafico

El algoritmo “Simplex”.
Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El
proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo
del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar
sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a
través de los lados delpolígono(o de las aristas del poliedro, si el número de variables
es mayor). Cómo el número de vértices y de aristas) es finito, siempre se podrá
encontrar la solución.
El método del simplex 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.
El método del simplex se utiliza,sobre todo, para resolver problemas de programación
lineal en los que intervienen tres o más variables.
El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un
sistema de ecuaciones lineales constituyen la base del método simplex.


Fue desarrollado en 1947 por el Doctor George B. Dantzig.



Mediante su aplicación es posible resolver problemas lineales con nvariables y n
restricciones.



Se aplica a problemas tanto de Maximización como de Minimización.



El algoritmo Simplex inicia en el origen y se desplaza por los bordes del área de
soluciones factibles evaluando cada esquina de esta, hasta encontrar la solución
óptima.



Actualmente existe en el mercado múltiple software para la solución de problemas
de programación lineal queaplica este algoritmo, como QSA, QSB, STORM, LINGO,
TORA, AMPL, AB:POM, etc.



En 1984 Narendra Karmarkar creó un nuevo método alternativo para la solución de
problemas de programación lineal, conocido como el algoritmo de Karmarkar o del
punto central.



Este algoritmo inicia situándose en el punto central del área de soluciones factibles,
desde donde evalúa cada esquina de esta,hasta encontrar la solución óptima.

2
Lcdo. Wilfredo Díaz



Ya existe software en el mercado que utiliza este algoritmo, ya que es relativamente
más veloz y de mayor capacidad para manejar más variables y restricciones que el
algoritmo Simplex.

Aplicación del algoritmo Simplex:
Problemas solo con restricciones
del tipo “≤”



Método Simplex convencional

Problemas conrestricciones de
los tipos “=” y/o “≥”




Método de la “Gran M”
Método de las “2 Fases”

Desarrollo del algoritmo Simplex.
Para resolver un problema de programación lineal por medio del algoritmo Simplex, se
deben desarrollar los tres pasos descritos a continuación:

1
Obtener la
forma “SIMPLEX ESTÁNDAR” del
modelo de programación lineal

2
Colocar la forma “SIMPLEX
ESTÁNDAR” delmodelo en la
TABLA SIMPLEX

3
Aplicar el
ALGORITMO SIMPLEX

1. Obtención de la forma “SIMPLEX ESTÁNDAR”.
a) Convertir las restricciones a ecuaciones:


A todas y cada una de las restricciones del tipo “≤” se les suma una variable de
“holgura” ( Si ).



A todas y cada una de las restricciones del tipo “=” se les suma una variable
“artificial” ( Ri ).



A todas y cada unade las restricciones del tipo “≥” se les resta una variable de
“exceso” ( Si ) y además se les suma una variable “artificial” ( Ri ).

3
Lcdo. Wilfredo Díaz

b) Todas las variables de “holgura” y de “exceso” se suman a la Función Objetivo con
coeficiente cero.
c) Todas las variables de “artificiales” ( Ri ) se suman a la Función Objetivo con un
coeficiente diferente de cero (métodos dela gran M y de las 2 fases).

2. La TABLA SIMPLEX.
Renglón Cj
Coeficiente
C1

Recursos
R1

Coeficientes de las variables de las restricciones

……….

Sn

Variables de la Función Objetivo

……….

S1
……….

Variables
Básicas

Coeficientes de las variables de la Función Objetivo

Cn

Rn
Valor de Z

Renglón Zj
Renglón Z j - Cj

Nota: Este formato de la tabla SIMPLEX,...