Tarea 1 - U3 - Investigacion

TECNOLÓGICO NACIONAL DE MÉXICO
CAMPUS VILLAHERMOSA
DEPARTAMENTO:
DEPTO. DE CIENCIAS DE LA TIERRA
MATERIA:
MODELO DE OPTIMIZACIÓN DE LOS RECURSOS
UNIDAD 3 - TEMA:
ALGORITMOS ESPECIALES DE PROGRAMACIÓN LINEAL
ALUMNO:
VICENTE VELÁZQUEZ MORALES
CATEDRÁTICO:
ING. JUAN SOLIS HERNÁNDEZ
CARRERA:
INGENIERÍA CIVIL
PERIODO:
AGOS- DIC 2021
VILLAHERMOSA, TABASCO A 22 DE NOVIEMBRE DEL 2021

ÍNDICE
CONTENIDO
INTRODUCCIÓN .................................................................... 3
MARCO TEÓRICO........................................................ 33 - 10
CONCLUSIÓN ........................................................................ 9
RECOMENDACIONES ......................................................... 11
ANEXOS ............................................................................... 12
BIBLIOGRAFÍA ..................................................................... 14
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
A) CARACTERISTICAS DE UN ALGORITMO ESPECIAL DE P. L.
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 muy usados 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.
B) MODELA FENÓMENOS DEL TRANSPORTE Y ASIGNACIÓN.
La manera de reconocer un problema de transporte es por su naturaleza o

estructura “de – Hacia”:
De un origen hacia un destino.

De una fuente hacia un usuario.
Del presente hacia el futuro.
De aquí hacia allá.
Una relación de uno a otro.
El problema del transporte en general se especifica mediante la siguiente
información:
Un conjunto de m orígenes tiene que surtir a n centros de consumo con un cierto

producto.
La capacidad de oferta del origen i es ai.
i = 1, 2, 3, …, m.
La demanda en el centro de consumo j es bj.
j = 1, 2, 3, …, n.
Si Cij es el costo de enviar una unidad del producto del origen i al centro de consumo
j.
Planteamiento del problema.
Cuántas unidades del producto deben enviarse del origen i al centro de consumo j
(i=1, 2, m; j=1, 2, n), tal que:
• Se minimicen los costos totales de distribución.

• Se satisfaga la demanda del centro de consumo j
• No se exceda la capacidad de oferta del origen i
Sea Xij la variable de decisión.

La matriz del problema lineal.
Tabla del problema del transporte:
Determinación de la solución básica factible inicial
Para resolver problemas de transporte se recomiendan métodos como:
• Método de la esquina Nor-Oeste (N-O)

• Método de matriz de costo mínimo.
• Método Vogel.
Ejemplo por el método (N-O).

Una compañía tiene 3 fábricas en A, B y C lugares, las cuales proveen a los
almacenes que están ubicados en D, E, F y G sitios. LA capacidad de producción
de las fabricas es de 70, 90 y 115 unidades mensuales respectivamente, mientras
que la capacidad de los almacenes son 50, 60, 70 y 95 unidades respectivamente.
El costo de envío de una unidad desde cada una de las fabricas a cada uno de los
almacenes se presenta en el siguiente cuadro (en $).
Datos tabulados:
Por lo que la solución es: Cij Como ningún método garantiza que la solución
encontrada sea la más óptima debemos estar seguros que ninguna de las variables
no buscada pueda entrar a la base haciendo que la función objetivo disminuya.
• Recurrimos al método MODI o UV.

Criterio de optimalidad y el algoritmo de mejoramiento de la solución
• Método de paso secuencial.
• Método de la Distribución modificada.
Se dibuja la matriz Zij que contiene los costos de la variable solución.

Se dibuja la matriz Zij que contiene los costos de la variable solución.
Siguiendo con el ejemplo anterior (resuelto por el método N-O)
Vj y Ui son un conjunto de números tal que la suma iguale a los valores de la matriz
Zij del paso anterior y la celda vacía se completa con la suma de Ui y Vj.
Se calcula Cij menos Zij
El costo de la nueva solución es Z1 = 5305 + 20(-15) = $5,005
A continuación, se comprueba si esta solución es la más óptima realizando

nuevamente el procedimiento:
(Cij - Zij)
Se calcula Cij menos Zij
El costo de la nueva solución es Z2 = 5005 + 30(-18) = 4465
Se comprueba si la solución es la óptima
El costo de la nueva solución es Z3 = 4465 + 20(-14) = 4185 Se comprueba si la
solución es la óptima.
Esta es la solución óptima.
Las características de los algoritmos son:
• Un algoritmo debe ser preciso e indicar el orden de realización de cada paso.
• Un algoritmo debe estar definido. Si se sigue un algoritmo dos veces, se
debe obtener el mismo resultado cada vez.
• Un algoritmo debe ser finito. Si se sigue un algoritmo, se debe terminar en
algún momento; o sea, debe tener un número finito de pasos.
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.
C) DETERMINA SOLUCIONES DE PROBLEMAS DE TRANSPORTE Y
ASIGNACIÓN.
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
2. se resta el mínimo de cada fila a cada uno de los valores de la fila respectiva,
para obtener la matriz reducida:
3. 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.
PROBLEMAS RESUELTOS DE P. L.
CONCLUSIÓN
A manera de conclusión podemos afirmar que la programación lineal es una

herramienta muy útil, tanto para personas con empresas independientes como para
grandes compañías. Permite administrar de la mejor manera los recursos con los
que se cuenta para poder aprovecharlos al máximo, como también ayuda a obtener
mayores ganancias y a minimizar los costos. La programación lineal es un
procedimiento o algoritmo matemático, mediante el cual se resuelve un problema
indeterminado. Consiste en optimizar (minimizar o maximizar) una función lineal,
que denominaremos función objetivo, de tal forma que dichas funciones estén
sujetas a una serie de restricciones que expresamos mediante un sistema de
inecuaciones lineales. La programación lineal nos permite utilizar diferentes
métodos los cuales nos permiten reducir costos y obtener ganancias.
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.
ANEXOS
BIBLIOGRAFÍA
 Loomba, N.P. Linear Programming: An introductory analysis. McGrawHill,

New York, 1964
 Universidad Peruana Unión - Biblioteca Central - libro número 0.001245/f12
Programación lineal.
 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.

Tarea 1 - U3 - Investigacion

Cargado por

Copyright:

Formatos disponibles

Tarea 1 - U3 - Investigacion

Cargado por

Información del documento

Descripción original:

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

Tarea 1 - U3 - Investigacion

Cargado por

Copyright:

Formatos disponibles

TECNOLÓGICO NACIONAL DE MÉXICO

VILLAHERMOSA, TABASCO A 22 DE NOVIEMBRE DEL 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

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

Algoritmos Especiales. - Son diseñados para problemas de programación lineal,

Son muy usados en la microeconomía y la administración de empresas, ya sea para

B) MODELA FENÓMENOS DEL TRANSPORTE Y ASIGNACIÓN.

La manera de reconocer un problema de transporte es por su naturaleza o

De un origen hacia un destino.

Un conjunto de m orígenes tiene que surtir a n centros de consumo con un cierto

Planteamiento del problema.

• Se minimicen los costos totales de distribución.

Sea Xij la variable de decisión.

• Método de la esquina Nor-Oeste (N-O)

Ejemplo por el método (N-O).

• Recurrimos al método MODI o UV.

Se dibuja la matriz Zij que contiene los costos de la variable solución.

A continuación, se comprueba si esta solución es la más óptima realizando

1) La función objetivo y las restricciones deben ser lineales.

• 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

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

1. identificar el valor mínimo de cada fila. En el caso de la fila 1 dicho valor es

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

A manera de conclusión podemos afirmar que la programación lineal es una

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

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

• 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

 Loomba, N.P. Linear Programming: An introductory analysis. McGrawHill,

También podría gustarte