5.3 Задачі з дискретними змінними

 

У ряді практичних оптимізаційних задач заздалегідь відомий набір допустимих розв’язків, з яких потрібно вибрати оптимальний розв’язок. Наприклад, один компенсувальний пристрій заданої потужності Q_k можна розмістити у вузлах 1,2,...n системи електропостачання. Потрібно вибрати оптимальний вузол розміщення компенсувального пристрою, який відповідає обраному критерію.

У ряді інших задач шукані змінні можуть приймати не будь-які, а тільки певні значення, з яких потрібно вибрати значення змінних, що відповідають оптимальному розв’язку. Наприклад, у заданому вузлі системи електропостачання потрібно встановити компенсувальний пристрій потужність якого може бути рівною значенням Q_k1,Q_k2,...Q_kn. Із цього ряду потрібно вибрати оптимальне значення потужності компенсувального пристрою, що відповідає обраному критерію. Зазначені задачі відносяться до задач вибору варіантів з числа заданих і вирішуються методами дискретного програмування. У цих методах поряд із традиційними змінними використовуються двійкові змінні, можливості яких за задачами логічних умов розглянуті в п. 5.2.

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

Нехай в оптимізаційній задачі є n шуканих змінних x_i (i=1,2,...n). Дискретні значення кожної змінної задані. В оптимальний розв’язок повинні ввійти k змінних (k<n). Кожній змінній x_i поставимо у відповідність двійкову змінну . Якщо у процесі розв’язуванні задачі , то змінна x_i увійде в оптимальний розв’язок; якщо , то змінна x_i не ввійде в оптимальний розв’язок.

Цільова функція містить у собі як дискретні x₁,x₂,...x_n, так і двійкові змінні :

                          (5.7)

У систему обмежень входять і дискретні, і двійкові змінні:

                            (5.8)

До цієї системи додаються обмеження вигляду:

                         (5.9)

Граничні умови, як такі, не записуємо, оскільки можливі значення дискретних змінних є заданими, а значення двійкових змінних можуть бути тільки 0 або 1.

Не вдаючись у подробиці методів дискретного програмування, відзначимо, що програмне забезпечення MS Excel дозволяє вирішувати оптимізаційні задачі з дискретними змінними. Тому надамо користувачеві складання математичної моделі оптимізаційної задачі й введення вихідної інформації в комп'ютер, а обчислювальну процедуру надамо комп'ютеру.