начення F зменшується. Збільшення змінної xm + 1 (зі збереженням нульових значень інших вільних змінних) відповідає переміщенню з початкової вершини уздовж деякого ребра.
Таке переміщення можна здійснювати до тих пір, поки базисні змінні відповідно до рівняннями (7.12) залишаються позитивними. При xm + 1=x (1) m + 1, xm + 2=0, ..., xn=0.
Формула (7.12) дає
xi=pi + qi, m + 1x (1) m + 1, i=1,2, ..., m.
Якщо всі коефіцієнти qi, m + 1 позитивні, то базисні змінні позитивні при будь-якому x (1) m + 1? 0. Це означає, що в цьому випадку x (1) m + 1 можна збільшувати безмежно (це можливо, якщо багатогранник допустимих значень необмежений). Тоді F необмежено убуває, т. Е. Завдання мінімізації не має рішення.
. Але на практиці цей випадок зустрічається рідко. Зазвичай рішення існує, і, відповідно, серед коефіцієнтів qi, m + 1 є негативні коефіцієнти. Якщо qi, m + 1, то умова позитивності xi призводить до умові:
x * m + 1 lt;-pi/qi, m + 1
(права частина цієї нерівності позитивна). Можливе найбільше значення xm + 1 є, таким чином,
x * m + 1=min {-pi/qi, m + 1} qi lt; 0.
Цьому значенню відповідає вершина, в яку ми потрапляємо, рухаючись уздовж ребра. Значення F в цій вершині менше, ніж у початковій вершині.
. Тут ми вибираємо як нових базисних змінних x1, x2, ..., xm - 1, xm + 1, висловлюємо їх і цільову функцію F через вільні змінні, і повторюємо всі обчислення і міркування, наведені вище. У результаті ми або виявимо, що ця вершина дає рішення, або перейдемо в нову вершину. Зрештою, ми отримаємо рішення. Можна довести, що кількість вершин, які доведеться перебрати при використанні цього методу, має порядок O (n), у той час як загальна кількість вершин має порядок O (2n).
В якості прикладу розглянемо задачу про розподіл ресурсів.
Приклад. Мається 300 кг металу, 100 м2 скла і 160 - людино-годин робочого часу; з них виготовляють вироби двох найменувань А і Б; вартість одного виробу А дорівнює 10 $, для його виготовлення потрібно 4 кг металу, 2 м2 скла і 2 людино-години робочого часу; вартість одного виробу Б дорівнює 12 $, для його виготовлення потрібно 5 кг металу, 1 м2 скла і 3 людино-години робочого часу; потрібно спланувати виробництво так, щоб призвести вироби з максимальною вартістю.
Рішення. Якщо x1, x2 є кількість виробів А і Б відповідно, то завдання така:
f (x1, x2)=10 · x1 + 12 · x2 ® max
при обмеженнях
· x1 + 5 · x2? 300
· x1 + x2? 100
· x1 + 3 · x2? 160
Наводимо задачу до канонічного вигляду. Для цього потрібно ввести 3 балансових змінних (по числу нерівностей) x3, x4, x5, і записати обмеження у вигляді
· x1 + 5 · x2 + x3=300
· x1 + x2 + x4=100 (7.14)
· x1 + 3 · x2 + x5=160
x1,2,3,4,5? 0
і замінити цільову функцію f на F:
F (x1, x2)=- f (x1, x2)=- 10 · x1- 12 · x2- 0 · x3 - 0 · x4 - 0 · x5 ® min (7.15)
Ми повинні вибрати 3 базисних змінних. Тут зручно взяти в якості базисних балансових змінні x3, x4, x5, оскільки вони легко виражаються з обмежень (7.14):
x3=300 - 4x1- 5x2
x4=100 - 2x1- x2 (7.16)
x5=160- 2x1- 3x2
Вважаючи вільні змінні x1, x2 рівними нулю, знаходимо початкову вершину (перше опорне рішення)
x (0) 1=0, x (0) 2=0, x (0) 3=300, x (0) 4=100, x (0) 5=160.
Значення F в цій вершині дорівнює 0. Підставляючи (7.16) в (7.15) знаходимо, що вид виразу (7.15) не змінюється. Оскільки коефіцієнти при вільних змінних негативні, то це рішення не оптимальне: значення F може бути зменшено шляхом збільшення як x1, так і x2.
Покладемо x2=0 і будемо збільшувати x1. У всіх співвідношеннях (7.16) коефіцієнти при x1 негативні, що призводить до оцінок
x1 lt; 300/4=75, x1 lt; 100/2=50, x1 lt; 160/2=80.
Таким чином, x1 можна збільшувати до 50, і при x1=50, x2=0 ми знаходимо нову вершину (друге опорне рішення).
x (1) 1=50, x (1) 2=0, x (1) 3=100, x (1) 4=0, x (1) 5=60.
Значення x3, x4, x5 тут знайдені з (7.16). Цільова функція F в цій вершині одно - 500; як і слід було очікувати, во...
