6.6. Наближені методи.Метод вектора спаду*
Розроблення та дослідження наближених алгоритмів є досить перспективним напрямком цілочислової оптимізації. Наближені методи заслуговують на увагу більше з практичного погляду, оскільки, як зазначалося вище, застосування точних методів потребує невиправдано значних витрат часу, тоді як пошук наближеного розв’язку дає змогу суттєво скоротити процес знаходження оптимального плану задачі.
Особливо вдалою в літературі, присвяченій проблемам наближених методів, є така ідея формування наближених алгоритмів розв’язування цілочислових задач. Вибирається початковий допустимий план задачі. З таким можливим варіантом розв’язку пов’язується певна (не дуже широка) множина варіантів, які утворюють окіл початкового варіанта. Перебираючи елементи околу, здійснюється перехід до кращого плану або фіксується локальна оптимальність певного варіанта. В першому випадку процес локального покращання плану продовжується, а в другому здійснюється випадковий вибір наступного плану, який беруть за початок пошуку нового оптимального плану. Отже, подібні методи мають вказувати спосіб визначення околу та механізм випадкового пошуку. Крім того, необхідно також ввести правило, за допомогою якого визначається момент закінчення процесу пошуку наближеного розв’язку.
Розглянемо без детальних доведень один з наближених методів, що дає назву методу вектора спаду [27]. Його розробив І. В. Сергієнко в середині 60-х років. У загальному випадку цей метод дає змогу знаходити локальний мінімум цільової функції, проте, якщо вона має відповідні властивості опуклості, то він приводить до визначення глобального мінімуму.
Допустимо, що розглядається задача цілочислового програмування виду:
(6.24)
за умов:
(6.25)
(6.26)
— цілі числа (6.27)
Перш ніж описувати алгоритм методу, введемо деякі необхідні поняття.
Нехай М — деякий дискретний точковий простір. — множина допустимих планів деякої цілочислової задачі виду (6.24)—(6.27). Введемо метрику в простір М, тобто функцію, що визначає відстань між довільними точками цього простору Х та Y. Позначимо її через . Метрика має задовольняти три аксіоми:
1) аксіому тотожності: за умови, що X = Y;
2) аксіому симетрії: ;
3) аксіому нерівності трикутника:
З аналітичної геометрії відомо, що відстань між точками (функцію можна визначати по-різному. Зокрема, у прямокутній декартовій системі координат це може бути довжина вектора тобто , де — відповідно координати точок X та Y у просторі М.
Нехай деякий допустимий план задачі дискретного програмування. Якщо взяти деяке число то множина всіх точок для яких виконується нерівність називається відкритим околом з центром у точці і радіусом r, а множина всіх точок для яких виконується нерівність називається закритим околом.
Визначимо деякий окіл точки з радіусом r1, такий, щоб крім плану він містив би і інші плани задачі, для чого r1 має бути не меншим від деякої величини R. Далі розглядатимемо лише зазначені околи планів задачі. Визначимо функцію у такий спосіб:
Назвемо вектором спаду функції у деякому околі довільної точки (що є одним з допустимих розв’язків задачі цілочислового програмування такий вектор, компонентами якого є величини , де — плани задачі, що належать околу .
Очевидно, що при невід’ємності всіх компонент вектора спаду в околі точки матимемо для будь-якого значення

Остання нерівність означає, що точка є точкою локального мінімуму функції відносно виділеного околу , тобто:

Якщо ж деякі компоненти вектора спаду будуть від’ємними, то це означає, що не є точкою мінімуму в зазначеному околі, оскільки в деяких точках цього околу функція набуває менших значень. Причому та точка виділеного околу, для якої різниця буде найменшою, визначає напрям найшвидшого спаду (зменшення) цільової функції оскільки Цей очевидний факт і лежить в основі обчислювальної схеми застосування методу вектора спаду.
Ідея методу полягає у визначенні компонент вектора спаду для деякої початкової точки. Якщо всі вони невід’ємні, то точку локального мінімуму знайдено, інакше знаходимо центр нового околу і перевіряємо його компоненти на невід’ємність. Процес пошуку розв’язку є послідовним перебором точок, що зменшують значення цільової функції.
Як правило, на кожному кроці алгоритму (тобто для кожного нового околу) не потрібно обчислювати всі компоненти вектора спаду, а лише частину з них, що дає істотний виграш в обсязі і тривалості обчислень.
Наведемо один з можливих алгоритмів реалізації методу вектора спаду.
1. Вибрати початкову точку Х0 і радіус околу R так, щоб точка Х0 була допустимим планом відповідної задачі цілочислового програмування а окіл був таким, що містить також інші допустимі плани задачі. Цей вибір може здійснюватись випадково з податковою перевіркою виконання зазначених умов.
2. Визначаються компоненти вектора спаду в вибраному околі. Якщо всі його компоненти невід’ємні, то точку локального мінімуму знайдено (тобто задача розв’язана і оптимальним цілочисловим планом є ).
3. Якщо не всі компоненти вектора спаду невід’ємні, то вибираємо компоненту яка має найменше значення і визначає точку , що зменшує значення цільової функції і є центром нового околу.
4. Повертаємось до пункту 2. Процес продовжуємо, поки для деякого всі компоненти відповідного вектора спаду не будуть невід’ємними.
Розв’яжемо цілочислову задачу, використовуючи зміст прикладу 6.1.
Розв’язання. Нехай Вибрана точка є допустимим планом задачі, оскільки задовольняє всі обмеження і умову цілочисловості, а окіл вибраного радіуса містить інші плани задачі, наприклад, точку
Визначаємо точки, які належать означеному околу (рис. 6.6). Це такі три точки:



Визначимо компоненти вектора спаду, ввівши такі позначення:

Найменшою є третя компонента вектора спаду, отже, відповідна їй точка стає центром наступного околу Радіус
У новий окіл будуть входити точки з координатами:







Необхідно обчислити значення компонент вектора спаду для зазначених точок. Однак для трьох точок потрібні величини були розраховані на попередньому кроці, і залишається обчислити компоненти вектора для нових точок.
Після проведення обчислень маємо, що найменшого значення набуває компонента вектора, яка відповідає точці тому наступний цент околу переміщається в нову точку Нехай
Обчислюємо компоненти вектора спаду лише в двох точках околу:


Зіставивши ці значення, визначаємо точку нового центру околу з радіусом Компоненти вектора спаду в цьому околі набувають тільки додатних значень. Отже, процедуру наближення завершено, і ця точка є оптимальним планом цілочислової задачі:
Зауважимо, що метод вектора спаду, як видно з опису реалізації алгоритму, придатний для знаходження цілочислового розв’язку також і нелінійних задач.
6.7. Приклади застосування цілочислових задач лінійного програмування у плануванні та управлінні виробництвом*
Задача про рюкзак. Найпростішою задачею цілочислового програмування, а саме задачею лише з одним обмеженням, є задача про рюкзак (або ранець). Така задача має багато прикладів практичного застосування. Назва «задача про рюкзак» пов’язана з інтерпретацією задачі вибору найкращого складу предметів, що задовольняють певні умови гіпотетичної проблеми туриста щодо вибору для походу оптимальної кількості речей.
Турист може вибирати потрібні речі із списку з n предметів. Відома вага кожного j-го предмета . Визначена також цінність кожного виду предметів . Максимальна вага всього вантажу в рюкзаку не може перевищувати зазначеного обсягу М. Необхідно визначити, скільки предметів кожного виду турист має покласти в рюкзак, щоб загальна цінність спорядження була максимальною за умови виконання обмеження на вагу рюкзака.
Позначимо через – кількість предметів j-го виду в рюкзаку. Тоді математична модель задачі матиме вигляд:

;
, — цілі числа, .
Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Він може купити добрива в упаковках по 35 кг вартістю 14 ум. од. або по 24 кг вартістю 12 ум. од. Метою фермера є закупівля не менше, ніж 107 кг добрив з мінімальними витратами. Причому потрібно купувати або цілу упаковку, або не купувати її зовсім, бо частину упаковки придбати неможливо.
Розв’язання. Позначимо кількість упаковок вагою 35 кг та вагою 24 кг відповідно змінними та . Маємо модель цієї задачі:

;
, — цілі числа.
У результаті розв’язування задачі будь-яким з вищенаведених методів отримаємо оптимальний план: , . Отже, за оптимальним планом найменші витрати, що дорівнюють 50 ум. од., можливі у разі закупівлі однієї упаковки добрив вагою 35 кг та трьох вагою по 24 кг.
Задача оптимального розкрою матеріалів. На підприємстві здійснюється розкрій m різних партій матеріалів у обсягах одиниць однакового розміру в кожній партії. Із матеріалів усіх партій потрібно виготовити максимальну кількість комплектів Z, у кожен з яких входить p різних видів окремих частин в кількості одиниць, враховуючи, що кожну одиницю матеріалу можна розкроїти на окремі частини n різними способами, причому у разі розкрою одиниці i-ої партії j-им способом отримуємо деталей r-го виду.