Как найти цикл в транспортной задаче

При построении
таблицы решения транспортной задачи
используются:

1. величины,
   характеризующие объем производства в
   каждом исходном пункте и спрос в каждом
   пункте назначения;

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

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

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

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

Основные шаги
алгоритма:

1.
Найти начальное допустимое решение.

2.
Выделить из числа небазисных переменных
вводимую в базис. Если все небазисные
переменные удовлетворяют условиям
оптимальное™ – конец, иначе – 3.

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

Существует
несколько методов отыскания опорного
решения:
метод наименьшей стоимости, метод
Фогеля. Самым же часто
используемым
является: метод
северо-западного угла:

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

Рассмотрим
на примере:

Составить план
перевозок зерна из районов А1, А2, А3 и А4
в которых запасы составляю соответственно
800, 700, 1000, 500 тыс. центнеров на 3- и элеватора
В1, В2, В3. Мощностью (объемом) 1000, 1100, 900
тыс. центнеров.

Начальное решение

	В1	В2	В3	Аi
А1	3	5	6	800
А2	7	2	4	700
А3	4	3	5	1000
А4	6	4	7	500
Вj	1000	1100	900	3000

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

	В1	В2	В3	Аi
А1	800*3			800
А2	200*7	500*2		700
А3		600*3	400*5	1000
А4			500*7	500
Вj	1000	1100	900	3000

Суммы затрат на
перевозки: 800*3+200*7+500*2+600*3+400*5+500*7=12100

9. Оптимизация решения транспортной задачи. При построении таблицы решения транспортной задачи используются:

1. величины,
   характеризующие объем производства в
   каждом исходном пункте и спрос в каждом
   пункте назначения;

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

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

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

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

Основные шаги
алгоритма:

1.
Найти начальное допустимое решение.

2.
Выделить из числа небазисных переменных
вводимую в базис. Если все небазисные
переменные удовлетворяют условиям
оптимальное™ – конец, иначе – 3.

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

При оптимизации
плана
используется понятие цикла.
Циклом в
транспортной задаче называется несколько
занятых клеток, соединённых замкнутой
ломаной линией, которая в каждой клетке
совершает поворот на 90,
одна из клеток свободная (начало цикла),
остальные базисные. Каждый цикл имеет
чётное число вершин и значит, чётное
число звеньев (стрелок). Существует
несколько вариантов цикла:

Условимся отмечать
знаком “+” те вершины цикла, в которых
перевозки необходимо увеличить, а знаком
“-“ те вершины, в которых перевозки
необходимо уменьшить. Цикл с отмеченными
вершинами называется “означенным”.
Перенести какое-то количество единиц
груза по означенному циклу – это значит
увеличить перевозки, стоящие в
положительных вершинах цикла, на
некоторое количество единиц, а перевозки,
стоящие в отрицательных вершинах
уменьшить на то же количество. Очевидно,
при переносе любого числа единиц по
циклу равновесие между запасами и
заявками не меняется: по-прежнему сумма
перевозок в каждой строке равна запасам
этой строки, а сумма перевозок в каждом
столбце – заявке этого столбца. Таким
образом, при любом циклическом переносе,
оставляющем перевозки неотрицательными
план остаётся допустимым. Цена цикла
равна алгебраической сумме стоимостей,
стоящих в вершинах цикла. Обозначим
цену цикла через .
При перемещении одной единицы груза по
циклу стоимость перевозок увеличивается
на величину .
При перемещении по нему k единиц груза
стоимость перевозок изменится на k.
Очевидно, для улучшения плана имеет
смысл перемещать перевозки только по
тем циклам, цена которых отрицательна.
Каждый раз, когда нам удаётся совершить
такое перемещение, стоимость плана
уменьшается на соответствующую величину
k.
Так как перевозки не могут быть
отрицательными, мы будем пользоваться
только такими циклами, отрицательные
вершины которых лежат в базисных клетках
таблицы, где стоят положительные
перевозки. Если циклов с отрицательной
ценой в таблице больше не осталось, это
означает, что дальнейшее улучшение
плана невозможно, то есть оптимальный
план достигнут.

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

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

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

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

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

Составить план
перевозок зерна из районов А1, А2, А3 и А4
в которых запасы составляю соответственно
800, 700, 1000, 500 тыс. центнеров на 3- и элеватора
В1, В2, В3. Мощностью (объемом) 1000, 1100, 900
тыс. центнеров.

Начальное решение

	В1	В2	В3	Аi
А1	3	5	6	800
А2	7	2	4	700
А3	4	3	5	1000
А4	6	4	7	500
Вj	1000	1100	900	3000

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

После выше
описанных действий и оптимизации
получаем:

	В1	В2	В3	Аi
А1	800*3			800
А2	200*7	500*2		700
А3		600*3	400*5	1000
А4			500*7	500
Вj	1000	1100	900	3000

Таким
образом:
суммы затрат на перевозки:
800*3+200*7+500*2+600*3+400*5+500*7=12100

Fenrir писал(а):

После того, как вы нашли все потенциалы — среди всех незагруженных клеток определяете ту, в которой разница между тарифом и суммой потенциалов максимальна по модулю из отрицательных. Для этой клетки и необходимо построить цикл перерасчета. Цикл начинается с этой клетки и может проходить как угодно, подчиняясь лишь двум правилам:
1. Цикл должен быть замкнутый
2. Поворачивать можно только на загруженных клетках.
А в остальном — цикл может быть абсолютно любым. И такой вариант как вы указали тоже возможен.

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

Одна из самых распространенных и востребованных оптимизационных задач в логистике — транспортная задача. В классическом виде она предполагает нахождение оптимального (т. е. сопряженного с минимальными затратами) плана грузоперевозок.

Например, у нас есть сеть розничных магазинов, которым требуется определенное количество товаров. Также имеется ряд складов поставщиков, где требуемые товары хранятся. При этом на каждом складе различный объем запасов этих товаров. Кроме этого нам известны тарифы — затраты на перевозку 1 товара от каждого склада к каждому магазину.

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

Теоретический материал по транспортной задаче

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

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

Математическая модель транспортной задачи имеет следующий вид:

где: Z — затраты на перевозку грузов;

X — объем груза;

C — стоимость (тариф) перевозки единицы груза;

A — запас поставщика;

B — запрос потребителя;

m — число поставщиков;

n — число потребителей.

Общий план решения транспортной задачи методом потенциалов

Решить транспортную задачу можно различными методами, начиная от симплекс-метода и простого перебора, и заканчивая методом графов. Один из наиболее применяемых и подходящих для большинства случаев методов — итерационное улучшение плана перевозок.

Суть его в следующем: находим некий опорный план и проверяем его на оптимальность (Z → min). Если план оптимален — решение найдено. Если нет — улучшает план столько раз, сколько потребуется, пока не будет найден оптимальный план.

Ниже приведен алгоритм решения транспортной задачи в самом общем виде:

1. Построение транспортной таблицы.
2. Проверка задачи на закрытость.
3. Составление опорного плана.
4. Проверка опорного плана на вырожденность.
5. Вычисление потенциалов для плана перевозки.
6. Проверка опорного плана на оптимальность.
7. Перераспределение поставок.
8. Если оптимальное решение найдено, переходим к п. 9, если нет — к п. 5.
9. Вычисление общих затрат на перевозку груза.
10. Построение графа перевозок.

Подробная инструкция по решению транспортной задачи

1. Построение транспортной таблицы

Заполняем транспортную таблицу с исходными данными, где указываем запасы материалов, имеющиеся на складах поставщиков (A_i), и потребности заводов (B_j) в этих материалах.

В нижний правый угол ячеек таблицы заносим значение тарифов на перевозку груза (C_ij).

2. Проверка задачи на закрытость

Обозначим суммарный запас груза у всех поставщиков символом A, а суммарную потребность в грузе у всех потребителей — символом B.

Тогда:

Транспортная задача называется закрытой, если A = B . Если же A ≠ B , то транспортная задача называется открытой. В случае закрытой задачи от поставщиков будут вывезены все запасы груза, и все заявки потребителей будут удовлетворены. В случае открытой задачи для ее решения придется вводить фиктивных поставщиков или потребителей.

Проверим задачу на закрытость:

A = 10 + 20 + 30 = 60.

B = 15 + 20 + 25 = 60.

A = B, следовательно данная транспортная задача — закрытая.

3. Составление опорного плана

Составляет предварительный (опорный) план перевозок. Он не обязательно должен быть оптимальный. Это просто своеобразный «черновик» или «набросок», итерационно улучшая который мы постепенно придем к оптимальному плану.

Есть разные методы нахождения опорного плана. Наиболее распространены следующие:

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

4. Проверка опорного плана на вырожденность

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

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

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

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

Ломаная линия может иметь точки самопересечения, но не в клетках цикла.

В нашем примере количество базисных клеток = 5; m + n — 1 = 3 + 3 — 1 = 5.

Следовательно, первоначальный план перевозок — невырожденный (5 = 5).

5. Вычисление потенциалов для плана перевозки

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

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

Итак, сопоставим каждому поставщику A_i и каждому потребителю B_j соответствующие величины U_i и V_j так, чтобы для всех базисных клеток плана было выполнено следующее соотношение: U_i + V_j = C_ij.

Добавим к транспортной таблице дополнительную строку и столбец для U_i и V_j.

Предположим, что U₁ = 0.

Тогда мы сможем найти V₃ = C₁₃ — U₁ = 1 — 0 = 1.

Зная V₃, мы теперь можем найти U₃:

По аналогии вычисляем все оставшиеся потенциалы:

6. Проверка плана на оптимальность методом потенциалов

Для каждой свободной клетки плана вычислим разности ΔC_ij = C_ij — (U_i + V_j ), и запишем полученные значения в левых нижних углах соответствующих ячеек.

План является оптимальным, если все разности ΔC_ij ≥ 0.

В данном случае план — неоптимальный (ΔC₂₂ < 0), и его следует улучшить путем перераспределения поставок.

7. Перераспределение поставок

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

Отметим ячейку с отрицательной разностью ΔC_ij знаком «+», следующую знаком «—», и так далее, поочередно.

Затем находим минимальное значение груза в ячейках цикла имеющих знак «-» (здесь это 5) и вписываем его в свободную ячейку со знаком «+». Затем последовательно обходим все ячейки цикла, поочередно вычитая и прибавляя к ним минимальное значение (в соответствии со знаками, которыми эти ячейки помечены: где минус — вычитаем, где плюс — прибавляем).

Получим новый опорный план перевозок:

Так как базисных клеток стало больше, чем m + n — 1, то базисную клетку с нулевым значением делаем свободной:

Снова вычисляем значения потенциалов и разности ΔC_ij:

На этот раз все разности ΔC_ij ячеек положительные, следовательно, найдено оптимальное решение.

8. Если оптимальное решение найдено, переходим к п. 9, если нет — к п. 5.

В нашем примере оптимальное решение найдено, поэтому переходим к пункту 9.

9. Вычисление общих затрат на перевозку груза

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

То есть нужно перемножить значения объемов грузоперевозок на соответствующие им тарифы.

Z_min = 10 ⋅ 1 + 15 ⋅ 3 + 5 ⋅ 2 + 15 ⋅ 1 + 15 ⋅ 2 = 110 ден. ед.

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

10. Построение графа перевозок

Найдя оптимальный план перевозок, построим граф. Вершинами графа будут «склады» и «магазины». В вершинах укажем соответствующие объемы запасов и потребностей. Дугам, соединяющим вершины графа, будут соответствовать ненулевые перевозки. Каждую такую дугу подпишем, указав объем перевозимого груза.

В результате получится граф, аналогичный изображенному ниже:

Все, транспортная задача решена. Поздравляю!

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

Транспортная задача применяется во многих случаях. В частности:

• оптимизация поставок сырья и материалов на производственные предприятия;
• оптимизация доставок товаров со складов в розничные магазины;
• оптимизация пассажирских перевозок.

Это далеко не полный перечень возможностей прикладного использования транспортной задачи.

© Копирование любых материалов статьи допустимо только при указании прямой индексируемой ссылки на источник: Галяутдинов Р.Р.

Транспортная задача. Методы решения

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

1. Математическая постановка транспортной задачи.

Общая постановка транспортной задачи заключается в определении оптимального плана перевозок некоторого однородного груза из пунктов отправления A₁, A₂,…, A_m в пункты назначения B₁, B₂,…, B_n. Критерий оптимальности берется минимальная стоимость перевозки или минимальное время доставки груза.

Рассмотрим транспортную задачу, где в качестве критерия оптимальности взята минимальная стоимость перевозок всего груза. Обозначим через С_ij тарифы перевозки единицы груза из пункта отправления i в пункт назначения j. Обозначим через A_i запасы груза i-м пункте отправления, а через B_j потребности груза j-м пункте назначения, а через X_j количество единиц груза переводимого из пункта отправления i в пункт назначения j.

Тогда математическая модель транспортной задачи состоит в определении минимального значения функции

(1.1)

при условиях

(1.2)

(1.3)

(1.4)

Поскольку удовлетворяется условия (1.2)−(1.4), то обеспечивается доставка необходимого количества груза в каждый из пунктов назначения, вывоз груза из всех пунктов отправления, а также исключаются обратные перевозки.

Определение 1. Любое неотрицательное решение X_ij=∥x_ij∥ (i=1,..,m; j=1,…,n) систем (1.2) и (1.3) называется допустимым планом транспортной задачи.

Определение 2. План при котором функция (1.1) принимает минимальное значение, называется оптимальным планом транспортной задачи.

Если сумма груза у поставщиков равно общей сумме потребностей в пунктах назначения:

(1.5)

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

Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие (1.5).

В случае превышения запаса над потребностью, т.е. при

,

вводится фиктивный (n+1)-ый пункт назначения с потребностью

.

Соответствующие тарифы считаются равными нулю: c_i n+1=0 (i=1,…,m). После этих преобразований получим закрытую модель транспортной задачи.

Аналогично, при вводится фиктивный (m+1) пункт отправления с грузом а тарифы полагаются равными нулю: c_m+1j=0 (j=1,…,n). После этих преобразований получим закрытую модель транспортной задачи.

Мы будем рассматривать закрытую модель транспортной задачи. Если же модель транспортной задачи является открытой, то с помощью вышеизложенных преобразований строим закрытую модель транспортной задачи.

Обычно данные транспортной задачи записывают в виде таблицы:

Число переменных X_ij равно mn, где m число пунктов отправнения , а n число пунктов назначения. Число уравнений в (1.2) и (1.3) равно m+n. Так как мы рассматриваем закрытую модель транспортной задачи (выполняется равенство (1.5)), то число линейно независимых уравнений равно m+n−1. Следовательно опорный план транспортной задачи может иметь не более m+n−1 отличных от нуля неизвестных.

Если в опорном плане количество отличных от нуля компонентов равно в точности m+n−1, то опорный план называется невырожденным, а если меньше − то вырожденным.

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

Для определения начального опорного плана существует несколько методов. Мы рассмоьтрим три метода. Метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля.

2. Определение опорного плана. Предварительные сведения

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

В первом случае временно исключаем из рассмотрения столбец j и изменяем запас груза пункта отправления i. Во втором случае временно исключаем из рассматрения строку i и изменяем потребность груза пункта назначения j. Далее повторяем процедуру с таблицей условий с исключенной строкой или столбцом.

В m+n−1-ом шаге получаем задачу с одним пунктом отправления и одним пунктом назначения. Остается свободной одна клетка. Запасы оставшегося пункта отправления будут равны потребностям пункта назначения. Заполнив эту клетку заканчиваем m+n−1-ый шаг и получаем опорный план.

Если на некотором шаге (но не на последнем) потребности очередного пункта назначения равны запасам пункта отправления, то временно исключаем из рассмотрения либо столбец, либо строку (только одно из двух). Тогда либо запасы данного пункта отправления, либо потребности данного пункта назначения считаем равным нулю. Этот нуль при очередном шаге записываем в очередную заполняемую клетку. Данный подход обеспечивает ровно m+n−1 занятых клеток, что обеспечивает возможность проверки полученного опорного плана на оптимальность и нахождение оптимального плана.

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

3. Метод северно-западного угла

При нахождении опорного плана транспортной задачи методом северно-западного угла, заполнене клеток таблицы условий начинают с верхней левой клетки K₁₁ поэтому метод и называется «метод северно западного угла»).

Рассмотрим метод на конкретном примере.

Пример 1. На три базы A₁, A₂, A₃ поступил очередной груз в количествах равных 140, 160, 120 ед. Этот груз требуется перевезти в четыре пунктов назначения B₁, B₂, B₃, B₄ в количествах 150, 90, 100, 80. Тарифы перевозок представлена матрицей

.

Найти план перевозок даной транспортной задачи методом северно-западного угла.

Решение. Запишем все данные в таблицу условий:

Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы.

Наличие груза у поставщиков равно: ∑A_i=140+160+120=420.

Общая потребность в грузе в пунктах назначения равна: ∑B_j=150+90+100+80=420.

∑A_i=∑B_j. Модель транспортной задачи является закрытой. Следовательно она разрешима.

Найдем опорный план задачи методом северно-западного угла.

A₁≤B₁. Следовательно в клетку (A₁, B₁ ) помещаем число min(A₁, B₁)=140. Запасы пункта A₁ полностью исчерпаны. Поэтому исключаем из рассмотрения строку A₁ и будем считать потребности пункта B₁ равными 150−140=10.

A₂>B₁. Следовательно в клетку (A₂, B₁) помещаем число min(A₂, B₁)=10. Потребности пункта B₁ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₁ и будем считать запасы пункта A₂ равными 160−10=150.

Таким образом, продолжая процедуру в m+n−1-ом шаге получим:

Запишем полученный опорный план:

При этом плане стоимость перевозок вычисляется так:

F=2·140+8·10+4·90+ 1·60+3·40+6·80=1380.

4. Метод минимального элемента

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

Рассмотрим метод минимального элемента на примере.

Пример 2. Найти опорный план транспортной задачи представленной в таблице условий ниже методом минимального элемента:

Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы. Тарифы перевозок единицы груза из кажного пункта отправления во все пункты назначения задаются матрицей

Наличие груза у поставщиков равно: .

Общая потребность в грузе в пунктах назначения равна: .

Модель транспортной задачи является закрытой. Следовательно она разрешима.

Минимальный тариф равный 1 находится в клетке (A₁, B₃). Поэтому заполняем эту клетку.

A₁>B₃. Следовательно в клетку (A₁, B₃) помещаем число 70. Потребности пункта B₃ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₃ и будем считать запасы пункта A₁ равными 150−70=80.

Минимальный тариф равный 1 находится в клетке (A₂, B₄). Поэтому заполняем эту клетку.

A₂>B₄. Следовательно в клетку (A₂, B₄) помещаем число 40. Потребности пункта B₄ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₄ и будем считать запасы пункта A₂ равными 100−40=60.

Таким образом, продолжая процедуру в m+n−1-ом шаге получим:

Запишем полученный опорный план:

При этом плане стоимость перевозок вычисляется так:

5. Метод аппроксимации Фогеля

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

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

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

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

Рассмотрим метод аппроксимации Фогеля на примере 2, рассмотренной выше.

Пример 3. Найти опорный план транспортной задачи представленной в таблице условий ниже методом аппроксимации Фогеля:

Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы. Тарифы перевозок единицы груза из кажного пункта отправления во все пункты назначения задаются матрицей

Наличие груза у поставщиков равно: .

Общая потребность в грузе в пунктах назначения равна: .

Модель транспортной задачи является закрытой. Следовательно она разрешима.

Для каждой строки A_i найдем разности между двумя минимальными тарифами, записанными в данной строке и поместим их в соответствующем дополнительном столбце.

В строке 1 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. В строке 2 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В строке 3 минимальный тариф равен 3, а следующий за ним равен 3, разность между ними 3−3=0.

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

В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 3 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1.

Вычислив все разности выберем наибольшую из них. В данном случае наибольшая разница равна 2. В этом столбце минимальный тариф равен 1 и находится в пересечении строки A ₁ и столбца B₃. Следовательно заполняем эту клетку.

A₁>B₃. Следовательно в клетку помещаем число 70. Потребности пункта B₃ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₃ и будем считать запасы пункта A₁ равными 150−70=80.

Для каждой строки A_i найдем разности между двумя минимальными тарифами, записанными в данной строке и поместим их в соответствующем дополнительном столбце.

В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 3 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. В строке 1 минимальный тариф равен 2, а следующий за ним равен 2, разность между ними 2−2=0. В строке 2 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В строке 3 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1.

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

В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1.

Вычислив все разности выберем наибольшую из них. В данном случае наибольшая разница равна 2. В этой строке минимальный тариф равен 1 и находится в пересечении строки A₂ и столбца B₄. Следовательно заполняем эту клетку.

A₂>B₄. Следовательно в клетку помещаем число 40. Потребности пункта B₄ полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B₄ и будем считать запасы пункта A₂ равными 100−40=60.

Таким образом, продолжая процедуру в m+n−1-ом шаге получим:

Запишем полученный опорный план:

При этом плане стоимость перевозок вычисляется так:

F=2·40+3·40+1·70+ 4·60+1·40+3·100=850.

Для определения оптимального плана транспортной задачи разработано нескольно методов. Мы расмотрим метод потенциалов и метод дифференциальных рент.

6. Метод потенциалов

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

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

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

При применении этих методов получаем m+n−1 занятых клеток в исходном плане. Отметим, что в некоторых клетках могут стоять нули. Полученный план следует проверить на оптимальность.

Теорема. Если для некоторого опорного плана (i=1,..,m; j=1,…,n) транспортной задачи существуют такие числа α₁, α₁, …, α_m, β₁, β₂, …, β_n, что

для всех i=1,..,m; j=1,…,n, то − оптимальный план транспортной задачи.

Определение 6.1. Числа α_i и β_j (i=1,..,m; j=1,…,n) называются потенциалами пунктов отправления и пунктов назначения, соответственно.

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

Алгоритм состоит в следующем. Предположим, что одним из рассмотренных выше методов найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы α_i и β_j (i=1,..,m; j=1,…,n) из системы уравнений

где с_ij − тарифы транспортной задачи в заполненных клетках.

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

Если среди чисел α_ij нет положительных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки α_ij>0, то данный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых α_ij>0 и среди данных чисел выбирают максимальное. Клетку с данным числом следует заполнить.

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

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

Если ломаннная линия, образующая цикл, самопересекается, то место пересечения не является вершиной. Некоторые циклы представлены на рисунке Рис.6.1.

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

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

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

При сдвиге по циклу пересчета число занятых клеток не изменяется и равно m+n−1. Если в минусовых клетках имеется два и более одинаковых минимальных числа x_ij, то освобождают только одину, о остальные оставляют занятыми с нулевыми значениями.

Далее полученный опорный план проверяют на оптимальность. Для этого определяют потенциалы пунктов отправления и назначения и находят числа α_ij=β_j−α_i−c_ij для всех свободных клеток. Если среди них не окажется положительный, то получен оптимальный план. Если же среди них есть положительный, то нужно перейти к новому опорному плану. После конечнего числа шагов получяют оптимальный план.

Таким образом алгоритм нахождения оптимального плана содержит следующие этапы:

1. Нахождение опорного плана. При этом число заполненных клеток должно быть равным m+n−1.

2. Нахождение потенциалов α_i и β_j (i=1,..,m; j=1,…,n) пунктов отправления и назначения соответственно.

3. Определение числа α_ij для каждой свободной клетки. Если среди α_ij нет положительных, то получен оптимальный план транспортной задачи. Если же они имеются, то делается переход к новому опорному плану.

4. Выбор максимального среди положительных чисел α_ij . Определение свободной клетки, которую нужно заполнить. Построение цикла пересчета для выбранной свободной клетки. Сдвиг по циклу пересчета.

5. Проверка полученного опорного плана на оптимальность, т.е. переход к пункту 2.

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

Рассмотрим метод потенциалов на примере.

Пример 6.1. Решить транспортную задачу, заданную в таблице условий методом потенциалов:

Решение. Найдем сначала опорный план с помощью одного из методов описанного выше. Пусть это будет метод минимального элемента. Тогда после m+n−1 шагов получим следующую таблицу с опорным планом:

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными:

Полагая α₁=0, находим β₂=2, β₃=1, α₂=-1, α₃=-3, β₄=0, β₂=5

Для каждой свободной клетки вычисляем число α_ij=β_j−α_i−c_ij. α₁₂=2, α₁₄=-2, α₂₂=2, α₂₃=-3, α₃₃=-1, α₃₄=-3.

Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы:

Среди чисел α_ij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 2 находится в пересечении строки A₁ и столбца B₂. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак «+» а остальные клетки цикла поочередно знаки «−» и «+».

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

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными:

Полагая α₁=0, находим β₂=3, β₃=1, α₃=-3, β₁=0, α₂=-3, β₄=-2

Для каждой свободной клетки вычисляем число α_ij=β_j−α_i−c_ij. α₁₁=-2, α₁₄=-4, α₂₂=2, α₂₃=-1, α₃₃=1, α₃₄=-3.

Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы:

Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы:

Среди чисел α_ij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 2 находится в пересечении строки A₂ и столбца B₂. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак «+» а остальные клетки цикла поочередно знаки «−» и «+».

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

Опорный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 6 уравнений с 7 неизвестными:

Полагая α₁=0, находим β₂=3, β₃=1, α₂=-1, β₁=2, β₄=0, α₃=-1

Для каждой свободной клетки вычисляем число α_ij=β_j−α_i−c_ij. α₁₁=0, α₁₄=-2, α₂₃=-3, α₃₂=-2, α₃₃=-1, α₃₄=-3.

Среди чисел α_ij нет положительных. Следовательно данный опорный план является оптимальным.

Ответ. Оптимальный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

7. Метод дифференциальных рент

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

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

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

Определение 7.2. Строки, запасы которых не распределены полностью называются избыточными или положительными.

После определения недостаточных и избыточных строк, в дополнительном столбце записываем величину избытка или недостатка. Избыток записывается со знаком «+», а недостаток со знаком «-«.

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

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

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

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

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

При определении избыточности или недостаточности строк могут возникнуть трудности когда ее нераспределенный остаток равен нулю. Этот вопрос мы рассмотрим ниже на конкретном примере.

После конечного числа итераций распределенный остаток станет равным нулю. В результате получим оптимальный план данной транспортной задачи.

Пример. Найти решение транспортной задачи представленной в таблице условий методом дифференциальных рент:

Решение. Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненых клетках таблицы. Тарифы перевозок единицы груза из каждого пункта отправления во все пункты назначения задаются матрицей

Наличие груза у поставщиков равно:

Общая потребность в грузе в пунктах назначения равна:

. Модель транспортной задачи является закрытой. Следовательно она разрешима.

Найдем оптимальный план транспортной задачи методом дифференциальных рент.

Итерация 1:

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

Последовательность заполнения клеток следующее: A₁B₁, A₃B₂, A₂B₃, A₂B₄.

В результате заполнения отмеченных клеток получен условно оптимальный план.

После получения условно оптимального плана определяем избыточные и недостаточные строки. Строка A₁ является недостаточной, поскольку запасы пункта отправления A₁ распределены полностью, а потребности пункта назначения B₁ удовлетворены частично. При этом величина недостатка равна 20. Строка A₃ является недостаточной, поскольку запасы пункта отправления A₃ распределены полностью, а потребности пункта назначения B₂ удовлетворены частично. При этом величина недостатка равна 20. Строка A₂ является избыточным, поскольку запасы пункта отправления A₂ распределены не полностью. При этом величина избытка этой строки равна 40.

Нераспределенный остаток равен 40. Суммарный объем поставок равен 150.

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

В столбце 1 минимальный тариф в избыточных строках равно 4 а число стоящее в рамке равно 2. Cледовательно, разность для данного столбца равна 4−2=2. В столбце 2 минимальный тариф в избыточных строках равно 3 а число стоящее в рамке равно 2. Cледовательно, разность для данного столбца равна 3−2=1. Для столбца 3 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке. Для столбца 4 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке.

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

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

Итерация 2:

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

Последовательность заполнения клеток следующее: A₁B₁, A₂B₃, A₂B₄, A₂B₂, A₃B₂.

В результате заполнения отмеченных клеток получен условно оптимальный план.

После получения условно оптимального плана определяем избыточные и недостаточные строки. Строка A₁ является недостаточной, поскольку запасы пункта отправления A₁ распределены полностью, а потребности пункта назначения B₁ удовлетворены частично. При этом величина недостатка равна 20. Строка A₃ является избыточным, поскольку запасы пункта отправления A₃ распределены не полностью. При этом величина избытка этой строки равна 20.

Нераспределенный остаток равен 20. Суммарный объем поставок равен 170.

Избыточные и недостаточные оценки помещаем в дополнительный столбец.

Определяем положительность или отрицательность нулевой строки A2. Для этого запасы этой строки увеличиваем на 1 и снова заполняем таблицу. Если суммарный объем поставок не изменится, то строка положительная, в противном случае − отрицательная.

Последовательность заполнения клеток следующее: A₁B₁, A₂B₃, A₂B₄,A₂B₂, A₃B₂:

Суммарный объем поставок не изменился (170). Следовательно строка A₂ избыточна (положительна).

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

В столбце 1 минимальный тариф в избыточных строках равно 4 а число стоящее в рамке равно 3. Cледовательно, разность для данного столбца равна 4−3=1. Для столбца 2 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке. Для столбца 3 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке. Для столбца 4 разность не определена, так как число, записанное в рамке в данном столбце находится в положительной строке.

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

Итерация 3:

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

Последовательность заполнения клеток следующее: A₂B₃, A₂B₄, A₁B₁, A₂B₁, A₃B₁,A₂B₂, A₃B₂.

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

Посмотрев на таблицу выше мы видим, что избыточных и недостаточных строк нет. Нераспределенный остаток равен 0. Суммарный объем поставок равен 190. Все имеющие запасы распределены в соответствии фактическими потребностями пунктов назначения. Следовательно получен оптимальный план.

Ответ.

Оптимальный план имеет следующий вид:

При этом плане стоимость перевозок вычисляется так:

5.4.1. Понятие цикла пересчета

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

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

Цикл называется означенным, если его вершинам попеременно приписаны знаки “+” и “-“.

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

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

В таблице 5.4 пунктиром показан один цикл пересчета, который проходит через свободную клетку (1,1).

5.4.2. Максимально допустимый сдвиг по циклу пересчета.

Сдвигом на величину h ≥ 0 по циклу пересчета называется увеличение на число h перевозок, стоящих в положительных вершинах цикла, и уменьшение на число h перевозок, стоящих в отрицательных вершинах.

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

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

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

Рассмотрим пример (табл.5.4). Сделаем максимально допустимый сдвиг по циклу пересчета, проходящему через свободную клетку (1,3). Перевозки, стоящие в отрицательных вершинах цикла, равны 40, 30 и 40. Поэтому величина максимально допустимого сдвига h=min(40,30,40)=30. После сдвига получим новый опорный план перевозок (табл.5.5).

Таблица 5.5.

Пн По	В1	В2	В3	Запасы
А1	2 10	3	1 30	40
А2	4 60	2	5	60
А3	3	2 40	6 10	50
Потребности	70	40	40	150=150

Разумеется, в новом опорном плане число базисных клеток по-прежнему равно 5.

Если минимальная перевозка стоит в нескольких отрицательных клетках, то в результате максимально допустимого сдвига только одна из этих клеток превращается в свободную, а остальные клетки остаются базисными и в них проставляется число 0. Только при соблюдении этого условия число базисных клеток остается равным m+n-1.

Обратимся к таблице 5.5. Величина максимально допустимого сдвига по указанному пунктиром циклу пересчета равна 10. Из двух отрицательных клеток (1,1) и (3,3) только одна в результате сдвига превращается в свободную. Сделав свободной клетку (3,3), получим новый опорный план перевозок (табл.5.6).

Сравним суммарные стоимости планов перевозок, изображенных в таблицах 5.4, 5.5, 5.6.

Таблица 5.4: f = 40·2 + 30·4 + 30·2 + 10·2 + 40·6 = 520 Таблица 5.5: f = 10·2 + 30·1 + 60·4 + 40·2 + 10·6 = 430 Таблица 5.6: f = 40·1 + 60·4 + 10·3 + 40·2 = 390

Таблица 5.6

Пн По	В1	В2	В3	Запасы
А1	2	3	1 40	40
А2	4 60	2	5	60
А3	3 10	2 40	6	50
Потребности	70	40	40	150=150

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Источник

Источник

.

12.1. 150 . 90 . . 1, 2, 3 60, 70, 110 . . 1. 1, 2, 3 60, 10, 40 . . 1 . , 1, 2, 3 120, 20, 80 . . 1 . . , .

12.2. , 120, 60, 100 . . 70, 90, 50, 70 . 1 . . , .

12.3. , . 50 , 40 , 70 . 30, 50, 40 40 . . , .

12.4. 90 . . 1, 2, 3 1, 3 5 .., 2, 5 4 .. . , .

12.5. , , 60, 80, 100 . , 1 40 , 2 60 , 3 80 4 60 . 1, 2, 3, 4 .., 4, 3, 2 1 .., 1, 2, 2, 1 ..

12.6. , , .1, 2, 3, 4. 30 . . , 40 . ., 20 . . : 1 20 . ., 2 30 . ., 3 30 . ., 4 10 . . 1 . . 1, 2, 3, 4 2, 3, 2, 4 .., 3, 2, 5, 1 .., 4, 3, 2, 6 .. , 90 . . .

12.7. 35, 45, 50 . . 40,25, 35 30 . . . () , .

12.8. , . 90 , 30 , 40 . : 70 ., 30 ., 20 ., 40 . (..):

I	II	III	IV
1 2 3	18 10 16	20 20 22	14 40 10	10 30 20

, .

12.9. , , 100, 150, 250 ., . 1 50 ., 2 100 ., 3 200 ., 4 150 . . 1 . (. .) 80, 30, 50, 20; 40, 10, 60, 70; 10, 90, 40, 30. .

12.10. , 60, 80, 106 , , 44 , 70, – 50 82 . 1 10 .. :

1	2	3	4
1 2 3	18 2 12	17 7 18	6 10 2	8 41 22

.

12.11. , 200 120 . . 80, 100 120 . ( ) :

1 . 1 5 .. .

: 5. .

12.12. , 140, 300 180 . , 90, 120, 230, 180 60 . , 100 . . 1 . , , , .

12.13. . 45 , 35 , 40 ., 30 , 40 , 50 . . . .

12.14. 340, 300, 460. 350, 200, 450 100. 1 . i- (i = 1, 2, 3) k- (k = 1, 2, 3, 4) . .

12.15. , , 120, 110 130 . 1, 2, 3, 4 5. 80, 60, 70, 100 50. , 2 4, , , , .

12.16. 1, 2, 3, 4 30, 40, 50 60 , , , 20, 40, 50 70 . . , .

12.17. , 200 , 120 , 150 , 130 200 , 250 , 150 . ( ) :

1	2	3
1 2 3 4	20 50 60 30	30 20 40 30	50 40 30 60

1 1 5 .. .

12.18. . 40 . , 70 . . , , . 20 . , 30, 15, 27, 28 . . . .

12.19. 10, 8, 7 , 6, 7, 8 5 . . 1 5 .. 100 . 1 3. . .

12.20. 150, 100, 90 110 . 1, 2, 3 160, 110, 180 . 1 i- (i = 1, 2, 3, 4) k- (k = 1, 2, 3) . , .

12.21. 50, 60, 80 50 . . 90, 100 50 . . . .

12.22. , 50, 60, 45 65 , . 100, 80 40 . , . 1 . , .

12.23. , , 100, 80, 120 . , 1 90 , 2 80 , 3 70 4 60 . 4, 5, 3, 4 .., 1, 3, 5 1 .., 6, 2, 7, 1 ..

12.24. 20%, 60%, 15%. . ( /): 2800; 3000; 3500, ( . ): 10; 25; 15; 30 1 . ( .): 8, 10, 15. .

12.25. , 600 700 . 250, 300, 150, 200 400 . . 1 . . , .

12.26. 90, 60 150 . . 120, 40, 60 80 . . .

, .

12.27. , , 50, 30 10 . , . 30, 30, 10 20 . .

, .

12.28. , 180, 350 20 . , 110, 90, 120, 80 150 . , , .

, .

12.29. 110, 190 90 . , 80, 60, 170 80 . 1 .

, .

12.30. 175, 125 140 . , 180, 110, 90 40 . 1 .

, .

. .

. .

. , xij . , .

. ( ) .

– . . , . . .

1	2	3	4
1	6	6	3	5	80
2	5	4	4	3	105
3	6	5	6	4	125
4	8	4	2	4	90
110	130	160	120

.

∑ a = 80 + 105 + 125 + 90 = 400

∑ b = 110 + 130 + 160 + 120 = 520

, . , . , () , 120 (520400). .

.

1	2	3	4
1	6	6	3	5	80
2	5	4	4	3	105
3	6	5	6	4	125
4	8	4	2	4	90
5			120
110	130	160	120

.

. : – , , =(cij), -.

1. , .

1	2	3	4
1	6[10]	6	3[70]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8	4	2[90]	4	90
5	0[100]	0[20]		120
110	130	160	120

, , , , .

2. , 8, m + n – 1 = 8. , .

:

F(x) = 6*10 + 3*70 + 3*105 + 5*110 + 4*15 + 2*90 + 0*100 + 0*20 = 1375

. , , .

, , .. .

. Δij, ( ), ij=1 i j.

, .

Δij ( ).

.

Δij . ( , , , ..).

() . () , .

, , Δij. , .. , .

, , , , , .

, , Δij. , : , , , . ., , . , .

.

– Δij, , .

4. .

(1;2) +, -, +, -.

1	2	3	4
1	6[10][-]	6[+]	3[70]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8	4	2[90]	4	90
5	0[100][+]	0[20][-]		120
110	130	160	120

(1,2; 1,1; 5,1; 5,2; ).

Δ12= (6) – (6) + (0) – (0) = 0

(1;4) +, -, +, -.

1	2	3	4
1	6[10][-]	6	3[70]	5[+]	80
2	5	4	4	3[105]	105
3	6	5[110][+]	6	4[15][-]	125
4	8	4	2[90]	4	90
5	0[100][+]	0[20][-]		120
110	130	160	120

(1,4; 1,1; 5,1; 5,2; 3,2; 3,4; ).

Δ14= (5) – (6) + (0) – (0) + (5) – (4) = 0

(2;1) +, -, +, -.

1	2	3	4
1	6[10]	6	3[70]	5	80
2	5[+]	4	4	3[105][-]	105
3	6	5[110][-]	6	4[15][+]	125
4	8	4	2[90]	4	90
5	0[100][-]	0[20][+]		120
110	130	160	120

(2,1; 2,4; 3,4; 3,2; 5,2; 5,1; ).

Δ21= (5) – (3) + (4) – (5) + (0) – (0) = 1

(2;2) +, -, +, -.

1	2	3	4
1	6[10]	6	3[70]	5	80
2	5	4[+]	4	3[105][-]	105
3	6	5[110][-]	6	4[15][+]	125
4	8	4	2[90]	4	90
5	0[100]	0[20]		120
110	130	160	120

(2,2; 2,4; 3,4; 3,2; ).

Δ22= (4) – (3) + (4) – (5) = 0

(2;3) +, -, +, -.

1	2	3	4
1	6[10][+]	6	3[70][-]	5	80
2	5	4	4[+]	3[105][-]	105
3	6	5[110][-]	6	4[15][+]	125
4	8	4	2[90]	4	90
5	0[100][-]	0[20][+]		120
110	130	160	120

(2,3; 2,4; 3,4; 3,2; 5,2; 5,1; 1,1; 1,3; ).

Δ23= (4) – (3) + (4) – (5) + (0) – (0) + (6) – (3) = 3

(3;1) +, -, +, -.

1	2	3	4
1	6[10]	6	3[70]	5	80
2	5	4	4	3[105]	105
3	6[+]	5[110][-]	6	4[15]	125
4	8	4	2[90]	4	90
5	0[100][-]	0[20][+]		120
110	130	160	120

(3,1; 3,2; 5,2; 5,1; ).

Δ31= (6) – (5) + (0) – (0) = 1

(3;3) +, -, +, -.

1	2	3	4
1	6[10][+]	6	3[70][-]	5	80
2	5	4	4	3[105]	105
3	6	5[110][-]	6[+]	4[15]	125
4	8	4	2[90]	4	90
5	0[100][-]	0[20][+]		120
110	130	160	120

(3,3; 3,2; 5,2; 5,1; 1,1; 1,3; ).

Δ33= (6) – (5) + (0) – (0) + (6) – (3) = 4

(4;1) +, -, +, -.

1	2	3	4
1	6[10][-]	6	3[70][+]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8[+]	4	2[90][-]	4	90
5	0[100]	0[20]		120
110	130	160	120

(4,1; 4,3; 1,3; 1,1; ).

Δ41= (8) – (2) + (3) – (6) = 3

(4;2) +, -, +, -.

1	2	3	4
1	6[10][-]	6	3[70][+]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8	4[+]	2[90][-]	4	90
5	0[100][+]	0[20][-]		120
110	130	160	120

(4,2; 4,3; 1,3; 1,1; 5,1; 5,2; ).

Δ42= (4) – (2) + (3) – (6) + (0) – (0) = -1

(4;4) +, -, +, -.

1	2	3	4
1	6[10][-]	6	3[70][+]	5	80
2	5	4	4	3[105]	105
3	6	5[110][+]	6	4[15][-]	125
4	8	4	2[90][-]	4[+]	90
5	0[100][+]	0[20][-]		120
110	130	160	120

(4,4; 4,3; 1,3; 1,1; 5,1; 5,2; 3,2; 3,4; ).

Δ44= (4) – (2) + (3) – (6) + (0) – (0) + (5) – (4) = 0

(5;3) +, -, +, -.

1	2	3	4
1	6[10][+]	6	3[70][-]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8	4	2[90]	4	90
5	0[100][-]	0[20]	0[+]		120
110	130	160	120

(5,3; 5,1; 1,1; 1,3; ).

Δ53= (0) – (0) + (6) – (3) = 3

(5;4) +, -, +, -.

1	2	3	4
1	6[10]	6	3[70]	5	80
2	5	4	4	3[105]	105
3	6	5[110][+]	6	4[15][-]	125
4	8	4	2[90]	4	90
5	0[100]	0[20][-]	0[+]	120
110	130	160	120

(5,4; 5,2; 3,2; 3,4; ).

Δ54= (0) – (0) + (5) – (4) = 1

, (4,2;) : (-1).

.

(4;2) , , , , .

ij , , .. = min (1, 1) = 10. 10 , 10 ij, . .

1	2	3	4
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8	4[10]	2[80]	4	90
5	0[110]	0[10]		120
110	130	160	120

F(x) = 3*80 + 3*105 + 5*110 + 4*15 + 4*10 + 2*80 + 0*110 + 0*10 = 1365

4. .

(1;1) +, -, +, -.

1	2	3	4
1	6[+]	6	3[80][-]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8	4[10][-]	2[80][+]	4	90
5	0[110][-]	0[10][+]		120
110	130	160	120

(1,1; 1,3; 4,3; 4,2; 5,2; 5,1; ).

Δ11= (6) – (3) + (2) – (4) + (0) – (0) = 1

(1;2) +, -, +, -.

1	2	3	4
1	6	6[+]	3[80][-]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8	4[10][-]	2[80][+]	4	90
5	0[110]	0[10]		120
110	130	160	120

(1,2; 1,3; 4,3; 4,2; ).

Δ12= (6) – (3) + (2) – (4) = 1

(1;4) +, -, +, -.

1	2	3	4
1	6	6	3[80][-]	5[+]	80
2	5	4	4	3[105]	105
3	6	5[110][+]	6	4[15][-]	125
4	8	4[10][-]	2[80][+]	4	90
5	0[110]	0[10]		120
110	130	160	120

(1,4; 1,3; 4,3; 4,2; 3,2; 3,4; ).

Δ14= (5) – (3) + (2) – (4) + (5) – (4) = 1

(2;1) +, -, +, -.

1	2	3	4
1	6	6	3[80]	5	80
2	5[+]	4	4	3[105][-]	105
3	6	5[110][-]	6	4[15][+]	125
4	8	4[10]	2[80]	4	90
5	0[110][-]	0[10][+]		120
110	130	160	120

(2,1; 2,4; 3,4; 3,2; 5,2; 5,1; ).

Δ21= (5) – (3) + (4) – (5) + (0) – (0) = 1

(2;2) +, -, +, -.

1	2	3	4
1	6	6	3[80]	5	80
2	5	4[+]	4	3[105][-]	105
3	6	5[110][-]	6	4[15][+]	125
4	8	4[10]	2[80]	4	90
5	0[110]	0[10]		120
110	130	160	120

(2,2; 2,4; 3,4; 3,2; ).

Δ22= (4) – (3) + (4) – (5) = 0

(2;3) +, -, +, -.

1	2	3	4
1	6	6	3[80]	5	80
2	5	4	4[+]	3[105][-]	105
3	6	5[110][-]	6	4[15][+]	125
4	8	4[10][+]	2[80][-]	4	90
5	0[110]	0[10]		120
110	130	160	120

(2,3; 2,4; 3,4; 3,2; 4,2; 4,3; ).

Δ23= (4) – (3) + (4) – (5) + (4) – (2) = 2

(3;1) +, -, +, -.

1	2	3	4
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6[+]	5[110][-]	6	4[15]	125
4	8	4[10]	2[80]	4	90
5	0[110][-]	0[10][+]		120
110	130	160	120

(3,1; 3,2; 5,2; 5,1; ).

Δ31= (6) – (5) + (0) – (0) = 1

(3;3) +, -, +, -.

1	2	3	4
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110][-]	6[+]	4[15]	125
4	8	4[10][+]	2[80][-]	4	90
5	0[110]	0[10]		120
110	130	160	120

(3,3; 3,2; 4,2; 4,3; ).

Δ33= (6) – (5) + (4) – (2) = 3

(4;1) +, -, +, -.

1	2	3	4
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8[+]	4[10][-]	2[80]	4	90
5	0[110][-]	0[10][+]		120
110	130	160	120

(4,1; 4,2; 5,2; 5,1; ).

Δ41= (8) – (4) + (0) – (0) = 4

(4;4) +, -, +, -.

1	2	3	4
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110][+]	6	4[15][-]	125
4	8	4[10][-]	2[80]	4[+]	90
5	0[110]	0[10]		120
110	130	160	120

(4,4; 4,2; 3,2; 3,4; ).

Δ44= (4) – (4) + (5) – (4) = 1

(5;3) +, -, +, -.

1	2	3	4
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110]	6	4[15]	125
4	8	4[10][+]	2[80][-]	4	90
5	0[110]	0[10][-]	0[+]		120
110	130	160	120

(5,3; 5,2; 4,2; 4,3; ).

Δ53= (0) – (0) + (4) – (2) = 2

(5;4) +, -, +, -.

1	2	3	4
1	6	6	3[80]	5	80
2	5	4	4	3[105]	105
3	6	5[110][+]	6	4[15][-]	125
4	8	4[10]	2[80]	4	90
5	0[110]	0[10][-]	0[+]	120
110	130	160	120

(5,4; 5,2; 3,2; 3,4; ).

Δ54= (0) – (0) + (5) – (4) = 1

, , , Fx , .

, .

: F(x) = 3*80 + 3*105 + 5*110 + 4*15 + 4*10 + 2*80 + 0*110 + 0*10 = 1365

, , , , . .

. , [m(m+n1)] , . , 1010 81 , 20×20 361 .

. .

1	2	3	4
1	1	2	4	3	6
2	4	3	8	5	8
3	2	7	6	3	10
4	6	8	8

. .

∑ a = 6 + 8 + 10 = 24

∑ b = 4 + 6 + 8 + 8 = 26

, . , . , () , 2 (2624). .

.

1	2	3	4
1	1	2	4	3	6
2	4	3	8	5	8
3	2	7	6	3	10
4					2
4	6	8	8

.

. : – , , =(cij), -.

1. , .

1	2	3	4
1	1[4]	2[2]	4	3	6
2	4	3[4]	8[4]	5	8
3	2	7	6[2]	3[8]	10
4			0[2]		2
4	6	8	8

.

1	2	3	4
1	5	4	3	2	190
2	4	7	4	4	200
3	3	5	6	8	160
4	4	3	7	5	100
180	200	150	120

.

.

∑ a = 190 + 200 + 160 + 100 = 650

∑ b = 180 + 200 + 150 + 120 = 650

. . , .

.

1	2	3	4
1	5	4	3	2	190
2	4	7	4	4	200
3	3	5	6	8	160
4	4	3	7	5	100
180	200	150	120

.

. : – , , =(cij), -.

1. , .

1	2	3	4
1	5	4	3[70]	2[120]	190
2	4[20]	7[100]	4[80]	4	200
3	3[160]	5	6	8	160
4	4	3[100]	7	5	100
180	200	150	120

, , , , .

2. , 7, m + n – 1 = 7. , .

:

F(x) = 3*70 + 2*120 + 4*20 + 7*100 + 4*80 + 3*160 + 3*100 = 2330

4. .

(1;1) +, -, +, -.

1	2	3	4
1	5[+]	4	3[70][-]	2[120]	190
2	4[20][-]	7[100]	4[80][+]	4	200
3	3[160]	5	6	8	160
4	4	3[100]	7	5	100
180	200	150	120

(1,1; 1,3; 2,3; 2,1; ).

Δ11= (5) – (3) + (4) – (4) = 2

(1;2) +, -, +, -.

1	2	3	4
1	5	4[+]	3[70][-]	2[120]	190
2	4[20]	7[100][-]	4[80][+]	4	200
3	3[160]	5	6	8	160
4	4	3[100]	7	5	100
180	200	150	120

Источник