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

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

Классическая постановка транспортной задачи. Пусть имеется m поставщиков А₁, А₂,…, А_i,..., А_m однородного а₁, а₂,…,а_i,…, а_m единиц и n потребителей В₁, В₂,…,В_j,…,В_n этого груза, потребность которых составляет соответственно b₁, b₂,…,b_j,…,b_n единиц.

Известны стоимости перевозок единицы груза от i-го поставщика к j-му потребителю —

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

Замечание. Перевозимый груз должен быть однородным, например, песок, уголь, лес, кирпичи, металл и т.п. Единицы измерения количества груза могут быть различными (т, м³, шт., л. и т.п.). Предполагается, что стоимость перевозимого груза пропорциональна его количеству. В качестве поставщиков груза могут выступать предприятия, базы, склады, а в качестве потребителей — предприятия, магазины, строительные объекты и т.п.

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

Чтобы лучше представить условие задачи, сведем исходные данные в таблицу 18. Строка таблицы соответствует поставщику, а столбец — потребителю.

Модели транспортной задачи. При постановке конкретных задач перевозки грузов может возникнуть одна из трёх ситуаций:

1) количество груза у всех поставщиков равно потребности в данном грузе всех потребителей :

или

(4.18)

2) количество груза у всех поставщиков больше потребности в данном грузе всех потребителей :

или

(4.19)

3) количество груза у всех поставщиков меньше потребности в данном грузе всех потребителей

или

(4.20)

Каждой ситуации соответствует определенная модель транспортной задачи.

Рассмотрим ситуацию (1), которой отвечает соотношение (4.18). Объектом исследования в транспортной задаче является планирование перевозок грузов. Цель исследования — составление плана перевозки грузов, обеспечивающего минимальные транспортные расходы. Критерий задачи — минимальные транспортные расходы. Отразим критерий задачи в целевой функции. Стоимость перевозки единицы груза от i-го поставщика к j-му потребителю составляет с_ij, а груза перевозится х_ij единиц. Следовательно, стоимость перевозки всего груза от i-го поставщика к j-му потребителю будет равна величине c_ijx_ij. Учитывая, что суммарная стоимость перевозки грузов от всех поставщиков ко всем потребителям должна быть минимальной, целевая функция транспортной задачи будет иметь вид:

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

Первая группа ограничений, количество которых равно т (количество поставщиков), отражает тот факт, что весь груз, имеющийся у поставщиков, должен быть вывезен:

Вторая группа ограничений, количество которых равно п (количество потребителей), отражает тот факт, что каждый потребитель должен получить ровно столько груза, сколько ему необходимо:

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

В компактном виде модель транспортной задачи можно представить следующим образом:

(4.21)

Для того, чтобы транспортная задача (4.21) была разрешима, т.е. имела оптимальный план, необходимо и достаточно выполнение условия (4.18).

Рассмотрим ситуацию (2), которой отвечает соотношение (4.19). В данной ситуации у всех поставщиков имеется больше груза, чем необходимо потребителям. Поэтому часть груза у поставщиков останется, а потребители получат весь необходимый груз. Поскольку у части поставщиков груз останется, ограничения первой группы будут иметь вид «≤», а модель транспортной задачи примет следующий вид:

В ситуации (3), которой отвечает соотношение (4.20), всем потребителям нужно больше груза, чем имеется у поставщиков. Поэтому каждый поставщик весь свой груз вывезет, а часть потребителей получат груза меньше необходимого количества и уже ограничения второй группы примут вид «≤».

Модель (4.21) называется закрытой моделью транспортной задачи, а соответствующая ей задача — сбалансированной. Модели, отвечающие соотношениям (4.19) и (4.20), называются открытыми. Количество переменных в модели равно (т×п), а количество ограничений — (m+п).

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

В ситуации (2), когда вводится фиктивный потребитель B_n+1 с потребностью b_n+1= . К левой части каждого ограничения первой группы прибавляется соответственно неотрицательная переменная X_i,n+1 (i=1,m), во вторую группу ограничений добавляется ограничение, соответствующее фиктивному потребителю B_n+1:

.

В таблицу исходных данных задачи (таблица 18) добавляется столбец.

В ситуации (3), когда , вводится фиктивный поставщик А_т+1 с наличием груза в количестве а_n+1= .

К левой части каждого ограничения второй группы прибавляется соответственно неотрицательная переменная X_m+1j (j=1,n), в первую группу ограничений добавляется ограничение, соответствующее фиктивному поставщику А_т+1:

.

В таблицу исходных данных задачи (таблица 18) добавляется строка.

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

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

Методы построения исходного плана. Для решения исходные данные транспортной задачи (4.21) сводятся в таблицу (таблица 18). Из условия (4.18) следует, что любое ограничение транспортной задачи является линейной комбинацией остальных. Следовательно, система ограничений транспортной задачи линейно зависима и содержит только m+n–1 независимых уравнений. Поэтому исходный допустимый невырожденный базисный план должен иметь m+n–1 базисную переменную и его легко можно получить непосредственно из данных таблицы. Все остальные переменные — небазисные и их значения равны нулю, которые в таблице можно не отражать, т.е. клетку, соответствующую небазисной переменной, оставлять незаполненной.

Метод северо-западного угла. Определение значений x_ij начинается с левой верхней клетки таблицы. Находим значение из x₁₁ соотношения

Возможны три варианта:

1. Если a₁<b₁, то x₁₁=a₁, строка i=1 исключается из дальнейшего рассмотрения, а потребность первого потребителя b₁ уменьшается на величину a₁;

2. Если a₁>b₁, то x₁₁=b₁, столбец j=1 исключается из дальнейшего рассмотрения, а наличие груза у первого поставщика a₁ уменьшается на величину b₁;

3. Если a₁=b₁, то x₁₁=a₁=b₁, строка i=1 и столбец j=1 исключается из дальнейшего рассмотрения. Данный вариант приводит к вырождению исходного плана.

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

После завершения описанного процесса необходимо провести проверку полученного плана на врожденность. Если количество заполненных клеток равно m+n–1, то план является невырожденными, в противном случае — вырожденным.

Если план вырожденный, т.е. количество заполненных клеток оказалось меньше m+n–1, то незаполненные клетки с минимальными стоимостями перевозок заполняются нулями, чтобы общее количество заполоненных клеток стало равным m+n–1. Однако при расстановке нулей необходимо помнить, что в таблице не должно быть ни одного прямоугольника, все вершины которого являются заполненными клетками. Например, переменные х₁₁, х₁₂, х₂₁, х₂₂ или х₁₁, х_1n, х₂₁, х_2n (таблица 18) не могут быть одновременно базисными.

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

Определение значений x_ij начинается с клетки, имеющей минимальную стоимость перевозки.

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

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

Проверка полученного плана на врожденность и расстановка (в случае вырожденности плана) нулей осуществляется так же, как это описано для метода северо-западного угла.

Метод потенциалов. Для нахождения оптимального плана транспортной задачи созданы специальные методы, самым распространенным из которых считается метод потенциалов.

Алгоритм, реализующий метод потенциалов.

1. Каждому поставщику A_i поставим в соответствие некоторое число u_i, называемое потенциалом A_i, а каждому потребителю B_j (т.е. каждому столбцу)поставим в соответствие некоторое число, называемое потенциалом B_j.

Для каждой заполненной клетки, т.е. для каждой базисной переменной, строится соотношение

(4.22)

Полученная система должна содержать m+n–1 уравнений с m+n неизвестными. Как известно, такая система имеет множество решений, и любое из них будет содержать искомые потенциалы. Чтобы найти одно из решений, значение одного потенциала в системе задается произвольно. Обычно считают, что u₁=0, и находят значения остальных потенциалов. Значения потенциалов записывают справа и снизу таблицы против соответствующих строк и столбцов.

2. Для каждой незаполненной клетки, т.е. для каждой небазисной переменной, рассчитываются так называемые косвенные тарифы (с′_ij) по формуле

(4.23)

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

3. Проверим полученный план на оптимальность по критерию оптимальности плана транспортной задачи. Если для каждой незаполненной клетки выполняется условие

(4.24)

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

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

5. В каждой клетке цикла, начиная с незаполненной, проставляются поочередно знаки «+» и «–». В клетках со знаком «–» выбирается минимальная величина. Новый базисный план получается путем сложения выбранной величины с величинами, стоящими в клетках цикла со знаком «+», и вычитания этой величины из величин, стоящих в клетках со знаком «–».

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

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

Осуществляется переход к пункту один алгоритма.

Пример: У трех поставщиков А₁,А₂, А₃ имеются однородные грузы соответственно в количествах 335, 2701 и 195 условных единиц, которые нужно распределить между потребителями В₁, В₂, В₃, В₄ и В₅ соответственно в количествах 95, 120, 205, 175 и 205 условных единиц.

Составить такой план перевозок, чтобы стоимость их была бы наименьшей, если тарифы С_ij на перевозку условной единицы груза даны в матрице:

Для получения первого опорного плана заполняем таблицу 19, начиная с клетки А₁В₁, расположенной в левом верхнем углу в направлении клетки А₃В₅ (метод северно-западного угла или метод наименьшего элемента в матрице).

Таблица 19

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

Подсчитаем стоимость перевозок по первому опорному плану:

L₁=11×95+15×120+12×120+14×85+10×175+11×10+17+195=10650 (денежных единиц).

Вычисляем оценки матрицы косвенных стоимостей (тарифов) U_i и V_j, используя тарифы только в занятых клетках.

u₁+v₁=11 u₁=0

u₁+v₂=15 v₁=11

u₁+v₃=12 v₂=15

u₂+v₃=14 v₃=12

u₂+v₄=10 u₂=2

u₂+v₅=11 v₁=8

u₃+v₅=17 v₅=9

u₃=8

Затем находим оценки Z_ij для свободных клеток по формуле:

Z_ij=(u_i+v_j) – c_ij

Z₁₄=0+8–18<0

Z₁₅=0+9–19<0

Z₂₁=2+11–8=5>0

Z₂₂=2+15–12=5>0 Выбираем клетку с наибольшим

Z₃₁=8+11–10=9>0 положительным Z_ij

Z₃₂=8+15–15=8>0 Здесь это Z₃₁=9

Z₃₃=8+12–18=2>0

Z₃₄=8+8–13=3>0.

Строим для клетки Z₃₁ — прямоугольный контур с вершиной Z₃₁, а остальные вершины должны быть в занятых клетках. Получим контур А₃В₁; А₁В₁, А₁В₃, А₂В₃, А₂В₅, А₃В₅.

Наименьшее из отрицательных вершин q — это 85. Сделаем перераспределение (таблица 20).

Таблица 20

Повторяем процесс.

Для занятых клеток:

u₁+v₁=11 u₁=0

u₁+v₂=15 v₁=11

u₁+v₃=12 v₂=15

u₂+v₄=10 v₃=12

u₂+v₅=11 u₃=–1

u₃+v₁=10 v₅=18

u₃+v₅=17 u₂=–7

v₄=17

Оценки для свободных клеток:

Z₁₄=0+17–18=–1<0

Z₁₅=0+18–19=–1<0

Z₂₁=–7+11–8=–4<0 Т.к. имеется клетка с

Z₂₂=–7+15–12<0 положительным Z_ij =Z₃₄>0,

Z₂₃=–7+12–14<0 то план не является оптимальным

Z₃₂=–1+15–15<0

Z₃₃=–1+12–18<0

Z₃₄=–1+17–13=3>0.

Для клетки А₃В₄ строим прямоугольный контур А₃В₄, А₂В₄, А₂В₅, А₃В₅. Из отрицательных вершин наименьшее число 110. Перемещаем его в клетку А₃В₄ и делаем перераспределение.

Таблица 21

L=11×10+15×120+12×205+10×65+11×205+10×85+13×110=9555 (денежных единиц).

Проверяем полученное решение на оптимальность

Для занятых клеток:

u₁+v₁=11 u₁=0

u₁+v₂=15 v₁=11

u₁+v₃=12 v₂=15

u₂+v₄=10 v₃=12

u₂+v₅=11 u₃=–1

u₃+v₁=10 v₄=17

u₃+v₅=17 v₂=–7

u₅=18

Оценки свободных клеток:

Z₁₄=0+14–18<0

Z₁₅=0+15–19<0

Z₂₁=–4+11–8<0

Z₂₂=–4+15–12<0

Z₂₃=–4+12–14<0

Z₃₂=–1+15–15<0

Z₃₃=–1+12–18<0

Z₃₅=–1+15–17<0.

Все Z_ij <0, следовательно план оптимальный.

Тогда, L(x)_min=9555 денежных единиц.

Пример: В пределах одного города перевозится одинаковый груз из трех пунктов отправления к трем местам назначения. Всего отправляется ежедневно 30тонн, в том числе из первого — 12тонн; второго — 8тонн; третьего — 10тонн. К первому — 6тонн; второму — 9тонн; и третьему — 15тонн. Требуется составить план перевозок, обеспечивающий минимальные транспортные расходы. Пункт назначения — цифры, пункт отправления — буквы. В клетках таблицы расположены девять неизвестных величин задачи, обозначающих объем перевозок в тоннах от i — отправителя к j — получателю. В тех же клетках в правом верхнем углу указано расстояние перевозки между пунктами в километрах. Например, расстояние от А до первого пункта получателя равно одному километру, до второго — три километра. Общее количество груза в тоннах, подлежащего отправке из каждого пункта, а также доставка в каждое место получателя указаны в итоговых клетках таблицы.

Математическая формулировка задачи: требуется минимизировать общий пробег груза т×км, т.е. сумму произведений каждого количества перевозимого груза на расстояние перевозки: x₁₁+3x₁₂+4x₁₃+2x₂₁+5x₂₂+3x₂₃+6x₃₁+7x₃₂+5x₃₃→min.

Ограничение данной задачи связано с тем, что из каждого пункта отправляется и в каждый пункт доставляется строго определенное количество груза. Например, из А можно отправлять груз трем получателям, но общее количество отправляемого груза должно составлять 12 тонн, т.е. x₁₁+x₁₂+x₁₃=12тонн А; x₂₁+x₂₂+x₂₃=8тонн Б; x₃₁+x₃₂+x₃₃=10тонн В.

Таблица 22

С другой стороны, в первый пункт назначения может поступать груз из трех различных мест отправки, но в определенном общем количестве 6 тонн, т.е. x₁₁+x₂₁+x₃₁=6, x₁₂+x₂₂+x₃₂=9; x₁₃+x₂₃+x₃₃=15. Эти шесть уравнений ограничивают условия транспортной задачи. Для решения задач необходимо воспользоваться распределительным методом, при котором общий принцип расчета аналогичен расчету при применении симплексного метода: в начале применяется исходный вариант перевозок, а затем последовательно применяются его улучшения до получения оптимальной программы. Для составления первоначального исходного плана перевозок удобно пользоваться так называемым приемом северо-западного угла. Этот прием заключается в том, что вначале максимально допустимое количество груза помещают в левую верхнюю клетку таблицы. Затем заполняется средняя клетка в строку или в столбец в зависимости от того, где имеются еще неиспользованные возможности перевозок. Таким же образом производится дальнейшее заполнение клеток до распределения всего количества груза. При этом количество заполняемых клеток составляет(n+m–1), где n — количество получателей, m — поставщиков.

Таблица 23

Заполнение таблицы начинается с левого верхнего угла. Первая клетка показывает количество груза, перевозимого из пункта А в первый пункт назначения, максимальное число — 6тонн. Затем переходим к следующей клетке в ней тоже 6 тонн, так как в А всего 12 тонн, а 6 тонн уже использовано. Заполнив две клетки, мы использовали полностью возможность отправителя А. При этом, во второй пункт будет доставлено 6тонн вместо 9тонн. Недостающие 3тонны могут поступать из следующего пункта Б . Поставим в клетке на линии строки Б и столбца 2 цифру 3 и затем перейдем к соседней клетке второй строки. В ней поставим 5тонн, и возможности отправления Б будут исчерпаны. Теперь остается перейти к правой нижней клетке и заполнить ее цифрой 10. Итак, составлена первоначальная программа перевозок.

Полученный вариант возможно и не оптимален, но он удовлетворяет всем ограничениям задачи. Общий пробег грузов при этом варианте составляет: 6т×1км+6×3+3×5+5×3+10×5=104(т×км).

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

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

1. Поставить в вершинах квадрата расстояния перевозок, обозначенные в клетках, причем, первой цифре для свободной клетки дать положительный знак, следующей цифре — отрицательный, третьей — «+» и т.д. Получим схему А3:

–3 +4

+5 –3

Определим сумму вершин: –3+4–3+5=3.

2. Для клетки на линии Б1:

–1 +3

+2 –5

S вершин = –1+3–5+2=1.

3. Для В1 =6–1+3–5+3–5=1

–1 +3

+6 –5

4. Для В2 S=7–5+3–5=0

–5 +3

7 –5

Экономическое значение алгебраических величин у вершин общих многоугольников, полученных для свободных клеток: А2=3; Б1=–1; В1=1; В2=0. Начнем с клетки А3. Если эту клетку с расстоянием перевозки 4км включить в программу и предусмотреть перевозку в этом направлении хотя бы 1тонны груза, то для сохранения общего равновесия программы придется уменьшить на одну тонну перевозки в двух примыкающих клетках (А2 и Б3) с расстояниями по 3км, и увеличить на одну тонну объем перевозок в клетке Б2 с расстоянием транспортировки 5км. Эта операция, если вести исчисления в тоннокилометрах, явно невыгодна, так как мы уменьшаем загрузку двух клеток с малыми расстояниями перевозки за счет увеличения загрузки других клеток с увеличением ее дальнейших расстояний. Алгебраическая сумма показывает, что при включении в данную незанятую клетку каждой тонны груза, увеличивается общая величина пробега груза на 3т×км — результат В1 говорит о том, что включение этой клетки в программу приводит к увеличению общего пробега на 1т×км, в расчете на каждую данную тонну груза. Для В2 — «0» безразлично, для Б1 — «–1» — этот результат говорит о том, что программу можно улучшить, так как это приведет к уменьшению на 1т×км.

В итоге второго этапа расчета установлено, что исходный вариант является оптимальным и может быть улучшен. Известно также в каком направлении нужно его улучшать. Третий этап — это улучшение исходной программы. Для этой цели используем многоугольник Б1А1А2Б2. В свободную клетку переносится меньшее из чисел, стоящее в клетке с отрицательным знаком. А в данном случае, это число 3 (Б2). Поместив эту цифру, в незанятую клетку, нужно одновременно прибавить его к числу со знаком»+» и отнять из отрицательной величины (в условии итоги по строкам и столбцам не нарушаются). После этого получаем новый вариант программы (таблица 24).

Таблица 24

Алгоритм модифицированного распределительного метода решений транспортной задачи.

1. В таблицу задачи вводятся дополнительно строка и столбец модифицированного распределительного метода (МРМ), клетки которых используются для нахождения специальных оценок (косвенных стоимостей) U_i и V_j, где индекс i соответствует номеру строки, а столбцы обозначим через V_j, где индекс j соответствует номеру столбца.

2. Первое опорное решение составляется методом северо-западного угла или методом наименьшего элемента в матрице и т.п.

3. Для проверки оптимальности полученного опорного плана используется матрица тарифов С_ij. Составляется система из m+n–1 уравнений с m+n неизвестными вида U_i+V_j=C_ij, где C_ij — коэффициенты матрицы тарифов (стоимость), соответствующие занятым клеткам опорного плана, исследуемого на оптимальность.

Рассмотрим какое-либо ее конкретное решение, для чего одной из оценок придаем произвольное числовое значение. Пусть, например, U₁=0. В этом случае остальные оценки U₂, U₃,..., U_m и V₁, V₂,…, V_n в системе уравнений будут определены однозначно.

Итак, оценки матрицы косвенных стоимостей U_i и V_j вычисляются только по занятым клеткам по формуле:

U_i+V_j=C_ij,

причем одной из оценок в начале расчета придается произвольное числовое значение, например, U₁=0.

4. Анализируется признак оптимальности МРМ. Если обозначить через Z_ij оценку свободной клетки, находящейся на пересечении строки с номером i и столбца с номером j, то вычисления производятся по следующей формуле:

Z_ij=(U_i+V_j) – C_ij.

Если для всех свободных клеток оценки Z_ij£0, то полученный опорный план оптимален при решении задач на min.

В случае выполнения признака оптимальности задача решена. Если же хотя бы одна из оценок свободных клеток Z_ij>0, то признак оптимальности не выполняется и исходное опорное решение подлежит улучшению.

5. Для перехода к новому базисному решению находится свободная клетка с наименьшей положительной оценкой, для задач на минимум и с отрицательной оценкой наибольшей по абсолютной величине для задач на максимум. Если таких клеток несколько, то лучше выбрать ту из них, у которой тариф С_ij является наименьшим. Для этой клетки строят прямоугольный контур, то есть замкнутый многоугольник, состоящий из горизонтальных и вертикальных прямых отрезков, одной из вершин которого является свободная клетка, а остальные вершины расположены в занятых клетках. Отрезки контура могут проходить через занятые клетки, которые не являются вершинами многоугольника, но в каждом контуре рассматриваются только его вершины. Для перераспределения поставок по анализируемому контору в свободную клетку записывается поставка +q, а в остальных клетках, принадлежащих вершинам контура, знаки +–q чередуются. Так как в любом прямоугольном замкнутом контуре число вершин всегда четное, то расстановка знаков у q не зависит от выбора направления, то есть эти знаки можно чередовать как по часовой, так и против часовой стрелки. Вершины контура, в которых поставка при перераспределении грузов увеличивается (+q), будем называть положительными, а в которых объем грузов уменьшается (–q) отрицательными.

Из объема поставок, которые в клетках контура с отрицательными вершинами, выбирается наименьшее число q, которое прибавляется к поставкам, стоящим в клетках с положительными вершинами, и вычитается из клеток контура с отрицательными вершинами.

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

Признак оптимальности при решении задач максимизации. Оценки свободных клеток Z_ij=(U_i+V_j)–C_ij должны быть ³ 0.

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

Контрольные вопросы и упражнения

1. Какие соотношения между количеством груза у поставщиков и потребностью в этом грузе у потребителей могут возникнуть при постановке конкретной задачи перевозки грузов?

2. При каком условии транспортная задача будет иметь решение?

3. Постройте исходные планы для транспортной задачи, данные которой приведены в таблице 25, рассмотренными выше методами. Сравните значения целевых функций для исходных планов, полученных разными методами.

4. Какое количество заполненных клеток должно содержаться в таблице транспортной задачи при её решении?

5. В каком случае базисный план транспортной задачи является оптимальным?

6. Как строится цикл?

7. Для решения каких экономических задач применяется модель транспортной задачи?