Metodo Simplex

1. INTRODUCCION.

El método SIMPLEX es una metodología de optimización que permite resolver problemas de la vida real, en los cuales una función objetivo es optimizada sujeta a un conjunto de restricciones.

Generalmente, los problemas de la vida real pueden ser descritos a través de un modelo matemático seleccionando adecuadamente las variables de decisión (a cada variable de decisión está asociada una actividad), planteando la función objetivo y todas las restricciones del problema.

2. MÉTODO SIMPLEX

El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones).

La razón matemática de esta mejora radica en que el método consiste en caminar

del vértice de un poliedro (cuerpo geométrico cuyas caras son planas y encierran un volumen finito) a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.

El método Simplex se basa en la siguiente propiedad: si la función objetivo Z no toma su valor máximo en el vértice A, entonces existe una arista que parte de A y a lo largo de la cual el valor de Z aumenta.

Será necesario tener en cuenta que el método Simplex únicamente trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y sus coeficientes independientes sean mayores o iguales a 0. Por tanto habrá que estandarizar las restricciones para que cumplan estos requisitos antes de iniciar el algoritmo del Simplex. En caso de que después de éste proceso aparezcan restricciones del tipo "≥" (mayor o igual) o "=" (igualdad), o no se puedan cambiar, será necesario emplear otros métodos de resolución, siendo el más común el método de las Dos Fases.

2.1.- Preparando el modelo para adaptarlo al método Simplex

La forma estándar del modelo de problema consta de una función objetivo sujeta a determinadas restricciones:

Función objetivo: c1•x1 + c2•x2 + ... + cn•xn

Sujeto a: a11•x1 + a12•x2 + ... + a1n•xn = b1

a21•x1 + a22•x2 + ... + a2n•xn = b2

...

am1•x1 + am2•x2 + ... + amn•xn = bm

x1,..., xn ≥ 0

El modelo debe cumplir las siguientes condiciones:

1. El objetivo consistirá en maximizar o minimizar el valor de la función objetivo (por ejemplo, incrementar ganancias o reducir pérdidas, respectivamente).

2. Todas las restricciones deben ser ecuaciones de igualdad (identidades matemáticas).

...