Page 21 - 6449

Якщо задачі (1.22), (1.24) надати такого ж значення, як (1.1) – (1.3),
то додаткові змінні будуть мати певний економічний зміст: якщо вказані
змінні входять в оптимальний розв’язок, то їх значення буде
характеризувати величину залишків певного виду сировини при
оптимальній стратегії виробництва продукції. В той же час умови (1.23) та
(1.24) є досить сильними, вони суттєво обмежують клас задач, для яких
вказаний підхід взагалі може бути застосованим.
Метод штучного базису
Симплекс метод є найбільш універсальним методом розв’язання
ЗЛП. Аналогічно, метод штучного базису є найбільш універсальним при
побудові початкового опорного плану задачі. Ідея вказаного методу
полягає в наступному: вихідна ЗЛП замінюється іншою ЗЛП, причому це
робиться в такий спосіб, що розв’язок модифікованої та вихідної задачі
мають співпадати. При цьому модифікується не тільки система обмежень,

але й цільова функція задачі. Якщо модифікована задача має оптимальний
розв’язок, до якого входять елементи штучного базису, то це означає, що
початкова ЗЛП не має оптимального розв’язку. Алгоритм одержання
початкового опорного розв’язку за методом штучного базису є таким:
нехай задача лінійного програмування ставиться таким чином: знайти
Z  X C  X C  X C  ......... X C  min (1.25 )
1 1 2 2 3 3 n n
за умови:
 a 11  x 1  a 12  x 2 .........  a n 1  x n  b 1

 a 21  x 1  a 22  x 2  .........  a 2 n  x n  b 2
 (1.26)
 .......... .......... .......... .......... .......... ..........
 a  x  a  x .........  a  x  b
 m1 1 m2 2 mn n m
x  0, b  0,
i i
Зауважимо, що задача вже приведена до канонічного виду.
Спочатку в (1.26) вводяться штучні змінні, при цьому ці змінні не мають
жодного практичного змісту. Система (1.26) набуває при цьому такого
вигляду:

 a 11  x 1  a 12  x 2 .........  a n 1  x n  x n 1  b 1

 a 21  x 1  a 22  x 2 .........  a 2 n  x n  x n 2  b 2
 (1.27)
 .......... .......... .......... .......... .......... ..........
 a  x  a  x .........  a  x  x  b
 m1 1 m2 2 mn n n m m
x  , 0 b  , 0
i i
Очевидно, що системи (1.26) та (1.27) є різними системами, і
розв’язок задачі (1.25) з умовами (1.26) буде суттєво відрізнятися від
розв’язку цієї ж задачі з умовами (1.27). Тому необхідно модифікувати
цільову функцію (1.25) в такий спосіб, щоб розв’язок модифікованої задачі
з умовами (1.27) співпадав би з розв’язком початкової задачі (1.25), (1.26).
З цією метою залежно від характеру екстремуму (мінімум чи
максимум) по-різному модифікується цільова функція (1.25). Нехай

21