Método Simplex.

Variables de holgura: Siempre positivas, hacen que una restricción que sea desigualdad se transformeen igualdad, y sus coeficientes en la función objetivo son ceros.Variables ficticias o artificiales: Sirven para hallar fácilmente una solución básica inicial,

suscoeficientes en la función objetivo son w si es minimización o -w si es maximización; w es un número mucho mayor que todos los participantes.

Luego de sumar las variables de holgura y/o artificiales necesarias para convertir las desigualdades en igualdades y para obtener los vectores unitarios (de la matriz identidad) para la base inicial se procede a ordenar los datos en una tabla Simples; después se prueba la solución para ver si es óptima, si no es óptima se realiza el siguiente procedimiento:

- Se calculan los valores de zj multiplicando los coeficientes de la base por cada columna, uno a uno, y sumando esos resultados.

- Luego se calculan los valores de zj- c j; si es minimización el valor más grande de zj- c j designa a la columna clave, y si es maximización el valor más pequeño de zj - cj designa a la columna clave.

- Se calculan las razones entre la cantidad solución y sus correspondientes de la columna clave, para los valores positivos de la cantidad solución; el valor mínimo de estas razones designa a la fila clave.

- El elemento que se encuentra en la intersección de la columna clave con la fila clave se llama pivote.

- El vector de la fila clave se reemplaza por el de la columna clave en la base, luego setransforma la matriz ampliada (A | B) para que el pivote sea igual a 1 y los demás elementos de ese vector sean ceros; y se ordenan nuevamente estos datos en una tabla Simples.

La solución óptima se reconoce cuando la cantidad solución tiene sólo cantidades no negativas; si es minimización los valores de zj - cj son todos no positivos, y si es maximización los valores de zj - cj son todos no negativos.

SOLUCION DE PROBLEMAS DE PROGRAMACION LINEAL POR EL METODO GRAFICO.

 El método gráfico se emplea para resolver problemas que presentan sólo 2 variables de decisión. El procedimiento consiste en trazar las ecuaciones de las restricciones en un eje de coordenadas X1, X2 para tratar de identificar el área de soluciones factibles (soluciones que cumplen con todas las restricciones).

La solución óptima del problema se encuentra en uno de los vértices de esta área de soluciones creada, por lo que se buscará en estos datos el valor mínimo o máximo del problema.

 

EJEMPLO 1:

 Una compañía de auditores se especializa en preparar liquidaciones y auditorías de empresas pequeñas. Tienen interés en saber cuantas auditorías y liquidaciones pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800 horas de trabajo directo y 320 horas para revisión. Una auditoría en promedio requiere de 40 horas de trabajo directo y 10 horas de revisión, además aporta un ingreso de 300 dls. Una liquidación de impuesto requiere de 8 horas de trabajo directo y de 5 horas de revisión, produce un ingreso de 100 dls. El máximo de liquidaciones mensuales disponibles es de 60.

OBJETIVO : Maximizar el ingreso total.

 VARIABLE DE DECISION: Cantidad de auditorías (X1).

Cantidad de liquidaciones (X2).

 RESTRICCIONES : Tiempo disponible de trabajo directo

Tiempo disponible de revisión

Número máximo de liquidaciones.

 Maximizar

Sujeto a:

La solución óptima siempre se encuentra en uno de los vértices del conjunto de soluciones factibles. Se analizan estos valores en la función objetivo. El vértice que representa el mejor valor de la función objetivo será la solución óptima.

 

 

Método de las dos fases

Éste método difiere del Simplex en que primero hay que resolver un problema auxiliar que

trata de minimizar la suma de las variables artificiales. Una vez resuelto este primer

problema y reorganizar la tabla final, pasamos a la segunda fase, que consiste en realizar

el método Simplex normal.

FASE 1

En esta primera fase, se realiza todo de igual manera que en el método Simplex normal,

excepto la construcción de la primera tabla, la condición de parada y la preparación de la

tabla que pasará a la fase 2.

- Construcción de la primera tabla: Se hace de la misma forma que la tabla inicial del

método Simplex, pero con algunas diferencias. La fila de la función objetivo cambia para

la primera fase, ya que cambia la función objetivo, por lo tanto aparecerán todos los

términos a cero excepto aquellos que sean variables artificiales, que tendrán valor “-1″

debido a que se está minimizando la suma de dichas variables (recuerde que minimizar F

es igual que maximizar F·(−1)).

La otra diferencia para la primera tabla radica en la forma de calcular la fila Z. Ahora

tendremos que hacer el cálculo de la siguiente forma: Se sumarán los productos Cb·Pj

para todas las filas y al resultado se le restará el valor que aparezca (según la columna

que se éste haciendo) en la fila de la función objetivo.

Tabla

C0 C1 C2 … Cn-k … Cn

Base Cb P0 P1 P2 … Pn-k … Pn Pi1 Ci1 bi1 a11 a12 … a1n-k … a1n Pi2 Ci2 bi2 a21 a22

… a2n-k … a2n … … … … … … … … … Pim Cim bim am1 am2 … amn-k … amn Z Z0

Z1 Z2 … Z2 … Zn

Siendo Zj = Σ(Cb·Pj) - Cj y los Cj = 0 para todo j comprendido entre 0 y n-k (variables de

decisión, holgura y exceso), y Cj = −1 para todo j comprendido entre n-k y n (variables

artificiales).

- Condición de parada: La condición de parada es la misma que en el método Simplex

normal. La diferencia estriba en que pueden ocurrir dos casos cuando se produce la

parada: la función toma un valor 0, que significa que el problema original tiene solución, o

que tome un valor distinto, indicando que nuestro modelo no tiene solución.

- Eliminar Columna de variables artificiales: Si hemos llegado a la conclusión de que el

problema original tiene solución, debemos preparar nuestra tabla para la segunda fase.

Deberemos eliminar las columnas de las variables artificiales, modificar la fila de la

función objetivo por la original, y calcular la fila Z de la misma forma que en la primera

tabla de la fase 1.

FASE 1. Formule un nuevo problema reemplazando la función objetivo por la suma de las

variables artificiales. La nueva función objetivo se minimiza sujeta a las restricciones del

problema original. Si el problema tiene un espacio factible el valor mínimo de la función

objetivo óptima será cero, lo cual indica que todas las variables artificiales son cero. En

este momento pasamos a la fase 2.

Si el valor mínimo de la función objetivo óptima es mayor que cero, el problema no

tiene solución y termina anotándose que no existen soluciones factibles

FASE 2. Utilice la solución óptima de la fase 1 como solución de inicio para el problema

original. En este caso, la función objetivo original se expresa en términos de las variables

no básicas utilizando las eliminaciones usuales Gauss-Jordan.

El método Simplex revisado

El método Simplex es un algoritmo de George Dantzig para resolver problemas de optimización (de la

rama de programación lineal).

En este artículo voy a realizar el proceso paso a paso y de forma sencilla, utilizando el método Simplex

Revisado, una versión computacional reducida del algoritmo, que puede que a varios compañeros que

cursen esta asignatura les venga bien.

Identificar el problema

Es muy importante tener siempre presente con que tipo de problema estamos trabajando: mínimo o

máximo (ya volveremos a esto más tarde), que las variables Xi con las que trabajamos son positivas, y

que los beneficios no pueden ser negativos.

En este último caso, habría que cambiar de signo a toda la restricción implicada (con beneficio negativo).

Habría que contemplar además, el caso en el que las restricciones sean inecuaciones. Si así fuese, hay

que tener presente el añadir la resta de una variable de excedente (inecuación mayor/igual) o añadir la

suma de una variable de holgura (inecuación menor/igual), convirtiendo así las inecuaciones en

ecuaciones.

Casos especiales

El Método 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 o cuando esta es óptima.

Este método, permite analizar cada variable del problema planteado, sus variaciones,

para determinar cual es la decisión más acertada a tomar en cualquiera que sea el área

de la empresa sobre la cual se presente la incertidumbre.

Existen casos especiales de solución de problemas por medio del simplex, tales como:

• Soluciones Múltiples

• Solución Degenerada

• Solución Infactible

• Sin Solución

A continuación se presenta un análisis detallado de cada caso especial de solución con

un ejemplo práctico.

CASO DE SOLUCIONES MÚLTIPLES

Cuando la función objetivo es paralela a una restricción que se satisface en el sentido de

la igualdad a través de la solución óptima, la función objetivo tomará el mismo valor

óptimo en más de un punto de la solución. Por esta razón reciben el nombre de Múltiples

alternativas óptimas.

CASO DE SOLUCIÓN DEGENERADA

La degeneración ocurre cuando en alguna iteración del método simplex existe un empate

en la selección de la variable que sale. Este empate se rompe arbitrariamente. En este

caso decimos que la nueva solución es degenerada. Sin embargo, cuando suceda esto

una o más veces de las variables básicas, será necesariamente igual a cero en la

siguiente iteración. En el método simplex, la presencia de una variable básica igual a cero,

no requiere ninguna acción especial; en todo caso, es necesario no descuidar las

condiciones de degeneración. En términos geométricos, la degeneración ocurre cuando

un vértice está definido por demasiadas restricciones.

CASO DE SOLUCIÓN INFACTIBLE

En un modelo de Programación Lineal, cuando las restricciones no se pueden satisfacer

en forma simultánea, se dice que este no tiene solución factible. Esta situación nunca

puede ocurrir si todas las restricciones son del tipo MENOR O IGUAL ( ), esto,

suponiendo valores positivos en el segundo miembro, ya que las variables de holgura

producen siempre una solución factible.

Sin embargo, cuando empleamos los otros tipos de restricciones, recurrimos al uso de

variables artificiales, que por su mismo diseño no ofrecen una solución factible al modelo

original. Aunque se hacen provisiones (a través del uso de penalizaciones) para hacer

que estas variables artificiales sean cero en el nivel óptimo, esto sólo puede ocurrir si el

modelo tiene una espacio factible. Si no lo tiene, cuando menos una variable artificial será

positiva en la iteración óptima.

Desde el punto de vista práctico, un espacio infactible, apunta a la posibilidad de que el

modelo no se haya formulado correctamente, en virtud de que las restricciones estén en

conflicto. También es posible que las restricciones no estén destinadas a cumplirse en

forma simultánea. En este caso, quizás se necesite una estructura del modelo totalmente

diferente que no admita todas las restricciones al mismo tiempo.

CASO DE NO SOLUCIÓN

En algunos modelos de Programación Lineal, los valores de las variables, se pueden

aumentar en forma indefinida sin violar ninguna de las restricciones, lo que significa que el

espacio es sin solución cuando menos en una dirección.

Como resultado, el valor de la función objetivo puede crecer (Maximización) o decrecer

(Minimización) en forma indefinida. En este caso, decimos que el espacio en el cual se

espera sea resuelto el modelo, y el valor óptimo de la función objetivo no tiene solución.

La falta de explicación de un modelo puede señalar solo una cosa, que este se encuentra

mal construido. Evidentemente resulta irracional hacer que un modelo produzca una

ganancia infinita. Las irregularidades más probables en este modelo son:

1. No se toman en cuenta una o más restricciones redundantes

2. No se determinan adecuadamente los parámetros (constantes) de alguna restricción.