Region factible programacion lineal

Programación lineal entera

Los problemas de aplicación en la empresa, la economía y las ciencias sociales y de la vida nos piden a menudo que tomemos decisiones en función de determinadas condiciones. Las condiciones o restricciones suelen adoptar la forma de desigualdades. En esta sección, empezaremos a formular, analizar y resolver dichos problemas, a un nivel sencillo, para comprender los muchos componentes de un problema de este tipo.

Un problema típico de programación lineal consiste en encontrar un valor extremo de una función lineal sujeta a ciertas restricciones. Tratamos de maximizar o minimizar el valor de esta función lineal, como maximizar el beneficio o los ingresos, o minimizar el coste. Por eso estos problemas de programación lineal se clasifican como problemas de maximización o minimización, o simplemente problemas de optimización. La función que intentamos optimizar se llama función objetivo, y las condiciones que deben cumplirse se llaman restricciones.

Cuando graficamos todas las restricciones, el área del gráfico que satisface todas las restricciones se denomina región factible. El Teorema Fundamental de la Programación Lineal establece que el valor máximo (o mínimo) de la función objetivo siempre tiene lugar en los vértices de la región factible. A estos vértices los llamamos puntos críticos. Éstos se encuentran utilizando cualquiera de los métodos del capítulo 3, ya que buscamos los puntos en los que se cruzan dos cualquiera de las líneas límite.

Región delimitada en programación lineal

Este artículo necesita citas adicionales para su verificación. Por favor, ayuda a mejorar este artículo añadiendo citas de fuentes fiables. El material sin fuentes puede ser cuestionado y eliminado.Find sources: "Feasible region" - news - newspapers - books - scholar - JSTOR (November 2018) (Aprende cómo y cuándo eliminar este mensaje de plantilla).

Un problema con cinco restricciones lineales (en azul, incluyendo las restricciones de no negatividad). En ausencia de restricciones enteras el conjunto factible es toda la región delimitada en azul, pero con restricciones enteras es el conjunto de puntos rojos.

En optimización matemática, una región factible, un conjunto factible, un espacio de búsqueda o un espacio de soluciones es el conjunto de todos los puntos posibles (conjuntos de valores de las variables de elección) de un problema de optimización que satisfacen las restricciones del problema, incluyendo potencialmente desigualdades, igualdades y restricciones enteras[1]. Este es el conjunto inicial de soluciones candidatas al problema, antes de que el conjunto de candidatos se haya reducido.

Optimización lineal y no lineal

Los gráficos de desigualdades (las "restricciones") se utilizan para crear una "región de viabilidad" (un área con forma de polígono en el gráfico). Las regiones de viabilidad son todos los lugares que representan soluciones "factibles" (posibles, correctas, viables) del sistema de desigualdades. Valores máximos y mínimos

Una vez establecida la región factible, la programación lineal examina una función que debe maximizarse o minimizarse dentro de esta región factible. Las coordenadas de cada vértice de la región factible se sustituyen en la función. El resultado más grande es el valor máximo, y el más pequeño es el valor mínimo de la función basada en esta región.

Jason pinta a medida tablas de snowboard y motos de nieve. Tarda 5 horas en pintar una moto de nieve y 2 horas en pintar una tabla de snowboard. El beneficio de una moto de nieve es de 35 $ y el de una tabla de snowboard es de 10 $. Jason sólo puede dedicar 19 horas a la semana a esta pintura personalizada, y debe pintar al menos 1 moto de nieve y 2 tablas de snowboard cada semana. ¿Cuántas motos de nieve y tablas de snowboard debe pintar Jason cada semana para maximizar su beneficio? ¿Cuál es su beneficio máximo?

Solución básica programación lineal

Supongamos que una vendedora que quiere calcular sus máximos ingresos posibles tiene 30 portarretratos pequeños que se venden a 5 $ cada uno, 20 portarretratos grandes que se venden a 8 $ cada uno, y un cliente que no quiere comprar más de 40 portarretratos. El siguiente sistema de inecuaciones puede representar esas condiciones: {eq}0 \leq S \leq30 {/eq}, {eq}0 \leq L \leq20 {/eq}, y {eq}S + L \leq40 {/eq}. No importa qué variable se asigna a x y qué variable se asigna a y en el gráfico. Usando un sistema en el que S es x y L es y, el conjunto de inecuaciones es: {eq}0 \leq x \leq30 {/eq}, {eq}0 \leq y \leq20 {/eq}, y {eq}x + y \leq40 {/eq}, que se reordena a {eq}y \leq40 - x {/eq}. Nótese que los precios no aparecen en las desigualdades. Más bien aparecen en la función de ingresos, R, que hay que maximizar, que es R = 5x + 8y. La figura 1 muestra un gráfico de las tres inecuaciones.

Región factible en un gráficoPara obtener el gráfico de la región factible, haga lo siguiente: 1. 1. Represente las condiciones del problema mediante un conjunto de inecuaciones (y ecuaciones, si procede). 2. Si hay más de dos variables, utilice la sustitución para reducir el sistema a dos variables. 3. A continuación, grafique el sistema e identifique la región factible como el área en la que se solapan todas las inecuaciones. 4. Por último, escribe la función para maximizar o minimizar y prueba cada vértice de la región factible como x e y en esa función para determinar qué vértice produce el resultado óptimo.