Основные формы задач линейного программирования
Получаемая на этапе структурирования линейная оптимизационная модель может быть представлена в различных формах задач линейного программирования:
Общей
Стандартной
Канони ческой.
Общая задача линейного программирования. (ЗЛП)
Требуется найти значения переменных х1,х2,…хn удовлетворяющих ограничениям вида
(1)
где - постоянные числа и .
И обращающих в минимум функцию
(2)
Функция 2 называется целевой функцией ЗЛП
Определение: Упорядоченный набор х1*,х2*,…хn* называется опорным решением задачи линейного программирования (1)(2) если он удовлетворяет системе ограничений (1)
Упорядоченный набор х1*,х2*,…хn* называется оптимальным решением задачи линейного программирования (1)(2) если он удовлетворяет системе ограничений (1) и обращает в минимум целевую функцию (2)
Стандартная ЗЛП
Требуется найти значения переменных х1,х2,…хn удовлетворяющих ограничениям вида
(3)
И обращающих в минимум функцию
(4)
Каноническая ЗЛП
Требуется найти значения переменных х1,х2,…хn удовлетворяющих ограничениям вида
(5)
где - постоянные числа и .
И обращающих в минимум функцию
(6)
Замечания все 3 формы ЗЛП эквивалентны минимум целевой функции во всех з-х задачах совпадает.
Замечание к каноническому можно отнести любую задачу ЛП
Если целевая функция →max, то Ž = -Z будет минимизироваться
Кроме того от любого ограничения неравенства можно перейти к ограничению равенства путем введения фиктивной неотрицательной переменной
3х1+7х2≤45
Х3≥0
3х1+7х2+ х3≤45
Вопрос №8
Графический метод решения задач линейного программирования.
Рассмотрим ЗЛП, зпданную в стандартной форме следущего вида:
с1х1+с2х2 →max (1)
a11x1+a12x2≤ b1
a21x1+a22x2≤ b2 (2)
am1x1+am2x2≤ bm
x1≥0 x2 ≥0
cj, bi, aij –некотрые действительные числа
Из курса математики нам известно, что множество решений неравенства a11x1+a12x2≤ b1
представляет собой одну из полуплоскостей вместе с прямой заданной уравнением a11x1+a12x2= b1
Множество решений системы неравенств (2) представляют собой выпуклый многоугольник
Для уравнения прямой ai1x1+ai2x2≤ bi упорядоченная пара чисел (ai1, ai2) ЗАДАЕТ КООРДИНАТЫ ВЕКТОРА НОРМАЛИ К ПРЯМОЙ
Определение:
Линии уравнения Z= с1х1+с2х2 называется множество точек координатной плоскости (х1,х2)координаты которой удовлетворяют неравенству с1х1+с2х2=к где к -константа
справедливы следующие утверждения
Теорема 1
Если задача линейного программирования (1) (2) имеет оптимальное решение, то целевая функция (1) достигает оптимального значения (максимума или минимума) в одной из вершин многоугольника, заданного системой неравенств (2)
Если целевая функция принимает оптимальное значение более чем в 1 вершине, то она достигает оптимума значения в любой точке прямой соединяющей эти вершины.
Теорема 2
Значение целевой функции (1) в точках линии уравнения увеличивается если линия уравнения перемещается параллельно начальному положению в направлении вектора нормали и уменьшается при перемещении в противоположном направлении.
Эти теоремы остаются справедливы для задач линейного программирования с любым конечным числом переменных.
Алгоритм графического метода решения ЗЛП
1 Построить многоугольник возможных (опорных) решений заданных системой ограничений (2)
2. Построить линию уравнения целевой функции (1) при к=0 (т.е. с1х1+с2х2=0)
3. найти вектор нормали
4. Передвигают прямую целевую функцию c1x2 + c2x2 = 0 в направлении вектора N до крайней точки многоугольника решений.
5. Вычисляют координаты точки и значение целевой функции в этой точке.
При этом могут возникать следующие ситуации:
1. Целевая функция принимает экстремальное (минимальное или максимальное) значение в единственной точке А.
2. Целевая функция принимает экстремальное значение в любой точке отрезка АВ.
3. Целевая функция не ограничена сверху (при поиске на максимум) или снизу (на минимум)
4. Система ограничений задачи несовместна
Вопос № 9