Programacion lineal
Páginas: 12 (2778 palabras)
Publicado: 2 de noviembre de 2011
1. PROGRAMACION 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.
Nos centraremos en este tema en aquellos problemas simples de programación lineal, los que tienen solamente 2 variables, problemasbidimensionales.
Para sistemas de más variables, el procedimiento no es tan sencillo y se resuelven por el llamado método Simplex (ideado por G.B.Danzig, matemático estadounidense en 1951). Recientemente (1984) el matemático indio establecido en Estados Unidos, Narenda Karmarkar, ha encontrado un algoritmo, llamado algoritmo de Karmarkar, que es más rápido que el método simplex en ciertos casos.Los problemas de este tipo, en el que intervienen gran numero de variables, se implementan en ordenadores.
1. Modelo 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. Algunos ejemplos de recursos son dinero y tipos especiales demaquinaria, equipo, vehículos y personal. Los ejemplos de actividades incluyen inversión en proyectos específicos, publicidad en un medio determinado y el envío de bienes de cierta fuente a cierto destino. En cualquier aplicación de programación lineal, puede ser que todas las actividades sean de un tipo general (como cualquiera de los ejemplos), y entonces cada una correspondería en forma individual alas alternativas específicas dentro de esta categoría general.
El tipo más usual de aplicación de programación lineal involucra la asignación de recursos a ciertas actividades. La cantidad disponible de cada recurso está limitada, de forma que deben asignarse con todo cuidado. La determinación de esta asignación incluye elegir los niveles de las actividades que lograrán el mejor valor posiblede la medida global de efectividad.
Ciertos símbolos se usan de manera convencional para denotar las distintas componentes de un modelo de programación lineal. Estos símbolos se enumeran a continuación, junto con su interpretación para el problema general de asignación de recursos a actividades.
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
El modelo establece el problema en términos de tomar decisiones sobre los niveles de las actividades, por lo que x1,x2,....,xn sellaman variables de decisión. Los valores de cj, bi y aij (para i = 1,2,....,m y j = 1,2,....,n) son las constantes de entrada al modelo. Las cj, bi y aij también se conocen como parámetros del modelo.
Forma estándar del modelo
Ahora se puede formular al modelo matemático para este problema general de asignación de recursos a actividades. En Datos necesarios para un modelo de programaciónlineal que maneja la asignación de recursos a actividades particular, este modelo consiste en elegir valores de x1,x2,....,xn para:
optimizar (maximizar o minimizar) Z = c1x1 + c2x2 +....+ cnxn,
sujeta a las restricciones:
a11x1 + a12x2 +....+ a1nxn < b1
a21x1 + a22x2 +....+ a2nxn < b2
.
. .
am1x1 + am2x2 +....+ amnxn < bm
X1 ³ 0, X2 ³0, ..., Xn ³0.
Suposiciones del Modelo de Programación Lineal
Proporcionalidad
La contribución de cada actividad al valor de la función objetivo Z es proporcional al nivel de actividad xj, como lo representa el término cjxj en la función objetivo. De manera similar, la...
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.
Nos centraremos en este tema en aquellos problemas simples de programación lineal, los que tienen solamente 2 variables, problemasbidimensionales.
Para sistemas de más variables, el procedimiento no es tan sencillo y se resuelven por el llamado método Simplex (ideado por G.B.Danzig, matemático estadounidense en 1951). Recientemente (1984) el matemático indio establecido en Estados Unidos, Narenda Karmarkar, ha encontrado un algoritmo, llamado algoritmo de Karmarkar, que es más rápido que el método simplex en ciertos casos.Los problemas de este tipo, en el que intervienen gran numero de variables, se implementan en ordenadores.
1. Modelo 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. Algunos ejemplos de recursos son dinero y tipos especiales demaquinaria, equipo, vehículos y personal. Los ejemplos de actividades incluyen inversión en proyectos específicos, publicidad en un medio determinado y el envío de bienes de cierta fuente a cierto destino. En cualquier aplicación de programación lineal, puede ser que todas las actividades sean de un tipo general (como cualquiera de los ejemplos), y entonces cada una correspondería en forma individual alas alternativas específicas dentro de esta categoría general.
El tipo más usual de aplicación de programación lineal involucra la asignación de recursos a ciertas actividades. La cantidad disponible de cada recurso está limitada, de forma que deben asignarse con todo cuidado. La determinación de esta asignación incluye elegir los niveles de las actividades que lograrán el mejor valor posiblede la medida global de efectividad.
Ciertos símbolos se usan de manera convencional para denotar las distintas componentes de un modelo de programación lineal. Estos símbolos se enumeran a continuación, junto con su interpretación para el problema general de asignación de recursos a actividades.
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
El modelo establece el problema en términos de tomar decisiones sobre los niveles de las actividades, por lo que x1,x2,....,xn sellaman variables de decisión. Los valores de cj, bi y aij (para i = 1,2,....,m y j = 1,2,....,n) son las constantes de entrada al modelo. Las cj, bi y aij también se conocen como parámetros del modelo.
Forma estándar del modelo
Ahora se puede formular al modelo matemático para este problema general de asignación de recursos a actividades. En Datos necesarios para un modelo de programaciónlineal que maneja la asignación de recursos a actividades particular, este modelo consiste en elegir valores de x1,x2,....,xn para:
optimizar (maximizar o minimizar) Z = c1x1 + c2x2 +....+ cnxn,
sujeta a las restricciones:
a11x1 + a12x2 +....+ a1nxn < b1
a21x1 + a22x2 +....+ a2nxn < b2
.
. .
am1x1 + am2x2 +....+ amnxn < bm
X1 ³ 0, X2 ³0, ..., Xn ³0.
Suposiciones del Modelo de Programación Lineal
Proporcionalidad
La contribución de cada actividad al valor de la función objetivo Z es proporcional al nivel de actividad xj, como lo representa el término cjxj en la función objetivo. De manera similar, la...
Leer documento completo
Regístrate para leer el documento completo.