Вопрос. Однопродуктовая транспортная задача в матричной постановке.

Есть m поставщиков и n потребителей одно­родного товара. Поставщик i характеризуется мощностью a_i

b_j- потребность потребителя j

c_ij- затраты на поставку

Задача - распределить товар с min-ми суммар­ными затратами

x_ij- объем поставки

-суммарная поставка потребителю j

-суммарный вывоз от поставщика i

мощность пр-ва товара должна быть больше, чем он поставляет

минимизируем затраты

Задача имеет решение тогда и т.т., когда она совместна и ограничена

Совместность:

Предлож-е i, спрос j. Поставка больше спроса, но меньше предло­жения поставщика

Суммарное наличие не меньше суммарной потребности

если достигается равенство, задача называется замкнутой, сбалансирован­ной

Если задача не сбалансирована, у какого-то поставщика будет излишек

Надо ввести фиктивного потребителя (n+1), который будет проглатывать излишек и задача становится сбалансированной:

С_i,n+1 – ущерб от избыточной единицы

Если задача несовместна

то надо вводить фиктивного поставщика m+1

Его мощность

C_m+1,j – ущерб потребителя j от недопоставки единицы товара