[PYTHON] Sehen Sie sich Wale mit Kombinationsoptimierung an

Was ist das

In den Sommerferien werden Sie Wale sehen. Verwenden Sie Kombinationsoptimierung, um zu überlegen, welcher der acht Punkte ausgewählt werden soll.

Punktinformationen mit Python anzeigen

import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addbinvars
n = 8 #Punkte
np.random.seed(639)
df = pd.DataFrame(np.random.rand(n,2).round(2)*[0.2,100], columns=['Prob','Time'])
df.insert(0,'Place', [chr(i+65) for i in range(n)])
print(df)

Ort repräsentiert den ** Namen ** des Punktes, Prob repräsentiert die ** Wahrscheinlichkeit **, den Wal zu sehen, und Zeit repräsentiert die ** Zeit ** (Minuten), die benötigt wird, um sich zu bewegen und den Punkt zu beobachten.

Problem 1

Maximieren Sie die Summe der ** Wahrscheinlichkeiten ** innerhalb der Gesamtzeit ** 140 Minuten **

Antwort 1

Rucksackproblem, also lösen wir es schnell.

python

m = LpProblem(sense=LpMaximize)
df['Var'] = addbinvars(n)
m += lpDot(df.Prob,df.Var)
m += lpDot(df.Time,df.Var) <= 140
m.solve()
df['Val'] = df.Var.apply(value)
print('%s found. Ave prob. = %.3f, Any prob. = %.3f'%(LpStatus[m.status],
      df[df.Val>0].Prob.sum(), 1-(1-df[df.Val>0].Prob).prod()))
print(df[df.Val>0])

Ergebnis

Optimal found. Ave prob. = 0.450, Any prob. = 0.381
  Place   Prob  Time    Var  Val
0     A  0.082  57.0  v0001  1.0
3     D  0.108  51.0  v0004  1.0
4     E  0.104   5.0  v0005  1.0
7     H  0.156  16.0  v0008  1.0

Die erwartete Häufigkeit, Wale zu sehen, beträgt 0,45. Die Wahrscheinlichkeit, es mehr als einmal zu sehen, beträgt jedoch 0,381.

Problem Nr. 2

Maximieren Sie die Wahrscheinlichkeit, innerhalb der Gesamtzeit mehr als einmal zu sehen ** 140 Minuten **

Antwort 2

Die Wahrscheinlichkeit, dass Sie es nie sehen werden, ist $ \ prod_i {(1-Prob_i)} $. So wie es ist, ist es nicht linear, aber linearisieren wir es mit $ \ log $ (was eine monotone Funktion ist).

python

m = LpProblem(sense=LpMaximize)
df['Var'] = addbinvars(n)
m += -lpDot(np.log(1-df.Prob),df.Var)
m += lpDot(df.Time,df.Var) <= 140
m.solve()
df['Val'] = df.Var.apply(value)
print('%s found. Ave prob. = %.3f, Any prob. = %.3f'%(LpStatus[m.status],
      df[df.Val>0].Prob.sum(), 1-(1-df[df.Val>0].Prob).prod()))
print(df[df.Val>0])

Ergebnis

Optimal found. Ave prob. = 0.444, Any prob. = 0.383
  Place   Prob  Time    Var  Val
2     C  0.184  89.0  v0011  1.0
4     E  0.104   5.0  v0013  1.0
7     H  0.156  16.0  v0016  1.0

Die Wahrscheinlichkeit, es mehr als einmal zu sehen, ist leicht von 0,381 auf 0,383 gestiegen.

das ist alles