Programación Lineal
Un problema de Programación Lineal consiste en encontrar el máximo o el mínimo de una función, como, por ejemplo, los beneficios de una empresa o el coste de una dieta, teniendo en cuenta una serie de limitaciones (restricciones) impuestas por las condiciones materiales en las que se desarrolla nuestro problema (número de trabajadores, cantidad mínima diaria de calorías, etc.)
Más en concreto, un problema de Programación Lineal presenta siempre los siguientes elementos:
· Un sistema de inecuaciones, llamadas restricciones, impuestas por la naturaleza del problema. El polígono convexo formado por las soluciones del sistema recibe el nombre de región factible.
· Una función lineal de dos variables, de la forma f(x,y)=ax+by+c, que recibe el nombre de función objetivo. Resolver el problema consiste en encontrar el punto, o los puntos, de la región factible en los que f alcanza su máximo o su mínimo.
Por ejemplo, vamos a buscar el máximo de la función
f(x,y)=-x+y+2,
sujeta a las restricciones:
x>=0, y>=0, 2x-3y<=0, 2x-9y<=-18.
Si observas la animación verás que una forma de resolverlo consiste en representar en el espacio la región factible (en el plano XY) y la función objetivo en la forma
z=f(x,y),
y encontrar el punto de la región factible en el que f(x,y) es más grande (aquél en el que z alcanza su mayor altura)
El inconveniente que presenta el método anterior es que nos obliga a utilizar una representación en el espacio.
Por eso, en la práctica resulta más conveniente representar en el plano la región factible y trazar las llamadas curvas de nivel, que, como en un mapa, representan los puntos en los que la función objetivo alcanza la misma altura.
Como la función objetivo es un plano, las curvas de nivel que obtenemos son rectas, todas ellas paralelas.
Según se va cambiando de una recta paralela a otra el valor de f va aumentando o disminuyendo.
Para terminar de resolver el problema, obtener el máximo o el mínimo que estás buscando, debes observar cómo varía la función objetivo (en algunas ocasiones el valor de la función objetivo aumenta cuando aumentas la ordenada en el origen de las rectas paralelas y en otras ocurre lo contrario) y en qué puntos las paralelas a ella "abandonan" la región factible.
Si la región no está acotada los extremos a veces no existen y si existen se alcanzan en un vértice, un segmento o una semirecta (¿por qué?). Si la región está acotada siempre existen los extremos y pueden alcanzarse en un vértice o en un segmento (¿por qué?).
Método gráfico de resolución de sistemas
Cada una de las ecuaciones que forman un sistema lineal de dos ecuaciones con dos incógnitas es la de una función de primer grado, es decir, una recta. El método gráfico para resolver este tipo de sistemas consiste, por tanto, en representar en unos ejes cartesianos, o sistema de coordenadas, ambas rectas y comprobar si se cortan y, si es así, dónde. Esta última afirmación contiene la filosofía del proceso de discusión de un sistema por el método gráfico. Hay que tener en cuenta, que, en el plano, dos rectas sólo pueden tener tres posiciones relativas (entre sí): se cortan en un punto, son paralelas o son coincidentes (la misma recta). Si las dos rectas se cortan en un punto, las coordenadas de éste son el par (x, y) que conforman la única solución del sistema, ya que son los únicos valores de ambas incógnitas que satisfacen las dos ecuaciones del sistema, por lo tanto, el mismo es compatible determinado. Si las dos rectas son paralelas, no tienen ningún punto en común, por lo que no hay ningún par de números que representen a un punto que esté en ambas rectas, es decir, que satisfaga las dos ecuaciones del sistema a la vez, por lo que éste será incompatible, o sea sin solución. Por último, si ambas rectas son coincidentes, hay infinitos puntos que pertenecen a ambas, lo cual nos indica que hay infinitas soluciones del sistema (todos los puntos de las rectas), luego éste será compatible indeterminado.
El proceso de resolución de un sistema de ecuaciones mediante el método gráfico se resume en las siguientes fases:
· Se despeja la incógnita y en ambas ecuaciones.
· Se construye, para cada una de las dos funciones de primer grado obtenidas, la tabla de valores correspondientes.
· Se representan gráficamente ambas rectas en los ejes coordenados.
· En este último paso hay tres posibilidades:
· Si ambas rectas se cortan, las coordenadas del punto de corte son los únicos valores de las incógnitas x e y. Sistema compatible determinado.
· Si ambas rectas son coincidentes, el sistema tiene infinitas soluciones que son las respectivas coordenadas de todos los puntos de esa recta en la que coinciden ambas. Sistema compatible indeterminado.
· Si ambas rectas son paralelas, el sistema no tiene solución. Sistema incompatible.
Un problema de Programación Lineal consiste en encontrar el máximo o el mínimo de una función, como, por ejemplo, los beneficios de una empresa o el coste de una dieta, teniendo en cuenta una serie de limitaciones (restricciones) impuestas por las condiciones materiales en las que se desarrolla nuestro problema (número de trabajadores, cantidad mínima diaria de calorías, etc.)
Más en concreto, un problema de Programación Lineal presenta siempre los siguientes elementos:
· Un sistema de inecuaciones, llamadas restricciones, impuestas por la naturaleza del problema. El polígono convexo formado por las soluciones del sistema recibe el nombre de región factible.
· Una función lineal de dos variables, de la forma f(x,y)=ax+by+c, que recibe el nombre de función objetivo. Resolver el problema consiste en encontrar el punto, o los puntos, de la región factible en los que f alcanza su máximo o su mínimo.
Por ejemplo, vamos a buscar el máximo de la función
f(x,y)=-x+y+2,
sujeta a las restricciones:
x>=0, y>=0, 2x-3y<=0, 2x-9y<=-18.
Si observas la animación verás que una forma de resolverlo consiste en representar en el espacio la región factible (en el plano XY) y la función objetivo en la forma
z=f(x,y),
y encontrar el punto de la región factible en el que f(x,y) es más grande (aquél en el que z alcanza su mayor altura)
El inconveniente que presenta el método anterior es que nos obliga a utilizar una representación en el espacio.
Por eso, en la práctica resulta más conveniente representar en el plano la región factible y trazar las llamadas curvas de nivel, que, como en un mapa, representan los puntos en los que la función objetivo alcanza la misma altura.
Como la función objetivo es un plano, las curvas de nivel que obtenemos son rectas, todas ellas paralelas.
Según se va cambiando de una recta paralela a otra el valor de f va aumentando o disminuyendo.
Para terminar de resolver el problema, obtener el máximo o el mínimo que estás buscando, debes observar cómo varía la función objetivo (en algunas ocasiones el valor de la función objetivo aumenta cuando aumentas la ordenada en el origen de las rectas paralelas y en otras ocurre lo contrario) y en qué puntos las paralelas a ella "abandonan" la región factible.
Si la región no está acotada los extremos a veces no existen y si existen se alcanzan en un vértice, un segmento o una semirecta (¿por qué?). Si la región está acotada siempre existen los extremos y pueden alcanzarse en un vértice o en un segmento (¿por qué?).
Método gráfico de resolución de sistemas
Cada una de las ecuaciones que forman un sistema lineal de dos ecuaciones con dos incógnitas es la de una función de primer grado, es decir, una recta. El método gráfico para resolver este tipo de sistemas consiste, por tanto, en representar en unos ejes cartesianos, o sistema de coordenadas, ambas rectas y comprobar si se cortan y, si es así, dónde. Esta última afirmación contiene la filosofía del proceso de discusión de un sistema por el método gráfico. Hay que tener en cuenta, que, en el plano, dos rectas sólo pueden tener tres posiciones relativas (entre sí): se cortan en un punto, son paralelas o son coincidentes (la misma recta). Si las dos rectas se cortan en un punto, las coordenadas de éste son el par (x, y) que conforman la única solución del sistema, ya que son los únicos valores de ambas incógnitas que satisfacen las dos ecuaciones del sistema, por lo tanto, el mismo es compatible determinado. Si las dos rectas son paralelas, no tienen ningún punto en común, por lo que no hay ningún par de números que representen a un punto que esté en ambas rectas, es decir, que satisfaga las dos ecuaciones del sistema a la vez, por lo que éste será incompatible, o sea sin solución. Por último, si ambas rectas son coincidentes, hay infinitos puntos que pertenecen a ambas, lo cual nos indica que hay infinitas soluciones del sistema (todos los puntos de las rectas), luego éste será compatible indeterminado.
El proceso de resolución de un sistema de ecuaciones mediante el método gráfico se resume en las siguientes fases:
· Se despeja la incógnita y en ambas ecuaciones.
· Se construye, para cada una de las dos funciones de primer grado obtenidas, la tabla de valores correspondientes.
· Se representan gráficamente ambas rectas en los ejes coordenados.
· En este último paso hay tres posibilidades:
· Si ambas rectas se cortan, las coordenadas del punto de corte son los únicos valores de las incógnitas x e y. Sistema compatible determinado.
· Si ambas rectas son coincidentes, el sistema tiene infinitas soluciones que son las respectivas coordenadas de todos los puntos de esa recta en la que coinciden ambas. Sistema compatible indeterminado.
· Si ambas rectas son paralelas, el sistema no tiene solución. Sistema incompatible.
EL METODO SIMPLEX PARA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL
Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.
Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
MODELO DE TRANSPORTE
DEFINICIÓN Y APLICACIÓN DEL MODELO DE TRANSPORTE
El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:
1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2. El costo de transporte unitario de la mercancía a cada destino.
Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.
La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al numero de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.
DEFINICIÓN Y APLICACIÓN DEL MODELO DE TRANSPORTE
El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:
1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2. El costo de transporte unitario de la mercancía a cada destino.
Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.
La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al numero de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.
MÉTODO de ASIGNACIÓN
El problema de asignación tiene que ver con la asignación de tareas a empleados, de territorios a vendedores, de contratos a postores o de trabajos a plantas. Al aplicar el método de transporte y el método de asignación la gerencia está buscando una ruta de distribución o una asignación que optimizará algún objetivo; éste puede se la minimización del costo total, la maximización de las utilidades o la minimización del tiempo total involucrado.
Al igual que el método de transporte el método de asignación es computacionalmente más eficiente que el método simplex para una clase especial de problemas.
No hay comentarios:
Publicar un comentario