これなに

ブルーバックスの離散数学「ものを分ける理論」のくだものを姉妹で分ける問題を読んでちょっとアレンジしました。

問題

6つのくだものがあります。
2人の姉妹で、分けます。
各々の価値観は異なります（それぞれ、価値の合計が100になるように、各くだものごとに点数をつけています）。
くだものは、なるべく分割しないで分けましょう。分割すると、価値はどちらも6割に減少するものとします。
各々の価値観で、価値の総和の最小を最大化してください。

Pythonで定式化して解く

例によって、PuLPで解きます。変数は下記の通り。定式化は簡単なので省略。

ライブラリーは、pip install pandas pulp ortoolpyでインストールしてください。

import pandas as pd
from pulp import LpProblem, LpMaximize, lpDot, lpSum, value, GLPK_CMD
from ortoolpy import addvar, addvars, addbinvars
def divide(df, rate = 0.6):
   # assert (df[['A', 'B']].sum() == 100).all()
    df['VarA'] = addbinvars(len(df))  # Aが貰う
    df['VarB'] = addbinvars(len(df))  # Bが貰う
    df['VarP'] = addvars(len(df))  # 分割してAが貰う割合
    df['VarQ'] = addvars(len(df))  # 分割してBが貰う割合
    m = LpProblem(sense=LpMaximize)
    obj = addvar()
    val_a = lpDot(df.A, df.VarA) + rate * lpDot(df.A, df.VarP)
    val_b = lpDot(df.B, df.VarB) + rate * lpDot(df.A, df.VarQ)
    m += obj
    m += obj <= val_a
    m += obj <= val_b
    for row in df.itertuples(False):
        m += row.VarA + row.VarB + row.VarP + row.VarQ == 1
    cmd = GLPK_CMD()
    m.solve(cmd)
    if m.status == 1:
        for c in 'ABPQ':
            df[f'Val{c}'] = df[f'Var{c}'].apply(value)
        return value(val_a), value(val_b)
    return -1, -1

divideは2人の価値の総和を返します。

df = pd.DataFrame([[36, 32], [24, 38], [12, 7], [12, 13], [10, 5], [6, 5]], 
    columns=['A', 'B'],
    index='もも めろん りんご みかん ぶどう ばなな'.split())
print(divide(df))
df
>>>
(58.0, 56.0)

	A	B	VarA	VarB	VarP	VarQ	ValA	ValB
もも	36	32	v000001	v000007	v000013	v000019	1	0
めろん	24	38	v000002	v000008	v000014	v000020	0	1
りんご	12	7	v000003	v000009	v000015	v000021	1	0
みかん	12	13	v000004	v000010	v000016	v000022	0	1
ぶどう	10	5	v000005	v000011	v000017	v000023	1	0
ばなな	6	5	v000006	v000012	v000018	v000024	0	1

「もも、りんご、ぶどう」（価値58）と「めろん、みかん、ばなな」（価値56）に分かれました。

ちょっと不公平ですね。
分割しても、価値が減少しないものとして、解きなおしてみましょう。

print(divide(df, 1))
df
>>>
(57.499995999999996, 57.500004000000004)

	A	B	VarA	VarB	VarP	VarQ	ValA	ValB	ValP	ValQ
もも	36	32	v000026	v000032	v000038	v000044	1	0	0.000000	0.000000
めろん	24	38	v000027	v000033	v000039	v000045	0	1	0.000000	0.000000
りんご	12	7	v000028	v000034	v000040	v000046	0	0	0.458333	0.541667
みかん	12	13	v000029	v000035	v000041	v000047	0	1	0.000000	0.000000
ぶどう	10	5	v000030	v000036	v000042	v000048	1	0	0.000000	0.000000
ばなな	6	5	v000031	v000037	v000043	v000049	1	0	0.000000	0.000000

りんごを分割して、2人とも57.5になりました。

補足

ソルバーとしてデフォルトのCBCではなくて、GLPKを使っています。くだもの2個だとCBCはバグって最適解が出ません。

GLPKは、macOSだとbrew install glpkでできます。Windowsの人は、頑張ってください。

lpDot

lpDotは、係数と変数リストでないといけません。

lpDot(df.A, df.VarA) + rate * lpDot(df.A, df.VarP)をlpDot(df.A, df.VarA + rate * df.VarP)とすると、rateが無視されるので注意しましょう。

以上

組合せ最適化で「ものを分ける」

これなに

問題

Pythonで定式化して解く

補足

lpDot