Лекции по "Развитию операционных систем"

Лекция 15.

 

п.15.  Основы математического моделирования.

Математическая модель.

 

15.1.  Введение.

 

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

Исследование операций, как наука появилась сравнительно недавно, и в настоящее время является одной из быстро развивающихся отраслей науки, проникающая во все более широкие области применения.

Что такое исследование операций? Для уяснения этого понятия воспользуемся двумя определениями.

1.  Исследованием операций называется теория математических моделей принятия оптимальных решений и практика их использования.

2.  Исследование операций представляет собой искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими способами.

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

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

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

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

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

С некоторыми классами задач, что рассматриваются в исследовании операций, мы столкнулись при изучении раздела «Элементы теории графов»: задача коммивояжера (метод ветвей и границ); задача о формировании на сети максимального потока; задача сетевого планирования.

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

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

В разделе «Основы математического моделирования» мы рассмотрим некоторые задачи, которые нашли применение в организации производства в машиностроении.

 

 

15.2.  Математическая модель.

 

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

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

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

Построение математической модели – своего рода искусство, которым можно овладеть только опытным путем, постепенно. И начнем изучение моделей задач матема-тического программирования.

 

Модель задачи математического программирования включает:

1)  план задачи (вектор управления, решение, стратегия, поведение и др.) – сово-купность неизвестных величин , действуя на которые, систему можно совершенствовать;

2)  целевую функцию (показатель эффективности, критерий оптимальности, функ-ционал задачи и др.) – функция, экстремальное значение которой нужно найти в условиях экономических возможностей. Целевую функцию обозначим . Это может быть прибыль, объем выпуска или реализации, затраты производства, уровень обслуживания, число комплектов, отходы и т.д.;

3)  систему ограничений (условия), налагаемые на неизвестные величины. Огра-ничениями являются материальные, финансовые и трудовые ресурсы, возможности технического, технологического и вообще научного потенциала. Математически огра-ничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений. Объединение всех условий (ограничений), налагаемых на неизвестные (искомые) величины задачи, обозначим буквой W ( ).

 

В развернутом виде математическую модель можно представить следующим образом:

Найти план , доставляющий экстремальное значение целевой функции Z, т.е.

при ограничениях

.

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

,

иногда – целочисленности.

 

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

 

 

15.3.  Классификация методов

математического программирования.

 

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

1)  задачи линейного программирования (ЗЛП), если целевая функция и функции, входящие в систему ограничений, линейны (первой степени) относительно входящих в задачу неизвестных . Методы и модели линейного программирования широко приме-няются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределения ее по исполнителям, при размещении заказов между исполнителей и по временным интервалам; при планировании грузопотоков; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т.д.

2)  задачи нелинейного программирования (НЛП), если в задаче математического программирования целевая функция и (или) хотя бы одна из функций системы ограничений нелинейны. Методы НЛП получили широкое применение при расчете экономически выгодных партий запуска деталей в производство, при определении поставочного комплекта, размеров запаса, размещении производительных сил и т.д.

3)  задачи целочисленного (ЦП) или дискретного программирования, если на все или некоторые переменные наложено условие дискретности, например, целочислен-ности. Методами ЦП решается широкий круг задач оптимизации с неделимостями, комбинаторного типа, с логическими условиями, с разрывной целевой функцией и т.д. В частности, задача выбора (о назначениях), о контейнерных перевозках (о рюкзаке), о маршрутизации (задача коммивояжера), теории расписаний и т.д.

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

 

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

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

 

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

К математическому программированию относятся также методы решения экстремальных задач с бесконечным числом переменных – бесконечномерное программ-мирование.

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

 

 

п.16.  Линейное программирование.

 

16.1.  Виды ЗЛП.

 

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

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

 

 

Задача о наилучшем использовании ресурсов.

 

Пусть некоторая производственная единица (цех, завод, объединение и т.д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначенными индексом , где каждый j-ый вид продукции обозна-чим Пj. Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.). Все эти виды ограничивающих факторов называют ингредиентами Ri. Пусть их число равно m; припишем им индекс . Они ограничены, и их количества равны соответственно условных единиц. Таким образом, – вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства и т.д. Примем в качестве такой меры, например, цену реализации , т.е. – вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов называют технологической и обозначают буквой A, т.е. .