Типичные классы задач исследования операций

Классические задачи исследования операций

=== Скачать файл ===

Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду х и х годов. Исследование операций — это научная подготовка принимаемого решения — это совокупность методов, предлагаемых для подготовки и нахождения самых эффективных или самых экономичных решений. Целью исследования операций является предварительное количественное обоснование оптимальных решений в соответствие с некоторым критерием эффективности. Природа систем, фигурирующих в приведенном определении под именем 'организационных', может быть самой различной. В самых разнообразных областях человеческой деятельности встречаются сходные между собой задачи:. Имеется ряд предприятий, использующих различные виды сырья; имеется ряд сырьевых баз. Базы связаны с предприятиями различными путями сообщения железные дороги, автотранспорт, водный, воздушный транспорт. Каждый транспорт имеет свои тарифы. Требуется разработать такой план снабжения предприятий сырьем, чтобы потребности в сырье были удовлетворены при минимальных расходах на перевозки. Сооружается участок железнодорожной магистрали. В нашем распоряжении определенное количество средств: Требуется назначить очередность работ, распределить людей и технику по участкам пути таким образом, чтобы завершить строительство в минимальные сроки. Под операцией понимается всякая система действий мероприятие , объединенных единым замыслом и направленных к достижению какой-то цели. Их значения считаются заданными до начала решения задачи. Постоянные параметры обозначаются начальными буквами латинского алфавита ;. Переменные параметры обозначаются конечными буквами латинского алфавита и называются переменными задачи. Значения переменных не определены перед началом решения задачи. Операция - это управляемое мероприятие, то есть от нас зависит, каким способом выбрать переменные параметры, характеризующие его организацию. Те параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут быть различные числа, векторы, функции, физически признаки и т. Элементами решения здесь будут числа xij , показывающие, какое количество грузов будет отправлено из i -того пункта отправления в j -ый пункт назначения. Чтобы сравнить между собой различные варианты, необходимо иметь какой-то количественный критерий — показатель эффективности W. Данный показатель называется целевой функцией. Этот показатель выбирается так, чтобы он отражал целевую направленность операции. Выбирая решение, стремимся, чтобы данный показатель стремился к максимуму или к минимуму. Если W — доход, то W max; а если W — расход, то W min. Если выбор зависит от случайных факторов погода, отказ техники, колебания спроса и предложения , то в качестве показателя эффективности выбирается среднее значение — математическое ожидание —. В качестве показателя эффективности иногда выбирают вероятность достижения цели. Здесь цель операции сопровождается случайными факторами и работает по схеме ДА-НЕТ. Задачи, рассматриваемые в теории операций обладают рядом общих признаков и решаются сходными методами. Построение математической модели, т. При решении любой конкретной задачи применение методов исследования операций заключается в следующем:. Ориентация на принятие решений. Основные результаты анализа должны иметь непосредственное и полностью определенное отношение к выбору способа действий стратегии или тактики ;. Оценка на основе критерия экономической эффективности. Сравнение различных возможных вариантов действий должно основываться на количественных оценках, позволяющих однозначно определить полезность ожидаемого исхода. Количественные оценки для коммерческих фирм обычно предполагают использование таких измеримых величин, как расходы, доходы, наличие денежных средств , норма прибыли от дополнительных капиталовложений и т. В рекомендуемом решении должен быть достигнут оптимальный баланс с учетом всех, нередко противоречивых факторов;. Процедуры обращения с упомянутыми выше параметрами должны быть определены настолько точно, чтобы любой специалист в области системного анализа смог их трактовать совершенно однозначно. Это условие отнюдь не является лишь желательным, оно скорее необходимо. Это обуславливается сложностью используемых математических моделей и большим объемом исходных данных. Вычисления могут быть громоздкими — необходимо использовать ЭВМ; а могут быть несложными, но в больших объемах статистические модели. Накопленный опыт в решении задач исследования операций и его систематизация позволили выделить следующие типы задач:. С ростом запасов, увеличиваются расходы на их хранение, но снижаются потери, связанные с возможной их нехваткой. Одна из задач управления запасами заключается в определении такого уровня запасов, который минимизирует следующие критерии:. Эти задачи возникают тогда, когда существует определенный набор операций работ , которые необходимо выполнить, а наличия ресурсов для выполнения операций наилучшим образом не хватает. В зависимости от условия задачи эти также делятся на 3 группы:. Распределить ресурсы между работами таким образом, чтобы максимизировать некоторую меру эффективности прибыль или минимизировать ожидаемые затраты издержки производства. Определить, какой состав работ можно выполнить с учетом этих ресурсов, чтобы обеспечить максимум некоторой меры эффективности. Какую продукцию следует производить, чтобы получить максимальный доход? Определить, какие ресурсы необходимы для того, чтобы минимизировать суммарные издержки производства. Какое количество экипажей необходимо подобрать, чтобы выполнить план с минимальными затратами? Имеется система, состоящая из некоторого набора каналов обслуживания. На вход системы поступает поток клиентов заявки , имеющий случайный характер, т. Если каналов обслуживания много, очереди не образуется, но возможны простои каналов обслуживания. Если каналов мало — образуется очередь. А следовательно, возможны затраты, связанные с ожиданием в очереди клиента или с отказом клиента от обслуживания. Для решения задач используется теория массового обслуживания. Эти задачи часто встречаются в производстве. Предположим, что в цехе изготавливается множество деталей по разным технологическим маршрутам. В парке оборудования имеется ограниченное число станков токарный, фрезерный, строгальный и др. На одном станке в данный момент времени может обрабатываться только 1 деталь. Появляется очередность выполнения работ , то есть появляются детали, ждущие обработки. Время обработки каждой детали обычно известно. Такая задача называется задачей календарного планирования или составлением расписания работ. Выбор очередности запуска деталей в обработку является задачей упорядочивания. В таких задачах в качестве критерия эффективности часто встречаются следующие:. Запаздывание определяется как разность фактическим и плановым сроком обработки каждой детали. Требуется определить сроки каждой операции, при которых:. Определить сроки начала каждой операции, чтобы минимизировать время на выполнение всего комплекса операций. Типичной задачей является задача выбора оптимального маршрута из нескольких вариантов. Стоимость прохождения и время на прохождение зависит от выбранного маршрута. При рассмотрении ряда маршрутов вводятся ограничения:. Задержки носят случайный характер. Данные задачи наиболее изучены и в литературе носят специфические названия — задача о коммивояжере или задача о максимальном потоке. Эти задачи нельзя решать независимо друг от друга. Причем, критерии эффективности этих задач часто противоречат друг другу. В свою очередь методы математического программирования делятся на следующие:. Рассмотренные выше классы задач можно решать указанными методами. Методами математического программирования решаются следующие классы задач:. Методом имитационного моделирования решаются комбинированные задачи. Данным методом можно решить задачу любого класса. Экономико-математическая модель — математическое описание исследуемого экономического процесса или объекта. На первом этапе ставятся цели и задачи исследования, проводится качественное описание объекта в виде экономической модели. Для определения каких величин должна быть построена модель, т. Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы? В чем состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному наилучшему решению задачи? Для построения математической модели остается только идентифицировать переменные и представить цель и ограничения в виде математических функций этих переменных. Предприятие изготавливает два вида продукции - П1 и П2, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья - А и В. Опыт работы показал, что суточный спрос на продукцию П1 никогда не превышает спроса на продукцию П2 более чем на 1 ед. Кроме того, известно, что спрос на продукцию П2 никогда не превышает 2 ед. Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализация продукции был максимальным? Предположим, что предприятие изготовит х1 единиц продукции П1 и х2 единиц продукции П2. Задачу легко обобщить на случай выпуска п видов продукции с использованием т видов ресурсов. Предприятие имеет m моделей машин различных мощностей. Задан план по времени и номенклатуре: Т i - время работы каждой машины; продукции j -го вида должно быть выпущено не менее Nj единиц. Необходимо также учесть неотрицательность переменных. Задача поставлена так, чтобы израсходовать все отведенное время работы машины, т. При этом количество выпускаемой продукции каждого вида должно быть по крайней мере не менее Nj. Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела. Обозначим — количество кормов I и II, входящих в дневной рацион. Тогда этот рацион см. Так как содержание питательных веществ в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим систему неравенств:. Итак, экономико-математическая модель задачи: Составить экономико-математическую модель задачи. Прежде всего определим всевозможные способы распила бревен, указав соответствующее число получаемых при этом брусьев табл. Имеется три поставщика и четыре потребителя однородной продукции. Известны затраты на перевозку груза от каждого поставщика каждому потребителю. Обозначим их cij, ,. Запасы грузов у поставщиков равны ai,. Известны потребности каждого потребителя bi,. Будем считать, что суммарные потребности равны суммарным запасам:. Требуется составить такой план перевозок, чтобы обеспечить минимальные суммарные затраты при полном удовлетворении потребностей. Введем переменные хij - количество груза, перевозимого от i -го поставщика j -му потребителю. Ограничения задачи выглядят следующим образом:. Временем рождения линейного программирования принято считать г. Данциг в году разработал весьма эффективный конкретный метод численного решения задач линейного программирования он получил название симплекс метода. Оптимизационная задача — это экономико-математическая задача, которая состоит в нахождении оптимального максимального или минимального значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т. Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешимой, если целевая функция f Х не ограничена сверху на допустимом множестве W. Методы решения оптимизационных задач зависят как от вида целевой функции f Х , так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования. Линейное программирование является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач линейного программирования следующие:. Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:. При этом система линейных уравнений 2. При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность означает, что вклад каждой переменной в целевой функции и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если, продавая j -й товар в общем случае по цене рублей, фирма будет делать скидку при определенном уровне закупки до уровня цены 95 рублей, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной x j. Аддитивность означает, что целевая функция и ограничения должны представлять собой сумму вкладов от различных переменных. Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого. Оптимальное решение — это план, при котором целевая функция принимает свое максимальное минимальное значение. Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот. Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:. Введем в каждое уравнение системы ограничений выравнивающие переменные x 4, x 5, x 6. Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:. Далее остается только идентифицировать переменные и представить цель и ограничения в виде математических функций этих переменных. Мы рассмотрели выше в п. Обобщая их, можно сделать следующие выводы. Ограничения в задачах линейного программирования могут быть выражены как равенствами, так и неравенствами. Каждое из неравенств 2. В том случае, если система неравенств 2. Так как множество точек пересечения данных полуплоскостей — выпуклое, то областью допустимых значений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств. Вектор с координатами с2 и с1, перпендикулярный к этим прямым, указывает направление наискорейшего возрастания Z , а противоположный вектор — направление убывания Z. Если в одной и той же системе координат изобразить область допустимых решений системы неравенств 2. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня , проходящую через начало координат и перпендикулярную вектору , и будем передвигать ее в направлении вектора до тех пор, пока она не коснется последней крайней угловой точки многоугольника решений. Координаты указанной точки и определяет оптимальный план данной задачи. Заканчивая рассмотрение геометрической интерпретации задачи 2. Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора , а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения. Оптимум функции Z достигается в любой точке АB. Область допустимых решений — пустая область. Для практического решения задачи линейного программирования 2. Построить прямые, уравнения которых получаются в результате замены в ограничениях 2. Построить прямую , проходящую через начало координат и перпендикулярную вектору. Передвигать прямую Z в направлении вектора , в результате чего либо находят точку точки , в которой функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве планов. Определить точки координаты максимума функции и вычислить значение целевой функции в этой точке. Рассмотрим решение задачи об ассортименте продукции пример 2. Построим многоугольник решений рис. Для этого в системе координат X10X2 на плоскости изобразим граничные прямые:. Взяв какую-либо точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство. Полуплоскости, определяемые неравенствами, на рис. Областью решений является многоугольник OABCD. Точка С лежит на пересечении прямых L1 и L3. Для определения ее координат решим систему уравнений:. Полученное решение означает, что объем производства продукции П 1 должен быть равен 2,4 ед. Доход, получаемый в этом случае, составит: Следовательно, путь решения любой задачи линейного программирования: Число перебираемых угловых точек можно сократить, если производить перебор с учетом изменений линейной функции, т. Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. Однако из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем — к оптимальной точке С. Для реализации симплексного метода — последовательного улучшения решения — необходимо освоить три основных элемента: Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т. Лекции по курсу Исследование операций. Общие понятия Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду х и х годов. В самых разнообразных областях человеческой деятельности встречаются сходные между собой задачи: Примеры задач 1 План снабжения предприятия. Каждая операция или, другими словами, задача характеризуется некоторым набором параметров. Постоянные параметры обозначаются начальными буквами латинского алфавита ; - переменные — их значения мы можем выбирать по нашему усмотрению в заданных пределах. Каждый определенный набор значений переменных параметров называется решением. Подписаться на рассылку Pandia. Интересные новости Важные темы Обзоры сервисов Pandia. Основные порталы, построенные редакторами. Каталог авторов частные аккаунты. Все права защищены Мнение редакции может не совпадать с мнениями авторов. Минимальная ширина экрана монитора для комфортного просмотра сайта: Мы признательны за найденные неточности в материалах, опечатки, некорректное отображение элементов на странице - отправляйте на support pandia. Расход сырья на 1 ед. О проекте Справка О проекте Сообщить о нарушении Форма обратной связи. Авторам Открыть сайт Войти Пожаловаться. Архивы Все категории Архивные категории Все статьи Фотоархивы. Лента обновлений Педагогические программы. Правила пользования Сайтом Правила публикации материалов Политика конфиденциальности и обработки персональных данных При перепечатке материалов ссылка на pandia.

Почему сайты отображаются текстом

Совместимость знаков зодиака женщин

Характеристика класса по фгос

Типичные классы задач исследования операций

Классические задачи исследования операций

=== Скачать файл ===

Классы операционных задач

Лекции по курсу Исследование операций

Принятие решений в условиях определенности

Report Page