Пример транспортной задачи

Имеется пунктов потребления и пунктов отправления некоего однородного товара. В каждом пункте отправления содержится запас товара количества . Спрос — го потребителя на поставку этого товара равен . Цена перевозки одной единицы груза из — го пункта отправления в — й пункт потребления равна . Требуется спланировать перевозки так, дабы их суммарная цена была мельчайшей.

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

Поставщики Потребители Запасы поставщиков
……
……
…….
………………. …… …… ……
……
Спрос потребителей ……

В то время, когда суммарные запасы поставщиков равны неспециализированному спросу потребителей, т.е. , транспортную задачу именуют сбалансированной (закрытая модель).

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

Ответ несбалансированной задачи сводится к ответу сбалансированной.

Пример. На трех базах находится однообразный груз числом 42, 30 и 28 тысячь киллограм. Груз нужно развести четырем потребителям , потребности которых в данном грузе составляют 25, 23, 18 и 34 тонны соответственно. Цена перевозок задана матрицей тарифов . Выстроить начальное распределение поставок.

Ответ. Запишем исходные данные в таблицу цены перевозок

Постав-щики Потребители Запасы поставщиков
Спрос потребителей

Способ потенциалов

В базе способа потенциалов лежит теорема, которая показывает, что

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

для клеток с ненулевыми поставками — заполненных , (2)

для клеток с нулевыми поставками — свободных .

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

Поставщики Потребители


Вычислим значения введенных потенциалов, применяя первое уравнение совокупности (2) для заполненных клеток таблицы ( ):

,

,

.

Взята совокупность шести уравнений с семью малоизвестными. Совокупность решается следующим образом. Задается значение одной из малоизвестных. В большинстве случаев вычисляют . Это разрешает выяснить остальные малоизвестные

, , .

Удостоверимся в надежности посредством неравенства совокупности (2) опорный замысел на оптимальность.

В случае если обозначить , то замысел оптимальный, в случае если все неотрицательны.

Неравенства записываются для свободных клеток таблицы :

,

,

,

,

,

.

Так как , одно из неравенств совокупности (2) не выполнено, следовательно, опорный замысел не есть оптимальным. Требуется его улучшение, другими словами перераспределение поставок.

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

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

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

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

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

Этот цикл изображен на вышеприведенной таблице.

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

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

В клетке величина поставки станет 13 (0+13),

в клетке величина поставки станет 4 (17-13),

в клетке величина поставки станет 30 (17+13),

в клетке величина поставки 0 (13-13), и она делается свободной.

Внесем полученные результаты в таблицу:

Поставщики Потребители

Количество заполненных клеток осталось 6 – замысел опорный.

Подсчитаем суммарные затраты на перевозки для взятого замысла

.

Они уменьшилась с 509 до 496.

Контролируем, есть ли замысел оптимальным по аналогичной схеме. Введем потенциалы

Поставщики Потребители


Выполним первое условие из совокупности (2)

,

,

.

По аналогии ответ совокупности

, , , , .

Из второго условия (2)

,

,

,

,

,

.

Все значения неотрицательны, полученный опорный замысел – оптимальный.

Примечание. В случае если кое-какие из — отрицательные, процедуру оптимизации направляться повторить.

Ответ. Матрица оптимальных количеств перевозок

,

Минимальные суммарные затраты на перевозку .

Федеральное национальное бюджетное образовательное учреждение

высшего образования

«Казанский национальный исследовательский технологический университет»

(ФГБОУ ВО КНИТУ)

Верховная школа экономики

Кафедра Экономики, управления и организации производством

ФОНД ОЦЕНОЧНЫХ СРЕДСТВ

с целью проведения промежуточной аттестации

по производственной практике

Экономика

(наименование и код направления подготовки/ профессии)

Транспортная задача 1часть (transportation problem p1)


Также читать:

Понравилась статья? Поделиться с друзьями: