Для связи в whatsapp +905441085890

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

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

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

Задача:

Перевозится однородный груз из трех пунктов Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям к четырем местам назначения Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям. Из пункта Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям может быть отправлено 50 т, из Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям — 40 т, из Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям — 20 т. При этом в пункт Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям должно поступить 30 т груза, Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям — 25 т, Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям — 35 т, Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям — 20 т. Расстояния Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям от Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям-го поставщика до Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям-го потребителя приведены в углах клеток табл. 2.6;

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

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

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

Решение. Пусть Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям — количество груза, которое будет доставлено из Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям-го пункта отправления в Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям-й пункт назначения; Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям. Целевая функция задачи — минимизировать общий пробег транспорта в тонно-километрах

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

при условии, что весь груз от поставщика должен быть вывезен —

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

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

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

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

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

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

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

А. Метод северо-западного угла — удовлетворяем потребность первого потребителя за счет первого поставщика; если потребности оказались выше возможностей первого поставщика, то подключаем второго поставщика. Если запасы первого поставщика выше потребностей первого потребителя, то остаток запасов первого поставщика передаем второму потребителю и т.д. Мы должны заполнить Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям клетку. Может оказаться, что число заполненных клеток меньше Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям (случай вырождения). Тогда клетки, недостающие до Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям, заполняем нулями (эти клетки выбираем произвольно) — это так называемые условные поставки. Процесс получения опорного решения нашей задачи методом северо-западного угла представлен в табл. 2.7.

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

Примечание. Помеченные (*) значения следует читать как зачеркнутые цифры.

За четыре итерации мы заполнили в таблице перевозок пять клеток вместо шести, но удовлетворил и условиям-ограничениям. Надо ввести нулевую клетку — условную поставку. Пусть это будет клетка(1, 4):Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям. Получили опорное решение:

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

Значение целевой функции при таком решении

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

(тонно-километров);

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

  • Проверка полученного плана перевозок на оптимальность.

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

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

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

при условии (для базисных клеток)

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

Для оптимального плана исходной задачи условия-ограниче-ния двойственной задачи выполнялись бы как равенства, так как согласно условиям дополняющей нежесткости, если в оптимальном плане исходной задачи значение какой-либо переменной строго больше нуля, то соответствующее ограничение двойственной задачи при подстановке в него оптимального плана становится равенством. Получим систему (2.3) из шести уравнений с семью переменными. Поскольку независимых переменных в данной системе ровно 3 + 4 — 1 = 6, то одна переменная свободная. Пусть это будет Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям. Положим а, = 0, получим Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителямТранспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям. Составим таблицу перевозок для данной итерации (табл. 2.8). Полученное решение Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям подставляем в ограничения двойственной задачи, не вошедшие в систему уравнений (2.3), т.е. соответствующие пустым клеткам. Если эти ограничения являются верными неравенствами для найденного решения, то проверяемый допустимый план исходной задачи является опти-

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

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

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

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

  • Составление нового допустимого плана. Наметив свободную переменную, которую надо перевести в базисную, определим базисную переменную, переводимую в свободные. Переменные, соответствующие свободным клеткам (2, 1); (3, 1) и (3, 2), в которых неравенства (2.4) нарушаются, могут быть переведены в базисные. Выбираем клетку (3,2). В симплекс-методе для выбора генерального элемента требуется рассмотреть положительные отношения в столбце Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям. В матрице перевозок положительные коэффициенты в столбце Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям равны +1 и отвечают тем базисным клеткам, которые соответствуют отрицательным вершинам некоторой замкнутой ломаной линии, называемой циклом пересчета для Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям. Следовательно, генеральным элементом является базисная переменная из числа отвечающих отрицательным вершинам цикла пересчета, значение которой минимально.

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

В каждой вершине встречаются только два звена, причем одно из них расположено по строке, другое — по столбцу. Никакие три вершины, встречающиеся подряд при обходе, не лежат на одной прямой. Если циклом служит самопересекающаяся линия, то точки самопересечения не могутбытьее вершинами. Свободной клетке в цикле присваивают знак «+», другим вершинам — чередующиеся по ходу знаки «—», «+», «-» и т. д. Построим цикл пересчета для свободной клетки (3,2) (табл. 2.9). В отрицательных вершинах цикла пересчета стоят два числа: 20, 20; минимальное из них 20. Так как число положительных и отрицательных вершин одинаково, то баланс не нарушится, если в отрицательных вершинах вычесть число Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям, а в положительных вершинах прибавить это же число Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям. Вычитая минимальное из чисел, стоящих в отрицательных вершинах, мы получаем новую свободную переменную Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям, а базисной станет Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям. Прибавим 20 в положительных вершинах цикла, вычтем 20 в отрицательных вершинах и получим допустимое решение, представленное в табл. 2.10.

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

Пусть Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям = 0, получим

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

Очевидно, что для клетки (2, 1) неравенство Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям не выполняется: Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям, т.е. данное решение не является оптимальным. Шаги 3 и 4 повторяем до тех пор, пока не достигнем оптимального решения.

Цикл пересчета для клетки (2, 1) показан в табл. 2.10. Третье допустимое решение приведено в табл. 2.11.

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

Здесь же показаны значения рассчитанных для данной итерации потенциалов. Нетрудно убедиться, что для всех свободных клеток сумма потенциалов меньше Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям, т.е. получено оптимальное решение. Оно означает, что от первого поставщика к первому потребителю надо перевезти 25 т груза, ко второму 5 т, к четвертому 20т; от второго поставщика надо перевезти к первому потребителю 5 груза, к третьему 35 т; от третьего поставщика надо перевезти 20 т груза только ко второму потребителю. Минимальное значение целевой функции Транспортная задача: как оптимально организовать поставку грузов от поставщиков к потребителям =3 25 + 2-5 + I -20 + 2-5 + 1 -35 + + 2-20 = 190 (тонно-километров).

Эта теория взята со страницы лекций по предмету «математическое программирование»:

Предмет математическое программирование

Возможно эти страницы вам будут полезны:

Двойственность в задачах линейного программирования
Геометрическая интерпретация теории двойственности в задачах линейного программирования
Задача о перевозках с перегрузкой в математическом программировании
Целочисленное линейное программирование