Задача по "Высшей математике"

Математическая модель транспортной задачи:

F = ∑∑cijxij,    

при условиях:

∑xij = ai,  i = 1,2,…, m,  

∑xij = bj,  j = 1,2,…, n,  

xij ≥ 0

Ограничения:

x11 + x12 + x13 + x14 ≤ 15

x21 + x22 + x23 + x24 ≤ 50

x31 + x32 + x33 + x34 ≤ 15

x11 + x21 + x31 = 25

x12 + x22 + x32 = 25

x13 + x23 + x33 = 25

x14 + x24 + x34 = 25

Целевая функция:

x11 + 5x12 + 7x13 + 6x14 + 10x21 + 11x22 + 4x23 + 2x24 + 8x31 + 3x32 + 12x33 + 9x34 → min

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 15 + 50 + 15 = 80

∑b = 25 + 25 + 25 + 25 = 100

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 20 (80—100). Тарифы перевозки единицы груза из базы ко всем потребителям полагаем равны нулю.

Метод минимального элемента.

F(x) = 1*15 + 4*25 + 2*25 + 3*15 + 0*10 + 0*10  = 210

m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Метод северо-западного угла.

F(x) = 1*15 + 10*10 + 11*25 + 4*15 + 12*10 + 9*5 + 0*20  = 615

Метод двойного предпочтения.

F(x) = 1*15 + 4*25 + 2*25 + 3*15 + 0*10 + 0*10  = 210

...