Алгоритм дихотомічного пошуку

Початковий етап.

Необхідно вибрати константу 2e > 0 і кінцеву допустиму довжину інтервалу невизначеності l>0. Визначити [а, в] і к=1 та перейти до основного етапу.

Основний етап.

Шаг 1. Якщо в_к ® а_к < l, то кінець розрахунків; точка мінімуму належить інтервалу [а, в]. В іншому випадку треба розрахувати

х₁= х₂=

і перейти до шагу 2.

Шаг 2. Якщо f(x₁) < f(x₂), то необхідно прийняти а_к+1 = а_к і в_к+1 = х₂. В іншому випадку треба прийняти а_к+1 = х₁ і в_к+1 = в_к. Замінити к на к+1 і перейти до шагу 1.

Довжина інтервалу невизначеності в початку (к+1)-ої ітерації дорівнює

(в_к+1 - а_к+1) = (в₁ – а₁) + 2e(1 - ).

Ця формула може бути використана для визначення числа ітерацій, необхідних для досягнення бажаної точності. Кожна ітерація потребує двох розрахунків, що дозволяє визначити число розрахунків для знаходження оптимуму функції f.

Рекомендована література

7.1. Основна

1. Українець А.І., Гуржій А.М., Самсонов В.В., Кривець Т.О., Городенська В.Я. Задачі лінійного та нелінійного програмування програмування. Навч. Посібник.- К.:НУХТ, 2007. – 156 с.

2. Бейко И.В., Бублик Б.Н., Зінько П.Н. Методы и алгоритмы решения задач оптимизации.- К.: Вища школа. Головное изд-во. 1983. –512с.

3. Ляшенко И.Н., Карагодова Е.А., Чернишова Н.В., Шор Н.З. Линейное и нелинейное программирование..- К.: Вища школа. Головное изд-во. 1975. –372с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. –М.: Высш. Шк., 1986. –319 с.

5. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. –М.: Физматгиз, 1963. –776с.

6. Вагнер Г. Основы исследования операций, 3т.: Пер. с анг.. –М.: Мир, 1973.

7. Базара М., Шести К. Нелинейное программирование. Теория и алгоритмы: Пер. с анг.. –М.: Мир, 1982. –583с.

8. Бєліков М.І., Гуржій А.М., Кігель В.Р., Самсонов В.В. Розв’язування оптимізаційних задач за допомогою методів лінійного програмування. –К.: УДУХТ, 1994. –132с.

9. Самсонов В.В., Гуржій А.М. Задачі оптимізації в практичної діяльності фахівця. –К.: УДУХТ, 1997. –176.

10. Задачі лінійного та нелінійного програмування: Навч. Посібник / А.І.Українець, А.М. Гуржий, В.В.Самсонов та ін. – К.: НУХТ, 2007. – 156 с.

6.2. Додаткова

11. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. –М.: Советское радио, 1966. –524с.

12. Вензель Е.С. Исследование операций. -М.: Советское радио, 1972. –552с.

13. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения: Пер. с анг. – Радио и связь, 1981. –560с.

14. Зайченко Ю.П. Дослідження операцій: Підручник.–4–те вид., перероб. і допов. – К., 2000. – Бібліограф. 67 найм. – 687с.