Вопросы для самоконтроля:

1. Перечень вопросов решаемых в задаче коммивояжера.

2. Методы решения задачи коммивояжёра.

3. Математическая постановка задачи коммивояжёра ее модель.

Список использованной литературы:

1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., «Мир», 1965, 174 с.

2. В. П. Сигорский. Математический аппарат инженера. - К., «Техніка», 1975, 768 с.

3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.

Лабораторная работа № 4

Тема лабораторной работы: Оптимизационные задачи линейного программирования с булевыми переменными и их решение средствами Excel.

Цель лабораторной работы: Получение навыков в решении задач о ранце

Программное обеспечение: Microsoft Excel

Основные сведения: Задача о ранце (рюкзаке) – одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные задачи часто возникают на транспорте, прикладной математике, экономики. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

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

Математическая постановка задачи. Морское судно грузоподъемностью M тыс. т. И вместимостью V тыс куб.м. может быть использовано для перевозки n видов неделимых грузов, имеющих массу m_i, объем v_i и стоимость c_i.

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

П остроение математической модели. Обозначим через x_i количество единиц i-го груза загружаемого на судно. Целевая функция, выражающая суммарную стоимость груза на судне, будет равна:

(1)

Ограничения задачи диктуются ограничением на грузоподъемность судна

(2)

и ограничением на вместимость судна

(3)

Количество единиц грузов не может быть отрицательным и дробным, т.к. все грузы неделимы, поэтому

x_i ≥ 0, целые,   i = 1, …, n

Пример решения задачи о ранце в программной среде Microsoft Excel:. Организация арендует баржу грузоподъемностью 83 т, на которой предполагает перевозить груз, состоящий из предметов четырех типов. Веса и стоимости предметов равны соответственно 24 т, 22 т, 16 т, 10 т и 96 у.е., 85 у.е., 50 у.е., 20 у.е. Требуется погрузить на баржу груз максимальной стоимости.

Экономико-математическая модель

Введем необходимые обозначения: пусть х_j (j = 1,2,3,4) — число предметов j-го типа, которое следует погрузить на баржу. Тогда ЭММ задачи о подборе для баржи допустимого груза максимальной ценности запишется следующим образом:

max f(x₁, х₂, х₃, х₄) = 96х₁ + 85х₂ + 50х₃ + 20х₄,

24x₁ + 22х₂ + 16х₃ + 10х₄ ≤ 83,

х_j (j = 1,2,3,4) – целые неотрицательные.

Решение. Приведенная ЭММ является моделью задачи целочисленного линейного программирования (ЦЛП). Для реализации этой модели средствами Excel в диалоговом окне режима Поиск решения с помощью кнопки Добавить следует ввести ограничение целочисленности переменных (целые числа в изменяемых ячейках). Специализированный (рабочий) лист может быть подготовлен в виде, представленном на рис. 2.5. Формулы этого листа очевидны. Диалоговое окно, отвечающее приведенному выше рабочему листу, представлено на рис. 2.5.

Результаты реализации разработанной ЭММ приведены ниже в таблице

Рис.1. Схема решения задачи о ранце

Таким образом, рекомендуемое управленческое решение с позиций принятого критерия оптимальности — следует погрузить три предмета первого типа и один предмет четвертого типа. В этом случае стоимость груза составит 308 у.е., и одна тонна грузоподъемности будет не использована (ее можно использовать на другие цели).