Modelo De Optimizacion

El Modelo de Programación Lineal

La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.

La programación lineal es una técnica de modelado (construcción de modelos).

• La programación lineal (PL) es una técnica matemática de optimización, es decir, un método que trata de maximizar o minimizar un objetivo.

• Su interés principal es tomar decisiones óptimas.

• Se usa mucho en la industria militar y en la petrolera. S i bien esos sectores han sido quizá los principales usuarios de ella, el sector servicios y el sector público de la economía también la han aprovechado ampliamente.

Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

Las variables

Las variables son números reales mayores o iguales a cero.

En caso que se requiera que el valor resultante de las variables sea un número entero, el procedimiento de resolución se denomina Programación entera.

Restricciones:

Las restricciones pueden ser de la forma:

Tipo 1: :

Tipo 2:

Tipo 3:

En Dónde:

 A = valor conocido a ser respetado estrictamente;

 B = valor conocido que debe ser respetado o puede ser superado;

 C = valor conocido que no debe ser superado;

 j = número de la ecuación, variable de 1 a M (número total de restricciones);

 a; b; y, c = coeficientes técnicos conocidos;

 X = Incógnitas, de 1 a N;

 i = número de la incógnita, variable de 1 a N.

En general no hay restricciones en cuanto a los valores de N y M. Puede ser N = M; N > M; ó, N < M.

Sin embargo si las restricciones del Tipo 1 son N, el problema puede ser determinado, y puede no tener sentido una optimización.

Los tres tipos de restricciones pueden darse simultáneamente en el mismo problema.

Función Objetivo:

La función objetivo puede ser:

ó

Dónde:

 fi = coeficientes son relativamente iguales a cero.

Programación Entera

En algunos casos se requiere que la solución óptima se componga de valores enteros para algunas de las variables. La resolución de este problema se obtiene analizando las posibles alternativas de valores enteros de esas variables en un entorno alrededor de la solución obtenida considerando las variables reales. Muchas veces la solución del programa lineal truncado está lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta. El más famoso es el método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método de Ramificar y Acotar parte de la adición de nuevas restricciones para cada variable de decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo entero, o en otras palabras el método simplex.

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: La función por optimizar (maximizar o minimizar)

Restricciones: Representan condiciones que es preciso satisfacer. Sistema de igualdades y desigualdades (≤ Ó≥ ).

Por lo tanto se hace la siguiente:

Tipos De Restricciones:

Al tener las restricciones tal como el ejemplo que estamos viendo, se puede notar que se puede graficar. Con los conocimientos que tenemos ahora en este nivel, podemos graficar esas ecuaciones sin ningún problema. Tal así que quedara como la imagen de abajo. Resolver este problema

El área sombreada de azul es la que corresponde al conjunto factible, cada punto que contiene el conjunto factible es un candidato para resolver este problema.

Sin embargo, ya que se tiene graficado el conjunto factible o sea el área azul de la gráfica, se identifica las coordenadas de todas las esquinas o vértices del conjunto factible:

Por lo tanto para poder encontrar las coordenadas del punto B se tiene que resolver el sistema de ecuaciones conformado por las dos ecuaciones anteriores 2X +3Y=12 y 2X+Y=8. Esto se hace sustituyendo los valores que se consigue en la gráfica. En lo cual esto quiere decir que El valor que toma la función objetivo en el vértice de solución óptima se llama valor del programa lineal.

Teoremas de dualidad.

Teorema de existencia.

La condición necesaria y suficiente para que un problema de programación lineal tenga solución es que, tanto el conjunto de oportunidades del primal (S) como en conjunto de oportunidades del dual (S’) no sean vacíos, es decir, que ambos problemas sean factibles.

Corolario del teorema de existencia.

Una vez analizadas las condiciones

...