Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Tipos de metodos programacion lineal

No description
by

Kenya Rodriguez

on 21 January 2017

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Tipos de metodos programacion lineal

Programación lineal
Rodriguez Vazquez Kenya Valeria
Moran Trejo Karen Raquel
Villegas Vatres Mariana
Romero Cruz Susana Guadalupe
2.1 Formulación y aplicación de modelos de programación lineal
En todos los problemas aplicados a la programación lineal hay una estructura común: se quiere optimizar un objetivo sujeto a una serie de restricciones; por supuesto todas estas condiciones se deben poder expresar linealmente. esta estructura común es precisamente el modelo de la programación lineal. La forma del modelo es la siguiente:
2.2 Método gráfico y programación lineal.
2.5 Método dual-simplex.
Programación lineal.
La programación lineal (PL) es una de las técnicas de modelación dentro de la investigación de operaciones, especialmente utilizada para la planeación óptima y para la toma de decisiones.

Se emplea para problemas de planeación de la producción dentro de la industria; la optimización en el uso de los recursos humanos y materiales de las organizaciones o instituciones; planear dietas, recorridos, carteras de inversiones, inventarios, y un sinnúmero de aplicaciones en distintas áreas.
• Variables de Decisión:
Con las variables de decisión nos referimos al conjunto de variables cuya magnitud deseamos determinar resolviendo el modelo de programación lineal.
• Restricciones:
Están constituidas por el conjunto de desigualdades que limitan los valores que puedan tomar las variables de decisión en la solución.
• Función Objetivo:

Es la función matemática que relaciona las variables de decisión.
• Linealidad:

Se refiere a que las relaciones entre las variables, tanto en la función objetivo como en las restricciones deben ser lineales.
• Desigualdades:
Las desigualdades utilizadas para representar las restricciones deben ser cerradas o flexibles, es decir, menor - igual (<=) o mayor – igual (>=). No se permiten desigualdades de los tipos menor- estrictamente o mayor – estrictamente, o abiertas.
• Condición de no – negatividad:
En la programación lineal las variables de decisión sólo pueden tomar valores de cero a positivos. No se permiten valores negativos.

2.3 Método simplex.
2.4 Método dual.
2.3.1 Método algebraico de programación lineal.
2.3.2 La tabla simples.
2.6 Ejemplo en poom
El concepto de dualidad indica que para cada problema de PL hay una asociación y una relación muy importante con otro problema de programación lineal, llamado precisamente dual.
La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades:
Aporta elementos que aumentan sustancialmente la compresión de la PL.
El análisis de dualidad es una herramienta útil en la solución de problemas de PL, por ejemplo: más restricciones que variables.
El problema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de PL.
La forma estándar general del primal se defina como; para maximizar o minimizar.


• El número de variables que presenta el problema dual se ve determinado por el número de restricciones que presenta el problema primal.
• El número de restricciones que presenta el problema dual se ve determinado por el número de variables que presenta el problema primal.
• Los coeficientes de la función objetivo en el problema dual corresponden a los términos independientes de las restricciones (RHS), que se ubican del otro lado de las variables.
• Los términos independientes de las restricciones (RHS) en el problema dual corresponden a los coeficientes de la función objetivo en el problema primal.
• La matriz que determina los coeficientes técnicos de cada variable en cada restricción corresponde a la transpuesta de la matriz de coeficientes técnicos del problema primal.

Relaciones entre problemas primales y duales.
El sentido de las igualdades y desigualdades se comporta según la tabla de TUCKER, presentada a continuación.
Importancia de la dualidad en programación lineal.
La resolución de los problemas duales respecto a los primales se justifica dada la facilidad que se presenta dados problemas donde el número de restricciones supere al número de variables. Además de tener gran aplicación en el análisis económico del problema.
Otra de las ventajas que presenta es que dado a que el número de restricciones y variables entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que presenten dos restricciones sin importar el número de variables.

El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.
Este famosísimo método fue creado en el año de 1947 por el estadounidense George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de solucionar problemas de m restricciones y n variables.

El método algebraico es una forma de trabajar con el método simplex pero sin usar las tablas, utiliza únicamente álgebra y lógica matemática para hallar la solución optima. Consta de los siguientes pasos:

1. Determinar si existe una básica factible inicial.
2. Determinar si existe una solución básica factible mejor. Si es así realizar el siguiente paso, de otro modo, la solución actual es optima.
3. Pasar a la siguiente solución básica factible, cambiando una variable básica por una no básica, haciendo que todas las variables sean no negativas y regresamos al paso 2.

Este método es poco aplicado porque llega a ser muy tardado y poco practico, a diferencia del simplex donde toda la información se almacena en tablas y las operaciones de estas tablas son rápidas. Pero este método trabaja muy rápido cuando los sistemas de restricciones es muy pequeño y no hay que hacer tantos movimientos entre los extremos de la región factible.

Este método se aplica a problemas óptimos, pero infactibles. En este caso, las restricciones se expresan en forma canónica (restricciones).
La función objetivo puede estar en la forma de maximización o de minimización. Después de agregar las variables de holgura y de poner el problema en la tabla, si algún elemento de la parte derecha es negativo y si la condición de optimidad está satisfecha, el problema puede resolverse por el método dual simplex. Note que un elemento negativo en el lado derecho significa que el problema comienza óptimo, pero infactible como se requiere en el método dual simplex. En la iteración donde la solución básica llega a ser factible esta será la solución óptima del problema.

CONDICION DE FACTIBILIDAD.
La variable que sale es la variable básica que tiene el valor más negativo (los empates se rompen arbitrariamente si todas las variables básicas son no negativas, el proceso termina y esta última tabla es la solución óptima factible).
CONDICION DE OPTIMIDAD.

La variable que entra se elige entre las variables no básicas como sigue. Tome los cocientes de los coeficientes de la función objetivo entre los coeficientes correspondientes a la ecuación asociada a la variable que sale. Ignore los cocientes asociados a denominadores positivos o cero. La variable que entra es aquella con el cociente más pequeño si el problema es de minimizar o el valor absoluto más pequeño si el problema es de maximización (rompa los empates arbitrariamente). Si los denominadores son ceros o positivos el problema no tiene ninguna solución factible.

Este método consiste en representar geométricamente las restricciones, variables y función objetivo.
El método gráfico se emplea para resolver problemas que presentan sólo 2 variables de decisión. El procedimiento consiste en trazar las ecuaciones de las restricciones en un eje de coordenadas X1, X2 para tratar de identificar el área de soluciones factibles (soluciones que cumplen con todas las restricciones).
La solución óptima del problema se encuentra en uno de los vértices de esta área de soluciones creada, por lo que se buscará en estos datos el valor mínimo o máximo del problema.

Los pasos necesarios para realizar el método son:

1. Hallar las
Restricciones
,
Función Objetivo
y las
Variables
del problema.
2.
Sustituir


y

por
(=)
para cada restricción, con lo cual se produce la ecuación de una línea recta.
3.
Trazar la línea recta correspondiente a cada restricción en el plano.
La región en cual se encuentra cada restricción, el área correspondiente a cada restricción lo define el signo correspondiente a cada restricción (≥ ó ≤).
4.
El espacio en el cual se satisfacen las tres restricciones es el área factible.
Cada punto situado en la frontera del espacio del área factible, es decir que satisfacen todas las restricciones, representa un punto factible.
5. Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de valores arbitrarios a fin de determinar la pendiente y la dirección en la cual crece o decrece el valor de la función objetivo.
6.
La solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo
, se procede a graficar la función objetivo, si es un problema de minimización la solución óptima es el primer punto factible que toque la función Z, y si por lo contrario es un problema de maximización, será entonces el último de los puntos factibles que toque la función Z.

La Programación Lineal no solo radica en el procedimiento matemático, sino en la
herramienta financiera que sirve de soporte para la toma de decisiones
en cualquier organización. Adicionalmente, vale la pena resaltar que, para el Administrador de Empresas, el Economista, el contador, el Gerente, el financiero, y para el empresario en general, es vital manejar adecuadamente esta herramienta que es aplicable a todas las áreas que componen una organización empresarial y que permiten la asignación eficiente de los recursos, además de la ayuda que presta para globalizar la información. La Programación Lineal busca la asignación eficiente de los recursos asignados, que permite maximizar las utilidades y minimizar los costos. Por lo tanto, Programación Lineal comprende la planificación de actividades, es decir un resultado que alcance la meta en la mejor forma teniendo en cuenta las restricciones propias de cada actividad.
La Economía de negocios
, donde se busca determinar el precio de los productos, el análisis del punto muerto, el calculo de costo de productos y la sustitución de equipos.
Las Finanzas
, que evalúan las empresas, planeando las finanzas personales, comercio de divisas y administración de efectivo, análisis de inversión y control de presupuestos de un proyecto entre otros.
Las Operaciones en la Producción
. Donde se evalúan decisiones sobre fuentes de aprovisionamiento, mezclas de productos, control de inventarios, planeación de personal y de producción y pronostico de ventas.
Importancia de la programación lineal.
¿Cómo se aplica la programación lineal en áreas empresariales?
Pasos:
1.-Realizar un cambio de variables y normalizar el signo de los términos independientes.
2.- Normalizar las restricciones.
3.-Igualar la función objetivo a cero.
4.-Escribir la tabla inicial del método Simplex.
5.- Condición de parada.
6.-Elección de la variable entrante y saliente de la base.
7.- Actualizar la tabla.
8.- Al comprobar la condición de parada se observa que no se cumple ya que entre los elementos de la última fila hay uno negativo, -1. Se continúa iterando nuevamente los pasos 6 y 7.
9.- Una nueva comprobación de la condición de parada revela que entre los elementos de la fila indicadora vuelve a haber uno negativo, -1. Significa que aun no se ha llegado a la solución óptima y hay que seguir iterando (pasos 6 y 7).
10.- Fin del algoritmo.
Importancia
La importancia de este método radica en que gracias a su existencia se pueden resolver problemas complejos. Este método conforma la base de la programación lineal y es debido a que facilita la toma de decisiones en casos complejos ya que permite solucionar sistemas donde en número de variables supera el número de ecuaciones, ha resultado ser muy eficiente en la práctica.

Ventajas
Es un Método heurístico. Se basa en consideraciones geométricas y no requiere el uso de derivadas de la función objetivo.
Es de gran eficiencia incluso para ajustar gran número de parámetros.
Se puede usar con funciones objetivo muy sinuosas pues en las primeras iteraciones busca el mínimo más ampliamente y evita caer en mínimos locales fácilmente.
Es fácil implementar y usar, y sin embargo tiene un alta eficacia.

Desventajas
Converge más lentamente que otros métodos, pues requiere más número de iteraciones.
En el caso de que la función tenga todas sus variables básicas positivas, y además las restricciones sean de desigualdad "≤", al hacer el cambio se quedan negativas y en la fila del valor de la función objetivo se quedan positivos, por lo que se cumple la condición de parada, y por defecto el valor óptimo que se obtendría es 0.

Las tablas simples es matemáticamente equivalente a la forma algebraica, nada más que en lugar de escribir cada conjunto de ecuaciones con todo detalle, se usa una tabla símplex para registrar sólo la información esencial, a saber:

1. los coeficientes de las variables
2. las constantes del lado derecho de las ecuaciones
3. las variables básicas que aparecen en cada ecuación

Importancia
• Las tablas simples te ayudará a encontrar la solución de cualquier problema usando únicamente los coeficientes de las ecuaciones, los cuales se colocan en una tabla, siguiendo el mismo formato del sistema de una tabla, siguiendo el mismo formato del sistema de ecuaciones original.
Ventaja
• Este método lo puedes aplicar para dos o más variables
• simplifica las operaciones y cálculos que tienes que realizar

Tipos de métodos y sus componentes para el desarrollo de un problema de
INTEGRANTES
SOLUCION
Full transcript