Лекция: Приведите ОЗЛП к каноническому виду.
Любую ЗЛП можно привести к каноническому виду, используя следующие правила:
а) максимизация целевой функции = c1x1+…+cnxn равносильна минимизации целевой функции: =-c1x1 -…-cnxn;
б) ограничение в виде неравенства, например, 3Х1 + 2Х2 – Х3 £ 6, может быть приведено к стандартной форме 3Х1 + 2Х2 – Х3 + Х4 = 6, где новая переменная Х4 неотрицательна. Ограничение Х1 – Х2 + 3Х3 ³ 10 может быть приведено к стандартной форме Х1 – Х2 + 3Х3 – – Х5 = 10, где новая переменная Х5 неотрицательна;
в) если некоторая переменная Хk может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду, где ³ 0 и ³ 0.
Перечислите свойства множества планов Р
Множество планов Р задачи линейного программирования (ЗЛП) есть замкнутое выпуклое множество.
Множество Р может быть как ограниченным, так и неограниченным, кроме того оно может оказаться пустым.
Теорема 3.2 (о крайней точке). Опорный план ЗЛП является крайней точкой множества P’ и наоборот.
Следствие 1. Крайняя точка множества P’ может иметь не более m строго положительных компонент.
Следствие 2. Число крайних точек множества P’ конечно и не превышает .
Следствие 3. Если множество P’ ограниченное, то оно является выпуклым многогранником
Теорема 3.3 (о существовании опорного плана или решения ЗЛП). Если линейная форма ограничена сверху на непустом множестве P’, то ЗЛП разрешима, то есть существует такая точка, что .
Теорема 3.4. Если множество P’ не пусто, то оно имеет опорный план (или крайнюю точку).
Теорема 3.5. Пусть векторы – планы задачи линейного программирования. Тогда вектор
(3.34)
где
(3.35)
будет решением задачи линейного программирования тогда и только тогда, когда её решением является каждый из векторов
(План или допустимое решение задачи линейного программирования – вектор пространства Еn, компоненты которого удовлетворяют функциональным и прямым ограничениям задачи.)
Дайте определение оптимального плана КЗЛП.
Планы соответственно прямой и двойственной ЗЛП являются оптимальными тогда и только тогда, когда
. (4.14)
Условия (4.14) называются условиями дополнительнойнежесткости.
Примечание 1.Для основной ЗЛП и двойственной к ней ЗЛП условия нежесткости имеют вид:
. (4.15)
План = (Х1*,…Хn*) будем называть решением задачи линейного программирования, или ее оптимальным планом, если
.
(План или допустимое решение задачи линейного программирования – вектор пространства Еn, компоненты которого удовлетворяют функциональным и прямым ограничениям задачи.Оптимальные решения, – решения, которые по тем или иным соображениям предпочтительнее других. Поэтому основной задачей исследования операций является предварительное количественное обоснование оптимальных решений.)
9 Какая ЗЛП называется разрешимой?
Будем говорить, что задача линейного программирования разрешима, если она имеет хотя бы один оптимальный план. У неразрешимой задачи или пуста область допустимых решений, или целевая функция не ограничена.