Порівняння методів одновимірного пошуку

Найкращими критеріями порівняння методів пошуку, які були описані вище, є їх ефективність і універсальність. Під ефективністю алгоритму розуміють число обчислень функції, необхідне для досягнення необхідного звуження інтервалу невизначеності. Із табл. 13.1 видно, що найкращим в цьому відношенні є метод Фібоначчі, а найгіршим – метод загального пошуку. Конструктор не з великим задоволенням використовує метод Фібоначчі, так як при його застосуванні необхідно заздалегідь задавати число обчислень значень функції. Однак він може скористатися методом золотого перетину. Як правило, метод золотого перетину, володіє високою ефективністю, найбільш підходить для розв’язку одновимірних унімодальних задач оптимізації.

Універсальність алгоритму означає, що його можна легко застосувати для розв’язку самих різноманітних задач. В цьому відношенні метод Фібоначчі, поступається іншим, так як потребує окремого обчислення положення точок, в яких будуть визначатися значення цільової функції на кожному новому кроці. Цим приходиться розплачуватися за підвищення ефективності метода. З точки зору універсальності малоефективний метод загального пошуку має по крайній мірі одну перевагу – його можна з успіхом застосовувати і для неунімодальних функцій, якщо вони достатньо гладкі. Нерідко заздалегідь не відомо, чи є розглянута цільова функція унімодальною. В таких випадках слід використати декілька різних алгоритмів і подивитись, чи дають вони усі один і той самий оптимум. Звідси витікає важливий висновок, який слід мати на увазі, розв’язуючи задачі оптимізації: не існує універсального алгоритму, який дозволяв би розв’язувати будь-які задачі. Вирішуючи складні задачі оптимізації, слід користуватися різними методами, так як це дозволяє збільшити долю вигідних розв’язків

Транспортна задача.

Транспортна задача — задача про оптимальний план перевезення продукту (-тів) із пунктів відправлення до пунктів споживання. Розробка і використання оптимальних схем вантажних потоків дозволяють знизити витрати на перевезення. ТЗ по теорії складності обчислень є NP-складною або входить в клас складності NP. Коли сумарний обсяг пропозицій (вантажів, наявних в пунктах відправки) не дорівнює загальному обсягу попиту на товари (вантажі), які потрібні пунктам споживання, то транспорта задача називається незбалансованою.

Постановка задачі

Нехай у пунктах виробляється деякий однорідний продукт, причому обсяг виробництва цього продукту в пункті A_i дорівнює a_i одиниць, Зроблений у пунктах виробництва продукт повинен бути доставлений до пунктів споживання причому обсяг споживання в пункті B_j складає b_j одиниць продукту. Вважається, що транспортування готової продукції можливе з будь-якого пункту виробництва в будь-який пункт споживання і транспортні витрати, що припадають на перевезення одиниці продукту з пункту A_i в пункт B_j, складають c_ij грошових одиниць. Задача полягає в організації такого плану перевезень, при якому сумарні транспортні витрати були б мінімальними.

Формально задача ставиться наступним чином. Нехай x_ij — кількість продукту, що перевозиться з пункту A_i в пункт B_j. Потрібно визначити сукупність з mn величин x_ij, які відповідають умовам:

1.

2.

3.

і для яких лінійна форма набуває найменшого значення.

Група обмежень (1)-(2) пов'язана з тою обставиною, що обсяг вивезеного з кожного пункту виробництва продукту в точності дорівнює обсягу виробленого в цьому пункті продукту, а обсяг ввезеного в пункт споживання продукту відповідає його потребі. За цих обмежень необхідною і достатньою умовою для розв'язності транспортної задачі є виконання умови балансу: