---
title: Froga Praktikoa
author: Josu Ceberio, Ana Zelaia
date: 2020ko Maiatzak 6
classoptions: gipuzkoa, eu, foot
name: Josu Ceberio, Ana Zelaia
course: Ikerkuntza Operatiboa
tel: 943 01 7119
mail: josu.ceberio@ehu.eus
address: | 
         | Manuel de Lardizabal, 1
         | 20018 Donostia
abstract: >
  Froga praktiko honetan `lpSolveAPI` eta `metaheuR` paketeekin lan egingo dugu, eta ezinbestekoa da biak instalatuta izatea. Lehenengoarekin, eredu linealak ebaztziko ditugu irakasgaiaren hasierako gaietan ikusi ditugun algoritmoak erabiliz, eta `metaheuR`-ekin optimizazio heuristikoko algoritmoen bitartez ebatziko ditugu optimizazio problemak. Froga ebaluagarria da, eta ebaluazio jarraituko notaren %20a suposatuko dut. Portzentaia hori, %5 eta %15 bezala banatuko da `lpSolveAPI` eta `metaheuR` ataletan, hurrenez hurren.
  
  Gogoratu froga praktikoa bakarkakoa dela, eta beraz, kopia kasuren bat aurkitzen badugu, unibertsitateak finkatuta protokoloa aplikatuko da kopian parte hartu duten ikasle guztientzako.
  
output: 
  pdf_document: 
    keep_tex: yes
---
# 1. Eredu linelak ebazten `lpSolveAPI` paketearekin

## 1.1 Eredu lineala

Giapetto Inc. empresak egurrezko tren eta soldadu jostailuak egiten ditu. Giapetto empresak bere jostailuak produzitzeko ondorengo baliabideak behar izaten ditu: soldatu bakoitzako egiteko egurrezko 3 tabloi behar ditu, eta 2 lan-orduko jarduera; tren bakoitza egiteko egurrezko 5 tabloi eta 4 lan-ordu behar ditu. Biltegian egurrezko 145 tabloi ditu Giapetto-k, eta 90 lan-ordu ordaindu ditzake guztira. Soldatu bakoitzaren salmenta prezioa \$32-koa da eta trenei dagokienez \$55.

Soldaduak eta trenak egiteaz gain, behar izanez gero Giapetto-k kanpoko hornitzaile bati erosi diezaioke egurrezko soldaduak eta trena. Horrela izanez gero, unitate bakoitzetik lortzen duen etekina \$5-koa da. Gehienez 50 soldadu eta 50 tren erosi ditzake. Enpresa orok bezela, Giapetto-k bere irabaziak maximizatu nahi ditu.

Lau erabaki aldagai definituko ditugu: $x_{SM}$= Produzitutako Soldaduak, $x_{TM}$= Produzitutako Trenak, $x_{SB}$= Erositako Soldaduak, $x_{TB}$= Erositako Trenak. Maximizatze problema ondorengo problema linealaren bitartez adieraziko dugu:

\begin{center}
$\begin{array}{rl}
\mbox{max}\ z=32x_{SM}+55x_{TM}+5x_{SB}+5x_{TB} &\mbox{(Profit obtained)} \\
\mbox{subject to}\hspace{4.5cm} & \\
3x_{SM} + 5 x_{TM} \hspace{2cm} \leq 145 & \mbox{(Egurrezko tabloiak)}\\
2x_{SM} + 4x_{TM} \hspace{2cm} \leq \ 90& \mbox{(Lan-orduak}\\
x_{SM} \hspace{1.5cm} +x_{SB} \hspace{1cm} \leq \ 50 & \mbox{(Soldaduak)}\\
\hspace{2cm} x_{TM} \hspace{1cm} +x_{TB} \leq \ 50 & \mbox{(Trenak)}\\
x_{SM},x_{TM}, x_{SB}, x_{TB}\geq 0
\end{array}$
\end{center}

## 1.2 Eredu lineala `lpSolveAPI` paketearekin definitzen

Lehenik eta behin, `lpSolveAPI` instalatu eta kargatuko dugu RStudion.
```{r, eval=FALSE}
# install.packages("lpSolveAPI") # Behar izanez gero, deskomentatu lerro hau.
library(lpSolveAPI)
```

`lpSolveAPI` paketeak implementatuta dituen funtzioak erabiliz, goiko eredu lineala implementatu dezakegu. Ondorengo kode zatian, implementatu goiko eredu lineala, eta behin implementatuta, inprimatu eredua, ziurtatzeko ondo dagoela. 
```{r, eval=FALSE}
# BETE HEMEN (10-12 lerro)
eredua <- make.lp(nrow=4, ncol=4)
set.column(lprec=eredua, column=1, x=c(3, 2, 1, 0))
set.column(lprec=eredua, column=2, x=c(5, 4, 0, 1))
set.column(lprec=eredua, column=3, x=c(0, 0, 1, 0))
set.column(lprec=eredua, column=4, x=c(0, 0, 0, 1))
set.objfn(lprec=eredua, obj=c(-32, -55, -5, -5), indices=1:4) #Negatiboa maximizatu nahi baitugu
set.constr.value(lprec=eredua, rhs=c(145, 90, 50, 50), constraints=1:4)
set.constr.type(lprec=eredua, types=c("<=", "<=", "<=", "<="), constraints=1:4)
aldagaiak   <- c("X1","X2", "X3", "X4")
murrizketak <- c("1. Murr", "2. Murr", "3. Murr", "4. Murr") 
dimnames(eredua) <- list(murrizketak, aldagaiak)
eredua
```

Behin eredu lineala prest dugularik, ondorengo ataletan, ataza batzuk egin beharko dituzu. Zehazki: 1)`lpSolveAPI`-ekin kode zatiak implementatu eta 2) galderak erantzun beharko dituzu. Adi! erantzun zure galderak ahalik eta zabalen.

## 1.3 Eredu lineala ebazten `lpSolveAPI`-ekin

Ebatzi eredua, eta erantzun azpiko galdera.

```{r, eval=FALSE}
# BETE HEMEN (2-3 lerro)
solve(eredua)
get.variables(eredua)
-get.objective(eredua)#Negatiboa maximizatu nahi baitugu
```

### Galdera

* Zein da soluzio optimoa? Eta, zein da soluzio optimoaren helburu-funtzioaren balioa?

```{r, eval=FALSE}
# ERANTZUNA
Soluzio optimoa: 1715
Helburu funtzioa: 45 0 5 50
```

## 1.4 Itzal prezioen interpretazioa

Egin itzal prezioen interpretazioa eta erantzun azpiko galderak:

```{r, eval=FALSE}
# Kalkulatu itzal prezioak
# BETE HEMEN (1-2 lerro)
itzalP <- get.sensitivity.rhs(eredua)
itzalP$duals
# Egin y1^*-en interpretazioa, ereduan duen eragina ikusiz.
# BETE HEMEN (4-5 lerro)

```

### Galderak

* Idatzi soluzio dual optimoa (itzal prezioak).

```{r, eval=FALSE}
# ERANTZUNA
0.0 -13.5  -5.0  -5.0   0.0   4.0   0.0   0.0
```

* Interpretatu $y^*_1$ itzal prezioa. Arrazonamendua egiteko, aldatu eredu lineala  $y^*_1$-rekiko, ebatzi eredua, eta aztertu lortutako emaitzak, eta begiratu erabilitako baliabideak. Zeintzuk izan dira aldaketak?

```{r, eval=FALSE}
# ERANTZUNA
```

## 1.5 Sentikortasun analisia - Aldaketak $\mathbf{c}$ bektorean

Une honetan, trenen salmenta prezioa, \$55-koa da. Giapetto aldiz, trenen salmenta prezioa aldatzekotan dabil. Egin sentikortasun analisia azpiko galderak erantzuten dituzularik:

```{r, eval=FALSE}
# Idatzi berriro hasierako eredu lineala (kopiatu zuzenean)
# BETE HEMEN (10-12 lerro)
eredua <- make.lp(nrow=4, ncol=4)
set.column(lprec=eredua, column=1, x=c(3, 2, 1, 0))
set.column(lprec=eredua, column=2, x=c(5, 4, 0, 1))
set.column(lprec=eredua, column=3, x=c(0, 0, 1, 0))
set.column(lprec=eredua, column=4, x=c(0, 0, 0, 1))
set.objfn(lprec=eredua, obj=c(-32, -55, -5, -5), indices=1:4) #Negatiboa maximizatu nahi baitugu
set.constr.value(lprec=eredua, rhs=c(145, 90, 50, 50), constraints=1:4)
set.constr.type(lprec=eredua, types=c("<=", "<=", "<=", "<="), constraints=1:4)
aldagaiak   <- c("X1","X2", "X3", "X4")
murrizketak <- c("1. Murr", "2. Murr", "3. Murr", "4. Murr") 
dimnames(eredua) <- list(murrizketak, aldagaiak)
eredua
# Ebatzi eredua
# BETE HEMEN (2-3 lerro)
solve(eredua)
get.variables(eredua)
-get.objective(eredua)#Negatiboa maximizatu nahi baitugu
# Egin sentikortasun analisia eta lortu behar diren balioen tarteak. 
# BETE HEME (lerro bat)
get.sensitivity.obj(eredua)
# Suposatu produzitutako trenen salmenta prezioa 58 dela. Aldatu eredua eta ebatzi.
# BETE HEMEN (4 lerro kode)
set.objfn(lprec=eredua, obj=c(-32, -58, -5, -5), indices=1:4) #Negatiboa maximizatu nahi baitugu
solve(eredua)
get.variables(eredua)
-get.objective(eredua) #Negatiboa maximizatu nahi baitugu
# Suposatu produzitutako trenen salmenta prezioa 60 dela. Aldatu eredua eta ebatzi.
# BETE HEMEN (4-5 lerro kode)
set.objfn(lprec=eredua, obj=c(-32, -60, -5, -5), indices=1:4) #Negatiboa maximizatu nahi baitugu
solve(eredua)
-get.objective(eredua)#Negatiboa maximizatu nahi baitugu
get.variables(eredua)
```

### Galderak

* $c_2$-ren zein balio tarterako (ekoitzitako trenen salmenta prezioa, $x_{TM}$) ez da oinarria aldatzen? 
```{r, eval=FALSE}
# ERANTZUNA
-7.0e+00 0e+00 tartean ez da aldatzen
```
 
Momentu honetan, trenenen produkzioa ez da errentagarria, soluzio optimoaren arabera, ez delako unitate bat bera ere ekoizten: $x_{TM}= 0$.

* Demagun, Giapetto-k ekoitzitako trenak \$58-etara saltzen dituela, zein izango da ereduaren soluzio berria? Eta, zer gertatutako da ekoitzitako trenen salmenta prezioa \$60-ra arte igotzen bada? Zein da prezio minimoa trenen salmenta errentagarria izateko? Probatu salmenta prezioak ereduan aldatzen, lortu soluzio berriak, eta egin interpretazioak.
```{r, eval=FALSE}
# ERANTZUNA
1715 58ra igotzen badu eta 1737.5 60ra igoz gero.
```

* Giapetto konturatu da, erabili behar dituen aldagaiak osokoak izan behar dutela, ez baitu zentzurik tren erdi, edo soldatu erdi ekoizteak. Nola aldatu genezake eredua?
```{r, eval=FALSE}
# ERANTZUNA
set.type(eredua, 1, type = "integer")
set.type(eredua, 2, type = "integer")
set.type(eredua, 3, type = "integer")
set.type(eredua, 4, type = "integer")
Honela aldagai guztiak osokoak bihurtuko ditugu.
```


# 2. Optimizazio heuristikoa `metaheuR` paketearekin

Lehenik eta behin, `metaheuR` paketea kargatuko dugu. Gogoratu instalatuta eduki behar duzuela aurretiaz, bestela ezinezkoa izango da froga egin ahal izatea.
```{r, eval=FALSE}
library(metaheuR)
```

## 2.1 Motxilaren problema
Froga honetan, motxilaren problemaren (`Knapsack Problem`) kasu zehatz bat ebazten saiatuko gara `metaheuR` paketearen bitartez. Kasu honetan, motxilaren probleman $10$ objektu garraiatu nahi ditugu, eta motxila bat dugu horretarako. Gauza da motxilak $26$ kiloko edukiera maximo bat duela, eta garraiatu nahi ditugun objektu guztiak ez direla sartzen batera. Erabaki ahal izateko zein elementu sartu motxilan eta zein ez, elementu bakoitzaren balioa eta pisuak ezagutzen ditugu. Zehazki, pisuak (4,2,7,3,2,2,6,3,7,4) kilokoak dira, eta balioak (12,75,89,37,4,46,100,46,92,55) eurokoak dira. Helburua, motxilan sartzen ditugun elementuen balioen batura maximizatzea da, motxilaren edukiera muga gainditzen ez dutelarik barruan dauden elementuen pisuen baturak. 

```{r,eval=FALSE}
# Knapsack problemaren eredua kargatu.
# Sortu Motxilaren problemaren objektua enuntziatuan adierazitako balioak erabilirik.
# BETE HEMEN (4-5 lerro)
pisua<-c(4,2,7,3,2,2,6,3,7,4)
bal<-c(12,75,89,37,4,46,100,46,92,55)
max=26
problema<-knapsackProblem(pisua, bal, max)
problema
```

Pentsatu kodeketa egoki bat motxilaren problemaren soluzioak kodetzeko, eta sortu ausazko soluzio bat eta ebaluatu. Adi! motxilaren problemaren helburu funtzioak kodeketa konkretu bat eskatzen du. Begiratu metaheuR-en laguntza.

```{r,eval=FALSE}
# Sortu ausazko soluzio bat, eta ebaluatu
# BETE HEMEN (2-3 lerro)
rnd <- runif(length(bal)) > 0.5
problema$evaluate(rnd)
problema$valid(rnd)
```

Dakizunez, soluzioek problema honetan ezin dute edukiera gainditu, edukiera gainditzen baldin badute ez direla **bideragarriak** esango dugu. Kasu horietan, ohiko teknika bat soluzioak zuzentzean datza. Bilatu `metaheuR`-en laguntzan `KnapsackProblem` objektuak dituen funtzio desberdinak. Zehazki, soluzio bat bideragarria den jakiten lagunduko diguten funtzioa aurkitu, eta bideragarria ez bada, soluzioa zuzentzen lagunduko digun funtzioa ere bilatu. Ondorengo kodean aztertu aurreko kode zatian sortu duzun ausazko soluzioa bideragarria den, eta beharrezkoa izanez gero, zuzendu ezazu. Ebaluatu, hasieran zenuen soluzioa, eta zuzendu ondorengoa ere.

```{r,eval=FALSE}
# Zuzendu soluzioa ez bada bideragarria
# BETE HEMEN (3-4 lerro)
corrected.solution <- problema$correct (rnd)
corrected.solution
problema$valid(corrected.solution)
```

## 2.2 Bilaketa lokala

Jarraian bilaketa lokaleko algoritmo bat implementatu beharko duzue. Gogoratu bilaketa lokalari hainbat parametro ezarri beharko dizkiogula. Ingurune-funtzio egoki bat, aukeraketa irizpide bat (zuek nahi duzuena), baina ez hori bakarrik, kasu honetan, (1) soluzio bideragarriekin zer egin (`non.valid` parametroa), (2) nola konprobatu bideragarritasuna (`valid` parametroa)  eta (3) nola zuzendu esan beharko diogu (`correct` parametroa). Gure helburua, soluzio ez bideragarriak zuzentzea izango da, beraz, `non.valid<- "correct"`. Zuek ikusi (2) eta (3) parametroei zer esleitu behar diezuen, baina dagoeneko erabili dituzuen funtzioak dira.

Begiratu `metaheuR`-en laguntza eskuineko menuan, eta begiratu bilaketa lokalari ezarri beharreko parametroak, eta aukeratu dauden ingurune-funtzio guztien artetik egokia den bat. Adi! Denek ez digute balio. Bilatu `neighborhood` gakoarekin dauden aukera desberdinak, eta erabili zentzua duen bat.

```{r,message=FALSE,eval=FALSE}
args<-list()
# BETE HEMEN (10 lerro inguru)
args$evaluate<-tsp.example$evaluate
args$selector<-greedySelector
args$non.valid <-"correct"
args$valid <- 
args$correct <- 
args$do.log <- FALSE
args$verbose <- FALSE
args$initial.solution <- init.sol
args$neighborhood <- swapNeighborhood(init.sol)
#args$neighborhood <- insertNeighborhood(init.sol)
```

Aurreko parametroez gain, algoritmoa exekutatzeko baliabideak ere zehatu egin behar ditugu. Kasu honetan, gehienez, algoritmoak $10^4$ helburu-funtzio ebaluazio egin ahal izango ditu gehienez.
```{r,eval=FALSE}
# BETE HEMEN (2 lerro)
args$resources <- cResource(evaluations = 10^4)
```

Azkenik, bilaketa lokalaren deia exekutatuko dugu, ezarritako parametroekin.
```{r,eval=FALSE}
# Exekutatu algoritmoa
# BETE HEMEN (1-2 lerro)
res<-do.call(basicLocalSearch, args)
```

### Galderak
Aurreko kodeak implementatu eta exekutatu ondoren, erantzun ondorengo galderak azalpen luzeak emanik. Frogaren ebaluazioren atal garrantzitsua da hau!

* Zein da bilaketa espazioaren tamaina? Bideragarriak eta ez bideragarriak, biak kontuan izanik.
```{r, eval=FALSE}
# IDATZI ERANTZUNA HEMEN.
Objetu kopuruaren, hau da 10, permutazioa izango da bilaketa espazioaren tamaina.
```
* Lortutako azken soluzioa bideragarria al da?
```{r, eval=FALSE}
# IDATZI ERANTZUNA HEMEN.

```
* Lortutako azken soluzioa optimoa al da?
```{r, eval=FALSE}
# IDATZI ERANTZUNA HEMEN.
Ezin dugu zehaztasunez jakin, soluzio optimo lokal bat da baina ez dakigu soluzio optimo globala den.
```
* Ebaluazio baliabide gehiago emanez gero bilaketa lokalari, soluzio hobeagoren bat lortuko al dugu? Zergaitik?
```{r, eval=FALSE}
# IDATZI ERANTZUNA HEMEN.
Ez. Baliabide kourua handitu arren puntu batetik aurrera ez du soluzio hobeagorik aurkituko eta ondorioz alferrekoa izango da hau luzatzea.
```
