ЗАДАНИЕ 6.    Тема:   «ЦЕЛОЧИСЛЕННОЕ И ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ». ЦЕЛОЧИСЛЕННАЯ ЗАДАЧА.

Задача 6.1.

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

Решить задачу методом ветвей и границ. Данные необходимые для решения, приведены в табл. 6.1.

Таблица  6.1

ЗАДАЧА ДИСКРЕТНОГО ПРГРАММИРОВАНИЯ. ЗАДАЧА КОММИВОЯЖЕРА.

Задача 6.2.

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

Задана матрица расстояний между городами c_ij. (см.условия задачи).

Сформулированная задача - задача целочисленная. Пусть х_ij = 1 , если путешественник переезжает из i -ого города в j-ый и х_ij = 0, если это не так.

Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.

Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u₁ = 0, u_n+1 = n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x_ij и переменные u_i. ( u_i целые неотрицательные числа).

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

Необходимые данные приведены ниже.

Условия задачи 6.2.   Матрица расстояний c_ij

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 0