 |
Предмет и задачи исследования операций
|
|
|
|
И.Н. Слинкина
Учебное пособие для студентов педагогических вузов
по специальности «Информатика»
Шадринск, 2003
Слинкина И.Н.
Исследование операций. Учебно-методическое пособие. – Шадринск: изд-во Шадринского государственного педагогического института, 2002. - 106 с.
Слинкина И.Н. – кандидат педагогических наук
В учебном пособии представлена теоретическая часть курса «Исследование операций». Оно предназначено для студентов очного и заочного отделений факультетов, реализующих специальность «Информатика».
© Шадринский государственный педагогический институт
© Слинкина И.Н., 2002
Оглавление
Вопросы к блокам по курсу «Исследование операций» 5
Блок 1. 7
1.1. Предмет и задачи исследования операций 7
1.2. Основные понятия и принципы исследования операций 8
1.3. Математические модели операций 10
1.4. Понятие линейного программирования 12
1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов 13
1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий 15
1.7. Примеры экономических задач линейного программирования. Задача о смесях 16
1.8. Примеры экономических задач линейного программирования. Транспортная задача 17
1.9. Основные виды записи задач линейного программирования 19
1.10. Способы преобразования 21
1.11. Переход к канонической форме 22
1.12. Переход к симметричной форме записи 25
Блок 2. 28
2.1. Геометрическая интерпретация задачи линейного программирования 28
2.2. Решение задач линейного программирования графическим методом 29
2.3. Свойства решений задачи линейного программирования 34
|
|
|
2.4. Общая идея симплексного метода 35
2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом 36
2.6. Признак оптимальности опорного плана. Симплексные таблицы 40
2.7. Переход к нехудшему опорному плану. 44
2.8. Симплексные преобразования 46
2.9. Альтернативный оптимум (признак бесконечности множества опорных планов) 51
2.10. Признак неограниченности целевой функции 52
2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание 53
2.12. Понятие двойственности для симметричных задач линейного программирования 54
Блок 3 57
3.1. Несимметричные двойственные задачи 57
3.2. Открытая и закрытая модели транспортной задачи 61
3.3. Построение начального опорного плана. Правило "Северо-западного угла" 63
3.4. Построение начального опорного плана. Правило минимального элемент 64
3.5. Построение начального опорного плана. Метод Фогеля 64
3.6. Метод потенциалов 65
3.7. Решение транспортных задач с ограничениями по пропускной способности 69
3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении 71
3.9. Сущность методов дискретной оптимизации 72
3.10. Задача выпуклого программирования 74
3.11. Метод множителей Лагранжа 75
3.12. Градиентные методы 77
Блок 4 78
4.1. Методы штрафных и барьерных функций 78
4.2. Динамическое программирование. Основные понятия. Сущность методов решения 79
4.3. Стохастическое программирование. Основные понятия 81
4.4. Матричные игры с нулевой суммой 83
4.5. Чистые и смешанные стратегии и их свойства 85
4.6. Свойства чистых и смешанных стратегий 88
4.7. Приведение матричной игры к ЗЛП 92
4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания 94
4.9. Потоки событий 96
4.10. Схема гибели и размножения 97
4.11. Формула Литтла 99
4.12. Простейшие системы массового обслуживания 101
|
|
|
Список рекомендуемой литературы 106
Вопросы к блокам по курсу «Исследование операций»
Блок 1
1. Предмет и задачи исследования операций.
2. Основные понятия и принципы исследования операций.
3. Математические модели операций.
4. Понятие линейного программирования.
5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов.
6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий.
7. Примеры экономических задач линейного программирования. Задача о смесях.
8. Примеры экономических задач линейного программирования. Транспортная задача.
9. Основные виды записи задач линейного программирования.
10. Способы преобразования.
11. Переход к канонической форме.
12. Переход к симметричной форме записи.
Блок 2
1. Геометрическая интерпретация задачи линейного программирования.
2. Решение задач линейного программирования графическим методом.
3. Свойства решений задачи линейного программирования.
4. Общая идея симплексного метода.
5. Построение начального опорного плана при решении задач линейного программирования симплексным методом.
6. Признак оптимальности опорного плана. Симплексные таблицы.
7. Переход к нехудшему опорному плану.
8. Симплексные преобразования.
9. Альтернативный оптимум (признак бесконечности множества опорных планов).
10. Признак неограниченности целевой функции.
11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание.
12. Понятие двойственности для симметричных задач линейного программирования.
Блок 3
1. Несимметричные двойственные задачи.
2. Открытая и закрытая модели транспортной задачи.
3. Построение начального опорного плана. Правило "Северо-западного угла".
4. Построение начального опорного плана. Правило минимального элемент.
5. Построение начального опорного плана. Метод Фогеля.
6. Метод потенциалов.
7. Решение транспортных задач с ограничениями по пропускной способности.
8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении.
9. Сущность методов дискретной оптимизации.
10. Задача выпуклого программирования.
|
|
|
11. Метод множителей Лагранжа.
12. Градиентные методы.
Блок 4
1. Метод штрафных и барьерных функций.
2. Динамическое программирование. Основные понятия. Сущность методов решения.
3. Стохастическое программирование. Основные понятия.
4. Матричные игры с нулевой суммой.
5. Чистые и смешанные стратегии.
6. Свойства чистых и смешанных стратегий.
7. Приведение матричной игры к ЗЛП
8. Задачи теории массового обслуживания. Классификация систем массового обслуживания.
9. Потоки событий.
10. Схема гибели и размножения.
11. Формула Литтла.
12. Простейшие системы массового обслуживания.
Блок 1.
Предмет и задачи исследования операций
Современное состояние науки и техники, в частности, развитие компьютерных средств расчета и математического обоснования теорий позволило значительно упростить решение многих проблем, поставленных перед различными отраслями науки. Многие из проблем сводятся к решению вопроса об оптимизации производства, оптимальному управлению процессами.
Потребности практики вызвали к жизни специальные научные методы, которые удобно объединять под названием «исследование операций».
Определение: Под исследованием операций будем понимать применение математических, количественных методов для обоснование решений во всех областях целенаправленной человеческой деятельности.
Пусть предпринимается какое-то мероприятие, направленное к достижению определенной цели. У лица (или группы лиц), организующего мероприятие, всегда имеется какая-то свобода выбора: оно может быть организовано тем или иным способом. Решение и есть какой-то выбор из ряда возможностей, имеющихся у организатора.
Необходимость принятия решений и проверки выдвинутой гипотезы решения математически подтверждают следующие примеры:
Задача 1. О наилучшем использовании ресурсов.
На предприятии выпускается несколько видов продукции. Для их изготовления используются некоторые ресурсы (в том числе человеческие, энергетические и т.д.). Необходимо рассчитать, каким образом спланировать работу предприятия, чтобы затраты ресурсов были минимальны, а прибыль – максимальной.
|
|
|
Задача 2. О смесях.
Необходимо подготовить смесь, обладающую определенными свойствами. Для этого можно использовать некоторые "продукты" (для расчета диет – продукты питания, для кормовых смесей – продукты питания для животных, для технических смесей – сплавы, жидкости технического назначения). задача заключается в выборе оптимального количества продуктов (по цене) для получения оптимального количества смеси.
Задача 3. Транспортная задача.
Существует сеть предприятий, выпускающих однотипную продукцию одного качества и сеть потребителей этой продукции. Потребители и поставщики связаны путями сообщений (автодороги, железнодорожные линии, авиационные линии). Определены тарифы перевозок. Необходимо рассчитать оптимальный план перевозок продукции, чтобы затраты при перевозке были минимальны, запросы всех потребителей удовлетворены, а у поставщиков весь товар вывезен.
В каждом из приведенных примеров речь идет о каком-то мероприятии, преследующем определенную цель. Заданы некоторые условия, характеризующие обстановку (в частности, средства, которыми можно распоряжаться). В рамках этих условий требуется принять такое решение, чтобы задуманное мероприятие было в некотором смысле более выгодным.
В соответствии с этими общими чертами вырабатываются и общие приемы решения подобных задач, в совокупности составляющие методологическую схему и аппарат исследования операций.
В настоящее время большое распространение принимают автоматизированные системы управления (АСУ), основанные на использовании компьютерной техники. Создание АСУ невозможно без предварительного обследования управляемого процесса методами математического моделирования. С ростом масштабов и сложности мероприятий математические методы обоснования решений приобретают все большую роль.
Основные понятия и принципы исследования операций
Определение: Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.
Операция есть всегда управляемое мероприятие, т.е. от расчетов зависит, каким способом выбрать параметры, характеризующие ее организацию. «Организация» здесь понимается в широком смысле слова, включая набор технических средств, применяемых в операции.
Определение: Всякий определенный выбор зависящий от решающих параметров называется решением.
Определение: Оптимальными называются решения, по тем или иным причинам предпочтительные перед другими.
|
|
|
Цель исследования операций – предварительное количественное обоснование оптимальных решений.
Иногда в результате исследования удается указать одно-единственное строго определенное решение, гораздо чаще – выделить область практически равноценных оптимальных решений, в пределах которой может быть сделан конечный выбор.
Само принятие решений выходит за рамки исследования операций и относится к компетенции ответственного лица, чаще – группы лиц, которым представляется право окончательного выбора и на которых возложена ответственность за этот выбор.
Определение: Параметры, совокупность которых образует решение, называются элементами решения.
В качестве элементов решения могут фигурировать различные числа, векторы, функции, физические признаки и т.д. Для упрощения всю совокупность элементов решения будем обозначать х.
Кроме элементов решения в любой задачи исследования операций имеются еще и заданные условия, которые фиксированы в условии задачи и нарушены быть не могут. В частности, к таким условиям относятся средства (материальные, технические, людские), которыми можно распоряжаться, и иные ограничения, налагаемые на решение. В своей совокупности они образуют так называемое «множество возможных решений». Обозначим это множество Х, а тот факт, что решение х принадлежит этому множеству, будем записывать: хÎХ.
Чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности (целевая функция). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. Лучшим будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели. Чтобы выбрать показатель эффективности Z, нужно прежде всего определить, к чему должно привести решение задачи. Выбирая решение, предпочтение отдается такому, которое обращает показатель эффективности Z в максимум или в минимум. Например, доход от операции хотелось бы обратить в максимум; если же показателем эффективности являются затраты, их желательно обратить в минимум.
Очень часто выполнение операции сопровождается действием случайных факторов: «капризов» природы, колебания спроса и предложения, отказы технических устройств и т.д. В таких случаях обычно в качестве показателя эффективности берется не сама величина, которую хотелось бы максимизировать (минимизировать), а среднее значение (математическое ожидание).
Задача выбора показателя эффективности решается для каждой проблемы индивидуально.
Задача 1. О наилучшем использовании ресурсов.
Задача операции – произвести максимальное количество товаров. Показатель эффективности Z – прибыль от продажи товаров при минимальных затратах на ресурсы (max Z).
Задача 2. О смесях.
Естественный показатель эффективности, подсказанный формулировкой задачи, - это цена необходимых для смеси продуктов при условии необходимости сохранения заданных свойств смеси(min Z).
Задача 3. Транспортная задача.
Задача операции – обеспечить снабжение товарами потребителей при минимальных расходах на перевозки. Показатель эффективности Z – суммарные расходы на перевозки товаров за единицу времени (min Z).
|
|
|
B. Статистические и экспериментальные исследования
E) тело, размерами которого можно пренебречь в условиях данной задачи
I ЭТАП. Постановка задачи
I. МЕТОДЫ ИССЛЕДОВАНИЯ МЕТАЛЛОВ
I. ПРЕДМЕТ И ЦЕЛИ ДОГОВОРА.
I. ПРЕДМЕТ, МЕТА І ЗАВДАННЯ ДИСЦИПЛІНИ
I. Цели и задачи учебной дисциплины
I. Цель задачи дисциплины «История государства и права зарубежных стран»
I. Энергетическое право - комплексная отрасль российского права, его предмет и методы.
II. Взаимодействие с предметом труда (с книгами)
