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

Имеется три поставщика некоего товара А1, А2, А3, у которых соответственно имеются 160, 310 и 250 условных единиц (у. е.) товара. В данном товаре нуждаются города B1, B2, B3, B4 в количествах, равных, соответственно, 100, 170, 200 и 250 у. е. Цена перевозки единицы продукции от поставщиков к потребителям задается следующей таблицей:

Поставщики Мощность Поставщиков их спрос и Потребители
B1 B2 B3 B4
А1
А2
А3

Составим экономико-математическую модель данной задачи.

Обозначим через — количество перевозки от поставщика Аi к потребителю Bj.

Тогда суммарные затраты на перевозку F составят:

спрос потребителей и Заданные мощности поставщиков накладывают ограничения на значения количеств перевозок :

мощности всех поставщиков должны быть реализованы:

Спросы потребителей должны быть удовлетворены:

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

Узнаем темперамент транспортной задачи, т. е. есть ли она открытой либо закрытой.

Потому, что

т. е. суммарная мощность равна суммарному спросу, то эта задача есть закрытой.

Находим начальное базовое распределение поставок способом мельчайших затрат.

Находим в таблице клетку с мельчайшим коэффициентом затрат. Таких клеток у нас две, в частности: (1,1) и (2,4). В этих клетках коэффициент затрат равен 5. Находим максимальные поставки в эти клетки:

Тут мы учитываем, что первый поставщик имеет груз числом 160, но первому потребителю нужно лишь 100.

.

Громаднейшая максимальная поставка будет в клетку (2,4). Исходя из этого реализуем эту поставку в клетку (2,4), т. е. даем данной клетке груз числом 250 у.е. Тогда, спрос четвертого потребителя всецело будет удовлетворен. Клетку (2,4) вычисляем заполненной, и перечеркиваем ее жирной целой линией. Наряду с этим выпадают из предстоящего рассмотрения остальные клетки четвертого столбца (спрос четвертого потребителя всецело удовлетворен), их перечеркиваем узкими линиями.

Поставщики Мощность Поставщиков их спрос и Потребители
B1 B2 B3 B4
А1
А2
А3

В оставшихся не перечеркнутых никакой линией клетках находим клетку с мельчайшим коэффициентом затрат. Это клетка (1,1). Максимально вероятную поставку в эту клетку мы уже нашли: . Реализуем эту поставку, наряду с этим спрос первого потребителя будет всецело удовлетворен и, следовательно, из предстоящего рассмотрения выпадет таблица и первый столбец будет иметь вид:

Поставщики Мощность Поставщиков их спрос и Потребители
B1 B2 B3 B4
А1
А2
А3

В оставшихся не перечеркнутых никакой линией клетках находим клетку с мельчайшим коэффициентом затрат. Это клетка (1,2), коэффициент затрат в которой равен 8. Максимальная поставка в эту клетку будет:

.

Тут мы учли, что от первого поставщика мы забрали 100 у. е. груза для первого потребителя. Реализуем поставку, наряду с этим мощность первого поставщика будет всецело реализована, и, следовательно, из предстоящего рассмотрения выпадет таблица и первая строка будет иметь вид:

Поставщики Мощность Поставщиков их спрос и Потребители
B1 B2 B3 B4
А1
А2
А3

В оставшихся не перечеркнутых никакой линией клетках находим клетку с мельчайшим коэффициентом затрат. Это клетка (2,3), коэффициент затрат в которой равен 9. Максимальная поставка в эту клетку будет:

.

Реализуем эту поставку, наряду с этим мощность второго поставщика будет всецело реализована, и, следовательно, из предстоящего рассмотрения выпадет вторая строка, и таблица будет иметь вид:

Поставщики Мощность Поставщиков их спрос и Потребители
B1 B2 B3 B4
А1
А2
А3

В оставшихся не перечеркнутых никакой линией клетках находим клетку с мельчайшим коэффициентом затрат. Это клетка (3,3), коэффициент затрат в которой равен 10. Максимальная поставка в эту клетку будет:

.

Реализуем эту поставку, наряду с этим спрос третьего потребителя всецело будет удовлетворен, и таблица будет иметь вид:

Поставщики Мощность Поставщиков их спрос и Потребители
B1 B2 B3 B4
А1
А2
А3

Из не перечеркнутых никакой линией клетках осталась одна клетка. Это клетка (3,2), коэффициент затрат в которой равен 17. Максимальная поставка в эту клетку будет:

.

Реализуем эту поставку, наряду с этим возьмём начальное базовое распределение поставок:

Поставщики Мощность Поставщиков их спрос и Потребители
B1 B2 B3 B4
А1
А2
А3

Проверка (необходима!).

По окончании нахождения начального распределения поставок нужно выполнить две проверки.

1 проверка. Нужно проверить суммы по строчкам, каковые должны совпадать с мощностями суммы и поставщиков по столбцам, каковые должны совпадать со спросами потребителей. Для отечественного примера:

суммы по строчкам:

100+60=160

60+250=310

110+140=250

суммы по столбцам:

100=100

60+110=170

60+140=200

250=250.

Видим, что совпадают.

2 проверка. Количество заполненных клеток должно быть равняется m+n-1.

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

Контролируем количество заполненных клеток (перечеркнутых жирной линией). Их 6, а m+n-1=4+3-1=6. В отечественном примере не требуется вводить фиктивные нулевые поставки.

Отыщем суммарные затраты на перевозку груза при начальном распределении поставок:

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

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

1 ход. Нахождение столбцов и потенциалов строк.

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

Число занятых клеток равняется (m+n-1) и, следовательно, для определения потенциалов, нужно решать совокупность из (m+n-1) уравнений с (m+n) малоизвестными. Совокупность есть неизвестной, т. е. имеет нескончаемое множество ответов, исходя из этого для облегчения нахождения частного ответа полагают . Потом двигаются по заполненным клеткам и находят остальные потенциалы.

2 ход. Нахождение матрицы оценок.

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

В случае если все элементы матрицы оценок неотрицательны, т. е.

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

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

3 ход. Построение цикла пересчета.

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

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

В цикле всего одна свободная клетка, остальные заполненные. В цикле неизменно четное число клеток. В вершинах цикла условно ставим символы: в свободную клетку цикла ставим «+». После этого символы чередуются.

В клетках со знаком «–» находим мельчайшую поставку, которую передаем по циклу. В клетки с «+» эту поставку прибавляем, с «–», соответственно, вычитаем. В случае если наряду с этим сходу в нескольких клетках получается 0, то лишь в одной клетке ничего не пишем, т.е. вычисляем ее свободной, а в клетки и остальные записываем формально нулевую поставку.

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

Пример. Отыщем оптимальное распределение поставок для отечественного примера. Сначала перепишем таблицу с начальным распределением поставок в виде:

1 итерация.

1 ход. Нахождение столбцов и потенциалов строк.

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

Наряду с этим полагают . Потом двигаются по заполненным клеткам и находят остальные потенциалы.

Двигаемся по первой строке распределительной таблицы. Заполненных клеток тут две: (1,1) и (1,2). Сначала идем до клетки (1,1). Данной клетке соответствует потенциал первой строки (т. к. клетка находится в первой строке) и потенциал первого столбца (клетка находится в первом столбце). Должно выполняться равенство:

Мы настойчиво попросили, дабы . Значение . Следовательно, значение . Записываем его в последней сроке распределительной таблицы.

В первой строке распределительной таблицы имеется, как было указано выше, еще одна заполненная клетка. Это клетка (1,2). Данной клетке соответствует потенциал первой строки (т. к. клетка находится в первой строке) и потенциал второго столбца (клетка находится во втором столбце). Должно выполняться равенство:

Мы настойчиво попросили, дабы . Значение . Следовательно, значение . Записываем его в последней сроке распределительной таблицы.

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

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

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

Мы нашли, что . Значение . Следовательно, значение . Записываем его в последнем столбце распределительной таблицы.

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

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

Мы нашли, что . Значение . Следовательно, значение . Записываем его в последней строчке распределительной таблицы.

Потом наблюдаем на третий столбец. В нем имеется заполненная клетка (2,3). Совершая действия, подобные выше рассмотренным, находим, что потенциал второй строки равен 8, а потенциал четвертого столбца равен –3. В следствии взяли следующую таблицу:

2 ход. Нахождение матрицы оценок.

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

Приобретаем матрицу оценок:

3 ход. Построение цикла пересчета.

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

В цикле всего одна свободная клетка, остальные заполненные.

Мы двигаемся из клетки (2,1). Потом идем лишь по заполненным клеткам так, дабы возвратиться назад, и наряду с этим учитываем все перечисленные выше правила. Исходя из этого приобретаем следующий путь:

В вершинах цикла условно ставим символы: в свободную клетку цикла ставим «+». После этого символы чередуются.

Из клеток со знаком «–» находим мельчайшую поставку. У нас три клетки со знаком «–». Это клетки (1,1), (2,3) и (3,2). Мельчайшая поставка находится в клетке (2,3) и она равна 60. Эту поставку передаем по циклу. В клетки с «+» ее прибавляем, с «–», соответственно, вычитаем. К примеру, клетка (3,3) со знаком «+», ветхая поставка в ней равнялась 140, прибавляем к ней 60, приобретаем 200. Клетка (3,2) была со знаком «–» и ветхая поставка в ней равнялась 110. Отнимаем 60 и приобретаем, что новая поставка в данной клетке равна 50. Свободная клетка (2,1) делается заполненной клеткой с поставкой 60, а ранее заполненная клетка (2,3) делается заполненной. Совсем приобретаем новую распределительную таблицу:

2 итерация.

1 ход. Нахождение столбцов и потенциалов строк.

Находим потенциалы столбцов и строк.

2 ход. Нахождение матрицы оценок.

Приобретаем матрицу оценок:

3 ход. Построение цикла пересчета.

Среди отрицательных элементов матрицы оценок выбираем мельчайшее. В нашем случае это –5, которое находится в клетке (3,4). Эта свободная клетка будет вершиной цикла пересчета. Строим цикл пересчета.

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

В вершинах цикла условно ставим символы: в свободную клетку цикла ставим «+». После этого символы чередуются.

Из клеток со знаком «–» находим мельчайшую поставку. У нас три клетки со знаком «–». Это клетки (1,1), (2,4) и (3,2). Мельчайшая поставка находится в клетке (1,1) и она равна 40. Эту поставку передаем по циклу. В клетки с «+» ее прибавляем, с «–», соответственно, вычитаем.

Совсем приобретаем новую распределительную таблицу:

3 итерация.

1 ход. Нахождение столбцов и потенциалов строк.

Находим потенциалы столбцов и строк.

2 ход. Нахождение матрицы оценок.

Приобретаем матрицу оценок:

3 ход. Построение цикла пересчета.

Среди отрицательных элементов матрицы оценок выбираем мельчайшее. В нашем случае это –3, которое находится в клетке (2,2). Эта свободная клетка будет вершиной цикла пересчета. Строим цикл пересчета.

В вершинах цикла условно ставим символы: в свободную клетку цикла ставим «+». После этого символы чередуются.

Из клеток со знаком «–» находим мельчайшую поставку. У нас две клетки со знаком «–». Это клетки (2,4) и (3,2). Мельчайшая поставка находится в клетке (3,2) и она равна 10. Эту поставку передаем по циклу. В клетки с «+» ее прибавляем, с «–», соответственно, вычитаем.

Совсем приобретаем новую распределительную таблицу:

4 итерация.

1 ход. Нахождение столбцов и потенциалов строк.

Находим потенциалы столбцов и строк.

2 ход. Нахождение матрицы оценок.

Приобретаем матрицу оценок:

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

Отметим, что при начальном распределении поставок, отысканном способом мельчайших затрат, суммарные затраты составили 6040 у. е.

Ответ. Оптимальный замысел распределения:

Минимальные суммарные затраты составляют 5450 у.е.

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


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

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