Investigacion De Operaciones

II.- ESTRUCTURA BÁSICA DE UN PROBLEMA DE PROGRAMACIÓN LINEAL (PL)

Un problema de PL consta de una función objetivo (lineal) por maximizar o minimizar,

sujeta a ciertas restricciones en la forma de igualdades o desigualdades.

Conceptos clave: Función objetivo, Restricciones

III.- FUNCION OBJETIVO

En esencia la programación lineal consiste en optimizar (maximizar o minimizar) una función objetivo, que es una función lineal de varias variables:

IV.- RESTRICCIONES

La función objetivo está sujeta a una serie de restricciones, expresadas por inecuaciones lineales:

Cada desigualdad del sistema de restricciones determina un semiplano.

Solución factible

El conjunto intersección, de todos los semiplanos formados por las restricciones, determina un recinto, acotado o no, que recibe el nombre de región de validez o zona de soluciones factibles.

Solución óptima

El conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el vértice donde se presenta la solución óptima se llam solución máxima o mínima según el caso).

Valor del programa lineal

El valor que toma la función objetivo en el vértice de solución óptima se llama valor del programa lineal.

V.- EL METODO SIMPLEX

Es un procedimiento interactivo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

El método 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.

Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo.

VI.- PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX

Esta es la forma estándar del modelo:

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

Para ello se deben cumplir las siguientes condiciones:

1. El objetivo es de la forma de maximización o de minimización.

2. Todas las restricciones son de igualdad.

3. Todas las variables son no negativas.

4. Las constantes a la derecha de las restricciones son no negativas.

Todas las restricciones son de igualdad.

A modo resumen podemos dejar esta tabla, según la desigualdad que aparezca, y con el valor que deben estar las nuevas variables.

Tipo de desigualdad

Tipo de variable que aparece

≥

- exceso + artificial

=

+ artificial

≤

...