Опорный конспект лекции дисциплины «Методы оптимизации и исследование операции» (стр. 1 )

Методические указания

Ф СО ПГУ 7.18.2/05

Министерство образования и науки Республики Казахстан

Павлодарский государственный университет им. С. Торайгырова

Кафедра информатики и информационных систем

Опорный конспект лекции

дисциплины «Методы оптимизации и исследование операции»

для специальностей 050602-Информатика,

050703 Информационные системы

Павлодар

Лист утверждения к методическим указаниям

Форма Ф СО ПГУ 7.18.1/05

УТВЕРЖДАЮ Декан ФФМиИТ _________ "___" __________200__г.

Составители: доцент ,

преподаватель

Кафедра «Информатика и информационные системы»

Опорный конспект лекции

по дисциплине «Методы оптимизации и исследование операции»

для студентов специальностей 050602-Информатика,

050703 Информационные системы,

Рекомендована на заседании кафедры от “__28__”_августа__2008г.

Протокол № __1_

Заведующая кафедрой ___________

Одобрена учебно-методическим советом факультета Физики, математики и информационных технологий “_1_”__сентября____2008г. Протокол №_1__

Председатель УМС__________________________

ВВЕДЕНИЕ

Понятие «оптимальный» прочно вошло в жизнь: если у рассматриваемой задачи есть множество решений, то естественно выбирается то из них, которое квалифицируется как лучшее. Математически проблема оптимальности описывается множеством V и функцией J, определенной на V со значением в R. Таким образом, речь идет о том, чтобы найти решение и такое, что

uÎV

J(u)£ J(v) "vÎV (*)

V – множество возможных способов достижения определенной цели или множество способов функционирования какой-нибудь системы (область ограничения).

Функция J – критерий, который предопределяет ваш выбор из множества возможных решений.

В задаче (*) надо выбрать решение u которое минимизирует значение функции J на множестве V. Если заменить J на –J, то задача преобразуется в задачу максимизации. На практике функцией J может быть стоимость, выработка, прибыль, время и т. д.

Решение задачи (*) может не существовать, тогда ищут реализуемое решение и, такое, чтобы J(u) было «достаточно близко» к inf J(v).

vÎV

Множество V описывается обычно с помощью уравнений и неравенств, которые связывают различные параметры системы. Однако сложные системы с трудом поддаются формализованному описанию, а полученные модели – численному исследованию. В таком случае довольствуются моделями, которые представляют собой упрощенное описание физической реальности.

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

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

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

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

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

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

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

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

Формальная постановка задачи.

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

Задача заключается в нахождении значений n переменных х1,х2,….хn, которые называются здесь "инструментами". Переменные, записанные в виде вектора-столбца

x= =(x1,x2,..xn) (2.1.1)

они составляют вектор инструментальных переменных в n-мерном евклидовом пространстве Е.

Если вектор инструментальных переменных х удовлетворяет ограничениям задачи, он называется допустимым, а множество всех допустимых векторов образует множество возможностей Х. Допустимое множество является подмножеством Е. Так как задача заключается в выборе инструментальных переменных из допустимого множества, то в любой нетривиальной задаче оно является непустым (т. е. система ограничений совместна) и содержит, по крайней мере две различные точки.

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

F=F(x)=F(x1,x2,..,xn). (2.1.2)

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

max F(x) при условии, что x X

x

где Х-подмножество n-мерного евклидового пространства.

Учитывая, что максимизация F(x) эквивалентна максимизации, а+bF(x), b>0, или минимизация a+bF(x), b<0, можно сделать вывод, что введение дополнительного слагаемого или положительного множителя в целевую функцию не изменяет задачи. В то время как отрицательный множитель может быть использован для преобразования задачи максимизации в задачу минимизации и наоборот.

Примеры линейных моделей:

Задача о диете.

Рассмотрим задачу составление наиболее экономного (т. е. наиболее дешевого рациона) питания, удовлетворяющее определенным медицинским требованиям (в армии, санаториях и т. д.)

Предполагаем, что известен перечень доступных продуктов из n-наименований (хлеб, сахар, масло, молоко и т. д.), которые обозначают буквами F1, F2, ...

Рассматриваются характеристики продуктов такие, как витамины, минеральные вещества, жиры, белки, калорийность и т. д. – N1, N2, ... , Nm.

Пусть для каждого продукта Fi (i=1,2,...,n) известна его медицинская характеристика, т. е. количественное содержание в одной единице (кг, гр) продукта указанных компонент.

То можно составить таблицу-справочник, содержащий характеристику продуктов.

F1 FFn

N1 a11 a1a1n a1a1n

N2 a21 a2a2n A= . . .

. amamn

Nm am1 am2 . . . amn

Допустим, что составили рацион х=(х1, . . ., хm) на некоторый срок (месяц), т. е. планируем каждому человеку на месяц х1 единиц (кг, гр) продукта F1, х2 – F2 и т. д. Нетрудно вычислить, какое количество витаминов, жиров и т. д. получит человек.

Именно компонента N1 присутствует в этом рационе в общем количестве:

а11х1+а12х2+ . . . +а1nхn, соответственно и для других.

Допустим, что имеются вполне определенные медицинские требования, касающиеся необходимого человеку количества каждой из компонент Ni (i=1, ..., m). Например, количество витаминов С не должна быть меньше заданного (цинга). Т. е. координаты xi вектора х должны удовлетворять следующей системе ограничений.

а11х1+а12х2+ . . . +а1nхn³ b1

. (1) (x1³0, ..., xm³0)

аm1х1+аm2х2+ . . . +аmnхn³ bm

Любой рацион должен удовлетворять условиям (1), но таких рационов множество.

Пусть цены на F1,..., Fn равны соответственно С1,...,Сn. Следовательно, стоимость всего рациона x=(x1,...,xn) может быть записана

с1х1+...+ спхп (1.3)

Окончательная формулировка задачи о диете такова: среди всех векторов x=(x1,...,xn), удовлетворяющих ограничениям (1) выбран такой, для которых выражение (1.3) принимает минимальное значение.

Выпуклое программирование.

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

()®min , (1)

выпуклых функций на выпуклых множествах конечномерного пространства Rn.

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

При формулировке основной задачи выпуклого программирования (1) принято множество задавать в форме =, где Q и компоненты m-вектор функции g() - выпуклые множество и функции.

Определение: Множество из n-мерного евклидова пространства Rn называется выпуклым, если наряду с двумя своими точками содержит и весь отрезок, соединяющий их (рис.1) . Другими словами, если 1,2 Х, то =1+(1-)2 при всех [0,1]

Рис 1.

Определение: Функция(), определенная и конечная на выпуклом множестве , называется выпуклой, если для 1 и 2 при всех [0,1] выполняется неравенство

(1+(1-)2)(1)+(1-)(2)