3 Цілочислові та дискретні задачі лінійного програмування

Серед практично важливих задач пошуку умовного екстремуму лінійної функції важливе місце посідають задачі з вимогою цілочисловості всіх змінних або їх частини.

Якщо в задачах вибору оптимального асортименту мова йде про масове виробництво (гайок, болтів, цвяхів та ін.), умова цілочисловості кількості виробів не принципова, бо округлення великих чисел до цілих не надто змінює загальний результат. Однак для дрібно серійного чи унікального обладнання (літаків, ракет і т. ін.) ця умова дуже суттєва.

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

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

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

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

для обмежень

2. Задача про комівояжера

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

Математична модель цієї задачі майже повністю збігається з моделлю попередньої. Її розв’язок послідовність пунктів, через які проходить маршрут комівояжера. Для відображення цього маршруту застосовують змінні, які можуть набувати лише двох значень: , якщо комівояжер переїжджає з-го пункту в-й;, якщо переїзду між пунктами немає.

Тоді математична модель задачі про комівояжера має такий вигляд: мінімізувати

для обмежень

3. Задача про рюкзак

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

для обмежень

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

4. Задача про вибір транспортних засобів

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

Формалізуємо цю задачу. Нехай -м маршрутом можна перевезти пасажирів. Перевезення можна виконати різними типами транспортних засобів. Для кожного (-го) з них відомі такі характеристики:

1) – місткість (кількість місць);

2) – чисельність обслуги;

3) – витрати пального за певний період часу;

4) – прибуток від використання-го засобу на-му маршруті.

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

Математична модель цієї задачі має такий вигляд: максимізувати

для обмежень