Транспортная задача – основные понятия, определения и теоремы

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

Математическая модель транспортной задачи

Постановка задачи

Пусть некоторый продукт, который мы будем называть грузом, нужно перевезти с одних складов в другие. Склады, в которых первоначально находится груз, мы будем называть поставщиками. Склады, в которые нужно перевести груз, будем называть потребителями. То есть весь груз нужно перевезти от поставщиков к потребителям. Считаем, что есть m поставщиков и n потребителей. Пронумеруем поставщиков от единицы до m. Пусть в i-ом складе поставщика имеется a_i единиц груза, . И пусть каждый j-ый потребитель может принять только определенное количество груза b_j, . Известна стоимость c_ij перевозки единицы груза от i-го поставщика к j-му потребителю. Требуется составить такой план перевозок, то есть определить количество груза x_ij, которое нужно перевести от i-го поставщика к j-му потребителю, при котором весь груз от поставщиков будет перевезен к потребителям с минимальными затратами на перевозки.

Построим математическую модель транспортной задачи. Затраты на перевозку груза от i-го поставщика к j-му потребителю равны произведению стоимости перевозки единицы груза на количество перевозимого груза. Суммируя по всем поставщикам и потребителям, получим суммарную стоимость перевозок:
.
Задача состоит в том, чтобы подбором величин , сделать суммарную стоимость перевозок минимальной:
.

Если просуммировать x_ij по всем потребителям j, то получим суммарное количество груза, перевезенного от i-го поставщика ко всем потребителям. Оно должно равняться запасам a_i этого поставщика:
.

Если просуммировать x_ij по всем поставщикам i, то получим суммарное количество груза, доставленного j-му потребителю от всех поставщиков. Оно должно равняться потребностям b_j этого потребителя:
.

Также мы должны учесть, что количество перевезенного груза не может быть отрицательным:
.

В результате, мы получаем математическую модель транспортной задачи:



.

Определение транспортной задачи

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

– это задача линейного программирования следующего вида:
(М.1)  
(М.2)  
(М.3)  
(М.4)   ,
где .
В транспортной задаче требуется определить количество груза , которое нужно перевезти от -го поставщика к -му потребителю, чтобы перевезти весь груз от поставщиков к потребителям, и при этом суммарные затраты на перевозки были минимальны.
Здесь – стоимость перевозки единицы груза от -го поставщика к -му потребителю; – мощность -го поставщика, то есть максимальное количество груза, которое может отправить этот поставщик; – мощность -го потребителя, то есть максимальное количество груза, которое может принять этот потребитель; m – число поставщиков; n – число потребителей.

Матрица транспортных издержек

– это матрица, составленная из элементов , каждый из которых равен затратам на перевозку единицы груза от -го поставщика к -му потребителю.

План перевозок транспортной задачи

– это совокупность переменных , каждая из которых равна количеству груза, перевозимого от -го поставщика к -му потребителю. Эти переменные удовлетворяют условиям (М.2), (М.3) и (М.4). План перевозок обычно записывают в виде матрицы.

Исследование математической модели

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

Чтобы использовать общие положения линейного программирования, нам нужно сделать переход от нумерации двумя индексами к нумерации одним индексом. Рассмотрим такой переход на примере с . Выпишем уравнения системы ограничений (М.2), (М.3) для этого случая:

Введем переменные, нумерованные одним индексом:
.
Тогда система ограничений примет обычный для задач ЛП вид:

Ее можно записать в матричном виде:
, где
;   ;   .

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

.

Нетрудно видеть, что в случае произвольных m и n, система ограничений транспортной задачи имеет каноническую форму:
, где

,   .
Элементы матрицы A удобно выразить через векторы условий. Тогда матрицу можно записать в виде одной строки:
, где
.

Закрытая и открытая модели

Согласно теореме о существовании решения ⇑, чтобы транспортная задача имела решение, сумма мощностей поставщиков должна равняться сумме мощностей потребителей:
.
Такая задача называется задачей с правильным балансом, а ее математическая модель – закрытой.

Транспортная задача с правильным балансом

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

Транспортная задача с неправильным балансом

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

Открытая модель

Если задача с неправильным балансом, то система ограничений (М.2), (М.3), (М.4) не имеет решений, поскольку, или часть потребителей не получат требуемое количество, или часть поставщиков не смогут реализовать все грузы. То есть уравнения системы ограничений не будут выполняться ни при каком плане перевозок . Чтобы исправить ситуацию, мы должны или в (М.2), или в (М.3), заменить равенства равенствами.

Пусть сумма мощностей поставщиков меньше суммы мощностей потребителей:
.
Тогда часть потребителей не получат требуемого количества груза. При этом все поставщики смогут реализовать груз в полном объеме. Это означает, что количество полученного потребителем j груза, , может быть меньше его потребности . В этом случае, нам надо заменить равенства (М.3) неравенствами:
(Т.1)   .

Аналогичным образом, пусть сумма мощностей поставщиков больше суммы мощностей потребителей:
.
В этом случае, можно составить такой план перевозок, при котором все потребители получат требуемое количество груза, но часть поставщиков не реализуют свой груз в полном объеме. То есть количество отправленного поставщиком i груза, , может быть меньше имеющегося запаса . Тогда, чтобы получить решение задачи, нужно заменить равенства (М.2):
(Т.2)   .

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

Приведение открытой модели к закрытой

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

Так, если , то мы вводим фиктивного поставщика с мощностью , и нулевыми затратами .

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

Решение транспортной задачи методом потенциалов

Транспортную задачу можно решить различными методами, применяемыми в линейном программировании. При этом наиболее широко используются методы, которые позволяют получить решение, используя специфический вид системы ограничений (М.2) – (М.3).

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

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

Таблицы для расчетов

Выполнение решения транспортной задачи удобно проводить в таблицах. Обычно их заполняют следующим образом.

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

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

При обращении к определенной клетке, указывают ее номер, состоящий из двух цифр, точно так, как и при обращении к элементам матрицы издержек . То есть, например, когда мы говорим, что это клетка (1, 2), то тем самым подразумеваем, что это клетка, в которой записано значение . Первой строкой считается строка, относящаяся к первому поставщику . А первым столбцом – к первому потребителю .

Построение первого опорного плана

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

Транспортная задача (М.1) – (М.4) имеет каноническую форму. Тогда, согласно теореме о числе базисных переменных, число базисных переменных в любом опорном плане равно рангу r матрицы коэффициентов системы ограничений. Как мы выяснили, ранг матрицы коэффициентов системы ограничений транспортной задачи ⇑ равен . Поэтому опорный план имеет базисных переменных. Остальные переменные равны нулю. Это не означает, что все базисные переменные отличны от нуля. Некоторые базисные переменные также могут иметь нулевые значения. Но свободные переменные всегда равны нулю, а базисные переменные определяются из решения системы ограничений (М.2) – (М.3).

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

Метод северо-западного угла

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

См. Пример составления первого опорного плана методом северо-западного угла.

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

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

Метод наименьшей стоимости

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

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

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

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

Цикл – переход от одного базиса к другому

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

Циклом в транспортной задаче

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

Занятая клетка

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

Свободная клетка

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

Циклом для выбранной свободной клетки

(или просто циклом для клетки) называется цикл, у которого одна из вершин находится в выбранной свободной клетке, а остальные вершины – в занятых клетках.

Сдвигом по циклу

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

Простейшим циклом является прямоугольник. Вот примеры более сложных циклов. Вершины циклов отмечены знаком ′+′ или ′–′.

Особенностью цикла является то, что прибавление и вычитание одинакового количества поставок в его смежных вершинах, не нарушает выполнение системы уравнений (М.2) – (М.3). Это позволяет видоизменять начальный план перевозок, включая в него новые переменные, и исключая старые. Как мы знаем, оптимальный план должен быть опорным, или быть линейной комбинацией опорных планов. Поэтому, при решении транспортной задачи, мы имеем дело только с опорными планами. Опорный план имеет базисных переменных (занятые ячейки таблицы). Остальные переменные свободные (пустые ячейки); они равны нулю. Для перехода от одного опорного плана к другому, мы должны включить одну из свободных переменных в состав базисных, и сделать одну из базисных переменных свободной.

Переход от одного опорного плана к другому выполняется следующим образом.
1) Определяем свободную переменную, которую нужно включить в состав базисных. В первой таблице ⇑, это переменная . Соответствующая ей клетка (5, 1) свободная.
2) Строим цикл для выбранной свободной клетки. Как указано в определении ⇑, у такого цикла одна вершина находится в выбранной свободной клетке, а другие вершины – в занятых клетках (с базисными переменными). В рассматриваемой таблице ⇑, это цикл с вершинами (5, 1); (5, 2); (2, 2); (2, 3); (3, 3) и (3, 1).
3) Отмечаем вершину цикла выбранной свободной клетки знаком ′+′. Далее отмечаем остальные вершины знаками ′–′ и ′+′, чередуя их. Теперь если увеличить значения переменных со знаком ′+′ и уменьшить значения переменных со знаком ′–′ на одно и то же число, то это не приведет к нарушению баланса. То есть система уравнений (М.2) – (М.3) по прежнему будет выполняться. Однако, если изменить переменные на слишком большое число, то это может привести к появлению отрицательных значений, что не допустимо. Чтобы такого не произошло, переходим к следующему шагу.
4) Находим наименьшее значение переменной для клеток, помеченных знаком ′–′. Для нашей таблицы ⇑ это клетка (3, 1) со значением . То есть
5) В клетках, отмеченных знаком ′+′, прибавляем ; в клетках со знаком ′–′, вычитаем . То есть выполняем сдвиг по циклу ⇑ на величину . В результате свободная клетка, для которой строился цикл окажется заполненной значением , то есть соответствующая ей переменная станет базисной. А значение переменной с наименьшим начальным значением , станет равным нулю. Эту переменную мы исключаем из базиса. В результате переходим к новому набору базисных переменных. Для нашего примера он отображен во второй таблице ⇑.

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

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

Теоремы

Ниже приводим важные теоремы, имеющие отношение к циклам.

Улучшение плана методом потенциалов

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

Оценками свободных переменных

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

Величины и называют потенциалами по аналогии с потенциальной энергией, применяемой в механике. Там имеет смысл не сама потенциальная энергия, а ее разность в двух точках. Например, потенциальная энергия U тела, находящегося в поле тяготения Земли, или другой планеты, зависит от расстояния r до ее центра: . Но если взять другое выражение для потенциальной энергии: , отличающееся на постоянную C (то есть на предварительно выбранное число), то при подстановке вместо , уравнения движения тела не изменятся. Постоянную C выбирают из соображений удобства проведения математических расчетов.

Если рассмотреть уравнения (П.1) – (П.2), то видно, что они не изменятся, если вместо и подставить другие величины и , отличающихся от прежних на произвольную постоянную C:
(П.4)   .
В самом деле, подставляя (П.4) в (П.1) и (П.2), постоянная сокращается:
;
.
И соотношения для и имеют тот же вид, что и (П.1) – (П.2):
;
.

Поэтому, при определении потенциалов и , мы можем присвоить одному из них произвольное значение. Мы будем полагать, что
.
Тогда из уравнений (П.1) легко определить остальные потенциалы.

Когда мы определим все потенциалы и , нужно проверить выполнение неравенств (П.2). Если они выполняются, то план оптимален. Если нет, то план не оптимален, нужно переходить к другим базисным переменным.

Выбор новых базисных переменных

Выбор новых базисных переменных осуществляется с помощью оценок свободных переменных, которые определяются по формуле:
.
Для базисных переменных, . Если план оптимален, то для всех переменных. Если существуют отрицательные оценки, то план не оптимален.

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

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

Здесь базисные переменные:
.
Значение целевой функции:
.
Определяем потенциалы. Для этого выпишем уравнения (П.1) для базисных переменных:
(П.5.1)   ;
(П.5.2)   ;
(П.5.3)   ;
(П.5.4)   ;
(П.5.5)   ;
(П.5.6)   .
Полагаем . Из уравнений (П.5.1), (П.5.2) и (П.5.3) находим:
.
Из уравнения (П.5.6):
.
Из уравнения (П.5.5):
.
Из уравнения (П.5.4):
.
В результате мы нашли потенциалы:
.

Находим оценки свободных клеток.
; ; ; ; ; .
Мы видим, что есть отрицательные оценки. Поэтому план не оптимален. Наименьшая оценка в клетке (3, 1).

Вводим переменную с наименьшей оценкой в базис. Для этого строим для нее цикл (см. Цикл – переход от одного базиса к другому ⇑).

Наименьшая поставка в клетках, отмеченных знаком ′–′:   в клетке (1, 1). Выполняем сдвиг по циклу на величину . В результате переменная входит, а выходит из базиса. Получаем новый опорный план.

Базисные переменные:
.
Значение целевой функции нового опорного плана:
.
Изменение целевой функции после введения в базис переменной :
.
Как и следовало ожидать, оно равно произведению на :
.

Множественное решение

Пусть мы получили оптимальный план, и при этом одна или несколько оценок свободных клеток равны нулю. Покажем, что в этом случае решение задачи не единственное, существует два или более оптимальных опорных планов, а их линейная комбинация может дать бесконечно много решений. Предположим, что оценка свободной клетки равна нулю. Тогда, в силу (П.3),
(П.6)   .
Перейдем к новым базисным переменным, включив в их состав . Допустим, что из базиса выйдет переменная . Тогда для определения потенциалов, мы получим ту же систему уравнений (П.1), в которой вместо уравнения будет уравнение (П.6). Но поскольку при решении первой системы мы получили, что уравнение (П.6) выполняется, тогда и новой системе удовлетворяют те же значения потенциалов. Поэтому новый план также будет оптимальным.

См. Пример решения транспортной задачи методом потенциалов

Использованная литература:
С. Гасс. Линейное программирование (методы и приложения). Москва, «Государственное издательство физико-математической литературы», 1961.
Общий курс высшей математики для экономистов. Под общей редакцией В. И. Ермакова. Москва, «ИНФРА-М», 2007.
К. Н. Лунгу. Линейное программирование. Руководство к решению задач. Москва, «ФИЗМАТЛИТ», 2005.
Д. Б. Юдин, Е. Г. Гольштейн. Задачи и методы линейного программирования. Москва, «Советское радио», 1961.

Автор: Олег Одинцов.     Опубликовано: 15-10-2021