Qu'est-ce que Mini Sam ou Mini Max?

Histoire sur l'optimisation

  • Le problème de la mini-somme est un problème qui minimise la somme (somme: somme) (mini: min).
  • Le problème minimax est un problème qui minimise la valeur maximale (max: max) (mini: min).

Lorsqu'il est appliqué au problème de planification d'évacuation, il devient comme suit.

  • Problème de minisam: minimiser le temps d'évacuation total pour tout le monde. --Problème Minimax: Minimiser le temps d'évacuation de la personne qui est le plus en retard.

En général, avec les solveurs d'optimisation mathématique, on peut dire ce qui suit.

  • Le problème de mini-somme est plus facile à résoudre que le problème de mini-max.

Allons vérifier.

python


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

Pour 1000 articles. Supposons que 100 utilisateurs aient différents sens du coût. Supposons que vous choisissiez la moitié des 1000 produits pour les problèmes suivants.

  • Problème minisum: minimiser le coût total de tous les utilisateurs --Problème Minimax: minimiser le coût maximum de chaque utilisateur

Regardons le temps de calcul tout en modifiant le nombre de produits.

python


it = [100, 200, 500, 1000] #Liste des numéros de produits
tm = []
for n in it:
    b = a[:n]
    #Problème minisum
    m1 = LpProblem() #Problème de minimisation(mini)
    m1 += lpDot(b.T[:-1].sum(), b.Var) #total(Sam)
    m1 += lpSum(b.Var) <= int(n * 0.5)
    m1.solve()
    #Problème Minimax
    m2 = LpProblem() #Problème de minimisation(mini)
    y = LpVariable('y', lowBound=0)
    # y >= max(Valeur de l'utilisateur j)
    for j in range(nombre d'utilisateurs): m2 += y >= lpDot(b.ix[:, j], b.Var)
    m2 += y #total(Max)
    m2 += lpSum(b.Var) <= int(n * 0.5)
    m2.solve()
    tm.append((m1.solutionTime, m2.solutionTime))

plt.plot(it, tm)
plt.legend(['Problème minisum','Problème Minimax'], loc='upper left')
plt.show()

image

Le problème Minimax prend beaucoup plus de temps que le problème Minisum.

Pourquoi le problème Minimax prend-il autant de temps?

  • Par rapport au problème de la mini-somme, le problème de la mini-max a de nombreuses solutions optimales. --Solver explore toutes les possibilités. --S'il existe de nombreuses solutions optimales, le solveur ne peut pas être calculé efficacement.

Ne pouvez-vous pas résoudre le problème minimax efficacement?

Dans certains cas, il peut être plus rapide de résoudre en deux étapes, telles que Comment résoudre le problème d'emballage du bac.

c'est tout

Recommended Posts