[PYTHON] Junior High School Komitee

Was ist das

Basierend auf den Wünschen der Schüler werden wir das "Problem der Zuweisung von Klassenmitgliedern" durch Kombinationsoptimierung lösen. Dies ist die Python-Version von Eine Geschichte über die Optimierung des Junior High School-Komitees zu den niedrigsten Kosten.

Politik

--Erstelle einen Pandas.DataFrame mit einer Aufzeichnung der Wünsche des Studentenkomitees.

• Die Kosten für die erste Wahl betragen 10 und die Kosten für die zweite Wahl 30. --Erstellen Sie mit DataFrame ein mathematisches Optimierungsmodell (Kostenminimierung). -Lösen Sie Mathematisches Optimierungsmodell mit einem Löser, um die Zuordnung zu erhalten.

Mathematisches Optimierungsmodell

--Variable: Erstellt als Spalte von DataFrame (1 Zeile, 1 Variable).

• Zielfunktion: Minimieren Sie die gewünschten Gesamtkosten --Beschränkungen
• Bis zu einem Mitglied kann ein Student sein
• Mitglieder treffen die feste Nummer

Eingang

Erstellen Sie einen DataFrame.

import pandas as pd
from pulp import lpDot, lpSum
from ortoolpy import model_min, addbinvars, addvals

lst = [['Taprice', 'Disziplinarausschuss', 10], ['Aoba', 'Klassensprecher', 10], ['Kaguya', 'Disziplinarausschuss', 10],
       ['Chino', 'Klassensprecher', 10], ['Spiegel', 'Disziplinarausschuss', 10],
       ['Taprice', 'Klassensprecher', 30], ['Aoba', 'Bibliothekskommission', 30], ['Kaguya', 'Bibliothekskommission', 30],
       ['Chino', 'Disziplinarausschuss', 30], ['Spiegel', 'Klassensprecher', 30]]
need = {"Klassensprecher": 1, "Bibliothekskommission": 2, "Disziplinarausschuss": 2}
df = pd.DataFrame(lst, columns=['Name', 'Committee', 'Cost'])
addbinvars(df)

print(df)

Die Var-Spalte ist variabel (1: zuweisen, 0: nicht zuweisen)

Modellieren und Lösen

m = model_min()
m += lpDot(df.Cost, df.Var)  #Summe der gewünschten Kosten
for _, gr in df.groupby('Name'):
    m += lpSum(gr.Var) <= 1  #Bis zu einem Mitglied kann Student sein
for k, gr in df.groupby('Committee'):
    m += lpSum(gr.Var) == need[k]  #Die Mitglieder des Ausschusses treffen eine feste Anzahl
m.solve()
addvals(df)

Ergebnis

print(df[df.Val > 0])

Ergänzung

Im Originalartikel handelt es sich um das Problem des minimalen Kostenflusses. In diesem Fall können Sie min_cost_flow von Network X verwenden.

Wenn Sie das Modell jedoch ändern möchten, ist ein mathematisch optimiertes Modell wie dieser Artikel einfacher zu handhaben. Die Berechnungszeit für die mathematische Optimierung ist ebenfalls schnell genug.