Моделирование транспортной задачи

,

где и - предварительные потенциалы, отвечающие исходному плану .

На каждой итерации рассматриваются и преобразуются две матрицы

и .

Матрица представляет собой опорный план задачи T, построенный в результате k-й итерации. Матрица составлена из оценок векторов относительно базиса плана , т.е.

где и - предварительные потенциалы, отвечающие плану .

Вначале будем предполагать задачу T невырожденной. Необходимые замечания относительно вырожденного случая будут сделаны ниже.

Предварительный этап. С помощью метода северо-западного угла или метода минимального элемента определяется исходный опорный план исследуемой задачи T. Далее, согласно правилам, изложенным при описании 1-го этапа метода потенциалов, вычисляем величины , , , и составляем матрицу

.

Если все элементы неотрицательны, то - решение задачи T. В противном случае переходим ко второму этапу, описание которго приводится ниже. Процесс вычисления предварительных потенциалов формализуется следующим образом. Пусть - номера тех столбцов матрицы С, которые содержат -существенные элементы в 1-й строке; - номера строк матрицы С, которые содержат -существенные элементы в столбцах с номерами . Если множества и для уже определены, то объединяет номера тех столбцов матрицы С, не принадлежащих , которые содержат -существенные элементы в строках с номерами , а состоит из номеров строк этой матрицы, не включенных в и содержащих -существенные элементы в столбцах с номерами . Образование множеств и производится до тех пор, пока процесс не прерывается получением пустого множества. Если , то под будем понимать такой элемент множества , что - -существенный элемент С. Аналогично, для определим как элемент , при котором является -существенным элементом С. Из опорности плана следует, что множества , равно как и множества , не пересекаются. Невырожденность плана приводит к тому, что объединение всех множеств есть , а объединение всех множеств составляет .

Полагаем и вычисляем

для .

Далее определяем

для .

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

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

.

Целью - й итерации является формирование матрицы и либо установление оптимальности плана , либо построение нового, более экономичного плана . Рассмотрим каждый из этапов - й итерации.

Этап 1. На этапе 1 вычисляется матрица , необходимая для проверки плана на оптимальность. Процесс преобразования матрицы в матрицу состоит в следующем. Выбираем отрицательный - существенный элемент матрицы . Пусть это (такой элемент обязательно существует и единствен, остальные - существенные элементы - нули). Выделим содержащую его строку и через обозначим совокупность - существенных элементов этой строки, не совпадающих с . Затем выделим столбцы , содержащие элемент и через обозначим множество - существенных элементов, лежащих в этих столбцах и отличных от элементов . Далее выделяются строки , содержащие элемент , и аналогично предыдущему вводится множество . Процесс выделения строк и столбцов матрицы продолжается до тех пор, пока очередное множество , скажем , не окажется пустым. Заметим, что, поскольку каждая строка (каждый столбец) не может быть выделена (выделен) более одного раза ( - опорный план!), . Закончив выделение линий (строк или столбцов) матрицы , приступим к построению матрицы . Для этого величину прибавим ко всем выделенным столбцам и вычтем из всех выделенных строк матрицы . Очевидно, что матрица, полученная после указанных преобразований, имеет вид

.

Кроме того, все ее - существенные элементы - нули. Действительно, после вычитания из - й строки элемент обращается в нуль, а все элементы становятся равными - . После прибавления к столбцам элементов эти элементы обращаются в нуль, а элементы принимают значения . Заметим, что поскольку линии отмечаются не более одного раза, элементы при дальнейших преобразованиях остаются равными нулю. Продолжая вычитать (из выделенных строк) и прибавлять (к выделенным столбцам) матрицы величину , обращаем последовательно в нуль элементы , и т.д.

После l - 1 шагов все ненулевые - существенные элементы оказываются принадлежащими . Пусть l - нечетное (четное) число. Поскольку - пустое множество, все - существенные элементы матрицы, полученной после вычитания (прибавления) величины из строк (к столбцам) элементов , равны нулю. Итак, величины , удовлетворяют системе (1.3), соответствующей плану .

Следовательно, - предварительные потенциалы, соответствующие плану , а

.

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

.

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

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

Этап 2. На этапе 2 производится улучшение плана . Основой этапа является процесс составления цепочки из положительных элементов этого плана. Выберем наименьший элемент матрицы , расположенный, скажем, на пересечении - й строки и - го столбца, и обозначим его через . По условию . Переходим к поиску цепочки из положительных элементов матрицы , замыкающейся на элементе (очевидно, =0). Соединим стрелками со всеми положительными элементами его строки, совокупность которых обозначим через . Затем каждый из элементов соединим стрелками со всеми положительными элементами, расположенными в его столбце. Совокупность всех таких элементов обозначим через . Процесс образования множеств продолжается до тех пор, пока при некотором p (p - нечетное число) среди столбцов, содержащих элементы , обнаружится столбец с номером . Заметим, что в силу опорности плана множества , не пересекаются, ибо в противном случае существовала бы замкнутая цепочка из ненулевых перевозок плана . Это обстоятельство, а также то, что любые  два пункта невырожденной задачи T могут быть соединены коммуникациями с ненулевыми перевозками, служит доказательством существования введенного выше числа . Теперь уже нетрудно образовать искомую цепочку. От элемента перейдем по столбцу к элементу . От по строке перейдем к соединенному с ним стрелкой элементу и т.д. Двигаясь таким образом вдоль намеченных стрелок по строкам и столбцам матрицы , получим в конце концов последовательность положительных элементов этой матрицы вида

                                   ,                           (4.1)

образующую цепочку, которая замыкается на элементе .

Построение цепочки (4.1) можно осуществить также с помощью метода вычеркивания строк. Для этого вводится множество Г, состоящее из положительных элементов матрицы и ее элемента .

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

Элементы матрицы , оставшиеся после процесса вычеркивания, составляют искомую цепочку. Построив цепочку (4.1), легко сформировать новый план .

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

                                                  .                                        (4.2)

Новый план определяется согласно правилу

                                                                          (4.3)

Другими словами, из нечетных элементов цепочки (4.1) вычитается , к четным элементам цепочки и к элементу величина прибавляется, остальные элементы плана сохраняют свои прежние значения.

Итак, в результате - й итерации мы перешли от плана и матрицы оценок

к улучшенному плану и к новой матрице

.

Из способа построения плана следует, что среди - существенных элементов лишь один не равен нулю.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2 Математический метод решения.

 

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

 

Таблица 3 - решение 2-ой задачи

	1	2	3	4	5	Запасы
1	1	2	3	2.5	3.5	50
2	0.4	3	1	2	3	20
3	0.7	1	1	0.8	1.5	75
4	1.2	2	2	1.5	2.5	80
Потребности	40	50	15	75	40

 

Проверим необходимое и достаточное условие разрешимости задачи.

 ∑ a = 50 + 20 + 75 + 80 = 225

 ∑ b = 40 + 50 + 15 + 75 + 40 = 220

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 5. Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу.

 

 

 

 

Таблица 4 - решение 2-ой задачи

 

	1	2	3	4	5	6	Запасы
1	1	2	3	2.5	3.5	0	50
2	0.4	3	1	2	3	0	20
3	0.7	1	1	0.8	1.5	0	75
4	1.2	2	2	1.5	2.5	0	80
Потребности	40	50	15	75	40	5

 

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

Таблица 5 - решение 2-ой задачи

 

	1	2	3	4	5	6	Запасы
1	1	2[50]	3	2.5	3.5	0	50
2	0.4[20]	3	1	2	3	0	20
3	0.7[20]	1	1	0.8[55]	1.5	0	75
4	1.2	2	2[15]	1.5[20]	2.5[40]	0[5]	80
Потребности	40	50	15	75	40	5