Транспортная задача на min времени

 

Цель работы: Изучение теоретических и практических приёмов решения транспортных задач с нелинейной целевой функцией.

Заменяя в транспортной задаче стоимость доставки на время доставки t_{i j} и введя критерий min времени: min T=max{ t _{i j}}, получим новую модель транспортной задачи с нелинейной целевой функцией.

Задачу можно свести к обычной транспортной, применив метод запрещенных клеток.

Метод запрещённых клеток.

 

Состоит из следующих шагов:

1. Находим опорное решение.

2. Из базисных клеток находим T = max t_{i j}, и все клетки с большим временем – запрещаем для использования,

3. Улучшение плана распределительным методом. Достигается циклическим переносом из клеток x_ij с t_{i j}= T в свободные клетки с меньшим временем. Допускается вхождение в цикл нескольких свободных клеток, помеченных знаком «+».

4. Переход ко второму пункту до тех пор, пока будет возможно построить цикл.

Покажем решение задачи на минимум времени на примере.

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

 

Таблица 2.1. Опорное решение задачи на min T

Пункты						Запасы ai
Запросы bj

 

T=max{ t _{i j}}= t₁₁ =10 и все клетки с большим временем запрещаем для использования, у нас это клетка x₄₁ с t₄₁=11.

Цикл, включающий клетку x₁₁, следующий: x₂₁® x₂₂® x₁₂® x₁₁® x₂₁, после переноса по циклу получим новую таблицу 2.2 и время T=max{ t _{i j}}= t₄₅ =9 и к запрещенным добавляется клетка x₁₁.

Перенос по циклу x₃₅® x₄₅® x₄₄® x₃₄® x₄₅, а затем x₄₃® x₄₅® x₃₅® x₃₃® x₄₃ даёт следующую таблицу 9 с T=max{ t _{i j}}= t₄₄ =8 и клетки x₄₅ и x₂₅ включаются в число запрещенных.

 

Таблица 2.2. Промежуточное решение с T=9

Пункты						Запасы ai
Запросы bj

 

Таблица 2.3. Промежуточное решение с T=8

Пункты						Запасы ai
Запросы bj

 

Перенос по циклу x₁₄® x₁₂® x₄₂® x₄₄® x₁₄, а затем x₁₃® x₁₂® x₄₂® x₄₃® x₁₃, затем x₃₂® x₁₂® x₃₅® x₃₃® x₃₂, затем x₃₁® x₃₂® x₂₂® x₂₁® x₃₁ даёт следующую таблицу 10 с T=max{ t _{i j}}= t₃₃ =7 и клетки x₁₂, x₃₂, x₃₄, x₄₄, включается в число запрещенных.

Попытка построить улучшающий цикл к успеху не приводит. Решение закончено.

Таблица 2.4. Оптимальное решение, T=7

Пункты						Запасы ai
Запросы bj

 

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

 

ЗАДАЧА О НАЗНАЧЕНИЯХ

 

Цель работы: Изучение теоретических и практических приёмов решения транспортных задач с булевскими переменными.

Если в обычной транспортной задаче положить запасы и потребности единичными (булевскими переменными), то получим специальный класс задач о назначениях.

Задачу можно рассматривать как частный случай транспортной. Предложение и спрос в каждом пункте равно 1, т. е. a_i=1, для всех i, b_j=1 для всех j. Стоимость «перевозки» (прикрепления работы i к станку j) равна c_ij. Ниже в таблице 3.1 иллюстрируется общая структура задачи о назначениях.

Прежде чем решать задачу методами, ассоциированными с транспортной моделью, необходимо «ликвидировать» дисбаланс, так что .

Задачу о назначениях можно представить следующим образом. Пусть

x_ij =0, если j -я работа не выполняется i -м станком,

x_ij =1, если j -я работа выполняется i -м станком.

Теперь задача будет формулироваться так:

найти min при ограничениях

Таблица 3.1. Задача о назначениях

	Станки	ai
		…	n
Виды работ		C11	C12	…	C1n
	C21	C22	…	C2n
m	Cm1	Cm2	…	Cmn
bJ				…

 

 

Для иллюстрации задачи о назначениях рассмотрим пример с тремя работами и тремя станками (табл. 3.2). Исходное решение (полученное по правилу северо-западного угла) будет, очевидно, вырожденным.

Таблица 3.2. Опорное решение

Cтанки
Виды работ

 

Эта особенность характерна для задачи о назначениях независимо от метода, используемого при получении начального базиса.

Специфическая структура задачи о назначениях позволяет разработать эффективный метод ее решения. Покажем, как реализуется этот метод на примере приведенной выше задачи.

 

Решение через нуль-базис

 

Оптимальное решение задачи о назначениях не изменится, если к любой строке или столбцу матрицы стоимостей прибавить (или вычесть) постоянную величину. Этот факт можно доказать следующим образом. Если и вычитаются из i -й строки и j -го столбца, то новые стоимости имеют вид . Отсюда получается новая целевая функция:

Поскольку , то . Отсюда следует, что минимизация исходной целевой функции z приводит к такому же решению, как минимизация z '.

Приведенное соображение показывает, что если можно построить новую -матрицу с нулевыми элементами и эти нулевые элементы или их подмножество соответствуют допустимому решению, то такое решение будет оптимальным, поскольку стоимость не может быть отрицательной.

Если сначала рассмотреть строки табл. 3.2, то получим -матрицу, представленную в табл.3.3. Вычитая из третьего столбца, последнюю матрицу можно преобразовать так, чтобы она имела больше нулей (табл. 3.4).

Заштрихованными квадратами в табл. 3.4 помечены элементы, соответствующие допустимому (и, следовательно, оптимальному) назначению (1, 1), (2, 3) и (3, 2) со стоимостью 5+12+13=30. Заметим, что эта стоимость равна p₁+p₂+p₃+q₃.

				pi

Таблица 3.3. Матрица стоимостей Таблица 3.4. Решение

 

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

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

Просматривая строки и столбцы, вычитаем минимальный элемент. Если в полученной матрице удаётся выделить нуль-базис, то решение закончено.

Чтобы выделить нуль-базис нужно применить процедуру min-покрытия нулей. Для этого вычеркиваем нули матрицы min-количеством прямых, если количество прямых равно размерности матрицы стоимостей, то они и задают базис, если это не выполнено, то выбирается наименьший не вычеркнутый элемент. Этот элемент вычитается из всех не вычеркнутых и прибавляется к элементам на пересечении прямых, и процедура покрытия повторяется.

После получения базиса:

Z=åp_i + åq_j + å W_k,

где p_i - минимальные элементы по строкам,

q_j - минимальные элементы по столбцам,

W_k- наименьшие не вычеркнутые элементы.

Чтобы получить требуемое распределение работ можно применить следующую процедуру.

В матрице определить минимальное количество нулей в строке и в столбце. Выбранный элемент распределяем, вычеркивая строку и столбец. К оставшейся матрице вновь применить указанную процедуру. Данная процедура одновременно отвечает на вопрос о размерности матрицы стоимостей. Если все работы распределены, то решение получено и оптимально.

Эти правила иллюстрируются на примере, приведенном в таблице 3.5. Выполняя те же начальные шаги, что и раньше, получим таблицу 3.6.

В этом случае невозможно найти допустимое решение, состоящее из нулей.

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

На следующем шаге выбирается наименьший не вычеркнутый элемент (C₃₂=1). Этот элемент вычитается из каждого не вычеркнутого элемента и прибавляется к каждому элементу, стоящему на пересечении проведенных прямых.

Таблица. 3.5. Исходная задача Таблица 3.6. Матрица с нулями

 

В результате получается табл. 3.8, которая соответствует оптимальному назначению (1, 1), (2, 3), (3, 2) и (4, 4). Суммарные затраты равны 1+10+5+5=21.

Табл. 3.7. Покрытие нулей Табл. 3.8. Оптимальное решение

 

Заметим, что если на последнем шаге оптимальное решение не достигнуто, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено допустимое решение.

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