Математические методы исследования операций в экономике (стр. 20 из 37)
т. е. 
является внутренней точкой относительно ограниченияgi(x).Поэтому данное условие также называют условием телесности.
Вообще говоря, существуют разные варианты необходимого условия Куна—Таккера. Приведем один из них.
 Теорема 2.4. (Необходимое условие наличия экстремума).Если (D, f) является задачей выпуклого программирования с решением х, ее целевая функция f(x) и функции ограничений gi(x) — дифференцируемы, нелинейные ограничения в форме неравенств удовлетворяют условию регулярности Слейтера, то существует такой вектор и ≥ 0, что (х,и) — седловая точка функции Лагранжа Ф(х,и). |
Мы не будем здесь приводить доказательство теоремы (2.4), которое является довольно сложным. Заинтересованный читатель может найти его в таких источниках, как [1, 13].
Значение теоремы Куна—Таккера состоит в том, что она позволяет связать процесс решения оптимизационной задачи с поиском седловых точек функции Лагранжа, т. е., грубо говоря, с максимизацией этой функции по х и минимизацией по и.
ОпределимF(x)как функцию, ставящую в соответствие каждому значению х минимальное значение функции Ф(х,и) по и:
и по аналогии
Рассмотрим задачу отыскания максимума функцииF(x)
и задачу минимизации G(u)
Очевидно, что
Отсюда следует, что максимум F(x)находится в допустимой областиD и совпадает с максимумом целевой функцииf(x) задачи (2.28):
Таким образом, задача (2.34), в определенном смысле, равносильна (2.28). Аналогичные выводы могут быть получены и для (2.35). Задачи (2.34) и (2.35) образуют двойственную пару. Как нетрудно догадаться, данное отношение является обобщением отношения двойственности для задач линейного программирования. Соответственно, при определенных условиях пара двойственных задач нелинейного программирования обладает свойствами, аналогичными свойствам двойственных линейных задач. В частности, при любых х∊Х, и≥0
Условие (2.36) находит широкое применение при построении оценок в итеративных методах решения оптимизационных задач. Например, если имеется возможность приблизительно решить прямую и двойственную задачи и получить последовательности приближений {х(q)} и {и(q)}, то с помощью неравенств вида
можно определить момент остановки вычислительной процедуры.
В заключение отметим, что возможен вариант вывода выражений для целевых функций и ограничений пары двойственных задач линейного программирования из общего определения отношения двойственности для нелинейных задач. Также отметим, что в процессе формирования нелинейных двойственных задач существует большая неоднозначность: их вид можно варьировать, включая в множество Х часть ограничений gi(x)≤0.
- Общая задача нелинейного программирования.
- Условная и безусловная оптимизация.
- Прямые и непрямые методы решения оптимизационных задач.
- Стационарная точка.
- Градиентные методы.
- Метод наискорейшего спуска и методы дробления шага.
- Выпуклая и вогнутая функции.
- Матрица Гессе.
- Достаточное условие выпуклости (вогнутости).
- Задача выпуклого программирования.
- Допустимое направление.
- Прогрессивное направление.
- Седловая точка.
- Теорема Куна—Таккера.
- Условие регулярности Слейтера.
2.1. При каких условиях оптимизационная задача может быть отнесена к классу нелинейных?
2.2. Приведите пример экономической модели, сводящейся к задаче нелинейного программирования.
2.3. Перечислите основные трудности, возникающие в процессе решения задачи нелинейного
программирования.
2.4. Какой смысл вкладывается в понятие «условная оптимизация»?
2.5. Для чего предназначен метод множителей Лагранжа и в чем он состоит?
2.6. Какая точка называется стационарной?
2.7. Какие принципиальные этапы входят в градиентные методы?
2.8. Для решения каких задач предназначены метод наискорейшего спуска и метод дробления шага?
2.9. Дайте определение выпуклой (вогнутой) функции.
2.10. Сформулируйте достаточное условие выпуклости (вогнутости) функции.
2.11. В чем заключена специфика задач выпуклого программирования?
2.12. Перечислите основные этапы, входящие в метод допустимых направлений.
2.13. Сформулируйте задачу, которая должна быть решена при определении шага в методе
допустимых направлений.
2.14. Исходя из каких соображений определяется допустимое прогрессивное направление?
2.15. Какое условие используется для определения оптимальности текущей точки в методе
допустимых направлений?
2.16. Дайте определение седловой точки. Приведите пример функции, имеющей седловую точку.
2.17. Сформулируйте необходимое и достаточное условия теоремы Куна—Таккера. Какое значение
они имеют для решения задач нелинейного программирования?
2.18. В чем состоит условие регулярности Слейтера? Поясните его содержание.
2.19. Какое условие получило название «правила дополняющей нежесткости»?
2.20. Приведите пример пары двойственных задач нелинейного программирования.
2.21. Какие свойства пары нелинейных двойственных задач могут быть применены для их решения?
ГЛАВА 3. ТРАНСПОРТНЫЕ И СЕТЕВЫЕ ЗАДАЧИ
Методы, рассмотренные в предыдущих главах, носили универсальный характер и были предназначены для решения очень широкого круга линейных и нелинейных задач. Платой за такую универсальность зачастую является снижение их эффективности, выражающееся в медленной сходимости, высоком объеме вычислений и т. п. В то же время существуют такие классы задач, для которых в силу их специфики разработаны более простые методы решения. Некоторых из них мы коснемся в этой главе.
3.1. ТРАНСПОРТНАЯ ЗАДАЧА И МЕТОДЫ ЕЕ РЕШЕНИЯ
3.1.1. Транспортная задача в матричной постановке и ее свойства. Вернемся к транспортной задаче в матричной, постановке, о которой мы уже упоминали при рассмотрении вопросов построения математических моделей. Напомним, что данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (║xi,j║mxn), который минимизирует целевую функцию
на множестве допустимых планов
при соблюдении условия баланса
Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения.
Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n)хmn. Матрицы систем уравнений в ограничениях (3.2) и (3.3) имеют ранги, равные соответственноm иn. Однако, если, с одной стороны, просуммировать уравнения (3.2) по m, а с другой — уравнения (3.3) по n, то в силу (3.5) получим одно и то же значение. Из этого следует, что одно из уравнений в системе (3.2)-(3.3) является линейной комбинацией других. Таким образом, ранг матрицы транспортной задачи равен m+n-1, и ее невырожденный базисный план должен содержать m+n-1 ненулевых компонент.
Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц, структура которых представлена на рис.3.1.
Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта аi), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится
цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (хi,j = 0), называют свободными, а ненулевые — занятыми (xi,j >0).