Первоначальный опорный план составьте методом северо-западного угла

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 18 + 22 + 15 = 55 ед.
∑b = 12 + 19 + 9 = 40 ед.
Как видно, суммарная потребность швейных фабрик меньше запасов на ткацких фабриках. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 15 (55-40). Тарифы перевозки единицы груза к этому магазину полагаем равны нулю.
Таблица 8 – Исходные данные с фиктивным потребителем
Поставщики Потребители Запасы продукции, ед.
B1 B2 B3 B4
А1 5 8 2 0 18
А2 8 9 4 0 22
А3 6 7 3 0 15
Потребности, ед. 12 19 9 15 55=55
Обозначим через Xij – количество груза, которое необходимо перевезти от i-го поставщика (склада) к j-му потребителю (магазину).
i = 1, 2, 3;
j = 1, 2, 3, 4.
Составим экономико-математическую модель задачи.
Переменные:
X11 – объем груза, перевозимого от поставщика А1 потребителю В1;
Х12 – объем груза, перевозимого от поставщика А1 потребителю В2;
Х13 – объем груза, перевозимого от поставщика А1 потребителю В3;
X14 – объем груза, перевозимого от поставщика А1 потребителю В4;
X21 – объем груза, перевозимого от поставщика А2 потребителю В1;
Х22 – объем груза, перевозимого от поставщика А2 потребителю В2;
Х23 – объем груза, перевозимого от поставщика А2 потребителю В3;
X24 – объем груза, перевозимого от поставщика А2 потребителю В4;
X31 – объем груза, перевозимого от поставщика А3 потребителю В1;
Х32 – объем груза, перевозимого от поставщика А3 потребителю В2;
Х33 – объем груза, перевозимого от поставщика А3 потребителю В3;
X34 – объем груза, перевозимого от поставщика А3 потребителю В4;
Ограничения:
по возможности поставщика А1, ед. х11 + х12 + х13+ х14 = 18;
по возможности поставщика А2, ед. х21 + х22 + х23+ х24 = 22;
по возможности поставщика А3, ед.х31 + х32 + х33+ х34 = 15.
по потребности потребителя В1, ед. х11 + х21+ х31 = 12;
по потребности потребителя В2, ед. х12 + х22+ х32 = 19;
по потребности потребителя В3, ед., х13 + х23+ х33 = 9;
по потребности по потребности В4, ед. х14 + х24+ х34 = 15.
Целевая функция:
F(x) = 5х11 + 8х12 + 2х13 + 0х14 + 8х21 + 9х22 + 4х23 + 0х24 +
+ 6х31 + 7х32 + 3х33 + 0х34→min.
Вначале определяется исходный вариант перевозок, а затем последовательно производится его улучшение до получения оптимального плана.
Для получения исходного плана перевозок используем правило «северо-западного» угла. Заполнение клеток таблицы ведём в направлении от верхней левой до нижней правой (таблица 9) . То есть, за счёт ресурсов первого поставщика удовлетворяются потребности первого потребителя (заполняется клетка 1.1). Если ресурс больше, чем потребность первого потребителя, то за счёт остатка удовлетворяются потребности второго потребителя (заполняется клетка 1.2). Если же ресурса первого поставщика недостаточно, то недостающая часть берётся у второго поставщика (заполняется клетка 2.1). Так постепенно распределяются ресурсы всех поставщиков. Следуя этому правилу, получим опорный план, представленный в таблице.
Таблица 9 – Исходный план перевозок
Поставщики Потребители Запас
Qi
B1 B2 B3 B4
А1 5
12 8
6 2 0 18
А2 8 9
13 4
9 0 22
А3 6 7 3 0
15 15
Спрос bj
12 19 9 15
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
х11 = 12 ед.; х12 = 6 ед.; х22 = 13 ед.; х23 = 9 ед.; х34 = 15 ед.
F (x) = 5*12+8*6+9*13+4*9+0*15 = 261 ден. ед.
По алгоритму решения следует каждую свободную клетку проверить на оптимальность. Для этого по каждой строке и столбцу определяют потенциалы занятых клеток по формуле:
ui +vj = cij, (2)
гдеvj – потенциал столбца
ui – потенциал строки
cij – тариф (показатель) занятой клетки
Расчёт потенциалов начинаем с того, что один из них приравниваем к нулю (u1 = 0).
U1 + V1 = 5; 0 + V1 = 5; V1 = 5;
U1 + V2 = 8; 0 + V2 = 8; V2 = 8;
U2 + V2 = 9; 8 + U2 = 9; U2 = 1;
U2 + V3 = 4; 1 + V3 = 4; V3 = 3.
На данном этапе возникла ситуация, когда для оставшихся занятых клеток не известно ни одного из потенциалов. Это результат вырожденности решения. Для его преодоления в одну из клеток нужно внести нулевую поставку, таким образом, такая клетка станет условно занятой.
Для неизвестного потенциала u3 нулевую поставку можно разместить в клетках:
(3;1), V1=5;
(3;2), V2=8;
(3;3), V3=3.
Для неизвестного потенциала v4 нулевую поставку можно разместить в клетках:
(1;4), U1=0;
(2;4), U2=1.
Среди этих клеток, в которых может быть размещена нулевая поставка, наименьший тариф имеет клетка (2, 4) с c24 = 0. Следовательно, нулевую поставку размещаем в клетку (2, 4), и она становится условно занятой.
U2 + V4 = 0; 1 + V4 = 0; V4 = -1;
Ранее поставленный псевдоноль из ячейки (1;3) убираем.
U3 + V4 = 0; -1 + U3 = 0; U3 = 1.
Для свободных клеток определяются характеристики по формуле (3):
dij = cij - (ui+ vj),(3)
где dij – характеристика свободной клетки.
d13 = 2-(0+3) = -1;
d14 = 0-(0-1) = 1;
d21 = 8-(1+5) = 2;
d31 = 6-(1+5) = 0;
d32 = 7-(1+8) = -2;
d33 = 3-(1+3) = -1.
Отрицательные характеристики при решении задач на min указывают на то, что транспортные расходы могут быть снижены, т.е