1,11 Mb.страница3/21Дата конвертации07.08.2012Размер1,11 Mb.Тип Смотрите также: 3 ^ Раздел 1. Основы теории оптимизации Лекция 1.1. Введение в теорию оптимизации. Введение. Теория оптимизации широкий раздел математики, в котором рассматриваются соответствующие задачи. Если речь идет об исследовании функций в конечномерных пространствах, то раздел этой теории называют математическим программированием. Самая общая формулировка такого рода задач может быть записана в виде , т.е. требуется минимизировать значение некоторой функции f на множестве W, являющемся частью евклидова пространства Rn. Наиболее простой частный случай этой задачи, когда f дифференцируемая функция, a W открытое множество (например, W = Rn), изучается в курсе математического анализа и для R1 известен уже школьникам. В этом случае речь идет об использовании теоремы Ферма, дающей необходимое условие оптимума в виде равенства нулю значения производной функции f. В математическом анализе изучается и другой частный случай указанной проблемы, когда W задается как множество решений некоторой системы уравнений вида , где fi также дифференцируемые функции. Это классические задачи на условный экстремум, и в этом случае применяется известное правило множителей Лагранжа, формально сводящее вопрос к прежнему случаю переходом к функции , гдеyi новые переменные,которые и называются множителями Лагранжа. Собственно задачи математического программирования, которые условно можно было бы назвать «неклассическими» задачами на условный экстремум, отличаются от «классических» тем, что уравнения заменяются неравенствами. Следует отметить, что математическая база для исследования этого нового класса задач на условный экстремум получена еще в начале XX столетия. Так, лемма Фаркаша, лежащая в основе теории линейных задач математического программирования (линейного программирования), получена уже в 1902 г. Появление нового раздела в теории оптимизации «запаздывало» ввиду отсутствия социального заказа. Именно потребности экономических исследований и явились заказом такого рода. Можно сказать, что своим рождением математическое программирование обязано экономике. Среди первых исследователей, стоявших у истоков нового направления, следует назвать Джона фон Неймана, в 20-х гг. положившего начало изучению задачи матричных игр, которая эквивалентна задаче линейного программирования. Он рассмотрел также линейную модель расширяющейся экономики, носящую теперь его имя. В 30-х годах В. В. Леонтьев начал изучать линейные балансовые модели применительно к экономике Америки. Датой рождения линейного программирования, по-видимому, следует считать 1939 г., когда вышла монография Л. В. Канторовича «Математические методы организации и планирования производства». В этой работе Л. В. Канторович уже отчетливо обозначил основные направления развития нового раздела прикладной математики, получившего в дальнейшем название «линейное программирование». На примерах конкретных моделей Л. В. Канторович показал эффективность разработанного им метода для решения различных задач практического планирования (задача о распределении программы, задача рационального раскроя, распределение грузов по нескольким видам транспорта и т. п.). Сам метод, названный автором методом разрешающих множителей, фактически использовал основные элементы возникшей позже теории двойственности. В том же году А. И. Толстой опубликовал статью «Методы устранения нерациональных перевозок при планировании», в которой намечает пути исследования широко известной теперь транспортной задачи. Несколько позже, в 1947 г., американский математик Дж. Данциг предложил свой метод решения задач линейного программирования, получивший название «симплекс-метода». После этого начался период бурного развития нового направления, его методов и приложений в разных областях конкретной экономики: нефтепереработке, пищевой промышленности, сельском хозяйстве, металлургии, металлообработке, на транспорте и т.д. В настоящее время математическое программирование оформилось в виде самостоятельного раздела теории оптимизации и по-прежнему вызывает интерес многочисленных исследователей. По этой тематике издаются журналы, ежегодно проводятся различные конференции. В том или ином виде математическое программирование включается в учебные программы для подготовки как математиков, так и экономистов. Работы Л. В. Канторовича получили высокую оценку мировой научной общественности в 1975 г. ему была присуждена Нобелевская премия по экономике. ^ Примеры моделей, приводящих к задачам линейного программирования С целью дать общее представление о характере задач, которыми нам предстоит заниматься, рассмотрим несколько типичных модельных примеров. Эти примеры призваны лишь проиллюстрировать общую постановку задачи линейного программирования. В то же время они позволяют увидеть характерные особенности возникающего класса математических задач, а также обозначить общие подходы к их исследованию. ^ 1. Задача о диете Изучается вопрос о рационе кормления некоего живого существа. Пусть на данном этапе развития этого существа наиболее важными для него являются три питательных вещества. Условно будем говорить о витаминах Е, F и PP. Пусть в
Задачи по линейному программированию и оптимизации 1 чел. помогло.
Раздел 1. Основы теории оптимизации - Задачи по линейному программированию и оптимизации
Комментариев нет:
Отправить комментарий