Вопросы к экзамену
«Методы оптимальных решений»
I. Общие вопросы исследования операций
1. Сформулируйте определения операции, решения, оптимального решения, модели операции. эффективности операции. В чем состоит основная задача исследования операций?
2. Сформулируйте задачу исследования операций в общем виде. Перечислите основные классы задач исследования операций.
3. Приведите примеры задач управления запасами, составления расписания (календарного планирования), планировки и размещения, массового обслуживания.
II. Линейное программирование
1. Сформулируйте общую задачу линейного программирования. Стандартная и каноническая формы задачи линейного программирования.
2. Допустимые и базисные решения системы т линейных уравнений с переменными. Условия существования допустимых базисных решений.
3. Правила определения первоначального допустимого базисного решения.
4. Геометрический (графический) метод решения задачи линейного программирования.
5. Алгоритм симплексного метода решения задачи линейного программирования. САМА
6. Критерий оптимальности решения при отыскании максимума линейной функции.
7. Критерий оптимальности решения при отыскании минимума линейной функции.
8. Особые случаи симплексного метода.
9. Постановка двойственной задачи линейного программирования.
10. Свойства взаимно двойственных задач линейного программирования.
11. Первая (основная) теорема двойственности и ее экономический смысл.
12. Вторая теорема двойственности. В чем состоит двойственный симплексный метод? Соответствие решений взаимно двойственных задач.
13. Экономический смысл компонент оптимального решения исходной и двойственной задач.
14. Сформулируйте задачу целочисленного программирования. В чем состоит идея методов отсечения?
15. Метод Гомори.
III. Транспортная задача
1. Общая постановка транспортной задачи.
2. Закрытая и открытая транспортные задачи. Каким образом открытая задача может быть приведена к закрытой?
3. Методы определения первоначального распределения поставок «первоначального опорного плана).
4. Метод потенциалов для решения транспортной задачи.
5. Что такое цикл пересчета?
6. Критерий оптимальности решения транспортной задачи и его соответствие критерию оптимальности решения задачи линейного программирования.
IV. Задачи динамическою программирования
1. Общая постановка задач динамического программирования.
2. Принцип оптимальности и уравнения Беллмана.
3. Постановка и решение задачи о распределении ресурсов между предприятиями.
4. Постановка и решение задачи о ремонте и замене оборудования.
5. Постановка и решение задачи о выборе оптимального маршрута.
V. Задачи Теорин игр
1. Общая постановка игровых задач.
2. Определение парной игры, множественной игры.
3. Определение игры с нулевой суммой, матричной игры, платежной матрицы.
4. Максиминные стратегии игроков.
5. Определение цены игры, седловой точки. Решение итры в чистых стратегиях.
6. Решение игры в смешанных стратегиях для платежной матрицы 2 х m, n х 2.
7. Решение игры в смешанных стратегиях сведением к задаче линейного программирования.
8. Игры с природой. Критерии Вальда. максимума. Гурвица. Сэвиджа. среднего выигрыша. Лапласа
VI. Задачи сетевого планирования и управления
1. Сетевая модель и се основные элементы.
2. Построение и упорядочение сетевого трафика.
3. Анализ сетевого графика. Построение линейной диаграммы.
4. Определение критического времени выполнения комплекса работ.
5. Определение резервов событий и работ.
6. Оптимизация сетевого графика.
I. Общие вопросы исследования операций
1. Сформулируйте определения операции, решения, оптимального решения, модели операции. эффективности операции. В чем состоит основная задача исследования операций?
Операция – это любое управляемое мероприятие, направленное на достижение цели.
Решение – всякий определенный выбор параметров.
Оптимальное решение – решение, которое по тем или иным соображениям предпочтительнее других.
Модель операции – это достаточно точное описание операции с помощью математического аппарата.
Эффективность операции – это степень ее приспособленности к выполнению задачи.
Основная задача исследования операций – предварительное количественное обоснование оптимальных решений.
Сформулируйте задачу исследования операций в общем виде. Перечислите основные классы задач исследования операций.
Все факторы, входящие в описание операции, можно разделить на две группы:
• постоянные (условия проведения операции), на которые мы влиять не можем. Обозначим их через λ1, λ2;
• зависимые (элементы решения), которые в известных пределах мы можем выбирать по своему усмотрению.
В общем случае целевая функция зависит от факторов обеих групп.
Оптимальную задачу можно сформулировать в общем виде.
Найти переменные Z = f(x1 х2,... xn), удовлетворяющие систему Yi=(x1 х2,... xn)≤bi и обращающая в max или min целевую функцию Z. Z=f(x1 х2,... xn) → max (min). Z=f(λ1 λ2 … λn x1 х2,... xn) Упорядоченная совокупность значений n-переменных представляется точкой n-мерного пространства X=(x1 х2,... xn). Оптимальное решение X*=(x1* х2*,... xn*)
Основные классы задач исследования операций (в зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых математических методов):
· задачи сетевого планирования и управления - рассматривают соотношения между моментами начала всех операций крупного комплекса работ и строками их окончания. Эти задачи состоят в нахождении минимальной продолжительности комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения;
· задачи массового обслуживания - посвящены изучению и анализу систем обслуживания, заявок и требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик. Задачи: определение оптимального числа каналов обслуживания; решение задачи на min время обслуживания;
· задачи управления запасами - состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта;
· задача распределения ресурсов - возникают при определенном наборе операций, которые необходимо выполнить при ограниченных ресурсах и требуется найти оптимальное распределение ресурсов между операциями или составом операций;
· задача ремонта и замены оборудования - актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. Задача сводится к определению оптимальных сроков, числа профилактических ремонтов, проверок, а так же моментов замены оборудования;
· задачи составления расписания (календарного планирования) - состоят в определении оптимальной очередности выполнения операций на различных видах оборудования;
· задачи планировки и размещения – состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой;
· задачи выбора маршрута (сетевые задачи) – чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов;
· модели принятия оптимальных решений в конфликтных ситуациях (теория игр) – встречаются интересы 2-х или более лиц, цели сторон могут быть разными, необходимо разработать рекомендации по разумному поведению участников конфликта, определить их оптимальные стратегии.
Приведите примеры задач управления запасами, составления расписания (календарного планирования), планировки и размещения, массового обслуживания.
1. задачи управления запасами - состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта;
2. задачи составления расписания (календарного планирования) - состоят в определении оптимальной очередности выполнения операций на различных видах оборудования;
3. задачи планировки и размещения – состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой;
4. задачи массового обслуживания - посвящены изучению и анализу систем обслуживания, заявок и требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик. Задачи: определение оптимального числа каналов обслуживания; решение задачи на min время обслуживания;
