Задача линейного программирования является задачей выпуклого программирования

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

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

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

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

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

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

Теорема 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) и не забудь поделиться с друзьями:

Источник

REVIZED / 12_Линейное_программирование

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

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

В предыдущих разделах пособия мы изучали задачи минимизации. Задача линейного программирования чаще формулируется как задача максимизации. Это объясняется тем, что ее истоки связаны с экономическими приложениями, например, с проблемой планирования производства с целью максимизации дохода.

Итак, общая форма записи задачи линейного программирования имеет вид:

Введем следующие обозначения: ; ; – матрица размерности ; – вектор-строка матрицы , ; – вектор-столбец матрицы , .

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

Каноническая форма:

Симметричная форма:

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

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

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

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

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

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

Доказательство. Пусть вектор – решение задачи. Очевидно, что ранг системы ограничений задачи равен , тогда по теореме 9.6 . Поэтому существуют векторы и такие, что . Отсюда

. (2)

Как следует из теоремы 9.7, . В то же время, так как – условный максимум, вектор не является направлением возрастания функции в точке . Тогда согласно замечанию к теореме 5.2 .

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

. (3)

Так как , а (см. теорему 9.6), то , где векторы – все вершины выпуклого многогранного множества . Тогда из (3)

. (4)

Пусть номер вершины множества таков, что . Тогда из равенства (4), учитывая неотрицательность всеx , имеем соотношения . Следовательно, так как вектор – точка максимума, . Что и требовалось.

Источник