- 4. Основные теоремы линейного программирования: сформулировать все, доказать теорему о существовании опорного плана (теорема 3).
- 5. Основные теоремы линейного программирования: сформулировать все, доказать теорему об оптимальности выпуклой комбинации планов злп (теорема 4).
- Основные теоремы линейного программирования.
4. Основные теоремы линейного программирования: сформулировать все, доказать теорему о существовании опорного плана (теорема 3).
Опорный план КЗЛП является крайней точкой множества P и наоборот.
Теорема 2(о сущесвованиии оптимального плана или решения задачи ЗЛП)
Если линейная форма ограничена сверху на непустом множестве , то ЗЛП разрешима, т.е. существует такая точка , что
Если множество не пусто, то оно имеет опорный план (или крайнюю точку)
Доказательство: Заметим что если правые части системы линейных уравнений равны нулю, то, т.к. ранг матрицы A равен m, вектор является вырожденным опорным планом ЗЛП. Поэтому далее будем предполагать , что среди есть отличные от нуля.
— план, но не опорный план ЗЛП с k строго положительными компонентами. Не нарушая общности, будем считать, что строго положительными являются первые k компонент вектора , тогда имеет место равенство (3.1) Так как вектор — не опорный план, то согласно определению (2) опорного плана Линейно зависимы, т.е. существуют действительные числа не все равные нулю и такие, что (3.2)
Введём обозначение (3.3) Изменением знака в (3.2) можно всегда добиться, чтобы было положительным. Умножим левую и правую части (3.2) на и полученное равенство сложим с (3.1), будем иметь Или, так как , (3.4) В силу (3.3) (3.5) И обязательно существует такое j, для которого с соотношении (3.5) имеет место равенство. Положим для определённости что Т.о., мы построили план ЗЛП, j-ая компонента которого есть а остальные n—k+1 компонент равны нулю. При этом,если векторы оказались линейно зависимыми, то, рассуждая аналогично, получим план ЗЛП, у которого k-2 строго положительных компонент > 0 и т.д. до тех пор пока не построим такой план ЗЛП с строго положительными компонентами, что соответствующие этим компонентам векторы будут линейно независимыми. Так как по предположению среди есть отличные от нуля, то . Построенный план является при l=m невырожденным, а при l
Пусть векторы планы задачи линейного программирования. Тогда вектор
(4.1) где (4.2) будет решением задачи ЗЛП тогда и только тогда, когда её решением является каждый из векторов
Пусть вектор является решением ЗЛП. Тогда во множестве планов существует крайняя точка, в которой линейная форма достигает своего глобального максимума в области .
Если решение ЗЛП достигается в нескольких крайних точках области , то оно достигается и в любой выпуклой линейной комбинации этих точек.
Утверждение теоремы 6 является следствием теоремы 4.
5. Основные теоремы линейного программирования: сформулировать все, доказать теорему об оптимальности выпуклой комбинации планов злп (теорема 4).
Теорема 1 (о крайней точке)
Опорный план КЗЛП является крайней точкой множества P и наоборот.
Теорема 2(о сущесвованиии оптимального плана или решения задачи ЗЛП)
Если линейная форма ограничена сверху на непустом множестве , то ЗЛП разрешима, т.е. существует такая точка , что
Если множество не пусто, то оно имеет опорный план (или крайнюю точку)
Пусть векторы планы задачи линейного программирования. Тогда вектор
(4.1) где (4.2) будет решением задачи ЗЛП тогда и только тогда, когда её решением является каждый из векторов
Пусть каждый из векторов является решением ЗЛП, т.е. Тогда т.е. вектор , определяемый соотношениями 4.1-4.2 также является решением ЗЛП. Обратно, пусть вектор где Является решением ЗЛП Предположим, что среди векторов есть хотя бы один вектор , который не является решением ЗЛП, т.е. имеет место следующее неравенство: Тогда, учитывая 4.2, будем иметь Получили противоречие, следовательно, каждый из векторов есть решение ЗЛП.
Пусть вектор является решением ЗЛП. Тогда во множестве планов существует крайняя точка, в которой линейная форма достигает своего глобального максимума в области .
Если решение ЗЛП достигается в нескольких крайних точках области , то оно достигается и в любой выпуклой линейной комбинации этих точек.
Утверждение теоремы 6 является следствием теоремы 4.
Основные теоремы линейного программирования.
Определение: Множество точек называется выпуклым, если вместе с его любыми двумя точками ему принадлежит и весь отрезок, соединяющий их.
На рис. 33.1 изображено выпуклое множество (выпуклый многоугольник), а на рис. 33.2 — невыпуклое.
Утверждение: Пересечение конечного числа выпуклых множеств также выпуклое множество.
Определение: Точка выпуклого множества называется угловой (или крайней), если через неё нельзя провести ни одного отрезка, состоящего только из точек данного множества и для которого она была бы внутренней.
Для выпуклого многоугольника угловыми точками являются все его вершины. В пространстве выпуклое множество с конечным числом угловых точек называется выпуклым многогранником.
Утверждение: множеством решений системы m линейных неравенств с n переменными является выпуклый многогранник в n-мерном пространстве (исключая случай, когда система несовместна).
Как известно, любая задача линейного программирования может быть приведена к канонической модели минимизации линейной целевой функции с линейными ограничениями типа равенств. Поскольку число переменных в задаче линейного программирования больше числа ограничений (n > m), то можно получить решение, приравняв нулю (n — m) переменных, называемых свободными. Оставшиеся m переменных, называемых базисными, можно легко определить из системы ограничений-равенств обычными методами линейной алгебры. Если решение существует, то оно называется базисным. Если базисное решение допустимо, то оно называется базисным допустимым (опорным планом). Геометрически, базисные допустимые решения соответствуют вершинам (угловым точкам) выпуклого многогранника, который ограничивает множество допустимых решений. Если задача линейного программирования имеет оптимальные решения, то по крайней мере одно из них является базисным.
Приведенные соображения означают, что при поиске оптимального решения задачи линейного программирования достаточно ограничиться перебором базисных допустимых решений. Число базисных решений равно числу сочетаний из n переменных по m:
и может быть достаточно велико для их перечисления прямым перебором за реальное время. То, что не все базисные решения являются допустимыми, существо проблемы не меняет, так как чтобы оценить допустимость базисного решения, его необходимо получить. Такой путь решения задачи хотя и возможен, но весьма трудоемок, так как число допустимых базисных решений может быть весьма большим.
Теорема 33.1: Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
Ранее говорилось, что ограничениями любой задачи линейного программирования являются либо система линейных уравнений, либо система линейных неравенств. Совокупность решений таких систем при условии их совместности, образует выпуклые множества с конечным числом угловых точек. В частном случае, когда в систему ограничений — неравенств входят только две переменные и это множество можно изобразить на плоскости (рис. 33.2, 33.3).
Теорема 33.2: Если существует, и при том единственное, оптимальное решение задачи линейного программирования, то оно совпадает с одной из угловых точек множества допустимых решений. Если линейная форма принимает минимальное (максимальное) значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.
Из теоремы 2 следует, что поиски оптимального решения можно ограничить перебором конечного числа угловых точек (их число меньше , где n — число неизвестных, а m – число ограничений), однако построение возможно только для двух и трёхмерных пространств, поэтому нужны аналитические методы, позволяющие находить координаты угловых точек.
Теорема 33.3: Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений системы ограничений, и наоборот.
Задача линейного программирования в стандартной форме с двумя переменными имеет вид:
Эти задачи допускают простое геометрическое истолкование. Рассмотрим вначале геометрическое истолкование системы ограничений задачи. Каждую совокупность значений переменных x1, x2 можно изобразить точкой на плоскости, если ввести систему координат и по одной оси откладывать x1, а по другой x2. Выясним, что геометрически означает совокупность решений одного отдельно взятого неравенства:
Рассмотрим прямую на плоскости с уравнением:
Эта прямая делит плоскость на две полуплоскости, в одной из которых справедливо наше неравенство, а в другой — противоположное. Для того, чтобы проверить, какая из полуплоскостей состоит из решений нашего неравенства, следует взять точку из какой-либо полуплоскости и проверить, выполняется ли наше неравенство в этой точке. Множество решений отдельно взятого линейного неравенства представляет собой полуплоскость. Для системы из нескольких таких неравенств точки, координаты которых удовлетворяют всем неравенствам одновременно, должны находиться во всех соответствующих полуплоскостях, т.е. принадлежать теоретико-множественному пересечению этих полуплоскостей. Множество точек на плоскости, удовлетворяющих системе ограничений, составляет, таким образом, некоторую выпуклую многоугольную область (область допустимых решений). Условия неотрицательности переменных x1 ≥ 0 и x2 ≥ 0 приводят к тому, что эта область находится в первой координатной четверти.
При решении двумерных задач линейного программирования возможны следующие ситуации (ОДР — область допустимых решений):
1. Основной случай — получающаяся область имеет вид ограниченного (замкнутого) выпуклого многоугольника (см. рис. 33.2).
2. Не основной случай — получается неограниченный (незамкнутый) выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 33.3
3. Наконец, возможен случай, когда неравенства противоречат друг другу, и допустимая область вообще пуста.
Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.
В общем виде, когда в задаче участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более трех весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.