Постановка транспортной задачи

1. Яка постановка стандартної транспортної задачі?
Транспортна задача (задача Монжа — Канторовича) — задача про оптимальний план перевезення продукту (-тів) із пунктів відправлення до пунктів споживання. Розробка і використання оптимальних схем вантажних потоків дозволяють знизити витрати на перевезення. ТЗ по теорії складності обчислень є NP-складною або входить в клас складності NP. Коли сумарний обсяг пропозицій (вантажів, наявних в пунктах відправки) не дорівнює загальному обсягу попиту на товари (вантажі), які потрібні пунктам споживання, то транспорта задача називається незбалансованою.
-------------------------------------------------
Постановка задачі
Нехай у пунктах  виробляється деякий однорідний продукт, причому обсяг виробництва цього продукту в пункті Ai дорівнює ai одиниць,  Зроблений у пунктах виробництва продукт повинен бути доставлений до пунктів споживання  причому обсяг споживання в пункті Bj складає bj одиниць продукту. Вважається, що транспортування готової продукції можливе з будь-якого пункту виробництва в будь-який пункт споживання і транспортні витрати, що припадають на перевезення одиниці продукту з пункту Ai в пункт Bj, складають cij грошових одиниць. Задача полягає в організації такого плану перевезень, при якому сумарні транспортні витрати були б мінімальними.
Формально задача ставиться наступним чином. Нехай xij — кількість продукту, що перевозиться з пункту Ai в пункт Bj.Потрібно визначити сукупність з mn величин xij, які відповідають умовам:
  1.
  2.
  3.
і для яких лінійна форма  набуває найменшого значення.
Група обмежень (1)-(2) пов'язана з тою обставиною, що обсяг вивезеного з кожного пункту виробництва продукту в точності дорівнює обсягу виробленого в цьому пункті продукту, а обсяг ввезеного в пункт споживання продукту відповідає його потребі. За цих обмежень необхідною і достатньою умовою для розв'язності транспортної задачі є виконання умови балансу:

  2. Запишіть математичну модель транспортної