REPÚBLICA BOLIVARIANA DE VENEZUELA
UNIVERSIDAD NACIONAL EXPERIMENTAL
“RAFAEL MARÍA BARALT”
VICERRECTORADO ACADÉMICO
PROGRAMA INGENIERÍA Y TECNOLOGÍA
PROGRAMA NACIONAL DE FORMACIÓN EN INFORMÁTICA
SISTEMA PARA EL CONTROL DE REGISTRO DE VACUNAS
EN EL AMBULATORIO DELICIAS
AUTORES:
T.M. Bozo Lauribeth, T.M. Gonzalez Miguel, T.M. Lopez Rafael, T.M. Ortiz José
ASESORA:
Lcda. Ana Capielo
Cabimas, de 2016
Cabimas, agosto de 2016
• Esquema
• Introducción
• Modelos de Programación Lineal
• Solución gráfica de problemas de dos dimensiones
• Método simplex de Resolución y simplex dual
• Conclusión
• Bibliografías
Introducción
Iniciarse en la técnica de programación lineal con el aspecto más importante del
método científico: la representación o modelo en formulación matemática lineal de
algunos problemas elegidos, los agrupados en "clásicos"; también debe aprender
los conceptos teóricos fundamentales utilizando la metodología gráfica en sólo dos
variables.
Modelo de programación lineal general.
El modelo de PL es una representación simbólica (abstracción) de la realidad que
se estudia, se forma con expresiones lógicas matemáticas conteniendo términos
que significan contribuciones: a la utilidad (con máximo), al costo (con mínimo), al
consumo de recurso (disponible con desigualdad <=), al recurso requerido (con
desigualdad >=), recurso especificado (con igual = ). Contiene las siguientes
cuatro partes:
1a parte
Definición con el significado cuantitativo de las variables de decisión
(controlables).
2a parte
Función económica u objetivo a optimizar (máximo o bien mínimo):
3a parte
Sujeta a restricciones:
4a parte
Condición de no negativo a variables:
PROPIEDADES DEL MODELO DE PROGRAMACIÓN LINEAL
Para que un modelo de PL sea válido, debe cumplir las propiedades siguientes:
Proporcionalidad.-Significa que la contribución al valor de la función objetivo y el
consumo o requerimiento de los recursos utilizados, son proporcionales al valor de
cada variable de decisión. Así el término 4X1 es proporcional, porque contribuye al
valor de la función Z con 4, 8, 12, etc. para los valores 1, 2, 3, etc.,
respectivamente, de X1. Se puede observar el aumento constante y proporcional
de 4 conforme crece el valor de X1. En contraste, el término no lineal 4X12,
contribuye con 4, 16, 36, etc., para los mismos valores 1, 2, 3, etc.,
respectivamente, de la variable X1; Aquí se observa que el aumento en la
contribución no es constante y por lo tanto no hay proporcionalidad.
Aditividad.- Significa que se puede valorar la función objetivo Z, así como también
los recursos utilizados, sumando las contribuciones de cada uno de los términos
que intervienen en la función Z y en las restricciones.
Divisibilidad.- Significa que las variables de decisión son continuas y por lo tanto
son aceptados valores no enteros para ellas. La hipótesis de divisibilidad más la
restricción de no negatividad, significa que las variables de decisión pueden tener
cualquier valor que sea positivo o por lo menos igual a cero.
Certidumbre.- Significa que los parámetros o constantes son estimados con
certeza, o sea, no interviene una función de probabilidad para obtenerlos
El modelo de programación lineal es un caso especial de la programación
matemática, pues debe cumplir que, tanto la función objetivo como todas las
funciones de restricción, sean lineales.
APLICACIONES TÍPICAS DE LA PROGRAMACIÓN LINEAL
Aparentemente, las estructuras de organización complejas propias de la sociedad
moderna han reconocido interesantes problemas de optimización tales como la
manera más eficiente de manejar la economía de un país o también la mezcla de
ingredientes de un fertilizante para satisfacer las especificaciones agrícolas a
costo mínimo. Ambos problemas utilizan el modelo de programación lineal (PL),
para optimizar una función lineal condicionada a restricciones lineales, que
essencillo en su estructura matemática, pero poderoso por su gran adaptación a
una amplia variedad de problemas.
La programación lineal es una técnica matemática de resolución de problemas, su
desarrollo representa una ayuda a los administradores para tomar decisiones en la
asignación de recursos. A continuación aparecen algunas aplicaciones típicas de
la PL:
Un fabricante desea desarrollar un programa de asignación en producción y una
política de inventario que satisfagan la demanda de ventas de periodos futuros.
Así se podría cumplir la demanda con mínimo costo total de producción y de
inventario.
Un analista financiero debe seleccionar una cartera de inversiones a partir de una
diversidad de alternativas en acciones y bonos. Se debe establecer la cartera
que maximice el rendimiento sobre la inversión asignada.
Un administrador de mercadotecnia desea determinar la mejor manera
de asignar un presupuesto de publicidad como radio, televisión, periódicos y
revistas. Al gerente le gustaría determinar la combinación de medios
que maximice la efectividad de la publicidad.
Una empresa tiene almacenes en varias. ubicaciones en todo el país. Para un
conjunto de demandas de sus productos por parte de sus clientes, la empresa
desearía determinar cuánto debe asignar en embarques a cada uno de los
almacenes y a cada cliente, de manera que los costos totales de transporte
resulten mínimos.
Estas aplicaciones representan unas cuantas situaciones en las que se ha
utilizado con éxito la programación lineal, pero ilustran su potencial en la solución
de problemas. Un estudio detallado revela las características comunes de ellas.
En el ejemplo 1, el fabricante desea minimizar costos; en el 2, el analista
financiero desea maximizar el rendimiento sobre la inversión; en el 3, el gerente de
mercadotecnia desea maximizar la efectividad de la publicidad, y en el ejemplo 4,
la empresa desea minimizar los costos totales de transporte. En todos los
problemas de programación lineal, el objetivo es el máximo o bien el mínimo de
alguna cantidad en la acción de asignar recursos.
Los problemas de programación lineal se caracterizan, además, por las
condiciones impuestas o restricciones de recursos, que limitan el grado en que se
puede cumplir algún objetivo. En el ejemplo 1, el fabricante está limitado por
restricciones que requieren que la demanda de producto quede satisfecha y por
restricciones respecto a la capacidad de producción. El problema de la cartera del
analista financiero está limitado por la cantidad total de fondos de inversión
disponibles y las cantidades máximas que se pueden invertir en cada acción o
bono. La decisión en la selección de medios del gerente de mercadotecnia, está
restringida por un presupuesto de publicidad fijo y por la disponibilidad de los
varios medios. En el problema de transportación, el programa de embarques de
costo mínimo está restringido al suministro de productos disponibles en cada
almacén. La diversidad de condiciones mencionadas, es parte de lo que puede
esperar aquel que decida enfrentar un problema, pues las restricciones son otra
característica general en todo problema de programación lineal.
Método gráfico para resolver modelos de programación lineal con solo dos
variables.
En esta sección interesa hacer análogos geométricos, esto es, gráficas de
funciones lineales que contiene el modelo matemático de programación lineal
obtenido en la formulación del problema que se analiza. Dicho modelo puede
contener expresiones tanto en forma de ecuaciones ( = ) como en desigualdades (
<= ó >= ), cada una de ellas corresponde a un gráfico en la analogía geométrica.
Primero considere la infinidad de puntos que constituyen en conjunto el plano y los
cuatro cuadrantes convencionalmente aceptados, para dividirlo en zonas
caracterizadas por la combinación de signo que se puede dar, a los valores
medidos con números reales. Para lograr los cuadrantes en el plano se utilizan los
ejes cartesianos con escala de medición de valores de las variables del problema;
por ejemplo, se puede asignar el eje horizontal de abscisas para la medición de
valores de la variable X1; también se puede asignar el eje vertical de ordenadas,
para la medición de valores de la variable X2. La localización de cualquier punto en
este espacio plano requiere de una distancia horizontal (X 1) y de una distancia
vertical (X2) denotado como par ordenado o vector (X1, X2). Un punto sobre el eje
X1 corresponde a X2=0 y un punto sobre el eje X2 corresponde a X1=0, que son las
ecuaciones respectivas de los ejes horizontal y vertical. Dichos ejes se cruzan en
el punto (X1, X2) = (0, 0), el cual se conoce como origen.
Si la ecuación tiene sólo dos variables, el gráfico de la misma sobre el plano es
una línea recta, es decir, se requiere un espacio de dos dimensiones, la horizontal
y la vertical, para graficar tal ecuación; pero la representación geométrica de una
ecuación en tres variables, requiere un espacio de tres dimensiones. En tal caso, a
los ejes X1 y X2, se les agrega un tercer eje X3 como tercera dimensión, que pasa
por el origen hacia el observador.
Método simplex de Resolución y simplex dual.
El método simplex dual resulta ser una estrategia algoritmica eficiente cuando
luego de llevar un modelo de programación lineal a su forma estándar, la
aplicación del método simplex no es inmediata o más bien compleja, por ejemplo,
puede requerir la utilización del método simplex de 2 fases.
Una aplicación típica del método simplex dual es en la resolución de problemas
con una función objetivo de minimización, con restricciones del tipo mayor o igual
y donde las variables de decisión son mayores o iguales a cero.
Ejemplo Simplex Dual
Considere el siguiente modelo de Programación Lineal:
Paso 1: Se lleva el modelo a su forma estándar. En nuestro ejemplo esto se logra
agregando variables de exceso en cada una de las restricciones (3 primeras: S1,
S2, S3, respectivamente). Luego, se multiplica cada fila de las restricciones por -1
de modo de disponer una solución básica inicial (infactible) en las variables de
exceso S1, S2 y S3. De esta forma se obtiene la siguiente tabla inicial.
A B C S1 S2 S3
-
-15 -2 -1 1 0 0
200
-
-7,5 -3 -1 0 1 0
150
-
-5 -2 -1 0 0 1
120
315 110 50 0 0 0 0
Paso 2: Se selecciona el lado derecho "más negativo" lo cual indicará cuál de las
actuales variables básicas deberá abandonar la base. En el ejemplo el lado
derecho más negativo se encuentra en la primera fila, por tanto S1 deja la base.
Para determinar cual de las actuales variables no básicas (A, B, C) entrará a la
base se busca el mínimo de {-Yj/aij} donde aij es el coeficiente de la respectiva
variable no básica en la fija i (del lado derecho más negativo, marcado en verde) y
donde Yj es el costo reducido de la respectiva variable no básica. De esta forma
se obtiene: Min {-315/-15, -110/-2, -50/-1} = 21, donde el pivote (marcado en rojo)
se encuentra al hacer el primer cuociente, por tanto A entra a la base.
Paso 3: Se actualiza la tabla anterior siguiendo un procedimiento similar al
utilizado en el Método Simplex. En el ejemplo se debe dejar a la variable A como
básica y S1 como no básica. La tabla que resulta es la siguiente:
A B C S1 S2 S3
-
1 2/15 1/15 0 0 40/3
1/15
0 -2 -1/2 -1/2 1 0 -50
-
0 -4/3 -2/3 -1/3 0 1
160/3
-
0 68 29 21 0 0
4.200
Paso 4: Continuar las iteraciones y siguiendo el mismo procedimiento hasta
disponer de una solución básica factible. Luego de unas iteraciones se obtiene la
siguiente tabla final:
A B C S1 S2 S3
-
1 0 0 0 1/10 8
1/10
0 1 0 1/4 -1 3/4 10
0 0 1 0 2 -3 60
-
0 0 0 4 10 36
6.620
La solución óptima es A=8, B=10, C=60 (marcado en verde) con valor
óptimo V(P)=6.620 (marcado en rojo - se obtiene con signo cambiado). También
es interesante notar que los costos reducidos de las variables artificiales S1, S2 y
S3 (marcado en amarillo), corresponde a la solución óptima del modelo
presentado en el tutorial de solver, esto dado que dicho modelo resulta ser
elproblema dual de nuestro ejemplo.
Conclusión
La programación lineal es una técnica poderosa para tratar problemas de asignación de
recursos escasos entre actividades que compiten, al igual que otros problemas cuya
formulación matemática es parecida. Se ha convertido en una herramienta estándar de gran
importancia para muchas organizaciones industriales y de negocios. Aún más, casi cualquier
organización social tiene el problema de asignar recursos en algún contexto y cada vez mayor
el reconocimiento de la aplicabilidad tan amplia de esta técnica.
Bibliografías
http://investigaciondeoperacionesind331.blogspot.com/p/programacion-
lineal_23.html
http://metodoscuantitativo2.galeon.com/
http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-
industrial/investigaci%C3%B3n-de-operaciones/programaci%C3%B3n-lineal/
antt
