redes

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 -Problema General
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
restriccionesy 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 horasen la Máquina A y una unidad tipo 2 necesita 2½
horas, entonces ambas necesitan 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 cualquierconstante.
4. Cuando se dice que hay m restricciones, no están incluidas las condiciones 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 lafunció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. Es decir, se puedeproceder de la
siguiente forma:
1. 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), 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
del contenido 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 lapregunta: Qué decisión debe
tomarse para optimizar la función objetivo ? . La respuesta a esta 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...