programación lineal-12(1)

Vista previa del material en texto

REPÚBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA EDUCACIÓN UNIVERSITARIA 
UNIVERSIDAD EXPERIMENTAL DE LA GRAN CARACAS (UNEXCA)
CARRERA: PNFI INFORMATICA - PROSECUCIÓN
ASIGNATURA: INVESTIGACION DE OPERACIONES SECCIÓN - AI30232-C2
INVESTIGACION DE OPERACIONES 
UNIDAD II
Profesor:					 Integrantes:
Edison Viloria				Banezca. Rosmery. C.I. V- 27.693.184
 Castillo V, Jean F. C.I. V- 26.483.721
 Gutiérrez D, Carla A. C.I. V-12.303.017
						Sinza B, Pedro M. C.I. V-13.691.869
 Montesinos, Juan M. C.I. V- 6.269.648 López. Daniel. C.I. V- 26.272.608
Caracas, Junio 2023.
INTRODUCCIÓN
	La programación lineal es una técnica matemática utilizada para optimizar una función objetivo, sujeta a un conjunto de restricciones lineales. Esta técnica se utiliza comúnmente en la toma de decisiones empresariales y de ingeniería para maximizar ganancias, minimizar costos o asignar recursos de manera óptima.
	En la programación lineal, se modela el problema como un sistema de ecuaciones lineales y se utiliza un algoritmo de optimización para encontrar la solución óptima. La solución óptima se encuentra en un punto extremo del conjunto de soluciones factibles, que se define por las restricciones lineales.
	La programación lineal es una técnica matemática utilizada para optimizar una función objetivo, sujeta a un conjunto de restricciones lineales. Esta técnica se utiliza comúnmente en la toma de decisiones empresariales y de ingeniería para maximizar ganancias, minimizar costos o asignar recursos de manera óptima.
	
UNIDAD II.
PROGRAMACIÓN LINEAL.
	La programación lineal es una técnica matemática que se utiliza en la investigación de operaciones para resolver problemas de optimización. Consiste en maximizar o minimizar una función lineal sujeta a restricciones lineales, donde las variables pueden ser continuas o discretas. Se utiliza comúnmente en la producción, logística, finanzas, recursos humanos y otras áreas donde es necesario optimizar los recursos limitados. La programación lineal se puede resolver gráficamente o mediante algoritmos de optimización numérica, como el método simplex. Es importante destacar que la programación lineal es solo una técnica dentro de la investigación de operaciones y se utiliza en combinación con otras técnicas como la simulación y el análisis de redes para resolver problemas más complejos.
DEFINICIÓN.
	La programación lineal es una técnica matemática que permite la optimización de una función objetivo a través de la aplicación de diversas restricciones lineales. Se trata de una técnica utilizada en la investigación de operaciones para resolver problemas de optimización, maximizando o minimizando una función objetivo lineal. Las variables pueden ser continuas o discretas y se pueden resolver utilizando métodos gráficos o algoritmos numéricos de optimización, como el método simplex. En resumen, la programación lineal es una herramienta matemática fundamental en la toma de decisiones, ya que ayuda a maximizar o minimizar una función objetivo sujeta a limitaciones en los recursos disponibles.
MODELOS DE PROGRAMACIÓN LINEAL.
	La programación lineal consiste en crear un modelo matemático que busca maximizar o minimizar una función lineal sujeta a un conjunto de restricciones lineales. Existen diferentes tipos de modelos de programación lineal, como el modelo de transporte, el modelo de asignación, el modelo de mezcla de productos, entre otros. Los modelos de programación lineal se pueden resolver usando diferentes técnicas, como el método simplex y el método de las regiones factibles. Estos modelos se aplican en una amplia variedad de áreas, como la producción, la logística, las finanzas y los recursos humanos. La programación lineal es una técnica muy utilizada en la investigación de operaciones para resolver problemas de optimización.
SOLUCIÓN GRÁFICA DE PROBLEMAS DE DOS DIMENSIONES.
Para resolver problemas de programación lineal en dos dimensiones mediante la técnica gráfica, se pueden seguir los siguientes pasos:
1. Identificar la función objetivo: La función objetivo es la ecuación lineal que se desea maximizar o minimizar y se puede representar como una línea recta.
2. Establecer las restricciones: Las restricciones son las ecuaciones lineales que limitan la solución factible del problema. Cada restricción se puede representar como una línea recta.
3. Graficar las restricciones: Las restricciones deben graficarse en un plano cartesiano, donde cada eje representa una variable de decisión. La solución factible es el área común de todas las restricciones.
4. Encontrar la solución óptima: La solución óptima se encuentra en uno de los vértices de la solución factible. Para encontrarla, se pueden analizar los puntos de intersección de las líneas de las restricciones y la función objetivo.
	Este método es útil para problemas de programación lineal en dos dimensiones con pocas variables de decisión. 
	Para problemas con más variables, es necesario utilizar técnicas numéricas como el método simplex.
Ejercicios Resueltos del Método Gráfico en Programación Lineal
Ejercicio 1 – Maximización – Really Big Shoe:
	The Really Big Shoe es un fabricante de calzado deportivo para básquetbol y fútbol. El gerente de marketing, Ed Sullivan, tiene que decidir la mejor forma de gastar los recursos destinados a publicidad. Cada uno de los equipos de fútbol patrocinados requiere 120 pares de zapatos. Cada equipo de básquetbol requiere 32 pares de zapatos. Los entrenadores de fútbol reciben $300,000 por concepto de patrocinio para calzado, y los entrenadores de básquetbol reciben $1,000,000. El presupuesto de Sullivan para promociones asciende a $30,000,000.
	The Really Big Shoe dispone de una provisión limitada (4 litros, o sea, 4,000 centímetros cúbicos) de flubber, un compuesto raro y costoso que se utiliza en la fabricación del calzado atlético de promoción. Cada par de zapatos para básquetbol requiere 3 cc de flubber y cada par de zapatos de fútbol requiere 1 cc. Sullivan desea patrocinar el mayor número de equipos de básquetbol y fútbol que sus recursos le permitan.
a. Formule un conjunto de ecuaciones lineales para describir la función objetivo y las restricciones. 
b. Utilice el análisis gráfico para encontrar la solución visual. 
c. ¿Cuál es el número máximo de cada tipo de equipo que The Really Big Shoe podrá patrocinar? 
Solución 1:
a) El planteamiento del problema de programación lineal sería:
Variables:
· x = Número de equipos de futbol a patrocinar 
· y = Número de equipos de básquetbol a patrocinar 
Función Objetivo:
Z = Maximizar (x + y)
Restricciones:
· Presupuesto: 300,000x + 1,000,000y ≤ 30,000,000 
· Flubber: 120x + 96y ≤ 4000 
· No negatividad: x, y ≥ 0 
Datos del Problema
Se requiere Maximizar el siguiente problema:
Función Objetivo
Z = X1 + X2
Sujeto a las siguientes restricciones
300000X1 + 1000000X2 ≤ 30000000 
120X1 + 96X2 ≤ 4000 
X1, X2 ≥ 0
Solución
	Para resolver el problema vamos a calcular la región factible que está formada por el área que satisface el conjunto de restricciones.
	A continuación presentamos los cálculos y gráficos detallados para resolver el problema:
Paso 1:
No Negatividad: X1, X2 ≥ 0
	Las variables de decisión del problema deben de cumplir la restricción de no negatividad; es decir, sus valores pueden ser de 0 a más.
En nuestro gráfico, significa que la región factible se encontrará en el primer cuadrante:
Gráfico 1.
Paso 2:
Restricción N° 1: 300000X1 + 1000000X2 ≤ 30000000 
Para graficar esta restricción, convertiremos la inecuación en una igualdad cambiando el "≤" por "=" para graficar la línea recta:
300000X1 + 1000000X2 = 30000000
	Calculamos los puntos de intersección de la recta con los ejes X1 y X2, para ello evaluamos la ecuación dándole el valor de 0 a cadauna de las variables:
· Sea X1 = 0 => 1000000X2 = 30000000 => X2 = 30000000/1000000 => X2 = 30
· Sea X2 = 0, entonces 300000X1 = 30000000 => X1 = 30000000/300000 => X1 = 100
	De los resultados obtenidos se obtienen los siguientes puntos: A = (0,30) y B = (100,0). La recta cruzará por ambos puntos en el gráfico.
Ahora que calculamos la recta de la gráfica, volvemos a la restricción inicial:
300000X1 + 1000000X2 ≤ 30000000 
	Para determinar si debemos sombrear la parte superior e inferior de la recta podemos seguir la siguiente regla:
	Dado que el inecuación es ≤ (menor igual que) y el signo del coeficiente X2 es positivo el área a sombrear corresponde a la parte inferior de la recta.
Nota: Otra forma de verificar que lado de la recta debes sombrear es eligiendo un punto al azar, ya sea de la parte superior o inferior de la recta. Si al reemplazar las coordenadas en la inecuación, se cumple la desigualdad; entonces el lado donde se encuentra el punto elegido es la que debes sombrear. En caso no se cumpla la desigualdad, el área a sombrear es la del otro lado.
	La parte de la gráfica que se encuentra completamente sombreada (sin transparencia) representa a la región factible de las restricciones evaluadas hasta el momento.
Gráfico 2.
Restricción N° 2: 120X1 + 96X2 ≤ 4000 
	Para graficar esta restricción, convertiremos la inecuación en una igualdad cambiando el "≤" por "=" para graficar la línea recta:
120X1 + 96X2 = 4000 
	
	Calculamos los puntos de intersección de la recta con los ejes X1 y X2, para ello evaluamos la ecuación dándole el valor de 0 a cada una de las variables:
· Sea X1 = 0 => 96X2 = 4000 => X2 = 4000/96 => X2 = 41.667
· Sea X2 = 0, entonces 120X1 = 4000 => X1 = 4000/120 => X1 = 33.333
De los resultados obtenidos se obtienen los siguientes puntos: A = (0,41.667) y B = (33.333,0). La recta cruzará por ambos puntos en el gráfico.
Ahora que calculamos la recta de la gráfica, volvemos a la restricción inicial:
120X1 + 96X2 ≤ 4000 
	Para determinar si debemos sombrear la parte superior e inferior de la recta podemos seguir la siguiente regla:
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	Dado que el inecuación es ≤ (menor igual que) y el signo del coeficiente X2 es positivo el área a sombrear corresponde a la parte inferior de la recta.
Nota: Otra forma de verificar que lado de la recta debes sombrear es eligiendo un punto al azar, ya sea de la parte superior o inferior de la recta. Si al reemplazar las coordenadas en la inecuación, se cumple la desigualdad; entonces el lado donde se encuentra el punto elegido es la que debes sombrear. En caso no se cumpla la desigualdad, el área a sombrear es la del otro lado.
	La parte de la gráfica que se encuentra completamente sombreada (sin transparencia) representa a la región factible de todas las restricciones del problema.
Gráfico 3.
Paso 4:
	Los vértices de la región factible son los posibles valores óptimos de la función objetivos, en ese sentido evaluaremos cada punto para Maximizar su valor:
	
	
	
	
	El máximo valor de la función objetivo se encuentra en el punto D=(700/57,500/19) con un resultado de 2200/57: 
Solución:
Valor Óptimo (Z)
2200/57
X₁
700/57
X₂
500/19
Gráfico 4
MÉTODOS SIMPLEX DE RESOLUCIÓN Y SIMPLEX DUAL.
	Los métodos simplex de resolución y simplex dual son técnicas utilizadas para resolver problemas de programación lineal. El método simplex se utiliza cuando la función objetivo y las restricciones son expresadas en forma de desigualdades, mientras que el método simplex dual se utiliza cuando las desigualdades se expresan en términos de restricciones de igualdad.
	
	En el método simplex, se utiliza una tabla (tabla simplex) para representar la matriz de coeficientes de las restricciones y la función objetivo. El objetivo es encontrar una solución factible óptima de la tabla, que se alcanza cuando se maximiza o minimiza la función objetivo.
	En el método simplex dual, se utiliza una tabla similar a la del método simplex, pero se involucran variables duales y se cambia el enfoque del problema. La solución al problema dual proporciona información valiosa sobre la sensibilidad de la solución óptima y permite una interpretación económica de la solución.
	Ambos métodos son iterativos y se basan en el pivoteo de la tabla para encontrar soluciones factibles mejoradas. La elección del pivote es esencial para garantizar la convergencia del método a la solución óptima.
	En resumen, los métodos simplex y simplex dual son técnicas importantes para resolver problemas de programación lineal, y se utilizan comúnmente en áreas como la producción, la logística, las finanzas y los recursos humanos, entre otros campos.
MÉTODOS SIMPLEX DE RESOLUCIÓN:
	El método simplex es una técnica utilizada para resolver problemas de programación lineal. Este método consiste en una serie de iteraciones que permiten encontrar la solución óptima del problema. El objetivo es maximizar (o minimizar) una función objetivo sujeta a ciertas restricciones lineales.
	El algoritmo simplex comienza con una solución básica factible, que se obtiene identificando las variables básicas y no básicas del problema. La solución factible inicial se evalúa mediante la función objetivo y se comparan las mejoras posibles. En cada iteración, el algoritmo mueve una variable no básica a la solución básica, y se ajustan las demás variables hasta obtener una nueva solución factible. El proceso se repite hasta que se alcanza la solución óptima.
	En cada iteración, el algoritmo simplex busca la mejor variable no básica que se puede introducir en la solución básica actual, y se verifica si esta adición mejora o empeora la solución. Para hacer esto, se utiliza el valor de la función objetivo en los vértices de la región de solución factible (es decir, los puntos de intersección de las restricciones), lo que permite identificar aquellos que maximizan (o minimizan) la función objetivo.
	El método simplex puede resolverse manualmente o mediante el uso de software especializado. Es una herramienta poderosa para la toma de decisiones empresariales y se utiliza comúnmente en áreas como la producción, la logística, las finanzas y los recursos humanos, entre otros campos.
SIMPLEX DUAL: 
	El método simplex dual es una variante del método simplex utilizado en la resolución de problemas de programación lineal. Al igual que el método simplex, el método dual simplex también se basa en una solución básica factible, pero se enfoca en cambiar las restricciones del problema en lugar de las variables de decisión.
	En el método dual simplex, el objetivo es minimizar (o maximizar) la cantidad de recursos utilizados en el problema. Se inicia con una solución básica factible inicial y se buscan variables que puedan mejorar la solución al mismo tiempo que se mantienen las restricciones, lo que se conoce como "condiciones de holgura".
	El método simplex dual funciona moviendo las variables restringidas a la lista de variables básicas y resolviendo el problema para verificar si se ha encontrado una solución óptima. Si no es así, se agregan restricciones adicionales y se ajustan las variables para garantizar que se cumplan las condiciones de holgura.
	El método simplex dual se ajusta particularmente para problemas de programación lineal con restricciones complejas y múltiples objetivos, y es una herramienta importante para profesionales de la investigación de operaciones, economistas y analistas de datos. Su eficacia se debe a la capacidad de encontrar rápidamente soluciones óptimas o casi óptimas, lo que permite a los tomadores de decisiones tomar decisiones informadas en un tiempo razonable.
EJERCICIOS MÉTODO SIMPLEX
EJERCICIO 1: 
	Hoy es su día de suerte. Acaba de ganar un premio de $10.000. Dedicará $4.000 a impuestos y diversiones, pero ha decidido invertir los otros $6.000. Al oír las nuevas, dos amigos le han ofrecido una oportunidad de convertirse en socio en dos empresas distintas, cada una planeada por uno de ellos. En ambos casos, la inversiónincluye dedicar parte de su tiempo el siguiente verano y dinero en efectivo. Para ser un socio completo en el caso del primer amigo debe invertir $5.000 y 400 horas, y su ganancia estimada (sin tomar en cuenta el valor del dinero en el tiempo) sería $4.500. Las cifras correspondientes para el segundo caso son $4.000 y 500 horas, con una ganancia estimada de $4.500. Sin embargo, ambos amigos son flexibles y le permitirán participar con cualquier fracción de participación que quiera. Si elige una participación parcial, todas las cifras dadas para la sociedad completa (inversión de dinero y tiempo, y la ganancia) se pueden multiplicar por esta fracción. Como de todas formas usted busca un trabajo de verano interesante (máximo 600 horas), ha decidido participar en una o ambas empresas en alguna combinación que maximice su ganancia total estimada. Usted debe resolver el problema de encontrar la mejor combinación.
RESOLUCIÓN: 
F0= 4500X1 + 4500X2			F0= 4500X1 + 4500X2 + 0S1 + 0S3 + 0S4
 Sujeto A:					 Sujeto A:
*
MATRIZ:
ANÁLISIS DE SENSIBILIDAD: 
	El análisis de sensibilidad es una técnica utilizada en la investigación de operaciones y en la toma de decisiones que permite evaluar cómo se ve afectada una solución óptima al cambiar los parámetros del problema, como el costo de los insumos, la demanda o los recursos disponibles. El objetivo del análisis de sensibilidad es evaluar la robustez de la solución y determinar cómo afectan las diferentes variables a la solución óptima. Esta técnica se utiliza comúnmente en problemas de programación lineal, donde las soluciones óptimas se ven afectadas por cambios en los coeficientes de las variables de decisión o en las restricciones del problema. El análisis de sensibilidad puede realizarse gráficamente o mediante el cálculo de los valores umbrales de las variables del modelo que provocan cambios en la solución óptima. En general, el análisis de sensibilidad es una herramienta útil para evaluar la incertidumbre asociada a los parámetros de un problema y para tomar decisiones más informadas en cuanto a la asignación de recursos y la planificación empresarial.
EJEMPLO DE ANÁLISIS DE SENSIBILIDAD: 
	La empresa KAMIR se dedica a la fabricación de tres productos; A, B y C. El procedimiento de producción involucra tres operaciones: formación, acabado e inspección. El departamento de ingeniería industrial ha establecido los siguientes estándares de producción en cada operación. 
Datos de producción para la compañía (minutos por producto).
 	Se desea saber el número de cada tipo de producto que deberán producirse de tal manera que se optimice el beneficio por las 8 horas de trabajo del día. Considerando la información, se planteó el modelo de programación lineal: 
X1: número de productos tipo A. 
X2: número de productos tipo B. 
X3: número de productos tipo C. 
Maximizar Z= 20 𝑋1 + 35 𝑋2 + 45 𝑋3 
SUJETO A: 		2 𝑋1 + 6 𝑋2 + 2 𝑋3≤ 480 		FORMACIÓN 
			3 𝑋1+ 2 𝑋2 + 2 𝑋 3≤ 480 		INSPECCIÓN 
			2 𝑋1 + 2 𝑋2 + 4 𝑋3 ≤ 480 	 ACABADO 
			𝑋1, 𝑋2, 𝑋3 ≥ 0 
	
CONCLUSIÓN
	La programación lineal es una técnica matemática poderosa que se utiliza para resolver problemas de optimización en una amplia variedad de campos, desde la planificación de la producción hasta la asignación de recursos. La programación lineal se basa en la formulación de un modelo matemático que representa el problema a resolver, utilizando ecuaciones lineales y restricciones.
	La solución óptima se encuentra en un punto extremo del conjunto de soluciones factibles, que se define por las restricciones lineales. La programación lineal se utiliza para maximizar ganancias, minimizar costos o asignar recursos de manera óptima.
	En la práctica, la programación lineal se utiliza en una amplia variedad de situaciones y ha demostrado ser una herramienta valiosa para la toma de decisiones empresariales y de ingeniería.
	La programación lineal es importante porque permite resolver problemas de optimización en una amplia variedad de campos, como la planificación de la producción, la asignación de recursos, la optimización de rutas, el diseño de redes, entre otros. La programación lineal es una técnica matemática poderosa que permite tomar decisiones informadas y basadas en datos, lo que puede llevar a una mayor eficiencia y rentabilidad en los negocios.
	Además, la programación lineal es una técnica muy versátil que puede adaptarse a diferentes situaciones y necesidades. También puede ser utilizada en combinación con otras técnicas de optimización para resolver problemas más complejos.
	La programación lineal es importante porque permite tomar decisiones informadas y basadas en datos para optimizar procesos empresariales y de ingeniería, lo que puede llevar a una mayor eficiencia y rentabilidad en los negocios. Además, es una técnica matemática versátil y adaptable a diferentes situaciones y necesidades.
REFERENCIAS BIBLIOGRÁFICAS
1. https://www.ingenieriaindustrialonline.com/investigacion-de-operaciones/programacion-lineal/
2. https://www.superprof.es/apuntes/escolar/matematicas/algebralineal/pl/ejercicios-y-problemas-resueltos-de-programacion-lineal.html
3. https://www.guao.org/sites/default/files/M%C3%A9todo%20gr%C3%A1fico%20de%20resoluci%C3%B3n%20de%20ecuaciones%20lineales.pdf
4. https://www.youtube.com/watch?v=7Bo4B278HJE