Модель грузоперевозок региональной транспортной компании

Задача об оптимальных назначениях

Задачи, продолжающие тему линейного программирования

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

3.1.1. Постановка задачи. В составе фирмы имеются n работников, которых предполагается назначить на выполнение m работ, в общем случае nm. Если n>m, менеджер фирмы ранжирует работников по их квалификации по всем m работам. На каждую j-ую работу назначается работник с наивысшей квалификацией по этой работе, остальные (n–m) работников увольняется.

Если n<m, исходя из тех же соображений некоторых работников можно назначить на выполнение нескольких работ, объявив их одной большой работой.

Приходим к оставшемуся варианту, когда n = m, n работников фактически надо назначить на выполнение m работ, но так, чтобы суммарная эффективность их работы для фирмы была наибольшей. При этом предполагается, что каждый работник может выполнять любую работу, но с различными эффективностями. Для определённости положим работу производственной, имеющей утверждённые нормативы выработки. Тогда эффективность работы будем считать производительностью труда. Можно построить квадратную матрицу А производительностей труда:

,

- производительность труда i-го работника при выполнении j-ой работы

Надо найти такой набор из n элементов матрицы А, сумма которых будет наибольшей. Но не всякий набор из n элементов нас устроит. По смыслу каждый работник должен выполнять одну работу, каждая работа выполняется одним работником. Если вдуматься в эти требования, то они означают: никакие два элемента из набора не должны находиться в одной строке или в одном столбце. В математике такой набор называется множеством из независимых элементов. Например, матрица порядка 3 имеет 6 различных множеств независимых элементов:

Квадратная матрица порядка n имеет n! различных множеств независимых элементов.

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

Рассмотрим сущность метода на примере матрицы производительностей труда порядка 4. Будем перебирать подряд все элементы, например, первой строки матрицы, полагая их первыми элементами множеств независимых элементов. Пусть выбран первый элемент первой строки. Тогда другие элементы множества независимых элементов, включающего этот элемент, не могут находиться в первой строке или в первом столбце исходной матрицы. Для перебора других элементов множества независимых элементов остаётся подматрица порядка 3 исходной матрицы. Повторим ту же процедуру к первой строке подматрицы порядка 3, получим 3 подматрицы порядка 2. Каждая подматрица порядка 2 имеет только 2 множества независимых элементов. Таким образом, для первого элемента первой строки исходной матрицы получили 6 различных множеств независимых элементов.

Теперь выбираем второй элемент первой строки исходной матрицы. Удаляя из неё первую строку и второй столбец, получаем подматрицу порядка 3, к которой применяем ту же процедуру. Получаем новые 6 множеств независимых элементов. Перебрав все 4 элемента первой строки исходной матрицы, имеем 24 различных множеств независимых элементов.

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

Итак:

“Звёздочками” (*) отмечены наибольшие значения суммы по каждой из четырёх групп множеств независимых элементов. Наибольшее значение суммы равно 30 для набора (9,6,8.7). Этот набор чисел образуют элементы, находящиеся на определённых местах в матрице А производительностей труда. Фиксируя места (номера строк и столбцов):

,

получаем возможность сформулировать решение задачи об оптимальных значениях:

- первый работник назначается на выполнение второй работы;

- второй работник назначается на выполнение первой работы;

- третий работник назначается на выполнение третьей работы;

- четвёртый работник назначается на выполнение четвёртой работы.

3.2.1. Постановка задачи. Рассмотрим деятельность региональной транспортной компании, специализирующейся на перевозках одного определённого продукта. Имеется n различных географических мест, в каждом из которых находится поставщик (или непосредственно производитель) продукта, располагающий запасом этого продукта в объёме a_i, i=1,2,…,n. В других различных m местах, удалённых от поставщиков, имеются потребители этого продукта в объёмах b_j, j=1,2,…m. Для поставщиков и потребителей продукт – товар, имеющий рыночную цену. Для транспортной компании продукт – груз, перевозка которого также имеет цену. Компания рассматривает поставщика как отправителя, а потребителя – как получателя груза.

Обозначим x_ij количество груза, перевозимого от i-го отправителя к j-му получателю, x_ij>0. Известна матрица С внутренних цен (себестоимостей) перевозок c_ij – стоимостей доставки единицы количества груза от от i-го отправителя к j-му получателю. Суммарные затраты на перевозку всех грузов . Цель компании – учитывая запросы потребителей и производителей продукта в его количествах, минимизировать затраты V при естественных ограничениях для x_ij. Возможные ситуации таковы.

а) Предложение и спрос на продукт строго сбалансированы: .

В этом случае – количество продукта, поставленного из i-го пункта всем потребителям, равно запасу i-го пункта; – количество продукта, поставленное из всех мест j-му потребителю, равно запросу j-го потребителя. Возникает так называемая замкнутая транспортная задача:

б) Предложение продукта превышает спрос (запас больше потребностей), . В этом случае – из i-го пункта вывозится не больше продукта, чем его имеется, а из некоторых пунктов - даже меньше, чем его имеется; – запрос каждого потребителя удовлетворяется полностью. Получаем естественную открытую транспортную задачу.

в) Спрос продукта превышает его предложение, . Здесь – из каждого i-го пункта вывозится весь продукт, – не каждый потребитель удовлетворяет свой запрос на продукт. Возникает открытая транспортная задача с дефицитом. Ниже представлены формулировки этих задач:

б) в)

3.2.2. Решение замкнутой транспортной задачи. Надо найти матрицу оптимального плана Х*, если известны a_i, b_j , c_ij ; .

Данные : Ищется матрица Х*:

(элементы матриц находятся в квадратиках)

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

а) Поиск опорного плана. Имеем пустую матрицу-таблицу опорного плана , окаймлённую внизу строкой потребностей, а справа – столбцом наличия продукта. Будем искать методом наименьших элементов матрицы цен перевозок. Для этого в матрице С выбирается наименьший элемент с_ij (то есть выбирается самая дешёвая перевозка между i-ым пунктом отправления и j-ым пунктом доставки). Если , то заполнение опорного плана начинается с присвоения . Таким образом, вся потребность j-го потребителя покрывается перевозкой продукта из i-го пункта. Тогда все остальные элементы j-го столбца заполняются нулями (не требуется вывоз продукта к j-му потребителю из других мест). Внизу в строке потребностей заменяется нулём, в столбце наличия из вычитается (рисунок 10).

Рисунок 10. Начальный этап построения матрицы опорного плана , случай ; на рисунке х₂₂ = , .

Если , то х_ij =В столбце наличия продуктов заменяется нулём (весь продукт из i-ого пункта вывезен j-му потребителю). Потребность j-го потребителя уменьшается на величину . Все элементы i-ой строки, кроме х_ij, заполняются нулями (нечего больше поставить потребителям из i-ого пункта) (рисунок 11).

Рисунок 11. Начальный этап Рисунок 12. Пример опорного плана .

построения опорного плана , ;

на рисунке х₂₂ = , х_ij =0, j ≠ 2.

Снова просматривается уменьшенная на одну строку (или один столбец) матрица С. Снова среди оставшихся элементов выбирается наименьший, обозначим его c_ks. По той же схеме находится соответствующий элемент х_ks опорного плана , остальные элементы строки (столбца) заполняются нулями. Затем процедура снова повторяется. В конце остаётся один нулевой в строке потребителей и один ненулевой в столбце наличия, причём . Последний ненулевой элемент матрицы : . Строка потребностей и столбец наличия заполнены нулями. Получен опорный план , часть элементов которого – нули. На рисунке 12 показан пример плана . В соответствии с ним внутренняя стоимость всех перевозок равна:

.

б) Улучшение опорного плана вплоть до оптимального. Опорный план подвергается «шевелению» путём приращения бывших в опорном плане нулевых компонент и соответствующего уменьшения ненулевых компонент. На изменённом плане подсчитывают суммарные затраты V⁺⁺ на перевозки. Если V⁺⁺ на изменённом плане меньше V⁺ на исходном опорном плане, то изменённый план X⁺⁺ принимается за новый опорный, и он снова подвергается процедуре «шевеления». Если «шевеление» всех нулей очередного опорного плана X^+…+ не приводит к уменьшению V^+…+, то X^+…+ и есть оптимальный план, X^+…+= X⁺, V^*=V(X^+…+)= V^+…+.

Конкретно процедура «шевеления» опорного плана – это оценка прироста транспортных затрат (ПТЗ) при перераспределении груза на единицу количества. В этом случае стоимости изменённых количеств численно являются ценами перевозок.

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

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

Пусть ПТЗ < 0 для данного контура. Среди вершин, соответствующих отрицательным ценам, выбирается вершина с наименьшим по значению элементом. Это значение вычитается из всех элементов, привязанных к отрицательным ценам, и добавляется ко всем элементам, соответствующих положительным ценам контура. На контуре возникает новый нуль, старый нуль заполняется положительным значением. Так образуется новый опорный план, частично изменённый по отношению к старому. Его снова улучшают по рассматриваемому методу оценки ПТЗ. Так продолжается до тех пор, пока ПТЗ для всех нулей последнего плана не станет неотрицательным. Тогда последний опорный – оптимальный. Для каждого опорного плана подсчитывается его стоимость V. Должны выполняться оценки:

V⁺> V⁺⁺>…> V^+…+= V^* .

На рисунке 13 показан пример перехода к новому опорному плану; предполагается, что нуль, расположенный во второй строке и во втором столбце, имеет ПТЗ < 0.

Рисунок 13. Построение нового опорного плана на основе нуля, находящегося во второй строке и втором столбце старого плана, обеспечивающего ПТЗ < 0.

Замечания. Каждому нулю в опорном плане Х отвечает ровно один замкнутый контур, если число всех ненулевых элементов равно m+n– 1. Если же ненулевых элементов меньше, то найдутся нули, для которых нельзя построить никакого контура. Такая ситуация может сложиться на этапе а) построения опорного плана, когда в процессе построения очередная самая дешёвая цена с_ij такова, что , то есть, сразу удовлетворены и поставщик, и потребитель продукта, поэтому нули заполняют строку и столбец одновременно. Надо обойти цену с_ij , выбрать следующую по дешевизне цену с_fg. Ещё один способ уменьшения нулей – при улучшении опорного плана вычитать из отрицательных элементов-вершин контура не весь наименьший элемент, а только его часть.