UNIVERSIDAD DE SANTIAGO DE CHILE

FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

GUÍA nro. 1: MODELAMIENTO

Profesor: Cristián Sepúlveda S.

Correo: [email protected]
Fecha: 19 de agosto de 2022

Problema 1
La fábrica Prisma, confecciona dos modelos de estuches y dos de mochilas, siendo su
principal diferencia el tamaño. El proceso de producción consta de dos etapas: corte y costura. Los
principales insumos utilizados son género e hilo, existiendo una disponibilidad semanal de 5000 m 2
y 20000 m respectivamente. Prisma, emplea a 5 trabajadores en el departamento de corte y 10 en
el de costura. La fábrica trabaja un turno único de 8 horas diarias, durante 5 días a la semana. La
siguiente tabla muestra los requerimientos de tiempos e insumos, además de las utilidades por
unidad para los cuatro productos fabricados:

Minutos por unidad Insumos por unidad Utilidad

Prenda Corte Costura Hilo (m) Género (m2) unitaria ($)
Estuche S 8 10 1 0.25 650
Estuche M 10 11 1.2 0.5 900
Mochila S 16 17 2.2 1 1500
Mochila M 18 20 2.8 1.25 1950

Plantee un modelo de programación lineal para determinar el programa de producción

semanal óptimo para Prisma.
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

Problema 2
La empresa de alimentos concentrados Cisterna S.A. produce alimentos para animales de
granja. Los productos se venden en dos formatos: polvo y gránulos. Las materias primas utilizadas
para la producción de los alimentos son: avena, maíz y melaza. En una primera etapa, las materias
primas (con la excepción de la melaza) deben ser trituradas, para luego en una segunda etapa, ser
mezcladas. En la última etapa del proceso de producción, la mezcla es transformada en gránulos o
tamizada para obtener el alimento en forma de polvo.

Los dos productos finales deben cumplir ciertos requisitos nutricionales. Los porcentajes
de proteínas, lípidos y de fibra contenidas en las materias primas y los porcentajes requeridos en
los productos finales se enumeran en la siguiente tabla.

Tabla 1: Contenido nutricional en porcentaje.

Materia prima Proteínas Lípidos Fibra
Avena 13.6 7.1 7
Maíz 4.1 2.4 3.7
Melaza 5 0.3 25
Requisitos ≥ 9.5 ≥2 ≤6

La siguiente tabla muestra la disponibilidad diaria de materias primas y sus respectivos

precios.

Tabla 2: Materias prima disponibles y precios.

Materia prima Disponibilidad en kg Costo en €/kg
Avena 11900 0.13
Maíz 23500 0.17
Melaza 750 0.12
Finalmente, los costos de las diferentes etapas de producción se indican en la siguiente
tabla.

Tabla 3: Costos de producción en €/kg.

Molienda Mezcla Granulación Tamizado
0.25 0.05 0.42 0.17
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

Considere una demanda diaria de nueve toneladas de gránulos y doce toneladas de

alimento en polvo. Formule un modelo de programación matemática que determine la cantidad
de cada materia prima requerida para minimizar el costo total de producción.

Problema 3
Una empresa siderúrgica ha recibido un pedido de 500 toneladas de acero destinado a la
construcción naval. El acero, debe cumplir con los siguientes requisitos porcentuales en su
composición.
Tabla 2: requisitos porcentuales.
Elemento Químico Mínimo Porcentual (%) Máximo Porcentual (%)
Carbón (C) 2 3
Cobre (Cu) 0.4 0.6
Manganeso (Mn) 1.2 1.65

La empresa cuenta con siete materias primas diferentes en stock que pueden ser utilizadas
para la producción del acero. En tabla nro. 3 se enumeran los porcentajes, las cantidades
disponibles y los precios de todas las materias primas.

Tabla 3: materias prima y costos.

Materia C% Cu % Mn % Disponibilidad Costo en €/t
prima en t
Hierro 1 2.5 0 1.3 400 200
Hierro 2 3 0 0.8 300 250
Hierro 3 0 0.3 0 600 150
Cobre 1 0 90 0 500 220
Cobre 2 0 96 4 200 240
Aluminio 1 0 0.4 1.2 300 200
Aluminio 2 0 0.6 0 250 165

El objetivo es determinar la composición de la aleación que optimice la producción.

UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

Problema 4
En el marco del programa de JUNJI para entrega de almuerzos a niños de educación
preescolar, un equipo de nutricionistas se encuentra diseñando una dieta que contenga toda la
energía (2000 Kcal), proteína (95 g), y calcio (800 mg) necesario para una alimentación saludable.
Con este fin, el equipo eligió seis alimentos por ser fuentes baratas de nutrientes y tabuló
sus datos de valores nutritivos por porción en la tabla 2.

Tabla 2: valores nutritivos.

Energía Proteínas Calcio Precio
Alimento Porción (Kcal) (g) (mg) (Pesos)
Avena 28 g 110 4 2 23
Pollo 100 g 205 32 12 240
Huevo 2 unidades 160 13 54 83
Leche 237 cc 160 18 185 210
Carne 270 g 420 64 22 620
Manzana 160 g 110 14 80 89

Plantee un modelo de PL para encontrar el menú que satisfaga las necesidades

nutricionales propuestas por el equipo de nutricionista al mínimo costo.

Problema 5
La industria papelera DIMAR que fabrica papel y lo distribuye en rollos debe determinar la
mejor forma de realizar el proceso de corte. Los rollos de papel que se producen tienen un ancho
de 100 cm; sin embargo, algunas librerías demandan rollos de 30 cm, 45 cm y 50 cm de ancho. Por
lo tanto, al cortar los rollos de 100 cm se incurre en una pérdida de material que depende de la
forma en que se corten los rollos originales.
Se desea determinar la forma de efectuar el corte de manera que se satisfaga la demanda
y se minimice la pérdida total de material. Se tiene un pedido de 800 rollos de 30 cm de ancho,
500 rollos de 45 cm y 1.000 rollos de 50 cm. Plantee un modelo de PL que minimice las perdidas.
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

Problema 6
Un fabricante mantiene tres centros de distribución: Cerrillos, Peñalolén y Quilicura. Estos
centros tienen disponibilidades de: 2000, 4000 y 4000 unidades respectivamente. Sus detallistas
requieren las siguientes cantidades: Maipú 2500, Estación Central 1000, Santiago 2000,
Providencia 3000 y La Reina 1500. El costo de transporte por unidad en pesos entre cada centro de
distribución y las comunas de los detallistas se dan en la tabla 4:

Tabla 4: costos de transporte.

Detallistas
Maipú Est. Central Santiago Providencia La Reina
Centros de Cerrillos 55 30 40 50 40
distribución Peñalolén 35 30 100 45 60
Quilicura 40 60 95 35 30

Formule un modelo para determinar el número de unidades que debe enviar el fabricante
desde cada centro de distribución a cada detallista, de manera que los costos totales de transporte
sean mínimos.

Problema 7
Una empresa naviera debe decidir qué cargas embarcar en uno de sus barcos con tal de
optimizar su viaje. El barco mercante cuenta con una superficie para cargas de 3000 m 2, se deben
seleccionar las cargas desde un grupo de ocho disponibles, cuyas superficies son de 400 m 2, 350
m2, 600 m2, 800 m2, 870 m2, 950 m2, 780 m2 y 640 m2. Los beneficios de transportar cada carga son
de $500, $600, $380, $750, $590, $820, $300 y $910 respectivamente. Plantee un modelo de PL
que maximice el beneficio.
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

Problema 8
VEKA Chile, fabricante de perfiles para ventanas, se adjudicó una licitación para proveer
100, 250, 190, 140, 220 y 110 ventanas en la construcción de un condominio durante los
siguientes seis meses.
El costo de producción (mano de obra, materiales y servicios) por ventana varía por
periodo y se estima que será de $35000, $31500, $38500, $33600, $36400 y $35000 durante los
próximos seis meses. Para aprovechar las fluctuaciones del costo de fabricación, VEKA Chile puede
producir más ventanas de las necesarias en un mes dado y conservar las unidades adicionales para
entregarlas en meses posteriores. Esto supondrá un costo de almacenamiento a razón de $4600
por ventana por mes, estimado en el inventario de fin de mes. Desarrolle un PL para determinar el
programa de producción óptimo.

Bibliografía:
Hamdy, Taha, Investigación de operaciones, Pearson Educación, México, 2012.
Guı́a 1 Modelamiento Universidad de Santiago de Chile
Métodos de Optimización Departamento de Informática
Prof. Cistián Sepúlveda S.

Problema 1
Variables de decisión:
x1 : Cantidad de estuches tipo S
x2 : Cantidad de estuches tipo M
x3 : Cantidad de mochilas tipo S
x4 : Cantidad de mochilas tipo M

Función Objetivo: (maximizar utilidad)

maximizar 650x1 + 900x2 ) + 1500x3 + 1950x4 )

Restricción de corte:
8x1 + 10x2 + 16x3 + 18x4 ≤ 12000 (5 trabajdores x 8 horas x 5 dı́as x 60 minutos)

Restricción de costura:
10x1 + 11x2 + 17x3 + 20x4 ≤ 24000

Restricción de hilo:
x1 + 1.2x2 + 2.2x3 + 2.8x4 ≤ 20000

Restricción de género:
0.25x1 + 0.5x2 + x3 + 1.25x4 ≤ 5000

Restricciones de no negatividad:
x1 , x2 , x3 , x4 ≥ 0

1
Problema 2
Variables de decisión:
x11 : Cantidad de avena utilizada en el alimento granulado
x12 : Cantidad de avena utilizada en el alimento tamizado
x21 : Cantidad de maı́z utilizada en el alimento granulado
x22 : Cantidad de maı́z utilizada en el alimento tamizado
x31 : Cantidad de melaza utilizada en el alimento granulado
x32 : Cantidad de melaza utilizada en el alimento tamizado

Función objetivo: (minimizar costos)

minimizar 0.13(x11 + x12 ) + 0.17(x21 + x22 ) + 0.12(x31 + x32 ) + 0.25(x11 + x12 + x21 + x22 ) +
0.05(x11 + x12 + x21 + x22 + x31 + x32 ) + 0.42(x11 + x21 + x31 ) + 0.17(x12 + x22 + x32 )

Restricciones de demanda:
x11 + x21 + x31 ≥ 9000 (alimento granulado)
x12 + x22 + x32 ≥ 12000 (alimento tamizado)

Restricciones de disponibilidad:
x11 + x12 ≤ 11900 (avena)
x21 + x22 ≤ 23500 (maı́z)
x31 + x32 ≤ 750 (melaza)

Restricciones nutricionales:
0.136x11 + 0.041x21 + 0.0.05x31 ≥ 0.095(x11 + x21 + x31 ) (proteı́nas alimento granulado)
0.136x12 + 0.041x22 + 0.0.05x32 ≥ 0.095(x12 + x22 + x32 ) (proteı́nas alimento tamizado)
0.071x11 + 0.024x21 + 0.003x31 ≥ 0.02(x11 + x21 + x31 ) (lı́pidos alimento granulado)
0.071x12 + 0.024x22 + 0.003x32 ≥ 0.02(x12 + x22 + x32 ) (lı́pidos alimento tamizado)
0.07x11 + 0.037x21 + 0.25x31 ≤ 0.06(x11 + x21 + x31 ) (fibra alimento granulado)
0.07x12 + 0.037x22 + 0.25x32 ≤ 0.06(x12 + x22 + x32 ) (fibra alimento tamizado)

Restricciones de no negatividad:
x11 , x12 , x21 , x22 , x31 , x32 ≥ 0

2
Problema 3
Variables de decisión:
xi : cantidad de materia prima tipo i utilizada en la aleación; con i = 1,...,7

Función objetivo: (minimizar costos)

minimizar 200x1 + 250x2 + 150x3 + 220x4 + 240x5 + 200x6 + 165x7

Restricciones:
0.025x1 + 0.03x2 ≥ 0.02 · 500
0.003x3 + 0.9x4 + 0.96x5 + 0.004x6 + 0.006x7 ≥ 0.004 · 500
0.013x1 + 0.008x2 + 0.04x5 + 0.012x6 ≥ 0.012 · 500
0.025x1 + 0.03x2 ≤ 0.03 · 500
0.003x3 + 0.9x4 + 0.96x5 + 0.004x6 + 0.006x7 ≤ 0.006 · 500
0.013x1 + 0.008x2 + 0.04x5 + 0.012x6 ≤ 0.0165 · 500

x1 + x2 + x3 + x4 + x5 + x6 + x7 = 500

Restricciones de disponibilidad:
x1 ≤ 400, x2 ≤ 300, x3 ≤ 600, x4 ≤ 500, x5 ≤ 200, x6 ≤ 300, x7 ≤ 250

Restricciones de no negatividad:
x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0

3
Problema 4
Variables de decisión:
x1 : porciones de avena
x2 : porciones de pollo
x3 : porciones de huevo
x4 : porciones de leche
x5 : porciones de carne
x6 : porciones de manzana

Función objetivo: (minimizar costos)

minimizar 23x1 + 240x2 + 83x3 + 210x4 + 620x5 + 89x6

Restricciones:
110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 110x6 ≥ 2000
4x1 + 32x2 + 13x3 + 18x4 + 64x5 + 14x6 ≥ 95
2x1 + 12x2 + 54x3 + 185x4 + 22x5 + 80x6 ≥ 800

Restricciones de no negatividad:
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

4
Problema 5
Esquema de corte pérdida
1 30 - 30 - 30 10
2 30 - 45 25
3 30 - 50 20
4 45 - 45 10
5 45 - 50 5
6 50 - 50 0

Variables de decisión:
x1 : número de rollos cortados según el esquema 1
x2 : número de rollos cortados según el esquema 2
x3 : número de rollos cortados según el esquema 3
x4 : número de rollos cortados según el esquema 4
x5 : número de rollos cortados según el esquema 5
x6 : número de rollos cortados según el esquema 6

Función objetivo:
minimizar 10x1 + 25x2 + 20x3 + 10x4 + 5x5

Restricciones:
3x1 + x2 + x3 ≥ 800
x2 + 2x4 + x5 ≥ 500
x3 + x4 + 2x6 ≥ 1000

Restricciones de no negatividad:
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

5
Problema 6
Variables de decisión:
xij : cantidad de unidades enviadas desde el centro i-ésimo al detallista j-ésimo; con i = 1,2,3 y
j = 1,...,5

Función objetivo:
minimizar 3i=1 5j=1 cij xij
P P

Restricciones:
oi : oferta del punto de distribución i-ésimo
dj : demanda del punto detallista j-ésimo
P5
xij ≤ oi ; con i = 1,2,3
Pj=1
3
i=1 ij ≥ dj ; con j = 1,...,5
x

Restricciones de no negatividad:
xij ≥ 0; con i = 1,2,3 y j = 1,...,5

6
Problema 8
Variables de decisión:
xi : unidades producidas en el mes i; con i = 1, · · · , 6
ij : unidades en inventario al fin del mes j; con j = 1, · · · , 6

Función objetivo: (minimizar costos)

minimizar 35000x1 +32500x2 +38500x3 +33600x4 +36400x5 +35000x6 +4600(i1 +i2 +i3 +i4 +i5 )

Restricciones:
x1 − i1 = 100
i1 + x2 − i2 = 250
i2 + x3 − i3 = 190
i3 + x4 − i4 = 140
i4 + x5 − i5 = 220
i5 + x6 = 110

Restricciones de no negatividad:
xi , ij ≥ 0

7
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

GUÍA N°3: SOLUCIONES BÁSICAS

Profesor: Cristián Sepúlveda S.

Correo: [email protected]
Fecha: 6 de septiembre de 2021

Problema 1

1. Estandarice el programa lineal.

2. Construya todas las submatrices cuadradas y verifique si son base, en caso de serlo,
obtenga la solución básica del sistema y verifique la factibilidad de la solución.
3. Calcule el valor objetivo para cada solución básica factible e identifique la solución óptima
del problema.
4. Grafique la región factible y asocie los puntos extremos con las soluciones básicas
obtenidas.

Maximizar 2x1 + 3x2 = z

s.a.
2x1 + x2 ≤ 4
x1 + 2x2 ≤ 5
x1, x2 ≥ 0

Referencias:
Bazaraa, M., Jarvis, J., Sherali, H., Linear Programming and Network Flows, John Wiley & Sons, New
Jersey, 2010.
Hillier, Lieberman, Introducción a la Investigación de operaciones, McGRAW-HILL, 2010.
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

GUÍA N°4: ITERACIONES EN SIMPLEX

Profesor: Cristián Sepúlveda S.

Correo: [email protected]
Fecha: 02 de septiembre de 2022

Problema 1

Para el siguiente problema de programación lineal, realice una iteración. Considere como
inicio la solución básica factible asociada a la base B = [a1, a2]. Grafique la iteración.

Minimizar 2x1 - x2 = z
s.a.
- x1 + x2 ≤ 2
2x1 + x2 ≤ 6
x1, x2 ≥ 0

Problema 2

Dado el siguiente programa lineal. Itere dos veces, comenzando desde la solución básica
factible asociada a la base B = [a3, a4]. Grafique ambas iteraciones.

Minimizar - x1 - 3x2 = z
s.a.
x1 + x 2 ≤ 6
- x1 + 2x2 ≤ 8
x1, x2 ≥ 0
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

GUÍA nro. 5: MÉTODO SIMPLEX MATRICIAL

Profesor: Cristián Sepúlveda S.

Correo: [email protected]
Fecha: 20 de septiembre de 2022

Problema 1
Maximizar 2 x 1 + 2 x2 = z

s.a. - 2 x1 + x2 ≤ 30

x1 + x2 ≤ 60

x1, x2 ≥ 0

Problema 2
Minimizar - 3 x 1 + x2 = z

s.a. – 4 x1 + 3 x2 ≤ 36

x1 - x2 ≤ 16

x1, x2 ≥ 0

Problema 3
Maximizar 3 x 1 + 2 x2 = z

s.a. 2 x1 + x2 ≤ 100

x1 + x2 ≤ 80

x1, x2 ≥ 0

Referencias:
Bazaraa, M., Jarvis, J., Sherali, H., Linear Programming and Network Flows, John Wiley & Sons, New
Jersey, 2010.
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

GUÍA nro. 6: MÉTODO SIMPLEX TABLEAU

Profesor: Cristián Sepúlveda S.

Correo: [email protected]
Fecha: 22 de septiembre de 2022

Problema 1
Maximizar 3x1 + 2x2 = z
s.a. 2x1 + x2 ≤ 100
x1 + x2 ≤ 80
x1 ≤ 40
x1, x2 ≥ 0

Problema 2
Maximizar 2x1 + 2x2 = z
s.a. -2x1 + x2 ≤ 30
x1 + x2 ≤ 60
4x1 + x2 ≤ 160
x1, x2 ≥ 0

Problema 3
Minimizar - 3 x1 + x2 = z
s.a. – 4 x1 + 3 x2 ≤ 36
x1 - x2 ≤ 16
x1, x2 ≥ 0

Referencias:
Bazaraa, M., Jarvis, J., Sherali, H., Linear Programming and Network Flows, John Wiley & Sons, New
Jersey, 2010.
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

Z X1 X2 X3 X4 X5 LD
Z 1
0
0
0

Z X1 X2 X3 X4 X5 LD
Z 1
0
0
0

Z X1 X2 X3 X4 X5 LD
Z 1
0
0
0

Z X1 X2 X3 X4 X5 LD
Z 1
0
0
0

Z X1 X2 X3 X4 X5 LD
Z 1
0
0
0
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

GUÍA N°6: MÉTODO SIMPLEX TABLEAU

Problema 1
Maximizar 3x1 + 2x2 ↔ - [Minimizar -3x1 - 2x2]

Minimizar z
s.a. z + 3x1 + 2x2 = 0
2x1 + x2 + x3 = 100
x1 + x2 + x4 = 80
x1 + x5 = 40
x1, x2 x3, x4 ≥ 0

Tableau inicial, con B= [a3, a4, a5]

Z X1 X2 X3 X4 X5 RHS
Z 1 3 2 0 0 0 0
X3 0 2 1 1 0 0 100
X4 0 1 1 0 1 0 80
X5 0 1 0 0 0 1 40

Iteración 1

Z X1 X2 X3 X4 X5 RHS
Z 1 0 2 0 0 -3 -120
X3 0 0 1 1 0 -2 20
X4 0 0 1 0 1 -1 40
X1 0 1 0 0 0 1 40

Iteración 2

Z X1 X2 X3 X4 X5 RHS
Z 1 0 0 -2 0 1 -160
X2 0 0 1 1 0 -2 20
X4 0 0 0 -1 1 1 20
X1 0 1 0 0 0 1 40
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

Iteración 3

Z X1 X2 X3 X4 X5 RHS
Z 1 0 0 -1 -1 0 -180
X2 0 0 1 -1 2 0 60
X5 0 0 0 -1 1 1 20
X1 0 1 0 1 -1 0 20

Con los costos reducidos de X3 y X4 < 0, la solución es óptima única X1 = 20, X2 = 60 y valor objetivo
óptimo z = 180.

Problema 3
Minimizar z
s.a. z + 3 x1 + -x2 = 0
-4 x1 + 3 x2 + x3 = 36
x1 - x2 + x4 = 16
x1, x2 ≥ 0

Tableau inicial, con B= [a3, a4]

Z X1 X2 X3 X4 LD
Z 1 3 -1 0 0 0
X3 0 -4 3 1 0 36
X4 0 1 -1 0 1 16

Iteración 1

Z X1 X2 X3 X4 LD
Z 1 0 2 0 -3 48
X3 0 0 -1 1 4 100
X1 0 1 -1 0 1 16

1
Debido a que el vector 0, entonces el problema no acotado.
1
Universidad de Santiago de Chile
Facultad de Ingeniería
Métodos de Optimización en Ingeniería

GUÍA N°8: DUALIDAD

Profesor: Cristián Sepúlveda S.

Correo: [email protected]
Fecha: 04 de octubre de 2022

Problema 1

Determine el dual para los siguientes programas lineales.

Maximizar 5x1 + 3x2 = z Minimizar 2x1 - 4x2 = z

s.a. 3x1 + 7x2 ≤ 15 s.a. x1 + 5x2 ≤ 8
5x1 + 2x2 ≤ 10 -6x1 + 7x2 ≥ 3
x1, x2 ≥ 0 x1 - 2x2 = -2
x1 ≤ 0, x2 irrestricta

Problema 2

Dado el siguiente problema primal.

Maximizar 60x1 + 30x2 + 20x3 = zP

s.a. 8x1 + 6x2 + x3 ≤ 48
4x1 + 2x2 + 1.5x3 ≤ 20
2x1 + 1.5x2 + 0.5x3 ≤ 8
x1, x2, x3 ≥ 0

Siendo X = [2 0 8] y Y = [0 10 10] soluciones básicas factibles para el primal y dual

respectivamente. Verifique haciendo uso de la propiedad débil del dual, si las soluciones dadas son
óptimas.
Universidad de Santiago de Chile
Facultad de Ingeniería
Métodos de Optimización en Ingeniería

Problema 3

Para el siguiente problema primal, construya su correspondiente problema dual y resuelva

ambos mediante el método geométrico.

Minimizar - x1 - x2 = zP
s.a. x 1 - x2 ≥ 1
- x1 + x 2 ≥ 1
x1, x2 ≥ 0

Problema 4

Considere el siguiente programa lineal, con solución óptima de su dual y 1 = 4/5, y2 = 3/5.
Aplique el teorema de holgura complementaria para obtener la solución óptima del primal.

Minimizar 2x1 + 3x2 + 5x3 + 2x4 + 3x5 = zP

s.a. x1 + x2 + 2x3 + x4 + 3x5 ≥ 4
2x1 – 2x2 + 3x3 + x4 + x5 ≥ 3
x1, x2, x3, x4, x5≥ 0

Problema 5

Para el siguiente PL se ha sugerido X = [2 4 0 0 7 0] como solución óptima ¿Es correcto?

Minimizar 18x1 - 7x2 + 12x3 + 5x4 + 8x6 = zP

s.a. 2x1 - 6x2 + 2x3 + 7x4 + 3x5 + 8x6 ≤ 1
3x1 + x2 - 4x3 + 3x4 - x5 - 2x6 ≥ 2
8x1 - 3x2 + 5x3 - 2x4 + 2x6 ≤ 4
4x1 + 8x3 + 7x4 - x5 + 3x6 ≤ 1
5x1 + 2x2 - 3x3 + 6x4 - 2x5 - x6 ≤ 5
x1, x2, x3, x4, x5, x6≥ 0

Referencias:
Bazaraa, M., Jarvis, J., Sherali, H., Linear Programming and Network Flows, John Wiley & Sons, New
Jersey, 2010.
Ortiz, C., Varas, S., Vera J., Optimización y Modelos para la Gestión, Dolmen ediciones, 2002.
Universidad de Santiago de Chile
Facultad de Ingeniería
Métodos de Optimización en Ingeniería

Formulación del dual

Minimización Maximización
si la variable es: la restricción correspondiente es:

0 
0 
irrestricta =

si la restricción es: la variable asociada es:

 0
 0
= irrestricta

Teorema de holgura complementaria

Dado 𝑋 ∗ y 𝑌 ∗ soluciones básicas factibles del primal y del dual entonces ellas son óptimas SSI

i) 𝑐 − 𝑌 ∗ 𝑎 𝑋 ∗ = 0, 𝑗 = 1, … , 𝑛
ii) 𝑌∗ 𝑎 𝑋∗ − 𝑏 = 0, 𝑖 = 1, … , 𝑚
Problema 1
Problema 2
Problema 3
Problema 4
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

GUÍA nro. 9: MÉTODO SIMPLEX DUAL

Profesor: Cristián Sepúlveda S.

Correo: [email protected]
Fecha: 11 de octubre de 2022

Problema 1
Minimizar 2 x1 + 3 x2 + 4 x3 = z
s.a. x1 + 2 x2 + x3 ≥ 3
2 x 1 - x2 + 3 x3 ≥ 4
x1, x2, x3 ≥ 0

Problema 2
Maximizar - 4 x1 - 12 x2 - 18 x3 = z
s.a. x1 + 3 x3 ≥ 3
2 x2 + 2 x3 ≥ 5
x1, x2, x3 ≥ 0
UNIVERSIDAD DE SANTIAGO DE CHILE
FACULTAD DE INGENIERÍA
MÉTODOS DE OPTIMIZACIÓN EN INGENIERÍA

Z X1 X2 X3 X4 X5 LD
Z 1
0
0

Z X1 X2 X3 X4 X5 LD
Z 1
0
0

Z X1 X2 X3 X4 X5 LD
Z 1
0
0

Z X1 X2 X3 X4 X5 LD
Z 1
0
0

Z X1 X2 X3 X4 X5 LD
Z 1
0
0

Z X1 X2 X3 X4 X5 LD
Z 1
0
0
Guı́a 1 Modelamiento Universidad de Santiago de Chile
Métodos de Optimización Departamento de Informática
Prof. Cistián Sepúlveda S.

Problema 1
Resuelto en la presentación correspondiente a la clase 10.

Problema 2
maximizar − 4x1 − 12x2 − 18x3
s.a.x1 + 3x3 ≥ 3
2x2 + 2x3 ≥ 5
x1 , x2 , x3 ≥ 0

Estandarizar

minimizar 4x1 + 12x2 + 18x3

s.a. − x1 − 3x3 ≤ −3
−2x2 − 2x3 ≤ −5
x1 , x2 , x3 ≥ 0

minimizar z
s.a. z − 4x1 − 12x2 − 18x3 = 0
−x1 − 3x3 + x4 = −3
−2x2 − 2x3 + x5 = −5
x1 , x2 , x3 , x4 , x5 ≥ 0

Tableau inicial
z x1 x2 x3 x4 x5 LD
z 1 −4 −12 −18 0 0 0
x4 0 −1 0 −3 1 0 −3
x5 0 0 −2 −2 0 1 −5

x5 : variable que sale de la base (mı́nimo lado derecho negativo)

z −c
x2 : variable que ingresa a la base (mı́nimo jyrj j : yrj < 0)
y22 = −2 : elemento pivote

z x1 x2 x3 x4 x5 LD
z 1 −4 0 −6 0 −6 30
x4 0 −1 0 −3 1 0 −3
x2 0 0 1 1 0 −1/2 5/2

1
x4 : variable que sale de la base (mı́nimo lado derecho negativo)
z −c
x3 : variable que ingresa a la base (mı́nimo jyrj j : yrj < 0)
y13 = −3 : elemento pivote

z x1 x2 x3 x4 x5 LD
z 1 −2 0 0 −2 −6 36
x3 0 1/3 0 1 −1/3 0 1
x2 0 −1/3 1 0 1/3 −1/2 3/2

Solución del problema primal:

x1 = 0, x2 = 3/2, x3 = 1

Solución del problema dual:

y1 = 2, y2 = 6