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

Sistemas de ecuaciones no lineales

Sistema_no_linealUn sistema de ecuaciones es no lineal si, por lo menos, una de sus ecuaciones no es lineal (hay un grado mayor o menor que uno en las variables). Estos sistemas se resolverán habitualmente por sustitución o igualación. Es recomendable dibujar las ecuaciones del sistema en la medida de lo posible para hacerse una idea aproximada de la interpretación geométrica de las soluciones, si las hay.

Es importante comprobar que la resolución analítica concuerda con la representación gráfica de las soluciones, ya sea manualmente, ayudándose con calculadora, o mediante ordenador. Esto permitirá a la vez comprender los resultados, lo cual es siempre más efectivo que resolver el sistema sin ninguna idea aproximada de su significado.

pdf_boton_p+ INFO (SISTEMAS DE ECUACIONES NO LINEALES)

web

applet

video-icon

Método de Gauss

Metodo_Gauss

El método de Gauss para resolver sistemas de ecuaciones lineales, es una generalización del método de reducción. Consiste en transformar el sistema dado en otro equivalente en forma escalonada y de fácil resolución.

Este método conocido también como de triangulación o de cascada, nos permite resolver sistemas de ecuaciones lineales con cualquier número de ecuaciones y de incógnitas.

La idea es muy simple; por ejemplo, para el caso de un sistema de tres ecuaciones con tres incógnitas se trata de obtener un sistema equivalente cuya primera ecuación tenga tres incógnitas, la segunda dos y la tercera una. Se obtiene así un sistema triangular o en cascada de la forma:

Ax + By + Cz = D
Ey + Fz = G
Hz = I

La resolución del sistema es ahora inmediata; basta calcular z en la tercera ecuación, llevar este valor de z a la segunda ecuación para obtener el valor de y, y así despejar la incógnita x en la primera ecuación, conocidos ya z e y.

Al resolver un sistema puede suprimirse, sin que varíe su resolución, cualquier ecuación que pueda obtenerse a partir de otras.

  • Te aconsejamos primero consultar un resumen con teoría y ejemplos aquí.
  • Puedes ver un ejemplo resuelto con la aplicación del álgebra de matrices aquí.
  • El método de Gauss distingue entre sistemas compatibles determinados (SCD), sistemas incompatibles SI y sistemas compatibles indeterminados (SCI). Pulsa para ver ejemplos aquí.

pdf_boton_p+ INFO (MÉTODO de GAUSS)

applet

video-icon

Ecuaciones racionales, puesta a punto

ecuacion_racional

¿Qué son las ecuaciones racionales?

Ecuaciones donde hay alguna x (o la incógnita) en algún denominador. Como en toda el ecuación, el objetivo es encontrar el o los valores de x que verifican la igualdad. Es decir, despejar la x (o la letra que tenga como incógnita) para llegar a la solución o soluciones. Hay varias formas de resolver una ecuación racional, dependiendo del tipo de ejercicio:

1) Buscando el denominador común entre todos los denominadores de las fracciones que aparecen en ambos miembros de la ecuación. Y luego de transformados los numeradores (como se hace en la suma de fracciones), los denominadores se pueden cancelar.

2) Pasando todos los términos de un lado, y que del otro quede 0 (“igualar a cero”). Luego se busca denominador común, se transforman los numeradores como en la suma de fracciones, y se puede cancelar el denominador común.

3) Buscar denominador común entre las fracciones de un miembro, y luego pasar ese denominador común multiplicando al otro miembro (ya que el denominador es algo que está dividiendo, en una ecuación se lo puede pasar multiplicando).

4) Si es una proporción (igualdad de dos fracciones), se puede usar la Propiedad fundamental de las proporciones (“El producto de los medios es igual al producto de los extremos”, o “Igualar los productos cruzados”). Pero si no es una proporción, también se puede buscar denominador común en cada término para que lo sea, y luego aplicar la propiedad.

¿Qué es la Condición de Existencia (C.E.)?

El denominador de una fracción no puede ser 0 (cero), porque el denominador de una fracción está dividiendo al numerador, y dividir por cero no se puede. Entonces, en una ecuación racional, la solución no puede ser un número que haga que un denominador dé cero.

¿Qué es el Conjunto Solución?

Hay ecuaciones que tienen una sola solución, otras que tienen dos, ninguna, etc. El conjunto formado por esas soluciones es el llamado Conjunto solución. Por tanto, después de resolver este tipo de ecuaciones, siempre hay que comprobar las posibles soluciones en la ecuación original.

Si quieres saber más y ver ejemplos resueltos pulsa aquí.

+ INFO (ECUACIONES RACIONALES)

recomendado

pdf_boton_p

applet

web