Рассмотрим следующую ситуацию. Допустим вы хотите поехать за границу, но валюту вам не меняют — вы можете перевезти с собой лишь товары для реализации на свободном рынке «там». С собой в самолет разрешено взять не более 20 кг. Возникает вопрос – какие товары взять, чтобы перевезти максимальную ценность, учитывая ограничение по весу? Водку (17$ / 1,5 кг), большую матрешку (30$ / 2,5 кг), балалайки (75$ / 6 кг) или еще что-то и в каких количествах?
Напрашивается решение – найти товар с самым лучшим соотношением цена/вес и взять его в максимальном количестве.
Посмотрим – 3 балалайки * 75$ + 1 бутылка * 17$ = 242$ (общий вес 19,5 кг). Осталось неиспользованными полкило, которые можно задействовать по-другому:
2 балалайки * 75$ + 2 большие матрешки * 30$ + 2 бутылки * 17$ = 244$ (общий вес 20 кг).
Т.е. «на глазок» не всегда может получиться самый выгодный вариант. К тому же, часто возникают дополнительные ограничения (больше 2-х бутылок не вывезти, в продаже всего 1 балалайка), да и при большом количестве товаров ручной подсчет затруднителен. Поэтому задачу формализуют для решения на компьютере.
Задача в общем виде (knapsack problem): Имеется набор предметов, каждый с определенным весом и определенной стоимостью. Из этого набора необходимо выбрать предметы с максимальной стоимостью, с учетом ограничения на максимальный вес (вес «рюкзака»).
Если в задаче можно только либо брать, либо не брать определенный товар, то задача будет бинарной (0-1 knapsack problem).
Если бы число предметов не предполагалось целым, то задача бы решалась как задача линейного программирования, например, симплекс-методом.
Вследствие целочисленности числа предметов, задача становится задачей целочисленного линейного программирования и решается методом ветвей и границ (branchAndBound или branchAndCut). Этот метод уже реализован в математических пакетах для многих языков программирования (обсудить его можно будет в специальном материале).
В нашем случае решать задачу предлагается с помощью свободно распространяемого решателя COIN-OR (www.coin-or.org) или GLPK (http://www.gnu.org/software/glpk/glpk.html), для которых есть удобная «обертка» на Python – PuLP. PuLP доступен в Google Code (http://code.google.com/p/pulp-or/).
Используя PuLP, получается вот такой код:
Файл можно загрузить отсюда: knapsack.py
В результате работы скрипта получаем решение:
Приятно видеть, что для данной задачи нам удалось его обнаружить самим.
Продолжая эксперименты вы можете увеличивать количество переменных, вводить новые ограничения. К тому же, большое количество других примеров можно найти в документации к PuLP (PDF)
Напрашивается решение – найти товар с самым лучшим соотношением цена/вес и взять его в максимальном количестве.
Посмотрим – 3 балалайки * 75$ + 1 бутылка * 17$ = 242$ (общий вес 19,5 кг). Осталось неиспользованными полкило, которые можно задействовать по-другому:
2 балалайки * 75$ + 2 большие матрешки * 30$ + 2 бутылки * 17$ = 244$ (общий вес 20 кг).
Т.е. «на глазок» не всегда может получиться самый выгодный вариант. К тому же, часто возникают дополнительные ограничения (больше 2-х бутылок не вывезти, в продаже всего 1 балалайка), да и при большом количестве товаров ручной подсчет затруднителен. Поэтому задачу формализуют для решения на компьютере.
Задача в общем виде (knapsack problem): Имеется набор предметов, каждый с определенным весом и определенной стоимостью. Из этого набора необходимо выбрать предметы с максимальной стоимостью, с учетом ограничения на максимальный вес (вес «рюкзака»).
Если в задаче можно только либо брать, либо не брать определенный товар, то задача будет бинарной (0-1 knapsack problem).
Если бы число предметов не предполагалось целым, то задача бы решалась как задача линейного программирования, например, симплекс-методом.
Вследствие целочисленности числа предметов, задача становится задачей целочисленного линейного программирования и решается методом ветвей и границ (branchAndBound или branchAndCut). Этот метод уже реализован в математических пакетах для многих языков программирования (обсудить его можно будет в специальном материале).
В нашем случае решать задачу предлагается с помощью свободно распространяемого решателя COIN-OR (www.coin-or.org) или GLPK (http://www.gnu.org/software/glpk/glpk.html), для которых есть удобная «обертка» на Python – PuLP. PuLP доступен в Google Code (http://code.google.com/p/pulp-or/).
Используя PuLP, получается вот такой код:
- #-*- coding: cp1251 -*-
- # импортируем функции PuLP
- from pulp import *
-
- # Создаем новую задачу Линейного программирования (LP) с максимизацией целевой функции
- prob = LpProblem("Knapsack problem", LpMaximize)
-
- # Переменные оптимизации, целые
- x1 = LpVariable("x1", 0, 10, 'Integer')
- x2 = LpVariable("x2", 0, 10, 'Integer')
- x3 = LpVariable("x3", 0, 10, 'Integer')
-
- # Целевая функция ("ценность рюкзака")
- prob += 17*x1 + 30*x2 + 75*x3, "obj"
-
- # Ограничение ("вес рюкзака")
- prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1"
-
- # Запускаем решатель
- prob.solve()
-
- # Выводим статус задачи
- print "Status:", LpStatus[prob.status]
-
- # Выводим получившиеся оптимальные значения переменных
- for v in prob.variables():
- print v.name, "=", v.varValue
-
- # Выводим оптимальное значение целевой функции
- print ("objective = %s$" % value(prob.objective))
* This source code was highlighted with Source Code Highlighter.
Файл можно загрузить отсюда: knapsack.py
В результате работы скрипта получаем решение:
~$ python knapsack.py
Status: Optimal
x1 = 2.0
x2 = 2.0
x3 = 2.0
objective = 244.0$
Приятно видеть, что для данной задачи нам удалось его обнаружить самим.
Продолжая эксперименты вы можете увеличивать количество переменных, вводить новые ограничения. К тому же, большое количество других примеров можно найти в документации к PuLP (PDF)