Tema 7 - Programación lineal - completo - Agostina Salas

Vista previa del material en texto

Unidad 7: 
Programación lineal
La unidad 7 es de programación lineal. Todo lo que estudiamos en el desarrollo de álgebra geometría analítica en las unidades anteriores datan de cientos de años, pero en esta unidad tenemos la oportunidad de estudiar muy brevemente la base de la programación lineal un tema que tienen su origen en el siglo 20. 
 
La programación lineal, como otras ramas de la matemática, se originó con el objetivo de resolver problemas prácticos. A diferencia de las matemáticas de siglos anteriores, que estaban muchas veces enraizadas en problemas de física y en problemas de astronomía, la programación lineal se creó a partir de un esfuerzo por resolver problemas relacionados con negocios, con economía, con planeación militar, solo por citar algunos. 
 
 
Entonces, el objetivo de esta clase va a ser el de adquirir la habilidad para razonar matemáticamente modelos que se puedan resolver a través de la programación lineal.
 
1
Programación lineal
Inecuaciones lineales con una variable
Inecuaciones lineales con dos variables
Sistema de inecuaciones lineales
PROGRAMACIÓN LINEAL
Modelo matemático
Satisfacción eficiente de los recursos
Satisfacción 
de metas
Se destina a:
Tiene como fin:
Hoy primeramente vamos a desarrollar conceptos teóricos que necesitamos para que ustedes puedan entender en qué consiste o cómo se resuelve un problema de programación lineal. Para esto, vamos a dar brevemente este los conceptos de: 
inecuaciones lineales con una variable (que ustedes ya lo vieron en la unidad 1 de álgebra), 
inecuaciones lineales con dos variables, que eso no dieron, pero no creo que les resulte muy difícil, 
sistema de inecuaciones lineales, acabamos de ver sistema de ecuaciones lineales así que tampoco creo o considero que vayan a tener dificultades
 
Y estos tres temas son para entrar en lo que es programación lineal.
 
La programación lineal en (síntesis porque después vamos a ver más profundamente) es un modelo matemático que se destina a: la satisfacción eficiente de los recursos y que tiene como fin la satisfacción de metas. Eso en síntesis, ya vamos a ver después más profundamente a qué se refiere esto pero es fundamentalmente un modelo matemático.
2
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.
Bueno, este es el tema que ustedes vieron en la unidad 1 en inecuaciones lineales. Cuando tenemos inecuaciones lineales con una variable sabemos que es una desigualdad algebraica, a diferencia de una ecuación que es una igualdad, en el caso de una inecuación es una desigualdad que divide dos miembros. En el caso de la igualdad los miembros están separados por el signo igual, pero en la desigualdad están involucrados los signos menor, menor o igual, mayor, o mayor o igual. Esto es lo que vieron ustedes en la unidad 1. Siempre vamos a intercambiar los términos “inecuación” y “desigualdad lineal”.
 
¿Qué significa resolver una inecuación lineal con una variable o incógnita? Significa hallar todos los valores que hagan verdadera esa desigualdad. Como vieron en la unidad 1 no hay una única solución, sino que tenemos infinitas soluciones y el resultado de resolver una inecuación es un intervalo o una unión de intervalos. ¿Se acuerdan geométricamente como hacíamos para representar esto? ¿Cómo representábamos geométricamente un intervalo? “Con una recta numérica” Exactamente. Los intervalos corresponden a: 
segmentos de rectas 
semirrectas o
a la misma recta real,
depende de cuál sea la solución.
 
Eso fue un pequeño repaso de la unidad 1. 
3
La suma de tres números ha de ser mayor que 10. El segundo es la mitad del primero, y el tercero el triple del segundo. 
Encuentra las soluciones y elige algunos ejemplos numéricos, comprobando que se cumplan las condiciones pedidas.
⇒
➤ Si 
➤ Si 
	a	b	c	suma
				
				
				
Ejemplos numéricos:
4
 
2
6
12
6
3
9
18
7
3,5
10,5
21
Ejercicio 1
Vamos a comenzar a trabajar un poco con inecuaciones. 
En el ejercicio 1 dice: la suma de tres números ha de ser mayor que 10, el segundo es la mitad del primero y el tercero es el triple del segundo. Encuentra las soluciones y elige algunos ejemplos numéricos comprobando que se cumplan las condiciones pedidas. Entonces ahora tenemos que traducir esto que está en lenguaje coloquial al lenguaje algebraico. Si los tres números son a b y c, ¿cómo traduzco la suma de tres números ha de ser mayor que 10? ¿cómo hago para expresar eso en lenguaje algebraico? “a + b + c > 10”. Etc.
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 .
La gráfica del 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.
Veamos la definición de inecuación lineal de dos variables:
Una desigualdad lineal, o una inecuación lineal … 
La gráfica del conjunto solución… 
 
La gráfica de una ecuación lineal más e igual a 0 que ya saben que es una recta divide al plano en dos semiplanos. 
5
La gráfica de una recta separa al plano en tres partes distintas.
1) La recta misma:
Inecuaciones lineales con dos variables
2) El semiplano 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: 
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.
En esta diapositiva, la gráfica de la recta va a dividir o va a separar el plano en tres partes distintas
¿cuáles les parecen que van a ser esas tres partes? “En la parte mayor, la menor y menor y la igual”. Exactamente, 
la recta misma viene a hacerle igual, esto es: todos los puntos que satisfagan la ecuación de la recta. 
la región por encima en la recta o el semiplano por encima de la recta que son todos los puntos cuyas coordenadas satisfacen la desigualdad “”.
el semiplano por debajo de la recta que, contrariamente a lo que dijimos antes, van a ser todos los puntos que satisfacen la in ecuación “”. 
6
La gráfica de una recta separa al plano en tres partes distintas.
1) La recta misma:
Inecuaciones lineales con dos variables
2) El semiplano 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: 
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
¿Qué condición debe cumplir un número “y” para que sea siempre menor que el doble de otro número “x”, menos 1?
Indicar de qué manera se representa una inecuación que involucra una variable y de qué manera se representa una inecuación que involucra dos variables en relación lineal.
Ejercicio 2
	x	0	1	2	3
	y				
Ejemplos:
Representación Inecuación
Una variable
Dos variables
Intervalo o unión de intervalos en la recta real
∞ soluciones
Todos los puntos (x; y) del plano, cuyas coordenadas satisfacen dicha desigualdadHablar de la dependencia lineal de “y” con respecto a “x”.
8
¿Qué condición debe cumplir un número “y” para que sea siempre menor que el doble de otro número “x”, menos 1?
Indicar de qué manera se representa una inecuación que involucra una variable y de qué manera se representa una inecuación que involucra dos variables en relación lineal.
Ejercicio 2
¿C´omo resolveríamos esto gráficamente?
1) Representamos la recta 
2) Determinar si la solución es el semiplano por encima de la recta, o el semiplano por debajo de ella.
Falso
Elegimos dos puntos del plano, por ejemplo: (0;0) y (2,0)
Verdadero
Esto no estaba en la consigna pero veamos cómo resolver este problema gráficamente
9
Sistema de inecuaciones lineales – Ejercicio 3
Un sistema de INECUACIONES es un conjunto de inecuaciones de dos variables que actúan a la vez.
⇒ 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.
Definir sistema de inecuaciones
10
¿Cuáles son los pares de valores que verifican simultáneamente las siguientes condiciones?
Ejercicio 3
Ejercicio 3
1
2
3
1
Otra forma:
Solución del sistema
Primero encontramos la forma explícita de la recta
11
¿Cuáles son los pares de valores que verifican simultáneamente las siguientes condiciones?
Ejercicio 3
Ejercicio 3 – Otra forma
1
2
3
1
Solución del sistema
Solución del sistema
12
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.
“La investigación operativa es un conjunto de herramientas….” “La programación lineal es una técnica matemática, un modelo matemático”
En cualquier organización económica, empresa, negocio, etc. Muchas de las decisiones que se toman tienen por objeto hacer el mejor uso posible (optimización) de los recursos de la misma.
 
Por recursos de una empresa entendemos la maquinaria que esta posea, sus trabajadores, capital financiero, instalaciones y materias primas que disponga.
 
Tales recursos pueden ser usados para fabricar productos o servicios.
 
La programación lineal es una técnica de modelado que se utiliza para determinar la asignación óptima de recursos en finanzas, en empresas y en otros campos de la actividad humana.
 
Es un modelo matemático diseñado para ayudar en la planificación y toma de decisiones referentes a la asignación de recursos.
13
Programación lineal – Características - Ejercicio 4 a
En cualquier ámbito que se presente un problema de PL, tiene cuatro propiedades comunes:
4) El problema debe plantear distintas alternativas posibles
1) Un conjunto de variables NO NEGATIVAS, referidas a la actividad que se desarrolla en el sistema que se quiere optimizar.
2) Un conjunto de restricciones lineales de las variables que expresan la relación entre el consumo de los recursos de los mismos, así como toda clase de características que hay que imponer al problema y que están asociadas a la actividad que se realiza en el sistema.
3) Una función obtjetivo: Criterio que se desea optimizar
Dados los siguientes modelos de programación lineal:
Maximizar:
F.O.: 6x+3y Sujeto a 
 e 
, , 
Maximizar: F.O.: 
14
Programación lineal – Función objetivo
En un problema de programación lineal en dos variables se trata de optimizar (hacer máximo o mínimo según sea el caso) una función, llamada función objetivo, de la forma:
Sujeta una serie de condiciones o restricciones dadas por las situaciones que describen el problema y se expresan en un sistema de inecuaciones lineales del tipo:
donde son llamadas variables de decisión 
(nosotros trabajamos con dos variables de decisión) 
F.O.: 
 → variables de decisión del problema
15
Programación lineal – 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. 
F.O.: 
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.) 
Maximizar: 
16
Programación lineal – 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.
17
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:
Certidumbre. Certeza de datos, se suponen ciertos los datos utilizados. Todos los parámetros del modelo son constantes conocidas que surgen de la realidad de la situación planteada.
Aditividad. Los efectos de las diferentes actividades son independientes y se suman en forma algebraica. No hay interacción entre las variables, es decir que una misma porción de un recurso no puede usarse para producir dos actividades diferentes. Para cada función, el valor total de la función se puede obtener sumando las contribuciones individuales de las actividades respectivas.
Proporcionalidad. Los niveles de utilización de los recursos por unidad de actividad se suponen constantes. La PL no toma en cuenta los rendimientos marginales físicos variables, se acepta la linealidad de las variables.
Divisibilidad. Todas las actividades son continuas y pueden tomar cualquier valor, sea entero o fraccionario. Las variables de decisión pueden asumir valores no enteros.
Certidumbre: se refiere a los parámetros del modelo, que son los valores o números reales multiplicando a cada variable. Se supone que estos valores o parámetros son conocidos
Proporcionalidad: es un supuesto tanto como para la función objetivo como para las restricciones estructurales y de positividad. El valor de la FO siempre tiene que ser proporcional al nivel de actividad de la variable x y la variable y. ¿Recuerdan cuándo un valor era proporcional a otro? Por ejemplo, 2x es proporcional a x. La proporcionalidad se refiere a que las variables x e y no pueden tener exponentes distintos de 1. 
Aditividad: se refiere a que cada función de un modelo de programación lineal, ya sea otra vez a la función objetivo o a las restricciones en la suma de las contribuciones individuales, no se mezclan o no se mezclan, cada uno hace su contribución separadas digamos. En eso se basa esta hipótesis de aditividad 
Divisibilidad: la última que es la de divisibilidad en un modelo de programación lineal las variables de decisión pueden tomar cualquier valor, no hace falta que sean enteros, pueden ser cualquier valor real: pueden ser números fraccionarios y por eso hablamos de divisibilidad las variables no están restringidas solamente a valores enteros
18
Programación lineal –Solución por el método gráfico
Los puntos del plano que satisfacen cada desigualdad determinan un semiplano y los puntos que satisfacen todas las desigualdades (inecuaciones) 
determinan un recinto convexo finito (polígono) o infinito llamado región de validez del problema o zona factible, incluyendo los puntos de la frontera que lo acotan (lados y vértices).
Para resolver problemas que presentan sólo dos variables de decisión. 
Consiste en representar las ecuaciones de las restricciones en un sistema de coordenadas 
para identificar el área de soluciones factibles, aquellas que cumplen con todas las restricciones.
Hablar de que un polígono es finito y el otro infinito si se puede o no encerrar en un círculo
El conjunto es finito pero la cantidad de soluciones que se pueden obtener son infinitas
19
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. 
20
Programación lineal – Solución por el método gráfico
Los puntos de la zona factible, que cumplen todas las restricciones a la vez son soluciones factibles. 
Los puntos que cumplen todas y cada una de las desigualdades, están en un recinto convexo cerrado (poligonal) o abierto, llamado región o zona factible. 
Los vértices de esa región se llaman puntos extremos.
Una vez representada la zona factible y hallada la solución óptima, se representa la función objetivo en el punto óptimo, trasladando la recta que representa a la en forma paralela hasta que toque el punto óptimo.
La solución factible que haga óptima (máxima o mínima) la función objetivo, se llama solución óptima.
21
Programación lineal – Solución por el método gráfico
Una vez representada la zona factible y hallada la solución óptima, 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.
Si hay una única solución esta estará en un vértice del recinto. Si hay infinitas soluciones, éstas se encontrarán sobre un lado del recinto. 
Función objetivo
Si hay una única solución, esta va a estar representada en el vértice del polígono.
Si hay una única solución esta estará en un vértice del recinto. Si hay infinitas soluciones, éstas se encontrarán sobre un lado del recinto. Es posible que no haya solución óptima, pues cuando el recinto es abierto, la F.O. puede crecer o decrecer indefinidamente. 
22
Ejercicio 5 - a
Dados los siguientes modelos de programación lineal:
Maximizar:
F.O.: 6x+3y Sujeto a 
i) Determinar gráficamente la zona factible
1
2
3
1
2
ZONA 
FACTIBLE
Está marcado lo que NO es.
23
Ejercicio 5 - a
Dados los siguientes modelos de programación lineal:
Maximizar:
F.O.: 6x+3y Sujeto a 
ii) Encontrar las coordenadas de los puntos extemos de la zona factible.
intersección de las rectas y
1
2
3
1
2
ZONA 
FACTIBLE
Si un problema de programación lineal tienen una solución, entonces esta debe aparecer en un vértice, o esquina, del conjunto factible S asociado con el problema.
24
Ejercicio 5 - a
Dados los siguientes modelos de programación lineal:
Maximizar:
F.O.: 6x+3y Sujeto a 
iii) Calcular la función objetivo en el punto óptimo
Maximiza
ZONA 
FACTIBLE
25
Ejercicio 5 - a
Dados los siguientes modelos de programación lineal:
Maximizar:
F.O.: 6x+3y Sujeto a 
iv) Trazar la función objetivo en el punto óptimo
Función objetivo
Valor máximo
ZONA 
FACTIBLE
Nos conviene usar la segmentaria
26
27
Ejercicio 6
Un fabricante de calculadoras produce dos modelos: estándar y científica. La demanda a largo plazo para los dos modelos recomienda que la compañía fabrique al menos 100 calculadoras estándar y 80 científicas al día. No obstante, debido a limitaciones en la capacidad de producción, no pueden manufacturarse más de 200 calculadoras estándar y 170 científicas al día. Para satisfacer el contrato firmado, se debe enviar un total de al menos 200 calculadoras por día. Si el costo de producción es de U$s 5 por una calculadora estándar y U$s7 por una científica, ¿cuántas de cada modelo se deben producir al día para minimizar este costo? 
Minimizar:
Si: 
Zona
Factible
A
B
C
D
E
28
Ejercicio 6
Un fabricante de calculadoras produce dos modelos: estándar y científica. La demanda a largo plazo para los dos modelos recomienda que la compañía fabrique al menos 100 calculadoras estándar y 80 científicas al día. No obstante, debido a limitaciones en la capacidad de producción, no pueden manufacturarse más de 200 calculadoras estándar y 170 científicas al día. Para satisfacer el contrato firmado, se debe enviar un total de al menos 200 calculadoras por día. Si el costo de producción es de U$s 5 por una calculadora estándar y U$s7 por una científica, ¿cuántas de cada modelo se deben producir al día para minimizar este costo? 
Minimizar:
Zona
Factible
A
B
C
D
E
Para hallar : 
(e,c)
29
Ejercicio6
Un fabricante de calculadoras produce dos modelos: estándar y científica. La demanda a largo plazo para los dos modelos recomienda que la compañía fabrique al menos 100 calculadoras estándar y 80 científicas al día. No obstante, debido a limitaciones en la capacidad de producción, no pueden manufacturarse más de 200 calculadoras estándar y 170 científicas al día. Para satisfacer el contrato firmado, se debe enviar un total de al menos 200 calculadoras por día. Si el costo de producción es de U$s 5 por una calculadora estándar y U$s7 por una científica, ¿cuántas de cada modelo se deben producir al día para minimizar este costo? 
Minimizar:
Zona
Factible
A
B
C
D
E
Para hallar : 
30
Ejercicio 5
Un fabricante de calculadoras produce dos modelos: estándar y científica. La demanda a largo plazo para los dos modelos recomienda que la compañía fabrique al menos 100 calculadoras estándar y 80 científicas al día. No obstante, debido a limitaciones en la capacidad de producción, no pueden manufacturarse más de 200 calculadoras estándar y 170 científicas al día. Para satisfacer el contrato firmado, se debe enviar un total de al menos 200 calculadoras por día. Si el costo de producción es de U$s 5 por una calculadora estándar y U$s7 por una científica, ¿cuántas de cada modelo se deben producir al día para minimizar este costo? 
Minimizar:
Zona
Factible
A
B
C
D
E
Mín
31
Ejercicio 6
Un fabricante de calculadoras produce dos modelos: estándar y científica. La demanda a largo plazo para los dos modelos recomienda que la compañía fabrique al menos 100 calculadoras estándar y 80 científicas al día. No obstante, debido a limitaciones en la capacidad de producción, no pueden manufacturarse más de 200 calculadoras estándar y 170 científicas al día. Para satisfacer el contrato firmado, se debe enviar un total de al menos 200 calculadoras por día. Si el costo de producción es de U$s 5 por una calculadora estándar y U$s7 por una científica, ¿cuántas de cada modelo se deben producir al día para minimizar este costo? 
Minimizar:
Zona
Factible
A
B
C
D
E
Se minimiza el costo cuando:
Para graficar la función objetivo:
Si 
F.O.
32
Ejercicio 7
Una pequeña fábrica de calzado hace dos estilos de zapatos: náutico y mocasín. En el proceso se utilizan dos máquinas: una cortadora y una de coser. En la tabla se proporcionan los tiempos de fabricación de los artículos. Si la utilidad es de U$s15 en cada par de náuticos y U$s20 en cada par de mocasines, ¿cuántos pares de cada tipo se deben producir al día para maximizar la utilidad? 
Maximizar:
1
2
1
2
A
B
C
D
Zona
Factible
33
Ejercicio 7
Una pequeña fábrica de calzadohace dos estilos de zapatos: náutico y mocasín. En el proceso se utilizan dos máquinas: una cortadora y una de coser. En la tabla se proporcionan los tiempos de fabricación de los artículos. Si la utilidad es de U$s15 en cada par de náuticos y U$s20 en cada par de mocasines, ¿cuántos pares de cada tipo se deben producir al día para maximizar la utilidad? 
Maximizar:
1
2
A
B
C
D
Zona
Factible
Para hallar despejamos de ambas ecuaciones y las igualamos:
34
Ejercicio 7
Una pequeña fábrica de calzado hace dos estilos de zapatos: náutico y mocasín. En el proceso se utilizan dos máquinas: una cortadora y una de coser. En la tabla se proporcionan los tiempos de fabricación de los artículos. Si la utilidad es de U$s15 en cada par de náuticos y U$s20 en cada par de mocasines, ¿cuántos pares de cada tipo se deben producir al día para maximizar la utilidad? 
Maximizar:
1
2
A
B
C
D
Zona
Factible
Máx
35
Ejercicio 7
Una pequeña fábrica de calzado hace dos estilos de zapatos: náutico y mocasín. En el proceso se utilizan dos máquinas: una cortadora y una de coser. En la tabla se proporcionan los tiempos de fabricación de los artículos. Si la utilidad es de U$s15 en cada par de náuticos y U$s20 en cada par de mocasines, ¿cuántos pares de cada tipo se deben producir al día para maximizar la utilidad? 
Maximizar:
1
2
A
B
C
D
Zona
Factible
Se maximiza la utilidad cuando:
Para graficar la función objetivo:
Si 
F.O.
36