[PYTHON] Koordinator und ganzzahliger linearer Plan

Vom eingereichten Koordinator formulierte und löste ich die optimale Kombination von Lunchpartys als ganzzahligen linearen Plan.

Ich habe es mit einem Python-Optimierungspaket namens PuLP gelöst.

Dieser Artikel ist sehr einfach zu verstehen, wie man PuLP benutzt. http://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17

Bedarf

Lassen Sie uns zuerst die Anpassung vornehmen.

** ・ Nehmen Sie unbedingt an einem Zeitplan pro Person teil ** ** ・ Gleichen Sie die Anzahl der Personen für jeden Zeitplan so weit wie möglich aus **

Lassen Sie uns unser Bestes geben, um dies zu formulieren.

Zuerst, $ P $ = (Gruppe von Mitgliedern) $ D $ = (Datumssatz) Wird besorgt.

Für $ p \ in P ist d \ in D $

\mathrm{hope}[p][d] = \left\{
\begin{array}{ll}
1 & (p wird d ○) \\
0 & (p wird d ×)
\end{array}
\right.

Und bestimmen Sie die Konstante aus dem Ergebnis von Mr. Adjustment.

Stellen Sie dann die Variablen ein.

$ \ mathrm {attend} [p] [d] = (1or0) $ ist eine Variable, die angibt, ob $ p $ tatsächlich an $ d $ teilnimmt. $ M $ ist die maximale Teilnehmerzahl für jeden Zeitplan. Um dies zu minimieren, können wir jedem Zeitplan eine einheitliche Anzahl von Personen zuweisen.

Wenn es formuliert ist, sieht es so aus.

\begin{align}
\mathrm{min} &\ M \\
\mathrm{s.t} \ &\forall d\in D\ \Sigma_{p \in P}\mathrm{hope}[p][d]\times \mathrm{attend}[p][d] \leq M \\
&\forall p\in P\ \Sigma_{d \in D}\mathrm{hope}[p][d]\times \mathrm{attend}[p][d] = 1

\end{align}

Die erste Formel der Einschränkungsbedingung lautet, dass die Anzahl der Teilnehmer an jedem Tag M oder weniger beträgt. Der zweite Ausdruck der Einschränkungsbedingung ist, dass jede Person nur einmal teilnehmen darf.

Lass uns das hart machen.

Code

chousei.py

import pulp

date = ["3/8", "3/9", "3/11", "3/15"]
people = #Fügen Sie hier eine Liste der Mitgliedsnamen ein

_table = [
[1,1,1,1], 
[0,1,0,0],
[1,1,0,0],
[0,1,1,0],
[1,0,0,0],
[1,1,0,1],
[1,0,0,0],
[0,1,0,1],
[0,1,1,0],
[1,1,1,1],
[1,1,1,1],
[1,1,0,0],
[1,0,0,1],
[0,1,1,1],
[0,1,0,0],
[1,1,1,1]] #Schreiben Sie das Ergebnis von Mr. Adjustment


table = {}
for i,p in enumerate(people):
    table[p] = {}
    for j,d in enumerate(date):
        table[p][d] = _table[i][j]
#In Wörterbuchtyp konvertieren

problem = pulp.LpProblem('chousei', pulp.LpMinimize)
attend = pulp.LpVariable.dicts('attend', (people, date), 0, 1, 'Binary')
M = pulp.LpVariable('M', 0, 1000, 'Integer')
problem += M

for p in people:
    each_people = 0
    for d in date:
        each_people += table[p][d]*attend[p][d]
    problem += each_people == 1

for d in date:
    each_date = 0
    for p in people:
        each_date += table[p][d]*attend[p][d]
    problem += each_date <= M

problem.solve()

for d in date:
    each_date = ''
    for p in people:
        if(table[p][d] == 1　and attend[p][d].value() > 0):
            each_date += p
    print "{}: {}".format(d, each_date)

Verbesserung

Wenn dies so bleibt, besteht die Möglichkeit, dass nur die Ältesten einen festgelegten Zeitplan haben. Ich denke, es ist besser, jedem Mitglied Gewicht zu geben und die Obergrenze der Summe der Gewichte für jeden Zeitplan zu minimieren. .. Ich werde es erklären, wenn ich Lust dazu habe.