Задача линейного программирования
В общем случае задача линейного программирования записывается так, что ограничениями могут быть как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольными. Если все ограничения являются уравнениями, а все переменные неотрицательны, то задачу линейного программирования называют канонической.
Каноническая задача линейного программирования в координатной форме имеет вид
.
Каноническая задача линейного программирования в векторной форме имеет вид
.
Так как в большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных, а при составлении математических моделей экономических задач ограничения формируются в основном в системы неравенств, необходимо выполнить переход от системы неравенств к системе уравнений. Это можно проделать следующим образом.
К левой части неравенства 
прибавляют некоторую величину 
такую, чтобы неравенство превратилось в равенство 
, здесь 
. Переменная величина 
называется дополнительной переменной.
Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на ее значение.
Если возникает необходимость перейти в задаче от нахождения минимума к нахождению максимума и наоборот, достаточно изменить знаки всех коэффициентов целевой функции на противоположные.
Наиболее известными методами решения задачи линейного программирования является графический метод и симплекс-метод. Теоретической основой линейного программирования являются две теоремы:
Теорема №1. Задача линейного программирования имеет оптимальное решение тогда и только тогда, когда целевая функция ограничена на допустимом множестве в направлении экстремума.
Теорема №2. Если экстремум целевой функции в задаче линейного программирования достигается, то он достигается в некоторой угловой точке допустимого множества.
Графический метод решения задач линейного программирования
Рассмотрим задачу линейного программирования: 
Решение: На плоскости двух переменных 
построим допустимое множество 
, ограниченное линиями 
 |
А
В
D
О С 
Прямая АВ задается уравнением 
, а прямая ВС уравнением 
. Допустимое множество является четырехугольником АВСО. По теореме №2 максимальное значение целевая функция достигает в одной из вершин четырехугольника: О(0,0), А(0,3), С(2,0). Координаты вершины В находим из системы уравнений: 
. Вычислим значение целевой функции в этих точках 
, 
, 
. Максимальное значение равно 
и достигается он при 
и 
.
Однако чаще данную задачу решают следующим способом. Целевая функция при фиксированных значениях 
является уравнением прямой линии . Построим прямую , она пройдет через начало координат. Все остальные прямые будут параллельны данной прямой, они называются линиями уровня.
Из курса аналитической геометрии известно, что коэффициенты при переменных в уравнении прямой являются координатами нормального вектора к этой прямой. Значит, нормальный вектор линий уровня в данном случае имеет координаты 
. Нормальный вектор показывает направление, в котором значения целевой функции возрастают. Поэтому в поисках максимума нужно двигать линию уровня в направлении нормального вектора.
Для данного случая, последней точкой в которой линия уровня коснется области допустимых решений будет точка . Значит, максимум функции 
.
Если в задаче нужно было найти минимум линейной функции, то линию уровня надо было двигать в сторону, противоположную направлению нормального вектора.
Линия уровня, имеющая общие точки с областью допустимых решений и расположенная так, что область допустимых решений целиком находится по одну сторону от данной линии, называется опорной прямой.
Из курса математического анализа следует, что если допустимое множество в задаче линейного программирования ограничено, то целевая функция имеет на нем и минимум и максимум. Если же допустимое множество неограниченно, то экстремума может и не быть, тогда задача линейного программирования не имеет решения.