이게 뭐야

광자 로켓에서 1열에 이르는 1000개의 별을 조사한다.

외계인이 있는지 확인합시다. 다만, 모든 별을 조사할 수는 없다.

별마다 조사 시간은 다르다. 조사 대상 별의 조사 시간의 합은 10000일 이내로 한다.

별마다 발견 확률을 추정하고 있다. 조사 대상 별의 발견 확률의 합을 극대화하라.

풀어봐

냅삭 문제 로 생각할 수 있다. 파이썬으로 풀어 보자.
Python에 의한 수리 최적화에 대해서는 참고 링크를 참조하십시오.

python3

import numpy as np
from pulp import *
np.random.seed(1)
星数 = 1000
調査時間 = np.random.randint(10,100,星数)
発見確率 = np.random.random(星数)/100000
m = LpProblem(sense=LpMaximize)
x = [LpVariable('x%.4d'%i, cat=LpBinary) for i in range(星数)]
m += lpDot(発見確率,x)
m += lpDot(調査時間,x) <= 10000
m.solve()
print(value(m.objective)) # 発見確率の総和
>>>
0.0022822674119170536

사실, 로켓은 최대 항속 가능 거리가 있습니다. 여기서는 단순히 거리가 아니라 최대 홉 수 +1을 mx로 한다.
mx를 바꿀 때 목적 함수가 어떻게 될지 살펴 보자. 가로축은 mx, 세로축은 목적 함수이다.

python3

r = []
for mx in range(4,17):
    m = LpProblem(sense=LpMaximize)
    x = [LpVariable('x%.4d'%i, cat=LpBinary) for i in range(星数)]
    m += lpDot(発見確率,x)
    m += lpDot(調査時間,x) <= 10000
    for i in range(星数-mx+1):
        m += lpSum(x[i:i+mx]) >= 1 # mx以内に1か所以上調査する
    m.solve()
    r.append(value(m.objective))

%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(range(4,17),r)
plt.hlines(0.0022822674119170536,4,16);

확대해 본다.

python3

plt.plot(range(4,17),r)
plt.hlines(0.0022822674119170536,4,16)
plt.xlim((9,16))
plt.ylim((0.00227,0.0023));

디폴트의 ​​무료 솔버 CBC라면 오차 탓에 제약조건이 엄격한 편이 해가 좋아지거나 하고 있다.

상용 솔버는 더 정확하게 해결되었습니다.



참고 링크
- 최적화에서 Python - Qiita

이상