Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




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

6.7. Угловые точки и допустимые решения

Почему же угловые точки выпуклого многогранника заслужили столь пристальное внимание? Ответ заключен в следующем весьма важном факте (было обещано его доказать).

Всякая линейная форма F(X) = γ0 + γ1x1 + ... + γnxn, значения которой рассматриваются в точках некоторого выпуклого многогранника Q, достигает своего наименьшего (наибольшего) значения в одной из его угловых точек. Если F (X) принимает наименьшее (наибольшее) значение более, чем в одной угловой точке, то она принимает то же значение в каждой точке, являющейся их выпуклой комбинацией.

В самом деле, по условию значения формы F (X) рассматриваются в точках многогранника Q. Обозначим через X(1), ..., X(n) его угловые точки (по определению выпуклого многогранника их конечное число). Допустим, что наименьшее значение F (X) достигает в некоторой точке X0 многогранника Q; иными словами, F(X0) = minF(X) = F*. Значит, для любой иной точки X из Q справедливо неравенство F (X) ≥ F (X0). Если X0 - одна из угловых точек, то первая часть утверждения уже доказана. Предположим, что X0 - не угловая точка. Но тогда X0 является выпуклой комбинацией угловых точек:

X0 = λ1X(1) + ... + λmX(m),

λk≥0 (k = 1, ..., m); λ1 + ... + λm = 1.

В силу свойств линейности формы F(X) ее значение в точке X0

F(X0) = F(λ1X(1) + ... + λmX(m)) = F(λ1X(1)) + ... + F(λmX(m)) = λ1F(X(1)) + ... + λmF(X(m)) (40)

оказывается выпуклой комбинацией значений в угловых точках. Проверяется этот факт непосредственным вычислением. Выберем наименьшую из величин F(X(1)), ..., F (X(m)); пусть это будет F(X(k)). Тогда F(X(i))≥F(X(k)) (i = 1, ..., m) и из (40) вытекает неравенство

F (X0) ≥ F (X(k)) (λ1 + ... + λm) = F (X(k)).

Однако по предположению F(X0)≤F(X) для любой точки X из Q, и, конечно, F (X0) ≤ F (X(k)). Остается предположить равенство F (X0) = F (X(k)), т. е. что наименьшее значение достигается по крайней мере в угловой точке X(k). Этим первая часть утверждения доказана.

Перейдем к доказательству второй части. Пусть F (X) достигает наименьшего значения F* в каждой из угловых точек (нумерация несущественна) Х(1), ..., Х(l) Составим их произвольную выпуклую комбинацию

X = λ1X(1) + ... + λlX(l); λl≥0 (i = 1, ..., l); λ1 + ... + λl = 1.

Тогда значение формы F(X) в точке X оказывается также наименьшим:

F(X) = λ1F (Х(1)) + ... + λlF (Х(1)) = λ1F* + ... + λlF* = F*.

Утверждение полностью доказано.

Мы приходим к выводу, что оптимальные значения формы F(X) на многограннике Q допустимых решений системы ограничений (30) задачи линейного программирования следует искать среди значений в угловых точках Q.

Но как находить эти угловые точки? Возможно ли их выявить, опираясь лишь на рассмотрение системы (30)?

Ответ на поставленный вопрос положительный: угловые точки выявляются вместе с нахождением допустимых базисных решений системы (30). Более точный ответ дает следующее утверждение.

Каждое допустимое базисное решение системы ограничений (30) задачи линейного программирования (например, решение x1 = ... = xk = 0; xk+1 = β1, ..., xk+r = β, уравнений (34)) определяет единственную угловую точку X. = (0, ..., 0, β1, ..., βr) многогранника Q. Обратно, каждая угловая точка X. многогранника Q определяет некоторое (вообще говоря, не единственное) допустимое базисное решение системы (30).

Это утверждение (доказательство см. в [17]) позволяет оценить верхнюю границу возможного числа угловых точек многогранника Q: угловых точек не больше, чем имеется в системе (30) допустимых базисных решений.

Будем считать, что ранг r системы (30) совпадает с числом m уравнений. В ином случае можно сохранить в системе только r линейно независимых уравнений, а остальные отбросить. Ранее отмечено (см. с. 114), что для задач линейного программирования интересен случай r<n. В линейной алгебре доказано, что разрешить систему (30) относительно неизвестных (базисных) xk+1, ..., xk+r и выразить их через свободные неизвестные x1, ..., xk можно тогда и только тогда, когда в матрице


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

Подобно этому выразить любые иные r базисных неизвестных xσ1, ..., xσr через остальные - свободные неизвестные xσr+1, ..., xσr+k можно лишь тогда, когда минор матрицы A, составленный из столбцов коэффициентов, отвечающих этим базисным переменным, отличен от нуля:


Легко подсчитать, что всех миноров порядка r в матрице А столько, сколько можно составить сочетаний из n столбцов по r, а именно:


Следовательно, существует не более, чем Crn различных базисных решений (ведь не все миноры порядка r матрицы А отличны от нуля). Кроме того, не всякое базисное решение является допустимым. Поэтому угловых точек заведомо не больше, чем Cnr. При r = 5, n = 10, C105 = 756. О примерном числе угловых точек можно составить представление по таблице:


Как видно, число угловых точек велико даже для относительно малых m и n. В практических задачах значения тип могут достигать нескольких сотен. Поэтому поиск тех угловых точек, которые доставляют форме F (X) оптимальное значение путем простого перебора, хотя и осуществим теоретически (ведь их конечное число!), практически является предприятием бесперспективным.

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

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



ИНТЕРЕСНО:

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru