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

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

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

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

Точка Х называется выпуклой линейной комбинацией точек , если выполняются условия

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

Можно доказать следующую теорему о представлении выпуклого многогран­ника.

Теорема 1.1. Выпуклый п-мерный многогранник является выпук­лой линейной комбинацией своих угловых точек.

Из теоремы 1.1 следует, что выпуклый многогранник порождается своими угловыми точками или вершинами: отрезок – двумя точками, треугольник – тремя, тетраэдр – четырьмя точками и т.д. В то же время выпуклая многогранная область, являясь неограниченным множеством, не определяется однозначно своими угловыми точками: любую ее точку нельзя представить в виде выпуклой линейной комбинации угловых точек.

Свойства задачи линейного программирования. Ранее были рассмотрены различные формы задачи линей­ного программирования и показано, что любая задача линейного программирования может быть представлена в виде общей или канонической задачи.

Для обоснования свойств задачи линейного программирования и методов ее решения целесообразно рассмотреть еще два вида записи канонической задачи.

Матричная форма записи:

Здесь С – матрица-строка, А – матрица системы, Х – матри­ца-столбец переменных, В – матрица-столбец свободных членов:

Векторная форма записи:

где векторы соответствуют столбцам коэффициентов при неизвестных.

Выше была сформулирована, но не доказана в общем виде следующая теорема.

Теорема 1.2. Множество всех допустимых решений системы ог­раничений задачи линейного программирования является выпуклым.

Доказательство: Пусть — два допустимых решения ЗЛП, заданной в матричной форме. Тогда и . Рассмотрим выпуклую линейную комбинацию решений , т.е.

и покажем, что она также является допустимым решением систе­мы (1.3). В самом деле

т.e. решение X удовлетворяет системе (1.3). Но так как , то и Х >0, т.е. решение удовлетворяет условию неотрицательности.

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

Ответ на вопрос, в какой точке многогранника решений воз­можно оптимальное решение задачи линейного программирова­ния, дается в следующей фундаментальной теореме.

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

Доказательство: Будем полагать, что многогранник решений является огра­ниченным. Обозначим его угловые точки через , а оптимальное решение — через X*. Тогда F(X*) ³ F(X) для всех то­чек Х многогранника реше­ний. Если X* – угловая точка, то первая часть тео­ремы доказана.

Предположим, что X* не является угловой точкой, тогда на основании теоре­мы 1.1 X* можно предста­вить как выпуклую линей­ную комбинацию угловых точек многогранника ре­шений, т.е.

Так как F(X) – линейная функция, получаем

В этом разложении среди значений выбе­рем максимальное. Пусть оно соответствует угловой точке X_k (1 £ k £ р); обозначим его через М, т.е. . Заменим в выражении (1.5) каждое значение этим максимальным значением М. Тогда

По предположению Х * – оптимальное решение, поэтому, с одной стороны, ,но, с другой стороны, доказано, что
F(X*) £ М, следовательно, , где X_k – угловая точка. Итак, существует угловая точка X_k, в которой линейная функция принимает максимальное значение.

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

Пусть Х – выпуклая линейная комбинация этих угловых точек, т.е.

В этом случае, учитывая, что функция F(X) – линейная, полу­чим

т.е. линейная функция F принимает максимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек.

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

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

Следующая теорема посвящена аналитическому методу нахождения угловых точек.

Теорема 1.4. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.

Доказательство: Пусть – допустимое базисное решение системы ограничений ЗЛП (1.4), в котором первые т компонент — основные переменные, а остальные п — т компо­нент – неосновные переменные, равные нулю в базисном реше­нии (если это не так, то соответствующие переменные можно перенумеровать). Покажем, что Х – угловая точка многогранника решений.

Предположим противное, т.е. что Х не является угловой точ­кой. Тогда точку Х можно представить внутренней точкой отрез­ка, соединяющего две различные, не совпадающие с X, точки

другими словами, – выпуклой линейной комбинацией точек многогранника решений, т.е.

где (полагаем, что , ибо в противном случае точка Х совпадает с точкой Х ₁ или Х ₂).

Запишем векторное равенство (1.6) в координатной форме:

Т.к. все переменные и коэффициенты неотрицательны, то из последних п-т равенств следует, что , т.е. в решениях Х ₁, Х ₂ и Х системы уравнений (1.4) значения п — т компонент равны в данном случае нулю. Эти компоненты можно считать значениями неосновных переменных. Но значения неосновных переменных однозначно определяют значения основных, следовательно,

Таким образом, все п компонент в решениях Х ₁, Х ₂ и Х совпада­ют, и значит, точки Х ₁ и Х ₂ сливаются, что противоречит допуще­нию. Следовательно, X – угловая точка многогранника решений.

Докажем обратное утверждение. Пусть – угловая точка многогранника решений и первые ее т координат положительны. Покажем, что Х – допустимое базис­ное решение.

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

Предположим противное, т.е. векторы линейно зависимы; тогда в равенстве

хотя бы один из коэффициентов отличен от нуля. Умножим почленно равенство (1.7) на множитель μ > 0:

Подставив координаты угловой точки Х многогранника реше­ний в систему ограничений (1.4), получим

Равенство (1.8) почленно сложим с равенством (1.9), а затем вычтем его из равенства (1.9). Получим

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

Поскольку все , то можно подобрать μ на­столько малым, что все компоненты решений Х ₁ и Х ₂ будут неот­рицательными. В результате Х ₁ и Х ₂ будут различными допусти­мыми решениями задачи (1.4). При этом, как легко ви­деть, решение , т.е. точ­ка Х лежит на отрезке (в данном случае в его середине), располо­женном в многограннике решений. Значит, Х не является угловой точкой, что противоречит условию. Следовательно, наше допуще­ние неверно, т.е. векторы линейно независимы и Х – допустимое базисное решение задачи (1.4).

Из теорем 1.3 и 1.4 непосредственно вытекает важное следст­вие: если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допусти­мых базисных решений.

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

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник

2.4. Основные теоремы линейного программирования

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

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

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

На рис. 2.1 а) и рис. 2.1 б) показаны примеры выпуклых множеств, а на рис. 2.1 в) – пример множества точек, которое не является выпуклым.

Рис. 2.1. Примеры выпуклых множеств точек (а и б) и невыпуклого множества точек (в)

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

Определение. Непустое множество планов основной задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

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

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

Теорема 5. Любая система из k векторов n-мерного векторного пространства при k < n является линейно зависимой.

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

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

3.2. Пример использования графического метода

3.3. Частные случаи использования графического метода

3.4. Общий алгоритм графического метода

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

Для представления задачи линейного программирования в геометрической форме для каждого i-го ограничения в n-мерном пространстве задается полуплоскость (или гиперплоскость) решений. В результате пересечения всех полуплоскостей, определяемых ограничениями, образуется выпуклый многогранник допустимых решений.

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

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

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

В том случае, если в системе ограничений будет не две, а три переменных, то каждое ограничение геометрически будет определяться гиперполуплоскостью трехмерного пространства. Если же в системе ограничений количество переменных больше, чем три (х₁, х₂,… х_n), то каждое ограничение определяет гиперполуплоскость n-мерного пространства.

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

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

Источник