GDEUS

based of the worst-case scenario

Calculate the minimum payoff of all choices and select the one that perform best.

The payoff table is based on “lost opportunity”

Calculate the lost opportunity for each entry in the table (the maximum gain per state - what that choice actually got).

Create a new State called regret, by selecting the max regret for each action and select the action that is there the smallest.

This criterion is based on the best possible scenario

Calculate the maximum payoff of all choices and select the one that perform best.

Calculate the net gain per choice, assuming that all choices are weight the same, and select the one that perform best.

different outcomes have probabilities that state how likely it is to occur

Decision making without probabilities

Calculated by getting the weighted sum of all states (EP) (by multiplying it with the probability) and the minimum (min)

best outcome per state, weight by likelyhod

Sum all weighted cells per action, select the action’s value that performs best

(Expected Return with Perfect Information) - (Expected Return under Risk)

(Expected payoff with forecast) / (Expected Value of Perfect Information)

Ein Problem ist linear,

• Wenn die Zielfunktion linear ist

• Wenn alle Nebenbedingungen linear sind

Variablen definieren

• Zielfunktion definieren

• constraints definieren

• Nicht-0 Bedingung

Gelöst graphisch

Eine Nebenbedingung wird verändert

Schattenpreis = Veränderung der optimalen Lösung (pro Einheit Nebenbedingung)

Create a new demand location b_{J+1}, to fill demand. (all cost beeing 0)

Create a new supply location b_{J+1}, to fill supply. (all cost beeing ???)

• Oben links maximalen Wert geben

• Nächstmögliche Zelle maximieren

• Repeat

Always yields solution

• Find min ship cost, and fill cell

• Repeat

is greedy

penalty cost = secondMin(row/column) - min(row/column)

• Find row/column with largest penalty

• Fill min cost in that row

• Recompute all penalties

• Repeat

heuristic

Start with a feasible solution

• for each empty cell, check if its value +1 better (see circle)

• If better, do it, till the first cell gets to 0

• Repeat

Divide a number of task between a number of people (each task can only be done by one person).

⇒ Special Type of Transportation Problem (Demand = 1 & supply = 1)

Each Task can’t be partially done / cant be split

1. Find minimal value in each row (not 0) and subtract every item in that row with that value

2. Find minimal value in each column (not 0) and subtract every item in that row with that value

3. Can you put x’es on a subset of all 0rors, so that each column and row has exactly 1 If posible go to 5.

1. Find the minimum value, not covert by these lines, and substract that from every uncovert value. And add 30 to all points where the lines intersect. Repeat to 3

2. Then fill these x’es in. Those are the solutions.

You have a set of items, each with its own value and weight. What items do you take, considering your max capacity and wanting max value.

Calculate Profitability index, value / weight

Pick highest until full

for i in row:

for k in column:

if i = 0:

// Keine Items zur auswahl

set 0

else:

// die Items 1 - i stehen zur auswahl

// Maximiere diesen Wert in dem optional:

// ein wert aus der unteren reihe

// oder den eigenen wert genommen wird

kapa = k

for i in reverse(row):

if A[i-1][kapa] = A[i][kapa]: // Element darunter

// Bedeutet Element nicht im Sack

else:

// Element im Sack

kapa = kapa - w[i]

Nur für positive Gewichte

Each node gets a label [distance; vorgänger]

• Start with item with smallest distance

• Assign to be permanent

• Recalc all reachable nodes labels

Kleinster Tree der alle Nodes einmal berührt.

Con := Set all connected

Uncon := Set all not connected

zufällige node $v$

Con := $\{v\}$

Uncon := $V \setminus v$

Find $e \in Uncon$ that is next to (lowest weight) a Con weight. Add that note to Con repeat

Suche Hamiltonkreis (jeder Knoten genau einmal)

(Wenn nicht möglich: A→ B → C → B → A, dann Kante ausdenken von C → A mit dem Addierten Gewicht)

Traveling Salesman Problem

Not optimal

1. Start Anywhere

2. Go to Nearest Unvisited City

3. Continue until all Cities visited

4. Return to Beginning

Traveling Salesman Problem

1. Create Minimum Spanning Tree

2. Sei M alle Kanten with odd degree Suche optimale matches zwischen allen Kanten in M, with min cost

3. Erstelle Eulerkreis

4. Erstelle Hamiltonkreis

Find k edges (often 2) in a graph, so that when switching those with k different edges, the path is optimised and not broken.

Vehicle Routing Problem

^^Called $C_{ij}$

Create savings $s_{ij}$ by $s_{ij} = c_{i0} + c_{0j} – c_{ij}$

Jede Zelle gibt an, wie viel es sparen würde direkt von Zeile → Spalte zu gehen, anstatt erst zu A zu gehen

Jetzt wird optimiert: Fangen mit dem größten Einsparungen an, und checken das der Demand $\not >$ Kapazität ist:

Weights on edges tell the max capacity. Each note should send as much as it becomes.

The actual flow is 0, the left capacity is 5

When the actual flow increases, the the left capacity decreases by the same amount.

Search for a Path between Start and T (regarding the capacties)

If no path exists it is optimal.

If it does fill the path to its maxima

A cut is defined as set of arcs so that the in and out nodes are split. Its value is the sum of all capacities.

Theorem says the smalls possible cut = maximum capacity of the flow

⇒ If a cut equals a found flow, the found flow must be optimal

Create dummy sink and sources, that connect to the real ones with arcs set to infinity.

Each arc has max capacity and cost.

Supply and/or demand is known.