Основные формы задач линейного программирования

Получаемая на этапе структурирования линейная оптимизационная модель может быть представлена в различных формах задач линейного программирования:

Общей

Стандартной

Канони ческой.

Общая задача линейного программирования. (ЗЛП)

Требуется найти значения переменных х12,…хn удовлетворяющих ограничениям вида

Основные формы задач линейного программирования - student2.ru (1)

Основные формы задач линейного программирования - student2.ru

Основные формы задач линейного программирования - student2.ru

где Основные формы задач линейного программирования - student2.ru - постоянные числа и Основные формы задач линейного программирования - student2.ru .

И обращающих в минимум функцию

Основные формы задач линейного программирования - student2.ru (2)

Функция 2 называется целевой функцией ЗЛП

Определение: Упорядоченный набор х1*2*,…хn* называется опорным решением задачи линейного программирования (1)(2) если он удовлетворяет системе ограничений (1)

Упорядоченный набор х1*2*,…хn* называется оптимальным решением задачи линейного программирования (1)(2) если он удовлетворяет системе ограничений (1) и обращает в минимум целевую функцию (2)

Стандартная ЗЛП

Требуется найти значения переменных х12,…хn удовлетворяющих ограничениям вида

Основные формы задач линейного программирования - student2.ru (3)

Основные формы задач линейного программирования - student2.ru

И обращающих в минимум функцию

Основные формы задач линейного программирования - student2.ru (4)

Каноническая ЗЛП

Требуется найти значения переменных х12,…хn удовлетворяющих ограничениям вида

Основные формы задач линейного программирования - student2.ru (5)

Основные формы задач линейного программирования - student2.ru

где Основные формы задач линейного программирования - student2.ru - постоянные числа и Основные формы задач линейного программирования - student2.ru .

И обращающих в минимум функцию

Основные формы задач линейного программирования - student2.ru (6)

Замечания все 3 формы ЗЛП эквивалентны минимум целевой функции во всех з-х задачах совпадает.

Замечание к каноническому можно отнести любую задачу ЛП

Если целевая функция →max, то Ž = -Z будет минимизироваться

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

1+7х2≤45

Х3≥0

1+7х2+ х3≤45

Вопрос №8

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

Рассмотрим ЗЛП, зпданную в стандартной форме следущего вида:

с1х12х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х12х2 называется множество точек координатной плоскости (х12)координаты которой удовлетворяют неравенству с1х12х2=к где к -константа

справедливы следующие утверждения

Теорема 1

Если задача линейного программирования (1) (2) имеет оптимальное решение, то целевая функция (1) достигает оптимального значения (максимума или минимума) в одной из вершин многоугольника, заданного системой неравенств (2)

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

Теорема 2

Значение целевой функции (1) в точках линии уравнения увеличивается если линия уравнения перемещается параллельно начальному положению в направлении вектора нормали и уменьшается при перемещении в противоположном направлении.

Эти теоремы остаются справедливы для задач линейного программирования с любым конечным числом переменных.

Алгоритм графического метода решения ЗЛП

1 Построить многоугольник возможных (опорных) решений заданных системой ограничений (2)

2. Построить линию уравнения целевой функции (1) при к=0 (т.е. с1х12х2=0)

3. найти вектор нормали

4. Передвигают прямую целевую функцию c1x2 + c2x2 = 0 в направлении вектора N до крайней точки многоугольника решений.

5. Вычисляют координаты точки и значение целевой функции в этой точке.

Основные формы задач линейного программирования - student2.ru


При этом могут возникать следующие ситуации:

1. Целевая функция принимает экстремальное (минимальное или максимальное) значение в единственной точке А.
Основные формы задач линейного программирования - student2.ru

2. Целевая функция принимает экстремальное значение в любой точке отрезка АВ.
Основные формы задач линейного программирования - student2.ru

3. Целевая функция не ограничена сверху (при поиске на максимум) или снизу (на минимум)
Основные формы задач линейного программирования - student2.ru

4. Система ограничений задачи несовместна
Основные формы задач линейного программирования - student2.ru

Вопос № 9

Наши рекомендации