Modelos de Transporte, asignación y PERT y CPM

 Unidad 3:

Modelos de Transporte

Los modelos de transporte son representaciones matemáticas o computacionales que permiten simular y analizar el movimiento de bienes o personas entre diferentes puntos geográficos. Su objetivo principal es encontrar soluciones eficientes, rentables y sostenibles para la distribución de recursos.

Tipos de Modelos de Transporte

- Modelo de Transporte Clásico (Lineal)

- Utiliza programación lineal para minimizar el costo de transporte.

- Supone una oferta y demanda conocidas en cada punto

- Ideal para redes con rutas fijas y costos constantes.

Modelos de Transporte Multimodal

- Integran distintos medios (camión, tren, barco, avión).

- Buscan reducir tiempos y costos considerando transbordos y compatibilidades.

Ejemplo:

Modelo de Asignación

El modelo de asignación es un tipo de problema de optimización donde se busca emparejar n agentes por ejemplo, trabajadores, máquinas o vehículos con n tareas, de forma que el costo total de asignación sea mínimo o la ganancia máxima.

• Cada agente puede realizar exactamente una tarea.
• Cada tarea debe ser asignada a un solo agente.
• El objetivo: encontrar la mejor combinación posible.

¿Cómo se resuelve?

El algoritmo más conocido para resolver estos problemas es el Método Húngaro. Este método garantiza encontrar la solución óptima en tiempo polinomial.

Pasos clave:

1. Restar el mínimo de cada fila y columna.
2. Cubrir todos los ceros con el menor número de líneas horizontales/verticales.
3. Si el número de líneas es igual al número de tareas/agentes, la solución es óptima.
4. Si no, ajustar la matriz y repetir.

Ejemplo:

Ventajas del Modelo de Asignación

• Simplicidad en su formulación.
• Soluciones exactas y eficientes para problemas de tamaño razonable.
• Muy útil cuando hay correspondencia uno a uno entre recursos y tareas.

Limitaciones

• No permite múltiples asignaciones por recurso/tarea.
• No gestiona bien la incertidumbre o cambios dinámicos (para eso se usan modelos estocásticos).
• Supone que todas las tareas y recursos son igualmente importantes o equivalentes.

Ejemplos de asignación:

Asignación de turnos:

Asignación de madera:

Modelos PERT y CPM

Tanto PERT como CPM son técnicas de planificación y control de proyectos basadas en diagramas de red que muestran las actividades y sus relaciones de dependencia. Su propósito principal es determinar el tiempo mínimo necesario para completar un proyecto.

PERT: Se utiliza cuando los tiempos de ejecución son inciertos. Es un modelo probabilístico.

CPM: Se usa cuando los tiempos son conocidos con precisión. Es un modelo determinista.

Ambos modelos comparten componentes clave:

Actividades: Tareas que consumen tiempo y recursos.

Eventos: Puntos de inicio o finalización de una o más actividades.

Red: Representación gráfica de la secuencia de actividades.

Ruta crítica: La secuencia de actividades que determina la duración total del proyecto. Si se retrasa, todo el proyecto se retrasa.

¿Cómo Funciona PERT?

PERT introduce tres estimaciones de tiempo para cada actividad:

Tiempo Optimista (O): El mejor escenario.

Tiempo Más Probable (M): El escenario más común.

Tiempo Pesimista (P): El peor caso.

Con estos valores, se calcula el tiempo esperado (TE):

¿Y cómo funciona CPM?

En CPM, cada actividad tiene un tiempo fijo y un costo asociado. Se enfoca en:

Determinar la ruta crítica.

Calcular holguras (tiempo que se puede retrasar una actividad sin afectar el proyecto).

Evaluar cómo acelerar el proyecto modificando actividades críticas.

Algoritmo simplex, dualidad e Informe de sensibilidad

Unidad 2

 Algoritmo simplex 

El algoritmo Simplex, una herramienta de la programación lineal que nos ayuda a tomar decisiones óptimas cuando enfrentamos restricciones.

El método Simplex recorre los extremos de la región factible que contiene todas las soluciones posibles buscando cuál de ellas maximiza o minimiza la función objetivo.

¿Cómo aplicar el método Simplex con Solver en Excel?

El Solver de Excel es una herramienta muy útil para resolver problemas de programación lineal como los que se resuelven con el método Simplex.

Paso 1: Activar el complemento Solver

1. Abre Excel.

2. Ve al menú Archivo > Opciones.

3. En la ventana que se abre, haz clic en Complementos.

4. En la parte inferior, donde dice “Administrar”, selecciona Complementos de Excel y haz clic en Ir…

5. Marca la casilla Solver y presiona Aceptar.

Ahora tendrás la opción "Solver" en la pestaña Datos.

Paso 2: Plantear el modelo en Excel

Paso 3: Usar Solver

1. Ve a Datos > Solver.

2. En “Establecer objetivo”, selecciona la celda donde calculaste la ganancia total.

3. Marca “Máx” (porque se quiere maximizar).

4. En “Cambiando las celdas de variable”, selecciona las celdas de las unidades a producir (X,Y y Z).

5. Agrega las restricciones

6. En “Método de resolución”, selecciona Simplex LP.

7. Haz clic en Resolver.

Ejemplos con solver

Dualidad y los precios sombra

En programación lineal, todo problema tiene dos caras: el primal (el original) y el dual, que es como ver la misma situación desde otra perspectiva.

Si el problema original busca maximizar ganancias, el dual busca asignar el valor justo a cada recurso. Por eso se dice que la dualidad responde a la pregunta:

¿Cuánto estaría dispuesto a pagar por una unidad adicional de un recurso limitado?

A esa respuesta se le llama precio sombra.

Informe de sensibilidad

Se supone que ya se encontró la mejor decisión usando el Simplex. Pero el mundo real cambia los precios suben, los recursos bajan, llegan nuevos pedidos entre otras cosas

¿Cómo saber si la solución sigue siendo la mejor?

Aquí entra el informe de sensibilidad, una herramienta que mide la estabilidad del modelo ante cambios en los datos.

Este informe dice:

• Qué tanto pueden cambiar los coeficientes de la función objetivo sin alterar la solución óptima.

• Cuánto puedes modificar el lado derecho de una restricción sin afectar el resultado.

• Qué precios sombra tienen las restricciones activas.

Ejemplos

Informe de sensibilidad 

Ejemplo 2

Informe de sensibilidad 

Método Algebraico

 Método algebraico

variable básica y no básica, cual entra y cual no

variable básica son las que tienen un valor, son las de holgura

variable no básica son las que empiezan en cero

Cual entra: La que vamos a utilizar para maximizar o minimizar

Método simplex: Es un método simplificado para resolver problemas de programación lineal basado en resolución de matrices

• Es un procedimiento algebraico. Sin embargo son conceptos fundamentamos de forma algebraico

Método algebraico

1. Hallar una solución básica y factible
   • Expresar las inecuaciones (desigualdades) como ecuaciones (igualdades)
   • Hallar una variable básica para casa ecuación
   • Organizar el sistema de ecuaciones
2. Escoger la variable que entra
   • La que vamos a utilizar para maximizar o minimizar
   • ¿Cómo? Comparo los coeficientes en la función objetiva y elijo el mayor o menor
3. Escoger la variable que sale
   • Divido los recursos las variables de holgura entre la variables que tengo
   • dividiendo los variables enteros entre los coeficientes correspondientes de la columna pivote y escojo el menor
   • Cojo las variables de la fila rhs y lo divido por la fila de x1, porque es mi columna pivote
   • La operación general para actualizar una fila es:
   •  Nueva fila=Fila original−(Coeficiente de la columna pivote×Fila pivote)
4. Reorganizar el sistema de ecuaciones
   • Aplicar gauss jordan,
5. Repetir los pasos 2,3 y 4 hasta encontrar la solución

Ejemplo

Describir el algoritmo, cuál entra cuál sale:

Estudio

 

 

Tipos de soluciones

Tipos de soluciones 

Igualación: En el método de igualación, se despeja la misma incógnita en ambas ecuaciones para luego igualarlas. Esto hace que una nueva ecuación tenga una sola incógnita.

Pasos para resolver un sistema de ecuaciones por el método de igualación

1. Despejar la misma incógnita en cada ecuación
2. Igualar las expresiones
3. Dejar la expresión en función de una sola variable
4. Obtener un valor de la variable

Sustitución: Consiste en despejar una de las variables en una ecuación y sustituirla en la otra.

Pasos para resolver un sistema de ecuaciones por el método de sustitución

1. Despejar una variable en una de las ecuaciones.
2. Sustituir la expresión obtenida en la otra ecuación.
3. Resolver la ecuación resultante para encontrar el valor de una variable.
4. Sustituir el valor hallado en la ecuación despejada en el primer paso para encontrar la otra variable.

Ejemplo:

 Reducción: 

Pasos del método de reducción

1. Ajustar coeficientes: Multiplicar una o ambas ecuaciones para que los coeficientes de una de las variables sean iguales o contrarios.

2. Sumar o restar las ecuaciones: Se eliminan una de las variables.

3. Resolver la ecuación resultante para hallar el valor de una variable.

4. Sustituir el valor obtenido en una de las ecuaciones originales para encontrar la otra variable.

Ejemplo:

 

Solución de modelos

Investigación de operaciones 

¿Qué es?

La investigación de operaciones es una disciplina que utiliza métodos matemáticos y técnicas analíticas para resolver problemas complejos relacionados con la toma de decisiones y la optimización de recursos.  

¿Cuándo se podría utilizar?

Se utiliza cuando se necesita tomar decisiones en situaciones que involucran varios factores y limitaciones, como en la programación de horarios, la gestión de inventarios o la optimización de rutas de transporte.

Solución de modelos 

Julián tiene un micro emprendimiento de ollas y pone a la venta una batería de cocina en dos presentaciones, una económica y otra de lujo. El gasto que tendrá de material es de 20€ para la económica y de 80€ para la de lujo. EL gasto de mano de obra es de 50€ para la económica y para la de lujo es de 80€. Julián dispone de 160,000€ para materiales y de 240,000€ para el pago de personal. Si la batería económica se vende en 100€ y la de lujo en 230€, ¿Qué modelo de producción debe seguir Julián para que su venta sea máxima?

Una empresa decide, por el día del trabajador, llevar de paseo a la playa a 400 trabajadores (por lo menos). Para ello contrata a una compañía de transporte, la cual dispone de autobuses para 60 pasajeros y microbuses para 20 pasajeros. El precio de alquiler de cada autobús es de 250€ y de cada microbús de 200€. La compañía de transporte solo dispone ese día de 8 choferes profesionales. ¿Qué número de autobuses y microbuses deben contratarse para que el costo sea mínimo?

Unos grandes almacenes desean liquidar  camisas y  pantalones de la temporada anterior. Para ello lanzan, dos ofertas,  y  . La oferta  consiste en un lote de una camisa y un pantalón, que se venden a  €; la oferta  consiste en un lote de tres camisas y un pantalón, que se vende a  €. No se desea ofrecer menos de  lotes de la oferta  ni menos de  de la  . ¿Cuántos lotes ha de vender de cada tipo para maximizar la ganancia?

En una granja de pollos se da una dieta, para engordar, con una composición mínima de 15 unidades de una sustancia A y otras 15 de una sustancia B. En el mercado sólo se encuentra dos clases de compuestos: el tipo X con una composición de una unidad de A y 5 de B, y el otro tipo, Y, con una composición de cinco unidades de A y una de B. El precio del tipo X es de 10 euros y del tipo Y es de 30 €. ¿Qué cantidades se han de comprar de cada tipo para cubrir las necesidades con un coste mínimo?

Un agricultor tiene 600 hectáreas en las que puede sembrar maíz o cebada y dispone de 800 horas de trabajo durante la temporada. Los márgenes de utilidad por hectárea para el maíz son de 60€ y para la cebada es de 70€. Los requerimientos laborales para trabajar en la siembra de maíz es de 1 hora por hectárea y en la siembra de cebada es de 2 horas por hectárea. ¿Cuántas hectáreas de cada cultivo debe sembrar para maximizar su utilidad?, ¿Cuál es la utilidad máxima?

Una empresa de transportes tiene dos tipos de camiones, los del tipo  con un espacio refrigerado de  m³ y un espacio no refrigerado de  m³. Los del tipo , con igual cubicaje total, al  % de refrigerado y no refrigerado. La contratan para el transporte de  m³ de producto que necesita refrigeración y  m³ de otro que no la necesita. El coste por kilómetro de un camión del tipo  es de  € y el  de  €. ¿Cuántos camiones de cada tipo ha de utilizar para que el coste total sea mínimo?

Links 

https://www.superprof.es/apuntes/escolar/matematicas/algebralineal/pl/ejercicios-y-problemas-resueltos-de-programacion-lineal.html

https://www.superprof.es/apuntes/escolar/matematicas/algebralineal/pl/problemas-de-programacion-lineal.html