Решение классических задач оптимизации

Первую в истории оптимизационную задачу сформулировал Леонардо Фибоначчи, итальянский математик XIII века. Его задача "О гирях" посвящена проблеме взвешивания с помощью рычажных весов и создания оптимальной системы гирь для этой цели.

Задача о рюкзаке

Одно из первых упоминаний об этой задаче можно найти в статье Джорджа Балларда Мэтьюса, датированной 1897 годом.

Пусть имеется набор предметов, каждый из которых имеет два параметра – вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. Дополнительно в задаче может быть оговорено максимальное количество предметов одного типа в рюкзаке (требование ассортимента).

В общем случае задача о рюкзаке бывает нескольких типов: простейший рюкзак (каждый предмет можно положить только в одном экземпляре), ограниченный рюкзак (каждый предмет кладется не более m раз), неограниченный рюкзак (каждый предмет можно укладывать сколько угодно раз), рюкзак с мультивыбором (все предметы разделены на S классов, обязательно вложить хотя бы один предмет каждого класса), мультипликативный рюкзак (имеется несколько рюкзаков, каждый со своей вместимостью) и многомерный рюкзак (у каждого предмета есть несколько характеристик, например, вес и объем, а у рюкзака – несколько ограничений).

Исходные данные к задаче представлены в табл. 15.2.

Табл. 15.2

№ предмета	Стоимость	Вес	Количество в рюкзаке
1
2
…	…	…	…

…	…	…	…

Здесь – количество предметов -го типа, которые нужно положить в рюкзак. – целое, для тех предметов, которые в рюкзак класть не имеет смысла, Суммарный вес вещей , суммарная их стоимость – .

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

Целевая функция будет иметь вид .

Пример организации данных в таблице Microsoft Excel (целевая функция выделена красным) показан на рис. 15.11.

Рис. 15.11 Задача о рюкзаке

Транспортная задача

Эта задача была впервые формализована французским математиком Гаспаром Монжем в 1781 году.

Допустим, требуется составить план перевозок однородного груза таким образом, чтобы общая стоимость перевозок была минимальной. Исходные данные к задаче представлены в табл. 15.3.

Табл. 15.3

Поставщики

Потребители

Запасы поставщиков

…

Спрос потребителей

…

Здесь – количество единиц груза, которые нужно вывезти из i -го пункта отправления (); – количество единиц груза, которое нужно привезти в j-й пункт назначения (); – стоимость перевозки единицы груза из i -го пункта в j -й, зависит от расстояния между пунктами и некоторых других факторов. Обозначим через количество единиц груза для перевозки из i -го пункта в j -й. Тогда можно записать: общая (суммарная) стоимость перевозок ; количество груза, вывозимого из i- го пункта ; количество груза, доставляемого в j -й пункт . Количество вывезенного груза должно быть равно количеству принятого.

В рассматриваемом случае должны выполняться как минимум следующие условия (они будут ограничениями задачи): , ; , ; .

Целевая функция представляет собой суммарную стоимость перевозок и имеет вид: .

Пример организации данных в таблице Microsoft Excel показан на рис. 15.12.

Рис. 15.12 Транспортная задача

Задача коммивояжера

Задача коммивояжёра (коммивояжёр – разъездной торговый агент) – одна из самых известных задач оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные точки хотя бы по одному разу с последующим возвратом в исходную точку. Допустим, нам необходимо посетить каждую точку строго один раз. Исходные данные к задаче представлены в табл. 15.4.

Здесь – стоимость переезда из i -го пункта в j -й, зависит от расстояния между пунктами и некоторых других факторов. Обозначим через двоичную переменную факт переезда коммивояжера из пункта в пункт . , если перемещение имеет место, и 0, если нет. Тогда можно записать: общие (суммарные) затраты на разъезды .

Каждый из пунктов нужно посетить только один раз. Чтобы отследить этот факт, введем переменные – количество выездов из пункта i, , , и – количество въездов в пункт j, , (). Величины и должны быть равны 1 для всех i и j.

Решение задачи с такими условиями может привести к неверному результату, когда будет определено несколько непересекающихся оптимальных кольцевых маршрутов. Чтобы маршрут был один, приходится ввести еще одну проверку. Будем считать, что коммивояжер выезжает из пункта 1 (и возвращается в него же). Тогда можно ввести переменную , характеризующую очередность въезда в пункт j. Для пункта, в который коммивояжер приедет из пункта 1, будет равно 0, для следующего пункта – 1, и т.д. В этом случае существование единственного замкнутого маршрута будет описано условием , где , .

Табл. 15.4

№ пункта	№ пункта										Количество въездов в пункт
	1		2		…	j		…	n
1		–			…			…

2				–	…			…

…	…				…	…		…	…		…
i					…		–	…

…	…		…		…	…		…	…		…
n					…			…		–

Количество выездов из пункта					…			…
Порядок посещения пункта	–				…			…