ДО тести (частина 2)

x₁ + 2x₂ → max; 

4x₁ - 2x₂ = 10;

3x₁ + 5x₂ = 25

x₁ + 2x₂ → min;

4x₁ - 2x₂ + x₃ = 10;

3x₁ + 5x₂ + x₄ = 25

 x₁ + 2x₂ - Mx₅ → max; 

4x₁ - 2x₂ + x₃ = 10;

3x₁ + 5x₂ - x₄ + x₅ = 25

x₁ + 2x₂ + Mx₅ → max;

4x₁ - 2x₂ - x₃ = 10; 

3x₁ + 5x₂ + x₄ = 25

x₁ + x₂ + x₃ = 1;

5x₁ + 4x₂ + 8x₃ → max;

7x₁ + 9x₂ + 3x₃ → max;

2x₁ + 5x₂ + 6x₃ → max

 x₁ + x₂ + x₃ → max; 

5x₁ + 7x₂ + 2x₃ ≤ 1; 

4x₁ + 9x₂ + 5x₃ ≤ 1;

8x₁ + 3x₂ + 6x₃ ≤ 1;

xᵢ ≥ 0, x₂ ≥ 0, x₃ ≥ 0

x₁ + x₂ + x₃ → min;

5x₁ + 4x₂ + 8x₃ ≥ 1;

7x₁ + 9x₂ + 3x₃ ≥ 1;

2x₁ + 5x₂ + 6x₃ ≥ 1;

xᵢ ≥ 0, x₂ ≥ 0, x₃ ≥ 0

x₁ + x₂ + x₃ → min; 

5x₁ + 7x₂ + 2x₃ ≥ 1; 

4x₁ + 9x₂ + 5x₃ ≥ 1; 

8x₁ + 3x₂ + 6x₃ ≥ 1;

xᵢ ≥ 0, x₂ ≥ 0, x₃ ≥ 0

Мінімальним

Ординарним

Максимальним

Пуасонівським

Прокляття розмірності

Складність обчислень

Неточність результатів

Обмеженість застосування

Знаходять мінімум

Знаходять максимум

Знаходять середнє значення

Знаходять оптимум

А₄ - А₁

А₄ - А₂

А₅ - А₁

А₅ - А₂

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

Будь-який набір значень змінних, що задовольняє обмеження

Точка максимуму цільової функції

 Множина всіх можливих розв'язків задачі

n!/(2m!(n-m)!)

C(n,m) = n!/(m!(n-m)!)

2^n

n×m

Якщо при переході від одного плану до іншого в стовпцю немає додатних елементів

Всі коефіцієнти цільової функції дорівнюють нулю

 Система обмежень суперечлива

Область допустимих рішень є пустою множиною

Квадратичного програмування

Теорії ігор

Лінійної оптимізації

Динамічного програмування

Експоненціальний розподіл часу обслуговування

Надходження заявок з обмеженої кількості

Пуасонівський потік заявок

Один канал обслуговування

max min αᵢ ≤ S ≤ min max αⱼ 

max min αᵢ ≥ S ≥ min max αⱼ 

max min αᵢ = S = min max αⱼ 

max min αᵢ > S > min max αⱼ

Мінімін

Максимін

Мінімакс

Максимакс

Лінійні обмеження

Нелінійні обмеження 

Цільові обмеження

Діапазон допустимих значень

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

кількість його додатних компонент дорівнює кількості базисних змінних

кількість його від'ємних компонент дорівнює кількості базисних змінних

кількість його комплексних компонент дорівнює кількості базисних змінних

Задача про розподіл ресурсів

Задача про призначення

Задача про дієту

Задача про перевезення

Заповнених клітинок у таблиці більше, ніж (m + n - 1)

Заповнених клітинок у таблиці менше, ніж (m + n - 1)

Заповнених клітинок у таблиці дорівнює (m + n - 1)

Заповнених клітинок у таблиці дорівнює (m × n - 1)

Cij = Vi + Uj 

Cij = Vj + Ui 

Cij = Vj - Ui

Cij = Vi - Uj

Вибрана оптимальна клітина небазисна, а всі інші клітини циклу базисні 

Вибрана неоптимальна клітина небазисна, а всі інші клітини циклу базисні

Всі клітини циклу є базисними

Всі клітини циклу є небазисними

Розв'язувати задачі комбінаторної оптимізації 

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

Знаходити оптимальні рішення лінійних задач

Аналізувати стохастичні процеси

Перший крок

Останній крок

Середній крок

Всі кроки одночасно

Сума програшів гравців дорівнює 1 

Сума виграшів гравців дорівнює 0

Сума виграшів більше нуля 

Сума програшів менше нуля

 β ≤ min max aᵢⱼ

β ≥ min max aᵢⱼ 

 β = min max aᵢⱼ

β > min max aᵢⱼ

Детермінованим 

Стаціонарним 

Періодичним

Випадковим

Найкоротший шлях з мінімальною тривалістю

Повний шлях з максимальною тривалістю

Середній шлях за тривалістю

Будь-який шлях у мережі

 Критерій очікуваного значення

Критерій мінімального ризику 

Максимізацію дисперсії

Критерій надійності

Використовують декілька цільових функцій

Існує декілька цільових функцій

Застосовують одну цільову функцію 

Не використовують цільові функції

На деякій ітерації небазисна змінна має в обмеженнях всі недодатні коефіцієнти, для задачі мінімізації виконується умова Δj = Zj – Cj < 0 (для задачі максимізації Δj > 0) і цю змінну необхідно ввести в базис 

На деякій ітерації небазисна змінна має в обмеженнях всі невід'ємні коефіцієнти, для задачі максимізації виконується умова Δj = Zj – Cj > 0 (для задачі мінімізації Δj < 0) і цю змінну необхідно ввести в базис 

Всі коефіцієнти в цільовій функції додатні

Система обмежень суперечлива

Набір значень змінних x₁, x₂, ..., xₙ, який задовольняє систему обмежень нерівностей ∑aᵢⱼxⱼ ≤ bᵢ, xⱼ ≥ 0

Набір значень змінних x₁, x₂, ..., xₙ, який задовольняє повній системі обмежень ∑aᵢⱼxⱼ = bᵢ, xⱼ ≥ 0

Оптимальне рішення задачі

Базисне рішення системи рівнянь

Знаходження мінімального розрізу мережі

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

Побудову остового дерева

Застосування жадібного алгоритму

План не є оптимальним

План потребує покращення 

Оптимальність транспортної задачі

Необхідно змінити базисні змінні

Можливість розбиття на етапи

Принцип оптимальності Беллмана

Цільова функція дорівнює ∑∑cᵢⱼxᵢⱼ 

Рекурентні співвідношення

Розв'язувати нелінійні задачі

Обмежити кількість розглядаємих базисних рішень

Знаходити всі можливі рішення

Працювати з цілочисельними змінними

Задача є виродженою

Задача має альтернативні оптимальні рішення

Задача має необмежені рішення

Задача не має рішення

допустимий діапазон зміни значення xᵢ* i=1,n оптимального рішення при незмінних коефіцієнтах цільової функції 

допустимий діапазон зміни коефіцієнтів цільової функції і отриманого оптимального рішення xᵢ* i=1,n при незмінному значенні цільової функції

допустимий діапазон зміни значення цільової функції при зміні значень обмежень

допустимий діапазон зміни коефіцієнтів цільової функції при незмінних значеннях xᵢ* i=1,n оптимального оптимального рішення

Додатнім надають додатні значення, а базисним – нульові

Небазисним надають нульові значення, а базисним – додатні 

Вільним надають нульові значення, а базисним – додатні

Всім змінним надають однакові значення