Задание 6. Поместить исходные данные задачи в форму:

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

Форма исходных данных для ТЗ

Пункт отправления	Пункт назначения	Запасы
B1	B2	B3	B4	B5
A1	с11=	c12=	c13=	с14=	c15=	=
A2	=	=	=	=	=	=
A3	=	=	=	=	=	=
A4	=	=	=	=	=	=
Потребность	=	=	=	=	=

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

Исходные данные для ТЗ.

Задача:

Имеется 4 склада содержащие некоторое количество единиц однотипной продукции (см.таблицу 1), имеется также 5 потребителей нуждающихся в определенном количестве данной продукции (см.таблицу 2). При перевозке одной единицы продукции со склада i потребителю j возникают издержки P_ij. Величины издержек приведены в таблице 3. При перевозке K единиц продукции со склада i потребителю j суммарные затраты на перевозку составляют K*P_ij.

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

Таблица 3
Издержки на перевозку единицы продукции со склада i потребителю j

Шаг: 1
Проверка на сбалансированность

Задача являетя сбалансированной (закрытой).

Шаг: 2
Отыскание начального решения. Метод северо-западного угла

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

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

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

Итерация: 1
Заполним клетку a₁, b₁.
Сравним значения остатков для производителя a₁ и потребителя b₁.

Нераспределенных остатков по потребностям для b₁ меньше (см. таблицу выше, красный шрифт), запишем меньшее число в клетку a₁, b₁ одновременно вычитая его из обеих клеток остатков (см. таблицу ниже). При этом клетка остатков по потребностям обнулится указывая, что все потребности для b₁ удовлетворены (см. таблицу ниже). Поэтому исключим столбец b₁ из дальнейшего рассмотрения (серый фон).
Ненулевое значение остатка по запасам для a₁ показывает, сколько единиц продукции у него осталось не потребленной.

Итерация: 2
Заполним клетку a₁, b₂.
Сравним значения остатков для производителя a₁ и потребителя b₂.

Нераспределенных остатков по потребностям для b₂ меньше (см. таблицу выше, красный шрифт), запишем меньшее число в клетку a₁, b₂ одновременно вычитая его из обеих клеток остатков (см. таблицу ниже). При этом клетка остатков по потребностям обнулится указывая, что все потребности для b₂ удовлетворены (см. таблицу ниже). Поэтому исключим столбец b₂ из дальнейшего рассмотрения (серый фон).
Ненулевое значение остатка по запасам для a₁ показывает, сколько единиц продукции у него осталось не потребленной.

Итерация: 3

Итерация: 4

Итерация: 5

Итерация: 6

Итерация: 7

Итерация: 8

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

Шаг: 3

Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1. В нашем случае N=8, n+m=5+4=9, что удовлетворяет условию невырожденности плана.

Шаг: 4

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

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

Шаг: 5

Проведем поэтапное улучшение начального решения, используя метод потенциалов.