[PYTHON] Was ist Mini Sam oder Mini Max?

Geschichte über die Optimierung

  • Das Minisummenproblem ist ein Problem, das die Summe (Summe: Summe) (Mini: Min) minimiert.
  • Das Minimax-Problem ist ein Problem, das den Maximalwert (max: max) (mini: min) minimiert.

Wenn es auf das Evakuierungsplanungsproblem angewendet wird, wird es wie folgt.

  • Minisam-Problem: Minimierung der gesamten Evakuierungszeit für alle.
  • Minimax-Problem: Minimierung der Evakuierungszeit der Person, die am spätesten ist.

Im Allgemeinen kann mit mathematischen Optimierungslösern Folgendes gesagt werden.

  • Das Mini-Summen-Problem ist einfacher zu lösen als das Mini-Max-Problem.

Lass uns nachsehen.

python


import numpy as np, pandas as pd, matplotlib.pyplot as plt
from pulp import *
Anzahl der Teile= 1000
Anzahl der Nutzer= 100
np.random.seed(1)
a = pd.DataFrame(np.random.rand(Anzahl der Teile,Anzahl der Nutzer),
                 index=['Produkt%d'%i for i in range(Produkt数)],
                 columns=['Nutzer%d'%j for j in range(Nutzer数)])
a['Var'] = [LpVariable('v%d'%i, lowBound=0) for i in range(Anzahl der Teile)]
Benutzer 0 Benutzer 1 Benutzer 2 Benutzer 3 Benutzer 4 ... Benutzer 99
Produkt 0 0,417022 0,720324 0,000114 0,302333 0,146756 td> ... 0,186260
........................
Produkt 999 0,950176 0,556653 0,915606 0,641566 0,390008 td> 0,485991 0,604310

Für 1000 Artikel. Angenommen, 100 Benutzer haben unterschiedliche Kostensinne. Angenommen, Sie wählen die Hälfte von 1000 Produkten für die folgenden Probleme.

  • Minisum-Problem: Minimierung der Gesamtkosten aller Benutzer
  • Minimax-Problem: Minimieren Sie die maximalen Kosten jedes Benutzers

Schauen wir uns die Berechnungszeit an, während wir die Anzahl der Produkte ändern.

python


it = [100, 200, 500, 1000] #Produktnummernliste
tm = []
for n in it:
    b = a[:n]
    #Mindestproblem
    m1 = LpProblem() #Minimierungsproblem(Mini)
    m1 += lpDot(b.T[:-1].sum(), b.Var) #gesamt(Sam)
    m1 += lpSum(b.Var) <= int(n * 0.5)
    m1.solve()
    #Minimax-Problem
    m2 = LpProblem() #Minimierungsproblem(Mini)
    y = LpVariable('y', lowBound=0)
    # y >= max(Wert des Benutzers j)
    for j in range(Anzahl der Nutzer): m2 += y >= lpDot(b.ix[:, j], b.Var)
    m2 += y #gesamt(Max)
    m2 += lpSum(b.Var) <= int(n * 0.5)
    m2.solve()
    tm.append((m1.solutionTime, m2.solutionTime))

plt.plot(it, tm)
plt.legend(['Mindestproblem','Minimax-Problem'], loc='upper left')
plt.show()

image

Das Minimax-Problem dauert erheblich länger als das Minisum-Problem.

Warum ist das Minimax-Problem so lang?

  • Im Vergleich zum Mini-Summen-Problem bietet das Mini-Max-Problem viele optimale Lösungen. --Solver erkundet alle Möglichkeiten.
  • Wenn es viele optimale Lösungen gibt, kann der Löser nicht effizient berechnet werden.

Können Sie das Minimax-Problem nicht effizient lösen?

In einigen Fällen kann die Lösung in zwei Schritten schneller erfolgen, z. B. So lösen Sie das Problem beim Verpacken von Behältern.

das ist alles

Recommended Posts