ADO TAV 03 2013 II

TAV 03

ADMINISTRACIÓN DE OPERACIONES

SOLUCIÓN DE UN PROBLEMA DE PROGRAMACIÓN
LINEAL
Mg. Paul Linares Ortega
Ingeniero Industrial

MÉTODOS DE PROGRAMACION LINEAL
Una vez formulado un problema de programación lineal existen tres
métodos para resolverlos o solucionarlos:
Método geométrico o gráfico:
Tiene un valor práctico limitado pero es de gran utilidad para
visualizar los conceptos de laprogramación lineal.
Método algebraico:
Muchos califican al método algebraico, como uno de los métodos
más importantes en el campo de la programación lineal
Método simplex:
Es utilizado para resolver cualquier problema de programación
lineal.

MÉTODO SIMPLEX
El método algebraico es muy dispendioso, en razón a que trabaja con todos
los datos de las ecuaciones, para mejorar éste aspecto se creó elmétodo
simplex cuya gran virtud es su sencillez, método muy práctico, ya que solo
trabaja con los coeficientes de la función objetivo y de las restricciones
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.
Para resolver en la prácticaproblemas de más de dos dimensiones, se
emplea el llamado Método Simplex, basada en el álgebra matricial y en el
empleo de espacios de “n” dimensiones.

En teoría, el método Simplex puede resolver un problema que consiste
en cualquier número de variable y restricciones; aunque en el caso de
problemas que tienen más de cuatro variables o restricciones, es mejor
que los cálculos sean hechos en elcomputador a través de un software
(WINQSB, SOLVER, LINDO, TORA, etc.).
Sin embargo, para poder comprender totalmente la programación lineal,
construir las ecuaciones para desarrollar el programa y poder integrar sus
resultados, es necesario desarrollar manualmente el Método Simplex.

Maximización

Los pasos que comprende el Método simplex en el caso de maximización son:
1.- Formular el problema,planteado la función objetiva, las restricciones y las
condiciones de no negatividad.
2.- Si la restricción es “menor o igual que” ( ≤ ), genera la inclusión de una variable
de holgura (S) al lado izquierdo de la desigualdad, para convertirla en ecuación.
3.- Elaborar la tabla inicial simplex, ingresando todos los coeficientes numéricos de la
función objetivo y de las restricciones. Luego calcularZj y Zj-Cj respectivamente.

Variables de Holgura (S): una variable de holgura representa la cantidad no utilizando
u ociosa de cada recurso. Se introducen las variables de holgura necesaria en cada
restricción; ya que estas convierten dichas restricciones en igualdades.
La función objetivo también refleja la suma de las variables de holgura; pero como
esta no genera utilidad su coeficiente es“0”.

Tabla inicial simplex
Costo de la variable j

Cj

Variables
Básicas

Variables de
decisión

Variables de
holgura

X1

S1

X2

S2

S1
S2
Zj
Zj - Cj
Contribución de la variable j
Contribución neta de la variable j

Solución

4.- Partiendo del calculo de Zj-Cj se escoge entre las restricciones un punto de apoyo
(Pivote) para lo cual se determina una columna pivote, eligiendo entre la
columna devariables a aquella que tenga el mayor valor negativo si se trata de
maximización. Posteriormente se determina una fila pivote, dividiendo la
columna solución entre la columna elegida, tomando como referencia el menor
valor positivo; la intercepción de ambas es el punto pivote.
5.- El punto Pivote por su ubicación indica que variable sale y que variable ingresa. El
Pivote, debe ser 1; si no es asítendrá que operarse ya sea multiplicando o
dividiendo con la finalidad de obtener 1. Una vez que el punto Pivote es la
unidad, se convierte en ceros todos los elementos de su columna.
El método simplex es un método iterativo (repetitivo), han de repetirse los pasos
hasta encontrar la solución óptima, es decir cuando en la fila Zj-Cj sean ceros o
positivos para la maximización.

Caso de...