Линия уровня целевой функции задачи линейного программирования

15 Что называется линией уровня целевой функции?

Линией уровня функции называется множество точек из ее области определения, в которых функция принимает одно и то же фиксированное значение. Градиентом функции f(x) называется вектор указывающий направление наиболее быстрого возрастания функции, и, стало быть, ориентированный перпендикулярно линиям уровня. Для линейной функции двух переменных линия уровня представляет собой прямую, перпендикулярную вектору с, который служит градиентом данной функции. Следовательно, если линия уровня определяется уравнением f(x)=c1x1+ c2x2 =const, то этот вектор имеет вид и указывает направление возрастания функции.

С₁Х₁ + С₂Х₂ = const – линия уровня функции , перпендикулярную вектору-градиенту

16 В каких случаях при решении ЗЛП графическим методом можно убедиться в ее неразрешимости? Задача линейного программирования называется разрешимой, если она имеет хотя бы одно оптимальное решение. У неразрешимой задачи или пуста область допустимых решений, или целевая функция не ограничена.

Если допустимая область решений Р представляет собой неограниченную область и прямая при движении в направлении вектора (или противоположном ему) не покидает Р, то в этом случае не ограничена сверху (или снизу), т.е. (или ).

17 Что означает разрешимость ЗЛП при графическом методе ее решения?

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

ЗЛП разрешима, то есть существует такая точка , что .

18 Запишите КЗЛП в алгебраической форме.

19 Запишите КЗЛП в векторно-матричной форме.

20 Дайте определение опорного плана КЗЛП.

_{Опорным планом (ОП) задачи линейного программирования будем называть такой ее план, который является базисным решением системы линейных уравнений} _.

_{(План или допустимое решение задачи линейного программирования – вектор пространства Еn, компоненты которого удовлетворяют функциональным и прямым ограничениям задачи.)}

_{Согласно определению и предположению о том, что} _r₍_A_{) =} _m , всякому опорному плану задачи линейного программирования (как и всякому базисному решению системы линейных уравнений ) соответствует базисная подматрица В порядка m матрицы А и определенный набор m базисных переменных системы линейных уравнений .

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

Отметим, что базисные компоненты опорного плана неотрицательны; остальные n-m его компонент равны нулю. Очевидно, что число опорных планов задачи линейного программирования конечно и не превышает . Число строго положительных компонент опорного плана не превышает m.

21Дайте определение К-матрицы КЗЛП.

К-матрицей КЗЛП будем называть расширенную матрицу системы линейных уравнений, равносильной системе , содержащую единичную подматрицу на месте первых n своих столбцов и все элементы ( n+1 )-го столбца которой неотрицательны.

Число К-матриц конечно и не превышает . Каждая К-матрица определяет ОП КЗЛП и наоборот.

22 Сформулируйте связь между опорным планом и К-матрицей.

Каждая К-матрица определяет ОП КЗЛП и наоборот.

23 Число опорных планов конечно или нет?

Число опорных планов задачи линейного программирования конечно и не превышает . Число строго положительных компонент опорного плана не превышает m.

24 Какого числа не превышает количество опорных планов КЗЛП?

m -ранг матрицы А системы уравнений , причем m < n.

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

Отметим, что базисные компоненты опорного плана неотрицательны; остальные n-m его компонент равны нулю.

25 Сформулируйте связь между опорным планом и крайней точкой.

Теорема (о крайней точке). Опорный план ЗЛП является крайней точкой множества P’ и наоборот.

Следствие 1. Крайняя точка множества P’ может иметь не более m строго положительных компонент.

Следствие 2. Число крайних точек множества P’ конечно и не превышает .

Следствие 3. Если множество P’ ограниченное, то оно является выпуклым многогранником.

26 Сформулируйте утверждение о существовании оптимального опорного плана.

Теорема 3.3 (о существовании опорного плана или решения ЗЛП). Если линейная форма ограничена сверху на непустом множестве P’, то ЗЛП разрешима, то есть существует такая точка , что .

Теорема 3.4. Если множество P’ не пусто, то оно имеет опорный план (или крайнюю точку).

27 Дайте определение симплекс-разности.

где – вектор, компонентами которого являются коэффициенты линейной функции при базисных ( ) переменных опорного плана, определяемого матрицей , назовем j-й симплекс-разностью матрицы .

28 Сформулируйте критерий оптимальности в алгоритме симплекс-метода.

_{Теорема}_{(критерий оптимальности опорного плана). Пусть все симплекс-разности матрицы} неотрицательные. Тогда опорный план , определяемый матрицей , является оптимальным.

29 Сформулируйте критерий отсутствия решений в алгоритме симплекс-метода.

Пусть в матрице есть симлекс-разности и в столбце ( , ) нет ни одного строго положительного элемента. Тогда ЗЛП (3.18) не имеет конечного решения.

30 Сформулируйте основные моменты, которые должен содержать любой конечный алгоритм решения ЗЛП.

Решением задачи является неотрицательное базисное решение системы линейных уравнений , то метод решения задачи должен содержать четыре момента:

обоснование способа перехода от одного опорного плана (К-матрицы) к другому;
указание признака оптимальности, позволяющего проверить, является ли данный опорный план оптимальным;
указание способа построения нового опорного плана, более близкого к оптимальному;
указание признака отсутствия конечного решения.

Источник

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

Графический метод применяется для решения задач линейного программирования малой размерности, когда количество искомых переменных не более 3. На практике этот метод применяют чаще всего для задач с двумя переменными.

В основе графического метода в случае двух (трех) переменных лежат следующие представления. Множество допустимых планов можно представить в виде некоторого многогранного выпуклого множества на плоскости (в пространстве). Оптимальное решение, если оно существует и единственно, лежит в угловой точке множества допустимых решений, где пересекаются прямые (плоскости), ограничивающие это множество.

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

Рассмотрим для определенности задачу максимизации для целевой функции, зависящей от двух переменных:

(1.12)

Шаг 1. Построение множества допустимых планов.

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

Если пересечение допустимых полуплоскостей для всех ограничений не пусто, тогда оно представляет собой область допустимых решений, которая называется многоугольником решений. Множество точек, принадлежащих этому многоугольнику, образует множество допустимых планов (1.12) исходной задачи. При условии не отрицательности переменных многоугольник будет лежать в первой четверти.

Шаг 2. Нахождение оптимального плана.

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

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

Для нахождения оптимальной точки рассмотрим целевую функцию задачи . Запишем ее в виде:

, где .

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

Вектор нормали к прямой к линии уровня целевой функции называется градиентом.Градиент указывает направление возрастания целевой функции.

Для нахождения точки экстремума графическим методом, необходимо сначала построить линию уровня для некоторого произвольного значения целевой функции. Затем осуществить ее параллельное передвижение в направлении градиента, если решается задача максимизации, и в обратном направлении, при решении задачи минимизации. Смещение производится до тех пор, пока не будет достигнута «последняя» точка области допустимых планов . Для задач максимизации (минимизации) такой точке области D соответствует наибольшее из возможных значений линии уровня. Последнее означает, что для нахождения точки экстремума в задаче линейного программирования мы должны сначала построить линию уровня для некоторого произвольного значения целевой функции. Затем необходимо осуществлять ее параллельное передвижение (так, чтобы она оставалась перпендикулярной векторус ) до тех пор, пока не достигнем такой точки области допустимых планов D , из которой смещение в направлении вектора с было бы невозможно. Такой метод решения получил название графического . Заметим, что решение задачи поиска минимума линейной функции осуществляется аналогично, с той лишь разницей, что движение по линиям уровня должно производиться в направлении, обратном градиенту целевой функции, т. е. по вектору (-с ).

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

Шаг 3. Нахождение максимального значения функции .

Аналитически оптимальная точка с координатами находится как точка пересечение двух прямых. Векторявляется оптимальным планом задачи. Затем вычисляется значение целевой функции в оптимальной точке.

Задача. При производстве товаров А и В используются три вида ресурсов: R1, R2, R3. Сведения о количестве ресурсов, необходимых для производства единицы каждого товара, запасе ресурсов и ценах, по которым товары продаются, приведены в табл. 1.3. Найдите оптимальный план, максимизурующий доход.

Источник