1.2 Основные методы решения задач линейного программирования
Основная
задача линейного программирования
(ОЗЛП) ставится следующим образом:
Имеется ряд переменных
.
Требуется найти такие их неотрицательные
значения, которые удовлетворяли бы
системе линейных уравнений:
{1.1}
и, кроме того, обращали бы в минимум линейную целевую функцию (ЦФ)
Очевидно, случай, когда ЦФ нужно обратить не в минимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию
Допустимым
решением
ОЗЛП называют любую совокупность
переменных
,
удовлетворяющую уравнениям (1.1).
Оптимальным решением называют то из допустимых решений, при котором ЦФ обращается в минимум.
На практике ограничения в задаче линейного программирования часто заданы не уравнениями, а неравенствами. В этом случае можно перейти к основной задаче линейного программирования.
Рассмотрим задачу линейного программирования с ограничениями-неравенствами, которые имеют вид
{1.2}
и
являются линейно-независимыми. Последнее
означает, никакое из них нельзя представить
в виде линейной комбинации других.
Требуется найти
,
которые удовлетворяют
неравенствам и обращают в минимум
Введём уравнения:
{1.3}
где
-
добавочные переменные, которые также
как и
являются неотрицательными.
Таким
образом, имеем общую задачу линейного
программирования - найти неотрицательные
,
чтобы
они удовлетворяли системе уравнений
(1.3) и обращали в минимум
.
Коэффициенты
в формуле (1.3) перед
равны нулю.
2. Графический метод решения задачи линейного программирования
2.1. Теоретическое введение
Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.
Каждое
из неравенств задачи линейного
программирования (1.2) определяет на
координатной плоскости
некоторую полуплоскость (рис.2.1), а
система неравенств в целом – пересечение
соответствующих плоскостей. Множество
точек пересечения данных полуплоскостей
называется областью
допустимых решений
(ОДР). ОДР всегда представляет собой
выпуклую
фигуру,
т.е. обладающую следующим свойством:
если две точки А и В принадлежат этой
фигуре, то и весь отрезок АВ принадлежит
ей. ОДР графически может быть представлена
выпуклым многоугольником, неограниченной
выпуклой многоугольной областью,
отрезком, лучом, одной точкой. В случае
несовместности системы ограничений
задачи (1.2) ОДР является пустым множеством.
Все вышесказанное относится и к случаю, когда система ограничений (1.2) включает равенства, поскольку любое равенство
можно представить в виде системы двух неравенств (см. рис.2.1)
ЦФ
при фиксированном значении
определяет на плоскости прямую линию
.
Изменяя значения L, мы получим семейство
параллельных прямых, называемых линиями
уровня.
Это
связано с тем, что изменение значения
L повлечет изменение лишь длины отрезка,
отсекаемого линией уровня на оси
(начальная ордината), а угловой коэффициент
прямой
останется постоянным (см.рис.1). Поэтому
для решения будет достаточно построить
одну из линий уровня, произвольно выбрав
значение L.
Вектор
с координатами из коэффициентов ЦФ при
и
перпендикулярен к каждой из линий уровня
(см. рис.2.1). Направление вектора
совпадает
с направлением
возрастания
ЦФ, что является важным моментом для
решения задач. Направление
убывания
ЦФ противоположно направлению вектора
.
Суть
графического метода заключается в
следующем. По направлению (против
направления) вектора
в ОДР производится поиск оптимальной
точки
.
Оптимальной считается точка, через
которую проходит линия уровня
,
соответствующая наибольшему (наименьшему)
значению функции
.
Оптимальное решение всегда находится
на границе ОДР, например, в последней
вершине многоугольника ОДР, через
которую пройдет целевая прямая, или на
всей его стороне.
При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.
Рисунок 1 Геометрическая интерпретация ограничений и ЦФ задачи.