Tema 7 - Programación lineal - sin ejercicios guia - Agostina Salas

Vista previa del material en texto

Unidad 7: 
Sistema de inecuaciones lineales. 
Programación lineal
Inecuaciones lineales. Conjunto solución. Representación gráfica. Sistemas de inecuaciones con dos variables. Solución analítica y gráfica. Programación lineal. Enfoque geométrico. Solución gráfica. Puntos extremos. Solución óptima. Método de punto en la esquina. Aplicaciones económicas.
Todo lo que estudiamos en el desarrollo de AGA datan de cientos de años.
En esta unidad tenemos la oportunidad de examinar, aunque brevemente, un tema que tiene su origen en el siglo XX.
La PL, como muchas otras ramas de la Matemática, se originó en un intento por resolver problemas prácticos, a diferencia de la matemática de siglos anteriores, a menudo enraizadas en las ciencias como la Física y la Astronomía, la PL se creó a partir de un esfuerzo por resolver problemas relacionados con negocios, economía y planeación militar (por citar algunos).
Cabe señalar que la palabra “programación” no se refiere a un programa de computadoras sino a un programa de acción a fin de maximizar o minimizar costos, recursos, etc. Proviene de la terminología militar de la época de la Segunda Guerra Mundial, durante la cual el entrenamiento, el abastecimiento y los planes de despliegue eran llamados programas. Cada programa era una asignación de recursos.
La programación lineal fue desarrollada por George Dantzig al final de la década de 1940, y la Fuerza Aérea de los Estados Unidos fue quién la utilizó por primera vez en la II Guerra Mundial a fin de reducir costos y aumentar las pérdidas del enemigo. Por esa razón se mantuvo en secreto hasta 1947.
En 1975 Kantorovich y Koopmans ganaron el premio Nobel de Economía por su trabajo en el desarrollo de esta técnica.
Esta técnica de modelado es probablemente la aplicación más importante de sistemas de desigualdades lineales.
OBJETIVOS DE LA CLASE: desarrollar la habilidad de razonar matemáticamente para CONSTRUIR modelos matemáticas que permitan resolver e interpretar problemas sobre cuestiones económicas o administrativas empleando la PL.
1
PROGRAMACIÓN LINEAL
Modelo matemático
Satisfacer metas a través de la descripción de un problema
Asignación eficiente de recursos
Se representa mediante un
Se destina a
Tiene como fin
Alguna de sus aplicaciones son:
Finanzas
Marketing
Logística
Producción
Asignación de recursos
La programación lineal es una técnica de modelado cuyo objetivo es la asignación eficiente de recursos. Es decir, satisfacer metas a través de la descripción de un problema.
 Se utiliza para determinar la asignación óptima de recursos en finanzas, marketing, logística, asignación de recursos, producción, etc.
3
Inecuaciones lineales
Con una variable:
Resolver una desigualdad 
que contenga una variable 
significa hallar todos los valores que hagan verdadera la desigualdad.
Desigualdad algebraica
Miembros →se encuentran relacionados por los signos :
   > 
Resultado: Intervalo o unión de intervalos
Geométricamente los intervalos corresponden a 
segmentos de recta, semirrectas o la misma recta real.
Lo vimos en la unidad I
4
Inecuaciones lineales
Con dos variables:
Una desigualdad lineal, o una inecuación lineal, con las variables x e y puede escribirse de una de las siguientes formas:
Siendo .
El conjunto solución de una desigualdad con dos variables está compuesta por todos los puntos del plano cuyas cooordenadas satisfacen la desigualdad.
La gráfica de la ECUACIÓN LINEAL 
 (recta)
divide al plano en dos semiplanos.
Uno de ellos es solución de la inecuación.
5
La gráfica de una recta separa al plano en tres partes distintas.
1) La recta misma:
Inecuaciones lineales con dos variables
2) La región por encima de la recta:
3) El semiplano por debajo de la recta: 
puntos (x;y) cuyas coordenadas satisfacen la ecuación 
puntos (x;y) cuyas coordenadas satisfacen la desigualdad 
puntos (x;y) cuyas coordenadas satisfacen la inecuación 
Si la desigualdad es estricta: 
( o )
La recta no está incluida en la solución de la desigualdad y se representa con linea de puntos
El semiplano solución es ABIERTO.
6
La gráfica de una recta separa al plano en tres partes distintas.
1) La recta misma:
Inecuaciones lineales con dos variables
2) La región por encima de la recta:
3) El semiplano por debajo de la recta: 
puntos (x;y) cuyas coordenadas satisfacen la ecuación 
puntos (x;y) cuyas coordenadas satisfacen la desigualdad 
puntos (x;y) cuyas coordenadas satisfacen la inecuación 
Si la desigualdad NO es estricta: 
( o )
La solución , la solución consiste en la recta y en el semiplano por debajo de ella. 
El semiplano solución es CERRADO.
La solución , la solución consiste en la recta y en el semiplano por encima de ella. 
La recta SI está incluida en la solución de la desigualdad y se representa con linea continua.
7
La gráfica de una recta separa al plano en tres partes distintas.
1) La recta misma:
Inecuaciones lineales con dos variables
2) La región por encima de la recta:
3) El semiplano por debajo de la recta: 
puntos (x;y) cuyas coordenadas satisfacen la ecuación 
puntos (x;y) cuyas coordenadas satisfacen la desigualdad 
puntos (x;y) cuyas coordenadas satisfacen la inecuación 
Los semiplanos que quedan determinados son DISYUNTOS (o disjuntos) , 
es decir, no tienen ningún punto en común
8
Inecuaciones lineales con dos variables - Ejemplo
1) Representamos la recta 
2) Determinar cuál de los semiplanos satisface la inecuación 
Podemos asegurarnos 
que seleccionamos el semiplano correcto 
eligiendo un punto y verificando:
Ejemplo → el punto 
x
Ejemplo → el punto 
✓
9
Sistema de inecuaciones lineales
Un sistema de INECUACIONES es un conjunto de inecuaciones de dos variables que actúan a la vez.
Geométricamente, es la REGIÓN común para todas las regiones determinadas por las desigualdades dadas.
⇒ es la intersección de los conjuntos solución de cada desigualdad del sistema.
La SOLUCIÓN de un sistema de desigualdades 
consiste en todos los puntos cuyas coordenadas 
satisfacen de manera SIMULTÁNEA todas las desigualdades dadas.
10
¿Cuáles son los pares de valores que verifican simultáneamente las siguientes condiciones?
Sistema de inecuaciones lineales - Ejemplo
1
2
3
1
Otra forma:
Solución 
del 
sistema
11
¿Cuáles son los pares de valores que verifican simultáneamente las siguientes condiciones?
Sistema de inecuaciones lineales – Ejemplo – Otra forma
1
2
3
1
Otra forma:
Pintar la zona que NO es solución
Solución 
del 
sistema
12
¿Cuáles son los pares de valores que verifican simultáneamente las siguientes condiciones?
 
Sistema de inecuaciones lineales - Ejemplo
1
2
1
Otra forma:
2
 
 
Otra forma:
 
 
 
Solución 
del 
sistema
13
Sistema de inecuaciones lineales acotado y no acotado
Cuando una región del plano puede ser cubierta por un círculo 
(suficientemente grande)
Región limitada o acotada
Cuando una región del plano NO puede ser cubierta por un círculo
Región limitada o No acotada
Programación lineal
Herramienta más importante de la INVESTIGACIÓN OPERATIVA
Conjunto de herramientas 
de las que dispone la matemática para la toma de decisiones.
Técnica matemática 
para hallar la mejor asignación 
de los recursos limitados de una empresa (optimizar) 
a actividades que compiten entre sí por ellos.
Como dijimos antes, la PL es una técnica de modelado.
Es la herramienta más importante de la INVESTIGACIÓN OPERATIVA
La investigación de operaciones, también llamada investigación operativa, es una disciplina que se ocupa de la aplicación de métodos analíticos avanzados para ayudar a tomar mejores decisiones
Empleando técnicas de otras ciencias matemáticas, como modelado matemático, análisis estadístico y optimización, la investigación de operaciones llega a soluciones óptimas o casi óptimas para problemas complejos de toma de decisiones.15
Programación lineal
Técnica matemática 
para hallar la mejor asignación 
de los recursos limitados de una empresa (optimizar) 
a actividades que compiten entre sí por ellos.
La función a MAXIMIZAR o MINIMIZAR se llama FUNCIÓN OBJETIVO
Sujeta a 
RESTRICCIONES
Representadas por 
un sistema de desigualdades lineales 
o ecuaciones lineales
META: encontrar una que sea una SOLUCIÓN ÓPTIMA (le de el máximo o mínimo valor a la función objetivo.
Situación que involucra todas estas condiciones
Problema de Programación Lineal
La PL es una técnica muy potente que se utiliza para construir modelo de optimización de funciones, que pueden aplicarse a cualquier rama de las ciencias económicas.
En cada problema de PL se deben tomar decisiones de maximización o minimización de objetivos representados por funciones lineales, las cuales están sujetas a determinadas condiciones llamadas restricciones que se representan a través de ecuaciones y/o desigualdades lineales.
Nosotros estudiaremos un método para resolver estos problemas: el gráfico.
Existe también un método analítico, llamado simplex, que se utiliza para resolver problemas con cualquier número de variables.
16
Programación lineal – Supuestos básicos
La búsqueda de una solución óptima mediante el uso de la PL, implica la preparación de un modelo. 
La elaboración del modelo matemático tiene limitaciones de naturaleza técnica y su formulación está basada en las siguientes hipótesis fundamentales:
Los datos son ciertos.
Surgen de la realidad de la situación planteada
Las variables pueden tomar cualquier valor (enteros o fraccionarios)
Se considera la linealidad de las variables
Los efectos de las distintas variables son independientes. No hay interacción entre ellas.
17
PROGRAMACIÓN LINEAL
CERTIDUMBRE
ADITIVIDAD
PROPORCIONALIDAD
DIVISIBILIDAD
Programación lineal – Características 
En cualquier ámbito que se presente un problema de PL, tiene cuatro propiedades comunes:
1
Variables no negativas
Todas las variables que intervienen en el problema deben ser no negativas.
2
Restricciones
Se refieren a las limitaciones o condicionamientos de los recursos o factores económicos.
3
Existencia de una función lineal de las variables cuyo valor se desea optimizar
Expresión matemática de la meta a alcanzar formulada en función de las variables.
4
El problema debe presentar las distintas alternativas posibles
Las técnicas de PL han sido utilizadas en ámbitos diferentes como el militar, industrial, financiero, etc.
A pesar de tal diversidad en las aplicaciones, todos los problemas de PL tienen cuatro propiedades comunes:
18
Características de un problema de PL – Restricciones
Las condiciones que se deben cumplir son limitaciones a las diferentes alternativas que se pueden presentar, esas condiciones se denominan restricciones, y se expresan matemáticamente a través de un conjunto de inecuaciones y/o ecuaciones lineales. 
Pueden ser de dos tipos:
Restricciones estructurales: se refieren a las limitaciones o condicionamientos de los recursos o factores económicos. Cada actividad consume una cierta cantidad de recursos (capacidad de la planta, capital, mano de obra, etc.) que no se puede sobrepasar.
Restricciones de no negatividad: como se trata de funciones en economía, no tiene sentido que las variables asuman valores negativos. Este tipo de restricciones garantiza que ninguna de las variables sea negativa.
La región que satisface de manera simultánea las restricciones se denomina ZONA FACTIBLE.
Cada punto en esta región representa una solución del sistema.
Aunque existe un número infinito de soluciones factibles, debemos encontrar una que maximice o minimice la función objetivo.
19
Características de un problema de PL – Función objetivo
Es la expresión matemática de la meta a alcanzar formulada en función de las variables de decisión. 
Debe definirse claramente y en forma matemática como una ecuación lineal. 
Se orienta a optimizar algún criterio de valor, lo que se optimiza es una función matemática que contiene los resultados. 
Puede resolver dos tipos de problemas:
Maximizar un determinado criterio de valor (margen bruto total, producción total, ingreso total, beneficios, etc.)
Minimizar un criterio de valor (costo total, uso de un recurso, etc.) 
20
Características de un problema de PL – Alternativas posibles
Determinadas por los puntos que cumplen todas y cada una de las restricciones.
Están en una porción del plano llamada REGIÓN o ZONA FACTIBLE.
Los puntos que cumplen todas las restricciones a la vez son SOLUCIONES FACTIBLES.
21
Programación lineal – Solución por el método gráfico
En cumplimiento de las restricciones de no negatividad, 
se trabaja en el I cuadrante, 
donde las dos variables son mayores o iguales a cero. 
22
Programación lineal – Solución por el método gráfico
Para resolver problemas que presentan sólo dos variables de decisión. 
1
Representar las ecuaciones o inecuaciones que representan las restricciones en un sistema de coordenadas .
2
Las mismas determinarán un recinto convexo cerrado (poligonal) o abierto llamado zona factible (cumple todas las restricciones simultáneamente)
3
Dicha zona incluye los puntos de frontera: los vértices del recinto que queda determinado.
4
Todos los puntos de la zona o región factible son soluciones factibles.
5
Encontrar UNA de esas soluciones que maximice o minimice la función objetivo.
Se trata de buscar un miembro de la familia que tenga un punto factible, y en el ejemplo del gráfico, cuyo valor de la función objetivo sea máximo. Deberá tener al menos un punto en común con la región factible.
Cualquier recta de isoutilidad con una utilidad mayor no contendrá puntos en común con la región factible.
23
Programación lineal – Solución por el método gráfico
6
Ya que la función objetivo tiene la siguiente forma:
Define una familia de rectas paralelas, cada una con pendiente y ordenada al origen 
Para distintos valores de obtendremos distintas rectas, todas paralelas entre sí.
Cada una de estas rectas representan cada una de las combinaciones de y de con las que se obtiene el mismo valor de la función objetivo.
Se denominan rectas de ISOUTILIDAD.
Lineas de isoutilidad
Tienen un número infinito 
de puntos en común 
con la región factible
No tiene puntos en común 
con la región factible
Buscamos un miembro de la familia que tenga UN punto factible y que el valor de sea máximo (o mínimo)
Una función lineal definida sobre una región factible no vacía, tiene un valor máximo o mínimo que puede hallarse en un vértice (punto extremo, esquina).
Esto nos da una forma de encontrar una solución óptima sin necesidad de representar las rectas de isoutilidad. Basta con evaluar la función objetivo en cada uno de los vértices de la región factible y después seleccionar un vértice en que la función sea óptima.
24
Programación lineal – Solución por el método gráfico
La función objetivo (lineal) definida sobre una región factible tiene un valor máximo o mínimo en un VÉRTICE (punto extremo, esquina)
⇒No es necesario representar todas 
las rectas de isoutilidad
Basta con evaluar la función 
en cada uno de los vértices de la región factible y luego seleccionar aquél en el que la función sea óptima.
7
Se representa la función objetivo en el punto óptimo.
La solución factible que haga óptima (máxima o mínima) la función objetivo, se llama solución óptima.
25
Dados el siguiente modelo de programación lineal:
Maximizar:
F.O.: Sujeto a 
Programación lineal – Solución por el método gráfico - Ejemplos
Función objetivo
Restricciones
26
Dados los siguientes modelos de programación lineal:
Maximizar:
F.O.: Sujeto a 
i) Determinar gráficamente la zona factible
1
2
3
1
2
Programación lineal – Solución por el método gráfico - Ejemplos
3
 
27
Dados los siguientes modelos de programación lineal:
Maximizar:
F.O.: Sujetoa 
1
2
3
Programación lineal – Solución por el método gráfico - Ejemplos
 
ZONA 
FACTIBLE
Si un problema de programación lineal tiene una solución, entonces esta debe aparecer en un vértice, o esquina, del conjunto factible S asociado con el problema.
ii) Encontrar las coordenadas de los puntos extemos de la zona factible.
intersección de las rectas y
1
2
28
Dados los siguientes modelos de programación lineal:
Maximizar:
F.O.: Sujeto a 
1
2
3
Programación lineal – Solución por el método gráfico - Ejemplos
 
ZONA 
FACTIBLE
Si un problema de programación lineal tiene una solución, entonces esta debe aparecer en un vértice, o esquina, del conjunto factible S asociado con el problema.
iii) Calcular la función objetivo en el punto óptimo
Maximiza
29
Dados los siguientes modelos de programación lineal:
Maximizar:
F.O.: Sujeto a 
1
2
3
Programación lineal – Solución por el método gráfico - Ejemplos
 
ZONA 
FACTIBLE
Si un problema de programación lineal tiene una solución, entonces esta debe aparecer en un vértice, o esquina, del conjunto factible S asociado con el problema.
iv) Trazar la función objetivo en el punto óptimo
Función objetivo
Valor máximo
30
31
Considere la función lineal:
 Sujeta a las restricciones 
Minimizar
Programación lineal – Solución por el método gráfico - Ejemplos
i) Determinar gráficamente la zona factible
1
2
3
1
 
2
3
Zona factible
32
Considere la función lineal:
 Sujeta a las restricciones 
Minimizar
Programación lineal – Solución por el método gráfico - Ejemplos
1
2
3
Zona factible
ii) Encontrar las coordenadas de los puntos extemos de la zona factible.
intersección de las rectas y
1
2
33
Considere la función lineal:
 Sujeta a las restricciones 
Minimizar
Programación lineal – Solución por el método gráfico - Ejemplos
1
2
3
Zona factible
iii) Calcular la función objetivo en el punto óptimo
Minimiza
34
Considere la función lineal:
 Sujeta a las restricciones 
Minimizar
Programación lineal – Solución por el método gráfico - Ejemplos
1
2
3
Zona factible
iv) Trazar la función objetivo en el punto óptimo
35
Programación lineal – Solución por el método gráfico - Ejemplos
Una compañía produce dos tipos de artículos: manuales y eléctricos.
Cada uno requiere para su fabricación del uso de tres máquinas A, B y C.
La siguiente tabla da la información relacionada con la fabricación de los mismos.
		A	B	C	Utilidad/unidad
	Manual	2 hs	1 h	1 h	$ 4
	Eléctrico	1 h	2 hs	1h	$ 6
	Horas disponibles	180	160	100	
Cada artículo manual requiere del uso de la máquina A durante 2 horas, de la máquina B por una hora y de la máquina C otra hora..
Un artículo eléctrico requiere 1 hora de la máquina A, 2 horas de la máquina B y 1 hora de la C.
Además, el número máximo de horas disponibles por mes para el uso de las máquinas A, B y C es de 180, 160 y 100 respectivamente.
La utilidad por cada artículo manual es de $4 y por cada artículo eléctrico $6.
Si la compañía vende todos los artículos que puede producir, ¿cuántos artículos de cada tipo debe producir con el fin de maximizar la utilidad mensual?
→ cant. art. manuales
→ cant. art. eléctricos
Para la máquina A:
Para la máquina B:
Para la máquina C:
Utilidad es una función de e :
Programación lineal – Solución por el método gráfico - Ejemplos
Una compañía produce dos tipos de artículos: manuales y eléctricos.
Cada uno requiere para su fabricación del uso de tres máquinas A, B y C.
La siguiente tabla da la información relacionada con la fabricación de los mismos.
		A	B	C	Utilidad/unidad
	Manual	2 hs	1 h	1 h	$ 4
	Eléctrico	1 h	2 hs	1h	$ 6
	Horas disponibles	180	160	100	
Si la compañía vende todos los artículos que puede producir, ¿cuántos artículos de cada tipo debe producir con el fin de maximizar la utilidad mensual?
→ cant. art. manuales
→ cant. art. eléctricos
Para la máquina A:
Para la máquina B:
Para la máquina C:
Utilidad es una función de e :
Maximizar:
Sujeto a
Programación lineal – Solución por el método gráfico - Ejemplos
Maximizar:
Sujeto a
1
1
2
2
3
3
Zona factible
i) Determinar gráficamente la zona factible
38
Programación lineal – Solución por el método gráfico - Ejemplos
Maximizar:
Sujeto a
1
2
3
Zona factible
ii) Encontrar las coordenadas de los vértices.
 intersección entre las rectas y 
1
3
⇒
 intersección entre las rectas y 
2
3
⇒
⇒
39
Programación lineal – Solución por el método gráfico - Ejemplos
Maximizar:
Sujeto a
1
2
3
Zona factible
iii) Evaluar la función objetivo en cada uno de los puntos
40
Programación lineal – Solución por el método gráfico - Ejemplos
Maximizar:
Sujeto a
1
2
3
Zona factible
iv) Trazar la función objetivo en el punto óptimo.
 
41