Vous allez voir des baleines pendant les vacances d'été. Utilisez Optimisation de combinaison pour déterminer lequel des huit points choisir.
Afficher les informations de point avec python
import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addbinvars
n = 8 #points
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)
| Place | Prob | Time | |
|---|---|---|---|
| 0 | A | 0.082 | 57.0 |
| 1 | B | 0.182 | 93.0 |
| 2 | C | 0.184 | 89.0 |
| 3 | D | 0.108 | 51.0 |
| 4 | E | 0.104 | 5.0 |
| 5 | F | 0.152 | 83.0 |
| 6 | G | 0.178 | 83.0 |
| 7 | H | 0.156 | 16.0 |
L'endroit représente le ** nom ** du point, Prob représente la ** probabilité ** de voir la baleine et le temps représente le ** temps ** (minutes) nécessaire pour se déplacer et observer le point.
Maximiser la somme des ** probabilités ** dans le temps total ** 140 minutes **
Problème de sac à dos, résolvons-le rapidement.
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])
résultat
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
Le nombre de fois prévu pour voir des baleines est de 0,45. Cependant, la probabilité de le voir plus d'une fois est de 0,381.
Maximisez la probabilité de voir plus d'une fois dans le temps total ** 140 minutes **
La probabilité de ne pas le voir même une fois est $ \ prod_i {(1-Prob_i)} $. En l'état, il n'est pas linéaire, mais linéarisons-le en utilisant $ \ log $ (qui est une fonction monotone).
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])
résultat
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
La probabilité de le voir plus d'une fois a légèrement augmenté de 0,381 à 0,383.
c'est tout
Recommended Posts