Решение транспортной задачи

Чтобы применить к решению транспортной задачи симплекс-метод, переобозначим неизвестные так:

x₁, х₂, х₃, х₄ – количество тонн бетона, которое вывозится с первого бетонного завода соответственно на 1, 2, 3 и 4-ю строительные площадки;

x₅, х₆, х₇, x₈ – количество тонн бетона, вывозимого со второго бетонного завода соответственно на 1, 2, 3 и 4-ю строительные площадки. Зададимся конкретными значениями стоимости перевозки одной тонны бетона с соответствующих заводов на строительные площадки (в определенных денежных единицах).

Все данные сведем в таблицу 12.

Таблица 12 – Транспортная задача

Тогда функция цели (стоимость всех перевозок) и система ограничений примут вид

f = 2x₁ + x₂ + 3x₃ + 2x₄ + 2x₅ + 3x₆ + 3x₇ + x₈

x₁ + x₂ + x₃ + x₄ = 400

x₅ + x₆ + x₇ + x₈ = 560

x₁ + x₂ = 220 (5.18)

x₂ + x₆ = 200

x₃ + x₇ = 180

x₄ + x₈ = 360

Выпишем матрицу системы ограничений

(5.19)

Теперь нужно найти ранг этой матрицы. Если первые две строки матрицы поменять местами, то можно получить неравный нулю определитель

(5.20)

Следовательно, ранг матрицы системы ограничений r = 5 (не равен нулю определитель пятого порядка, а все определители большего порядка равны нулю).

Значит, пять неизвестных будут базисными, а три – свободными. Обозначим их так:

x₁, х₂, х₃ - свободные неизвестные;

х₄, х₅, х₆, х₇, x₈ – базисные неизвестные.

Из системы ограничений (5.18) выражаем базисные неизвестные:

х₄ = 400 –х₁ – х₂ – х₃

х₅ = 220 – х₁

х₆ = 200 – х₂ (5.21)

х₇ = 180 – х₃

х₈ = - 40 + х₁ + х₂ + х₃

Если все свободные неизвестные принять равными нулю, то х₈ = -40 < 0. Следовательно, опорный план не найден. Нужно неизвестную х перевести в базисные неизвестные, а х₈ – в свободные.

Тогда из (5.21) получим выражение новых базисных неизвестных через свободные:

x₁ = 40 –х₂ – х₃ + х₈

х₄ = 360 –х₈

х₅ = 180 + х₂ + х₃ – х₈ (5.22)

х₆ = 200 – х₂

х₇= 180-х₃

Теперь при равных нулю свободных неизвестных все базисные неизвестные положительны. Следовательно, план (40, 0, 0, 360, 180, 200, 180, 0) является опорным.

Запишем функцию цели (5.18) в базисной форме:

(5.23)

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

Наибольший по модулю отрицательный коэффициент в (5.23) стоит перед х₂, поэтому эту неизвестную переведем из свободных в базисные, а неизвестную х₁, переведем из базисных в свободные. Тогда система ограничений (5.22) примет вид

х₂ = 40 – х₁ – х₃ + х₈

х₄ = 360 – х₈

х₅ = 220-х₁ (5.24)

x₆=160 + х₁ + х₃ – х₈

х₇ = 180-х₃

Запишем новый опорный план (0, 40, 0, 360, 220, 160, 180, 0). Функция цели (5.23) также изменится и примет вид

(5.25)

Опять найденный опорный план не является оптимальным, так как в функции цели (5.25) перед х₈ стоит отрицательный коэффициент. Значит, неизвестную х₈ нужно перевести из свободных в базисные. При этом базисная неизвестная x₆ перейдет в свободные.

Система ограничений теперь примет вид

x₂=200-x₆

x₄=200-x₁-x₃+x₆

x₅=220-x₁ (5.26)

x₇=180-x₃

x₈=160+x₁+x₃-x₆

Новый опорный план будет (0, 200, 0, 200, 220, 0, 180, 160), а функция цели

(5.27)

И опять найденный опорный план не будет оптимальным, так как перед некоторыми неизвестными в функции цели (5.27) стоит отрицательный коэффициент.

Переведем неизвестную х₁ из свободных в базисные, тогда базисная неизвестная x₄ перейдет в свободные.

Теперь система ограничений (5.26) примет вид

x₁=200-x₃-x₄+x₆

x₂=200-x₆

x₅=20+x₃+x₄-x₆ (5.28)

x₇=180-x₃

x₈=160-x₄

Опорный план будет таким (200, 200, 0, 0, 20, 0, 180, 360), а функция цели

(5.29)

Так как все коэффициенты при неизвестных в функции цели (5.29) неотрицательны, то найденный опорный план (5.28) будет оптимальным.

Следовательно, чтобы стоимость всех перевозок бетона была минимальной, с первого бетонного завода нужно вывести на первую строительную площадку 200 т, на вторую – тоже 200 т. На третью и четвертую бетон не завозить. Со второго бетонного завода на первую строительную площадку вывести 20 т, на третью - 180т, на четвертую – 360 т, а на вторую площадку бетон не завозить. Стоимость всех перевозок при таком плане будет составлять 1540 соответствующих единиц.