PROBLEMAS DE PROGRAMACIÓN LINEAL RESUELTOS
Programación lineal es un método que sirve para investigar, para así, hallar la solución a un problema dado dentro de un conjunto de soluciones factibles y es la operación que se utiliza para poder obtener la maximación de ganancias o minimizar los costos. Además la programación lineal se utiliza en extensas operaciones industriales y militares.
PREGUNTA 1
Un lago se llena de dos especies de peces S1 y S2. La especie S1 proporciona un peso promedio de 4 kg de carne y la especie S2 un peso promedio de 2kg. Dos tipos de comida F1 y F2 están disponibles en el lago. El requerimiento promedio de la especie S1 es 1 unidad de F1 y 3 unidades de F2, mientras que el requerimiento de S2 son 2 unidades de F1 y 1 unidad de F2 cada día. Si se dispone diariamente de 500 unidades de F1 y 900 unidades de F2, determine el número total de peces en el lago que maximice el peso total de carne de pescado.
A) 360
B) 380
C) 400
D) 420
E) 460
Clave B
Reglas importantes para la programación lineal
1- Cuando se suma o se recta un número en ambos lados de la igualdad esta
2- Si se multiplica o divide los dos lados de la igualdad o desigualdad con
3- Cuando se multiplica o divide los dos lados de la igualdad o desigualdad
mantiene el mismo sentido.
2- Si se multiplica o divide los dos lados de la igualdad o desigualdad con
números positivos, también mantiene el mismo sentido.
3- Cuando se multiplica o divide los dos lados de la igualdad o desigualdad
con número negativo cambia su sentido.
INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL
En numerosos problemas de la vida cotidiana se nos pide optimizar (maximizar o minimizar) una función (llamada función objetivo) sujeta a un sistema de ecuaciones o inecuaciones. Este sistema de ecuaciones o inecuaciones a la que está sujeta la función objetivo refleja las restricciones, impuestas en la(s) solución(es) del problema. Este tipo de problemas se llaman problemas de programación matemática. En particular, los problemas en los que tanto la función objetivo como las restricciones son expresadas en forma de ecuaciones o inecuaciones lineales se llaman problemas de programación lineal.
GUÍA PARA PROGRAMACIÓN LINEAL
1. IDENTIFICAR VARIABLES
determine que variables del problema deben recibir el nombre de «x» e «y».
2. ENCONTRAR LA FUNCIÓN OBJETIVO
escriba una expresión para la función que deseamos maximizar o minimizar.
3. GRAFICAR LA REGIÓN FACTIBLE
la región factible está formada por el conjunto de puntos del plano que verifican el sistema de inecuaciones (restricciones del problema). Dichos puntos forman un recinto convexo acotado (poligonal) o no acotado.
4. ENCONTRAR EL MÁXIMO O MÍNIMO
evalúe la función objetivo en los vértices de la región factible para determinar su valor máximo o mínimo.
SOLUCIONES ÓPTIMAS
son el conjunto de pares ordenados que pertenecen a la región factible y que, al ser evaluados en la función objetivo, generan un máximo o mínimo valor.
TEOREMA 1
Una función lineal definida sobre una región factible acotada no vacía tiene un valor máximo (mínimo) que puede hallarse en un vértice.
TEOREMA 2.
Si la función objetivo asume el mismo valor óptimo en dos vértices consecutivos de una frontera de la región factible entonces también asume el máximo valor en todos los puntos del segmento formado por dichos vértices.
.gif)
.gif)
.gif)
.gif)
ORIGEN DE LA PROGRAMACIÓN LINEAL Y SU INFLUENCIA EN LA HISTORIA
En los siglos XVII y XVIII, grandes matemáticos como Newton , Leibnitz , Bernouilli y , sobre todo , Lagrange , que tanto habían contribuido al desarrollo del cálculo infinitesimal , se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones. Posteriormente el matemático fránces Jean Baptiste–Joseph Fourier (1768 – 1830) fue el primero en intuir , aunque de forma imprecisa , los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva.
Si exceptuamos al matemático Gaspar Monge (1746-1818), quien en 1776 se interesó por problemas de este género, debemos remontarnos al año 1939 para encontrar nuevos estudios relacionados con los métodos de la actual programación lineal . En ese año , el matemático ruso Leonodas Vitalyevich Kantarovitch publica una extensa monografía titulada Métodos matemáticos de organización y planificación de la producción , en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida llamada, hoy en día, programación lineal . En 1941–1942 se formula por primera vez el problema de transporte, estudiado independientemente por Koopmans y Kantarovitch , razón por la cual se suele conocer con el nombre de problema de Koopmans-Kantarovitch.
Tres años más tarde, G.Stigler plantea otro problema particular conocido con el nombre de régimen alimenticio optimal. En estos años posteriores a la Segunda Guerra Mundial , en Estados Unidos se asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad , que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal . Paralelamente a los hechos descritos se desarrollan las técnicas de computación y los ordenadores , instrumentos que harían posible la resolución y simplificación de los problemas que se estaban gestando. En 1947, G.B. Dantzig formula , en términos matemáticos muy precisos , el enunciado estándar al que cabe reducir todo problema de programación lineal. Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formarían el grupo que dio en denominarse SCOOP (Scientific Computation of Optimum Programs).
Una de las primeras aplicaciones de los estudios del grupo SCOOP fue el puente aéreo de Berlín. Se continuó con infinidad de aplicaciones de tipo preferentemente militar. Hacia 1950 se constituyen, fundamentalmente en Estados Unidos, distintos grupos de estudio para ir desarrollando las diferentes ramificaciones de la programación lineal. Cabe citar, entre otros, Rand Corporation, con Dantzig ,Orchard-Hays, Ford, Fulkerson y Gale, el departamento de Matemáticas de la Universidad de Princenton, con Tucker y Kuhn, así como la Escuela Graduada de Administración Industrial, dependiente del Carnegie Institute of Technology , con Charnes y Cooper. Respecto al método del simplex , que estudiaremos después , señalaremos que su estudio comenzó en el año 1951 y fue desarrollado por Dantzig en el United States Bureau of Standards SEAC COMPUTER, ayudándose de varios modelos de ordenador de la firma IBM.
Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro Janos von Neuman (1903–1957), quien en 1928 publicó su famoso trabajo Teoría de Juegos. En 1947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos.
La influencia de este respetado matemático, discípulo de David Hilbert en Gotinga y , desde 1930, catedrático de la Universidad de Princenton de Estados Unidos, hace que otros investigadores se interesaran paulatinamente por el desarrollo riguroso de esta disciplina . En 1858 se aplicaron los métodos de la programación lineal a un problema concreto: el cálculo del plan óptimo de transporte de arena de construcción a las obras de edificación de la ciudad de Moscú .
En este problema había 10 puntos de partida y 230 de llegada. El plan óptimo de transporte ,calculado con el ordenador Strena en 10 días del mes de junio, rebajó un 11% los gastos respecto a los costes previstos. Se ha estimado , de una manera general , que si un país subdesarrollado utilizase los métodos de la programación lineal , su producto interior bruto (PIB) aumentaría entre un 10 y un 15% en tan sólo un año.
LA PROGRAMACIÓN LINEAL HACE HISTORIA EL PUENTE AÉREO DE BERLÍN :
En 1946 comienza el largo período de la guerra fría entre la antigua Unión Soviética (URSS) y las potencias aliadas (principalmente , Inglaterra y Estados Unidos). Uno de los episodios más llamativos de esa guerra fría se produjo a mediados de 1948, cuando la URSS bloqueó las comunicaciones terrestres desde las zonas alemanas en poder de los aliados con la ciudad de Berlín, iniciando el bloqueo de Berlín. A los aliados se les plantearon dos posiblidades : o romper el bloqueo terrestre por la fuerza , o llegar a Berlín por el aire. Se adoptó la decisión de programar una demostración técnica del poder aéreo norteamericano ; a tal efecto, se organizó un gigantesco puente aéreo para abastecer la ciudad: en diciembre de 1948 se estaban transportando 4500 toneladas diarias ; en marzo de 1949, se llegó a las 8000 toneladas, tanto como se transportaba por carretera y ferrocarril antes del corte de las comunicaciones. En la planificación de los suministros se utilizó la programación lineal. (El 12 de mayo de 1949, los soviéticos levantaron el bloqueo) En infinidad de aplicaciones de la industria, la economía, la estrategia militar, etc. se presentan situaciones en las que se exige maximizar o minimizar algunas funciones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones. Para hacernos una idea más clara de estos supuestos, veamos dos ejemplos :
EJEMPLO 1:
PROBLEMA DE MÁXIMOS
En una granja se preparan dos clases de combinity , P y Q, mezclando dos productos A y B. Un saco de P contiene 8 kg de A y 2 de B, y un saco de Q contiene 10 kg de A y 5 de B. Cada saco de P se vende a s/. 300. y cada saco de Q a s/.800 . Si en la granja hay almacenados 80 kg de A y 25 de B, ¿cuántos sacos de cada tipo de combinity deben preparar para obtener los máximos ingresos?
EJEMPLO 2 :
PROBLEMA DE MÍNIMOS
Una campaña para promocionar una marca de productos lácteos se basa en el reparto gratuito de yogures con sabor a limón o a fresa. Se decide repartir al menos 30000 yogures. Cada yogur de limón necesita para su elaboración 0,5 gramos de un producto de fermentación y cada yogur de fresa necesita 0,2 gramos de este mismo producto. Se dispone de 9 kilogramos de este producto para fermentación. El costo de producción de un yogur de limón es de 30 soles y 20 soles uno de fresa.
En los dos ejemplos descritos está claro que tanto la cantidad que deseamos maximizar como la cantidad que deseamos minimizar podemos expresarlas en forma de ecuaciones lineales. Por otra parte , las restricciones que imponen las condiciones de ambos problemas se pueden expresar en forma de inecuaciones lineales.
Trataremos de plantear en términos matemáticos los dos ejemplos enteriores :
USOS DE LA PROGRAMACIÓN LINEAL EN EL PERÚ
Desde los primeros años de la década del 60 diversas empresas y entidades han aplicado la programación lineal para la toma de decisiones en problemas específicos . Dentro de las aplicaciones conocidas en nuestro medio , mencionaremos las siguientes: Petroperu
* Modelo matemático de transporte de crudos y refinados para la asignación óptima de la flota nacional.
* Modelo de refinerías para la obtención de gasolinas del octanaje adecuado al mínimo costo.
* Modelo matemático para la planta de lubricantes del callao Nicolini Hnos. s.a.
* Modelo de mezcla insumos para la fabricación de alimentos balanceados para aves. Unileche s.a.
* Modelo de transportes para las asignaciones de rutas y vehículos de reparto de leche en Lima Metropolitana. Sider Perú
* Modelo de mezcla de insumos para la alimentación del alto horno. Ministerio de transportes
* Modelo de evaluación de proyectos de construcción vial considerando los efectos regionales de centros de producción y consumo. Instituto nacional de planificación
* Modelo de selección de cartera de proyectos de desarrollo económico. Ministerio de agricultura Iowa State University
* Modelo de rotación de cultivos para los valles de la costa norte del Perú. A continuación presentaremos un ejemplo práctico de la programación lineal.
