Область допустимых решений задачи линейного программирования может быть

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

где — произвольные неотрицательные числа, удовлетворяющие условию .

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

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

Многогранником решений задачи линейного программирования называется множество планов (непустое) задачи линейного программирования. Вершиной называется всякая угловая точка многогранника.

Допустимые планы задачи линейного программирования считаются базисными, если в многограннике решений им соответствуют угловые (крайние) точки.

Базисные планы с неотрицательными компонентами называются опорными

Теорема 1.1. Множество планов основной задачи линейного программирования является выпуклым (если не является пустым).

Теорема 1.2. Если задача линейного программирования имеет оптимальное решение (в ограниченной области всегда, а в неограниченной – в зависимости от условий, наложенных на функцию ), то оно совпадает, по крайней мере, с одним из опорных решений системы ограничительных уравнений.

Теорема 1.3. 1. Целевая функция f задачи линейного программирования достигает своего экстремального значения в вершине многогранника области допустимых решений (единственное решение).

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

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

можно перейти к нахождению максимума функции

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

Постановка задачи в этом случае имеет вид:

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

Если рассматривается система неравенств, то областью её решений может быть один из следующих случаев. 1) Система несовместна, когда область решений является пустым множеством.

2) Система неравенств совместна, то есть, область её решений выпуклое непустое множество, называемое многоугольником решений (в отличие от «многогранника решений», когда число неизвестных ), либо выпуклая многогранная область, уходящая в бесконечность.

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

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

1. Если , построить линию уровня (h –некоторая постоянная), таким образом, чтобы она проходила через многоугольник решений. При выполнении условия (то есть, проходит через начало координат) линия называется опорной. Построить вектор – градиент целевой функции . Передвигать линию уровня параллельно самой себе в направлении градиента, до тех пор, пока не будет достигнута последняя точка многоугольника решений (Рис.1.1). Координаты соответствующей точки дадут оптимальный план решений. Координаты точки можно уточнить аналитически, решая систему уравнений для прямых, которые пересекаются в данной точке.

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

При решении могут встретиться следующие случаи.

1. Целевая функция F принимает максимальное значение в единственной точке А рис.1.1 (единственное решение).
2. Целевая функция принимает минимальное значение в точке В рис. 1.2 (единственное решение).
3. Целевая функция F принимает максимальное значение в любой точке прямой АВ рис 1.3. Прямая АВ перпендикулярна градиенту. (бесконечное множество решений).
4. Целевая функция не ограничена сверху на множестве допустимых решений Рис. 1.4. Максимум недостижим.
5. Система ограничений несовместна рис. 1.5. Решений нет.

Чтобы найти решение задачи линейного программирования геометрическим способом, необходимо:

а) построить прямые, которые получаются из ограничений заменой знаков неравенств на знаки равенства,

б) найти полуплоскости, определяемые каждым из ограничений.

а) построить прямую (линию уровня) , проходящую через область допустимых значений (иногда удобно строить опорную линию f = ),

б) передвигать линию уровня параллельно самой себе в направлении градиента (при отыскании максимума), либо в направлении антиградиента (при отыскании минимума), до точки, в которой целевая функция либо принимает максимальное (минимальное) значение, либо устанавливается её неограниченность,

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

Пример 3. Найти максимальное и минимальное значения функции

Решение. Строим координатную плоскость и наносим на неё прямые — ограничения (Рис.1.6). Первое уравнение неравенства можно преобразовать в равенство, уравнение границы или уравнение прямой (1) в отрезках и построить её, откладывая на соответствующих осях и отрезки 3 и 8. Если в неравенство (1) подставить координаты точки О(0;0), то неравенство будет , что неверно, отсюда следует, что области решений будет принадлежать полуплоскость со стороны, противоположной началу координат. Аналогичным образом преобразуем второе неравенство: и построим прямую (2). Области решений будет принадлежать полуплоскость с той стороны от прямой, где находится начало координат, так как при подстановке точки О(0;0) получим верное неравенство . Преобразуем третье неравенство: и построим прямую (3). Области решений будет принадлежать полуплоскость с той стороны от прямой, где находится начало координат, так как при подстановке точки О(0;0) получим верное неравенство . Таким образом, область решений задачи представляет собой треугольник АВD.

Для определения максимума целевой функции строим линию уровня , проходящую через область решений, и перпендикулярно к ней – вектор . В направлении этого вектора перемещаем линию уровня параллельно самой себе до точки А, которая является конечной точкой области решений. Эта точка, в которой целевая функция достигает максимума. Чтобы найти её координаты, решаем совместно второе и третье уравнения

Таким образом, максимальное значение целевой функции будет .

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

Следовательно, минимальное значение целевой функции будет

Источник

Свойства области допустимых решений

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

2.1. Свойства области допустимых решений

Пусть дана задача в канонической форме:

Пусть все уравнения линейно-независимые.

И пусть есть несколько — мерных векторов .

Выпуклая оболочка — мерных векторов – множество точек вида:

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

Двумерное пространство

Трехмерное пространство

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

Теорема 1: Область допустимых решений задачи ЛП выпуклая.

П усть , т.е. для них выполняются (2) и (3).

таким образом, условие (3) выполняется.

таким образом и условие (2) выполняется, произвольная точка отрезка принадлежит области D, то есть эта область выпукла.

Точка называется угловой (крайней), если не существует двух других точек области, на отрезке между которыми лежит эта точка.

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

Таким образом, если найти все угловые точки, то любая точка внутри области записывается через уравнение (4).

Теорема 2: Оптимальное решение задачи ЛП достигается в одной из угловых точек области допустимых решений .

Покажем, что оптимальное решение не может быть внутри области.

Пусть – внутренняя точка области. Тогда функция дифференцируема в этой точке:

Так как в этой точке достигается максимум, то и производная здесь обратится в ноль.

Но это противоречит условию, которое мы накладывали ранее, а именно . Значит точка, в которой достигается оптимальное решение, лежит на границе области. Можно показать [8], что хотя бы одно оптимальное решение достигается в угловой точке.

2.2. Базисные и опорные решения

Напомним, что допустимое решение задачи линейного программирования называется планом ( ). В силу условия (3) компоненты плана неотрицательны. Выделим отдельно положительные и отрицательные компоненты. Пусть первые k компонент положительны. Будем рассматривать вектора условий при положительных и отрицательных компонентах плана.

Допустимое решение называется опорным, если вектора условий при его положительных компонентах решения линейно-независимы.

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

Проверим, опорное это решение или нет:

– опорное решение (невырожденное).

В трехмерном пространстве максимум только 3 вектора могут быть независимыми.

– не является опорным решением, так как векторы линейно-зависимые. Значит, эта точка будет внутренней точкой области.

– опорное решение (вырожденное).

Так как определитель равен нулю, вектора линейно-зависимые.

– не является опорным решением.

Положительные компоненты опорного решения называются базисными.

Вектора условий линейных компонентов могут быть базисом в пространстве.

Базис — мерного пространства – совокупность любых линейно-независимых векторов .

Опорное решение называется невырожденным, если количество положительных компонент равно числу линейно-независимых ограничений (k=m).

Опорное решение называется вырожденным, если количество положительных компонент меньше числа линейно-независимых ограничений (km).

Нулевые переменные невырожденного опорного решения называются свободными.

Матрица, состоящая из векторов при положительных компонентах невырожденного опорного плана, называется базисной.

Базисное решение – решение системы уравнений (2) , если вектора условий при его ненулевых компонентах линейно-независимые.

Базисная матрица – матрица из линейно-независимых векторов условий, содержащая все вектора условий при ненулевых компонентах. Она всегда квадратная.

Базисная матрица невырожденного решения определяется однозначно, а базисная матрица вырожденного – неоднозначно.

Для определения базисного решения нужно выбрать произвольные переменных , вычислить определитель B из векторов условий этих переменных. Если , то занулить остальные переменные. Тогда для базисных переменных получим систему уравнений:

Максимальное количество базисных решений равно .

Опорное решение – допустимое базисное решение. Для поиска опорных решений можно перебрать все базисные решения и выбрать из них допустимые (с неотрицательными компонентами).

Теорема 3: опорные решения задачи ЛП совпадают с угловыми точками области допустимых решений.

Доказательство теоремы смотри в [8].

Источник

Читайте также:  Uprog программирование адреса ау