Итак, имеем

Wj = 0, ы2 = 5, u3 - 3,

v, = 10, v2 = 2, v3 = 4, v4= 15.

Далее, используя найденные значения потенциалов, для каждой небазисной переменной вычисляются величины ul + vt - с,. Результаты вычисления этих величин приведены в следующей таблице.

Небазисные переменные

Значения и, + i/y - с,у

Х13 *14 *21 *31 *32 *33

Щ + 1/з - Ci3 = 0 + 4 - 20 = -16 Ul + 1/4 - С14 = 0 + 15- 11 = 4 и2 + 1/1 - с21 = 5 + 10- 12 = 3 из + 1/1 - с31 = 3 + 10 - 4 = 9 иъ + 1/2 - с32 = 3 + 2 - 14 = -9 и3 + 1/3 - Сзз = 3 + 4 - 16 = -9

Вычисленные значения совместно с нулевыми значениями для базисных переменных (поскольку ut + v - ctj = 0 для любой базисной переменной х ) фактически являются коэффициентами z-строки симплекс-таблицы.

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

Описанные вычисления обычно выполняются непосредственно в транспортной таблице, как показано в табл. 5.22. В этом случае нет необходимости в явном виде выписывать уравнения для потенциалов. Вычисления в транспортной таблице начинаются с присвоения потенциалу их нулевого значения: их = 0. Затем вычисляются v-потенциалы для всех столбцов, имеющих базисные переменные в первой строке. Далее на основании уравнения для потенциалов, соответствующего переменной jc22, определяется величина потенциала и2. Зная значение потенциала и2, вычисляем потенциалы v3 и v4, что позволяет найти потенциал и3. Поскольку все потенциалы определены, далее вычисляются величины ut + vs - ctj для каждой небазисной переменной х . Эти величины показаны в табл. 5.22 в левом нижнем углу ячеек транспортной таблицы.

5.3. Решение транспортной задачи Таблица 5.22

V! = 10

1/2 = 2

1/з = 4

i/4 = 15 Предложение

1/1 = 0

и2 = 5

из = 3 Спрос

Определив вводимую в базис переменную х31, далее следует найти исключаемую из базиса переменную. Напомним, если какая-либо переменная вводится в базис, одна из текущих базисных переменных должна стать небазисной (и равной нулю), чтобы количество базисных переменных оставалось постоянным (в данном примере количество базисных переменных равняется 3 + 4-1 = 6).

Исключаемая из базиса переменная определяется следующим образом. Выбрав в качестве вводимой переменную х31, мы хотим, чтобы перевозки по маршруту, соответствующему этой переменной, уменьшили общую стоимость перевозок. Какой объем груза можно перевезти по этому маршруту? Обозначим через 0 количество груза, перевозимого по маршруту (3, 1) (т.е. х31 = 0). Максимально возможное значение 9 определяем из следующих условий.

1. Должны выполняться ограничения на спрос и предложение.

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

Эти условия позволяют найти значение 0 и определить исключаемую переменную. Сначала построим замкнутый цикл, который начинается и заканчивается в ячейке, соответствующей вводимой переменной (в данном примере - это ячейка (3, 1)). Цикл состоит из последовательности горизонтальных и вертикальных отрезков (но не диагональных), соединяющих ячейки, соответствующие текущим базисным переменным, и ячейку, соответствующую вводимой переменной. В табл. 5.23 показан цикл для вводимой переменной х31. Для любой вводимой переменной можно построить только один замкнутый цикл.

Теперь найдем значение 0. Для того чтобы удовлетворить ограничениям по спросу и предложению, надо поочередно отнимать и прибавлять 0 к значениям базисных переменных, расположенных в угловых ячейках цикла, как показано в табл. 5.23 (не имеет значения направление обхода цикла: по часовой стрелке или против). Новые значения базисных переменных останутся неотрицательными, если будут выполняться следующие неравенства.

хп = 5-0>0, х22 = 5-0>0, х, = 10-0>0.

Таблица 5.23

Vj = 10 v2 = 2 v3 = 4 v4 = 15 Предложение

Спрос

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

Определив значение для вводимой переменной (х31 = 5) и выбрав исключаемую переменную, далее следует откорректировать значения базисных переменных, соответствующих угловым ячейкам замкнутого цикла, как показано в табл. 5.24. Поскольку перевозка единицы груза по маршруту (3, 1) уменьшает общую стоимость перевозок на 9 долл. (= м3 + v, - с31), суммарная стоимость перевозок будет на 9x5 = 45 долл. меньше, чем в предыдущем решении. Таким образом, новая суммарная стоимость перевозок будет равна 520 - 45 = 475 долл.

Имея новое базисное решение, следует повторить вычисления потенциалов, как показано в табл. 5.24. Новой вводимой в базис переменной будет хи. Замкнутый цикл, соответствующий этой переменной, позволяет найти ее значение (л,4 = 10) и исключаемую переменную л24.

Новое решение, показанное в табл. 5.25, на 4 х 10 = 40 долл. уменьшает значение целевой функции. Таким образом, новая суммарная стоимость перевозок составляет 475 - 40 = 435 долл. Теперь новые значения величин и, + vf - сц для всех небазисных переменных х. отрицательные. Поэтому решение, представленное в табл. 5.25, оптимально.

Таблица 5.24

v, = 1 v2 = 2 v3 = 4 v4=15 Предложение

и, = 0

щ = 5

СпР0С 5 15 15 15