Исходный опорный план составить методом северо-западного угла. Найти оптимальный план перевозок, при котором транспортные издержки

Исходный опорный план составить методом северо-западного угла. Найти оптимальный план перевозок, при котором транспортные издержки были бы минимальными. Из трех пунктов отправления необходимо доставить однородный груз в четыре пункта назначения. Стоимость перевозки единицы груза, его запасы и потребности к ним указаны в табл. 2. Таблица 2 Поставщики Потребители Запасы В1 В2 В3 В4 А1 с11 с12 с13 с14 30 А2 с21 с22 с23 с24 60 А3 с31 с32 с33 с34 10 Потребности 40 10 20 30 Значения тарифов Cij указаны ниже (табл. 4). Таблица 4 № З-ч с11 с12 с13 с14 с21 с22 с23 с24 с31 с32 с33 с34 1 7 3 12 5 10 4 3 11 9 1 6 2

Стоимость перевозки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов:
Таблица 1
Поставщики Потребители Запасы
В1
В2
В3 В4
А1
7 3 12 5 30
А2
10 4 3 11 60
А3 9 1 6 2 10
Потребности 40 10 20 30
Проверим необходимое и достаточное условие разрешимости задачи.
∑А = 30 + 60 + 10 = 100
∑В = 40 + 10 + 20 + 30 = 100
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
Таблица 2
Поставщики Потребители Запасы
В1
В2
В3 В4
А1
7 3 12 5 30
А2
10 4 3 11 60
А3 9 1 6 2 10
Потребности 40 10 20 30
Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
Искомый элемент равен c11 = 7 (1,1). Для этого элемента запасы равны 30, потребности 40. Поскольку минимальным является 30, то вычитаем его.
х11 = min(30,40) = 30.
Таблица 3
Поставщики Потребители Запасы
В1
В2
В3 В4
А1
7 - - - 30 – 30 =0
А2
10 4 3 11 60
А3 9 1 6 2 10
Потребности 40 – 30 = 10 10 20 30
Искомый элемент равен c21=10 (2,1). Для этого элемента запасы равны 60, потребности 10. Поскольку минимальным является 10, то вычитаем его.
х21 = min(60,10) = 10.
Таблица 4
Поставщики Потребители Запасы
В1
В2
В3 В4
А1
7 - - - 0
А2
10 4 3 11 60 – 10 = 50
А3 - 1 6 2 10
Потребности 10 – 10 =0 10 20 30
Искомый элемент равен c22=4

. Для этого элемента запасы равны 50, потребности 10. Поскольку минимальным является 10, то вычитаем его.
х22 = min(50,10) = 10.
Таблица 5
Поставщики Потребители Запасы
В1
В2
В3 В4
А1
7 - - - 0
А2
10 4 3 11 50 – 10 = 40
А3 - - 6 2 10
Потребности 0 10 – 10 =0 20 30
Искомый элемент равен c23=3. Для этого элемента запасы равны 40, потребности 20. Поскольку минимальным является 20, то вычитаем его.
х23 = min(40,20) = 20.
Таблица 6
Поставщики Потребители Запасы
В1
В2
В3 В4
А1
7 - - - 0
А2
10 4 3 11 40 – 20 =20
А3 - - - 2 10
Потребности 0 0 20 – 20 =0 30
Искомый элемент равен c24=11. Для этого элемента запасы равны 20, потребности 30. Поскольку минимальным является 20, то вычитаем его.
х24 = min(20,30) = 20.
Таблица 7
Поставщики Потребители Запасы
В1
В2
В3 В4
А1
7 - - - 0
А2
10 4 3 11 20 – 20 =0
А3 - - - 2 10
Потребности 0 0 0 30 – 20 = 10

Искомый элемент равен c34=2. Для этого элемента запасы равны 10, потребности 10. Поскольку минимальным является 10, то вычитаем его.
х34 = min(10,10) = 10.
Таблица 8
Поставщики Потребители Запасы
В1
В2
В3 В4
А1
7 - - - 0
А2
10 4 3 11 0
А3 - - - 2 10 – 10 =0
Потребности 0 0 0 10 – 10 = 0
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
Таблица 9
Поставщики Потребители Запасы
В1
В2
В3 В4
А1
7 [30] 3 12 5 30
А2
10 [10] 4 [10] 3 [20] 11 [20] 60
А3 9 1 6 2 [10] 10
Потребности 40 10 20 30
Подсчитаем число занятых клеток таблицы (должно быть m + n - 1 = 6), имеем, что опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 7*30 + 10*10 + 4*10 + 3*20 + 11*20 + 2*10 = 650
Проверим оптимальность опорного плана