Решить транспортную задачу, заданную распределительной таблицей, где параметр а = 8, b = 8

Решить транспортную задачу, заданную распределительной таблицей, где параметр а = 8, b = 8 . 40 – a 20 40 + b 1 30 + b 2 25 3 15 4 30 – a Примечание. Первоначальный опорный план строить методом минимальной стоимости!

Для данных варианта №1 получим:
Пункты
отправления Пункты назначения Запасы
В1 В2 В3
А1 3 5 4 38
А2 4 2 1 25
А3 1 3 2 15
А4 5 3 5 22
Потребности 32 20 48  
Суммарные запасы Σ аі = 38+25+15+22=100 , суммарные потребности Σ bj=32+20+48=100.
Σ аі = Σ 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
17
21
а1 = 38 а1 ’= 21
А2 ___ 4 ___ 2
1
25
а2 = 25
А3
1 ___ 3 ___ 2

15
а3 = 15
А4 ___ 5
3
5
20
2
а4 = 22 а4 ’= 2
Потребн
bj b1 = 32 b2 = 20 b3 = 48
b1’= 17
b3 ’= 23
b3 ’’= 2
, строку А3 вычёркиваем.
, строку А2 вычёркиваем.
, столбец В1 вычёркиваем.
, столбец В2 вычёркиваем.
.

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