Download Presentación

Investigación de operaciones
Autor: Raymundo Palacios
Capítulo 3
Formulación de problemas
3.1 Introducción
La primera referencia a la programación lineal (PL) se remonta
al año de 1781, cuando el general francés Gaspard Monge
abordó el problema de la construcción y abastecimiento de
fortificaciones militares de Napoleón.
Para resolver el caso, el general utilizó el método de “cortar y
llegar”; es decir, ir abasteciendo las diferentes trincheras
desde los depósitos de materiales ya existentes.
3.1 Introducción
Muchos analistas consideran que la PL inició
con el método de análisis de insumoproducto, desarrollado por el economista
Vassily Leontief en 1936, el cual tiene por
objeto encontrar las relaciones entre la
materia prima y los procesos de producción,
durante un periodo de tiempo.
3.1 Introducción
El Dr. George Dantzig (1947) revolucionó la
PL con su método símplex (algoritmo que
sigue un procedimiento de solución
sistemática que permite realizar una serie de
pasos repetitivos que optimizan el objetivo
deseado, el cual se encuentra condicionado a
restricciones).
3.1 Introducción
La programación lineal (PL) se define como
una
técnica
que
utiliza
métodos
cuantitativos, en el que una función objetivo
claramente definida debe de maximizarse
(utilidad) o minimizarse (tiempo o costos)
cuando se consideran ciertas restricciones
(recursos limitados y requerimientos).
3.1 Introducción
La palabra “lineal” en PL se refiere a un modelo
simbólico formulado por medio de un sistema de
ecuaciones lineales.
El término “programación” no tiene relación
alguna ni con la programación para
computadoras ni con el desarrollo del software
correspondiente
Su origen está relacionado con procedimientos y
programas de actividades para realizar
eficazmente una tarea en términos matemáticos.
3.1 Introducción
Desde su aparición a finales de la década de 1940, la PL
ha demostrado ser una de las herramientas más
efectivas en la investigación de operaciones (IO).
Su éxito se debe a la flexibilidad para describir un gran
número de situaciones reales en el terreno militar, en
la agricultura, en el transporte, en la economía, en la
salud, e incluso en la conducta psicológica y social del
ser humano.
3.1 Introducción
La utilidad de la PL como herramienta
determinística trasciende sus aplicaciones
inmediatas.
De hecho, la PL forma el pilar de otras técnicas de
la IO, como son: la asignación de transbordo, la
programación entera, la programación dinámica,
las líneas de espera, los modelos de producción,
inventarios y pronósticos, etcétera.
3.2 Estructura matemática de modelos en programación lineal
La programación lineal (PL) es una herramienta
cuantitativa basada en un sistema de ecuaciones lineales,
la cual debe satisfacer un objetivo específico sujeto a
restricciones:
Maximizar (o minimizar) la función: F = c1x1 + c2y2 +…+
crzu
Sujeta a restricciones: R1 (k11x11 + k12y12 + … + k1sz1n) + …
≤ ( =, ≥ ) b1
R2 (k21x21 + k22y22 + … + k2sz2n) + … ≤ ( =, ≥ ) b2
:
:
Rv (kp1xm1 + kp2ym2 + … + kpszmn) + .. ≤( =,≥ ) bq
Donde: xmn ≥ 0 , ymn ≥ 0,… …,zmn ≥ 0
3.2 Estructura matemática de modelos en programación lineal
La función objetivo o función de utilidad F= c1x1 + c2y2+…+ crzu
establece el rendimiento máximo (medido en cantidades de
plusvalía) o mínimo (medido en cantidades de tiempo o en
costos).
La función de restricción establece los requerimientos (≥) o
limitaciones ( ≤ y = ) bajo las cuales se encuentra sujeto lo que
se desea maximizar o minimizar:
R1, R2 hasta Rv (kp1xm1 + kp2ym2 +…+ kpszmn) + …≤ ( =,≥ ) bq
Las incógnitas xmn, ymn +… zmn se llaman variables de decisión,
las cuales son cantidades controladas por la administración.
Las variables de decisión no pueden adquirir valores negativos
(xmn ≥ 0 , ymn ≥ 0,… …zmn ≥ 0)
Cr y kps, son constantes cuyos valores numéricos (datos) se
conocen.
3.2 Estructura matemática de modelos en programación lineal
El modelo exige que la función de restricción debe
satisfacer una condición expresada mediante una
desigualdad o igualdad matemática (≤, = y ≥), siendo
b1, b2 hasta bq parámetros cuyos valores numéricos
(datos) se encuentran determinados.
En otras palabras, en el lenguaje de los modelos de la
programación lineal, una restricción es una igualdad o
desigualdad matemática que debe ser satisfecha.
3.2 Estructura matemática de modelos en programación lineal
Una restricción matemática del tipo Rv (kp1xm1 + kp2ym2 +…+
kpszmn) = bq se denomina ecuación porque es una igualdad en
la que hay una o varias cantidades desconocidas llamadas
incógnitas y que sólo es verdadera para determinados valores
de las incógnitas.
Las restricciones matemáticas del tipo Rv (kp1xm1 + kp2ym2 +…+
kpszmn) + ..≥ bq y Rv (kp1xm1 + kp2ym2 + … + kpszmn) + ..≤ bq se
llaman desigualdades, lo que indica que una cantidad es
menor-igual o mayor-igual que otra.
3.3 Formulación PL basada en la producción de sofás
Una fábrica de muebles elabora un sofá tipo A y otro tipo B en cuatro
departamentos de la siguiente manera (Ver la tabla 3.1):
Se desea saber cuántos sofás del tipo A y B se deben fabricar para
maximizar las ganancias.
El precio de cada sofá A es de €10 y el del sofá B es de €25 por pieza
El problema de PL queda planteado como sigue:
Maximizar:
Z = 10 X + 25 Y
Sujeto a:
X+ 2Y ≤ 80 Departamento de corte
(3/4)X + (1/2)Y ≤ 20 Departamento de armado
X≤ 50 Departamento de tapicería
Y≤ 10 Departamento de cubiertas
donde: X,Y ≥ 0
3.4 MODELO DE PL BASADO EN UNA DIETA PARA UN CABALLO LUSITANO
Un veterinario le recomendó a uno de sus clientes que
alimentara a su caballo lusitano durante tres meses con
maíz, trigo y sorgo.
El dueño sólo puede proporcionar estos tres alimentos
mezclando dos costales que contengan las cantidades en
diferentes proporciones que se muestran en la tabla 3.2.
La cantidad de alimentos que deberá comprar durante
los tres meses se encuentra estimada en la tabla 3.3.
Al dueño le cuesta $30 pesos el costal X y $40 pesos el
costal Y ¿Cuántos costales puede comprar de X y Y al
menor costo posible?
3.4 MODELO DE PL BASADO EN UNA DIETA PARA UN CABALLO LUSITANO
El problema de PL queda planteado como sigue:
Minimizar Z = 30X + 40Y
Sujeto a:
4X ≥ 12 Cantidad de maíz
3Y ≥ 6 Cantidad de trigo
X + 1.5Y ≤ 9 Cantidad de sorgo
donde X, Y ≥ 0