2. Распределение средств во взаимоисключающие направления.

Задачи такого типа, когда имеются направления, исключающие друг друга, называются «задачàìè о ранце».

Пусть есть альтернативы принятия каких-либо решений. Другими словами можно брать несколько предметов из ранца, но на них накладывается какое-либо ограничение. То есть можно брать определенное количество предметов из круга возможных так, чтобы они удовлетворяли имеющемуся ограничению. У каждого предмета своя ценность и свой вес.

x	1	2	3	4	5	6
а	1	2	5	4	4	4
c	3	3	4	5	4	1
с/a	3	3/2	4/5	5/4	1	1/4
Выбор	+	+		+	+

Задачу можно решить, через удельную ценность предмета, т.е. вычислив сколько стоит 1 единица предмета. Например, в таблице а_i — вес предмета, с_i — стоимость предмета, c_i/a_i — удельная стоимость предмета. Допустим, имеется ограничение на вес — в сумме предметы должны давать не более 12. То есть:

Теперь, определив удельные стоимости каждого предмета, мы ранжируем из по убыванию этой удельной стоимости и по порядку выбираем самые ценные, смотря, чтобы сумма их весов не превысила наше установленное ограничение.

В результате мы находим оптимальное решение: <1, 2, 4, 5>.

Если бы в задаче добавлялось еще одно ограничение, то мы проверяли бы сразу два ограничения. В случае множества ограничений, нужно выбирать основным то ограничение, которое более жесткое.

Кривая Парето.

Схема «ветвей и границ».

В случае наличия еще одного

ограничения его включают тем

тем же образом (т.е. расчет c/a è ò.ä.)

В качетсве исходного берется более

жесткое ограничение

()

В принципе можно решить N «задач

о ранце», но это приведет к

усложнению логики задачи.