UPN, PASIÓN POR
TRANSFORMAR VIDAS
En el mundo de la optimización matemática, la programación lineal nos
ofrece una poderosa herramienta para minimizar costos, maximizar
beneficios y encontrar soluciones eficientes en una amplia gama de
problemas. Hoy, nos sumergiremos en el fascinante mundo de la
programación lineal y exploraremos cómo podemos utilizarla para
optimizar nuestras decisiones.
Mg. Ing. Kenia Correa Hernández
[email protected]
OPTIMIZACIÓN Y
SIMULACÓN
MÓDULO 3: PROGRAMACIÓN LINEAL
PARA LA MINIMIZACIÓN
UG – 2024-2
Sesión complementaria 04
Tema: INTRODUCCÍÓN A LA OPTIMIZACIÓN
AGENDA
Participación del Debate
Introducción al tema
Desarrollo del contenido (Sub temas)
Ejemplos a través de casos
Actividad a realizar en casa / Verificación de Aprendizaje
Conclusiones y Consultas
OPTIMIZACIÓN Y SIMULACIÓN – SEMANA 4
OBJETIVO DEL MÓDULO 3 -> LOGRO DE APRENDIZAJE
Al término del módulo, el estudiante resuelve problemas básicos de programación lineal de
minimización, utilizando el método simplex, demostrando orden y precisión.
¿Cómo lo lograremos?
1. Hallar la forma estándar para los modelos de programación lineal de
minimización.
2. Dar solución a modelos de programación lineal de minimización utilizando el
método simplex
¿Por qué es importante este tema?
porque permite optimizar la asignación de recursos y la toma de decisiones en una amplia gama
de aplicaciones, lo que conduce a sistemas más eficientes, rentables y efectivos. Ayuda a abordar
problemas complejos de manera cuantitativa y objetiva, lo que es esencial en el campo de la
ingeniería de sistemas computacionales.
POR FAVOR RSPONDE LAS PREGUNTAS QUE SE TE
HARAN A TRAVÉS DEL SONDEO DE LA SALA
PROGRAMACIÓN LINEAL PARA
MAXIMIZACIÓN Y MINIMIZACIÓN
Construir el modelo de PL
Forma estándar, transformar las inecuaciones de las restricciones.
Conversión de la función objetivo de maximizar o minimizar
RECORDEMOS PARA MAXIMIZAR
Max Z = 36X1 + 48X2
RESTRICCIÓN REGLA RESTRICCIÓN EN FORMA
ESTÁNDAR
10X1 + 4X2 <= 24 (<=) Sumar variable de 10X1 + 4X2 + S1= 24
holgura.
Casos 5X1 – X2 >= 36 (>=) Restar variable de holgura 5X1 – X2 – S2 + A1= 36
ejemplo y sumar variable artificial.
12X1 + 6X2 =48 (=) Sumar variable artificial. 12X1 + 6X2 + A2 =48
Conversión de la Función Objetivo Maximizar:
Max Z = 36X1 + 48X2 + 0S1 + 0S2 – 0A1 – 0A2
RECORDEMOS PARA MINIMIZAR
Min Z = 36X1 + 48X2
RESTRICCIÓN REGLA RESTRICCIÓN EN FORMA
ESTÁNDAR
10X1 + 4X2 <= 24 (<=) Sumar variable de holgura. 10X1 + 4X2 +S1= 24
5X1 – X2 >= 36 (>=) Restar variable de holgura y 5X1 – X2 – S2 + A1= 36
sumar variable artificial.
12X1 + 6X2 =48 (=) Sumar variable artificial. 12X1 + 6X2 + A2 =48
Conversión de la Función Objetivo Minimizar:
Min Z = 36X1 + 48X2 + 0S1 + 0S2 + 0A1 + 0A2
MÉTODO SIMPLEX DE MAXIMIZACIÓN VS MÉTODO SIMPLEX DE MINIMIZACIÓN
Pasamos el problema a la forma estándar,
Cj
(coeficientes de la añadiendo variables de exceso, holgura, y
MAXIMIZACIÓN función objetivo artificiales según corresponda
STANDARIZADA)
FUNCIÓN OBJETIVO:
Z=4x1+3x2
RESTRICCIONES:
2x1+x2<=8
1x1+2x2<=6
X1,x2>=0
Zj •Como la restricción 1 es del tipo '≤' se agrega la variable de holgura X3.
XB •Como la restricción 2 es del tipo '≤' se agrega la variable de holgura X4..
Ymn
(Coeficientes de las (coeficientes de las
variables básicas / restricciones / coeficientes
solución básica) tecnológicos)
MÉTODO SIMPLEX DE MAXIMIZACIÓN VS MÉTODO SIMPLEX DE MINIMIZACIÓN
Pasamos el problema a la forma estándar,
Cj
(coeficientes de la añadiendo variables de exceso, holgura, y
MINIMIZACIÓN función objetivo artificiales según corresponda
STANDARIZADA)
FUNCIÓN OBJETIVO:
Z=3x1+2x2
RESTRICCIONES:
2x1+x2≥6
x1+2x2≥4
x1,x2 ≥0
Zj
•Como la restricción 1 es del tipo '≤' se agrega la variable de holgura X3.
XB Ymn •Como la restricción 2 es del tipo '≤' se agrega la variable de holgura X4.
(Coeficientes de las (coeficientes de las
variables básicas / restricciones / coeficientes
solución básica) tecnológicos)
un proyecto de pintado de veredas puede ser realizado por 2 empresas E1 y
E2. Se debe pintar las veredas en tres zonas A, B y C. La empresa E1 puede
pintar por día 4 veredas de la zona A, 2 veredas de la zona B y 2 veredas de la
zona C. La empresa E2 puede pintar por día 2 veredas de la zona A, 4 veredas
de la zona B y 2 veredas de la zona C. Se necesita pintar como mínimo 12
veredas en la zona A, 24 veredas en la zona B y 20 veredas en la zona C, el
costo diario por el pintado de veredas E1 y E2 es de S/ 500 y S/ 550
respectivamente. ¿Cuántos días debe trabajar cada empresa para finalizar el
proyecto con el mínimo costo?
PASO 1:
Primero, definamos las variables y la función objetivo:
Variables de decisión:
•X1: número de días que trabaja la empresa E1.
•X2: número de días que trabaja la empresa E2.
Función objetivo (a minimizar):
Z=500x1+550X2
Esta función representa el costo total de contratar a
las empresas E1 y E2 para completar el proyecto.
PASO 2:
Segundo, definamos las restricciones
Restricciones:
1. Zona A: 4x1+2x2≥12 1. Se deben pintar al menos 12 veredas en la zona A
2. Zona B: 2x1+4x2≥24 2. Se deben pintar al menos 24 veredas en la zona B
3. Zona C: 2x1+2x2≥20 3. Se deben pintar al menos 20 veredas en la zona C)
4. No negatividad: x1≥0 y x2≥0. 4. X1 y x2 no puedes ser negativos
PASO 3:
Pasamos el problema a la forma estándar, añadiendo variables de exceso, holgura, y artificiales según
corresponda
•Como la restricción 1 es del tipo '≥' se resta la variable de holgura S1 y se suma la variable artificial A1.
•Como la restricción 2 es del tipo '≥' se resta la variable de holgura S2 y se suma la variable artificial A2.
•Como la restricción 3 es del tipo '≥' se resta la variable de holgura S3 y se suma la variable artificial A3.
MINIMIZAR: FUNCION OBETIVO ESTANDAR
.
Z=500X1+5050X2 ----------------------→ MAXIMIZAR Z= -500X1-550X2+0S1+05S+053+MA1+MA2+MA3
SUJETO A: RESTRICCIONES STANDAR
4 X1 + 2 X2 ≥ 12 -----------------→ 4 X1 + 2 X2 -S1 + A1 = 12
2 X1 + 4 X2 ≥ 24 -----------------→ 2 X1 + 4 X2 -S2 + A2 = 24
2 X1 + 2 X2 ≥ 20 -----------------→2 X1 + 2 X2 -S3 + A3 = 20
X1, X2 >=0 -----------------→ S1, S2, S3, A1,A2,A3 >= 0
PASO 4:
Crear Tabla Simplex: (utilizar PHPSIMPLEX). MAXIMIZAR Z= -500X1-550X2+0S1+05S+053+MA1+MA2+MA3
Cj (coeficientes de la función objetivo STANDARIZADA
Tabla 1 -500 -550 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P1 -500 8 1 0 0 0.5 -1
P2 -550 2 0 1 0 -0.5 0.5
P3 0 24 0 0 1 1 -3
Z -5100 0 0 0 25 225
XB
(Coeficientes de las
variables básicas /
solución básica)
PASO 5
Solución:
La solución óptima es Z = 5100
X1 = 8
X2 = 2
INTERPRETACIÓN:
•X1: número de días que trabaja la empresa E1: 8
•X2: número de días que trabaja la empresa E2: 2
•Z= Costo mínimo 5100
COMPARTE LO QUE APRENDISTE
HOY A TRAVÉS DEL CHAT DE LA
PATAFORMA
Conclusiones
IMPORTANTE
RECUERDA:
➢ El Modelo de programación lineal es un MODELO
MATEMATICO
➢ El PIVOTE es el cruce de la variable de entrada y la
variable de salida para la nueva iteración.
➢ La Solución óptima de las variables se identifica en la
ITERACIÓN OPTIMA con los valores CB y VB
➢ Es falso que las iteraciones del método simplex
terminan cuando se encuentra un Z positivo.
➢ Una diferencia del método simplex para la
minimización: Los Cj están multiplicados por -1
➢ La prueba de optimalidad del modelo de
minimización es: Zj-Cj=0; donde Zj y Cj son
INDICADORES DE OPTIMALIDAD
Minimización de Costos de Operación de Servidores en una
Empresa de Tecnología
Una empresa de tecnología opera tres centros de datos en
diferentes ubicaciones para ofrecer servicios en la nube a sus
clientes. La empresa desea minimizar el costo total de
operación de estos centros de datos, que incluye costos de
energía y mantenimiento. Cada centro de datos tiene una
capacidad máxima de procesamiento, y las cargas de trabajo
que deben procesarse varían en función de la demanda de los
clientes.
Los centros de datos deben manejar un mínimo de demanda
en términos de unidades de procesamiento para garantizar el
servicio adecuado a sus clientes.
19
Datos del problema:
Capacidad máxima (en unidades de procesamiento) por centro de datos:
• Centro de Datos 1 (CD1): 200 unidades.
• Centro de Datos 2 (CD2): 150 unidades.
• Centro de Datos 3 (CD3): 180 unidades.
Demanda mínima total (en unidades de procesamiento) que debe cubrirse:
• 350 unidades.
Costo de operación por unidad de procesamiento:
CD1: $10 por unidad.
CD2: $15 por unidad.
CD3: $12 por unidad.
Requerimiento adicional: Para mantener la seguridad y redundancia, el Centro de
Datos 1 (CD1) debe operar al menos con 50 unidades de procesamiento.
OPTIMIZACIÓN Y SIMULACIÓN – SEMANA 4
LO QUE LOGRAMOS HOY
Resolver problemas básicos de programación lineal de minimización, utilizando el método simplex, demostrando
orden y precisión..
¿Cómo lo hicimos?
1. Hallar la forma estándar para los modelos de programación lineal de
minimización.
2. Dar solución a modelos de programación lineal de minimización utilizando el
método simplex (phpsimplex)
¿En qué aporta a mi carrera?
Nos permite optimizar la asignación de recursos y la toma de decisiones en una amplia gama de
aplicaciones, lo que conduce a sistemas más eficientes, rentables y efectivos. Ayuda a abordar
problemas complejos de manera cuantitativa y objetiva, lo que es esencial en el campo de la
ingeniería de sistemas computacionales.
Tema:
CONSULTAS
Realice consultas a través del chat
o solicita al docente activar el
micrófono para participar.
También podrás enviar sus consultas a través de
Pregúntale al profesor y te responderé en 24 horas.
TEMA
SEMANA 5
PROGRAMACIÓN LINEAL
PARA VARIABLES
IRRESTRICTAS
SIMULACIÓN DE SISTEMAS
2024-1
Sesión complementaria 5
