Математическая модель

Математическое программирование 

вид занятия: Семинар

ЗАДАЧА КОММИВОЯЖЁРА

 

Примеры задач динамического программирования: оптимизация инвестиций в N предприятий с нелинейной зависимостью дохода от инвестиций, распределение финансов между отраслями на N лет,

 

Методы динамического программирования применяются при решении оптимизационных задач, в которых целевая функция или ограничения, или же и первое, и второе одновременно характеризуются нелинейными зависимостями:

1. Задача распределения инвестиций. Распределении инвестиций между предприятиями П₁, П₂,..., П_n. Инвестируемая сумма E усл. ден. ед.
2. Задача распределения ресурсов. Планируется работа двух предприятий на n лет. Начальные ресурсы равны s₀.
3. Метод прогонки.
4. Задача замены оборудования.
5. Складская задача: составить оптимальную программу выпуска продукции X, которая минимизирует суммарные издержки предприятия.
6. Задача Джонсона.
7. Задача о рюкзаке (решение задачи о загрузке транспортного средства).

Решение задачи о назначениях в программе Microsoft Excel1.

Задача о назначениях.

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

Задача

Для выполнения n работ могут быть использованы n работников. Эффективность i-го работника i = 1, …, n при выполнении им j-ой работы j = 1, …, n равна сij . Предполагается, что каждый работник может быть использован только на одной работе, а каждая работа может выполняться только одним работником. Определить, какую работу необходимо поручить каждому работнику, чтобы достичь максимальной эффективности по выполнению всех работ.

Математическая модель.

Введем переменную xij значение которой равно 1, если выполнение j-ой работы поручено i-му работнику, и равно 0, в противном случае. Тогда, поскольку на работе j может быть задействован только один работник, то справедливо равенство:

 .

Так как один работник может выполнять только одну работу, то справедливо следующее равенство:

 .

Целевая функция определяет эффективность всех работников при выполнении всех работ, которая должна быть максимальной

 .

По своей постановке эта задача относится к целочисленной транспортной задаче закрытого типа (суммарная мощность поставщиков равна суммарной мощности потребителей).

 

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

Имеется n городов. Расстояния между любой парой городов i и j известны и составляют cij . Коммивояжер выезжает из какого-либо города и должен посетить все города побывав в каждом только один раз и вернуться в исходный город. Ставится задача определить такую последовательность объезда городов, или маршрут, при которой суммарная длина маршрута была бы минимальной.