Сутність ЕММ

Для розв’язання транспортної задачі як часткового випадку задачі лінійного програмування у сер. 40-х рр. Дж. Данцигом та його учнями було запропоновано універсальний алгоритм, який дозволяє знайти точку мінімуму (максимуму) довільної лінійної функції на множині, яку визначено за допомогою інших рівнянь або нерівностей. Цей алгоритм дістав назву “симплекс-метод”. Цей метод та його вдосконалення – модифікрваний симплекс-метод, двоїстий симплекс-метод тощо – широко застосовується для розв’язку загальних задач зазначеного класу. Щодо транспортної задачі застосування таких загальних алгоритмів не є раціональним, тому що існують спеціалізовані методи розв’язання таких задач.Це зокрема запропонований Л. В. Канторовичем та його науковою школою спеціалізовані алгоритми розв’язання розглянутої транспортної задачі з додатковими обмеженнями шляхів перевезень , задач з урахуванням реальної конфігурації комунікацій тощо:

•Метод потенціалів

•Метод диференційних рент

Для транспортної задачі з обмеженнями на пропускну спроможність та для одержання її цілочисельного розв’язку метод потенціалів було запропоновано ще в 30-ті рр. – “угорський метод” (використовується дуже рідко відносно транспортної задачі, але знайшом широке застосування при розв’язанні “задачі про призначення”).

Задача про призначення

На [n] вакантних посад в деякій установі претендує [m] [n] претендентів. ВІдомий виграш установи [cij] у випадку, якщо і-ий претендент обійме j-ту посаду . Треба розподілити претендентів таким чином, щоб кожного з претендентів було призначено не більш, ніж на 1 вакантну посаду, кожна посада була б зайнята лише одним претендентом і сукупний виграш установи від розподілу претендентів за посадами був якомого більший. У задачі маємо справу з плануванням нових альтернативних дій. Для позначення цих дій математичними засобами використовуються “бульові змінні”: 0 – не змінюється, 1 – змінюється.

Математична умова того, що претендент може бути призначений не більш ніж на 1 посаду

Сукупні витрати:

На відміну від транспортної задачі в задачі про призначення іі змінні можуть приймати лише значення “1” або “0”.

Задачі пошуку екстремуму функції звуться задачами цілочисельного програмування. Окремий випадок задачі цілочисельного програмування, в якому всі змінні бульові, має назву “задача комбінаторної оптимізації”. Слід зауважити, що якщо у транспортній задачі з обмеженнями на пропускну спроможність кільксіть товарів у пункті зосередження, потреби споживачів та максимальні припустимі обмеження преревезень є цілими числами, то серед оптимальних розв’язків такої задачі є хоча б один цілочисельний.

Проте використання методів розв’язання транспортої задачі до задачі про призначення, яку можна розглядати як частковий випадок транспортної задачі за умов:

ai=bj=1,

dij=1, i=1,m

не є раціональним.

Для розв’язання задачі про призначення існують спеціальні алгоритми, що мають більшу ефективність на цьому класі задач, ніж методи транспортної задачі.

Моделі макро- та мезо- рівнів. Гравітаційна модель