Page 165 - 5637

РОЗДІЛ 8

ОПТИМІЗАЦІЯ ДИСКРЕТНИХ ПАРАМЕТРІВ СИСТЕМИ

УПРАВЛІННЯ

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

Сучасна інженерна практика висуває величезну кількість задач оптимізації

дискретних параметрів систем [67 – 73]. Всі ці завдання об'єднуються загальною

постановкою і можуть бути зведені до завдань цілочисельного програмування,

загальне формулювання яких наступна.

Нехай – -мірний ( ≥ 1) евклідів простір, – його цілочисельна решітка,

тобто найбільшу підмножина , що складається з векторів = { , … , } , всі

компоненти { , = 1, … , } яких цілочисельні. Задані функціонал ( ) і деякий

підмножина решітки . Ставиться завдання знаходження такого , що

⋳ ⊆ , (8.1)

= opt ( ), (8.2)
⋳
Тут opt – операція визначення мінімуму або максимуму. Надалі без обмеження

спільності будемо вважати, що наше завдання – мінімізація функціоналу ( ). Безліч

– безліч допустимих значень аргументу, задається, як правило, за допомогою

сукупності обмежень виду

( ), … , ( ) ≤ 0, ≥ 0. (8.3)

Найбільш поширені класи задач цілочисельного програмування (8.1) – (8.3) такі:

1. Завдання лінійного програмування – задачі (8.1) – (8.3), у яких

( ) = і ( ) = ,

де і ( = 1, … , ; = 1, … , ) задані; = { , … , } . В разі нелінійності хоча б

однієї з функцій ( = 1, … , ) задача (8.1) – (8.3) стає завданням нелінійного

цілочисельного програмування.
2. Завдання з булевими змінними = 2 і = 0,1 ( = 1, 2).

3. Комбінаторні задачі цілочисельного програмування – рішення задачі (8.1) –

(8.3) шукається на кінцевому безлічі завдання функціонала (∙).