Для строительства трех дорог используется гравий из четырех карьеров. Запасы гравия (тонны) в каждом из карьеров представлены в первом столбце таблицы. Потребности в гравии (тонны) для строительства каждой из дорог – в первой строке таблицы. Тариф перевозок 1 тонны гравия из i-го карьера к j-й строящейся дороге задан в таблице на пересечении строки i и столбца j.
Составить такой план перевозок гравия, при котором потребности в нем каждой из строящихся дорог были бы удовлетворены при наименьшей общей стоимости перевозок.
Решение
Проверяем необходимое и достаточное условие разрешимости задачи.∑a = 600 + 300 + 330 = 1230∑b = 350 + 350 + 230 + 300 = 1230
Т.к. условие баланса соблюдается (запасы равны потребностям), то модель транспортной задачи является закрытой.
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Отыскиваемый элемент равен c11=1. Для этого элемента запасы равны 600, потребности 350. Т.к. минимальным является 350, то вычтем его.x11 = min(600,350) = 350.
1 4 1 9 600 - 350 = 250
x 2 2 8 300
x 1 7 3 330
350 - 350 = 0 350 230 300
Отыскиваемый элемент равен c13=1. Для этого элемента запасы равны 250, потребности 230. Т.к. минимальным является 230, то вычтем его.x13 = min(250,230) = 230.
1 4 1 9 250 - 230 = 20
x 2 x 8 300
x 1 x 3 330
0 350 230 - 230 = 0 300
Отыскиваемый элемент равен c32=1. Для этого элемента запасы равны 330, потребности 350. Т.к. минимальным является 330, то вычтем его.x32 = min(330,350) = 330.
1 4 1 9 20
x 2 x 8 300
x 1 x x 330 - 330 = 0
0 350 - 330 = 20 0 300
Отыскиваемый элемент равен c22=2. Для этого элемента запасы равны 300, потребности 20. Т.к. минимальным является 20, то вычтем его.x22 = min(300,20) = 20.
1 x 1 9 20
x 2 x 8 300 - 20 = 280
x 1 x x 0
0 20 - 20 = 0 0 300
Отыскиваемый элемент равен c24=8. Для этого элемента запасы равны 280, потребности 300. Т.к. минимальным является 280, то вычтем его.x24 = min(280,300) = 280.
1 x 1 9 20
x 2 x 8 280 - 280 = 0
x 1 x x 0
0 0 0 300 - 280 = 20
Отыскиваемый элемент равен c14=9
. Для этого элемента запасы равны 20, потребности 20. Т.к. минимальным является 20, то вычтем его.x14 = min(20,20) = 20.
1 x 1 9 20 - 20 = 0
x 2 x 8 0
x 1 x x 0
0 0 0 20 - 20 = 0
В результате получен первый опорный план, который является допустимым, так как весь гравий из карьеров вывезен, потребности дорог удовлетворены, а план соответствует системе ограничений транспортной задачи.
1 2 3 4 Запасы
1 1[350] 4 1[230] 9[20] 600
2 9 2[20] 2 8[280] 300
3 6 1[330] 7 3 330
Потребности 350 350 230 300
Значение целевой функции для этого опорного плана равно:
F(x) = 1∙350 + 1∙230 + 9∙20 + 2∙20 + 8∙280 + 1∙330 = 3370.
Проверяем оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1u1 + v3 = 1; 0 + v3 = 1; v3 = 1u1 + v4 = 9; 0 + v4 = 9; v4 = 9u2 + v4 = 8; 9 + u2 = 8; u2 = -1u2 + v2 = 2; -1 + v2 = 2; v2 = 3u3 + v2 = 1; 3 + u3 = 1; u3 = -2
v1=1 v2=3 v3=1 v4=9
u1=0 1[350] 4 1[230] 9[20]
u2=-1 9 2[20] 2 8[280]
u3=-2 6 1[330] 7 3
Опорный план не является оптимальным, т.к. существуют оценки свободных клеток, для которых ui + vj > cij
(3;4): -2 + 9 > 3; ∆34 = -2 + 9 - 3 = 4 > 0
Выбираем максимальную оценку свободной клетки (3;4): 3
Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 Запасы
1 1[350] 4 1[230] 9[20] 600
2 9 2[20][+] 2 8[280][-] 300
3 6 1[330][-] 7 3[+] 330
Потребности 350 350 230 300
Цикл приведен в таблице (3,4 → 3,2 → 2,2 → 2,4).
Из грузов хij которые стоят в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
