![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Решение транспортной задачи
Чтобы применить к решению транспортной задачи симплекс-метод, переобозначим неизвестные так: x1, х2, х3, х4 – количество тонн бетона, которое вывозится с первого бетонного завода соответственно на 1, 2, 3 и 4-ю строительные площадки; x5, х6, х7, x8 – количество тонн бетона, вывозимого со второго бетонного завода соответственно на 1, 2, 3 и 4-ю строительные площадки. Зададимся конкретными значениями стоимости перевозки одной тонны бетона с соответствующих заводов на строительные площадки (в определенных денежных единицах). Все данные сведем в таблицу 12.
Таблица 12 – Транспортная задача
Тогда функция цели (стоимость всех перевозок) и система ограничений примут вид
f = 2x1 + x2 + 3x3 + 2x4 + 2x5 + 3x6 + 3x7 + x8 x1 + x2 + x3 + x4 = 400 x5 + x6 + x7 + x8 = 560 x1 + x2 = 220 (5.18) x2 + x6 = 200 x3 + x7 = 180 x4 + x8 = 360
Выпишем матрицу системы ограничений
Теперь нужно найти ранг этой матрицы. Если первые две строки матрицы поменять местами, то можно получить неравный нулю определитель
Следовательно, ранг матрицы системы ограничений r = 5 (не равен нулю определитель пятого порядка, а все определители большего порядка равны нулю). Значит, пять неизвестных будут базисными, а три – свободными. Обозначим их так: x1, х2, х3 - свободные неизвестные; х4, х5, х6, х7, x8 – базисные неизвестные. Из системы ограничений (5.18) выражаем базисные неизвестные:
х4 = 400 –х1 – х2 – х3 х5 = 220 – х1 х6 = 200 – х2 (5.21) х7 = 180 – х3 х8 = - 40 + х1 + х2 + х3
Если все свободные неизвестные принять равными нулю, то х8 = -40 < 0. Следовательно, опорный план не найден. Нужно неизвестную х перевести в базисные неизвестные, а х8 – в свободные. Тогда из (5.21) получим выражение новых базисных неизвестных через свободные:
x1 = 40 –х2 – х3 + х8 х4 = 360 –х8 х5 = 180 + х2 + х3 – х8 (5.22) х6 = 200 – х2 х7= 180-х3
Теперь при равных нулю свободных неизвестных все базисные неизвестные положительны. Следовательно, план (40, 0, 0, 360, 180, 200, 180, 0) является опорным. Запишем функцию цели (5.18) в базисной форме:
Так как некоторые коэффициенты при неизвестных в функции цели отрицательны, то найденный опорный план не является оптимальным. Наибольший по модулю отрицательный коэффициент в (5.23) стоит перед х2, поэтому эту неизвестную переведем из свободных в базисные, а неизвестную х1, переведем из базисных в свободные. Тогда система ограничений (5.22) примет вид х2 = 40 – х1 – х3 + х8 х4 = 360 – х8 х5 = 220-х1 (5.24) x6=160 + х1 + х3 – х8 х7 = 180-х3 Запишем новый опорный план (0, 40, 0, 360, 220, 160, 180, 0). Функция цели (5.23) также изменится и примет вид
Опять найденный опорный план не является оптимальным, так как в функции цели (5.25) перед х8 стоит отрицательный коэффициент. Значит, неизвестную х8 нужно перевести из свободных в базисные. При этом базисная неизвестная x6 перейдет в свободные. Система ограничений теперь примет вид
x2=200-x6 x4=200-x1-x3+x6 x5=220-x1 (5.26) x7=180-x3 x8=160+x1+x3-x6
Новый опорный план будет (0, 200, 0, 200, 220, 0, 180, 160), а функция цели
И опять найденный опорный план не будет оптимальным, так как перед некоторыми неизвестными в функции цели (5.27) стоит отрицательный коэффициент. Переведем неизвестную х1 из свободных в базисные, тогда базисная неизвестная x4 перейдет в свободные. Теперь система ограничений (5.26) примет вид
x1=200-x3-x4+x6 x2=200-x6 x5=20+x3+x4-x6 (5.28) x7=180-x3 x8=160-x4
Опорный план будет таким (200, 200, 0, 0, 20, 0, 180, 360), а функция цели
Так как все коэффициенты при неизвестных в функции цели (5.29) неотрицательны, то найденный опорный план (5.28) будет оптимальным. Следовательно, чтобы стоимость всех перевозок бетона была минимальной, с первого бетонного завода нужно вывести на первую строительную площадку 200 т, на вторую – тоже 200 т. На третью и четвертую бетон не завозить. Со второго бетонного завода на первую строительную площадку вывести 20 т, на третью - 180т, на четвертую – 360 т, а на вторую площадку бетон не завозить. Стоимость всех перевозок при таком плане будет составлять 1540 соответствующих единиц.
|