質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.61%

複数の制約下において最も価値が高くなる組み合わせを求めたい。

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,636

score 13

前提・実現したいこと

以下の様な複数の制約下においてもっとも価値が高くなる組み合わせを求めることを Python で実現したいのですが、どのようなアルゴリズムを採用すべきか皆目見当がつきません。

レストランにおいて、いくつかの制約を抱えた上で最も満足度(S)の高いメニューの組み合わせを求めたい。
いくつかの制約とは、所持金(M)、摂取カロリー(C)、胃の容積(V)である。
Mmax = 3000(yen)
Cmax = 1000(kcal)
Vmax = 300(mL)

リゾット M = 800(yen), C = 400(kcal), V = 100(mL), S = 30
パスタ M = 900(yen), C = 500(kcal), V = 120(mL), S = 25
サラダ M = 300(yen), C = 50(kcal), V = 50(mL), S = 10
スープ M = 500(yen), C = 150(kcal), V = 100(mL), S = 12
味噌汁 M = 500(yen), C = 100(kcal), V = 90(mL), S = 13
ハンバーグ M = 1000(yen), C = 800(kcal), V = 200(mL), S = 50

ナップサック問題の一種なのでは、とは思っているのですが検索ワードも全く見当がつかないため、今回質問させていただきました。
ご教示いただけますと幸いです。よろしくお願いいたします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+2

典型的な 線形計画問題 と思われます。
Python だと pulp という最適化問題を解くためのライブラリがあります。

import pulp

# メニュー一覧
menus = [['リゾット', 800, 400, 100, 30],
         ['パスタ', 900, 500, 120, 25],
         ['サラダ', 300, 50, 50, 10],
         ['スープ', 500, 150, 100, 12],
         ['味噌汁', 500, 100, 90, 13],
         ['ハンバーグ', 1000, 800, 200, 50]]
num_menus = len(menus)

# 線形計画問題を作成する。
prob = pulp.LpProblem('Menu Selection Problem', pulp.LpMaximize)

# 変数を作成する。
x = [pulp.LpVariable('x[{}]'.format(i), 0, 10, 'Integer')
     for i in range(num_menus)]

# 目的関数を作成する。
obj = 0
for i in range(num_menus):
    obj += menus[i][4] * x[i]
prob += obj

# 制約条件
money, calorie, volume = 0, 0, 0
for i in range(num_menus):
    money += menus[i][1] * x[i]
    calorie += menus[i][2] * x[i]
    volume += menus[i][3] * x[i]
prob += (money <= 3000)  # 金額
prob += (calorie <= 1000)  # カロリー
prob += (volume <= 300)  # 胃の容量

# 線形計画問題の概要を表示する。
print(prob)

# 解を求める。
status = prob.solve()
print('Status', pulp.LpStatus[status])

total = 0
for i, menu in enumerate(menus):
    cnt = int(pulp.value(x[i]))
    print('{} ({}, {}, {}, {}): {}品'.format(*menu, cnt))
    total += menu[4] * cnt
print('満足度', total)

定式化

目的関数 (最大化)
# 満足度を最大化
30*x_0_ + 25*x_1_ + 10*x_2_ + 12*x_3_ + 13*x_4_ + 50*x_5_ + 0

制約条件
# 費用の合計は3000円以下
_C1: 800 x_0_ + 900 x_1_ + 300 x_2_ + 500 x_3_ + 500 x_4_ + 1000 x_5_ <= 3000
# カロリーの合計は1000以下
_C2: 400 x_0_ + 500 x_1_ + 50 x_2_ + 150 x_3_ + 100 x_4_ + 800 x_5_ <= 1000
# 胃の容量の合計は300以下
_C3: 100 x_0_ + 120 x_1_ + 50 x_2_ + 100 x_3_ + 90 x_4_ + 200 x_5_ <= 300

変数 (0 ~ 10個注文できる)
0 <= x_0_ <= 10 Integer
0 <= x_1_ <= 10 Integer
0 <= x_2_ <= 10 Integer
0 <= x_3_ <= 10 Integer
0 <= x_4_ <= 10 Integer
0 <= x_5_ <= 10 Integer

答え

Status Optimal
リゾット (800, 400, 100, 30): 2品
サラダ (300, 50, 50, 10): 2品
満足度 80

使い方は公式ドキュメントや Qiita の記事を参考にしてください。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/02/28 14:48

    ご丁寧に利用すべきモジュールや非常に参考になるサンプルコードを提示してくださり、誠にありがとうございます。
    tiitoi 様のご回答を参考にコードを書いてみたいと思います。重ね重ねになりますが、この度は誠にありがとうございました。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る