Предположим, что задана некоторая система из m-линейных неравенств (или уравнений) с n переменными х1, х2, ..., хn. Система неравенств в случае совместности определяет некоторое выпуклое множество в n-мерном пространстве, ограниченное или бесконечное (многогранник решений).
Допустим далее, что нам задана некоторая линейная форма от этих переменных, определяющая функцию цели:
¦=c1x1+c2x2+ ... +cnxn
В каждой точке выпуклого множества, т.е. для каждого решения нашей системы, линейная форма ¦ принимает определенное значение. Возникает вопрос: в каких точках выпуклого множества линейная форма ¦ достигает своего наибольшего и наименьшего значения, если, конечно, такие существуют? Решение общей задачи линейного программирования сводится, таким образом, к нахождению точек выпуклого множества, в которых заданная линейная форма достигает оптимального значения, и мы ищем такие точки (х1, х2, ..., хn), координаты которых неотрицательны. Сформулируем одно важное утверждение, облегчающее решение задачи.
þ В тех случаях, когда множество решений задачи линейного программирования образует выпуклый многогранник, линейная форма достигает оптимального значения в одной из его вершин, в связи с чем последние и называются экстремальными точками.
В общем случае, линейная форма ¦=c1x1+c2x2+ ... +cnxn задает гиперплоскость в n-мерном пространстве. При ¦=0 эта гиперплоскость проходит через начало координат. Затем передвигаем эту плоскость параллельно самой себе в направлении вектора P перпендикулярно к этой плоскости. Первая из вершин, в которой линейная форма (гиперплоскость) встретит выпуклый многогранник, будет точкой, в которой линейная форма достигает наименьшего значения, а последняя из вершин - точкой, в которой линейная форма достигает наибольшего значения.
Может случиться, что гиперплоскость окажется параллельной одной из граней или ребер выпуклого многогранника, и тогда линейная форма ¦ достигает своего наименьшего или наибольшего значения в любой точке, лежащей на этом ребре. Но и тогда она достигает эти значения в вершине, лежащей на этом ребре.
Существуют различные методы решения задач линейного программирования. Одним из наиболее простых и наглядных методов решения является графический метод. Этот метод позволяет решать задачи, которые приводят к системам уравнений с двумя или тремя переменными. Большинство задач линейного программирования приводит к системам линейных неравенств с большим числом переменных. Эти задачи решаются симплексным методом.