T1 - U3 - 18300196 - Maria Dolores Botello Lastra

INSTITUTO TECNOLÓGICO DE
VILLAHERMOSA
DEPARTAMENTO DE CIENCIAS DE LA TIERRA

MATERIA:
MODELOS DE OPTIMIZACIÓN DE RECURSOS
UNIDAD III
TEMA:
ALGORITMOS ESPECIALES DE PROGRAMACIÓN

LINEAL
AUTOR:
MARíA DOLORES BOTELLO LASTRA
CATEDRÁTICO:
ING. JUAN SOLíS HERNÁNDEZ
VILLAHERMOSA, TABASCO 22 DE NOVIEMBRE DE 2021

ÍNDICE
INTRODUCCIÓN .............................................................................................................................. 3
MARCO TEÓRICO........................................................................................................................... 4
CONCLUSIÓN ................................................................................................................................ 11
RECOMENDACIONES.................................................................................................................. 12
GLOSARIO DE TÉRMINOS ......................................................................................................... 13
ANEXOS .......................................................................................................................................... 14
BIBLIOGRAFÍA ............................................................................................................................... 16
INTRODUCCIÓN
La programación lineal es un conjunto de técnicas racionales de análisis y de

resolución de problemas que tiene por objeto ayudar a los responsables en las
decisiones sobre asuntos en los que interviene un gran número de variables;
consiste en optimizar (minimizar o maximizar) una función lineal, denominada
función objetivo, de tal forma que las variables de dicha función estén sujetas a una
serie de restricciones que expresamos mediante un sistema de inecuaciones
lineales.
En el desarrollo de este trabajo vamos a desglosar uno de los casos especiales de

la programación lineal el problema de transporte, que en su modelo más elemental
podemos decir que surge cuando se necesita un modelo costo-efectividad que
permita transportar bienes de un lugar de origen a un destino que necesita aquellos
bienes, con algunas restricciones en la cantidad de insumos que se puede
transportar.
MARCO TEÓRICO
Características de los algoritmos de P. L.

¿Qué es un algoritmo?
Un algoritmo es un conjunto ordenado y finito de pasos o instrucciones que permite

realizar una actividad mediante pasos sucesivos sin generar duda a quien deba
realizar dicha actividad.
Algoritmos Especiales
Son diseñados para problemas de programación lineal, son problemas enunciados
con ecuaciones lineales, con una función objetivo y una o más funciones
restricciones para lograr la optimización de la función objetivo que se analiza.
Son implementados en la microeconomía y la administración de empresas, ya sea

para aumentar al máximo los ingresos o reducir al mínimo los costos de un
sistema de producción.
Problema Del Transporte

El objetivo del modelo es
minimizar el costo de
transporte total al mismo
tiempo que se satisfacen
las restricciones de la
oferta y la demanda.
La manera más fácil de
reconocer un problema de
transporte es por su
estructura "de-hacia": de
un origen hacia un destino,
de una fuente hacia un usuario. Se conocen las fuentes y los destinos, las
capacidades y demandas y los costos de cada trayectoria. Debe haber una
combinación óptima que minimice el costo (o maximice la ganancia). La dificultad
está en el gran número de combinaciones posibles. La estructura especial del
problema de transporte permite una representación compacta del problema
utilizando el formato tabla de transporte.
Para que un problema pueda ser resuelto por el método del transporte debe cumplir:
1) La función objetivo y las restricciones deben ser lineales.
2) El total de unidades que salen en origen debe ser igual al total de unidades que
entran en destino.
Planteamiento Del Problema
(Ejemplo Práctico)
Una empresa debe planificar la producción de un artículo para los 4 trimestres del
próximo año. Puede estimar la demanda en las siguientes unidades: 200, 150, 200
y 100 en cada uno de los trimestres. La capacidad de producción está limitada a
150 unidades en cada trimestre. Las demandas de un trimestre no se pueden
satisfacer en trimestres posteriores. El coste unitario de producción es de 2
unidades, pero en el caso de que haya almacenamiento se incrementa en 0.5
unidades en cada periodo por cada unidad almacenada.
Consideramos que tanto los orígenes como los destinos son los 4 trimestres.
Definimos xij, i = 1, . . ., 4, j = 1, . . ., 4, como el número de unidades que deben
producirse en el trimestre i para satisfacer la demanda del trimestre j.
• Oferta de los orígenes: 150, 150, 150, 150.
• Demanda de los destinos: 200, 150, 200, 100.
• El coste de producción cij = 2 si i = j, i, j = 1, . . ., 4
• El coste cij = coste de producción + coste de almacenamiento si i < j. Por ejemplo,

c12 = 2.5, c13 =3. De la misma forma se calculan el resto de costes.
• Si i > j asignamos a cij un valor M suficientemente grande para evitar que xij sea
básica.
La forma matricial cuyo objetivo es minimizar es la siguiente:

El problema de asignación
El problema de asignación consiste en encontrar la forma de asignar ciertos

recursos disponibles (máquinas o personas) para la realización de determinadas
tareas al menor coste, suponiendo que cada recurso se destina a una sola tarea, y
que cada tarea es ejecutada por uno solo de los recursos.
Los problemas de asignación presentan una estructura similar a los de transporte,

pero con dos diferencias: asocian igual número de orígenes con igual número de
demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en
cada destino. La restricción importante para cada agente es que será asignado a
una sola tarea.
Se dice que un problema de asignación se encuentra balanceado, si los recursos

totales son iguales a las demandas totales. En caso contrario se dice que no está
balanceado el problema. Además, en el modelo, m = n (obtener una matriz
cuadrada), en donde m número de renglones y n es número de columnas. Para
lograr que el modelo este balanceado se pueden agregar trabajadores/tareas
ficticias con costos de cero.
A continuación, presentaremos un ejemplo que muestra la aplicación del Método

Húngaro que nos permite decidir la asignación de trabajadores a puestos de trabajo.
Ejemplo:
Un equipo de 3 ingenieros debe ser asignado para la realización de 3 tareas, donde

cada ingeniero debe hacer una tarea. Se requiere encontrar la asignación de costo
mínimo para lo cual se dispone de los costos asociados a que el ingeniero i realice
la tarea j. Por ejemplo, representa el costo correspondiente a que el ingeniero 1
asuma la tarea 1.
1. identificar el valor mínimo de cada fila. En el caso de la fila 1 dicho valor es
$9 siendo el costo de que el ingeniero realice la tarea
se resta el mínimo de cada fila a cada uno de los valores de la fila respectiva,
para obtener la matriz reducida:
2. Se produce los mínimos de cada columna según se observa en la tabla

anterior. Al restar esos valores de las columnas respectivas se obtiene la
siguiente matriz reducida:
Las celdas con valor cero y color azul son la solución óptima. En
consecuencia, el ingeniero 1 realiza la tarea 2, el ingeniero 2 asuma la tarea
1 y el ingeniero 3 la tarea 3. Cada ingeniero realiza exactamente una tarea y
el costo total de dicha asignación (valor óptimo) es de: $9 + $10 + $8 = $27.
Ejemplos de problemas prácticos aplicados a la ingeniería civil
1. Una constructora construye casas para a tres clientes, y cada uno

requiere 30 bultos de cemento para efectuar sus obras y tienen que cubrir
la demanda. La compañía tiene dos almacenes. El almacén 1 tiene 40
unidades disponibles y el almacén 2 tiene 30 disponibles. Los costos de
enviar una unidad desde el almacén al cliente se muestran a continuación.
Hay una penalización por cada unidad de demanda no suministrada al
cliente: cliente 1 se incurre en un costo de penalización de $90, con el
cliente 2 $80 y con el cliente 3 $100. Plantear los tres modelos
equilibrados.
Modelo de la red:
Modelo de Programación Lineal:

Xij: Unidades de bienes suministrados del almacén “i” de la compañía al cliente “j”.
Yj: Unidades de bienes que no se suministran a la compañía “j”.
Minimizar Z = 15x11 + 35x12 + 25x13 + 10x21+ 50x22+ 40x23 + 90y1 + 80y2 +
110y3
Sujeto a:
x11 + x21 + y1 = 30
x11 + x12 + x13 = 40
x12 + x22 + y2 = 30
x21 + x22 + x23 = 30
x13 + x23 + y3 = 30
y1 + y2 + y3 = 20
xij ≥ 0; xij ϵ Ƶ
Tabla de Transporte:
2. VIGAC fabrica tres tipos vigas de acero en diferentes plantas. El tiempo

requerido para fabricar una tonelada de acero (sin importar el tipo) y los
costos en cada planta se ilustran en la siguiente tabla. Cada semana debe
producirse 100 toneladas de cada tipo de acero (1,2 y 3). Cada planta
está abierta 40 hrs por semana. Plantear los tres modelos.
MODELO DE RED.
(Se plantea el modelo de red DESEQUILIBRADO.)
MODELO DE PROGRAMACIÓN LINEAL.
Se plantea el modelo de programación lineal DESEQUILIBRADO.
MODELO TABLA DE TRANSPORTE.

Se plantea el modelo de tabla de transporte EQUILIBRADA.
CONCLUSIÓN
En la actualidad la gran mayoría de las industrias de cualquier índole utilizan este

tipo de modelos como solución práctica a problemas de costo- tiempo para
maximizar las ganancias de la empresa y por ende minimizar las perdidas, es así
como nos percatamos de la importancia de la programación lineal y su
implementación ya que los problemas se describen fácilmente a través de los
modelos lineales. La salida generada por el programa que resuelve el modelo de
programación lineal entrega información útil para responder nuevas condiciones. Es
una herramienta que facilitara las mejoras más óptimas y seguras en una empresa
de cualquier tipo.
RECOMENDACIONES
 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.
 Los análisis de dualidad y sensibilidad en los modelos de transporte

resultan ser bastante interesantes, pues pueden llegar a determinar
aumentos de capacidad en las fuentes si el precio sombra de las rutas en
relación a ellas lo justifica.
 El método del transporte de la programación lineal, no es como la

metodología de tablas y gráficos (de ensayo y error), proporciona un plan
óptimo para minimizar los costes.
 Todos los costes están relacionados linealmente con la cantidad de bienes

producidos, es decir, un cambio en el volumen de bienes genera un cambio
proporcional en los costes.
GLOSARIO DE TÉRMINOS
 ALGORITMO: Es la representación gráfica de una

sucesión lógica de operaciones o pasos que conducen a la solución de un
problema o a la producción de un bien o a la prestación de un servicio.
 COSTES: Cantidad de dinero que cuesta una cosa.
 DECISIÓN: Un conjunto de valores numéricos asignados a las variables de

decisión.
 DESTINO: Localidad en la que hay demanda de materiales en un problema

de transportes.
 FUNCIÓN OBJETIVO: Todo programa lineal que tiene una función objetivo
que representa la meta que va a ser maximizada o minimizada.
 OPTIMIZAR: Es un concepto teórico (es decir matemático), en cuanto se

opone al concepto del mundo real. Una decisión óptima o mejor producida
por un modelo, significa que hay grandes esperanzas de que sea una buena
decisión para el problema real puede ser maximizar o minimizar.
 DECISIÓN ÓPTIMA: Una decisión factible que optimiza la función objetivo.
 RESTRICCIÓN: Desigualdad matemática (desigualdad restringida) o

igualdad (restringida) que debe ser satisfecha por las variables del modelo.
 SOLUCIÓN ÓPTIMA: Punto de una región factible que maximiza o minimiza

la función objetivo.
 MINIMIZAR: Reducción de la cantidad de algo.
 MAXIMIZAR: Desarrollar al máximo una cosa material o inmaterial.
 BALANCEADO: Igualar, equilibrar.

ANEXOS
MÉTODO DE TRANSPORTE O DISTRIBUCIÓN

BIBLIOGRAFÍA
 Arreola Risa J., y Arreola Risa, A. “Programación Lineal”. Una

Introducción a la toma de decisiones cuantitativas”. Edit. Thomson.
México, 2003.
 Concepción Maroto, Javier Alcaraz Soria, Rubén Ruiz García.
“Investigación Operativa: Modelos y Técnicas de Optimización”,
Edición: Valencia, 2002, ISBN 9788497052399
 Hillier y Lieberman. “Investigación de Operaciones”. 8ª. Edición.
Edit. Mac GrawHill. México. D. F., 2008.

T1 - U3 - 18300196 - Maria Dolores Botello Lastra

Cargado por

Copyright:

Formatos disponibles

T1 - U3 - 18300196 - Maria Dolores Botello Lastra

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

T1 - U3 - 18300196 - Maria Dolores Botello Lastra

Cargado por

Copyright:

Formatos disponibles

INSTITUTO TECNOLÓGICO DE

DEPARTAMENTO DE CIENCIAS DE LA TIERRA

ALGORITMOS ESPECIALES DE PROGRAMACIÓN

VILLAHERMOSA, TABASCO 22 DE NOVIEMBRE DE 2021

La programación lineal es un conjunto de técnicas racionales de análisis y de

En el desarrollo de este trabajo vamos a desglosar uno de los casos especiales de

Características de los algoritmos de P. L.

Un algoritmo es un conjunto ordenado y finito de pasos o instrucciones que permite

Son implementados en la microeconomía y la administración de empresas, ya sea

Problema Del Transporte

• Oferta de los orígenes: 150, 150, 150, 150.

• Demanda de los destinos: 200, 150, 200, 100.

• El coste de producción cij = 2 si i = j, i, j = 1, . . ., 4

• El coste cij = coste de producción + coste de almacenamiento si i < j. Por ejemplo,

La forma matricial cuyo objetivo es minimizar es la siguiente:

El problema de asignación consiste en encontrar la forma de asignar ciertos

Los problemas de asignación presentan una estructura similar a los de transporte,

Se dice que un problema de asignación se encuentra balanceado, si los recursos

A continuación, presentaremos un ejemplo que muestra la aplicación del Método

Un equipo de 3 ingenieros debe ser asignado para la realización de 3 tareas, donde

2. Se produce los mínimos de cada columna según se observa en la tabla

1. Una constructora construye casas para a tres clientes, y cada uno

Modelo de Programación Lineal:

2. VIGAC fabrica tres tipos vigas de acero en diferentes plantas. El tiempo

MODELO TABLA DE TRANSPORTE.

En la actualidad la gran mayoría de las industrias de cualquier índole utilizan este

 Los problemas de transporte o distribución son uno de los más aplicados en

 Los análisis de dualidad y sensibilidad en los modelos de transporte

 El método del transporte de la programación lineal, no es como la

 Todos los costes están relacionados linealmente con la cantidad de bienes

 ALGORITMO: Es la representación gráfica de una

 COSTES: Cantidad de dinero que cuesta una cosa.

 DECISIÓN: Un conjunto de valores numéricos asignados a las variables de

 DESTINO: Localidad en la que hay demanda de materiales en un problema

 OPTIMIZAR: Es un concepto teórico (es decir matemático), en cuanto se

 DECISIÓN ÓPTIMA: Una decisión factible que optimiza la función objetivo.

 RESTRICCIÓN: Desigualdad matemática (desigualdad restringida) o

 SOLUCIÓN ÓPTIMA: Punto de una región factible que maximiza o minimiza

 MINIMIZAR: Reducción de la cantidad de algo.

 MAXIMIZAR: Desarrollar al máximo una cosa material o inmaterial.

 BALANCEADO: Igualar, equilibrar.

MÉTODO DE TRANSPORTE O DISTRIBUCIÓN

 Arreola Risa J., y Arreola Risa, A. “Programación Lineal”. Una

También podría gustarte