Общая постановка задачи линейного программирования

Задача, в которой требуется обратить в максимум (минимум) целевую функцию.

при условиях.

(I. 1.1.).

называется общей задачей линейного программирования в произвольной форме.

Вектор, удовлетворяющий ограничениям задачи линейного программирования называется ее решением или планом. Если при этом переменные еще и неотрицательны, то план является допустимым. Множество всех допустимых планов, образуют область допустимых решений (ОДР) задачи ЛП. Это выпуклое Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую линейную комбинацию (линейную оболочку). многогранное множество. Поэтому задачи ЛП являются частным случаем более общих задач выпуклого программирования.

Допустимый план, соответствующий крайней Две граничные точки некоторого отрезка, состоящего из граничных точек ОДР, называются крайними. Точка называется граничной для некоторого множества точек, если для любого сколь угодно малого в окрестности ее находятся и точки множества, и точки ему не принадлежащие. точке ОДР, является опорным планом, либо допустимым базисным решением задачи ЛП.

Допустимый план, обращающий в максимум (минимум) целевую функцию, называется оптимальным планом задачи ЛП.

Теорема (ЛП): Пусть допустимое множество задачи ЛП является многогранником (в обобщенном смысле). Если целевая функция принимает максимальное (минимальное) значение в некоторой точке множества, то она (точка) является крайней точкой для. Если целевая функция принимает максимальное (минимальное) значение более, чем в одной точке, то она принимает это же значение и в любой их выпуклой комбинации: Здесь внутренняя точка отрезка; граничная точка отрезка или крайняя точка ОДР; некоторый числовой параметр, «пробегающий» все значения из отрезка .