Транспортная задача

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Транспортная задача

Постановка транспортной задачи состоит в следующем. Имеется m поставщиков товара, каждый из которых обладает мощностью M (i = 1, 2, …, m), и n потребителей товара с мощностями (потребностями) N (j = 1, 2, …, т). Стоимости перевозок единицы груза от каждого i-го поставщика каждому j-му потребителю c известны и называются коэффициентами затрат. Найти объемы перевозок x для каждой пары «поставщик – потребитель» так, чтобы:

1) мощности всех поставщиков были реализованы;

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

Математически требования 1) и 2) могут быть записаны:

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

Математически формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (1) и (2) найти такое решение X = (x , x , …, x , …, x ), при котором значение целевой функции (3) минимально.

Выражения (1) – (3) линейны относительно переменных, в связи с чем транспортная задача является частным случаем задачи линейного программирования. Особенности экономико-математической модели транспортной задачи состоят в следующем:

- система ограничений есть система уравнений, т.е. задача задана в канонической форме;

- коэффициенты при переменных системы ограничений равны единице или нулю;

- каждая переменная входит в систему ограничений два раза: один раз – в систему (1) и один раз - в систему (2).

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

Такие транспортные задачи называются закрытыми.

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

Решить транспортную задачу распределительным методом. Исходные данные приведены в таблице 1.

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

Нахождение первоначального базисного распределения поставок. Базисным называется распределение, удовлетворяющее требованиям (1) и (2), а также содержащее определенное количество заполненных клеток таблицы. Это количество равно рангу матрицы r = m + n –1. Последнее условие определено спецификой симплексного метода, в котором количество основных переменных строго определено. В распределительном методе основными переменными являются переменные в заполненных клетках таблицы.

Формирование первоначального базисного распределения поставок чаще всего производится методом «северо-западного угла» или методом наименьших затрат. Найдем такое распределение методом «северо-западного угла». Дадим переменной x максимально возможное значение, т.е. максимально возможную поставку в клетку (1, 1) - «северо-западный» угол таблицы поставок: x = min(40, 20) = 20. После этого спрос первого потребителя будет удовлетворен, в результате чего первый столбец таблицы поставок выпадет из последующего рассмотрения (заполненные клетки будем перечеркивать сплошной линией, а клетки, выпавшие из рассмотрения - пунктирной). Далее в таблице поставок найдем новый северо-западный угол - клетку (1, 2) в нее максимально возможную поставку. Учитывая, что первый поставщик уже отдал 20 единиц груза, поставка будет равна x = min (20, 30) = 20. После этого мощность первого поставщика будет полностью реализована и из рассмотрения выпадает первая строка таблицы поставок. Следуя этой схеме, производим заполнение остальных клеток таблицы. В результате получим:

Приведенное в таблице распределение поставок является базисным. Здесь выполняются условия баланса по строкам и столбцам таблицы, а число заполненных клеток равно r = 5 + 5 – 1 = 9. Общая стоимость перевозок, т.е. значение целевой функции может быть получено как сумма по всем клеткам таблицы произведений коэффициентов ликвидности на соответствующие объемы перевозок: F = 2× 20 +3× 20 + 3× 10 + 2× 20 +2× 20 + 2× 10 + 1× 50 + 5× 10 + 1× 40 = 370.

Полученное решение может оказаться искомым оптимальным решением задачи. В симплексном методе факт оптимальности базисного решения устанавливается по выражению целевой функции через неосновные переменные. Для приведенной таблицы это выражение будет иметь вид: F = 370 + x , где индексы k и l соответствуют незаполненным клеткам таблицы. Для определения коэффициентов

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

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

Найдем оценки свободных клеток как сумму потенциалов строки и столбца и коэффициента затрат клетки. Например, для клетки (1, 3): 0 + 1 – 2 = - 1. Аналогично для клетки (2, 5): 5 +3 – 2 = 6 и так далее. В результате получаем матрицу оценок:

В соответствии с полученной матрицей выражение целевой функции через неосновные переменные примет вид:

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

В соответствии с этим на втором шаге решения переменную x переведем в основные. Это означает, что ее значение станет

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

- ломаная должна быть связной, т.е. из любой ее вершины можно попасть в любую другую по звеньям ломаной;

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

- одна из вершин цикла лежит в свободной клетке, остальные - в заполненных;

- цикл пересчета называется означенным, если в его вершинах расставлены знаки «+» и «– «так, что в свободной клетке стоит знак «+», а соседние вершины имеют противоположные знаки.

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

Далее необходимо определить максимально возможный размер поставки в свободную клетку (5, 3). Для сохранения условий баланса в сточках и столбцах таблицы поставок при назначении поставки в свободную клетку необходимо изъять такую же поставку из соседних клеток, означенных «– «. С учетом того, что поставка не может быть отрицательной (нулем поставка может быть) получим: x = min(10, 10) = 10. При изъятии 10 единиц продукции из клеток (4, 3) и (5, 4) в этих клетках остаются нулевые поставки. Любая из этих клеток может быть свободной на следующем шаге решения.

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

Проведенное исследование дает возможность сформировать новое базисное распределение поставок, показанное в таблице 2.

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

Дадим поставку в клетку с отрицательной оценкой (1, 3). Цикл пересчета имеет вид:

Максимально возможная поставка x = min (20, 20) = 20. Свободной на следующем шаге будем считать клетку (1, 2).