1.2. Симплекс метод решения задач линейного программирования

_{Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.}

_{Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.}

_{Допустимым решением (допустимым планом) задачи ЛП, данной в стандартной форме, называется упорядоченное множество чисел (х1, х2, …, хn), удовлетворяющих ограничениям; это точка в n-мерном пространстве.}

_{Множество допустимых решений образует область допустимых решений (ОДР) задачи ЛП. ОДР представляет собой выпуклый многогранник (многоугольник).}

_{В общем виде, когда в задаче участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах.}

_{Базисным называется решение, при котором все свободные переменные равны нулю.}

_{Опорное решение — это базисное неотрицательное решение. Опорное решение может быть невырожденным и вырожденным. Опорное решение называется невырожденным, если число его ненулевых координат равно рангу системы, в противном случае оно является вырожденным.}

_{Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным и обозначается .}

_{Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.}

_{Симплекс-метод - это универсальный метод решения задач ЛП, представляющий собой итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области допустимых решений до тех пор, пока не достигнет оптимального значения.}

_{С его помощью можно решить любую задачу линейного программирования.}

_{В основу симплексного метода положена идея последовательного улучшения получаемого решения.}

_{Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худшее) значение до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).}

_{Таким образом, имея систему ограничений, приведенную к канонической форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении целевая функция, если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решением поступают так же, пока не отыщется решение, которое является оптимальным.}

_{Процесс применения симплексного метода предполагает реализацию трех его основных элементов:}

1. _{способ определения какого-либо первоначального допустимого базисного решения задачи;}

2. _{правило перехода к лучшему (точнее, не худшему) решению;}

3. _{критерий проверки оптимальности найденного решения.}

_{Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.}