Aplicacions per a la presa de decisions | Repte 1

Pregunta 1

Enunciat

Una empresa dissenya un nou pla de distribució publicitària per maximitzar l’audiència total. Té tres canals disponibles (A, B i C) amb els següents costos i audiències:

• Canal A: cost 80.000€, audiència per anunci 15.000 persones.
• Canal B: cost 150.000€, audiència per anunci 28.000 persones.
• Canal C: cost 5.000€, audiència per anunci 8.000 persones.

Condicions:

• Pressupost màxim: 600.000€.
• Màxim 3 anuncis al canal B.
• Com a mínim el 15% dels anuncis han de ser al canal A.
• El nombre d’anuncis al canal C no pot ser més gran que la suma dels altres dos.

Formuleu i resolgueu el problema de programació lineal per maximitzar l’audiència.

RESPOSTA:

Sabem que aquest és un problema clàssic de programació lineal per prendre decisions, on el nostre objectiu és aconseguir maximitzar l’audiència total.

El primer que hem de fer és extreure, o enunciar, les nostres variables, la funció objectiu i les restriccions.

Variables:

• \(x_a\): nombre d’anuncis que emetrem al canal A

• \(x_b\): nombre d’anuncis que emetrem al canal B

• \(x_c\): nombre d’anuncis que emetrem al canal C

Funció objectiu:

Com hem dit abans, el nostre objectiu és maximitzar l’audiència total tot considerant l’audiència per persona de cadascún dels canals disponibles. Per tant:

\[ \text{max } Z = 15.000 \cdot x_A + 28.000 \cdot x_B + 8.000 \cdot x_C \]

Restriccions:

En funció de les consicions que hi consten a l’enunciat hem de definir la implicació d’aquestes en forma de restricció:

1. Pressupost: s’estableix un pressupost màxim de 600.000€, és a dir, que el cost total dels tres anuncis no pot superar aquesta quantitat. Sabem que pel canal A el cost és de 80.000€, pel canal B és de 150.000€ i pel canal C 5.000€, podem establir la restricció de pressupost de la segünet manera:

   \[ 80.000 \cdot x_A + 150.000 \cdot x_B + 5.000 \cdot x_C \leq 600.000 \]

2. Màxim 3 anuncis al canal B

   \[ x_b \le 3 \]

3. Com a mínim el 15% dels anuncis han de ser al canal A

   \[ x_A \geq 0.15 \cdot (x_A + x_B + x_C) \]

   Ara bé, hem de “convertir” aquesta equació a la forma lineal:

   \[ 85x_A - 15x_B - 15x_c \geq 0 \]

   Podem dividir entre 5 i transformar a la forma menor o igual que 0:

   \[ 3x_B + 3x_C - 17x_A \leq 0 \]

4. El nombre total d’anuncis al canal C no pot ser més gran que la suma dels altres dos

\[ x_C \leq x_A +x_B \]

I convertim a la forma que ens va bé:

\[ x_C - x_A -x_B\leq 0 \]

5. No negativitat: totes les variables han de ser majors que 0 (no podem fer anuncis negatius)

   \[ x_A, x_B, x_C \geq 0 \]

6. A més, com que no es poden emetre porcions d’anuncis, sabem també que les variables han de ser nombres enters

Un cop establertes les restriccions ho hem de convinar tot, obtenint:

\[ \max_{x_A,x_B,x_C} Z(x_A,x_B,x_C) = 15.000 \cdot x_A + 28.000 \cdot x_B + 8.000 \cdot x_C \]

Subjecte a les restriccions:
\[ \Bigg\{ \begin{align} 80.000 \cdot x_A + 150.000 \cdot x_B + 5.000 \cdot x_C \leq 600.000 \\ x_B \leq 3 \\ 3x_B + 3x_C - 17x_A \leq 0 \\ x_C - x_A -x_B\leq 0 \\ x_A, x_B, x_C \geq 0 \end{align} \]

Un cop ben formulat el problema, farem servir el mètode Simplex per tal de resoldre’l.

Aquest mètode ens ajudarà a trobar els valors òptims de les tres variables tenint en compte les restriccions definides.

# Carreguem llibreries
rm(list=ls())
.packages <- c("lpSolveAPI")
.unavailable <- setdiff(.packages, rownames(installed.packages()))
install.packages(.unavailable)
invisible(lapply(.packages, library, character.only = TRUE))

Warning: package 'lpSolveAPI' was built under R version 4.3.3

# Creem el model
model <- make.lp(0, 3)

# Com que volem maximitzar, el tipus d'optimització serà "max"
lp.control(model, sense="max")

$anti.degen
[1] "fixedvars" "stalling" 

$basis.crash
[1] "none"

$bb.depthlimit
[1] -50

$bb.floorfirst
[1] "automatic"

$bb.rule
[1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 

$break.at.first
[1] FALSE

$break.at.value
[1] 1e+30

$epsilon
      epsb       epsd      epsel     epsint epsperturb   epspivot 
     1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 

$improve
[1] "dualfeas" "thetagap"

$infinite
[1] 1e+30

$maxpivot
[1] 250

$mip.gap
absolute relative 
   1e-11    1e-11 

$negrange
[1] -1e+06

$obj.in.basis
[1] TRUE

$pivoting
[1] "devex"    "adaptive"

$presolve
[1] "none"

$scalelimit
[1] 5

$scaling
[1] "geometric"   "equilibrate" "integers"   

$sense
[1] "maximize"

$simplextype
[1] "dual"   "primal"

$timeout
[1] 0

$verbose
[1] "neutral"

# Definim funció
set.objfn(model, c(15000,28000,8000))

# Definim les restriccions
add.constraint(model, c(80000,150000,5000), "<=", 600000) #R1
add.constraint(model, c(0,1,0), "<=", 3) #R2
add.constraint(model, c(-17,3,3), "<=", 0) #R3
add.constraint(model, c(-1,-1,1), "<=", 0) #R4
add.constraint(model, c(1,0,0), ">=", 0) #R5
add.constraint(model, c(0,1,0), ">=", 0) #R5
add.constraint(model, c(0,0,1), ">=", 0) #R5

# Fixem el tipus de variables (nombres enters) R6
set.type(model, 1, "integer")
set.type(model, 2, "integer")
set.type(model, 3, "integer")

# Validem el model
model

Model name: 
              C1      C2      C3           
Maximize   15000   28000    8000           
R1         80000  150000    5000  <=  6e+05
R2             0       1       0  <=      3
R3           -17       3       3  <=      0
R4            -1      -1       1  <=      0
R5             1       0       0  >=      0
R6             0       1       0  >=      0
R7             0       0       1  >=      0
Kind         Std     Std     Std           
Type         Int     Int     Int           
Upper        Inf     Inf     Inf           
Lower          0       0       0           

Un cop definit i validat el model, el podem resoldre per recuperar la informació i veure els resultats:

# Resolem model
solve(model)

[1] 0

# Obtenim els valors
get.objective(model)

[1] 161000

get.variables(model)

[1] 7 0 7

Veiem que el problema es resol correctament i ens dona els següents resultats:

• 161.000 és el valor màxim de la funció objectiu, és a dir, de la nostra audiència màxima que podem aconseguir.

• 7 0 7 és el vector de valors retornat i representa el nombre òptim d’anuncis per a cada canal ( 7 anuncis canal A, cap anunci canal B i 7 anuncis canal C)

Podem comprovar que amb aquests valors es compleixen les restriccions, ja que:

\[ 7 * 80000 + 0* 150000 + 7* 5000 = 595000 \]

és a dir, menor que els 600.000€ de pressupost.

La segona restricció també és compleix ja que 0<3, i pel que fa a la tercera també, ja que 7 de 14 anuncis representen més d’un 15%.

A més totes les variables són nombres enters i no negatius.

Pregunta 2

Enunciat

Les empreses poden gestionar inventaris mitjançant diversos models. Els dos més coneguts són EOQ i EPQ. Elabora una comparació detallada entre els models EOQ i EPQ tenint en compte: fonaments, supòsits, aplicabilitat, impacte en la gestió d’inventari i limitacions.

RESPOSTA

Pregunta 3

Enunciat

TechSpare vol optimitzar la gestió de bateries per ordinadors. Té una demanda anual de 15.000 unitats. Cada comanda costa 120€ i el cost de manteniment és de 0,4€/unitat/any. L’empresa treballa 250 dies a l’any.

• Calculeu: Quantitat Econòmica de Comanda (EOQ), nombre de comandes anuals, punt de reordre, cost total de comanda i manteniment.
• Afegiu una discussió sobre com variaria el model si el temps de subministrament fos incert.

Pregunta 4

Enunciat

Els algoritmes heurístics ofereixen aproximacions eficients a problemes d’optimització complexos. Tres d’aquests algoritmes són el Nearest Neighbor Algorithm (NNA), el Randomized Nearest Neighbor Algorithm (RNNA) i el Clarke-Wright Savings Algorithm (CLA).

• Defineix amb les teves paraules el funcionament bàsic de cadascun d’aquests algorismes.
• Explica la seva aplicació en problemes logístics, com el problema del viatjant (TSP) o ruteig de vehicles.
• Estableix una comparació detallada tenint en compte criteris com: eficiència, qualitat de solució, facilitat d’implementació, escalabilitat i robustesa.
• Justifica amb una breu referència teòrica quina mena de problemes són més adequats per a cadascun.

Pregunta 5

Enunciat

Una empresa logística vol millorar l’eficiència de les seves rutes de distribució a nivell nacional. Actualment disposa d’una llista de 30 punts de distribució repartits per Espanya i vol determinar la millor ruta per a un dels seus vehicles que ha de visitar totes les ubicacions exactament una vegada i tornar al punt d’origen.

Es demana:

• Proposar un mètode d’obtenció de les coordenades geogràfiques dels punts de distribució a partir d’un llistat de ciutats.
• Construir la matriu de distàncies geogràfiques entre els punts fent servir la distància de Haversine.
• Resoldre el problema del viatjant de comerç (TSP) utilitzant almenys dos algorismes heurístics (com per exemple, NNA i CLA).
• Determinar quina solució proporciona una millor ruta en termes de distància recorreguda.
• Explicar com aquests algorismes poden ajudar a prendre decisions logístiques reals.

Pregunta 6

Enunciat

Una empresa vol determinar quina combinació òptima de tres productes hauria de fabricar per maximitzar el benefici sota certes restriccions de recursos.

• Els beneficis per unitat són:
  • Producte 1: 4 €
    
  • Producte 2: 6 €
    
  • Producte 3: 5 €
• Disponibilitat de recursos:
  • 60 hores de màquina
  • 48 hores de mà d’obra
• Consum de recursos per unitat de producte:

Producte	Màquina (h)	Mà d’obra (h)
Producte 1	2	3
Producte 2	4	2
Producte 3	3	4

Formuleu i resolgueu un problema d’optimització lineal per determinar quantes unitats de cada producte s’han de fabricar per tal de maximitzar el benefici total, tot respectant les restriccions de recursos.

Pregunta 7

Enunciat

Torna a resoldre la pregunta 3 fent servir ChatGPT (o Claude) i respon:

• Quin sistema has utilitzat, versió i data.
• El prompt exacte utilitzat i l’estratègia de construcció.
• La solució proporcionada.
• Si és aplicable directament o necessita correccions.
• Compara la teva solució a la pregunta 3 amb la generada per IA.
• Creus que podries generar un prompt per generar problemes com la pregunta 3 de manera generalista?