Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas...
-
Upload
carlos-picano -
Category
Documents
-
view
218 -
download
0
Transcript of Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas...
![Page 1: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/1.jpg)
![Page 2: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/2.jpg)
Objetivos
• Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos.
• Saber plantear un problema de programación lineal partiendo de su enunciado en términos generales.
• Conocer y valorar el origen de la programación lineal y su influencia en la historia.
• Dominar el lenguaje propio de la programación lineal: función objetivo, restricciones, región factible, etc...
![Page 3: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/3.jpg)
Competencias:El alumno utilizando correctamente la resolución de ecuaciones e inecuaciones será capaz de maximizar beneficios y minimizar pérdidas.
Conocimientos previos:Sistemas de Ecuaciones e Inecuaciones de 1er
grado con dos variablesFunciones lineales
![Page 4: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/4.jpg)
Breve Reseña Histórica
1776 Gaspar Monge
1939 Leonid V. Kantorovitch publica Métodos matemáticos de organización y planificación de la producción.
1941-1942 Problema de transporte
Post Guerra: EE.UU. Proyecto SCOOP Uso de la Programación Lineal para administrar energía y recursos de la Nación.
1947 Dantzig y el Método Simplex
El nombre de PL procede del
término militar “programar” =
realizar planes de tiempo para el
entrenamiento o despliegue.
![Page 5: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/5.jpg)
¿Qué es la Programación Lineal?Es un método que se utiliza en la resolución de problemas donde se plantea optimizar el uso de ciertos recursos que se disponen para maximizar utilidades, beneficios, ingresos, eficiencia o minimizar costos, perjuicios, egresos, etc.
![Page 6: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/6.jpg)
¿Qué es un Problema de programación lineal?
Definición: Es una técnica matemática y de investigación de operaciones que se utiliza en la planificación administrativa y económica para maximizar las funciones lineales de un gran número de variables sujetas a determinadas restricciones.
El nombre de programación lineal no procede de la creación deprogramas de ordenador, sino de un término militar, programar, quesignifica realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate.• En sí, se llama programación lineal al conjunto de técnicas matemáticas que
pretenden resolver la siguiente situación:• Optimizar (maximizar o minimizar) una función objetivo, función lineal de
varias variables, sujeta a una serie de restricciones, expresadas por inecuaciones lineales.
![Page 7: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/7.jpg)
Debe cumplir con:
1. La función f(x,y) = ax + by + c llamada función objetivo y que es necesario optimizar. En esa expresión x e y son las variables de decisión, mientras que a, b y c son constantes.
2. Las restricciones que deben ser inecuaciones lineales.
![Page 8: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/8.jpg)
3. La región factible es un polígono convexo y puede ser: acotado, no acotado y vacío, es decir, que no haya ni un solo punto que verifique todas las restricciones al mismo tiempo.
Factibles: Si existe el conjunto de soluciones o valores que satisface lasrestricciones, que a su vez pueden ser:
• Con solución única: La solución es única, y corresponde al vértice para el que la función objetivo toma el valor máximo
• Con solución múltiple: si existe mas de una solución, la función objetivo es paralela
a una de las restricciones. • Con solución no acotada: Cuando no existe límite para la función objetivo, En este
caso no existe un valor extremo para la función objetivo, por lo que puede decirse que el problema carece de solución.
4. No Factibles: Cuando no existe el conjunto de soluciones que cumplen lasrestricciones, es decir, las restricciones son inconsistentes.
![Page 9: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/9.jpg)
Importancia de la programación lineal
La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal. Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución.
![Page 10: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/10.jpg)
Algunos Ejemplos:
• Optimización de la combinación de diámetros comerciales en una red ramificada de distribución de agua.
• Aprovechamiento óptimo de los recursos de una cuenca hidrográfica, para un año con afluencias caracterizadas por corresponder a una determinada frecuencia.
• Soporte para toma de decisión en tiempo real, para operación de un sistema de obras hidráulicas;
• Solución de problemas de transporte.
![Page 11: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/11.jpg)
Ejemplo 1Gerardito es un estudiante que dedica parte de su tiempo al reparto de propaganda publicitaria. La empresa A le paga Lps. 5 por cada impreso repartido y la empresa B, con folletos más grandes, le paga Lps. 7 por impreso. El estudiante lleva dos bolsas: una para los impresos A, en la que caben 120, y otra para los impresos B, en la que caben 100. Ha calculado que cada día es capaz de repartir 150 impresos como máximo. Lo que se pregunta el estudiante es: ¿cuántos impresos habrá de repartir de cada clase para que su beneficio diario sea máximo?
![Page 12: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/12.jpg)
DEFINICIONES
VariablesCantidades
desconocidas
Función Objetivo
Es la que se desea
maximizar o minimizar Z=ax+by+c
Solución Optima Es una solución
factible que maximiza o minimiza la
función objetivoRestricciones
Son las inecuaciones lineales que
limitan la región factible
Solución Factible Es cualquier
punto situado en la región
factible
Región Factible Es el
polígono convexo formado al
resolver gráficamente el
Sistema de Inecuaciones
![Page 13: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/13.jpg)
Planteamiento del Ejemplo 1
Paso 1 (Variables decisorias)Sea x el número de impresos ASea y el número de impresos B
Paso 2 (Construcción de la función objetivo)El objetivo es maximizar la función f(x,y) = z = 5x + 7y
Paso 3 (Restricciones) Máximo de Impresos A igual 120 x ≤ 120 Máximo de Impresos B igual 100 y ≤ 100 150 impresos como máx. x + y ≤ 150, x ≥ 0 , y ≥ 0
![Page 14: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/14.jpg)
Esquema de Solución del Ejemplo 1
• x: numero de impresos A (variable)
• y: número de impresos B (variable)
• Maximizar z = 5x + 7y (Función objetivo)
• Sujeto a:• x ≤ 120 (restricción 1)• y ≤ 100 (restricción 2)• x + y ≤ 150 (restricción 3)
con: x ≥ 0 , y ≥ 0
![Page 15: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/15.jpg)
Representación gráfica de la Región Factible
![Page 16: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/16.jpg)
Evaluando los vértices• Los vértices de la región factible (0;0); (0;100); (50;100);
(120;30) y (120;0)
Vértice (x ; y) z = 5x + 7y(0 ; 0) 0
(0 ; 100) 700
(50 ; 100) 950
(120 ; 30) 810
(120 ; 0) 600
Solución Optima
• Respuesta: Para maximizar la ganancia se debe repartir 50 impresos de la empresa A y 100 impresos de la empresa B.
![Page 17: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/17.jpg)
ALGORITMO DE RESOLUCIÓN
Identificar las variables, la función objetivo y las
restricciones.
Graficar el sistema de desigualdades lineales
que forman las restricciones e identificar
la región factible.
Determinar los vértices de la región factible.
Completar una tabla de valores para la función
objetivo utilizando todos los vértices.
Si se va a maximizar (o minimizar), el valor más
grande (o pequeño) es una solución optima.
Interpretar los resultados.
![Page 18: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/18.jpg)
Problema 1
Dada la región del plano definida por las inecuaciones: x + y – 1 ≥ 0; 0 ≤ x ≤ 3 ; 0 ≤ y ≤ 2.¿Para qué valores de la región es máxima la función Z = 5x + 2y?
Solución:Maximizar z = 5x + 2y (Función objetivo)Sujeto a:
• x+ y ≥ 1 (restricción 1)• x ≤ 3 (restricción 2)• y ≤ 2 (restricción 3)
con: x ≥ 0 , y ≥ 0
![Page 19: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/19.jpg)
• Respuesta: La función Z es máxima para el vértice (3,2), que es 19
![Page 20: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/20.jpg)
Problema 2
Representar gráficamente el conjunto de puntos que satisfacen las siguientes inecuaciones lineales:x + 2y ≤ 10; x + y ≥ 2; x ≤ 8; x ≥ 0; y ≥ 0Hallar el mínimo de F(x,y) = x – 3y
Solución:Maximizar z = x-3y (Función objetivo)Sujeto a:
• x+ 2y ≤ 10 (restricción 1)• x +y ≥ 2 (restricción 2)• x ≤ 8 (restricción 3)
con: x ≥ 0 , y ≥ 0
![Page 21: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/21.jpg)
• Respuesta: El mínimo se alcanza en (0,5) y es - 15
![Page 22: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/22.jpg)
Problema 3
En una fábrica de bombillas se producen dos tipos de ellas, las de tipo normal valen S/. 4.50 y las halógenas S/. 6.00. La producción está limitada por el hecho de que no pueden fabricarse al día más de 400 normales y 300 halógenas ni más de 500 en total. Si se vende toda la producción, ¿cuántas de cada clase convendrá producir para obtener la máxima facturación?Solución:
• x: numero de bombillas tipo normal(variable) • y: número de bombillas halógenas(variable)
Maximizar z = 4.50x + 6.00y (Función objetivo)Sujeto a:
• x+ y ≤ 500 (restricción 1)• x ≤ 400 (restricción 2)• y ≤ 300 (restricción 3)
con: x ≥ 0 , y ≥ 0
![Page 23: Objetivos Captar la idea de la programación lineal y sus posibilidades de aplicación a problemas prácticos. Saber plantear un problema de programación.](https://reader035.fdocumento.com/reader035/viewer/2022062500/5665b4571a28abb57c90acec/html5/thumbnails/23.jpg)
• Respuesta: Se deben producir 200 bombillas normales y 300 halógenas