Классика оптимизации: задача рюкзака (knapsack problem)

Рассмотрим следующую ситуацию. Допустим вы хотите поехать за границу, но валюту вам не меняют — вы можете перевезти с собой лишь товары для реализации на свободном рынке «там». С собой в самолет разрешено взять не более 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, получается вот такой код:

1. #-*- coding: cp1251 -*-
2. # импортируем функции PuLP
3. from pulp import *
4.  
5. # Создаем новую задачу Линейного программирования (LP) с максимизацией целевой функции
6. prob = LpProblem("Knapsack problem", LpMaximize)
7.  
8. # Переменные оптимизации, целые
9. x1 = LpVariable("x1", 0, 10, 'Integer')
10. x2 = LpVariable("x2", 0, 10, 'Integer')
11. x3 = LpVariable("x3", 0, 10, 'Integer')
12.  
13. # Целевая функция ("ценность рюкзака")
14. prob += 17*x1 + 30*x2 + 75*x3, "obj"
15.  
16. # Ограничение ("вес рюкзака")
17. prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1"
18.  
19. # Запускаем решатель
20. prob.solve()
21.  
22. # Выводим статус задачи
23. print "Status:", LpStatus[prob.status]
24.  
25. # Выводим получившиеся оптимальные значения переменных
26. for v in prob.variables():
27.   print v.name, "=", v.varValue
28.  
29. # Выводим оптимальное значение целевой функции
30. 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)