Симплекс метод. Идея метода.
Этот метод - это последовательный перебор угловых точек, при которых значение целевой функции убывает от одной угловой точки к другой.
Рассмотрим задачи каноническую ЛП 4 min c, x R0 x Ax b, x?0 x?R0 Задача 4 -невырожденная, т.е. невырожденна каждая угловая точка ?R0. Итерационный шаг состоит в переходе от одной угловой точки х круговой точке х, при котором значение целевой функции убывает C, x C, x x -угловая точка.
Базис В образует, первые m столбцов матрицы А. Будем записывать матрицу А В,D , где В a1, a2 am. D an 1, an 2 an xT xвТ, xдТ , CТ CвТ, CдТ хВ - базис компоненты, хд - в небазисные компоненты. 2 Выбор столбца для ввода в базис. Известна угловая точка х хв 0, хд 0, det В ?0, Вхв в Рассмотрим векторы хк хк ? xв bak-1 ? k m 1,n 0 где ? является к - й компонентой вектора х. Если хв 0, то при малых ? 0 хk?0, т.к. Ахk в, то хk? R0 при малых ? 0. Кроме того C1 xk C1 x Cв, B-1ak -Ck C, x k ?к - определитель для любого к 1,n, причем при к 1,m ?к Cв, B-1ak -Ck Cв, Cк Cк Cк-Cк 0 Окончательно C1 xк C1x x k 1,n 3 Выбор столбца для ввода из базиса.
В зависимости от значков величины ?к и В-1ak возникает 3 случая. a Если для любого к 1,n будет ?к 0, то точка х - оптимальная. б Если найдется номер к?m 1 такой, что ?к 0 и В-1ak?0, то множество R0 неограниченно и функция С1х неограниченна снизу на R0. в Пусть найдутся такие к?m 1 и i?m, что ?к 0 и В-1akа 0. 4 Конечность метода. хk - новая угловая точка, причем C1k C1x 0 ?k C1 x. Из этого следует, что итерационный шаг симплексного метода состоит в таком переходе от базиса а1, а2 аs, аs 1, am к базису a1, a2 as-1, as 1 am, ak при котором целевая функция убывает, а значит, симплексный метод приводит к угловой точке х, в которой достигает минимума за конечное число итераций.