Проверим необходимое и достаточное условие разрешимости задачи.∑a = 30 + 60 + 10 = 100∑b = 40 + 20 + 10 + 30 = 100
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Решение
Отыскиваемый элемент равен c34=2. Для этого элемента запасы равны 10, потребности 30. Т.к. минимальным является 10, то вычитаем его.x34 = min(10,30) = 10.
7 9 11 8 30
12 6 7 5 60
x x x 2 10 - 10 = 0
40 20 10 30 - 10 = 20
Отыскиваемый элемент равен c24=5. Для этого элемента запасы равны 60, потребности 20. Т.к. минимальным является 20, то вычитаем его.x24 = min(60,20) = 20.
7 9 11 x 30
12 6 7 5 60 - 20 = 40
x x x 2 0
40 20 10 20 - 20 = 0
Отыскиваемый элемент равен c22=6. Для этого элемента запасы равны 40, потребности 20. Т.к. минимальным является 20, то вычитаем его.x22 = min(40,20) = 20.
7 x 11 x 30
12 6 7 5 40 - 20 = 20
x x x 2 0
40 20 - 20 = 0 10 0
Отыскиваемый элемент равен c11=7. Для этого элемента запасы равны 30, потребности 40. Т.к. минимальным является 30, то вычитаем его.x11 = min(30,40) = 30.
7 x x x 30 - 30 = 0
12 6 7 5 20
x x x 2 0
40 - 30 = 10 0 10 0
Отыскиваемый элемент равен c23=7. Для этого элемента запасы равны 20, потребности 10
. Т.к. минимальным является 10, то вычитаем его.x23 = min(20,10) = 10.
7 x x x 0
12 6 7 5 20 - 10 = 10
x x x 2 0
10 0 10 - 10 = 0 0
Отыскиваемый элемент равен c21=12. Для этого элемента запасы равны 10, потребности 10. Т.к. минимальным является 10, то вычитаем его.x21 = min(10,10) = 10.
7 x x x 0
12 6 7 5 10 - 10 = 0
x x x 2 0
10 - 10 = 0 0 0 0
В результате получен первый опорный план, который является допустимым, так как все грузы из складов вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
B1 B2 B3 B4 Запасы
A1 7[30] 9 11 8 30
A2 12[10] 6[20] 7[10] 5[20] 60
A3 4 10 9 2[10] 10
Потребности 40 20 10 30
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 7; 0 + v1 = 7; v1 = 7u2 + v1 = 12; 7 + u2 = 12; u2 = 5u2 + v2 = 6; 5 + v2 = 6; v2 = 1u2 + v3 = 7; 5 + v3 = 7; v3 = 2u2 + v4 = 5; 5 + v4 = 5; v4 = 0u3 + v4 = 2; 0 + u3 = 2; u3 = 2
v1=7 v2=1 v3=2 v4=0
u1=0 7[30] 9 11 8
u2=5 12[10] 6[20] 7[10] 5[20]
u3=2 4 10 9 2[10]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;1): 2 + 7 > 4; ∆31 = 2 + 7 - 4 = 5 > 0
Выбираем максимальную оценку свободной клетки (3;1): 4
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 Запасы
1 7[30] 9 11 8 30
2 12[10][-] 6[20] 7[10] 5[20][+] 60
3 4[+] 10 9 2[10][-] 10
Потребности 40 20 10 30
Цикл приведен в таблице (3,1 → 3,4 → 2,4 → 2,1).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
