Решить транспортную задачу заданную распределительной таблицей

Для данных варианта №1 получим:
Пункты
отправления Пункты назначения Запасы
В1 В2 В3
А1 3 5 4 40
А2 4 2 1 25
А3 1 3 2 15
А4 5 3 5 26
Потребности 36 20 50
Суммарные запасы Σ аі = 40+25+15+26=106 , суммарные потребности Σ bj=36+20+50=106.
Σ аі = Σ bj, запасы равняются потребностям, то есть это закрытая модель транспортной задачи.
Составим математическую модель задачи.
Пусть хіj – количество единиц груза, которое планируется перевезти из пункта Аі к пункту Вj (это план перевозок). Тогда общая стоимость всех перевозок будет : Z = Σ Σ Cij хij, ее необходимо минимизировать.
Количество единиц не может быть отрицательным, поэтому
хіj ≥ 0.
Из условия задачи вытекает, что должны выполняться такие условия :
Σ хіj = аі , i =1,2,3,4,
то есть весь груз из пунктов Аі необходимо вывезти.
Кроме того нужды потребителей Вj должны быть полностью удовлетворены, то есть Σ хіj = bj , j = 1,2,3.
Таким образом, математическая модель задачи имеет вид :
1415415120015Z = Σ Σ Cij хіj → min
Σ хіj = аі , і=1,2,3,4
Σ хіj = bj , j = 1,2,3.
хіj ≥ 0
00Z = Σ Σ Cij хіj → min
Σ хіj = аі , і=1,2,3,4
Σ хіj = bj , j = 1,2,3.
хіj ≥ 0
Распишем эту систему подробно:
хіj ≥ 0, і=1,2,3,4, j = 1,2,3.
Для поиска начального опорного плана используем метод “минимальной стоимости”.
Составим транспортную таблицу, в углы клеток запишем заданные тарифы Сіj, а в середины клеток будемо последовательно заносить значения хіj по схеме :
Из всей таблицы стоимостей выбираем клетку АіВj с наименьшей стоимостью Сіj, то есть ищем min Сіj , и заносим в нее число хіj = min {аі , bj } .
Потом вычеркиваем и больше не рассматриваем строку, которая отвечает поставщику, запасы которого полностью исчерпаны, или столбец, который отвечает потребителю, нужды которого полностью удовлетворенны.
В части таблицы , которая осталась после вычеркивания, снова ищем min Сіj и процесс распределения продолжаем до тех пор, пока все запасы не будут исчерпаны, а нужды – удовлетворены.
В1
В2
В3
Запасы
аі
А1
3 ___ 5
4
21
19
а1 = 40 а1 ’= 19
А2 ___ 4 ___ 2
1
25
а2 = 25
А3
1 ___ 3 ___ 2

15
а3 = 15
А4 ___ 5
3
5
20
6
а4 = 26 а4 ’= 6
Потребн
bj b1 = 36 b2 = 20 b3 = 50
b1’= 21
b3 ’= 25
b3 ’’= 6
, строку А3 вычёркиваем.
, строку А2 вычёркиваем.
, столбец В1 вычёркиваем.
, столбец В2 вычёркиваем.
.

Транспортная таблица заполнена