Загальна задача лінійного програмування

Загальну задачу лінійного програмування (ЗЛП) визначимо таким чином:

необхідно знайти такі значення змінних , при яких досягається максимум (мінімум) функції

(1.1.1)

і які задовольняють системі лінійних обмежень

(1.1.2)

де символ заміняє один із знаків ≤, =, ≥; - задані дійсні числа.

Співвідношення (1.1.2) називаються обмеженнями задачі лінійного програмування, а функція (1.1.1) — цільовою функцією задачі лінійного програмування. Сукупність точок , які задовольняють обмеженням (1.1.2), називається допустимою множиною (областю) ЗЛП, котру ми будемо записувати також у вигляді

.

Будь-яка точка називається допустимим розв’язком або планом задачі.

Допустимий розв’язок , що доставляє максимум (мінімум) цільової функції називається оптимальним розв’язком або оптимальним планом, або просто розв’язком ЗЛП.

Тобто, для будь-якого іншого допустимого розв’язку

,

якщо задача на максимум, і

,

якщо задача на мінімум.

Оптимальний розв’язок будемо записувати таким чином:

. При цьому будемо називати оптимальним значенням цільової функції або оптимумом ЗЛП.

Приклад 1.1. Знайти , при якому досягається максимум функції

при обмеженнях:
	(1.1.3)

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

Значення цільової функції відповідно дорівнюють та . Оскільки, , тоді допустимий розв’язок не є оптимальним. Щодо розв’язку , то без додаткових досліджень не можна визначити, чи буде він оптимальним чи ні.

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

Задачу лінійного програмування, яка має допустимі розв’язки (тобто система (1.1.2) сумісна), надалі будемо називати допустимою; задачу з несумісною системою обмежень — недопустимою.

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

Такі обмеження будемо називати прямими обмеженнями на змінні.

Методи розв’язування ЗЛП охоплюють велику кількість різноманітних конкретних варіантів, які відрізняються між собою як вимогами до цільових функцій (знайти максимум чи мінімум), так і структурою системи обмежень (самі лише нерівності або рівності чи поєднання рівностей і нерівностей). Один з варіантів ЗЛП узято за стандарт — канонічна форма задачі лінійного програмування (КЗЛП).

КЗЛП визначається таким чином:

знайти вектор , який максимізує лінійну функцію

(будемо це записувати так: )

і задовольняє системі обмежень

… , .

(1.1.4)

 

Позначимо ,

, , , ,

Тоді КЗЛП можна записати у матричній формі:

(1.1.5)

або у векторній формі

(1.1.6)

 

ЗЛП, записану у вигляді

(1.1.7)

будемо називати ЗЛП у стандартній формі, а задачу виду:

(1.1.8)

- ЗЛП у симетричній формі.

Всі форми ЗЛП є еквівалентними з точки зору розв’язку задачі.

Неважко бачити, що будь-яку ЗЛП можна привести до канонічного виду.

Задача мінімізації еквівалентна задачі максимізації функції , тобто еквівалентно

Обмеження-нерівності

перетворюються у обмеження-рівності за допомогою невід’ємних додаткових змінних:

Нарешті, якщо знак деяких змінних у ЗЛП не визначений, тоді робимо заміну цих змінних за правилом:

, причому

Приклад 1.2. Привести ЗЛП до канонічного виду.

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

Отже КЗЛП має вигляд:

Наведемо приклад запису лінійної математичної моделі задачі про оптимальне використання сировини.

Приклад 1.3. Із сировини трьох видів — , запаси яких відповідно дорівнюють 300, 450, 260 умовних одиниць, може бути виготовлена продукція двох видів: і . Для виготовлення одиниці продукції потрібно 10 одиниць сировини , 8 одиниць сировини , 6 одиниць сировини ; одиниці продукції — 7 одиниць , 14 одиниць та 13 одиниць сировини . Прибутки від реалізації одиниці продукції кожного виду становлять відповідно 35 грн., 50 грн.

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

Вихідні дані задачі наведено в табл.1.1.

Таблиця 1.1.

Вид сировини	Запас сировини	Витрати сировини для виробництва одиниці продукції
	300 () 450 () 260 ()	10 () 8 () 6 ()	7 () 14 () 13 ()
Прибуток	35 гр.	50 гр.

 

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