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

Строительство магистральной дороги включает задачу заполнения имеющихся на трассе выбоин до уровня основной дороги и срезания в некоторых местах дороги выступов. Срезанным грунтом заполняются выбоины. Перевозка грунта осуществляется грузовиками одинаковой грузоподъемности. Расстояние в километрах от срезов до выбоин объем работ указано в таблице 5. Таблица 5 – Исходные данные к задаче Поставщики Потребители Наличие грунта, т В1 В2 В3 А 1 2 3 110 В 2 1 3 130 С 5 3 4 20 Требуемое количество грунта, т 60 140 60 260 Составьте план перевозок, минимизирующий общий пробег грузовиков.

Обозначим через Xij – количество груза, которое необходимо перевезти от i-го поставщика к j-му потребителю.
i = 1, 2, 3;
j = 1, 2, 3, 4.
Составим экономико-математическую модель задачи.
Переменные:
X11 – объем груза, перевозимого от поставщика А потребителю В1, т;
Х12 – объем груза, перевозимого от поставщика А потребителю В2, т;
Х13 – объем груза, перевозимого от поставщика А потребителю В3, т;
X21 – объем груза, перевозимого от поставщика В потребителю В1, т;
Х22 – объем груза, перевозимого от поставщика В потребителю В2, т;
Х23 – объем груза, перевозимого от поставщика В потребителю В3, т;
X31 – объем груза, перевозимого от поставщика С потребителю В1, т;
Х32 – объем груза, перевозимого от поставщика С потребителю В2, т;
Х33 – объем груза, перевозимого от поставщика С потребителю В3, т.
Ограничения:
по возможности склада А, т х11 + х12 + х13 = 110;
по возможности склада В, т х21 + х22 + х23 = 130;
по возможности склада С, тх31 + х32 + х33 = 20.
по потребности потребителя В1, т х11 + х21+ х31 = 60;
по потребности потребителя В2, т х12 + х22+ х32 = 140;
по потребности потребителя В3, т х13 + х23+ х33 = 60.
Целевая функция:
F(x) = х11 + 2х12 + 3х13 + 2х21 + х22 + 3х23 + 5х31 +
+ 3х32 + 4х33 →min.
Вначале определяется исходный вариант перевозок, а затем последовательно производится его улучшение до получения оптимального плана.
Для получения исходного плана перевозок используем правило «северо-западного» угла

. Заполнение клеток таблицы ведём в направлении от верхней левой до нижней правой (таблица 6). То есть, за счёт ресурсов первого поставщика удовлетворяются потребности первого потребителя (заполняется клетка 1.1). Если ресурс больше, чем потребность первого потребителя, то за счёт остатка удовлетворяются потребности второго потребителя (заполняется клетка 1.2). Если же ресурса первого поставщика недостаточно, то недостающая часть берётся у второго поставщика (заполняется клетка 2.1). Так постепенно распределяются ресурсы всех поставщиков. Следуя этому правилу, получим опорный план, представленный в таблице 6.
Таблица 6 – Исходный план перевозок
Поставщики Потребители Запас
Qi
В1 В2 В3
А 1
60 2
50 3
х 110
В 2
х 1
90 3
40 130
С 5
х 3
х 4
20 20
Спрос bj
60 140 60 260=260
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
х11 = 60 т; х21 = 50 т; х22 = 90 т; х23 = 40 т; х33 =20 т.
F(x) = 60 + 2*50 + 90 + 3*40 + 4*20 = 450 ден. ед.
Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.
По алгоритму решения следует каждую свободную клетку проверить на оптимальность