Тема 1. 2. Елементарні перетворення лінійних моделей

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

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

Для побудови ЕММ слід визначити список основних змінних, функцію мети і систему найсуттєвіших обмежень. Якщо ФМ і обмеження є лінійними функціями, то ЕММ називається лінійною. При відсутності інших застережень будемо вважати всі моделі, які розглядаються нижче, лінійними і детермінованими.

Загальна лінійна ЕММ має вигляд:

 

f(x) = c_j x_j ® max (1.15)

a_ij x_j £ b_i, i Î (1.16)

a_ij x_j ³ b_i, i Î (1.17)

x_j ³ 0, (1.18)

де c_j, a_ij, b_i - задані сталі величини (b_i ³ 0);

x_j - шукане значення змінної величини;

(1.15) - функція мети;

(1.16)‑(1.18) - обмеження, що визначають множину допустимих розв’язків задачі.

 

Розв’язком (допустимим розв’язком) задачі (1.15‑(1.18) називається вектор X=(x₁,x₂,...,x_n), для якого виконуються умови (1.16)‑(1.18). Оптимальним буде допустимий розв’язок, при якому ФМ досягає максимального значення.

 

Канонічною (основною) називається така модель:

 

f(x) = c_j x_j ® max, (1.19)

a_ij x_j = b_i, i Î , (1.20)

x_j ³ 0. (1.21)

 

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

Перехід від загальної до канонічної моделі здійснюється за допомогою додаткових невід”ємних змінних S_i, U_i:

a_ij x_j + S_i = b_i, i Î (1.16¢)

a_ij x_j - U_i = b_i, i Î (1.17¢)

 

Якщо в умові певної задачі є змінна V, на яку не поширюється умова невід”ємності типу (1.21), то для зведення задачі до лінійного виду слід в систему обмежень додатково включити таку умову:

 

 

V = V⁺ - V^-, (1.22)

 

де V⁺; V^- ³ 0.

 

В лінійній задачі можна без зміни суті задачі поміняти напрям оптимізації, тобто здійснити перехід від задачі на пошук максимуму f(x) до задачі на знаходження мінімуму f(-x), оскільки

 

max f(x) = ‑min f(-x)

 

Розглянемо типову задачу виробничого менеджменту - планування оптимального випуску продукції (див.приклад 2 теми1). Будемо вважати, що на підприємстві існує можливість виробництва певної сукупності виробів, кожний з яких користується попитом споживачів. Умови випуску продукції можна описати за допомогою обмеження на виробничі ресурси:

 

a_ij x_j £ b_i, i Î (1.23)

 

де i - індекс виду ресурсу;

j - індекс виду продукції;

x_j - шукана кількість випуску продукції j-го виду;

b_i - розмір ресурсного забезпечення.

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

 

c_rj x_j ³ C_r, r Î (1.24)

 

де c_rj - значення r-го показника;

C_r - плановий рівень показника.

Попит на продукцію врахуємо шляхом включеня в модель обмеження на границі випуску виробів:

 

d_j £ x_j £ D_j, j Î (1.25)

де d_j, D_j - нижня, верхня межі випуску продукції j-го виду.

В якості функції мети будемо розглядати “максимум прибутку”:

 

f(x) = p_j x_j ® max (1.26)

 

де p_j - прибуток на одиницю j-го виробу.

 

Якщо для початкового розв”язку X=(d₁; d₂;...d_n) умова (1.23) не виконується, то можна стверджувати про первісну неузгодженість умов задачі (1.23)‑(1.26). Якщо для початкового розв”язку X=(D₁; D₂;...D_n) умова (1.24) не справджується, то можна стверджувати про наявність вторинної неузгодженості умов задачі. Первісна неузгодженість викликається невідповідністю між встановленими нижніми межами випуску продукції і розміром відповідного ресурсногогo забезпечення. Вторинна неузгодженість зумовлюється невідповідністю між встановленими верхніми межами випуску продукції і плановим рівнем показників C_r.

Зведемо задачу (1.23)‑(1.26) до канонічного виду:

 

f(x) = p_j x_j + 0·S_i + 0·U_r + (0·S_j + 0·U_j) ® max, (1.27)

a_ij x_j + S_i = b_i, i Î , (1.28)

C_rj x_j - U_r = C_r, r Î , (1.29)

x_j - S_j = d_j, j Î , (1.30)

x_j + U_j = D_j, j Î , (1.31)

x_j, S_i, U_r, S_j, U_j ³ 0. (1.32)

 

Додаткова змінна S_i характеризує використання ресурсу i-го виду. Якщо для розв’язку X^o значення S_i=0, то це означає, що в умові задачі і-ий ресурс використаний повністю.

Додаткова змінна U_r характеризує розмір перевищення планового завдання по r-му показнику; S_j - розмір випуску продукції j-го виду понад нижню межу d_j; U_j - розмір відхилення від верхньої межі виробництва продукції D_j.

Якщо умови задачі не узгоджені, то це означає, що не існує таких невід’ємних додаткових змінних типу (1.32), при яких справджуються обмеження (1.28)‑(1.31). Якщо ж додаткові змінні приймають від’ємні значення, то задача (1.27)‑(1.32) виходить за межі задачі лінійного програмування. Скористаємося стандартною заміною змінних, за допомогою якої задача з неузгодженими умовами буде завжди мати допустимий розв’язок. З цією метою виконаємо такі перетворення:

 

S_i = S_i⁺ - S_i^-, U_r = U_r⁺ - U_r^-, (1.33)

S_j = S_j⁺ - S_j^-, U_j = U_j⁺ - U_j^-, (1.34)

де S_i⁺ - характеризує залишок ресурсу;

S_i^- - нестачу ресурсу;

U_r⁺ - розмір перевищення планового значення r - го показника;

U_r^- - розмір недосягнення планового рівня показника;

S_j⁺ - розмір випуску продукції понад нижню межу;

S_j^- - розмір недосягнення нижньої межі випуску продукції;

U_j⁺ - розмір відхилення від верхньої межі випуску;

U_j^- - розмір перевищення випуску продукції понад верхню межу.

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