programacion lineal
TRANSCRIPT
José Gonzales VillanuevaProfesor de Matemática
LICEO NAVAL CAPITÁN DE CORBETA MANUEL CLAVERO MUGA
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...
• Resolver un problema de programación lineal usando el software POM.
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
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.
¿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.
Ejemplo 1Huguito es un estudiante que dedica parte de su tiempo al reparto de propaganda publicitaria. La empresa A le paga S/. 5 por cada impreso repartido y la empresa B, con folletos más grandes, le paga S/. 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?
DEFINICIONES
VariablesCantidades desconocid
as
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 objetivo
Restricciones 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
Fundamentación Matemática
Teorema 1
• El conjunto de todas las soluciones factibles a un problema de Programación Lineal es un conjunto convexo.
Teorema 2
• La función objetivo alcanza su máximo en un punto extremo del conjunto convexo, generado por el conjunto de soluciones factibles.
Planteamiento del Ejemplo 1Paso 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
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
Representación gráfica de la Región Factible
Evaluando los vértices• Los vértices de la región factible (0;0); (0;100); (50;100);
(120;30) y (120;0)• De acuerdo con el Teorema 2 debe encontrarse una solución
entre estos pares.
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.
ALGORITMO DE RESOLUCIÓNIdentificar 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.
Uso del Software EducativoPOM para Windows
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
• Respuesta: La función Z es máxima para el vértice (3,2), que es 19
Problema 3
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
• Respuesta: El mínimo se alcanza en (0,5) y es - 15
Problema 5
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
• Respuesta: Se deben producir 200 bombillas normales y 300 halógenas
