Programación lineal

region_factible_2La programación lineal (PL) es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuaciones lineales optimizando una función objetivo, también lineal.

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.

Como origen de la PL, 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. Se trata de dar respuesta a situaciones en las que se exige maximizar o minimizar funciones (beneficios, costes, etc) que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones (nº de operarios, maquinaria, kg mercancía, etc) .

Su empleo es frecuente en aplicaciones de la industria, la economía, la estrategia militar, etc.

Existen tres métodos para resolver un problema de PL con dos variables (x,y):

Nosotros optaremos por explicar el segundo método, pues resulta más intuitivo y sencillo.

barra

ETAPAS DEL MÉTODO DE LOS VÉRTICES APLICADO A LA PROGRAMACIÓN LINEAL

Los pasos a seguir son:

1  Elegir las incógnitas.

2  Escribir la función objetivo en función de los datos del problema.

3  Escribir las restricciones en forma de sistema de inecuaciones.

4  Averiguar el conjunto de soluciones factibles representando gráficamente las restricciones.

5  Calcular las coordenadas de los vértices del recinto de soluciones factibles (si son pocos).

6  Calcular el valor de la función objetivo en cada uno de los vértices para ver en cuál de ellos presenta el valor máximo o mínimo según nos pida el problema (hay que tener en cuenta aquí la posible no existencia de solución si el recinto no está acotado)

Función Objetivo

En esencia la programación lineal consiste en optimizar (maximizar o minimizar) una función objetivo, que es una función lineal de varias variables, en casos sencillos dos variables: f(x,y) = ax + by

Restricciones

La función objetivo está sujeta a una serie de restricciones, expresadas por inecuaciones lineales:

a1x + b1y ≤ c1

a2x + b2y ≤ c2

anx + bny ≤ cn

Cada desigualdad del sistema de restricciones determina un semiplano.

Región factible

El conjunto intersección, de todos los semiplanos formados por las restricciones, determina un recinto limitado o ilimitado,  llamado región factible, acotado o no, que recibe el nombre de región de validez o zona de soluciones factibles.

Solución óptima

El conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el vértice donde se presenta la solución óptima  se llama solución máxima (o mínima según el caso).

Pulsa en este enlace para visualizar un ejemplo totalmente comentado que te ayudará a comprender este método.

Valor del programa lineal

El valor que toma la función objetivo en el vértice de solución óptima se llama valor del programa lineal.
barra
CASOS DE EJERCICIOS QUE SE PUEDEN PRESENTAR
 
Los problemas de Programación Lineal con dos variables se pueden clasificar, atendiendo al tipo de solución que presentan, en:

  • Factibles (con solución, por tanto, cuando existen uno más valores que satisfacen las restricciones)
  • No factibles (sin solución, por tanto, cuando las restricciones son inconsistentes)

A su vez los casos factibles pueden ser de:

  • Solución única
  • Solución múltiple
  • Solución no acotada (algunos casos en los que la región factible sea ilimitada)
web+ INFO (MÉTODO DE PROGRAMACIÓN LINEAL)

pdf_boton_p

applet

teacher_fem

video-icon

Inecuaciones y sistemas lineales de inecuaciones con dos variables

sistemas_dos_variables

RESOLUCIÓN DE UNA INECUACIÓN LINEAL CON DOS VARIABLES

Una inecuación con dos variables puede ser escrita como:   ax + by < c  , o cualquier expresión de la forma anterior que, en lugar del símbolo < incluya cualquier otro símbolo de desigualdad: > , o ≥ . Donde a, b y c son constantes y las letras “x” e “y” son variables.

Resolver una inecuación en dos variables consiste en encontrar todos los pares de valores solución (x,y) para los cuales se cumple la desigualdad.

Cuando intercambiamos el signo de desigualdad por el signo igual, obtenemos la ecuación ax + by = c, que representa a la recta asociada.

La inecuación anterior, mediante transformaciones de equivalencia, se puede expresar, dependiendo del signo de relación, como , es decir, la verifican todos los puntos que tiene una ordenada(y) menor (o mayor o igual, según el signo de relación) que la ordenada de los puntos de la recta. Por lo tanto, la solución general de una inecuación lineal con dos incógnitas es un semiplano, del que la recta anterior es su frontera.

Para resolver una inecuación de este tipo seguiremos los siguientes pasos:

  1. Despejar la variable “y” en la desigualdad, discerniendo si se trata de un semiplano superior (caso y >) o inferior (caso y <).
  2. Representar la recta asociada ax + by = c , que dividirá el plano cartesiano en dos mitades.
  3. Sombrear el semiplano solución, (superior o inferior) según lo indicado en el punto 1, teniendo en cuenta que si la desigualdad es ≥ o ≤ la frontera está incluida en la solución, en caso contrario la frontera no está incluida.

Ejemplo:
Resolver la siguiente inecuación 2·x + 3·y ≥ 6

Al despejar la variable “y” se obtiene:

y ≥ -2/3·x +2 (semiplano superior asociado a la recta  2·x+3·y = 6)

La recta se representa mediante dos puntos cualesquiera, que suelen ser los cortes con los ejes. En este caso los puntos (3,0) y (0,2)

inec_lineal_dos_variables

 

RESOLUCIÓN DE UN SISTEMA DE INECUACIONES LINEALES CON DOS VARIABLES

MathType 5.0 Equation

Como ya vimos, el conjunto solución de cada inecuación es un semiplano. Intuitivamente colegimos que el conjunto solución del sistema es la intersección de todos los semiplanos de las soluciones particulares. Hay que hacer notar que algunas veces el conjunto solución de un sistema de inecuacIones es el conjunto vacío. Para resolver un sistema de inecuaciones es recomendable utilizar el método gráfico.

Ejemplo:

Sistema_inec_lineal_dos_variables

pdf_boton_p

web

applet

video-icon

Inecuaciones racionales

Son aquellas inecuaciones en las que intervienen fracciones algebraicas, es decir, cocientes polinómicos.

Para resolverlas se pasan a un miembro todos los términos para que en el otro miembro quede un cero, obteniéndose así una inecuación equivalente. Luego se estudia en una tabla el signo de la fracción que se ha obtenido, descomponiendo el numerador y denominador en producto de factores y teniendo en cuenta, como condición, que el denominador no se puede anular.

Ejemplo:

inecuacion_racional

La solución del ejemplo de esta imagen sería el intervalo (0,1)

pdf_boton_p+ INFO (INECUACIONES RACIONALES)

web

applet

video-icon

Inecuaciones polinómicas de grado superior a dos

Son inecuaciones que se pueden escribir de la forma:  an xn  + an-1 xn-1 + …….. + a1 x + a0 > 0

Para su resolución, se procede de forma similar al caso de las inecuaciones polinómicas de segundo grado, es decir, se factoriza el polinomio y se estudia su signo.

inecuacion_polinomicaPara resolver una inecuación polinómica , seguiremos los siguientes pasos:

  1. Escribir la inecuación en la forma general, es decir, realizar las operaciones necesarias para que todo la expresión polinómica quede a un lado de la inecuación y cero en el otro lado.
  2. Factorizar el polinomio. Si no se puede factorizar, encontrar los puntos donde el polinomio es igual a cero.
  3. Hallar los intervalos de prueba. Esto se logra determinando los valores en que cada factor es cero, estos puntos determinarán los límites de los intervalos en la recta numérica.
  4. Seleccionar un punto de prueba en cada intervalo para determinar el signo en cada intervalo.

La solución la conforman todos los intervalos que hacen que la desigualdad sea cierta. La solución se puede expresar algebraica (como intervalo) y gráficamente.

Ejemplo:

inecuacion_Ngrado

Factorizamos la inecuación:

(x -1)(x – 2)(x – 1/2)(x + 2/3) < 0

En la que inter las raíces:

x = 1   ,    x = 2  ,   x = 1/2  ,   x =- 2/3

Estudiamos el signo en los intervalos:

(-∞ , – 2/3)
(-2/3 , 1/2)
(1/2 , 1)
(1 , 2)
(2 , ∞)
(x -1)(x – 2)(x – 1/2)(x + 2/3)
+ + +

El conjunto solución es:    (-2/3 ,1/2) ∪ (1 , 2)

pdf_boton_p+ INFO (INECUACIONES DE GRADO SUPERIOR A DOS)

web

applet

video-icon

Inecuaciones con valor absoluto

inecuacion_lineal

Todas las inecuaciones con valor absoluto se resuelven con la propiedad de acotación :

Si │a│< k  =>  -k < a < k  (casos 1 y 2 en los videos)

Si │a│> k  =>  -k > a > k  (casos 3 y 4 en los videos)

pdf_boton_p+ INFO (DESIGUALDADES CON VALOR ABSOLUTO)

video-icon

A continuación, para profundizar, te proponemos 4 videos muy aclaratorios.

Leer más de esta entrada