안녕하세요.
오늘 나는 위치를 바꾸는 문제를 통해 정수 계획 문제와pup의 기본 내용을 소개하고 싶다.
정수 계획 문제는 가장 최적화된 문제의 해결 방안에 정수의 제약을 넣은 것을 가리킨다.
오늘은 위치를 바꾸는 문제와 내가 제멋대로 명명한 문제로 정수 계획 문제를 설명한다.
좌석 바꾸기 문제란 정해진 좌석 수 가운데 각자 좌석에 대한 희망을 갖고 전체적인 희망을 최대한 충족시키기로 한 좌석 바꾸기 문제다.
그림에서 보듯이 아래와 같다.

공식화

수학 공식화.
학생$i$좌석 수차례 희망도 벡터 $W나는 달러가 있다.
학생 대표의 좌석 벡터는 $i$$$$$xi$로 정의합니다. 자리에 앉으면 1, 안 앉으면 0 입니다.이 $x이것은 i$i가 구하는 변수입니다.
학생 집합은 $I, 좌석 집합은 $S 입니다.
목적 함수{i\in I} {W_i}^t x_$i.전체적인 희망도를 극대화하기 위해 이 목표 함수를 극대화합니다.
제약에 가입하다.
한 자리에 한 사람만 앉을 수 있다

\displaystyle \sum_{i \in I} x_{ij} = 1 \ (\forall j)

제약 ② 한 사람이 한 자리만 앉을 수 있다

\displaystyle \sum_{j \in S} x_{ij} = 1 \ (\forall i)

자리에 앉다

x_{ij} \in \{ 0 ,1 \} \ (\forall i\in I, \forall j\in S )

총괄적으로 말하면 이번에 해결된 가장 최적화된 문제는 다음과 같다.

\begin{align}
Maximize \hspace{22pt}& \displaystyle \sum_{i \in I} {W_i}^t x_i\\
subject \ to \displaystyle \sum_{i \in I} x_{ij} &= 1 \ (\forall j)\\
\displaystyle \sum_{j \in S} x_{ij} &= 1 \ (\forall i)\\
x_{ij} &\in \{ 0 ,1 \} \ (\forall i, \forall j )
\end{align}

pup을 통해 실현

공식화가 끝난 후pup을 사용하여 설치합니다.
pup의 사용 방법에 관하여 아래의 문장은 매우 총괄적이다.
https://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17
seat_change.py

import pulp
import random
import numpy as np


def main():
    n = 10
    seat = n
    W = np.zeros([seat,n])

    #値を入れる
    for i in range(seat):
        for j in range(n):
            W[i,j] = random.random()

    # 各行を割合に変換
    sumbox = W.sum(axis=0, dtype='float') 
    W /= sumbox


    # 問題の宣言
    problem = pulp.LpProblem(name='change seat', sense=pulp.LpMaximize)

    # 変数の宣言
    x = {(i,j):pulp.LpVariable(name='x_{}_{}'.format(i, j), cat='Binary') for i in range(seat) for j in range(n)}

    # 目的関数
    problem += pulp.lpSum([W[i,j]*x[i,j] for i in range(seat) for j in range(n)])

    #一つの席には一人だけ
    for i in range(seat):
        problem.addConstraint((pulp.lpSum([x[i,j] for j in range(n)]) == 1),"seat_limitation_{}".format(i))

    #ユーザーは１つの席のみに入る
    for j in range(n):
        problem.addConstraint((pulp.lpSum([x[i,j] for i in range(seat)]) == 1),"user_gets_onlyoneseat_{}".format(j))

    status = problem.solve()
    print(pulp.LpStatus[status])
    print("目的関数値 = {}".format(pulp.value(problem.objective)))


    for j in range(n):
        for i in range(seat):
            if pulp.value(x[i,j]) > 0:
                print(f'user {j} seat {i} : {pulp.value(x[i,j])}')



if __name__ == '__main__':
    main()

③의 제한 사항은 변수 선언에 "Binary"형식으로 포함됩니다.
또 이번 학생들의 희망도는 랜덤수다.
실행 후 다음과 같은 결과를 얻을 수 있다.

이렇게 하면 pup으로 좌석 교환 문제를 해결할 수 있다.

최후

정수계획법이 해결하는 좋은 부분 중 하나로서 이 기본적인 문제에 대한 추가 제한을 통해 하고 싶은 문제를 해결할 수 있다.
예컨대
남에게 가중을 주어 우선도를 고려하다
이웃의 조건을 더하다
잠깐만요.어떻게 공식화할지 생각해 보세요.