Más información
Programación lineal
Conceptos de programación lineal
La técnica matemática conocida por programación lineal se utiliza para obtener una solución óptima a un problema condicionado por unas variables de partida sujetas a ciertas restricciones. Un problema clásico de la programación sería el siguiente: teniendo n productos del tipo A y m del tipo B, que pueden envasarse en dos clases de paquetes en diferentes proporciones y con un precio distinto para cada paquete, cuántos paquetes de cada tipo deberán formarse para obtener una cantidad máxima de ingresos.
En el planteamiento del problema se manejan varios conceptos esenciales:
- Las variables.
- Las restricciones que se imponen, expresadas por inecuaciones lineales.
- La función objetivo, de tipo lineal, que describe el problema.
El grupo de las soluciones posibles recibe el nombre de conjunto restricción o conjunto solución factible. La solución debe situarse en el área definida por las inecuaciones de restricción, que se conoce por región factible.
Región factible del sistema de inecuaciones lineales:
La región factible puede estar acotada, como en la figura, o no acotada. Cuando está acotada, se representa gráficamente como un polígono con un número de lados menor o igual que el de restricciones (en la figura, el polígono acotado tiene cuatro lados, y las restricciones también son cuatro).
Se llama solución óptima a la que maximiza o minimiza la función objetivo. Esta solución si es única siempre se encuentra en un vértice o punto extremo de la región factible.
Resolución por método gráfico
Para resolver gráficamente un problema de programación lineal, se hace lo siguiente:
- Se representan gráficamente las inecuaciones del sistema, obteniéndose el conjunto restricción.
- Si la función objetivo es f (x,y)= ax + by, se trazan rectas paralelas a esta función (que serán de la forma ax + by=k) y que pasen por cada uno de los vértices del conjunto restricción.
- Se observa en qué vértice la función objetivo se hace máxima (o mínima) sin más que tener en cuenta cuál de las rectas tiene mayor (o menor) ordenada en el origen.
Esta técnica se conoce por método de las rectas de nivel.
Método algebraico de resolución
Para resolver un problema de programación lineal por métodos algebraicos, se aplica el siguiente procedimiento operativo:
- 1. Se definen las variables.
- 2. Para cada restricción existente se escribe una inecuación lineal representativa.
- 3. Se define la expresión matemática de la función objetivo.
- 4. Se construyen sistemas cuadrados de ecuaciones a partir del conjunto inicial de inecuaciones lineales. Por ejemplo, si se tuvieran cuatro inecuaciones con dos incógnitas, se podrían construir seis sistemas distintos de ecuaciones lineales (sustituyendo la desigualdad por igualdad).
- 5. Se resuelven todos estos sistemas y se anota el valor de los puntos obtenidos como solución.
- 6. Se comprueban estos puntos en cada una de las inecuaciones. Los que cumplan todas las restricciones serán los vértices de la región factible.
- 7. Se calcula el valor de la función objetivo para cada vértice.
- 8. La solución óptima será aquella para la cual la función objetivo es máxima (o mínima, según el planteamiento del problema).
Esta técnica recibe el nombre de método de los vértices.
Tipos de soluciones
En los problemas de programación lineal con dos variables pueden darse varios tipos de soluciones óptimas:
- Solución única.
- Solución múltiple (infinitas soluciones).
- Solución no acotada (ausencia de solución), cuando la función objetivo no tiene valores extremos, pues la región factible es no acotada.
- Solución no factible, cuando no existe región factible por falta de puntos comunes en el sistema de inecuaciones.
- Solución degenerada, si en un solo punto (que se dice degenerado) coinciden tres o más de las rectas que limitan la región factible.
Enviar la página por correo a
¿Qué son los iconos de "Compartir"?
Todos los iconos apuntan a servicios web externos y ajenos a HIRU.com que facilitan la gestión personal o comunitaria de la información. Estos servicios permiten al usuario, por ejemplo, clasificar , compartir, valorar, comentar o conservar los contenidos que encuentra en Internet.
¿Para qué sirve cada uno?
-
Comparte con amigos y otros usuarios fotos, vídeos, noticias y comentarios personales, controlando la privacidad de los mismos.
-
Conversa sobre los temas que te interesan y que proponen los expertos. Todo ello en 280 caracteres con fotos y vídeos. Lee, pregunta e infórmate.
-
Contacta y comparte con amigos, familiares y compañeros de trabajo mensajes cortos (tweets) de no más de 140 caracteres.
-
Conéctate, comparte y comunícate con tus amigos, compañeros de trabajo y familia.
-
Comparte tus novedades, fotos y vídeos con tus amigos e inicia conversaciones sobre los temas que te interesan.
-
Sitio web que se sirve de la inteligencia colectiva para dar a conocer noticias. Los usuarios registrados envían historias que los demás usuarios del sitio pueden votar.
Derechos de reproducción de la obra
-
Los derechos de propiedad intelectual de la web hiru.eus y de los distintos elementos en ella contenidos son titularidad del Departamento de Educación, Universidades e Investigación del Gobierno Vasco.
No obstante, se permite el uso de los contenidos de hiru.eus en el ámbito educativo, siempre que se haga referencia y bajo las condiciones de licencia Creative Commons CC-BY-NC-SA.
Para más información: descarga el PDF (969,4k) .El Departamento de Educación, Universidades e Investigación del Gobierno Vasco se reserva la facultad de efectuar, en cualquier momento y sin necesidad de previo aviso, modificaciones y actualizaciones sobre la información contenida en su web o en su configuración o presentación.
El Departamento de Educación, Universidades e Investigación del Gobierno Vasco no garantiza la inexistencia de errores en el acceso a la web, en su contenido, ni que éste se encuentre oportunamente actualizado, aunque desarrollará los esfuerzos precisos para evitarlos y, en su caso, subsanarlos o actualizarlos a la mayor brevedad posible.
Tanto el acceso a la web, como el uso que pueda hacerse de la información contenida en el mismo son de la exclusiva responsabilidad de quien lo realiza. El Departamento de Educación, Universidades e Investigación del Gobierno Vasco no responderá de ninguna consecuencia, daño o perjuicio que pudieran derivarse de dicho acceso o uso de información, con excepción de todas aquellas actuaciones que resulten de la aplicación de las disposiciones legales a las que deba someterse en el estricto ejercicio de sus competencias.
El Departamento de Educación, Universidades e Investigación del Gobierno Vasco no asume responsabilidad alguna derivada de la conexión o contenidos de los enlaces de terceros a los que se hace referencia en la web.
La utilización no autorizada de la información contenida en esta web, el uso indebido de la misma, así como los perjuicios y quebrantos ocasionados en los derechos de propiedad intelectual e industrial del Departamento de Educación, Universidades e Investigación del Gobierno Vasco dará lugar al ejercicio de las acciones que legalmente le correspondan a dicha Administración y, en su caso, a las responsabilidades que de dicho ejercicio se deriven.
Privacidad
Los datos aportados por la persona interesada se utilizarán, con carácter único y exclusivo, para los fines previstos en el procedimiento o actuación que se trate.
El órgano responsable del fichero donde se recogen dichos datos es la Dirección de Aprendizaje Permanente del Departamento de Educación, Universidades e Investigación del Gobierno Vasco, ante quién podrán ejercerse los derechos de acceso, rectificación, cancelación y oposición. Para tal fin contacta con info@hiru.eus.