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

Anuncios

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

La anécdota del Príncipe de las Matemáticas

Libro_GaussDe la infancia de Carl Friedrich Gauss, llamado el Príncipe de las Matemáticas, se cuenta que aprendió a leer él solo (autodidacta) y que a los tres años le corrigió un error aritmético a su padre. Gauss fue escolarizado de forma temprana en la ciudad de Braunschweig, cerca de Hannover.

En 1784, tras su séptimo cumpleaños, el pequeño entró en una escuela pública de educación primaria donde las clases las impartía un profesor llamado J. B. Büttner. La escuela estaba ubicada en una habitación sombría, de techo bajo, suelo desigual, … donde cerca de un centenar de pupilos de Büttner iban y venían. El profesor imponía una disciplina rígida y nadie podía llevarle la contraria. En esta escuela, que seguía el patrón de la Edad Media, Gauss llevaba dos años como alumno sin provocar ningún incidente reseñable.

El primer día que Gauss asistió a la clase de Aritmética, en la que había niños de hasta 15 años, ocurrió un incidente que Gauss solía contar ya anciano para el deleite de sus contertulios. Cuando el profesor proponía un problema, el alumno que acababa el primero tenía que llevar su pizarrita hasta la mesa del profesor. El segundo que lo lograra colocaba la suya encima, y así sucesivamente. El primer día que el joven Gauss entró en clase, el profesor Büttner, a viva voz, estaba dictando un problema de aritmética para sus alumnos. Justo al acabar de dictar el problema, Gauss colocó su pizarrita sobre la mesa del profesor, quien con absoluta seguridad afirmó: “Debe estar mal.” Mientras, el resto de los alumnos continuaron con su tarea (contando, multiplicando, y sumando). Büttner recorría la clase observando a sus alumnos con una mirada irónica, casi compasiva, hacia sus alumnos. Sólo un niño estaba sentado, callado, con su tarea ya finalizada, consciente de que la había resuelto correctamente y que su resultado era el único posible.

escuela_Gauss

Al final de la clase, el profesor dio por acabado el examen y volvió las pizarras hacia arriba. La primera, la del joven Gauss, sólo contenía un número. Cuando Büttner lo leyó, para su sorpresa y la de todos los presentes, resultó que la respuesta del joven Gauss era correcta. Muchos de sus compañeros, sin embargo, habían obtenido una respuesta errónea.

Según se relata en algunas biografías de Gauss, parece ser que el viejo profesor Büttner castigó a todos los niños a sumar los 100 primeros números naturales para tenerlos entretenidos y callados un buen rato.

Gauss obtuvo la respuesta casi de inmediato: 1 + 2 + 3 + … + 99 + 100 = 5050. Una historia mil veces contada. Todos los profesores de primaria y secundaria se la cuentan a sus alumnos. ¿Ocurrió de verdad? ¿Hay alguna evidencia histórica? Sigue la historia contando que Gauss, el niño prodigio, se dio cuenta de que 1 + 100, 2 + 99, 3 + 98, etc., todos suman 101, y que hay 50 de estos pares, resultando 50 × 101 = 5050.

suma_gauss

Gauss había deducido la fórmula que da la suma de n términos de una progresión aritmética de la que se conocen el primero (1) y el último término (100):

Suma_progresiondónde a1 es el primer término, an el último, y n es el número de términos de la progresión y parece ser esta fórmula se conoce, como mínimo, desde el s. VIII. Leer más de esta entrada