Введення
Лінійне програмування наука про методи дослідження та відшукання екстремальних значень лінійної функції, на параметри якої накладено лінійні обмеження.
Методи рішення задач лінійного програмування відносяться до обчислювальної математики. З ростом потужності комп'ютерів необхідність застосування витончених методів обчислення знижується, оскільки в багатьох випадках час рахунку перестає бути лімітуючим фактором, оскільки вельми мало (частки секунд). Можна виділити лише три таких методу.
1. Простий перебір. Візьмемо деякий багатовимірний паралелепіпед, в якому лежить багатогранник, що задається обмеженнями. Як його побудувати? Наприклад, якщо є обмеження типу 2Х 1 + 5Х 2 ≤ 10, то, очевидно, 0 ≤ Х 1 ≤ 10/2 = 5 і 0 ≤ Х 2 ≤ 10/2 = 5. Аналогічним чином від лінійних обмежень загального вигляду можна перейти до обмежень на окремі змінні. Залишається взяти максимальні межі за кожної змінної. Якщо багатогранник, що задається обмеженнями, необмежений, як було в задачі про дієту, можна схожим, але трохи більш складним чином виділити його "звернену" до початку координат частину, що містить рішення, і укласти її в багатовимірний паралелепіпед.
Проведемо перебір точок паралелепіпеда з кроком 1/10 n послідовно при n = 2,3, ..., обчислюючи значення цільової функції та перевіряючи наявність обмежень. З усіх точок, задовольняють обмеженням, візьмемо ту, в якій цільова функція максимальна. Рішення знайдено!
2. Спрямований перебір. Почнемо з точки, що задовольняє обмеженням (її можна знайти простим перебором). Будемо послідовно (або випадково - т.зв. метод випадкового пошуку) міняти її координати на певну величину О”, кожен раз в точку з більш високим значенням цільової функції. Якщо вийдемо на площину обмеження, будемо рухатися по ній (знаходячи одну з координат по рівнянню обмеження). Потім рух по ребру (коли два обмеження-нерівності переходять в рівності) ... Зупинка - у вершині лінійного багатогранника. Рішення знайдено! (Більш строго висловлюючись, знайдено з точністю до О”; якщо необхідно, в околиці знайденого рішення проводимо спрямований перебір з кроком О”/2, О”/4 і т.д.)
3. Симплекс-метод. Цей один з перших спеціалізованих методів оптимізації, націлений на вирішення завдань лінійного програмування, в той час як методи простого і спрямованого перебору можуть бути застосовані для вирішення практично будь-якої задачі оптимізації. Він був запропонований американцем Г. Данцигом в 1951 р. Симплекс-метод полягає в просуванні по опуклого багатогранника обмежень від вершини до вершини, при якому на кожному кроці значення цільової функції поліпшується до тих пір, поки не буде досягнутий оптимум.
Такий багатогранник обмежень можна назвати функцією, яка для задачі лінійного програмування є цільовою, а обмеження, записувані у вигляді лінійних рівнянь або нерівностей, називаються системою обмежень.
Загальним завданням для лінійного програмування є знаходження неотрицательного рішення системи лінійних обмежень, яке оптимізує лінійну цільову функцію:
max (min)
Виділяють дві форми завдань лінійного програмування:
1. стандартна форма
2. канонічна форма
Планом називається вектор x = (x 1 , x 2 , ..., x n ) R n , що задовольняє умовам (1) - (3). Безліч всіх допустимих рішень задачі будемо позначати через X. Допустиме рішення x X, при якому цільова функція досягає найбільшого (max) або найменшого значення (min), називається оптимальним рішенням задачі лінійного програмування. Базисне ненегативне рішення x = (x 1 , x 2 , ..., x r , 0, ..., 0), де r-ранг системи обмежень, називається опорним рішенням.
1. Звичайні і модифіковані Жорданових виключення
Для розгляду суті симплекс методу в задачах лінійного програмування необхідно зупинитися на понятті В«звичайні й модифіковані Жорданових виключенняВ».
Нехай дана система з m лінійних функцій y 1 , ..., y m від n невідомих x 1 , x 2 , ..., x n : y i = ОЈ a ij x j (1.1), де a ij - постійні величини (i = 1, m; j = 1, n).
Уявімо систему (1.1) в формі таблиці 1.3, яку в подальшому будемо називати Жорданових.
Таблиця 1.3
x 1 ... x j ... X s ... x n
y 1 =
...
y i =
...
y j =
...
y m =
a 11 ... a 1j ... A 1s ... a 1n
........................................
a i1 ... a ij ... A is ... a in
.......................................
a k1 ... a k j ... A ks ... A kn
.......................................
a m1 ... a mj ... a ms ... a mn
Перейдемо до звичайного запису системи шляхом множення елементів a ij i-го рядка на відповідні невідомі x j , що стоять у верхній заголовної рядку, потім отримані твори складаємо і прирівнюємо до y i .
Вибираємо з (1.1) k-е рівняння y k = ОЈa kj x j (1.2 ), і, покладемо, коефіцієнт при x s відмінний від нуля. Висловимо x s :
x s = ОЈ
Така операція називається кроком жорданова виключення виробленим над табл.1.3 з дозволяючим елементом a ks з k-й роздільною рядком і s-му дозволяючим стовпцем. Далі для з'ясування як зміняться інші елементи у табл. 1.3. підставляємо значення x s з в інші рівності системи
Система запишеться у вигляді
y i = ОЈ (i = 1, ..., m)
перетворити систему переписуємо у формі Жорданових таблиці (табл. 1.4)
Таблиця 1.4
x 1 ... y до ... x n
y 1 =
...
x s =
...
y m =
b 11 ...... b 1n
...........................
......
...........................
b m1 ...... b mn
Зіставляючи табл. 1.3 і 1.4, необхідно звернути увагу, що крок звичайного жорданова виключення з дозволяючим елементом a ks переводить одну таблицю в іншу за схемою з чотирьох правил:
1. дозволяє елемент (РЕ) замінюється зворотною величиною;
2. інші елементи роздільної рядка діляться на РЕ та міняють знаки;
3. інші елементи дозволяючого стовпця діляться на РЕ;
4. інші елементи обчислюються за формулою (1.5).
На практиці зручно користуватися правилом прямокутника:
..................................
......... a ij ......... a is .........
.................................
........ a kj ......... a ks .........
.................................
Тоді з...
