емальних завдань, можна укласти, що на принциповому рівні пошук їх рішень зводиться до послідовного перебору кутових точок безлічі допустимих планів або, що те ж саме, перебору відповідних допустимих базисних планів. Засобом вирішення даної проблеми з'явилися прикладні оптимізаційні методи, засновані на послідовному, цілеспрямованому переборі базисних планів ЗЛП.
Класичним методом вирішення ЗЛП став симплекс-метод, що отримав також у літературі назву методу послідовного поліпшення плану (впорядкованість забезпечується монотонним зміною значення цільової функції при переході до чергового плану), розроблений в 1947 р. американським математиком Джорджем Данцигом.
Нехай стоїть завдання максимізації
(2.1)
за умов
, (2.2)
X j Ві 0, j = 1, ..., n (2.3)
Припустимо, що нам вдалося знайти опорний план X 0 , в якому, наприклад, перші m компонент відмінні від нуля:
X 0 = (X 1 0 , X 2 0 , ..., X m 0 , 0, ..., 0), (2.4)
і відповідний базис Б = (A 1 , A 2 , ..., A m ).
Спробуємо вибрати іншу систему базисних векторів з метою побудови нового опорного плану, в якому k-я змінна (k> m) приймає значення Q> 0:
X (Q) = (X 1 (Q), X 2 (Q), ..., X m (Q), 0, ..., Q, ... 0) (2.5)
Підставляючи (2.4) в (2.2), маємо
(2.6)
Підставивши (2.5) в (2.2), отримуємо
(2.7)
Розкладемо вектор A k по векторах вихідного базису
(8)
У загальному випадку для отримання коефіцієнтів такого розкладу доведеться вирішувати систему m рівнянь з m невідомими, яка має єдине рішення, оскільки базисні вектори лінійно незалежні і відповідна матриця має ненульовий визначник. Зауважимо, що в ситуації, коли базисні вектори є одиничними (утворюють одиничну матрицю), шукані коефіцієнти збігаються з компонентами вихідного вектора; тому надалі ми віддамо перевагу працювати з одиничним базисом.
Підставляючи (2.6) і (2.8) в (2.7), отримуємо
, (2.9)
звідки маємо
(2.10)
Оскільки система рівнянь (2.10) має єдине рішення, то отримуємо уявлення перших m компонент нового плану
(2.11)
Природно зажадати неотрицательность компонент нового плану. Так як порушення неотрицательности в (2.11) може виникнути лише при Z jk > 0, то значення Q потрібно взяти не перевищує найменшого з відносин до позитивним Z jk .
Якщо до того ж врахувати, що число позитивних (базисних) компонент опорного плану має залишатися рівним m, то одну з перших m (ненульових) компонент вихідного плану звертаємо в нуль вибором
(2.12)
Підставляючи...
