![](https://habrastorage.org/getpro/habr/upload_files/dc5/c88/3f0/dc5c883f0d6e83a2e0c03f2e9ef6cca9.jpg)
Прочие статьи цикла
Транспортная задача линейного программирования
Транспортная задача линейного программирования относится к перечню классических задач, решаемых в практике деятельности людей. Эта задача методами классической математики не решается. В задаче необходимо отыскивать экстремум целевой функции. В задаче целевая функция – линейная. Ограничения на переменные (их может быть очень много) описываются также линейными зависимостями. Казалось бы чего проще. Но как раз ограничения и порождают трудности, связанные не просто с поиском max и min при отсутствии ограничений, а с необходимостью учета таких ограничений. Искать требуется не просто экстремум, а условный экстремум. Методы решения задачи позволяют учитывать особенности структуры задачи и даже отказаться от симплексного метода решения в чистом виде.
I. Основные параметры, термины и обозначения
Для ощущения масштаба задачи приведу парочку изображений того, что рассматривается в транспортной задаче линейного программирования.
Зеленый цвет - пассажирские суда, желтые - грузовые, розовый - частные яхты, оранжевый - танкеры и др. Аналогичная картина наблюдается и для авиационных перевозок, перевозок по железной дороге или автотранспортом. Изображения получены в начальном периоде Пандемии короновируса, что привело к огромным пробкам в узостях мирового Океана (Панамский, Суэцкий и др. каналы). Танкеры отправили отстаиваться на рейде, экипажам судов на берег сойти не разрешалось. Это форс-мажорные обстоятельства, которые в теории должны рассматриваться и учитываться специальным образом, что пока к сожалению перевозчиков не сделано.
В теории в тексте задачи Хичкока ничего не говорится о равенстве имеющегося общего запаса судов в портах отправления и общей потребности в судах в портах прибытия (назначения). Если такого равенства нет, то система ограничений несовместна. В случае равенства
транспортная задача называется «сбалансированной». Задачи, в которых условие баланса не задано, должны быть приведены к «сбалансированному» виду. Это можно выполнить использованием «фиктивных» перевозок. Рассматриваем два случая:
Поэтому ранг системы равен не n+m, а n+m – 1, т.е с mn неизвестными. Общее число опорных планов равно числу сочетаний из mn по n+m – 1.. Применение симплекс метода для решения задачи возможно, но требует большого объема вычислений уже при n и m ≈ 10 -15. Заметим также, что каждая неизвестная входит лишь в два уравнения системы (матрица коэффициентов системы ограничений имеет в каждой строке и каждом столбце только два ненулевых элемента). Более того, транспортная задача всегда имеет допустимое решение. Все сказанное вызвало потребность попытаться учесть специфику задачи и создать метод ее решения более простой, чем симплекс метод. Такие методы были найдены и получили названия метода потенциалов и распределительного метода. Это разновидности симплексного метода. Они удобно реализуются, если условие задачи представлено в виде таблиц.
ТАБЛИЦА 1 - Вид данных транспортной задачи линейного программирования
Метод содержит три последовательных этапа:
Формирование опорного плана;
Проверка опорного плана на оптимальность;
Переход к новому опорному плану, если предыдущий не оптимален.
II. Формирование опорного плана перевозок
Рассмотрим способ получения начального опорного плана транспортной задачи, названный способом северо-западного (С-З) угла. Способ заключается в заполнении ячеек таблицы m×n значениями переменной xij, таким образом, чтобы удовлетворялись условия задачи. При этом план решения Х[m, n] может быть и не оптимальным, но обязательно должен быть допустимым.
В этом способе формируют опорный план, двигаясь по таблице: сверху вниз по строкам и слева направо вдоль строки. Начинают с левого верхнего угла (ячейки), куда вписывают значение x11 =min{a1, b1}.Первые строка и столбец из рассмотрения далее исключаются.
Затем, если a1 > b1, то определяется остаток (a1 – b1) продукта на первом пункте отправления и его запас реализуется на 2-м пункте назначения. Остаток потребностей 2-го пункта назначения удовлетворяется за счет 2-го пункта отправления, остатки которого направляются в 3-й пункт назначения и т.д. Ниже метод будет иллюстрирован числовым примером.
Пример 1. Построение опорного плана методом Северо-Западного угла
Заданы значения: m = 3, n = 4; a1 = 60, a2 = 80, a3 =100, b1 = 40,b2 = 60, b3 = 80, b4 = 60. Слева в таблице приведены dij удельные стоимости перевозок; справа - Вij стоимости совместно с предложениями ai и потребностями bj .
Требуется найти план Х [m,n] перевозок, удовлетворяющий условиям на целевую функцию Q и переменные хij задачи Q.
РЕШЕНИЕ Построить исходный опорный план способом северо-западного угла. Строим симплексную таблицу: Таблица 3. Опорный план задачи
В таблице способом северо-западного угла получен опорный план. Базисные переменные (их число = 6): x11 = 40, x12= 20, x22= 40, x23= 40, x33= 40, x34= 60. Свободные переменные: x13= x14= x21= x24= x31= x32= 0 (их число равно 6).
Ячейки таблицы, соответствующие базисным переменным, называют базисными, остальные – свободными. Далее в алгоритме будем следовать идее симплекс метода. Суммарная стоимость перевозок Q, соответствующая плану Х[m,n], получает представление
Q = d11∙x11 + d12∙x12 + d22∙x22 + d23 ∙x23+ d33 ∙x33+ d34 ∙x34 = = 5∙40 + 2∙20 + 10∙40 + 2∙40 + 8∙40 + 5∙60 = 200+40+400 + 80 + 320+ 300 = 1340 ед
Коэффициенты dij называются фиктивными или косвенными стоимостями; их выражают через косвенные величины α и β, d'ij = αi +βj . Здесь параметры αi и ( - βj ), по аналогии с механикой называют потенциалами i-го пункта отправления и j-го пункта прибытия. Значения потенциалов определяется из системы линейных уравнений: αi + βj = dij
Каждому из таких уравнений соответствует какая-либо базисная переменная хij Система уравнений с потенциалами содержит m+n неизвестных потенциалов, число же уравнений равняется числу базисных ячеек таблицы, т.е. (m + n – 1). Следовательно, один из потенциалов можно задать произвольно, положив его равным, например, нулю.
Решая далее систему уравнений для потенциалов, находим значения потенциалов строк и столбцов, все фиктивные стоимости dij и коэффициенты γij. Если для всех свободных клеток γrs ≤ 0, то перевод в базис любой свободной переменной не уменьшит значения целевой функции и, следовательно, выбранный опорный план не является оптимальным. Если же некоторые γrs >0, то данный план можно улучшить путем перевода в базис свободной переменной, соответствующей max γrs, а также путем исключения из базиса, принадлежащей ему переменной, первой обращающейся в нуль. Переход к новому опорному плану и поиск оптимального плана рассмотрим на примере. Другой способ формирования опорного плана предложен Фогелем. Этот способ при первом чтении можно пропустить, так как дальше он в тексте не используется.
Пример 2. Способ аппроксимации Фогеля
В большинстве случаев этот способ дает опорный план наиболее близкий к оптимальному. Удобен для матриц большой размерности. Используется концепция штрафов, взимаемых за выбор не самого оптимального с точки зрения транспортных издержек маршрута. Штраф по каждой строке и каждому столбцу определяется из анализа маршрутов с различными показателями издержек (как разность двух различных уровней транспортных издержек). Первой заполняется клетка матрицы (таблицы), в которой фиксируется самый крупный штраф. После заполнения клетки штрафы пересчитываются и так до тех пор, пока все ресурсы не будут распределены. Исходные данные для этого примера заполняют таблицу слева вверху.
Этапы алгоритма: 1. Вычисление разностей в каждой строке и в каждом столбце между наименьшей стоимостью и ближайшей к ней по величине. Разности по строкам записываются справа в столбце разностей, разности по столбцам – внизу в строке разностей. Например, для строк А1 разность равна А1В2 – А1В3 = 38 – 24 = 14 и т. д.
ТАБЛИЦА 2 - Метод Фогеля для получения опорного плана транспортной задачи
2. Поиск из всех разностей, как по строкам, так и по столбцам максимальный. В нашем примере максимальная разность равна 38 и находится в строке А2. Обведем максимальную разность рамкой.
3. Размещение в клетку, где находится наименьшая стоимость (А2В2 = 18) (строка с наибольшей разностью), максимально возможного количества ресурсов. Оно равно 20, т.е. всему ресурсу отправителя А2. Поскольку все ресурсы отправителя А2 исчерпаны, строку А2 исключаем из дальнейших расчетов, для чего отметим все клетки этой строки точками.
4. Вычисление разностей столбцам и строкам, не принимая во внимание стоимость в клетках, имеющих ресурсы и клетках с точкой (исключенную строку или столбец) и определение максимальной разности в строке или столбце (В3 = 76).
5. Поиск минимального элемента в строке или в столбце с максимальной разностью (А1В3 = 24) и размещения в данную клетку максимально возможного количества ресурса, возвращение к этапу №4 и т.д. Окончательно
ЦФ Q=23∙19 + 7∙3 + 20∙18 + 2∙10 + 14∙24 + 1∙100 +3∙48 = = 437 + 21 + 360 + 20 +3 36 + 100 + 272 =1546 ед. Это значение соответствует опорному плану Фогеля.
III. Транспортная задача линейного программирования
Как основной метод решения транспортной задачи – используется метод потенциалов. Ни симплексный метод, ни распределительный метод здесь не рассматриваются. У них имеются свои плюсы и минусы, но объем изложения достаточно велик. Возможно этому позднее я уделю внимание и время, но пока отвечаю на пожелание читателя Хабра.
Пример 3 - Транспортная задача. Метод потенциалов
Исходные данные задачи удобно представить двумя матрицами.
ТАБЛИЦА - Исходные данные
Требуется найти план Х [m,n] перевозок, удовлетворяющий условиям на целевую функцию Q и переменные хij задачи
Решение задачи:
1. Формирование начального опорного плана способом Северо-Западного угла.
Базисные n + m – 1 = 3 + 4 – 1 = 6 переменные:
x11 =70, x12 = 20, x22 = 10, x23 = 20, x24 = 0, x34 = 40.
Остальные переменные nm – n + m – 1 = 12 – 6 = 6 свободные:
x13 = x14 = x21 = x24 = x31= x32 = 0 .
Суммарная стоимость перевозок для опорного плана получает представление:
Q = d11 ∙x11 + d12∙x12 + d22∙x22 + d23∙x23+ d24∙x24+ d34∙x34 =
=2∙70 + 3∙20 + 3∙10 + 1∙20 + 2∙0 + 2∙40 = 140 + 60 + 30 + 20 + 0 +80 = 330 ед.
2. Проверка опорного плана на оптимальность
Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов. Определим систему уравнений для потенциалов и вычислим их значения:
α1 + β1 = d11 = 2;
α1 + β2 = d12 = 3;
α2 + β2 = d22 = 3;
α2 + β3 = d23 = 1;
α2 + β4 = d24 = 2;
α3 + β4 = d34 = 2.
Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пусть β1 = 0. Тогда после решения системы получены значения потенциалов: α1= 2, α2= 2, α3= 2, β1 =0, β2=1, β3 =–1, β4 =0,
Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].
Выделяем в Г [m, n] свободные ячейки, содержащие γrs. Проверяем наличие положительных переменных γi,j > 0. Так как в матрице (в свободных ячейках) имеем γ32 = 2 > 0, то исходный опорный план может быть улучшен, он не является оптимальным.
3. Переход к новому (улучшенному) опорному плану
Переменную x32 =x следует ввести в базис. Обозначим ее предварительно через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся начальным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок
Обозначим ее предварительно через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся начальным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок Очевидно, что наибольшее x определяется теми xij в базисных клетках, из которых этот х вычитается. Следовательно, x11 = min{х22, х34} = {10, 40} = 10. При x >10 перевозка х22 становится отрицательной. Переменную х22 исключаем из базиса и переводим ее в разряд свободных переменных. Далее повторяются рекурсивно три пункта алгоритма.
Получаем из модифицированного плана новый опорный план
В нем объемы перевозок распределены иначе чем в начальном опорном плане.
Суммарная стоимость перевозок для этого опорного плана получает представление:
Q = d11 ∙x11 + d12∙x12 + d23∙x23 + d32∙x32 + d24∙x24+ d34∙x34 =
=2∙70 + 3∙20 + 2∙10 + 1∙20 + 1∙10 + 2∙30 = 140 + 60 + 20 + 20 + 10 + 60 = 310 ед. Затраты на перевозки при этом плане уменьшились на 330 – 310 = 20 ед.
Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов.
2. Проверка опорного плана на оптимальность
Определим систему уравнений для потенциалов и вычислим их значения:
α1 + β1 = d11 = 2;
α1 + β2 = d12 = 3;
α2 + β3 = d23 = 1;
α2 + β4 = d24 = 2;
α3 + β2 = d32 = 1;
α3 + β4 = d34 = 2.
Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пустьα1 = 0. Тогда после решения системы получены значения потенциалов: α1= 0, α2= – 2, α3= –2, β1 =2, β2=3, β3 = 3, β4 =4.
Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].
Свободные ячейки матрицы Г [m, n] содержат γi,j > 0 (γ14 = 1>0). План не оптимален.
3. Переход к новому (улучшенному) опорному плану
Из свободных переменных с xij > 0, выбираем одну x14 для введения ее в базис. Обозначим ее как и ранее через x без индексов. С учетом того, что х должна быть положительна х > 0. Найдем значение max x при условии сохранения баланса перевозок. Для этого воспользуемся очередным опорным планом. Будем добавлять переменную х в ячейки таблицы так, чтобы сохранялись условия баланса перевозок
Очевидно, что наибольшее x определяется теми xij в базисных клетках, из которых этот х вычитается. Следовательно, x11 = min{х12, х34} = {20, 30} = 20. При х12 >20 перевозка х12 становится отрицательной. Переменную х12 исключаем из базиса и переводим ее в разряд свободных переменных. Переходим к новой итерации
1. Получаем из модифицированного плана новый опорный план.
В нем объемы перевозок распределены иначе чем в предшествующем опорном плане.
Суммарная стоимость перевозок для этого опорного плана получает представление:
Q = d11 ∙x11 + d14∙x14 + d23∙x23 + d32∙x32 + d24∙x24+ d34∙x34 =
=2∙70 + 3∙20 + 1∙20 + 2∙10 + 1∙30 + 2∙10 = 140 + 60 + 20 + 20 + 30 + 20 = 290 ед. Затраты на перевозки при этом плане уменьшились на 310 – 290 = 20 ед. Является ли найденный опорный план оптимальным? Ответ может быть получен после составления и решения системы уравнений для потенциалов.
2. Проверка опорного плана на оптимальность
Определим систему уравнений для потенциалов и вычислим их значения:
α1 + β1 = d11 = 2;
α1 + β4 = d14 = 3;
α2 + β3 = d23 = 1;
α2 + β4 = d24 = 2;
α3 + β2 = d32 = 1;
α3 + β4 = d34 = 2. Каждое из этих значений соответствует одной базисной ячейке. Одну из неизвестных в системе можно задавать произвольно. Пусть β1 = 0. Тогда после решения системы получены значения потенциалов: α1= 2, α2= 2, α3= 2, β1 =0, β2=1, β3 =–1, β4 =0.
Формируем матрицу фиктивных стоимостей D'[m, n] и матрицу Г [m, n].
При переходе к новому опорному плану проверяем наличие положительных свободных переменных γi,j >0. Но таких переменных не оказалось. Отсюда следует вывод, что полученный последним модифицированный план является оптимальным и ему соответствует значение линейной формы
Q'= 2∙70 + 3∙20 + 1∙20 + 2∙10 + 1∙30 + 2∙10 = 290.
Заключение
Вся теория исследования операций с позиций математики решает неклассические задачи оптимизации целевых функций. Отличие от классики в том, что те ограничения на переменные, которые исследователи вынуждены накладывать в рамках моделей, созданы и вызваны реальностью. Отыскивать требуется экстремумы функций при многих ограничениях, так называемые условные экстремумы. Классика не позволяет этого делать. Взятие производных и приравнивание их нулю "не видит" ограничений. Лучшее, что там имеется это функция Лагранжа, но ее использование также весьма ограничено. Транспортные задачи – частный, но важный случай в исследовании операций. Надеюсь, что читатель разобравшись в приведенных примерах, лучше стал понимать логику задачи и сумеет самостоятельно постигать интересующие его вопросы по другим публикациям в учебниках и журнальных статьях.
Литература
Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.
Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.
Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.
Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.
Пфанцагль И. Теория измерений. – М.: Наука, 1988.–384 с.
Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.
Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.