BWI Coding Challenge

Code für die Teilnahme an der BWI Coding Challenge (https://www.get-in-it.de/coding-challenge).

 

Requirements und Ausführung:

Requirements:

• numpy
• pulp

Die Requirements können über pip mit folgendem Befehl installiert werden:

pip3 install -r requirements.txt

Das Programm wird mit folgendem Befehl ausgeführt:

python3 opt_transport.py

(Getestet mit Python 3.9.1)

 

Algorithmus:

Für die Lösung des Problems wird auf Integer Linear Programming zurückgegriffen, da es sich hier um ein klassisches lineares Optimierungsproblem (Nutzenmaximierung) mit linearen Nebenbedingungen (begrenzte Anzahl an Einheiten, begrenztes Fassungsvermögen der Transporter, etc.) handelt, dessen Lösung ganzzahlig sein muss. Zum Modellieren und Lösen des Problems wird PuLP verwendet: https://pypi.org/project/PuLP/

Der Lösungsvektor x := [x₁, x₂, x₃, ..., x₁₉, x₂₀] ist wie folgt definiert:

  x₁ = Anzahl Notebook Büro 13" in Transporter 1
  x₂ = Anzahl Notebook Büro 14" in Transporter 1
  ...
  x₉ = Anzahl Tablet outdoor klein in Transporter 1
  x₁₀ = Anzahl Tablet outdoor groß in Transporter 1
  x₁₁ = Anzahl Notebook Büro 13" in Transporter 2
  x₁₂ = Anzahl Notebook Büro 14" in Transporter 2
  ...
  x₁₉ = Anzahl Tablet outdoor klein in Transporter 2
  x₂₀ = Anzahl Tablet outdoor groß in Transporter 2

Die Nebenbedingungen für das jeweilige Ladegewicht der Transporter können wie folgt definiert werden:

  ∑_{i = 1}¹⁰ g_i · x_i ≤ 1100000 - 72400

und

  ∑_{i = 11}²⁰ g_i-10 · x_i ≤ 1100000 - 85700,

wobei g_i das Gewicht von Gerät i pro Einheit in Gramm angibt, i = 1, ..., 10.

Zudem darf die Gesamtzahl für jedes Gerät die benötigte Anzahl e_i an Einheiten nicht übersteigen.

  x_i + x_i+10 ≤ e_i   ∀ i = 1, ..., 10.

 

Optimale Verteilung der Hardware:

Gesamtnutzen:   74660

Gesamtanzahl der jeweils transportierten Geräte:

Gerät	Anzahl
Notebook Büro 13"	0
Notebook Büro 14"	0
Notebook outdoor	0
Mobiltelefon Büro	60
Mobiltelefon Outdoor	157
Mobiltelefon Heavy Duty	220
Tablet Büro klein	595
Tablet Büro groß	0
Tablet outdoor klein	4
Tablet outdoor groß	370

 

Anzahl der jeweils transportierten Geräte in Transporter 1:

Gerät	Anzahl
Notebook Büro 13"	0
Notebook Büro 14"	0
Notebook outdoor	0
Mobiltelefon Büro	27
Mobiltelefon Outdoor	0
Mobiltelefon Heavy Duty	4
Tablet Büro klein	358
Tablet Büro groß	0
Tablet outdoor klein	2
Tablet outdoor groß	251

 

Anzahl der jeweils transportierten Geräte in Transporter 2:

Gerät	Anzahl
Notebook Büro 13"	0
Notebook Büro 14"	0
Notebook outdoor	0
Mobiltelefon Büro	33
Mobiltelefon Outdoor	157
Mobiltelefon Heavy Duty	216
Tablet Büro klein	237
Tablet Büro groß	0
Tablet outdoor klein	2
Tablet outdoor groß	119