IIND 2103 PRINCIPIOS DE OPTIMIZACIÓN

Departamento de Ingeniería Industrial

Facultad de Ingeniería

Preguntas de preparación – Examen Final 2024-10

Parte 1. Preguntas teóricas.

1. Para los literales 1.a – 1.c, determine si la afirmación es verdadera o falsa.

a. Todas las variables de un modelo de optimización lineal deben aparecer en la función

objetivo. Falso
b. Si existe alguna restricción de igualdad, no hay región factible. Falso
c. En todas las restricciones de un modelo de optimización lineal debe aparecer al
menos una variable. Verdadero

2. Si nos encontramos en una base factible en el problema primal, puede pasar que:

I. La base correspondiente en el problema dual sea infactible y nos encontramos en la

solución óptima.
II. La base correspondiente en el problema dual sea factible pero no nos encontramos en la
solución óptima.

a. I y II son verdaderas
b. I es verdadera y II es falsa
c. I es falsa y II es verdadera
d. I y II son falsas.

3. ¿Cuál de las siguientes afirmaciones es falsa sobre un problema de optimización lineal de

maximización y su respectivo problema dual?

a. Si se está parado sobre un punto en el problema primal que es factible y al revisar su

base correspondiente en el problema dual se encuentra que también es factible, este
es el óptimo de los dos problemas.
b. Si el problema primal es infactible, entonces el problema dual solo puede ser
infactible.
c. La función objetivo de puntos factibles del problema dual nunca puede ser menor a
la función objetivo de puntos factibles del problema primal.
d. Si el problema primal es no acotado, entonces el problema primal debe ser infactible.

4. Elija la afirmación correcta respecto al método de inicialización de dos fases.

a. Si los costos reducidos permiten declarar optimalidad en la primera fase, no es

necesario a llevar a cabo la segunda fase.
b. El método de dos fases tiene siempre una eficiencia inferior al método de la gran M,
puesto que no considera la función objetivo del problema original.
c. El sentido de optimización (min o max) de la primera fase no depende del sentido de
optimización de la segunda fase.
d. El número de variables artificiales a introducir en un método de inicialización
depende exclusivamente del número de variables de holgura con signo negativo que
se agreguen.

Universidad de los Andes | Vigilada Mineducación

Reconocimiento como Universidad: Decreto 1297 del 30 de mayo de 1964.
Reconocimiento personería jurídica: Resolución 28 del 23 de febrero de 1949 Minjusticia.
IIND 2103 PRINCIPIOS DE OPTIMIZACIÓN
Departamento de Ingeniería Industrial
Facultad de Ingeniería

Parte 2. Preguntas prácticas.

5. Considere el siguiente problema de optimización:

min 𝑧 = ∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗 + ∑ 𝑓𝑖 𝑦𝑖

𝑖∈𝑂 𝑗∈𝐷 𝑖∈𝑂
s. a,
∑ 𝑥𝑖𝑗 ≥ 𝑑𝑗 , ∀ 𝑗 ∈ 𝐷; b
𝑖∈𝑂

∑ 𝑥𝑖𝑗 ≤ 𝑀𝑦𝑖 , ∀ 𝑖 ∈ 𝑂; 4
𝑗∈𝐷
𝑥𝑖𝑗 ≤ 𝑘𝑖𝑗 , ∀ 𝑖 ∈ 𝑂, 𝑗 ∈ 𝐷 | 𝑖 < 𝑗 5 + u + 3 +
z =
14
∑ 𝑓𝑖 𝑦𝑖 ≤ 𝑏 1

𝑖∈𝑂
𝑦𝑖 ≥ 0, ∀ 𝑖 ∈ 𝑂;
𝑥𝑖𝑗 ≥ 0, ∀ 𝑖 ∈ 𝑂, 𝑗 ∈ 𝐷.

Además, se sabe que 𝑂 = {1,2,3,4} y 𝐷 = {1,2, … ,6}. Entonces, ¿cuántas restricciones tiene este
problema sin contar las restricciones de naturaleza de las variables?
a. 29
b. 28
c. 25
d. 35

6. Botes Tominé es una empresa que se dedica a la fabricación de botes de remo. La demanda
de botes para los próximos cuatro trimestres es de 40, 60, 75, y 25 botes, respectivamente.
Botes Tominé tiene la capacidad de producir estos botes en dos turnos (día y noche). La
capacidad de producción en cada uno de los dos turnos es de 40 botes. Por convención, se
asume que todos los botes producidos en un trimestre pueden ser utilizados para satisfacer
la demanda del mismo trimestre. Se desea formular un modelo de optimización lineal que
ayude a Botes Tominé a determinar cuántos botes debe producir en los próximos cuatro
trimestres. Sean 𝑥𝑡 y 𝑦𝑡 el número de botes que se producen en el horario diurno y nocturno
en el trimestre 𝑡, respectivamente. Sea 𝐼𝑡 el inventario de botes disponibles al final del
trimestre 𝑡. La expresión que representa el nivel de inventario al final del período 3 es:

a. 𝐼3 = 𝐼2 + 40 + 60
b. 𝐼4 = 𝐼3 + 𝑥3 + 𝑦3 − 75
c. 𝐼4 = 𝐼3 + 𝑥3 + 𝑦3 − 25
d. 𝐼3 = 𝐼2 + 𝑥3 + 𝑦3 − 75

7. Suponga un problema de optimización lineal con las siguientes restricciones y región factible
(en azul):

Universidad de los Andes | Vigilada Mineducación

Reconocimiento como Universidad: Decreto 1297 del 30 de mayo de 1964.
Reconocimiento personería jurídica: Resolución 28 del 23 de febrero de 1949 Minjusticia.
IIND 2103 PRINCIPIOS DE OPTIMIZACIÓN
Departamento de Ingeniería Industrial
Facultad de Ingeniería

1
Con base en el gradiente del problema, representado como el vector ( ), considere las siguientes
1
afirmaciones:

I. Los coeficientes que acompañan a 𝑥 y a 𝑦 en la función objetivo son iguales.

II. Se puede concluir que, sin importar el sentido de optimización, la solución del
problema siempre serán óptimos alternos.

a. I y II son verdaderas.
b. I es verdadera y II es falsa.
c. I es falsa y II es verdadera.
d. I y II son falsas.

8. Considere la siguiente región factible resaltada en azul. Sean 𝑥3 , … , 𝑥7 las variables de

holgura asociadas a las restricciones 𝑅1 , 𝑅2 , 𝑅3 , 𝑅4 y 𝑅5 , respectivamente.

Partiendo de la solución básica marcada con el punto rojo y realizando un movimiento en la

dirección marcada de rojo ¿Cuál variable aumenta su valor? ¿Cuál variable reduce su valor?

Universidad de los Andes | Vigilada Mineducación

Reconocimiento como Universidad: Decreto 1297 del 30 de mayo de 1964.
Reconocimiento personería jurídica: Resolución 28 del 23 de febrero de 1949 Minjusticia.
IIND 2103 PRINCIPIOS DE OPTIMIZACIÓN
Departamento de Ingeniería Industrial
Facultad de Ingeniería

a. 𝑥4 aumenta su valor y 𝑥6 reduce su valor

b. 𝑥6 aumenta su valor y 𝑥4 reduce su valor
c. 𝑥2 aumenta su valor y 𝑥4 reduce su valor
d. 𝑥4 aumenta su valor y 𝑥2 reduce su valor

9. Considere el siguiente problema de optimización lineal:

max 10𝑥1 − 12𝑥2 + 15𝑥3 − 2𝑥4

s. a, 𝑥1 + 2𝑥2 + 5𝑥3 − 𝑥4 ≥ 6
3𝑥1 + 2𝑥3 ≤ −2
𝑥3 + 𝑥4 ≤ 3
5𝑥2 + 3𝑥3 + 2𝑥4 ≥ 10
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

¿Cuál(es) de las siguientes opciones representa(n) el problema en formato estándar?

a.
max 10𝑥1 − 12𝑥2 + 15𝑥3 − 2𝑥4 + 0𝑠1 + 0𝑠2 + 0𝑠3 + 0𝑠4
s. a, 𝑥1 + 2𝑥2 + 5𝑥3 − 𝑥4 − 𝑠1 = 6
−3𝑥1 − 2𝑥3 − 𝑠2 = 2
𝑥3 + 𝑥4 + 𝑠3 = 3
5𝑥2 + 3𝑥3 + 2𝑥4 − 𝑠4 = 10
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑠1 , 𝑠2 , 𝑠3 , 𝑠4 ≥ 0

b.
max 10𝑥1 − 12𝑥2 + 15𝑥3 − 2𝑥4 + 0𝑠1 + 0𝑠2 + 0𝑠3 + 0𝑠4
s. a, 𝑥1 + 2𝑥2 + 5𝑥3 − 𝑥4 + 𝑠1 = 6
−3𝑥1 − 2𝑥3 + 𝑠2 = 2
𝑥3 + 𝑥4 + 𝑠3 = 3
5𝑥2 + 3𝑥3 + 2𝑥4 − 𝑠4 = 10
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑠1 , 𝑠2 , 𝑠3 , 𝑠4 ≥ 0

c.
max 10𝑥1 − 12𝑥2 + 15𝑥3 − 2𝑥4 + 0𝑠1 + 0𝑠2 + 0𝑠3 + 0𝑠4
s. a, 𝑥1 + 2𝑥2 + 5𝑥3 − 𝑥4 − 𝑠1 = 6
−3𝑥1 − 2𝑥3 + 𝑠2 = −2
𝑥3 + 𝑥4 + 𝑠3 = 3
5𝑥2 + 3𝑥3 + 2𝑥4 − 𝑠4 = 10
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑠1 , 𝑠2 , 𝑠3 , 𝑠4 ≥ 0

d.

Universidad de los Andes | Vigilada Mineducación

Reconocimiento como Universidad: Decreto 1297 del 30 de mayo de 1964.
Reconocimiento personería jurídica: Resolución 28 del 23 de febrero de 1949 Minjusticia.
IIND 2103 PRINCIPIOS DE OPTIMIZACIÓN
Departamento de Ingeniería Industrial
Facultad de Ingeniería

max 10𝑥1 − 12𝑥2 + 15𝑥3 − 2𝑥4 + 0𝑠1 + 0𝑠2 + 0𝑠3 + 0𝑠4

s. a, 𝑥1 + 2𝑥2 + 5𝑥3 − 𝑥4 − 𝑠1 = 6
3𝑥1 + 2𝑥3 + 𝑠2 = −2
𝑥3 + 𝑥4 + 𝑠3 = 3
5𝑥2 + 3𝑥3 + 2𝑥4 − 𝑠4 = 10
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑠1 , 𝑠2 , 𝑠3 , 𝑠4 ≥ 0

10. Cementos Arquos usa el material X en la producción de cemento. En un problema de

optimización lineal donde se busca maximizar los ingresos de la empresa, el precio sombra
del material es de $200,000 pesos por kilogramo.

¿La empresa estaría dispuesta a pagar $150,000 pesos por un kilogramo adicional del material
X?
a. Verdadero.
b. Falso.

11. En una iteración intermedia del método Simplex sobre un problema de maximización, se
cuenta con la siguiente información:

𝐼𝐵 = {2,3} 𝐼𝑁 = {1,4}

𝐫 𝑇 = [0 0 ⋮ go
2.5 −2.5]
2 0 1 1 1/2 0
𝐁=[ ] 𝐍=[ ] 𝐁−𝟏 = [ ]
3/7 1 1 0 −3/14 1
𝑢
𝑣
𝐝𝑞 = [ _ _ _ ]
?
?
a =

[i]
Los valores de 𝑢 y 𝑣 son:

a. 𝑢 = − 2
1
y 𝑣 = 14
3
d=
-
Ba

( . ] (i)
1 11
b. 𝑢 = − 2 y 𝑣 = − 14 =
10
c. 𝑢 = −2 y 𝑣=−
7
3

[] [in]
d. 𝑢 = −2 y 𝑣= −7
=

12. Una firma debe decidir invertir o no en cada proyecto 𝑗 de su portafolio de proyectos 𝐽. La
firma debe tener en cuenta que cada proyecto 𝑗 ∈ 𝐽 requiere de una cantidad de recursos de
tipo 𝑖 ∈ 𝐼. Sin embargo, cada recurso es limitado, por lo que las decisiones que se tomen
deben tener en cuenta la disponibilidad de cada recurso. Seleccione la mejor manera de
modelar la situación anterior:

Universidad de los Andes | Vigilada Mineducación

Reconocimiento como Universidad: Decreto 1297 del 30 de mayo de 1964.
Reconocimiento personería jurídica: Resolución 28 del 23 de febrero de 1949 Minjusticia.
IIND 2103 PRINCIPIOS DE OPTIMIZACIÓN
Departamento de Ingeniería Industrial
Facultad de Ingeniería

a. b.

𝑎𝑖𝑗 : cantidad de recursos 𝑖 ∈ 𝐼 que requiere el 𝑎𝑖𝑗 : cantidad de recursos 𝑖 ∈ 𝐼 que requiere el
proyecto 𝑗 ∈ 𝐽 proyecto 𝑗 ∈ 𝐽
𝑥𝑖𝑗 : variable binaria. Toma el valor de 1 si se 𝑥𝑗 : variable binaria. Toma el valor de 1 si se
decide invertir el recurso 𝑖 ∈ 𝐼 en el proyecto decide invertir en el proyecto 𝑗 ∈ 𝐽, 0 𝑑. 𝑙. 𝑐.
𝑗 ∈ 𝐽, 0 𝑑. 𝑙. 𝑐. 𝑏𝑖 : cantidad disponible del recurso 𝑖 ∈ 𝐼
𝑏𝑗 : cantidad disponible para invertir en el
proyecto 𝑗 ∈ 𝐽 ∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 , ∀ 𝑖 ∈ 𝐼
𝑗∈𝐽
∑ ∑ 𝑎𝑖𝑗 𝑥𝑖𝑗 ≤ 𝑏𝑗 , ∀𝑖 ∈ 𝐼
𝑖∈𝐼 𝑗∈𝐽

c. d.

𝑎𝑖𝑗 : cantidad de recursos 𝑖 ∈ 𝐼 que requiere el 𝑎𝑖𝑗 : cantidad de recursos 𝑖 ∈ 𝐼 que requiere el
proyecto 𝑗 ∈ 𝐽 proyecto 𝑗 ∈ 𝐽
𝑥𝑖 : cantidad del recurso 𝑖 ∈ 𝐼 a invertir 𝑥𝑗 : cantidad a invertir en el proyecto 𝑗 ∈ 𝐽
𝑏𝑗 : cantidad disponible para invertir en el 𝑏𝑖 : cantidad disponible del recurso 𝑖 ∈ 𝐼
proyecto 𝑗 ∈ 𝐽
∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 , ∀ 𝑗 ∈ 𝐽
∑ 𝑎𝑖𝑗 𝑥𝑖 ≤ 𝑏𝑗 , ∀ 𝑗 ∈ 𝐽 𝑗∈𝐽
𝑖∈𝐼

13. MIC es una empresa que se dedica a la fabricación de productos farmacéuticos. La gerencia
de MIC ha formulado un modelo de optimización lineal que le permite planear la producción
mensual buscando maximizar su utilidad. Este modelo considera que no se puede usar más
de 𝑘 miles de litros de uno de los insumos. ¿Cuál de las siguientes gráficas describe de mejor
forma el comportamiento de la máxima utilidad que recibirá MIC para diferentes valores de
𝑘?

a. b.

6000 6.000

5000 5.000
Máxima utilidad ($)
Máxima utilidad ($)

4000 4.000

3000 3.000

2000 2.000

1000 1.000

0 0
0 3 6 9 12 0 3 6 9 12
k (miles de litros) k (miles de litros)

Universidad de los Andes | Vigilada Mineducación

Reconocimiento como Universidad: Decreto 1297 del 30 de mayo de 1964.
Reconocimiento personería jurídica: Resolución 28 del 23 de febrero de 1949 Minjusticia.
IIND 2103 PRINCIPIOS DE OPTIMIZACIÓN
Departamento de Ingeniería Industrial
Facultad de Ingeniería

c. d.

6000 6000
5000 5000
Máxima utilidad ($)

Máxima utilidad ($)

4000 4000

3000 3000

2000 2000

1000 1000

0 0
0 3 6 9 12 0 3 6 9 12
k (miles de litros) k (miles de litros)

14. Considere el siguiente problema de optimización no lineal:

max 2𝑥1 + 𝑥22

s. a, −𝑥1 + 𝑥2 ≤ 1
𝑥1 + 𝑥2 ≤ 4
𝑥1 , 𝑥2 ≥ 0

Usted decide resolver el problema utilizando un procedimiento de búsqueda local, en el que

el vecindario asociado a una solución factible 𝕩𝑡 en la iteración 𝑡 está dado por los puntos
que están a una unidad de distancia horizontal o vertical del punto inicial. A manera de
ejemplo, el vecindario del punto rojo en la imagen a continuación son los puntos verdes:

1.5
En la iteración 1 del procedimiento, la solución evaluada es 𝕩1 = [ ]. Se puede afirmar
2
que:
e. Ha encontrado un óptimo global en la iteración 1. X
f. Ha encontrado un óptimo local en la iteración 1.
1.5
g. 𝕩2 = [ ] X fo menor
1
0.5
h. 𝕩2 = [ ] X RI
3

Universidad de los Andes | Vigilada Mineducación

Reconocimiento como Universidad: Decreto 1297 del 30 de mayo de 1964.
Reconocimiento personería jurídica: Resolución 28 del 23 de febrero de 1949 Minjusticia.
Chocolateria :

Conjuntos :

C :
tipos de chocolates ; C =
E chocolate oscuro ,
chocolate blancos

I :
tipos de ingrediente ; I =
E manteca de cacao
o azucar]

Parametros :

p
:
peso de 1 unidad de chocolate ; p
=
60g
ceC
.
Ve : precio de venta de 1 unidad del chocolate

: costos asociados a
produccion de 1 unidad del chocolate c C .

Ki : cantidad disponible de cada ingrediente i I .

da : demanda semanal del chocolate <C

.

No, i : cantidad requerida del ingrediente iel

para producir el chocolate ceC .

Variables de decision

Xc : cantidad producida del chocolate cEC semanalmente .

Funcion objetivo :

maximizar utilidad

VeXc C Xa
-
:

max

ce Ct2

Restricciones :

1) Naturaleza variables

Xc10 XcEC

2) Cumplir con la demanda

Xc]dcVc C

LimitedeCantidad disponible de ingredients

3) a

CEC
Produccion de jugos :

Conjuntos :

K conjunto de
jugos autoctonos
:
.

R :
conjunto de frutas tropicales .

Parametros :

lki :
porcentaje minimo de la fruta i ER en el jugo Kek .

Uki : porcentaje maximo de la fruta i ER en el jugo Kef

.

bi : litros disponibles del zumo de la fruta i R .

dk : demanda minima de litros del jugo KEK.

PK :
precio de venta de un litro de jugo KEK.

Variables de decision.

Xki cantidad de litros del de la fruta ieR producir el KEK

: zumo
para jugo
.

Funcion objetivo :

maximizar ingresos.

max
PkXki
kek ver

Restricciones :

1) Naturaleza variables

Xk :20 .
X kek ,
itR

2) Porcentaje de zumo de la fruta itR del

jugo KEK
.

Xi &k ,
i Xki Vktk
,
itR
jER

Xi Uki Xk = Vkek ,
itR
jeR

3) Litros disponible

Yi bi VieR
kek

u) cumplir demanda

* kidk kek
.

·r
Transporte de productos lacteos :

Conjuntos :

P :
conjunto de plantas de produccion.
C :
conjunto de clientes

Parametros :

de : demanda mensual del cliente ceC .

(litros)

tpc : costo de transporte desde la planta peP hasta el cliente cel .

Kp :
capacidad de produccion de la planta peD . (Fro.

Variables de decision :

Xp c
: cantidad enviada desde la planta pep hasta el cliente cEC Clitros)
,

Funcion objetivo :

minimizar costos

min
Epic Xpic
Dep cec

Restricciones :

1) Naturaleza de variables

Xp . c 10 Vptp ,
C

2) Limite de capacidad de produccion

Xp c Kp
,
V pe P
JEC

3) Cumplir demanda

Xpi]da YcC
pEP
Produccion de cemento :

Conjuntos
S :
conjunto de semanas .

Parametros :

costo de produccion tonelada la seS

.
Ps :
por en semana

as costo de almacenamiento tonelada en la semana seS

:
por

ds : demanda (toneladas) en la semana .

seS

Us :
precio de venta por tonelada en la semana seS
.

10 : inventario inicial ; io =
12
, 000 toneladas
.

l : limite maximo a producir ; l =

110 , 000 toneladas.

m : limite minimo a producir ; m = 85 000

,
toneladas .

Variables de decision

Xs : cantidad de toneladas a producir en la semana .

seS

is : inventario final de la semana .

seS

Funcion objetivo :

maximizar utilidad

max
seg
Usds-PsXs -

As is

Restricciones

1) Naturaleza de variables

Xs0 VseS

is 10 VseS

2) Inventarios

In 20 = +
X1 -

Is =
is -
1
+
Xs- ds VieS) is 1

3) Limites de produccion

X 1lVstS

Xs ] m YstS
Planeacion de menus :

Conjuntos :

T conjunto de
grupos alimenticios
:
.

A :
conjunto de alimentos .

N :
conjunto de nutrientes.

Parametros :

In : cantidad minima del nutriente n EN que el menu debe contener .

ca
: costo por
100 del alimento a EA
g .

Kan cantidad del nutriente nEN que contiene del alimento EA

:
100 g a .

A alimenticio t

Co elalimento
T

ena
esta E .
si a
grupo
:
Paz

Variables de decision :

cantidad de de del alimento A

Xa :
porciones 100g ae
para incluir en el menu .

funcion objetivo :

min Ca Xa
aea

Restricciones :

1) Incluir exactamente una porcion de

100g, entre los alimentos,
para cada giupo
alimenticio :

Xa =
1 ,
f + ET
atAlpat = 1

2) Se debe complis con con la cantidad requerida de cada nutriente :

* In VneN
aakariXa ,

3) Naturaleza variables :

Xa = 0 ,
FatA
Asignacion de tareas :

Conjuntos :

M :
conjunto de miembros del equipo.

R :
conjunto de responsabilidades.

Parametros :

Emr Choras) que demora mem la rER

:
tiempo se el miembro en hacer
responsabilidad .

dm :
disponibilidad horaria del miembro m =M
.

Pmr
: indice de preferencia del miembro meM para haver la
responsabilidad reR
.

Variables de decision :

[1
la -ER le mem
Xmr :
,
si
responsabilidad se
asigna al miembro

G
d I . . .
C

Funcion objetivo :

max
Pmr
·

Xmr
mem rem

Restricciones :

1) No sobrepasar disponibilidad de los miembros :

tur ·

Xmrdm ,
.
V meM
VER

2) Cada responsabilidad debe ser asignada a solo una persona :

Xmr = 1 ,
VER
mEM

3) Naturaleza de variables :

Xmr =
[0 , 13 ,
V meM
,
rER .
Extraccion minera :

Conjuntos :

M :
conjunto de zonas .

K :
conjunto de tipos de carbon .

Parametros :

carbon del
puede extraer tipo
ESelazona
em se

dij :

Ci : costo de extrae 1 tonelada de carbon en la zona itM

.

ni :
capacidad maxima de extraccion de la zona .
itM

bj : cantidad minima de toneladas a extraer del carbonjek

Variables de decision :

Xi : cantidad de carbon a extraer en la zona itM

.

Funcion objetivo :

min Ci ·
Xi
iEM

Restricciones :

1) Complir con la cantidad minima a extraer .

Xi = bj ,
v jtk
ima =

2) No sobrepasar la cantidad de extraccion de cada zona

.

Xi 1 ni ,
VitM

3) Naturaleza variables

X : 10 ,
f itM
.
Salsa al Parque :

Conjuntos :

A :
conjunto de artistas .

H :
conjunto de horas .

Parametros :

& it : audiendia pronosticada para el artista itA en la hora teH.

di :
duracion de la presentacion del artista veA .

Variables de decision :

S
Xit : 1. si el artista itA inicia la presentacion en la hora tel.

O ,
d l .
.

(1 el artista lea durante la tel.

Yiz
:
, si se presenta hora

O ,
d .
l . .
c

Funcion objetivo :

max & it Yit

·

itA th

Restricciones :

1) todos los artistas se presentan una sola vez :

Xit = 1 Vit A
t = It

2) Max dos artistas se pueden presenta en la misma hora

.

Yit I V t H
it A

3) consecutividad de presentaciones
presentase desde de
·

en horas consecutivas el inicio su

presentacion :

t + di - 1

VitA
Yij - di Xit to H1 t + di 11 (H)
-

, ,
jtt

presentar exactamente las horas que dura la presentacion :

Yit = di ,
FitA
tCH

·
no iniciar presentacion si no hay tiempo suficiente
.

Xit =
0 ,
VitA ,
tH)t + di =
1>(H)

4) Naturaleza variables :

Xit , Yi
= [1 03, ,
FitA ,
FtH
Introducción

supuestos

ProporcionalidadNovariableselevadas en . en
Divisibilidadlasvariabledebenserfraccionariosraesa tan las variables de decision se deben conocer con certeza

Tipos de solución

Optimo unico : Un punto optimo

Optimo acotado :
Multiples soluciones ,
se ven en una recta especifica

Optimo no acotado :
Multiples soluciones
, no se
pueden delimitar . Optimo infinito

Infactible soluciones
: No
hay para el problema .

Indexación restricciones

·
Para calcular el numero de restricciones

↳ El
Un para todo : número de elementos del conjunto
↳ elementos
Mas de un para todo : Producto de la cantidad de de los conjuntos.

↳
Tal contar
que uno a una

Metodo grafico

Conceptos

Gradiente vector derivadas do

de parciales
,
do
:
g
=
,
dy

Isoclinas : rectas perpendiculares al gradiente

Procedimiento

·
Graficar restricciones ( = )

·
Identificar region factible

Graficar gradiente a isoclinas

·
Concluir :

↳
Maximización : Recorrer la region factible en la dirección del
gradiente, el último punto que toque una isoclina es el optimo

↳
Minimización : Recorrer la region factible en la dirección contraria al
gradiente, el último punto que toque una isoclina es el optimo

Estructuras comunes

Balance

pep Xp YP VpeP
=

pep

Todo lo
que
entra sale

Mezcla

·
Xa & Xi Fact
in

Cuando piden una proporción

Inventarios

Restricción de inventario

↳
t = 1 : ( +
xx
-

v =
it ft eT(t = 1

↳
t >
:
(t -
+ Xt- re = it SteT1 + >1

Inventario positivo
↳
*
t = 1 (
:
+ X+ = rt VteTlt =

t 1 :
(t + X2 Ut XteTlty
Busqueda Local

Procedimiento

Graficar la
región factible

*
Encontrar una solución factible (x .
1

·
Explorar el vecindario de Xt

+
-
Si en el vecindario se puede mejorar la función objetivo me muevo a ese punto (X )
y
vuelvo al paso
.
2

Si no se puede mejorar , estoy en un optimo local.

Paradigma de busqueda

Si un de determinada dirección, puedo llegar a

función objetivo
numero
mejor
me una una
nuevo pasos en .

Dirección

·
Determina hacia donde me muevo

↑
Notación : X

Dirección factible X viola restricción

10X no
ninguna
· :
+

·
Dirección de
mejora : Fo (x + + xx) Fo(x +
)

·
me muevo

Siempre debe ser positiva (220)

·
Pasos para determinar a

↳
+
Reemplazar X por X + 10 X en las restricciones

↳
Reemplazar el valor de X

↳
cada restriccion
Despejar 1 en
y escoger

#X debe ser una dirección factible y

a positivo .

Formatos

Canonico

Problemas de maximización : Restricciones de menor o

igual

·
problemas de minimización Restricciones de
igual
mayor
:
o

¿ Como pasar restricciones ?

↳
Menor o
igual a
mayor o
igual y
viceversa :
Multiplicar por -1

↳
Igualdad Se
:
separa en una de menor o
Igual y
otra de
mayor o
igual .

Formato estandar

Matricial

·
Variables de decisión : vector X
X Xz
.

,
...

*
7

·
coeficientes lado izquierdo de las restricciones : Matriz A "

Coeficientes en la función objetivo : vector c

Función objetivo : cT .

X
.

Conceptos de optimización lineal

Holguras
~
-
Son variables de decision que muestran que tan lejos está un punto de una restricción
 ·
a esa restricción es 0 .

Punto extremo

Para un problema de u variables y m restricciones

.

un punto es extremo si
hay n o más restricciones activas

·
Un punto extremo siempre es factible .

Bases

Para contrar factible puedo valores de variables de decision

en una solución
asignar
0 a
algunas

Si variable de decisión tiene valor de o está la base vector

una em en no .
Se
organizan en el XN

Matriz B :
Se toman las X basicas de la matriz A .

Matriz N Se
: toman las X no basicas de la matriz A .

Costos basicos (C) : Costos de las X basicas

.

Costos no basicos ([ñ) : Costos de las x no basicas

.

· Función objetivo :
Cis .

Restricciones :
BXB = .
6 b . B" = XB

Metodo simplex

·
Es una
busqueda local solo con los puntos extremos . Cuenta con 5 pasos .

↳ 1 .
Situacion inicial

↳
.
2 Prueba de optimalidad

↳ .
3 Dirección de movimiento

↳ 4
. Longitud de movimiento

↳ 3
. Actualización

Situación inicial

Determinar las matrices A B B" N XB el valor de la Fo

, , , , y

Prueba de optimalidad

·
Determina si el punto actual es el optimo .

· Calcular los multiplicadores simplex. WT = Ci B .

Calcular
· los costos reducidos rT = wiN -
c

Si el costo reducido de una variable es positivo, ingresarlo a la base aumenta la FO

,
si es
negativo la
disminuye .

Maximización :
entre los positivos entra el
mayor ,
si solo
hay negativos estoy en el optimo .

Dirección de movimiento

Después de variable entra la base se calcula el vector de dirección de movimiento

escoger que a
,

· Este vector describe el movimiento favorece la entrada de variable de decision la base

que una a

dq
-BAq donde Aq la columna la matriz A vector
X
de corresponde la variable entra la base de 1 0
que que y es un
que
=
es a a
y ,
XN

es 1 si la variable no basica entra a la base

,
O si no .
Solo pueden salir las XB que sean
negativas en este vector
.

Longitud de movimiento

se utiliza la prueba de la razón minima

para determinar que variable sale de la base
·
XB %. b Quiero la base la identidad B"b 1 b de vector
B 0
.
siempre XB20
que sea para que
= = .
un
.

todos positivos restricciones de meto las variables artificiales

Dejo los b
y
en las
holguras negativas o
igualdad .

Base :
Holguras positivas y
variables artificiales .

Dos fases

fase 1

las restricciones tenía

Minimizar variables adicionales sujeto a las
que ya .

Si al final Xa = 0 es infactible .
Si xa = o
sigo a la fase 2 .

fase 2

solucionar problema de optimización

Gran M

Asignar costos negativos si

estoy maximizando
,
positivos si
estoy minimizando .

Resolver hasta que ya

salgan de la base .
Si
algun XaFo es infactible.

Dualidad

Como sacar un problema dual

El problema dual es el transpuesto del dual .

Si el problema primal es de maximización

, el dual es de minimización
y
viceversa

El numero de restricciones del dual es el numero de variables del primal.

El numero de variables del dual es el numero de restricciones del primal .

Interpretación economica

Solo se
puede con variables continuas

La variable dual de una restricción muestra el cambio en la F O

.
si la disponibilidad del recurso aumenta una unidad

↳
Recurso abundante : W =

↳ Recurso Wo
escaso :

. Es una forma de ver como se valoran los recursos

losmultiplicadoressimplexsonlas variablesdualesa contrario no

Teoremas de dualidad

Teorema de dualidad debil

· zmin zmax optimo

[
min

...........................
max

zmin
optimo min
- [

max znatimo

Dual

Optimo Infactible No acotado

Optimo
-

Infactible
No acotado
 Holgura complementaria
·
Relaciona una base del primal con su correspondiente del dual .

Se cumplen X .

r = o
y
W .

s =
0

Condiciones KKT

↑
-
Se puede declarar optimalidad si se cumplen las
siguientes condiciones

↳
solución factible en el primal y en el dual

↳ Bases relacionadas complementaria

con holgura

Sensibilidad

·
solo puede hacer variables continuas el optimo
y
se con en

sensibilidad de recurso

·¿ Que pasa con mis variables de decisión si la disponibilidad de un recurso cambia ?

Procedimiento

Plantear 6 : se le suma una variable e al recurso de interés .

Encontrar XB con la ecuación XB = B.b ,

en este caso Xis = B" (b + -

Plantear desigualdades :
XBL o
para que la base no cambie

Encontrar de Q
rango
·
.

En de e la base mantiene
ese
rango se
.

Graficas maximizacion

Restricción de Restricción de
igual
r

menor o
igual mayor o

Fo FO

recurso recurso

Graficas minimización

Restricción de
igual Restricción de
menor o
mayor o
igual

Sensibilidad de costos

¿ Que pasa con mis variables de decisión si el costo de una variable de decision cambia ?

Procedimiento

Plantear C : se le suma una variable o al costo de interés .

·
Encontrar rí con la ecuación r = -C B" .

N
,
en este caso rí =
ci -

Kis + e) .
BN

. Plantear desigualdades : Si es un problema de maximización 0. Si es de minimización ro

Encontrar de
rango .
· E
QUICES :

·
#
 *

·
 *

·
·
·
 #

·
 Xy = 0
#
Xy = 0

IB [2
=
,
3 ,
5, 63

·
 *
Xs = 0

Xy = 0

IB =
52 3
, ,
4, 63

·
 *
Xy = 0

Xs = 0

IB [7
=
,
2 3
, ,
63
 #

·
·

min
G min G

⑧
*
*
 *

⑧
 #

⑨
 *