Поняття задачі лінійного програмування та різні форми її задання

Під задачею лінійного програмування в загальному вигляді розуміють задачу знаходження мінімуму (максимуму) лінійної функції від змінних на множині розв’язків системи лінійних нерівностей або лінійних рівнянь. Розглянемо це на конкретному прикладі.

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

Таблиця 3.1.

Сировина	Щомісячне надходження сировини (ум.од.)	Витрати сировини на одиницю кожного виробу
А1 А2 А3 А4
Прибуток від реалізації одиниці виробу
Кількість продукції

 

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

 

Складемо математичну модель цієї задачі, тобто опишемо її в термінах математичної символіки. Позначимо через відповідно ті кількості продукції асортиментів , які треба випустити, щоб мати максимальний прибуток від їх реалізації. Тоді на випуск продукції буде витрачено умовних одиниць сировини ; на випуск - , на випуск - , на випуск - умовних одиниць сировини . Витрати сировини не повинні перевищувати 1260 умовних одиниць. Матимемо таку лінійну нерівність: .

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

Прибуток від реалізації випущеної продукції (позначимо її через ), очевидно визначається так:

Дані системи лінійних нерівностей і лінійна функція визначають математичну модель розглянутої задачі: знайти такі значення змінних , які задовольняють систему отриманих лінійних нерівностей і перетворюють у максимум отриману лінійну функцію .

Тепер розглянемо чисельне розв’язання таких задач.

У наведеній задачі значення змінних повинні задовольняти систему лінійних нерівностей лише виду . Трапляються задачі, де значення змінних задовольняють систему нерівностей лише виду , або систему лінійних рівнянь, або мішану систему рівнянь і нерівностей.

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

і перетворюють в екстремум (максимум або мінімум) лінійну функцію

.

Цю функцію називають цільовою функцією, вона моделює поставлену в задачі мету.

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

З цього випливають три форми задач лінійного програмування:

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

2) стандартна (симетрична);

3) канонічна.

Загальна задача лінійного програмування подається у вигляді:

(3.1)

за умов:

(3.2)

…, . (3.3)

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

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

Вектор , координати якого задовольняють систему обмежень (3.2) та умови невід’ємності змінних (3.3), називається допустимим розв’язком (планом) задачі лінійного програмування.

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

Опорний план , називається невиродженим, якщо він містить точно додатних змінних, інакше він вироджений.

Опорний план , за якого цільова функція (3.1) досягає максимального (чи мінімального) значення, називається оптимальним розв’язком (планом) задачі лінійного програмування.

Стандартна (симетрична) задача лінійного програмування подається у вигляді: за умов:

, або .

…, .

Задачу (3.1)-(3.3) можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (3.2) всі невід’ємні, а всі обмеження є рівностями.

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

то останню завжди можна звести до рівності, увівши додаткову змінну :

.

Аналогічно обмеження виду

зводиться до рівності, віднімаючи від лівої частини додаткову змінну :

,

Така заміна нерівностей рівняннями за допомогою введення додаткових змінних не змінить розв’язку початкової задачі.

Задачі лінійного програмування можна розв’язувати графічно і аналітично.