Исследование очередного решения на оптимальность

Пример № 1

На трех базах находится однородный груз. На базе А₁ в количестве 300 т., на базе А₂ в количестве 150 т., на базе А₃ в количестве 50 т. Весь этот груз необходимо развести четырем заказчикам так, чтобы стоимость перевозок была наименьшей. Заказчику в пункте В₁ должно поступить 170 т., в пункте В₂ – 110 т., в пункте В₃ – 100 т., в пункте В₄ – 120 т. Расстояния между базами и пунктами назначения приведены в таблице 1 в угловых скобках.

Таблица 1

Базы	Заказчики	Запасы на базах
В1	В2	В3	В4
А1				—	300 т.
А2	—	—			150 т.
А3	—	—	—		50 т.
Потребности заказчика	170 т.	110 т.	100 т.	120 т.	500 т. 500 т.

Решение

1. Описание транспортной задачи как задачи линейного программирования

Пусть из i-ой базы (i = ) j-му заказчику (j = ) доставлено х_ij тонн груза. От j-го заказчика i-я база находится на известном расстоянии с_ij (км), указанном в таблице 1 в угловой скобке. В этом случае х_іjс_іj есть количество тонно-километров необходимое для такой перевозки. Рассматривая в произведениях х_іjс_іj всевозможные комбинации значений индексов i и j, получим для каждой такой комбинации свое значение тонно-километров. Из суммы этих произведений образуется общая стоимость перевозок F, выраженная в тонно-километрах

. (1)

Требуется найти такой план перевозок (х₁₁, х₁₂,…, х₃₄), который минимизирует его стоимость. Этот план перевозок называется оптимальным.

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

Покажем, что транспортная задача есть частный случай задачи линейного программирования. Действительно, целевая функция F в ней это линейная функция вида (1) относительно определяемых переменных х_іj. Линейной является и система ограничений, на которой требуется найти минимум функции F. Так в примере №1 система ограничений представлена уравнениями

х₁₁ + х₁₂ + х₁₃ + х₁₄ = 300,

х₂₁ + х₂₂ + х₂₃ + х₂₄ = 150,

х₃₁ + х₃₂ + х₃₃ + х₃₄ = 50,

х₁₁ + х₂₁ + х₃₁ = 170,

х₁₂ + х₂₂ + х₃₂ = 110,

х₁₃ + х₂₃ + х₃₃ = 100,

х₁₄ + х₂₄+ х₃₄ = 120.

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

Примечание.Часто с_ij означают не расстояния между базами и заказчиками, а стои-мость перевозки одной тонны груза между ними. Очевидно, что эта стоимость пропорциональна расстоянию. Поэтому, если х_іj – количество тонн груза, перевозимого из i-ой базы j-му заказчику, то функция (1) означает в этом случае стоимость всех перевозок, выраженную не в тонно-километрах, а в рублях.

2. Формирование опорного решения (опорного плана перевозок) методом северо-западного угла

При формировании опорного плана методом северо-западного угла, заполняется левая верхняя клетка (северо-западный угол) исходной таблицы или её оставшейся части. После заполнения северо-западного угла с учетом предельных возможностей базы, лежащей с заполняемой клеткой в одной строке, из таблицы исключается или очередной столбец слева, или очередная строка сверху. Так в данной таблице потребность заказчика В₁ может быть полностью удовлетворена базой А₁ (а₁ = 300; в₁ = 170; а₁ > в₁). Полагая х₁₁=170, вписываем это значение в клетку (1;1) и исключаем из рассмотрения первый столбец.

На базе А₁ остается 130 т. груза ( ). В новой таблице с тремя строками А₁, А₂, А₃ и тремя столбцами В₂, В₃, В₄ северо-западным углом оказывается клетка (1;2). Первая база с оставшимися 130 т. груза может полностью удовлетворить потребность второго заказчика В₂ ( > в₂). Полагая х₁₂ = 110, вписываем это значение в клет-ку (1; 2) и исключаем из рассмотрения второй столбец. На базе А₁ остается 20 т. груза ( ).

В новой таблице с тремя строками А₁, А₂, А₃ и двумя столбцами В₃, В₄ северо-западный угол соответствует клетке (1;3). Теперь третий заказчик

В₃ может принять весь запас с базы А₁ ( < в₃ ). Полагая

х₁₃ = 20, вписываем это значение в клетку (1;3) и исключаем из рассмотрения первую строку. Но потребность заказчика В₃ оказалась не удовлетворенной ( ). Эту потребность может удовлетворить база А₂. После чего в ней останется (т. груза). Записывая в клетку (2;3) х₂₃ = 80 мы полностью удовлетворяем потребность заказчика В₃ и вычеркиваем третий столбец. Теперь на северо-западе находится клетка (2;4) и потребность заказчика В₄ будет частично удовлетворяться остатками груза с базы А₂. Таким образом,

х₂₄ = 70, что приводит к исключению второй строки в таблице 1. А не вполне удовлетворенная потребность заказчика В₄ ( ) удовлетворяется запасами груза с базы А₃. При этом х₃₄ = 50.

Опорный план составлен. Ошибки в его составлении можно обнаружить, если найти суммы указанных значений х_іj по строкам и сравнивать их на равно с запасами груза на базах. Суммы х_іj по столбцам сравниваются на равно с потребностями заказчиков.

3. Циклы пересчета в таблице перевозок

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

Циклом пересчета в таблице перевозок называется последовательность переменных х_іj, удовлетворяющих следующим условиям:

1) в каждый цикл может входить только одно свободное переменное (пустая клетка – клетка с прочерком). Все остальные переменные должны быть базисными (заполненные клетки);

2) каждые две последовательные переменные, входящие в цикл, могут находиться только на одной строке или только в одном столбце;

3) каждая строка или столбец данного цикла может содержать только две переменные;

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

Если для свободной клетки исходной таблицы, заполненной методом северо-западного угла, можно построить цикл пересчета, то такой цикл является единственным. Число вершин в этом цикле чётно. Если же для какой-либо свободной клетки исходной таблицы цикл пересчета построить нельзя, то для реализации этой возможности некоторые из свободных переменных обращаются в базисные переменные с нулевыми значениями (в пустых клетках записываются нули. См. пример № 2). Решение, содержащее нулевые значения базисных переменных, называется вырожденным.

Укажем циклы пересчета для всех свободных клеток таблицы 1 и пере-распределение груза в них по следующим правилам:

а) снабдим свободную клетку знаком (+) и с каждым переходом к следую-щей клетке цикла будем изменять знак на противоположный;

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

Циклы пересчета в примере №1:

1)

F = 70·170 + 50·110 + 80·20 + 40·100 + 60·50 + 11·50 = 26 550 (т.км.);

2)

F = 70 · 90 + 50 · 110 + 15 · 100 + 80 · 80 + 60 · 70 + 11 · 50= 24 450 (т.км.);

3)

F = 70 · 170 + 50 ·30 + 15 ·100 + 80 · 90 + 60 · 70 + 11 · 50 = 26 850 (т.км.);

4)

F = 70 ·120 + 50 ·110 + 15 ·70 + 40 ·30 + 60 ·120 + 50 · 50 = 25 850 (т.км.);

5)

F = 70 · 170 + 50 · 60 + 15 · 70 + 40 ·30 + 60 ·120 + 10 · 50 = 24 850 (т.км.);

6)

F = 70 ·170 + 50 ·110 + 15 · 20 + 40 · 30 + 60 ·120 + 90 ·50 = 30 600 (т.км.);

Следует сравнить стоимость перевозок в каждом цикле со стоимостью перевозок по опорному (первоначальному) плану

F_нач = 70·170 + 50·110 + 15·20 + 40·80 + 60·70 + 11·50 = 25650 (т.км.)

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

Таблица 2

Базы

Заказчики Запасы на базах В₁ В₂ В₃ В₄ А₁ ―   300 т. А₂ ― ―   150 т. А₃ ― ― ―   50 т. Потребности заказчика   170 т.   110 т.   100 т.   120 т. 500 т. 500 т.

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

4. Критерий оптимальности решения транспортной задачи

Величины с_ij в клетках таблицы 1, таблицы 2 и последующих таблицах означают или расстояния между i–ой базой и j-ым заказчиком, или стоимость перевозки одной единицы груза между ними. Эти величины в общем случае называются тарифами.

Изменение стоимости перевозок в каждом из шести вышерассмотренных вариантов связано с изменением количества груза в вершинах циклов. Пусть это количество изменяется на m (фиксированное число цикла) т. в соответствии со знаком вершины. (Если вершина снабжена знаком (+), то это количество груза на m т. увеличивается; (-) - на m т. уменьшается.) Тогда в первом варианте стоимость перевозок изменится на

m · с₁₄ – m · с₁₃ + m · с₂₃ – m · с₂₄ = (с₁₄ – с₁₃ + с₂₃ – с₂₄) · m =

= (80 – 15 + 40 – 60) · 20 = 45 · 20 = 900 = 26 550 – 25 650 (т.км.).

То есть, в первом варианте стоимость перевозок 26 550 т.км. больше по сравнению с предыдущим (опорным) решением 25 650 т. км. на 900 т.км.

Во втором варианте изменение составит

m · с₂₁ – m · с₂₃ + m · с₁₃ – m · с₁₁ = (с₂₁ – с₂₃ + с₁₃ – с₁₁) · m =

= (80 – 40 + 15 – 70) · 80 = –15 · 80 = – 1200 = 24 450 – 25 650 (т.км).

То есть, во втором варианте стоимость перевозок уменьшается на 1200 т.км.

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

с₂₂ – с₂₃ + с₁₃ – с₁₂ = 90 – 40 + 15 – 50 = 15 > 0.

Таким образом, в третьем варианте стоимость перевозок увеличивается по сравнению с предыдущим (опорным) решением. Следовательно, этот вариант интереса не представляет. В четвертом

с₃₁ – с₃₄ + с₂₄ – с₂₃ + с₁₃ – с₁₁ = 50 – 11 + 60 – 40 + 15 – 70 = 4 > 0.

и шестом вариантах

с₃₃ – с₃₄ + с₂₄ – с₂₃ = 90 – 11 + 60 – 40 = 150 – 51 = 99 > 0.

мы приходим к тому же выводу. И только для пятого варианта алгебраическая сумма тарифов

с₃₂ – с₃₄ + с₂₄ – с₂₃+ с₁₃ – с₁₂ =10 – 11 + 60 – 40 +15 – 50 = 85 – 101 = –16 < 0,

что говорит о том, что стоимость перевозок будет уменьшаться на m ·16 т.км., где m = 50т. Таким образом, стоимость перевозок по 5-му варианту уменьшиться на 800 = 25 650 – 24 850 (т.км.).

Однако, есть лучший вариант – второй, в котором стоимость перевозок уменьшается на 1200 т.км. Этот вариант и принимается в качестве следующего решения, зафиксированного в таблице 2.

Становится очевидным и критерий оптимальности очередного решения:

Очередное решение определяет оптимальный план перевозок, если алгебраические суммы тарифов для всех возможных циклов пересчета больше или равны нулю или в наилучшем цикле пересчета при отрицательном значении алгебраической суммы тарифов количество перевозимого груза равно нулю (см. пример №2).

5. Метод потенциалов

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

В рассматриваемой таблице каждый тариф с_ij в клетке с базисным переменным представляется в виде суммы с_ij = . Тогда для опорного плана, полученного в примере №1 методом северо-западного угла, образуется система уравнений

= с₁₁ = 70,

= с₁₂ = 50,

= с₁₃ = 15,

= с₂₃ = 40,

= с₂₄ = 60,

= с₃₄ = 11.

Если цикл пересчета можно построить для любой свободной клетки исходной таблицы, то число уравнений, в системе всегда будет на единицу меньше числа неизвестных. При этом значение одного из данных неизвестных можно выбирать произвольно. Например, можно принять, что α₁ = 0. Тогда решение системы примет вид

α₁ = 0, β₁ = 70,

α₂ = 25, β₂ = 50,

α₃ = – 24, β₃ = 15,

β₄ = 35.

Полученные значения α_i называют потенциалами соответствующих баз,

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

щую первому циклу пересчета для свободной клетки (1,4) в таблице 1.

s₁₄ = c₁₄ – c₁₃ + c₂₃ – c₂₄ = c₁₄ – (α₁ + β₃) + (α₂ + β₃) – (α₂ + β₄) =

= c₁₄ – α₁ – β₃+ α₂+ β₃– α₂– β₄= c₁₄ – (α₁ + β₄).

Сумму α_i + β_j принято называть косвенным тарифом свободной клетки (i, j) и обозначать как c¢_ij. Тогда алгебраическая сумма тарифов для данной свободной клетки представится разностью истинного и косвенного тарифов. В частности

s₁₄ = c₁₄ – c'₁₄= 80 – (0 + 35) = 45.

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

s₂₁ = c₂₁ – c'₂₁ = с₂₁ – (α₂ + β₁) = 80 – (25 + 70) = - 15,

s₂₂ = c₂₂ – c'₂₂ = с₂₂ – (α₂ + β₂) = 90 – (25 + 50) = 15,

s₃₁ = c₃₁ – c'₃₁ = с₃₁ – (α₃ + β₁) = 50 – (–24 + 70) = 4,

s₃₂ = c₃₂ – c'₃₂ = с₃₂ – (α₃ + β₂) = 10 – (–24 + 50) = - 16,

s₃₃ = c₃₃ – c'₃₃ = с₃₃ – (α₃ + β₃) = 90 – (–24 + 15) = 99.

(Сравните полученные результаты с предыдущими.)

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

При этом стоимость перевозок уменьшится на

(т.км.).

А для клетки (3;2) имеем

При этом стоимость перевозок уменьшится на

(т.км.).

Принимается наибольшее уменьшение стоимости перевозок, соответствующее циклу пересчета со свободной клеткой (2;1), что и приводит нас к таблице 2.

Исследование очередного решения на оптимальность

С помощью метода потенциалов, уменьшающего объём вычислений, легко определить, является ли полученное решение оптимальным. Так для определе-ния оптимальности решения, представленного таблицей 2, каждый тариф с_ij, находящийся в одной клетке с базисной переменной, выражается в виде суммы потенциалов соответствующей базы α_iи заказчика β_j. Тогда для найденного плана перевозок образуется система уравнений

с₁₁ = α₁ + β₁ = 70,

с₁₂ = α₁ + β₂ = 50,

с₁₃ = α₁ + β₃ = 15,

с₂₁ = α₂ + β₁ = 80,

с₂₄ = α₂ + β₄ = 60,

с₃₄ = α₃ + β₄ = 11.

Если α₁ = 0, то β₁ = 70,

α₂ = 10, β₂ = 50,

α₃ = – 39, β₃ = 15,

β₄ = 50.

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

s₁₄ = c₁₄ – c'₁₄ = c₁₄ – (α₁ + β₄) = 80 – 50 = 30,

s₂₂ = c₂₂ – c'₂₂ = c₂₂ – (α₂ + β₂) = 90 – (10 + 50) = 30,

s₂₃ = c₂₃ – c'₂₃ = c₂₃ – (α₂ + β₃) = 40 – (10 + 15) = 15,

s₃₁ = c₃₁ – c'₃₁ = c₃₁ – (α₃ + β₁) = 50 – (–39 + 70) = 19,

s₃₂ = c₃₂ – c'₃₂ = c₃₂ – (α₃ + β₂) = 10 – (–39 + 50) = –1,

s₃₃ = c₃₃ – c'₃₃ = c₃₃ – (α₃ + β₃) = 90 – (–39 + 15) = 114.

Вычисления показывают, что план перевозок, соответствующий последнему решению, представленному в таблице 2, можно улучшить, производя цикл пересчёта со свободной клеткой (3;2):

Таблица 3

Базы

Заказчики Запасы на базах В₁ В₂ В₃ В₄ А₁ –   300 т. А₂ – –   150 т. А₃ – – –   50 т. Потребности заказчика   170 т.   110 т.   100 т.   120 т. 500 т. 500 т.

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

с₁₁ = α₁ + β₁= 70, с₂₁ = α₂ + β₁= 80,

с₁₂ = α₁ + β₂= 50, и с₂₄ = α₂ + β₄= 60,

с₁₃ = α₁ + β₃= 15 с₃₂ = α₃ + β₂= 10.

Тогда, если α₁ = 0, то β₁= 70,

α₂ = 10, β₂= 50,

α₃ = – 40, β₃= 15,

β₄= 50.