PROGRAMACION-LINEAL - 2020 I Semana 2

PROGRAMACIÓN
LINEAL
Investigación Operativa I
Introducción
En la vida real, las organizaciones operan con recursos escasos y todas ellas
tienen que tomar decisiones sobre cómo asignar estos recursos. Continuamente
la dirección debe asignar estos recursos escasos para alcanzar las metas de la
organización.
El tipo más común de aplicación abarca el problema general de asignar recursos

limitados entre actividades competitivas de la mejor manera posible (forma
óptima), este problema incluye elegir el nivel de ciertas actividades que compiten
por recursos escasos necesarios para realizarlas. Los niveles de actividad
elegidos dictan la cantidad de cada recurso que consumirá cada una de ellas.
La programación lineal utiliza el modelo matemático para describir el problema.

El adjetivo lineal significa que usa funciones lineales (de orden 1) y la palabra
programación es sinónimo de planeación. Así la programación lineal trata de la
planeación de las actividades para obtener un resultado óptimo, esto es, el
resultado que mejor alcance la meta especificada entre todas las alternativas de
solución.
Modelos de programación lineal
-Los problemas de Programación Lineal se expresan

mediante un conjunto de relaciones matemáticas que se
conoce como Modelo.
-Los modelos se pueden representar en su forma

estándar o en su forma canónica
El esfuerzo se centra tanto en la construcción

del modelo como en la resolución del mismo.
Modelos de programación lineal
En el planteamiento del modelo de programación lineal, se
debe distinguir entre recursos, actividad, nivel de actividad,
medida global de efectividad.
En estos problemas se trata de calcular el valor de las

variables que están sujetas a una serie de restricciones
y para las que una determinada función objetivo Z
alcanza su valor máximo o mínimo.
Forma Estándar
Notación:
◼ Z: Valor de la medida global de efectividad. También llamada Función Objetivo, es el

criterio y va referido a la minimización de los costos de la actividad, o a la maximización
de beneficios.
◼ xj: Nivel de la actividad j (para j = 1, 2, …., n)
◼ cj : Incremento en Z que resulta al aumentar una unidad en el nivel de la actividad j
◼ bi: Cantidad del recurso i disponible para asignar a las actividades (para i = 1, 2, …, m)
◼ aij: Cantidad del recurso i consumido por cada unidad de la actividad j.
FORMA ESTÁNDAR
Consumo de recurso por unidad de actividad Cantidad de
Recurso actividades recurso
1 2 n disponible
1 a11 a12 a1n b1
2 a21 a22 a2n b2
m am1 am2 amn bm

Contribución a
Z por unidad de c1 c2 cn
actividad
Los valores xj son las variables de decisión y los valores de cj, bi , y aij son las constantes de
entrada al modelo (parámetros del modelo).
Resolución de un problema de programación
lineal (PPL) mediante el método gráfico
(dos variables de decisión)
❖ El método de solución gráfica es aplicable sólo a problemas

simples que no excedan de dos variables.
❖ No obstante, dos variables no son suficientes para describir o

representar problemas reales, pero éste método proporciona
importantes ideas de los procedimientos de solución de P.L.
Método Gráfico, Ejemplo 1:
Una pequeña empresa de muebles fabrica dos productos: mesas y silla, que se
deben procesar a través de los departamentos de ensamble y acabado.
Ensamble tiene 60 horas disponibles y acabado puede manejar a lo máximo 48
horas de trabajo. La fabricación de una mesa requiere de 4 horas de ensamble
y dos horas de acabado. Cada silla requiere de dos horas de ensamble y cuatro
horas de acabado.
Si la utilidad es de $8 u.m. por mesa y de $6 u.m. por silla. El problema es

determinar la mejor combinación posible de mesas y sillas para producir, para
así vender y obtener la máxima utilidad.
Hay dos limitaciones (restricciones) en el problema: El tiempo disponible de

ensamble y de acabado.
Resumen de Información:
Mesa (u) Silla (u) Horas Directas

Disponibles (hr)
Ensamble 4 (hr) 2 (hr) 60
Acabado 2 (hr) 4 (hr) 48
Utilidad u.m. $8 $6
Método Gráfico, Ejemplo 1:
Planteamiento del Problema
1.- Definición de Variables de Decisión: Cantidad de sillas y mesas a producir
Xm: cantidad de mesas a producir (u)

Xs cantidad de sillas a producir (u)
2.- Restricciones:
• Departamento de Ensamble: 4 X m + 2 X s  60
• Departamento de Acabado: 2 X m + 4 X s  48
• Restricción de No Negatividad:
Xm  0
Xs  0
3.- Función Objetivo: Max
U = 8X m + 6X s
Gráfica: Se dibuja sobre el gráfico las restricciones de No Negatividad, según la
figura siguiente:
XsX
s
X
Xm
m
Cada una de las restricciones se grafican, considerando inicialmente la
desigualdad como una igualdad.
Así, se grafica la primera restricción como la ecuación:
4 X m + 2 X s = 60
Si : X m = 0  X s = 30
Si : X s = 0  X m = 15
Las dos coordenadas anteriores se señalan en la gráfica y se unen con una línea
recta, pero el signo de la desigualad incluye a todos los pares ordenados que
están a la izquierda de dicha recta. La siguiente figura representa dicha
situación:
XsX
s
Restricción 1
Restricción 1
XXm
m
Para la segunda ecuación, se efectúa el mismo desarrollo, es así:
2 X m + 4 X s = 48
Si : X m = 0  X s = 12
Si : X s = 0  X m = 24
Las dos coordenadas anteriores se señalan en la gráfica y se unen con una línea recta,
pero el signo de la desigualad incluye a todos los pares ordenados que están a la
izquierda de dicha recta. La siguiente figura representa dicha situación:
Xs Xs
Restricción 2 2
Restricción
Xm
Xm
La intersección de las dos inecuaciones, combinada a la ecuación de no negatividad, genera
la región de soluciones factible (RSF), como se indica en la figura. La región achurada indica
que todos los puntos que están en los bordes y dentro de a región factible, satisfacen
simultáneamente todas las restricciones del PPL.
Restricción 1 XX s
s
Restricción 1
Restricción 2
Restricción 2
RSF
XX m
m
El problema es encontrar uno o más puntos (o soluciones) en la RSF, de manera tal que
maximice la función objetivo original. La solución óptima se debe graficar, a través de
toda la región de soluciones. Así, cada línea de isoganancias se obtiene haciendo la
función objetivo igual a un valor arbitrario, por ejemplo, se elegimos igualar la utilidad a
$48 (u.m.), esta se gráfica (con línea segmentada) de igual manera que las inecuaciones
anteriores. Esta línea de isoganancias representa todas las cantidades posibles de
mesas y sillas que producirán una utilidad total de $48 (u.m.). El problema, finalmente, se
resume en encontrar la línea de isoganancia que tenga la mayor utilidad y que este sobre
la región de soluciones factibles. Lo anterior se realiza, moviendo la línea de isoganancia
en forma paralela a una línea de isoganancia arbitraria, hasta que alcance el último punto
de la RSF.
De esta manera, el último punto factible es el identificado con la letra D, por lo cual, es el punto óptimo se
encuentra por la intersección de las restricciones 1 y 2, así:
4 X m + 2 X s  60
2 X m + 4 X s  48
 X s = 6 (u) sillas
 X m = 12 (u) mesas
El valor de la contribución máxima es:
max
U = 8X m + 6X s
U = $132 (u.m)
Restricción Restricción
1 1 Xs
Xs
U=132(um)
U=$132 (u.m.)
Restricción 2
Restricción 2
U=$48 (u.m.)
U=48(um)
D
RSF
Xm
Xm
GRACIAS

PROGRAMACION-LINEAL - 2020 I Semana 2

Cargado por

Copyright:

Formatos disponibles

PROGRAMACION-LINEAL - 2020 I Semana 2

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

PROGRAMACION-LINEAL - 2020 I Semana 2

Cargado por

Copyright:

Formatos disponibles

PROGRAMACIÓN

El tipo más común de aplicación abarca el problema general de asignar recursos

La programación lineal utiliza el modelo matemático para describir el problema.

-Los problemas de Programación Lineal se expresan

-Los modelos se pueden representar en su forma

El esfuerzo se centra tanto en la construcción

En estos problemas se trata de calcular el valor de las

◼ Z: Valor de la medida global de efectividad. También llamada Función Objetivo, es el

m am1 am2 amn bm

❖ El método de solución gráfica es aplicable sólo a problemas

❖ No obstante, dos variables no son suficientes para describir o

Si la utilidad es de $8 u.m. por mesa y de $6 u.m. por silla. El problema es

Hay dos limitaciones (restricciones) en el problema: El tiempo disponible de

Mesa (u) Silla (u) Horas Directas

1.- Definición de Variables de Decisión: Cantidad de sillas y mesas a producir

Xm: cantidad de mesas a producir (u)

Así, se grafica la primera restricción como la ecuación:

También podría gustarte