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

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Programación Lineal

Algebra Lineal
by

Yurenis Pelayo Nava

on 2 August 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Programación Lineal

ALGEBRA
LINEAL
Realizado por:
Br. Yurenis Pelayo
C.I. 20.553.300

Programación Lineal
La programación lineal es una técnica matemática relativamente reciente (siglo XX), que consiste en una serie de métodos y procedimientos que permiten resolver problemas de optimización en el ámbito, sobre todo, de las Ciencias Sociales.

En infinidad de aplicaciones de la industria, la economía, la estrategia militar, etc.. se presentan situaciones en las que se exige maximizar o minimizar algunas funciones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.
Concepto
El adjetivo lineal significa que todas las funciones matemáticas del modelo deber ser funciones lineales. En este caso, las palabra programación no se refiere a programación en computadoras; en esencia es un sinónimo de planeación. Así, la programación lineal trata la planeación de las actividades para obtener un resultado óptimo.
FORMULACIÓN DEL PROBLEMA DE PROGRAMACIÓN LINEAL
Los términos clave son recursos y actividades, en donde m denota el número de distintos tipos de recursos que se pueden usar y n denota el número de actividades bajo consideración.
Z = valor de la medida global de efectividad.
Xj = nivel de la actividad j (para j = 1,2,...,n).
Cj = incremento en Z que resulta al aumentar una unidad en el nivel de la actividad j.
bi = cantidad de recurso i disponible para asignar a las actividades (para i = 1,2,...,m).
aij = cantidad del recurso i consumido por cada unidad de la actividad j.
ESTRUCTURA DE UN MODELO DE PROGRAMACIÓN LINEAL
1. Función objetivo. Consiste en optimizar el objetivo que persigue una situación la cual es una función lineal de las diferentes actividades del problema, la función objetivo se maximizar o minimiza.
2. Variables de decisión. Son las incógnitas del problema. La definición de las variables es el punto clave y básicamente consiste en los niveles de todas las actividades que pueden llevarse a cabo en el problema a formular.
Programación Lineal
Metodo Simplex
el tipo más común de aplicación abarca el problema general de asignar recursos limitados entre actividades competitivas de la mejor manera posible (es decir, en forma óptima). Este problema de asignación puede surgir cuando deba elegirse el nivel de ciertas actividades que compiten por recursos escasos para realizarlas.
ESTRUCTURA DE UN MODELO DE PROGRAMACIÓN LINEAL
3. Restricciones Estructurales. Diferentes requisitos que debe cumplir cualquier solución para que pueda llevarse a cabo, dichas restricciones pueden ser de capacidad, mercado, materia prima, calidad, balance de materiales, etc.
4. Condición técnica. Todas las variables deben tomar valores positivos, o en algunos casos puede ser que algunas variables tomen valores negativos.
MODELO GENERAL DE PROGRAMACION LINEAL
Supuestos básicos de programación lineal
Técnicamente, existen cinco requerimientos adicionales de un problema de programación lineal a los cuales hay que tomar en consideración

Certeza
Proporcionalidad
Aditividad
Divisibilidad
No negatividad
Casos Especiales
de programación lineal
Ninguna solución factible: No existe una solución factible que satisfaga todas las restricciones dadas.
No acotación: Cuando un programa lineal no tiene soluciones finitas.
Redundancia: Es aquella que no afecta a la región de solución factible.
Soluciones óptimas alternativas: Un problema de programación lineal puede tener una o más soluciones.
FORMA ESTÁNDAR DE LOS MODELOS DE PROGRAMACIÓN LINEAL.
Supóngase que existe cualquier número (digamos m) de recursos limitados de cualquier tipo, que se pueden asignar entre cualquier número (digamos n) de actividades competitivas de cualquier clase. Etiquétense los recursos con números (1, 2, ..., m) al igual que las actividades (1, 2, ..., n). Sea xj (una variable de decisión) el nivel de la actividad j, para j = 1, 2, ..., n, y sea Z la medida de efectividad global seleccionada. Sea cj el incremento que resulta en Z por cada
incremento unitario en xj (para j = 1, 2, ..., n). Ahora sea bi la cantidad disponible del recurso i (para i = 1, 2, ..., m). Por último defínase aij como la cantidad de recurso i que consume cada unidad de la actividad j (para i= 1, 2, ..., m y j = 1, 2, ..., n). Se puede formular el modelo matemático para el problema general de asignar recursos a actividades. En particular, este modelo consiste en elegir valores de x1, x2, ..., xn para: Maximizar Z = C1X1 + C2X2 + ... +
CnXn,
Sujeto a las restricciones:
Ésta se llamará nuestra forma estándar (porque algunos libros de texto adoptan otras formas) para el problema de PL. Cualquier situación cuya formulación matemática se ajuste a este modelo es un problema de PL. En este momento se puede resumir la terminología que usaremos para los modelos de PL. La función que se desea maximizar, c1x1 + c2x2 + ... + cnxn, se llama función objetivo. Por lo general, se hace referencia a las limitaciones como
restricciones. Las primeras m restricciones (aquellas con una función del tipo ai1x1 + ai2x2 + ... + ainxn, que representa el consumo total del recurso i) reciben el nombre de restricciones funcionales. De manera parecida, las restricciones xj ≥ 0 se llaman restricciones de no negatividad. Las variables xj son las variables de decisión. Las constantes de entrada, aij, bi, cj, reciben el nombre de parámetros del modelo.
OTRAS FORMAS DE MODELOS DE PROGRAMACIÓN
Es conveniente agregar que el modelo anterior no se ajusta a la forma natural de algunos problemas de programación lineal. Las otras formas legítimas son las siguientes:

1. Minimizar en lugar de maximizar la función objetivo: Minimizar Z = c1x1 + c2x2 + ... + cnxn,

2. Algunas restricciones funcionales con desigualdad
en el sentido mayor o igual:
ai1x1 + ai2x2 + ... + ainxn, ³ bi, para algunos valores de i,

3. Algunas restricciones funcionales en forma de ecuación: ai1x1 + ai2x2 + ... + ainxn, = bi, para algunos valores de i,

4. Las variables de decisión sin la restricción de no negatividad: xj no restringida en signo para algunos valores de j .
FORMULACIÓN ALGEBRAICA: FORMA CANÓNICA
IMPORTANCIA DE LA FORMA CANÓNICA
• La forma canónica es importante porque todos los desarrollos e interpretaciones económicas del problema pueden referirse a la misma.
• Es posible transformar un problema de PL a un problema equivalente en forma canónica. • Un problema de PL puede consistir en: • Buscar un máximo o un mínimo de la función objetivo• Restricciones de tipo “≤“, “≥“ e “=“ • Variables positivas, negativas o no restringidas en signo • Conversión de un problema lineal general a su forma canónica: • Cambiar el sentido de la optimización • Cambiar el sentido de la desigualdad • Cambiar una desigualdad en igualdad Variable de holgura o “slack” Variable surplus • Cambiar igualdades en desigualdades • Cambiar variables sin restricción de signo a otras de signo positivo o nulo
TERMINOLOGÍA Y CONCEPTOS BÁSICOS
Conjunto factible
Es el conjunto de puntos que satisfacen simultáneamente todas las restricciones (o “filas”) del problema
• Actividades, columnas o variables (xj)
Representan los usos alternativos que deben competir entre sí para la obtención de los recursos de forma que se optimice la función objetivo
• Recursos (bi) Son productos, tiempo, etc. Se cuantifican en el término independiente o Right Hand Side (RHS) del problema.
• El conjunto factible de un problema de PL, si existe, es representable mediante un poliedro convexo
El método simplex fue desarrollado por George dantzig (1947) y es un método algebraico que se utiliza para resolver problemas de programación lineal en un número finito de pasos en una computadora. Este método establece una solución factible y luego prueba si es óptima o no. Si no lo es busca una mejor solución y si esta no es optima entonces repite el proceso hasta hallar una solución óptima.
Método Gráfico
La forma más fácil de resolver un pequeño problema de programación lineal es con el método de solución gráfico.

Para encontrar la solución óptima a un problema de programación lineal, primero se debe identificar un conjunto, o región, de soluciones factibles (Restricciones)
Solución gráfica de un problema de programación lineal
El método de
línea Insoluta
, es el primer método que se presenta para encontrar la solución óptima después de haber sido establecida la región factible.
Con respecto al método de solución de
punto de esquina
, la teoría matemática indica que la solución óptima debe quedar en uno de los puntos de esquina en la región factible.
Método de la Gran M
Se define la letra M como un número muy grande pero finito para usarlo como coeficiente de las variables artificiales en la función objetivo y con sentido contrario a la misma para penalizar de manera muy grande la existencia de las mismas en la solución. Si el objetivo es minimizar las variables artificiales entraran con M positivo y si es maximizar las variables artificiales se usaran como -M.
1- Pasar a la forma estándar el modelo matemático.

2- Agregar variables artificiales en las ecuaciones que no tienen variables de holgura.

3- Se deben penalizar a las variables artificiales en la función objetivo asignándoles coeficientes positivos muy grandes. Sea M un número muy grande. (En los modelos de Minimización la penalización para cada variable artificial se suma y en los de Maximización se restan).
Pasos
4- En la función objetivo no deben aparecer variables básicas por lo que se hace necesario eliminar las variables artificiales de la F.O. (Quitar las "M" de las columnas de las artificiales).

5- Con la solución inicial artificial se aplica el método simplex de la forma acostumbrada generando las tablas necesarias para llegar a una solución.
Pasos
Método de Dualidad
El dual es un problema de PL que se obtiene matemáticamente de un modelo primal de PL dado. Los problemas dual y primal están relacionados a tal grado, que la solución simplex óptima de cualquiera de los dos problemas conduce en forma automática a la solución óptima del otro.
¿Cómo convertir un problema primal a dual?
EJEMPLO
Primal:
Z=16X1+44X2

SUJETO A:

16X1+8X2>=176
32X1+64X2>=1024
4X1+10X2>=200
X1, X2>=0
Minimizar:
Dual:
EJEMPLO
W=176Y1+1024Y2+200Y3

SUJETO A:
16Y1+32Y2+4Y3<=16
8Y1+64Y2+10Y3<=44
Y1; Y2; Y3>=0
Maximizar:
SOLUCIÓN
16Y1+32Y2+4Y3+H1=16
8Y1+64Y2+10Y3+H2=44

W-176Y1-1024Y2-200Y3=0
Z= 800; X1=50; Y3=4
GRACIAS POR SU ATENCIÓN
Full transcript