Задача линейного программирования

В общем случае задача линейного программирования записывается так, что ограничениями могут быть как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольными. Если все ограничения являются уравнениями, а все переменные неотрицательны, то задачу линейного программирования называют канонической.

Каноническая задача линейного программирования в координатной форме имеет вид

.

Каноническая задача линейного программирования в векторной форме имеет вид

.

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

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

Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на ее значение.

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

Наиболее известными методами решения задачи линейного программирования является графический метод и симплекс-метод. Теоретической основой линейного программирования являются две теоремы:

Теорема №1. Задача линейного программирования имеет оптимальное решение тогда и только тогда, когда целевая функция ограничена на допустимом множестве в направлении экстремума.

Теорема №2. Если экстремум целевой функции в задаче линейного программирования достигается, то он достигается в некоторой угловой точке допустимого множества.

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

Рассмотрим задачу линейного программирования:

Решение: На плоскости двух переменных построим допустимое множество , ограниченное линиями

А

В

D

О С

Прямая АВ задается уравнением , а прямая ВС уравнением . Допустимое множество является четырехугольником АВСО. По теореме №2 максимальное значение целевая функция достигает в одной из вершин четырехугольника: О(0,0), А(0,3), С(2,0). Координаты вершины В находим из системы уравнений: . Вычислим значение целевой функции в этих точках , , . Максимальное значение равно и достигается он при и .

Однако чаще данную задачу решают следующим способом. Целевая функция при фиксированных значениях является уравнением прямой линии . Построим прямую , она пройдет через начало координат. Все остальные прямые будут параллельны данной прямой, они называются линиями уровня.

Из курса аналитической геометрии известно, что коэффициенты при переменных в уравнении прямой являются координатами нормального вектора к этой прямой. Значит, нормальный вектор линий уровня в данном случае имеет координаты . Нормальный вектор показывает направление, в котором значения целевой функции возрастают. Поэтому в поисках максимума нужно двигать линию уровня в направлении нормального вектора.

Для данного случая, последней точкой в которой линия уровня коснется области допустимых решений будет точка . Значит, максимум функции .

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

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

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