Симплекс метод

Метод  основан на закономерностях выведенных в геометрическом способе решения о том, что решения находятся на границах области допустимых решений. Тогда поиск решения сводится к перебору вершин, вычислению в каждой вершине значения целевой функции и выбору экстремального значения.

Для определения области допустимых решений нам нужно решить эту систему ограничений. Она состоит из двух уравнений с 4 неизвестными. Придавая двум неизвестным произвольные значения и решая систему относительно оставшихся мы будем получать решения ( не всегда допустимые). Интерес представляют то решение, когда лишние неизвестные полагаются равными нулю. Если оно имеется и единственное, то оно называется базисным. А если оно к тому же и допустимое, то называется базисным допустимым. Для задачи с n переменными, подчиненными m  ограничениям базисные решения могут быть получены, приравнивая нулю n-m переменных и решая m уравнений относительно оставшихся. Переменные приравненные нулю называются небазисными, остальные -базисными. Для нашего примера 2 небазисные переменные можно выбрать 6 способами. Базисные решения можно свести в таблицу, где каждое решение соответствует паре небазисных переменных (x₁x₂)(x₁x₃)(x₁x₄)(x₂x₃)(x₂x₄)(x₃x₄). Из этих 6 базисных решений только 4 являются допустимыми и они соответствуют вершинам многоугольника.

 Запишем таблицу для нашего случая

В основу построения симплекс метода положено наблюдение, что оптимальному решению всегда соответствует одна из угловых точек пространства решений. Процесс начинается с некоторой исходной допустимой угловой точки (обычно начала координат) и осуществляются последовательные переходы от одной допустимой точки к другой до тех пор, пока не будет найдено оптимальное решение. Решение в точке А называется начальным из нее осуществляется переход к некоторой смежной точке В или D. Выбор каждой последующей точки определяется двумя правилами:

1)каждая последующая точка должна быть смежной с предыдущей, т.е.переход идет по ребрам, по границам области решений

2)обратный переход к предшествующей точке производится не может.

Переменные х₁,х₂,х₃,х₄ можно упорядочить исходя из того, какое значение

( нуль или нет) имеет данная переменная в экстремальной точке.

Таблица

Можно заметить закономерность, что смежные экстремальные точки отличаются друг от друга только одной переменной в каждой группе ( нулевых и ненулевых переменных). Она полезна при построении вычислительной процедуры последовательного перехода от одной точки к смежной другой. Так как смежные точки отличаются только одной переменной, можно определить каждую последующую (смежную) экстремальную точку  путем замены одной из текущих небазисных переменных (нулевых) текущей базисной перемененной. Из решения 0 переход в точку С следует при увеличении небазисной переменной х₁ от исходного 0 значения до значения соответствующего точке С. В точке С переменная х₃ ( которая в точке 0 была базисной) автоматически обращается в 0 и становится небазисной переменной.

Следовательно, при переходе к соседней точке одна переменная выводится из базиса, а другая вводится в базис.