Construccion de un modelo

...

2.1.2 Naturaleza de los procedimientos de optimización casos diversos

El Alcance de la Optimización

Una de las herramientas más importantes de la optimización es la programación lineal. Un problema de programación lineal está dado por una función lineal de varias variables que debe ser optimizada (maximizada o minimizada) cumpliendo con cierto número de restricciones también lineales.

El matemático G.B. Dantzig desarrolló un algoritmo llamado el método simplex para resolver problemas de este tipo. El método simplex original ha sido modificado a fin de obtener un algoritmo eficiente para resolver grandes problemas de programación lineal por computadora.

Por medio de la programación lineal se pueden formular y resolver problemas de una gran variedad de campos del quehacer humano, entre los que se puede mencionar: asignación de recursos en la planificación de gobierno, análisis de redes para planificación urbana y regional, planificación de la producción en la industria, y la administración de sistemas de transporte y distribución. Por esto la programación lineal es uno de los éxitos de la moderna teoría de la optimización.

La Optimización como una rama de las Matemáticas

Se puede ver, por lo dicho en la sección anterior, que la teoría de la optimización es matemática por naturaleza. Típicamente involucra la maximización o minimización de una función (a veces desconocida) que representa el desempeño de algún sistema. Esto se resuelve encontrando los valores de las variables (cuantificables y controlables) que hacen que la función alcance su mejor valor. A fin de entender cómo operan los algoritmos se requieren conocimientos de álgebra lineal y cálculo diferencial con varias variables.

Conceptos Básicos de Optimización

Esta sección introduce algunos de los conceptos básicos de optimización que se utilizan a lo largo del presente compendio. Cada concepto se ilustra por medio del siguiente ejemplo.

El problema es:

[pic 8]

Este es un problema típico en la teoría de optimización: la maximización (o minimización) de una función real de variables reales (a veces una sola variable) sujeta a un número de restricciones (a veces este número es cero).

La función f se llama función objetivo, x1 y x2 se llaman variables independientes o variables decisionales. El problema es encontrar valores reales para x1 y x2, que satisfagan las restricciones (1.2), (1.3) y (1.4), los cuales introducidos en (1.1) hagan que f (x1,x2) tome un valor no menor que para cualquier otro par x1,x2.

En la figura siguiente se muestran tres contornos de la función objetivo.

[pic 9]

La función objetivo tiene el mismo valor en todos los puntos de cada línea, de modo que los contornos pueden asimilarse a las isobaras (o isotermas) de un mapa climático.

No es difícil ver que la solución del problema es:

X ( x 1 , x 2 ) (1, 0)

Esto significa que

f ( X ) f ( X ) , X S (1.5)

Cuando una solución X S satisface (1.5) se llama solución óptima, y en este caso solución máxima (también solución optimal o maximal). Si el símbolo en (1.5) fuera “ ”, X sería una solución mínima. Además, f ( X ) se llama valor óptimo, y no debe ser confundido con solución óptima.

En la figura se observa que se podrían obtener valores mayores de f eligiendo ciertos x1, x2 fuera de S.

Cualquier par ordenado de números reales se llama solución del problema y el valor correspondiente de f se llama valor de la solución. Una solución X tal que X S se llama solución factible, en tanto que S = {(x1,x2) : h (x1,x2) 0, x1 0, x2 0}, que generalmente es una región conexa, se llama región factible.

Método de banquillo (stepping stones)

Este método sirve para probar si ya se alcanzó la optimización en el método de transporte. Una vez que se tiene una buena solución al método de transporte usando el MAV, es necesario probar si esta es óptima, cambiando unas unidades a otras rutas, para evaluar cada cuadro abierto (sin número asignado). Siga estos pasos

1.-Determine una trayectoria cerrada. Empezando con el cuadro abierto a ser evaluado y saltando a otros cuadros cerrados (con asignaciones), hasta regresar al cuadro original abierto. Cada elemento de la esquina de la trayectoria debe ser un cuadro cerrado (con asignaciones)

2.- Empezando con el cuadro abierto a ser evaluado, asigne un signo más (+) alterne signos menos (-) y más (+). A las esquinas (cuadros) de la trayectoria. Es indiferente si el circuito se recorre en el sentido de las manecillas del reloj o en sentido contrario

3.-Sume los costos por unidad en los cuadros con el signo más (+), reste los costos por unidad en los cuadros con el signo menos (-). Si el resultado es negativo, significa que se puede obtener una disminución de los costos con una nueva asignación

4.- Si el resultado del punto 3 fue negativo, entonces la variable que sale es aquel cuadro cerrado que tiene el valor más pequeño ya que será la primera que llegue al valor cero y cualquier disminución adicional causará se negatividad. El cuadro deberá tener el signo menos (-)

5.- Cuando la suma de todos los cuadros abiertos sea positiva, entonces se ha llegado a la solución óptima

Nota: recuerde que el número de variables básicas (cuadros cerrados) debe ser m+n-1.

Definición del problema de asignación.

Considere la situación de asignar m trabajos o trabajadores a n máquinas. Un trabajo i (i=1, 2, 3…, m) cuando se asigna a la máquina j (j=1, 2, 3,…, n) incurre en un costo Cij. El objetivo es asignar los trabajos a las máquinas (un trabajo por máquina) con el costo mínimo total. Este caso es conocido con el nombre de asignación.

La formulación de este problema puede considerarse como un caso especial del método de transporte. Aquí los trabajos representan “orígenes” y las máquinas representan “destinos”. La oferta disponible en cada fuente es 1. De igual manera la demanda requerida en cada destino