Temario Unidad 1
Unidad 1 Programación Lineal
1.1 Definición desarrollo y tipos de modelos de investigación de operaciones
1.2 Formulación de modelos.
1.3 Método gráfico.
1.4 Fundamentos del método simplex.
1.5 Aplicaciones diversas de programación lineal
1.1 Características de la Investigación de Operaciones
• La Investigación de Operaciones usa el método científico para investigar el
problema en cuestión. En particular, el proceso comienza por la observación
cuidadosa y la formulación del problema incluyendo la recolección de datos
pertinentes.
• La Investigación de Operaciones adopta un punto de vista organizacional. De
esta manera intenta resolver los conflictos de interés entre los componentes de
la organización de forma que el resultado sea el mejor para la organización
completa.
• La Investigación de Operaciones intenta encontrar una mejor solución (llamada
solución óptima), para el problema bajo consideración. En lugar de contentarse
con mejorar el estado de las cosas, la meta es identificar el mejor curso de
acción posible.
• En la Investigación de Operaciones es necesario emplear el enfoque de
equipo. Este equipo debe incluir personal con antecedentes firmes en
matemáticas, estadísticas yteoría de probabilidades, economía, administración
de empresas ciencias de lacomputación, ingeniería, etc. El equipo también
necesita tener la experiencia y las habilidades para permitir la consideración
adecuada de todas las ramificaciones del problema.
• La Investigación de Operaciones ha desarrollado una serie de técnicas y
modelos muy útiles a la Ingeniería de Sistemas. Entre ellos tenemos: la
Programación No Lineal, Teoría de Colas, Programación Entera, Programación
Dinámica, entre otras.
• La Investigación de Operaciones tiende a representar el problema
cuantitativamente parapoder analizarlo y evaluar un criterio común.
Definición de Modelos
• Un modelo de decisión debe considerarse como un vehículo para resumir un
problema de decisión en forma tal que haga posible la identificación y
evaluación sistemática de todas las alternativas de decisión del problema.
Después se llega a una decisión seleccionando la alternativa que se juzgue
sea la mejor entre todas las opciones disponibles.
• Un modelo es una abstracción selectiva de la realidad.
• El modelo se define como una función objetivo y restricciones que se expresan
en términos de las variables (alternativas) de decisión del problema.
• Una solución a un modelo, no obstante, de ser exacta, no será útil a menos
que el modelo mismo ofrezca una representación adecuada de la situación de
decisión verdadera.
• El modelo de decisión debe contener tres elementos:
Alternativas de decisión, de las cuales se hace una selección.
Restricciones, para excluir alternativas infactibles.
Criterios para evaluar y clasificar alternativas factibles.
Tipos de Modelos de Investigación de Operaciones.
(a) Modelo Matemático: Se emplea cuando la función objetivo y las
restricciones del modelo se pueden expresar en forma cuantitativa o
matemática como funciones de las variables de decisión.
(b) Modelo de Simulación: Los modelos de simulación difieren de los
matemáticos en que las relaciones entre la entrada y la salida no se indican en
forma explícita. En cambio, un modelo de simulación divide el sistema
representado en módulos básicos o elementales que después se enlazan entre
si vía relaciones lógicas bien definidas. Por lo tanto, las operaciones de
cálculos pasaran de un módulo a otro hasta que se obtenga un resultado de
salida.
Los modelos de simulación cuando se comparan con modelos matemáticos;
ofrecen mayor flexibilidad al representar sistemas complejos, pero esta
flexibilidad no esta libre de inconvenientes. La elaboración de este modelo
suele ser costoso en tiempo y recursos. Por otra parte, los modelos
matemáticos óptimos suelen poder manejarse en términos de cálculos.
Modelos de Investigación de Operaciones de la ciencia de la
administración: Los científicos de la administración trabajan con modelos
cuantitativos de decisiones.
Modelos Formales: Se usan para resolver problemas cuantitativos de decisión
en el mundo real. Algunos modelos en la ciencia de la administración son
llamados modelos determinísticos. Esto significa que todos los datos relevantes
(es decir, los datos que los modelos utilizarán o evaluarán) se dan por
conocidos. En los modelos probabilísticos (o estocásticos), alguno de los datos
importantes se consideran inciertos, aunque debe especificarse la probabilidad
de tales datos.
En la siguiente tabla se muestran los modelos de decisión según su clase de
incertidumbre y su uso en las corporaciones. (D, determinista; P, probabilista; A,
alto; B, bajo)
Tipo de Modelo Clase de Incertidumbre Frecuencia de uso en
corporaciones
Programación Lineal D A
Redes D,P A
(Incluye PERT/CPM)
Inventarios, producción y D,P A
programación
Econometría, pronóstico D,P A
y simulación
Programación Entera D B
Programación Dinámica D,P B
Programación P B
Estocástica
Programación No Lineal D B
Teoría de Juegos P B
Control Optimo D,P B
Líneas de Espera P B
Ecuaciones Diferenciales D B
Modelo de Hoja de Cálculo Electrónica: La hoja de cálculo electrónica facilita
hacer y contestar preguntas de "que si" en un problema real. Hasta ese grado
la hoja de cálculo electrónica tiene una representación selectiva del problema y
desde este punto de vista la hoja de cálculo electrónica es un modelo.
En realidad es una herramienta más que un procedimiento de solución.
Etapas de la Investigación de Operaciones.
Las etapas de un estudio de Investigación de Operaciones son las siguientes:
Definición del problema de interés y recolección de los datos relevantes.
Formulación de un modelo matemático que represente el problema.
Desarrollo de un procedimiento basado en computadora para derivar una
solución al problema a partir del modelo.
Prueba del modelo y mejoramiento según sea necesario.
Preparación para la aplicación del modelo prescrito por la administración.
Puesta en marcha.
1.2 Formulación del Modelo
Una vez que nos aseguramos que la definición del problema ha sido construida
de manera específica y correcta, continuamos con la formulación del modelo.
El modelo, usualmente matemático, debe ser formulado de tal manera que
exprese la esencia del problema:
El modelo matemático está basado en ecuaciones y desigualdades
establecidas en términos de variables, las cuales expresan la esencia del
problema a resolver; las cuales son definidas en función del modelo del
problema.
Después de localizar las variables en función del problema, se procede a
determinar matemáticamente las dos partes que constituyen el modelo:
• La medida de efectividad que permite conocer el nivel de logro de los
objetivos y generalmente es una función llamada función objetivo.
• Las limitantes del problema, llamadas restricciones, que son un conjunto
de igualdades o desigualdades que constituyen las barreras y
obstáculos para la consecución del objetivo.
• Un modelo matemático es una idealización abstracta de un problema, lo
cual mayormente nos lleva a aproximaciones y suposiciones. Por lo que
debemos cuidar que el modelo siempre sea una representación valida
del problema.
La valides de un modelo requiere que exista una alta correlación entre las
predicciones del modelo y la realidad; para lograr esto es importante hacer un
número considerable de pruebas al modelo y caso de ser necesario, las
pertinentes modificaciones. Aun cuando la validación del modelo se incluyera al
final de este documento, la mayor parte de la validación del modelo se hace
durante la etapa de la construcción del modelo.
• Validación del Modelo
• Solución Optima
1.3 METODO GRAFICO
La PL es una técnica mediante la cual se toman decisiones, reduciendo el
problema bajo estudio a un modelo matemático general, el cual debe ser
resuelto por métodos cuantitativos.
En desarrollo de este capítulo se aplicarán la solución de dichos modelos
aplicando diversas técnicas como: el método gráfico, método simplex, método
matricial, técnica de la gran M.
Además se desarrollara la aplicación de variables artificiales y obtención de
soluciones para identificar a qué tipo de clasificación pertenecen. Por medio de
dichos modelos de solución se podrá obtener la solución adecuada para cada
problema y facilitar la toma de decisiones.
Método gráfico.
El método gráfico se utiliza para la solución de problemas de PL, representando
geométricamente a las restricciones, condiciones técnicas y el objetivo.
El modelo se puede resolver en forma gráfica si sólo tiene dos variables. Para
modelos con tres o más variables, el método gráfico es impráctico o imposible.
Cuando los ejes son relacionados con las variables del problema, el método es
llamado método gráfico en actividad. Cuando se relacionan las restricciones
tecnológicas se denomina método gráfico en recursos.
Los pasos necesarios para realizar el método son nueve: 1. graficar las
soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas
las restricciones en forma simultánea.
2. Las restricciones de no negatividad Xi>= 0 confían todos los valores
posibles.
3. El espacio encerrado por las restricciones restantes se determinan
sustituyendo en primer término <= por (=) para cada restricción, con lo cual
se produce la ecuación de una línea recta.
4. trazar cada línea recta en el plano y la región en cual se encuentra cada
restricción cuando se considera la desigualdad lo indica la dirección de la flecha
situada sobre la línea recta asociada.
5. Cada punto contenido o situado en la frontera del espacio de soluciones
satisfacen todas las restricciones y por consiguiente, representa un punto
factible.
6. Aunque hay un número infinito de puntos factibles en el espacio de
soluciones, la solución óptima puede determinarse al observar la dirección en la
cual aumenta la función objetivo.
7. 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.
Ejemplo.
Maximizar Z = 3X1 + 2X2 restricciones:
X1 + 2X2 <=6 (1)
2X1 + X2 <=8 (2)
-X1 + X2 <=1 (3)
X2 <= 2 (4)
X1 >= 0 (5)
X2 >= 0 (6)
Convirtiendo las restricciones a igualdad y representándolas gráficamente se
tiene:
X1 + 2X2 = 6 (1)
2X1 + X2 = 8 (2)
-X1 + X2 = 1 (3)
X2 = 2 (4)
X1 = 0 (5)
X2 = 0 (6)
Figura 1 Espacio de solución presentada con WinQsb
Figura 2 Determinación de solución
1.4 Método simplex
En la solución gráfica observamos que la solución óptima está asociada
siempre con un punto extremo del espacio de soluciones. El método simplex
está basado fundamentalmente en este concepto.
Careciendo de la ventaja visual asociada con la representación gráfica del
espacio de soluciones, el método simplex emplea un proceso iterativo que
principia en un punto extremo factible, normalmente el origen, y se desplaza
sistemáticamente de un punto extremo factible a otro, hasta que se llega por
último al punto óptimo.
Existen reglas que rigen la selección del siguiente punto extremo del método
simplex:
1. El siguiente punto extremo debe ser adyacente al actual.
2. La solución no puede regresar nunca a un punto extremo considerado con la
anterioridad.
El algoritmo simplex da inicio en el origen, que suele llamarse solución inicial.
Después se desplaza a un punto extremo adyacente. La elección específica de
uno a otro punto depende de los coeficientes de la función objetivo hasta
encontrar el punto óptimo.
Al aplicar la condición de optimidad a la tabla inicial seleccionamos a Xi como la
variable que entra. En este punto la variable que sale debe ser una de las
variables artificiales.
Los pasos del algoritmo simplex son (10):
1. Determinar una solución básica factible inicial.
2. Prueba de optimidad: determinar si la solución básica factible inicial es
óptima y sólo si todos los coeficientes de la ecuación son no negativos ( >= 0
). Si es así, el proceso termina; de otra manera se lleva a cabo otra
interacción para obtener la nueva solución básica factible inicial.
3. Condición de factibilidad.- Para todos los problemas de maximización y
minimización, variable que sale es la variable básica que tiene la razón más
pequeña (positiva). Una coincidencia se anula arbitrariamente.
4. Seleccionar las variables de holgura como las variables básicas de inicio.
5. Selecciona una variable que entra de entre las variables no básicas actuales
que, cuando se incrementan arriba de cero, pueden mejorar el valor de la
función objetivo. Si no existe la solución básica es la óptima, si existe pasar
al paso siguiente.
6. Realizar el paso iterativo.
a) Se determina la variable básica entrante mediante la elección de la variable
con el coeficiente negativo que tiene el valor mayor valor absoluto en la
ecuación. Se enmarca la columna correspondiente a este coeficiente y se le da
el nombre de columna pivote.
b) Se determina la variable básica que sale; para esta, se toma cada
coeficiente positivo (>0) de la columna enmarcada, se divide el lado derecho de
cada renglón entre estos coeficientes, se identifica la ecuación con el menor
cociente y se selecciona la variable básica para esta ecuación.
c) Se determina la nueva solución básica factible construyendo una nueva
tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene.
Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1,
se divide todo el renglón entre el número pivote, entonces
Renglón pivote nuevo = renglón pivote antiguo número
pivote
Para completar la primera iteración es necesario seguir usando la eliminación
de Gauss para obtener coeficientes de 0 para la nueva variable básica Xj en los
otros renglones, para realizar este cambio se utiliza la siguiente fórmula:
Renglón nuevo = renglón antiguo - ( coeficiente de la columna pivote X renglón
pivote nuevo)
Cuando el coeficiente es negativo se utiliza la fórmula:
Renglón nuevo = renglón antiguo + (coeficiente de la columna pivote X renglón
pivote nuevo)
TABLA SIMPLEX
como se capturaría la solución básica factible inicial en el siguiente ejemplo:
Sea:
Maximizar Z = 2X1+4X2 sujeto
a:
2X1+ X2<= 230
X1+ 2X2<= 250
X2<= 120 todas
las X1,X2>=0
BASE Z X1 X2 S1 S2 S3 SOLUCIÓN RAZÓN
Z 0 -2 -4 0 0 0 0 0
S1 0 2 1 1 0 0 230 230/1
S2 0 1 2 0 1 0 250 250/2
S3 0 0 1 0 0 1 120 120/1
Seleccione la variable que entra y la variable que sale de la base:
Entra X2 y sale S3, se desarrolla la nueva tabla solución y se continua el
proceso iterativo hasta encontrar la solución optima si es que está existe.
Tabla Óptima:
BASE Z X1 X2 S1 S2 S3 SOLUCIÓN RAZÓN
Z 0 0 0 0 2 0 500
S1 0 0 0 1 -2 3 90
X1 0 1 0 0 1 -2 10
X2 0 0 1 0 0 1 120
Solución: Z = $500
fabricando X1=10
X2=120
Sobrante de
S1 = 90
Tipo de solución: Optima Múltiple
1.5 Aplicaciones diversas de programación lineal.
Conceptos fundamentales
Programación lineal y método simplex:
Una vez se tiene un concepto general de lo que es la programación lineal, es
importante conocer la forma de actuación particular de los algoritmos que
resuelven programas lineales. De entre todos los algoritmos destaca por su
importancia histórica y práctica el método simplex. Dicho método fue
desarrollado por Dantzig en 1947, alcanzando un éxito inusitado en las
décadas posteriores con el desarrollo de los computadores. El conocimiento
básico de dicho método ayuda a la comprensión de las diferentes formas de
resolución de programas lineales. Dicho método puede ser estudiado en alguno
de los manuales que se presentan a continuación: Hillier y Liebermann (2001)
(Capítulos 4 y 5) o bien Winston (1994) (Capítulos 3 y 4). Por otra parte, el
estudio de aplicaciones de la Programación Lineal es exhaustivo en los textos
de Hillier, Hillier y Liebermann (2000); Eppen et al.(1998); o bien de Anderson,
Sweeney y Williams (2001).
Clasificación de las aplicaciones de PL:
La Programación Lineal presenta un gran número de aplicaciones en multitud
de ámbitos empresariales, industriales, de gestión y en general, de toma de
decisiones. En este mathblock tan sólo se hace una exposición sucinta de las
aplicaciones más clásicas. Sin embargo, se aconseja al lector la consulta de los
documentos de Internet siguientes:
[Link]
[Link]
En el primero se describen los problemas clásicos de mezclas y de la dieta,
mientras en el segundo se desarrolla un elenco de aplicaciones que sirven muy
bien para completar los casos aquí descritos. En otro orden de cosas, en el
presente mathblock se van a desarrollar campos de aplicación de la
programación lineal en los ámbitos siguientes: Marketing, Producción,
Asignació