Практическое занятие №1. Оптимизация грузопотоков с помощью модели транспортной задачи линейного программирования с использованием метода аппроксимации Фогеля

1. Описание метода расчета

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

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

Пример 10.1. Имеются четыре поставщика груза А₁….А₄ с имеющимся у каждого поставщика количеством груза соответственно 100, 300, 75, 125 т. Имеются пять потребителей груза В₁….В₅ соответственно с потребностью 25, 150, 100, 175, 150 т каждый. Объемы наличия и потребности в грузе совпадают, следовательно, имеет место задача закрытого типа. Расстояния между всеми пунктами известны. Все данные представлены в табл.–матрице 10.5. Расстояния между пунктами в км указаны в правом верхнем углу клеток.

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

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

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

Наибольшая разность зачеркивается. Если окажется, что спрос потребителя

Таблица 10.5