Formulacion

Formulación

Capítulo 2 Formulación Max ó Min Z = C X C.S.R. AX 0 ; j = 1, 2, ..., n

Objetivo El presente trabajo es una recopilación de algunos problemas representativos de programación lineal, en donde se muestra al lector la solución a diferentes modelos, buscando desarrollar la capacidad inventiva para formular problemas de optimización de recursos. Programación Lineal - ProblemaGeneral La Programación Lineal resuelve un tipo muy especial de problema, uno en el cual todas las relaciones entre las variables son lineales, tanto en las restricciones como en la Función Objetivo. 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:

15

Formulación

Maximizar ó Minimizar

Z = C1X1 + C2X2 +

......

+ CnXn

Con las siguientes restricciones: a11X1 + . . ai1X1 + . . am1X1 + .....
.

.....

.....

+ a1jXj + . . . + aijXj + . . . + amjXj+

.....

.....

.....

+a1nXn . . + ainXn . . . + amnXn

.

≤ó≥ . . ≤ó≥ . . ≤ó≥

b1 . . bi . . bm

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

Características de la Programación Lineal 1. Linealidad asume que no pueden haber términos así: X1X2 X32 a14Log X4

2. Asume las propiedades aditivas y multiplicativas. • • Si una unidad tipo 1 necesita 2 horas en la Máquina A y una unidad tipo 2 necesita 2½ horas, entonces ambasnecesitan 4½ horas. Si una unidad tipo 3 necesita 1 hora en la máquina B, entonces 10 unidades necesitan 10 horas.

3. La función que se va a optimizar (maximizar ó minimizar) se llama función objetiva, fíjese que no aparece ningún término independiente ó constante. Los valores de las Xj son independientes de cualquier constante. 4. Cuando se dice que hay m restricciones, no están incluidas lascondiciones Xj ≥ 0 (condición de no negatividad). 5. a) Cualquier conjunto de Xj que satisface las m restricciones se llama una solución al problema.

16

Formulación b) Si la solución satisface la condición de no negatividad Xj ≥ 0 , se llama una solución

factible

c) Una solución factible que optimiza la función objetiva se llama una solución factible

óptima

Usualmente hay unnú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. Es decir, se puede proceder de la siguiente forma: 1. Exprese cada restricción en palabras; al haceresto, 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), una limitación de la forma ≤ (menor ó igual que, no mayor que, como máximo), ó = (igual a, exactamente igual a). 2. Después expresar el objetivo en palabras. 3. Identificar verbalmente las variables de decisión: Con frecuencia, una cuidadosa lectura delcontenido del problema le revelará que las variables de decisión y el objetivo se le dan en la forma exacta que necesita. Es imperativo e importante que estén definidas en forma correcta sus variables de decisión. En ocasiones encontrará que hay varias elecciones posibles. Una guía útil es hacerse a si mismo la pregunta: Qué decisión debe tomarse para optimizar la función objetivo ? . La respuesta aesta pregunta le ayudará a llegar a identificar correctamente las variables de decisión. 4. Expresar la función objetivo mediante símbolos, es decir en términos de las variables de decisión. 5. Expresar las restricciones mediante símbolos, es decir, en términos de las variables de decisión. En esta etapa es necesario e imperativo comprobar si las unidades son consistentes. Por ejemplo, si los...