1.2. Свойства решений задач линейного программирования
где — произвольные неотрицательные числа, удовлетворяющие условию .
Множество точек линейного пространства называется выпуклым, если вместе с любыми двумя своими точками оно содержит и их произвольную линейную комбинацию.
Любая точка х выпуклого множества называется угловой, если она не может быть представлена в виде линейной комбинации каких-либо двух других различных точек данного множества.
Многогранником решений задачи линейного программирования называется множество планов (непустое) задачи линейного программирования. Вершиной называется всякая угловая точка многогранника.
Допустимые планы задачи линейного программирования считаются базисными, если в многограннике решений им соответствуют угловые (крайние) точки.
Базисные планы с неотрицательными компонентами называются опорными
Теорема 1.1. Множество планов основной задачи линейного программирования является выпуклым (если не является пустым).
Теорема 1.2. Если задача линейного программирования имеет оптимальное решение (в ограниченной области всегда, а в неограниченной – в зависимости от условий, наложенных на функцию ), то оно совпадает, по крайней мере, с одним из опорных решений системы ограничительных уравнений.
Теорема 1.3. 1. Целевая функция f задачи линейного программирования достигает своего экстремального значения в вершине многогранника области допустимых решений (единственное решение).
2. Если линейная функция принимает экстремальное значение более чем в одной вершине, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих вершин (бесконечное множество решений).
Задачи линейного программирования на минимум и на максимум могут быть преобразованы к одному виду задач, например на максимум. Так как справедливо соотношение , то для отыскания минимума целевой функции
можно перейти к нахождению максимума функции
Графический метод решения задач линейного программирования Случай двух переменных
Постановка задачи в этом случае имеет вид:
Каждое из ограничительных неравенств области решений определяет полуплоскость с граничными прямыми
Если рассматривается система неравенств, то областью её решений может быть один из следующих случаев. 1) Система несовместна, когда область решений является пустым множеством.
2) Система неравенств совместна, то есть, область её решений выпуклое непустое множество, называемое многоугольником решений (в отличие от «многогранника решений», когда число неизвестных ), либо выпуклая многогранная область, уходящая в бесконечность.
Если система является совместной, то сторонами многоугольника решений являются прямые, которые получаются при замене знаков неравенств в ограничениях на знаки равенств.
Для определения экстремума ограниченной сверху целевой функции необходимо для случая:
1. Если , построить линию уровня (h –некоторая постоянная), таким образом, чтобы она проходила через многоугольник решений. При выполнении условия (то есть, проходит через начало координат) линия называется опорной. Построить вектор – градиент целевой функции . Передвигать линию уровня параллельно самой себе в направлении градиента, до тех пор, пока не будет достигнута последняя точка многоугольника решений (Рис.1.1). Координаты соответствующей точки дадут оптимальный план решений. Координаты точки можно уточнить аналитически, решая систему уравнений для прямых, которые пересекаются в данной точке.
2. Если , то линия уровня передвигается в направлении, противоположном своему градиенту (в направлении антиградиента) до достижения крайней точки многоугольника решений (Рис.1.2).
При решении могут встретиться следующие случаи.
- Целевая функция F принимает максимальное значение в единственной точке А рис.1.1 (единственное решение).
- Целевая функция принимает минимальное значение в точке В рис. 1.2 (единственное решение).
- Целевая функция F принимает максимальное значение в любой точке прямой АВ рис 1.3. Прямая АВ перпендикулярна градиенту. (бесконечное множество решений).
- Целевая функция не ограничена сверху на множестве допустимых решений Рис. 1.4. Максимум недостижим.
- Система ограничений несовместна рис. 1.5. Решений нет.
Чтобы найти решение задачи линейного программирования геометрическим способом, необходимо:
а) построить прямые, которые получаются из ограничений заменой знаков неравенств на знаки равенства,
б) найти полуплоскости, определяемые каждым из ограничений.
а) построить прямую (линию уровня) , проходящую через область допустимых значений (иногда удобно строить опорную линию f = ),
б) передвигать линию уровня параллельно самой себе в направлении градиента (при отыскании максимума), либо в направлении антиградиента (при отыскании минимума), до точки, в которой целевая функция либо принимает максимальное (минимальное) значение, либо устанавливается её неограниченность,
в) определить координаты точки пересечения граничных прямых, в которой целевая функция принимает экстремальное значение.
Пример 3. Найти максимальное и минимальное значения функции
Решение. Строим координатную плоскость и наносим на неё прямые — ограничения (Рис.1.6). Первое уравнение неравенства можно преобразовать в равенство, уравнение границы или уравнение прямой (1) в отрезках и построить её, откладывая на соответствующих осях и отрезки 3 и 8. Если в неравенство (1) подставить координаты точки О(0;0), то неравенство будет , что неверно, отсюда следует, что области решений будет принадлежать полуплоскость со стороны, противоположной началу координат. Аналогичным образом преобразуем второе неравенство: и построим прямую (2). Области решений будет принадлежать полуплоскость с той стороны от прямой, где находится начало координат, так как при подстановке точки О(0;0) получим верное неравенство . Преобразуем третье неравенство: и построим прямую (3). Области решений будет принадлежать полуплоскость с той стороны от прямой, где находится начало координат, так как при подстановке точки О(0;0) получим верное неравенство . Таким образом, область решений задачи представляет собой треугольник АВD.
Для определения максимума целевой функции строим линию уровня , проходящую через область решений, и перпендикулярно к ней – вектор . В направлении этого вектора перемещаем линию уровня параллельно самой себе до точки А, которая является конечной точкой области решений. Эта точка, в которой целевая функция достигает максимума. Чтобы найти её координаты, решаем совместно второе и третье уравнения
Таким образом, максимальное значение целевой функции будет .
Чтобы найти минимальное значение целевой функции, линию уровня передвигаем влево, до конечной точки В. Получаем . Координаты точки В получаем, решая совместно первое и третье уравнения
Следовательно, минимальное значение целевой функции будет
Билет № 7
2. Теорема об экстремуме целевой функции задачи линейного программирования.
Теорема 3.3. Целевая функция задачи линейного программирования достигает экстремума в угловой точке области допустимых решений; причем, если целевая функция достигает экстремума в нескольких угловых точках области допустимых решений, то она также достигает экстремума в любой выпуклой линейной комбинации этих точек.
Д о к а з а т е л ь с т в о. Будем считать, что решается задача на нахождение максимума целевой функции
Z(X) = CX max,
Докажем, что целевая функция достигает экстремума в угловой точке области допустимых решений G от противного. Если является оптимальным решением, то . Предположим, что оптимальное решение задачи не является угловой точкой (рис.3.5).
Тогда по теореме 3.1 , , (j = 1, 2, …, n) – угловые точки области G. Найдем
Среди значений выберем наибольшее. Пусть это будет ,
что противоречит тому, что оптимальное решение в задаче на максимум. Следовательно, является угловой точкой области G.
2. Докажем второе утверждение теоремы. Пусть угловые точки области допустимых решений являются оптимальными решениями, т.е. и . Выпуклая линейной комбинации этих угловых точек равна .
Найдем значение целевой функции
т.е. этот вектор также является оптимальным решением.
Билет № 8
2. Первая теорема двойственности.
Теорема 5.1. Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение; причем значения целевых функций задач на своих оптимальных решениях совпадают. Если же одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.
Д о к а з а т е л ь с т в о. Пусть имеется несимметричная пара двойственных задач
Z(X) = CX max, ,
Прежде, чем приступить к доказательству, получим ряд соотношений. Предположим, что первая (прямая) из задач решалась симплексным методом и получено оптимальное решение с базисом . Запишем последнюю симплексную таблицу (табл. 5.1).
Запишем разложение вектора по базису оптимального решения
Преобразуем данное разложение:
, k = 0, 1, 2, . n. (5.11)
Умножим данное матричное равенство на обратную матрицу слева:
Так как D = Е, Е = , то = , k = 0, 1, 2, . n. (5.12)
Аналогично можно получить
Запишем с учетом полученного оценки , k = 0, 1, 2, . n.
В общем случае формула для расчета оценок имеет вид (4.9)
Обозначим через матрицу-строку коэффициентов при базисных переменных в оптимальном решении. Тогда для оценок разложений векторов-условий по базису оптимального решения имеем
Обозначим матрицу, составленную из векторов , через , т.е. ; матрицу-строку из оценок через , т.е. и матрицу-строку коэффициентов целевой функции через С, т.е. . Кроме того, матрица системы уравнений-ограничений .
Получим из формул (5.12) и (5.14) следующее:
Теперь приступим к доказательству первого утверждения теоремы.
1. Сначала докажем, что допустимое решение двойственной задачи имеет вид
Действительно, так как решение прямой задачи на максимум оптимальное, то ее оценки неотрицательные
т.е. удовлетворяет системе ограничений двойственной задачи.
2. Далее докажем, что при и
где область допустимых решений прямой задачи, область допустимых решений двойственной задачи.
Для этого систему ограничений прямой задачи умножим слева на допустимое решение двойственной задачи Y, а систему ограничений двойственной задачи умножим справа на допустимое решение Х исходной задачи, получим
4. Далее докажем, что является оптимальным решением. Так как прямая задача на максимум, а оптимальное решение, то . Двойственная задача на минимум, поэтому значение ее целевой функции на оптимальном решении должно удовлетворять условию . Как показано в пункте 3, , поэтому значение не может быть меньше , а может быть только равно . Это равенство достигается при
которое и является оптимальным решением двойственной задачи. Первое утверждение теоремы доказано.
Запишем полезное для нахождения оптимального решения двойственной задачи соотношение. Матричное равенство представим следующим образом
где матрица обратная к матрице D, составленной из векторов-условий задачи, образующих базис оптимального решения. Матрица находится в последней симплексной таблице под единичными векторами первой симплексной таблицы, столбцами её элементов являются .
Отсюда следует, что Так как , то или
Данная формула позволяет, используя оценки в последней симплексной таблицы решения прямой задачи, записывать оптимальное решение двойственной задачи как сумму оценок и коэффициентов целевой функции.
Докажем второе утверждение теоремы. Пусть прямая задача не имеет оптимального решения ввиду неограниченности целевой функции Z(X) +. Так как и , то является пустым множеством.