Образец выполнения. Найти минимальное остовное дерево графа, представленного на рис

Пример.

Найти минимальное остовное дерево графа, представленного на рис. 6.

Рис. 6. Исходные данные задачи

Решение:

1. Зададим начальные значения переменных:

2. Введем линейную целевую функцию:

3. Введем ограничения задачи:

4. Определим оптимальное решение задачи с помощью встроенной функции Minimize:

5. Найдем длину остовного дерева:

ВЫВОД: Кратчайшее остовное дерево 1-3; 2-3; 3-5; 4-5; 4-7; 5-6. Длина остовного дерева 28.

ВАРИАНТЫ ЗАДАНИЙ

На рис. 7 показана транспортная сеть, соединяющая населенные пункты, и расстояния между ними. Найдите кратчайшее остовное дерево для своего варианта.

Варианты	Города
	Чебоксары – Мариинский Посад – Цивильск – Урмары – Янтиково – Канаш – Калинино
	Чебоксары – Новочебоксарск – Цивильск – Урмары – Янтиково – Канаш – Калинино
	Чебоксары – Новочебоксарск – Тюрлема – Урмары – Янтиково – Канаш – Калинино
	Чебоксары – Мариинский Посад – Тюрлема – Урмары – Янтиково – Канаш – Калинино
	Чебоксары – Красноармейское – Цивильск – Урмары – Янтиково – Канаш – Калинино
	Чебоксары – Красноармейское – Калинино – Аликово – Красные Четаи – Ядрин – Моргауши
	Чебоксары – Калинино – Шумерля – Красные Четаи – Ядрин – Моргауши
	Канаш – Комсомольское – Яльчики – Батырево – Ибреси – Вурнары – Калинино
	Канаш – Комсомольское – Яльчики – Алатырь – Ибреси – Вурнары – Калинино
	Новочебоксарск – Цивильск – Канаш – Ибреси – Вурнары – Калинино – Чебоксары
	Канаш – Ибреси – Батырево – Алатырь – Порецкое – Шумерля – Калинино
	Алатырь – Порецкое – Шумерля – Калинино – Канаш – Ибреси – Батырево

Рис. 7. Транспортная сеть Чувашии

ЛАБОРАТОРНАЯ РАБОТА № 19

ЗАДАЧА ПОИСКА КРАТЧАЙШЕГО ПУТИ