Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

1.2. Линейное программирование. Основные свойства задачи

Задача линейною программирования, как отмечалось выше, состоит в отыскании значений n переменных х1, х2, ...., хn) доставляющих экстремум функции z = nΣj = 1 cjxj при условиях

(1.1)

представляющих собой систему линейных нестрогих неравенств, которые в случае необходимости могут быть превращены в равенства посредством присоединения искусственных переменных xn+i:


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

Форма записи ограничений (1.1) является достаточно обшей, хотя сюда обычно добавляется условие ∀xj≥0 (в противном случае нужно иметь m>n). Полезно заметить, что включение в (1.1) хотя бы одного строгого неравенства осложняет решение задачи; например, если z = x1 и x1 < 1, то нельзя указать значение x1 которое доставило бы максимум z.

Свойства решений задачи линейного программирования во многом зависят от особенностей области определения, заданной неравенствами (1.1). Для изучения этих свойств введем следующие понятия:

- отрезком, соединяющим две данные точки X1, Х2, называется множество точек X с координатами xj = axj1 + (1 - a)xj2 (0 ≤ а ≤ 1, j = 1,...,n), где xj1, xj2 - координаты точек X1 и Х2 соответственно; а - изменяемый параметр, определяющий положение X (нетрудно видеть, что при а = 1 точка X совпадает с Х1 а при а = 0 - с Х2);

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

- множество точек X, координаты которых удовлетворяют неравенству вида a1x1 + a2x2 +...+ anxn ≤ b называется замкнутым (т. е. содержащим собственную границу) полупространством (оно обладает свойством выпуклости);

- точка X, принадлежащая выпуклой области, называется крайней, если в данной области нет двух таких точек Х1≠X2, что xj - axj1 + (1 - a)xj2 при 0 < а < 1 (крайняя точка не может находиться на отрезке между X1 и Х2, принадлежащими той же области).

Приведенные определения иллюстрирует рис. 1.2. Легко заметить, что система неравенств (1.1) указывает в Rn область U, являющуюся пересечением m замкнутых полупространств (т. е. выпуклым многогранником). Это подтверждает и рис. 1.3, где показана область U, определяемая условиями -x1 + x2 ≤ 1; -х1 - x2 ≤ 0; x1 ≤ 3. С увеличением числа переменных наглядность геометрических представлений теряется, однако аналогии с рассматриваемым примером сохраняются полностью, и в дальнейшем область определения линейной задачи будет условно изображена так, как показано на

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

Рис. 1.2
Рис. 1.2

Рис. 1.3
Рис. 1.3

Обратимся теперь к следующей теореме (1): экстремум целевой функции в задаче линейного программирования (если он существует) всегда является абсолютным.

Доказательство: пусть для определенности экстремум z есть максимум, и в U все-таки

существует точка Х° (рис. 1.5) с координатами х°1, х°2, ....,х°n. Предполагая таким образом наличие локального максимума z, необходимо допустить и существование в U некоторой точки X̄, где значение z больше, чем z° = f(X°) (иначе величину z° надо было бы признать абсолютным максимумом z). Рассмотрим отрезок, соединяющий Х° с X̄. В любой его точке X, заданной координатами xj = ax̄j + (1 - a)x°j (0 < a <1, j = 1,..,n), целевая функция 14 принимает значение z = f(X) = nΣj = 1 cj(ax̄j + [1 - a)x°j] = af(X) + (1 - a)f(X°) или f(X) = a[f(X) - f(X°)] +f(X°).

Поскольку f(X) - f(X°) > 0 (исходное допущение), значения f(X) непрерывно возрастают с увеличением а от 0 до 1. Другими словами, f(X) > f(X°), даже если X при надлежит достаточно малой окрестности Х°; но это противоречит утверждению о том, что z имеет в Х° локальный максимум. Следовательно, в У не может быть точек Х°, отличных от Х*.□

Рис. 1.4
Рис. 1.4

Рис. 1.5
Рис. 1.5

Теперь можно говорить о множестве {X*} глобально оптимальных решений (точек) X*, допуская, что в каких-то случаях оно содержит один элемент, в каких-то более одного, а иногда вообще является пустым.

Другое важное свойство линейных задач отражено в теореме (2): множество точек X* в задаче линейного программирования (если оно не пусто) всегда содержит хотя бы одну крайнюю точку многогранника U.

Доказательство: пусть число элементов множества {X*} больше единицы, и среди точек X* нет ни одной крайней точки многогранника U. Это значит, в U можно найти такие две различные точки Х1, Х2, что произвольно взятая точка Х*∈{Х*} окажется на соединяющем их отрезке, и тогда f(X*) = [f(X1) - f(X2)]a* + f(X2). Очевидно, рассматриваемое равенство должно существовать совместно с требованиями f(X*) ≥ f(X1) и f(Х*) ≥ f(Х2), вытекающими из определения абсолютного экстремума (для определенности - максимума), однако достичь этого удается лишь при f(X1) = f(X2) = f(X*) (проверку можно осуществить непосредственной подстановкой выражения f(X*) в оба указанных выше неравенства). Таким образом, из исходных предположений следует вывод о принадлежности X1, Х2 множеству {X*}, причем этот вывод относится к любым Х1, Х2, допустимым по условию построения отрезка, содержащего выбранную точку X* (в частности, к любым точкам этого отрезка). Заметим теперь, что указанными свойствами могут обладать лишь точки, находящиеся на границе многогранника U (если бы X* оказалась внутренней точкой, было бы нетрудно нарушить условие f(X1) = f(X2) = f(X*), построив прямые, лежащие в разных плоскостях; см. рис. 1.6). Следовательно, множество {X*} является либо гранью, либо ребром выпуклого многогранника, но в таком случае оно обязательно содержит хотя бы одну крайнюю точку, которая может рассматриваться как экстремальная.

Сделанные замечания легко переносятся на случай, когда {X*} содержит всего один элемент - единственную точку X*. Здесь равенства f(X1) = f(Х2) = f(Х*) означают совпадение Х1, Х2, X*, вследствие чего необходимо признать X* крайней точкой U.

Рис. 1.6
Рис. 1.6

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

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"