Опорное решение транспортной задачи

Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения, используют циклы.
Циклом называется такая последовательность клеток таблицы транспортной задачи, в которой две и только соседние клетки расположены в одной строке или столбце, причем первая и последняя также находятся в одной строке или столбце. Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи, i=1,2,...,m; j=1,2,...,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.

Приближенные методы решения транспортной задачи.
Метод вычеркивания (метод двойного предпочтения). Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждом столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным.
Метод «северо-западного угла» состоит в последовательном переборе строк и столбцов транспортной таблицы, начиная с левого столбца и верхней строки, и выписывании максимально возможных отгрузок в соответствующие ячейки таблицы так, чтобы не были превышены заявленные в задаче возможности поставщика или потребности потребителя. На цены доставки в этом методе не обращают внимание, поскольку предполагается дальнейшая оптимизация отгрузок.
Метод «минимального элемента». Отличаясь простотой данный метод все же эффективнее чем, к примеру, метод Северо-западного угла. Кроме того, метод минимального элемента понятен и логичен. Его суть в том, что в транспортной таблице сначала заполняются ячейки с наименьшими тарифами, а потом уже ячейки с большими тарифами. То есть мы выбираем перевозки с минимальной стоимостью доставки груза. Это очевидный и логичный ход. Правда он не всегда приводит к оптимальному плану.
Метод «аппроксимации Фогеля». При методе аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

ПРИМЕР №1. Матрица тарифов (здесь количество поставщиков равно 4, количество магазинов равно 6):

	1	2	3	4	5	6	Запасы
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	10	1	100	60
Потребности	10	30	40	50	70	30

Решение. Предварительный этап решения транспортной задачи сводится к определению ее типа, открытой она является или закрытой. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
Условие баланса соблюдается. Запасы равны потребностям. Итак, модель транспортной задачи является закрытой. Если бы модель получилась открытой, то потребовалось бы вводить дополнительных поставщиков или потребителей.
На втором этапе осуществляется поиск опорного плана методами, приведенными выше (наиболее распространенным является метод наименьшей стоимости).
Для демонстрации алгоритма приведем лишь несколько итераций.
Итерация №1. Минимальный элемент матрицы равен нулю. Для этого элемента запасы равны 60, потребности 30. Выбираем из них минимальное число 30 и вычитаем его (см. в таблице). При этом из таблицы вычеркиваем шестой столбец (потребности у него равны 0).

3	20	8	13	4	x	80
4	4	18	14	3	0	60 - 30 = 30
10	4	18	8	6	x	30
7	19	17	0	1	x	60
10	30	40	50	70	30 - 30 = 0	0

Практическая работа № 8

1. Тема практического занятия «Составление расписаний и схемы движения по маршруту. »

2. Количество часов  2 часа        

3. Место проведения аудитория № 309(А)

4. Характер работы: частично – поисковый

5. Форма организации учебной деятельности студентов групповая

6. Цель практического занятия: обобщение, закрепление и углубление теоретических знаний; формирование умения анализировать материал, выступать перед аудиторией и вести дискуссию по обсуждаемым проблемам.

7. Пример выполнения работы:

– Расписание движения автобусов по маршруту

Наименование и вид маршрута	Перевозчик	Марка автобуса	Протяжённость маршрута, км	Периодичность, раз/нед
Минск-Рига, регулярный	U-Trans	NEOPLAN-INTEGRAL N122
Туда	Наименование остановочных пунктов	Обратно
прибытие,	стоянка,	отправление	прибытие	стоянка,	отправление,
ч.мин.	ч.мин.	ч.мин		ч.мин.	ч.мин.	ч.мин.
8:00	1:00	9:00	Минск	17:15
10:10	0:30	10:40	Воложин	15:35	0:30	16:05
12:10	0:30	12:40	Лида	13:35	0:30	14:05
14:30	0:30	15:00	Гродно	11:15	0:30	11:45
16:15	2:00	18:15	Прохождение пограничного перехода Литва/Беларусь	8:00	2:00	10:00
19:45	0:30	20:15	Вильнюс	6:00	0:30	6:30
21:45	0:30	22:15	Поневежес	4:00	0:30	4:30
0:15	0:30		Рига		0:30	2:00

– Схема маршрута

Практическая работа № 9

1. Тема практического занятия «Составление расписаний и схемы движения по маршруту. »

2. Количество часов  2 часа        

3. Место проведения аудитория № 309(А)

4. Характер работы: частично – поисковый

5. Форма организации учебной деятельности студентов групповая

6. Цель практического занятия: обобщение, закрепление и углубление теоретических знаний; формирование умения анализировать материал, выступать перед аудиторией и вести дискуссию по обсуждаемым проблемам.

7. Пример выполнения работы:

Нахождение кратчайшего расстояния.

Необходимо найти кратчайший путь между 2-мя заданными городами. Построим линейную модель и с помощью надстройки Поиск решения решим задачу. В статье Поиск решения MS EXCEL (6.3). Задача коммивояжера (полный граф, линейная модель) рассматривались модели, в которых коммивояжёру требуется посетить все имеющиеся города. В этой задаче посещение всех городов не требуется.

Задача Имеется 11 городов, координаты которых известны. Маршруты проложены только между некоторыми городами (неполный граф). Найти кратчайший путь между 2-мя заданными городами. Построить Линейную модель.

Создание модели Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера). Расстояния рассчитаем с помощью формулы: =КОРЕНЬ((ИНДЕКС($C$7:$D$17;ПОИСКПОЗ($A30;$A$7:$A$17;0);1)-ИНДЕКС($C$7:$D$17;ПОИСКПОЗ(B$29;$A$7:$A$17;0);1))^2 +(ИНДЕКС($C$7:$D$17;ПОИСКПОЗ($A30;$A$7:$A$17;0);2)-ИНДЕКС($C$7:$D$17;ПОИСКПОЗ(B$29;$A$7:$A$17;0);2))^2)

Теперь создадим линейную модель для решения задачи с помощью Поиска решения. Совет: Вводная статья про Поиск решения в MS EXCEL 2007 находится здесь.

Обратите внимание, что не все города соединены сообщением (столбцы J:M), например нет прямого маршрута между Москвой и Парижем. Также для модели принципиально направление маршрута: Москва - Лондон, это не тоже самое, что Лондон-Москва (при необходимости список маршрутов можно расширить).Переменные (выделено зеленым). В качестве переменных модели следует взять номера маршрутов между городами: если маршрут включен в кратчайший путь, то переменная =1, если нет, то =0. Ограничения (выделено синим). Необходимо, чтобы из каждого города, в котором побывал путешественник, был входящий и выходящий маршрут. Так как входящий маршрут обозначается 1, а исходящий -1, то их сумма, равная 0, будет означать, что в город вошли и вышли (включен в кратчайший путь). Исключение составляют город – начальные и конечные пункты путешествия. Целевая функция (выделено красным). Длина маршрута должна быть минимальной.

 

Примечание: для удобства настройки Поиска решения используются именованные диапазоны. Выберите Линейный метод поиска решения, т.к. созданная модель является линейной. Найденное Решение Поиск решения гарантировано найдет самый короткий маршрут, т.к. модель линейная.

Изменив начальный и конечный пункт путешествия, и перезапустив Поиск решения, получим другой маршрут.

Будьте внимательны, не все пары конечных и начальных пунктов допустимы. Например, задав путешествие из Москвы в Копенгаген, Поиск решения не найдет маршрут, т.к. для этого потребуется «двигаться назад», а в маршрутах между городами обратные пути не прописаны (маршруты, конечно, можно добавить в столбцы J:M, но не забудьте изменить и другие формулы).

Итоговый вариант:

 

Практическая работа №10

1. Тема практического занятия «Решение задач подсистемы АСУ. »

2. Количество часов  2 часа        

3. Место проведения аудитория № 309(А)

4. Характер работы: частично – поисковый

5. Форма организации учебной деятельности студентов групповая

6. Цель практического занятия: обобщение, закрепление и углубление теоретических знаний; формирование умения анализировать материал, выступать перед аудиторией и вести дискуссию по обсуждаемым проблемам.

7. Порядок выполнения работы:

Прочтите текст.