Лабораторная работа 4 (Вариант 7), «Оптимизация функционирования производственной системы при заданных ограничениях по ресурсам и спросу», Гречишников Е.В. – Шабанов А.П. (Системный анализ и принятие решений, САПР) – Lindo

Цель выполнения работы

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

Постановка задачи

 Пусть имеется n пунктов и задана матрица c={cij} расстояний между ними. Выезжая из одного пункта, коммивояжер должен побывать во всех пунктах по одному и только по одному разу и вернуться в исходный пункт. Требуется определить: в каком порядке следует объезжать пункты, чтобы суммарное пройденное расстояние было бы минимальным (найти минимальный полный замкнутый маршрут).

Построение математической модели задачи.

Управляемые переменные. Введем переменные xij, показывающие истинность или ложность факта переезда из пункта i в пункт j. Переменные xij такие, что xij=1, если коммивояжер переезжает из пункта i в пункт j, и xij=0 - в противном случае.

Целевая функция имеет вид:

где сij - расстояние между пунктами i и j,

n - количество пунктов.

Система ограничений на значения управляемых переменных имеет вид:

- условия отъезда:

- условия прибытия:

- условия, обеспечивающие существование полного замкнутого маршрута:

где

 - произвольные целые и неотрицательные числа.