ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Классификация методов исследования операций.

Предыдущая 1 234 5 6 7 8 9 10 11 12 13 14 15 16 Следующая

К основным методам отыскания оптимальных решений относится математическое программирование. В свою очередь методы математического программирования делятся на следующие типологические блоки:

· линейное программирование,

· нелинейное программирование,

· динамическое программирование,

· целочисленное программирование,

· стохастическое программирование,

· эвристическое программирование,

· теория массового обслуживания,

· сетевые модели планирования и управления,

· имитационное моделирование.

Если критерий эффективности Z = f(x₁ ,x₂,.., x_n) представляет линейную функцию, а функции f_i(x₁ ,x₂,.., x_n) в системе ограничений также линейны, то такая задача является задачей линейного программирования. Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования. В частности, если указанные функции обладают свойством выпуклости, то полученная задача является задачей выпуклого программирования.

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

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

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

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

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

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

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

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

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

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

Задачи планировки и размещения состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой.

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

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

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

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

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

1. Задачи управления запасами.

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

В зависимости от условий, задачи управления запасами делятся на 3 группы:

o моменты поставок или оформления заказов на поставки, пополнение запасов фиксированы. Определить объемы производимой или закупаемой партии запасов;

o объемы производимой или закупаемой партии запасов фиксированы. Определить моменты оформления заказов на поставки;

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

2. Задачи распределения ресурсов.

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

1. Заданы работы и ресурсы. Распределить ресурсы между работами таким образом, чтобы максимизировать некоторую меру эффективности (прибыль) или минимизировать ожидаемые затраты (издержки производства).

Пример: известны производственное задание и производственные мощности предприятия. При существующих различных способах получения изделия, ограничения по мощности не позволяют для каждого изделия использовать наилучшую технологию. Какие способы производства надо выбрать, чтобы выполнить задание с минимальными затратами?

2. Заданы только наличные ресурсы. Определить, какой состав работ можно выполнить с учетом этих ресурсов, чтобы обеспечить максимум некоторой меры эффективности.

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

3. Заданы только работы. Определить, какие ресурсы необходимы для того, чтобы минимизировать суммарные издержки производства.

Пример: известно месячное расписание движения полетов пассажирских самолетов на авиалинии. Какое количество экипажей необходимо подобрать, чтобы выполнить план с минимальными затратами?

3. Задачи ремонта и замены оборудования.

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

4. Задачи массового обслуживания.

Данные задачи возникают там, где образуется очередь. С образованием очереди приходится сталкиваться как в производстве, так и в быту (производство: очередность выполнения заказа; в быту: магазин, поликлиника). Подобные задачи существуют и на транспорте. Очередь возникает из-за того, что поток клиентов (заказов) поступает неравномерно и имеет случайный характер. То есть поток клиентов неуправляем. Объект, который обслуживает клиента, называется каналом обслуживания (продавец, врач, взлетно-посадочная полоса). Если каналов обслуживания много, очереди не образуется, но возможны простои каналов обслуживания. Если каналов мало – образуется очередь. А следовательно, возможны затраты, связанные с отказом клиента от обслуживания.

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

5. Задачи упорядочивания.

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

6. Задачи сетевого планирования и управления (СПУ).

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

Ø должно существовать точно определяемое количество операций,

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

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

Ø известна взаимосвязь между ресурсами и продолжительностью выполнения операции.

Если все условия выполнены, возможны следующие постановки задачи:

1. Задана продолжительность выполнения всего комплекса операций. Требуется определить сроки каждой операции, при которых:

минимизируются общие затраты на выполнение всего комплекса операций,

определяется вероятность невыполнения комплекса работ в установленные сроки,

определяется среднеквартальные отклонения требуемых ресурсов от наличных.

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

2. Задачи маршрутизации.

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

3. Комбинированные задачи.

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

Пример: при планировании и управлении производством необходимо решить комплекс задач:

a. сколько изделий каждого вида необходимо выпустить и каковы оптимальные размеры партии изделий – задача планирования производства;

b. распределить заказы или детали по видам оборудования, причем оптимальный план производства задан – задача распределения;

c. определить в какой последовательности следует выполнить производственные заказы – календарное планирование.

Историческая справка.

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

Экстремальными задачами занимались многие античные ученые (Евклид, Архимед, Аристотель и др.). Известна следующая задача Евклида (IV век до н.э.): в заданный треугольник ABC вписать параллелограмм ADEF наибольшей площади. Нетрудно доказать, что решением этой задачи является параллелограмм, вершины D, E, F которого делят соответствующие стороны треугольника пополам.

Открытое И. Кеплером основное свойство экстремумов было затем оформлено в виде теоремы сначала П. Ферма (для многочленов), потом И. Ньютоном и Г. В. Лейбницем для произвольных функций и носит теперь название теоремы Ферма, согласно которой в точке экстремума x₀ непрерывной функции f (x) производная функции равна нулю.

С конца XVII до середины XX века теория экстремальных задач прошла огромный путь.

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

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

1) большие экстремальные задачи,

2) задачи оптимизации в условиях неопределенности.

Каждая конечномерная экстремальная задача имеет два размера: количество ограничений и количество переменных. Если эти размеры большие, то задача называется большой.

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

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

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

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

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

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

Наибольший вклад в формирование и развитие новой науки сделали Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Т. Саати, Р. Чермен (США), А. Кофман, Р. Форд (Франция) и др. Важная роль в создании современного математического аппарата и развития многих направлений исследования операций принадлежит Л.В. Канторовичу, Б.В. Гнеденко, М.П. Бусленко, В.С. Михалевичу, М.М. Моисееву, Ю.М. Ермолаеву, Н.З. Шору и др. За выдающийся вклад в разработку теории оптимального использования ресурсов в экономике академику Л.В. Канторовичу вместе с профессором Черльзом Купменсом (США) в 1975 г. присвоена Нобелевская премия в экономике.

В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л.В. Канторович, Н.П. Бусленко, Е.С. Вентцель, Н.Н. Воробьев, Н.Н. Моисеев, Д.Б. Юдин и многие другие. Особо следует отметить роль академика Л. В. Канторовича, который в 1939 г., занявшись планированием работы агрегатов фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудования, о раскрое материалов с наименьшими потерями, о распределении грузов по нескольким видам транспорта и др.

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

Предыдущая 1 234 5 6 7 8 9 10 11 12 13 14 15 16 Следующая