Operacion De Investigaciones

PROGRAMACIÓN LINEAL: SOLUCIÓN DE PROBLEMAS CON EL MÉTODO SIMPLEX

El Método Simplex soluciona problemas de Programación Lineal de cualquier tamaño, desde dos hasta "n"variables de decisión. Los problemas pueden ser

maximización

o de

minimización

dependiendo del tipo deFunción Objetivo que tengan y en cuanto al tipo de solución óptima que den, pueden ser de

solución única

o de

solución múltiple o alterna.

La computadora es un medio tecnológico que da gran apoyo en la solución de problemas en ProgramaciónLineal, utilizando su gran velocidad de procesamiento de datos. La computadora puede utilizar cualquier tipo desoftware diseñado para este propósito, pero todos ellos emplearán el algoritmo matemático del MétodoSimplex. Algunos paquetes de software que se pueden utilizar para solucionar estos problemas son, elWinQSB, Storm, Lindo, etc. También se puede programar una hoja electrónica para este fin, con el Solver delExcel . Un requisito indispensable para usar la computadora con esta orientación, es tener el problema previamente

modelado

para facilitar la captura de los datos de entrada, que deberán ser de acuerdo al formato del softwareutilizado y proceder a su ejecución. La solución que da la computadora en su reporte de salida, se debe de

interpretar

para apoyar la toma de decisiones.El enfoque de este tema es, conocer los fundamentos del Método Simplex como un apoyo para interpretar lasolución óptima, que es la solución matemática que dá la computadora. Para lograr esto, se presenta la

metodología

que sigue el Método Simplex en la solución manual de problemas de Programación Lineal ya seande maximización o de minimización:

1.

Igualar las restricciones del problema modelado.2.

Formar la "Tabla Inicial".3.

Reconocer si la solución que dá la Tabla es óptima, checando el cumplimiento del "Criterio deOptimabilidad (C

j

-Z

j

≤

0)

".

Si la solución no es óptima, se debe:4.

Calcular la "Nueva Tabla". hasta encontrar la solución óptima.5.

Repetir el "Paso 3 y 4" hasta que la tabla calculada cumpla con el criterio de optimabilidad.6.

Dar la "Solución Optima" del problema.7.

"Interpretar" la solución óptima del problema.

Para presentar la aplicación de esta metodología, se hará con tres problemas: uno de maximización, otro deminimización y el último de solución óptima alterna o múltiple.

1. PROBLEMA DE "MAXIMIZACIÓN".

Se explicará esta metodología general con un problema de maximización, de dos variables de decisión, que esun problema pequeño solo para ilustrar el Método Simplex. Con la finalidad de comparar el Método Gráfico y el Simplex, se retoma el problema de "fabricación defertilizantes" que anteriormente se había solucionado con el Método Gráfico y ahora se hará con el Simplex.Primero se presenta la solución del problema y luego se hará la comparación entre ambos métodos:

1.1. Solución del problema por el Método Simplex.

A continuación se da el modelo del problema de los fertilizantes (problema presentado en las notas del MétodoGráfico) para ser solucionado con el Método Simplex: Máx. Z = 185X

1

+ 200X

2

s. a. Nitrato 0.05X

1

+ 0.05X

2

≤

1,100Fosfato 0.05X

1

+ 0.10X

2

≤

1,800Potasio 0.10X

1

+ 0.05X

2

≤

2,000 JEVA / PTI2

PROGRAMACIÓN LINEAL MÉTODOSIMPLEX

Paso 1. Igualar las restricciones.

Se igualan las restricciones para tener la

matriz identidad

del problema. Esta matriz identidad es el puntode partida que utiliza el Método Simplex para solucionar el problema. Existen las siguientes

reglas

para hacer la igualación de las restricciones: Si se tiene una restricción

menor o igual

se agregará una

variable de holgura (H).

Si la restricciónes

mayor o igual

se restará una

variable de excedente (E)

y se sumará una

variable artificial (A)

. Sila restricción es una

igualdad

se sumará una

variable artificial (A).

Un pequeño ejemplo para mostrar la aplicación de estas reglas es igualando las siguientesrestricciones: Restricciones Igualando las restricciones2X

1

+ 4X

2

≤

80 2X

1

+

...