Universidad Nacional Autónoma de México
Facultad de Estudios Superiores Cuautitlán
Ingeniería Industrial
Programación lineal
Investigación de operaciones
Ramírez Flores Oscar
#419062448
Manuel Jauregui Renault
1705
2022-I
Fecha de entrega:
Programación lineal
La programación lineal es, entonces, un proceso por el cual se maximizará una
función lineal. Es decir, una ecuación de primer grado, donde las variables están
elevadas a la potencia 1.
La Programación Lineal es un enfoque de solución de problemas elaborado para
ayudar a tomar decisiones. Es un modelo matemático con una función objetivo
lineal, un conjunto de restricciones lineales variables no negativas. En el
ambiente de negocios actual, pueden encontrarse gran cantidad de aplicaciones.
La función objetivo define la cantidad que se va a maximizar o minimizar en un
modelo de programación lineal.
Las restricciones limitan o reducen el grado en que puede perseguirse el
objetivo.
Las variables son las entradas controlables en el problema.
Para resolver un problema de programación lineal es recomendable seguir
ciertos pasos que son:
1. Definición del problema
2. Desarrollo de un modelo matemático y recolección de datos
• Identificación de las variables de decisión
• Identificación de los datos del problemas
• Identificación de la función objetivo
• Identificación de las restricciones
3. Resolución del modelo matemático
4. Validación, instrumentación y control de la solución
5. Modificación del modelo
Variables de decisión: Una cantidad cuyo valor se puede controlar y es
necesario determinar para solucionar un problema de decisión.
Función objetivo: Objetivo global de un problema de decisión expuesto en
forma matemática en términos de los datos y de las variables de decisión.
Restricciones: Es una limitación sobre los valores de las variables en un modelo
matemático típicamente impuesto por condiciones externas.
Ejemplo 1:
1.-Una fábrica produce televisores y computadoras
2.- Necesitan pasar en la sección de montaje de acabado que cuentan con 120 y
180 hrs disponibles
3.- Las computadoras necesitan de 3 hrs en ambas secciones
4.- Los televisores 3 horas en montaje y 4 en acabado
5.- La fábrica obtiene $300 por la producción de computadoras y $400 por los
televisores
¿Qué cantidad debe producir de cada uno para maximizar sus ganancias?
Primero obtenemos la función objetivo:
Z= 300x1 +400x2
Definimos restricciones
Montaje: 3x1+3x2<=120
Acabado: 3x1+6x2<=180
Sujeto a:
X1>= 0, x2<=0
VARIABLES DE HOLGURA
3x1+3x2+s1=120
3x1+6x2 +s2=180
CREAMOS LA TABLA SIMPLEX
z X1 X2 S1 S2 R
Z 1 -300 -400 0
S1 0 3 3 1 120
S1 0 3 5 1 180
La columna pivote será la fila pivote y dividimos la columna R/x2
R= 0, 40, 30
Y eligiendo la fila con menor cociente nos dará en la intersección el elemento
pivote
Ahora creamos nuestra segunda tabla simplex
Calculamos la fila entrante dividiendo la fila pivote entre el elemento pivote
z X1 X2 S1 S2 R
Z
S1
S1 0 0.5 1 0 .17 30
Calculamos las otras filas con esta formula:
FA-(PF*FN)
Fila anterior menos la multiplicación entre el pivote de la fila y la fila nueva
Y así con la otra fila
z X1 X2 S1 S2 R
Z 1 -100 0 0 66 12000
S1 0 1.5 0 1 -.5 30
X2 0 0.5 1 0 .17 30
Si la fila de la función objetivo se presenta un numero negativo, tendremos que
volver a aplicar el valor de encontrar la columna pivote, la fila pivote y hacer
una nueva tabla simplex hasta tener en positivos los valores.
z X1 X2 S1 S2 R
Z 1 0 0 66.67 33.34 14000
X1 0 1 0 .67 -.33 20
X2 0 0 1 -.33 .34 20
Resolvemos la función objetivo
Z=300(20)+400(20)=14000
La empresa deberá fabricar 20 unidades de tv y 20 de computadoras para
obtener la máxima ganancia de $14000
Ejercicio
Resuelva el siguiente problema mediante el simplex tabular:
Solución
Añadiendo al modelo las variables de holgura que corresponden:
Siendo el coste reducido de las variables no básicas:
Iteración 1 - Entra en la base X2 ya que tiene el coste reducido negativo, y de
todos los negativos, el
mayor en valor absoluto. Sale de la base:
Iteración 2 - Entra en la base X1 ya que tiene el coste reducido negativo, y de todos los negativos,
el mayor en valor absoluto. Sale de la base:
La solución hallada es óptima dado que ninguna variable puede entrar en la
base y mejorar la
solución actual, ya que el coste reducido de las variables no básicas es positivo
y el problema es de
maximización. La solución óptima:
X=27 X=11,5 z= 111,5
Ejercicio
Resuelva el siguiente problema mediante el simplex tabular:
Solución
Añadiendo al modelo las variables de holgura que corresponden:
Siendo el coste reducido de las variables no básicas:
Iteración 1 - Entra en la base X1 ya que tiene el coste reducido negativo, y de
todos los negativos, el mayor en valor absoluto. Sale de la base:
La solución hallada es óptima dado que ninguna variable puede entrar en la
base y mejorar la solución actual, ya que el coste reducido de las variables no
básicas es positivo y el problema es de maximización. La solución óptima:
Método Dual Simplex
l Método Simplex Dual nos ofrece una alternativa algorítmica para abordar la
resolución de modelos de Programación Lineal. En particular este método se
puede utilizar cuando luego de llevar a la forma estándar un modelo de
Programación Lineal no se dispone de una solución básica factible inicial con
la cual se pueda dar inicio a las iteraciones del algoritmo. En este contexto a
continuación se presenta un ejemplo con los detalles de la aplicación de este
procedimiento.
Ejemplo del Método Simplex Dual
Consideremos el siguiente problema para ilustrar sobre la aplicación del
Método Simplex Dual:
Para llevar el problema anterior a la forma estándar se requiere agregar 2
variables de exceso no negativas para la restricción 1 y 2, que llamaremos
respectivamente X4 y X5. De esta forma el problema en su formato estándar
queda definido por:
Luego construimos la tabla inicial del Método Simplex:
¿Cómo continuar con las iteraciones del Método Simplex?. Antes de ello es
necesario disponer de una solución básica factible inicial. En este contexto si
quisiéramos usar X4 y X5 como variables básicas (y en consecuencia X1, X2 y
X3 como variables no básicas) se requiere que X4 y X5 sean mayores o iguales
a cero, sin embargo, sus coeficientes en las respectivas filas son negativos y por
tanto no se dispone de la identidad (matriz con “1” como diagonal y el resto de
coeficientes igual a cero).
En consecuencia para formar la identidad podemos multiplicar por “-1” la fila
1 y 2, obteniendo lo siguiente:
En la tabla anterior se tiene una solución básica (infactible en las variables
primales), pero al tener costos reducidos no negativos esto define una solución
básica factible en el dual.
Ahora X4 y X5 son variables básicas y adoptan los valores de -1 y -3/2,
respectivamente, lo que claramente no satisface las condiciones de no
negatividad para las variables de decisión, es decir, no corresponde a una
solución básica factible.
Sin embargo, en esta instancia podemos aplicar el Método Simplex Dual como
alternativa de resolución. Para ello seleccionaremos una variable que deje la
base y adoptaremos como criterio de selección aquella variable básica asociada
al lado derecho “más negativo” (con esto se busca favorecer la rapidez de
convergencia).
En el ejemplo dicha variable es X5. Luego para determinar que variable entra a
la base realizamos un mínimo cuociente entre el negativo del costo reducido de
las variables no básicas y las entradas estrictamente menores a cero para las
variables no básicas en la fila 2 (fila asociada al lado derecho más negativo).
Es decir: Min{-160/-2; -120/-2; -280/-2}=60 ==> el cuociente mínimo se
alcanza en la segunda columna asociada a la variable no básica X2, por tanto
dicha variable entra a la base.
En cada iteración del Método Simplex Dual se escoge un lado derecho con valor
negativo, identificando la respectiva variable básica primal, quien deja la base.
Finalmente se realiza una iteración realizando las operaciones filas que sean
necesarias, de modo de ingresar X2 a la base al mismo tiempo que X5 deja la
base. Los resultados serían:
Notar que ahora las variables básicas son X4 y X2 donde sólo X4=-1/4 lo que
no satisface la condición de ser una solución básica factible. Por lo tanto
realizamos una nueva iteración, en este caso sacando de la base a la
variable X4 y calculamos el mínimo cuociente: Min{-40/-1; -160/-3; -60/-
1/2}=40 ==> el cuociente mínimo está en la primera columna por tanto la
variable X1 entra a la base.
En consecuencia se actualiza la tabla quedando lo siguiente:
Las variables básicas ahora son X1=1/4 y X2=1/2 (que cumplen las condiciones
de no negatividad). Adicionalmente el costo reducido de las variables no básicas
también es mayor o igual a cero, por tanto estamos frente a la solución óptima
del problema.
Se puede reconocer adicionalmente que el valor óptimo es V(P)=100 que se
obtendría al evaluar la solución óptima del problema en la función objetivo, sin
embargo, en el procedimiento dicho valor se obtiene con signo cambiado.
El ejemplo anterior nos permitió apreciar cómo a través del Método Simplex
Dual se puede abordar la resolución de un modelo de Programación Lineal que
luego de ser llevado a la forma estándar no provee una solución básica factible
inicial.
Cabe destacar que el Método Simplex Dual que no es la única alternativa
algorítmica a la cual podemos recurrir para resolver el problema propuesto. Por
ejemplo, podríamos haber alcanzado idénticos resultados aplicando el Método
Simplex de 2 Fases con algo más de trabajo.
Modelos de transporte
El problema del transporte o distribución es un problema de redes especial en
programación lineal que se funda en la necesidad de llevar unidades de un punto
específico llamado Fuente u Origen hacia otro punto específico llamado
Destino. Los problemas de transporte o distribución son uno de los más
aplicados en la economía actual, dejando como es de prever múltiples casos de
éxito a escala global que estimulan la aprehensión de los mismos. La función
objetivo consiste en reducir al mínimo el costo de transporte y satisfacer los
requerimientos de las bodegas dentro de las limitaciones de la capacidad de las
fábricas.
Se han desarrollado varios métodos para resolver un problema de transporte,
dentro de los cuales, los comunes son:
• Mínimos
• Vogel
• Prueba de Optimidad
• Esquina Noroeste
La meta de un modelo de transporte es minimizar el costo total de un envío de
un producto desde los puntos de existencia hasta los puntos de demanda bajo
las siguientes condiciones:
• La función objetivo y las restricciones deben ser lineales. Las mercancías para
distribuir deben ser uniformes.
• La suma de la capacidad de todos los orígenes deben ser iguales a la capacidad
de los destinos; es decir oferta igual a demanda.
Identificación de las restricciones:
• El embarque total de cada planta no se debe exceder de su capacidad.
• El embarque total recibido por cada tienda al por menor debe satisfacer se
demanda.
Ejemplo:
A continuación, se dan las capacidades de 3 fábricas y las necesidades de 3
almacenes y los costos unitarios de transporte.
• La tabla que se utiliza normalmente es la que aparece a continuación observe
que es una disposición matricial de filas y columnas en las que aparecen los
orígenes en las filas y los destinos en las columnas, además usted puede ver que
los costos de envío se encuentran en los recuadros pequeños, así como las
respectivas ofertas y demandas.
Método de la esquina noroeste
Es uno de los métodos más fácil para determinar una solución básica factible
inicial. Este también considerado por ser el menos probable para dar una buena
solución de “bajo costo” porque ignora la magnitud relativa de los costos.
Pasos para desarrollar este método: 1. Seleccionar la celda de la esquina
noroeste (esquina superior izquierda). 2. Haga el más grande envío como pueda
en la esquina de la celda de la esquina noroeste, esta operación agotará
completamente la disponibilidad de suministros en un origen a los
requerimientos de demanda en un destino. A este procedimiento o paso se le
llama con frecuencia saturar. 3. Corrija los números del suministro y
requerimiento para reflejar lo que va quedando de suministro y vuelva al paso
uno.
Reglas para el desarrollo del método esquina noroeste: 1. Los envíos son
indicadores dentro de cada celda. 2. Los suministros y requerimientos que
quedan pueden ser registrados a la derecha de los números originales. 3. Las
filas correspondientes a los orígenes pueden ser eliminadas o señaladas, después
de que sus requerimientos estén completamente llenos.
Tabla esquina noroeste
Costo Total = (400*2)+(100*3)+(600*1)+(200*5)+(1000*1) Costo Total =
800+300+600+1000+1000 Costo Total = $ 3.700
Método del costo mínimo
Método del costo mínimo
Costo Total = (400*2)+(100*6)+(700*1)+(100*5)+(1000*1)
Costo Total = 800+600+700+500+1000
Costo Total = $ 3.600
Método de Aproximación de Vogel
Este método es considerado el más cercano a una solución óptima para evaluar
una solución factible de bajo costo. Procedimiento
• Se restan los dos valores mínimos de cada columna e igualmente en las filas,
• Se toma como punto de partida el valor mínimo de la columna o fila en donde
se encuentra ubicado el mayor valor obtenido en la resta inicial(mayor
diferencia),
• Se repite los pasos anteriores con las filas y columnas que aún quedan sin
saturar hasta que se asignen todas las cantidades requeridas para satisfacer la
demanda de acuerdo con la oferta dada,
• Se determina el costo y se verifica que la tabla no sea degenerada,
• Se aplica la técnica del salto de la piedra para buscar la solución óptima en
caso de poder hacerlo.
Modelos de distribución
Con modelos de logística de distribución nos referimos al tipo de infraestructura
que crea una entidad para hacer llegar sus productos hasta el mercado. Hay que
tener en cuenta que una compañía puede optar de forma simultánea por varios
de estos modelos, compaginándolos o apostando por unos u otros en
determinados lugares, clientes, etc.
Modelo descentralizado
Este modelo se basa en las existencias de almacenes más cercanos a los clientes.
La mercancía que ya ha sido fabricada pasa desde el almacén original -o desde
el final del proceso de fabricación- a diversos almacenes de proximidad o
delegaciones. Esto permite estar más cerca de los clientes finales, lo que puede
permitir que las entregas se realicen un menor tiempo. El principal enemigo de
este modelo es el alto coste de contar con diversas infraestructuras.
Es un modelo al que también se recurre con frecuencia y ya casi por necesidad
con las multinacionales. Por ejemplo, Amazon sería prácticamente impensable
con un único almacén central.
Modelo centralizado
Este modelo de logística de distribución, en vez de recurrir a un mayor número
de almacenes confía en el transporte para optimizar sus tránsitos y sus costes.
La mejora en los tiempos de entrega y la agilidad de respuesta del transporte ha
ido facilitando la presencia de estos modelos. Por ejemplo, el desarrollo de los
envíos exprés de palés en España, como nuestra red de Palibex, ha hecho que
muchas compañías puedan distribuir sus productos con rapidez y seguridad
desde un único almacén.
En este caso es el transportista el que ha de asegurarse contar con una red
amplia. Esta capilaridad es la que tomará el lugar de los almacenes de
proximidad o de las delegaciones que veíamos en el modelo descentralizado.
Modelo cross-docking
El modelo cross-docking podríamos definirlo como un modelo descentralizado,
pero en el que la mercancía no llega a almacenarse. El cross-docking consiste
en la reexpedición de la mercancía en un máximo de 24 horas desde la llegada
de la mercancía a la plataforma de cross-docking.
Consolidación
La consolidación consiste en reunir en el centro de consolidación la mercancía
de distintos proveedores para, desde allí, realizar los envíos hacia los distintos
clientes. El objetivo de esto es ser capaces de utilizar vehículos más grandes,
buscando optimizar los tránsitos y sus costes.
Referencias
https://www.youtube.com/watch?v=QcISx32Rmb0
https://sites.google.com/site/investigaciondeoperacionescun/programacion-
lineal
https://economipedia.com/definiciones/programacion-lineal.html
https://es.slideshare.net/leonardohlanda/modelos-de-transporte-63391582
https://www.gestiondeoperaciones.net/programacion_lineal/como-resolver-un-
modelo-de-programacion-lineal-con-el-metodo-simplex-dual/
https://www.omniascience.com/books/index.php/scholar/catalog/download/18
/72/94-1?inline=1
https://www.transgesa.com/blog/modelos-logistica-distribucion/
