Optimierung von Excel zu R

Question

Ich habe Probleme mit der Lösung unten Optimierung in R. Es war einfach für mich mit Excel-Löser zu tun, aber ich bin nicht in der Lage, das gleiche Problem in R. Ich habe nicht viel Erfahrung in der Optimierung R Problem ist zuzuordnen, wenn eine bestimmte Aktivität über den Zeitraum ausgeführt werden soll. A1, A2, ..., A12 sind 12 Aktivitäten, die in einem Feld ausgeführt werden. 0 steht für nicht zugewiesen, 1 steht für zugewiesen.

Constraints sind -

• A2 passieren sollte nach A1 abgeschlossen ist, sollte A3 auftreten, nachdem A2 abgeschlossen ist und so weiter
• A3, A5, A6 - nur zwei dieser Aktivitäten auf einem bestimmten passieren kann Tag
• Jede Aktivität in einem Feld (in Excel Solver, diese Einschränkung, indem Zeilensumme definiert passieren soll, ist gleich ein

Es wäre eine große Hilfe sein, wenn jemand in SolVin helfen kann g Dieses Problem. Ich habe ein Bild zum besseren Verständnis dieses Problems beigefügt. Bitte lassen Sie mich auch wissen, wenn es eine Website oder Buch, reich an Beispielen auf "wie Optimierungsprobleme in R zu lösen" gibt. Danke Ihnen im Voraus.

Answer 1

Sie können Ihr Problem mit dem lpSolve Paket lösen.

Sie benötigen Informationen zu Kostenvektor und Randbedingungen. Randbedingungsinformation in in der folgenden Struktur in die Funktion eingespeist:

• lhs: a "linke Seite" Matrix von Koeffizienten, einer für jede Entscheidungsvariable
• dir: eine "Richtung", nämlich <, <=, ==, >=, >
• rhs: eine "rechte Seite" als numerischer Wert

Um Ihre Liste der Zusammenarbeit zu bauen Nstraints, ich finde es nützlich, jede Entscheidung, die Sie möglicherweise als ein X nehmen könnten (wird zu einer Spalte in der lhs Tabelle) und jede Beschränkung, die Sie als eine separate Gleichung definieren möchten (wird zu einer Zeile in der lhs Tabelle, mit a entsprechenden Wert in dir und rhs, respectively)

Lassen Sie uns mit allen möglichen Entscheidungen starten:

library(tidyverse) 
library(stringr) 

# What are the decision variables? ---- 

# Which action to take 
actions <- str_c('A',seq(1:12) %>% formatC(width = 2, flag = '0')) 
actions 
#[1] "A01" "A02" "A03" "A04" "A05" "A06" "A07" "A08" "A09" "A10" "A11" "A12" 

# When to take it 
timings <- str_c('T',seq(1:12) %>% formatC(width = 2, flag = '0')) 
timings 
#[1] "T01" "T02" "T03" "T04" "T05" "T06" "T07" "T08" "T09" "T10" "T11" "T12" 

# List of all possible decisions is this: 
decisions <- expand.grid(actions, timings) 

# Convert it to a vector 
decision_variables <- str_c(decisions[,1], '_', decisions[,2]) 

# You also need a cost vector. 
# We'll use a value increasing as a function of timings, 
# as this will penalize "late" actions? 
cost <- rep(seq(1:length(timings)), length(actions)) %>% sort 

Jedes Element decision_variables ist eine mögliche Aktion (dh ergreifen Sie eine Aktion zu einer bestimmten Zeit. Jetzt können wir beginnen, die Optionen, die dem Löser zur Verfügung stehen, einzugrenzen, indem wir Einschränkungen einführen.

---

Erste Art von Einschränkung: Jede Option sollte nur einmal genommen werden! (Dies ist eigentlich Ihre dritte, aber ich beginnen diese mit, wie es das einfachste ist) Wir, die wie folgt formulieren:

# Create a matrix with one column per possible decision 
# and one row per action (for now) 
lhs <- matrix(0, 
    nrow = length(actions), 
    ncol = length(decision_variables), 
    dimnames = list(
    actions, 
    decision_variables)) 

# Each action should only be taken once! 
for (i in 1:length(actions)) { 
    # Which fields does an action occur in? 
    this_action <- str_detect(colnames(lhs), actions[i]) 
    # Set their coefficients to 1 
    lhs[i,this_action] <- 1 
} 
# create corresponding dir and rhs values 
dir <- rep('==', length(actions)) 
rhs <- rep(1, length(actions)) 

Sie können sehen, dass wir den Koeffizienten aller X ‚s (Entscheidungen) gesetzt die die action in Frage zu 1 enthalten. In unserer endgültigen Lösung wird jeder X den Wert 0 oder 1 annehmen. Wenn X Null ist, ist der Koeffizient irrelevant. Wenn X1 ist, wird der Koeffizient zur Summe von lhs addiert und mit dir mit dem Wert rhs verglichen.

Hier ist unsere Einschränkung, dass die Summe coefficient * X == 1 für jede der Einschränkungen, die wir gerade eingeführt haben. Die Koeffizienten sind 1 für alle möglichen Entscheidungen, die eine bestimmte Aktion enthalten. Ergo, eine Lösung ist nur gültig, wenn eine bestimmte Aktion nur einmal ausgeführt wird.

---

Zweite Einschränkung: Nur zwei von c('A03', 'A05', 'A06') sollte an einem bestimmten Tag gemeinsam auftreten.

Wir generieren wiederum eine Linie pro Abhängigkeit. In diesem Fall, denke ich, brauchen wir eine Beschränkung pro Tag. Wir fügen Sie die Werte, die wir zu den bereits bestehenden lhs, dir und rhs Variablen erzeugen:

# only one of A3, A5, A6 at any given time. 
# One constraint for each timestep 
for (j in timings) { 
    lhs <- rbind(lhs, ifelse(str_detect(decision_variables, paste0('A0[356]{1}_',j)), 1, 0)) 
    dir <- c(dir, '<=') 
    rhs <- c(rhs, 2) 
} 

---

Platzhalter für dritte Einschränkung

---

Presto, haben wir unser Problem formuliert. Lass jetzt lpSolve die Zahlen knacken! Sie können unser Problem in den Algorithmus wie folgt füttern:

library(lpSolve) 

# Run lpSolve to find best solution 
solution <- lp(
    # maximise or minimise the objective function? 
    direction = 'min', 
    # coefficients of each variable 
    objective.in = cost, 
    const.mat = lhs, 
    const.dir = dir, 
    const.rhs = rhs) 

# Extract the values of X for the best solution: 
print(solution$solution) 

# Convert it into ta matrix of the format you are familiar with 
matrix(solution$solution, 
     nrow = length(timings), 
     ncol = length(actions), 
     dimnames = list(actions, timings)) 

Ist dies tun, was Sie brauchen?

Haben Sie Fragen?