Investigación de Operaciones y Simulación

1. Programación Lineal – Problema General
2. Características de la Programación Lineal
3. Pautas y comentarios para la formulación de modelos
4. Formulación de Modelos

Evaluación y formulación de problemas de optimización de recursos empresariales

Max ó Min Z = C X

S.A:

A X = B

XJ > 0 ; j = 1, 2, …, n

Objetivo

Mediante una recopilación de problemas representativos de programación lineal se busca desarrollar la capacidad inventiva para formular problemas de optimización de recursos.

Programación Lineal – Problema General

Definición:

Dado un conjunto de m desigualdades lineales ó ecuaciones lineales, con n variables, se requiere hallar valores no negativos de éstas variables que satisfagan las restricciones y maximicen ó minimicen alguna función lineal de las variables llamada Función Objetivo.

Matemáticamente:

Hallar XJ , J = 1, 2, . . . . . n para:

Maximizar

ó Z = C1X1 + C2X2 + . . . . . . + CnXn

Minimizar

Con las siguientes restricciones:

a11X1 + . . . . . . + a1jXj + . . . . . . + a1nXn = ó = b1

.

ai1X1 + . . . . . . + aijXj + . . . . . + ainXn = ó = bi

.

am1X1 + . . . . . . + amjXj+ . . . . . . + amnXn = ó = bm

Xj =0 ; j = 1, 2, . . . . . . n

Características de la Programación Lineal

• Linealidad asume que no pueden haber términos así: X1X2, X3 2 a14Log X4

• Asume las propiedades aditivas y multiplicativas.

• Si una unidad tipo E necesita 2 horas en la Máquina A y una unidad tipo F necesita 2½ horas, entonces ambas necesitan 4½ horas.

• Si una unidad tipo E necesita 1 hora en la máquina B, entonces 10 unidades necesitan 10 horas.

• La función a optimizar (maximizar ó minimizar) se llama función objetivo, no contiene ningún término constante.

• En las m restricciones, no están incluidas las condiciones Xj =0 (condición de no negatividad).

• Soluciones:

• Cualquier conjunto de Xj que satisface las m restricciones se llama una solución al problema.

• Si la solución satisface la condición de no negatividad Xj =0 , se llama una solución factible

• Una solución factible que optimiza la función objetiva se llama una solución factible óptima

Usualmente hay un número infinito de soluciones factibles al problema, de todas estas, tiene que hallarse una óptima

Pautas y comentarios para la formulación de modelos

En la conversión de modelos verbales a modelos formales, será muy útil describir primero con palabras un modelo que corresponda al problema dado.

Se puede proceder de la siguiente forma:

• Exprese cada restricción en palabras; al hacer esto, ponga cuidadosa atención en si la restricción es un requerimiento de la forma:

= (mayor ó igual que, al menos, por lo menos, como mínimo),

= (menor ó igual que, no mayor que, como máximo), ó

= (igual a, exactamente igual a).

• Expresar el objetivo en palabras.

• Identificar verbalmente las variables de decisión. Una guía útil es hacerse la pregunta:¿Qué decisión debe tomarse para optimizar la función objetivo?. La respuesta a esta pregunta ayudará a identificar correctamente las variables de decisión.

• Expresar la función objetivo en términos de las variables de decisión. Verificar la consistencia de unidades. Por ejemplo, si los coeficientes de una función objetivo Cj están dados en S./ por kilo, las variables de decisión Xj deben estar en kilos, no en toneladas ni onzas.

• Expresar las restricciones en términos de las variables de decisión. Comprobar que para cada restricción las unidades del lado derecho son las mismas que las del lado izquierdo. Las restricciones no pueden tener una desigualdad estricta, con los signos < ó >. La razón de esto es de naturaleza matemática.

Formulación de Modelos