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

Стоимость перевозки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов:
Таблица 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
Проверим оптимальность опорного плана