- •Требования к отчету по курсовой работе
- •I. Задача линейного программирования (лп)
- •6. Задача налинейного программирования
- •7. Дискретные задачи математического программирования (мп)
- •Задания для выполнения курсовой работы
- •11. Задача оптимального планирования
- •12. Производство оптимального набора продуктов
- •Литература
СИСТЕМНЫЙ АНАЛИЗ И ИСЛЕДОВАНИЕ ОПЕРАЦИЙ
Методические указания к курсовой работе
Омск - 1994
Составитель Зыкина Анна Владимировна,
канд., физ.-мат. наук, доц.
Редактор Г. М. Кляут
ЛР № 020321 от 28.11.91
Подписано к печати 09.01.95. Формат 60 x 84 1/16.Бумага газетная.
Оперативный способ печати. Усл. печ. л. 1,5. Уч.-изд. л. 1,5.
Тираж 100 экз. Заказ 19
_______________________________________________________________________________
Редакционно-издательский отдел ОмГТУ. 644050, Омск, пр-т Мира, II Типография ОмГТУ
Для более эффективного использования теоретических знаний по системному анализу и исследованию операций будущими специалистами по автоматизированным системам организации и управления важно научиться методике формального описания разнообразных реальных объектов и представления их в виде структур, описываемых типичными математическими схемами.
Данные методические указания окажут помощь при выполнении курсового задания по дисциплине "Системный анализ и исследование операций", состоящего в построении математической модели конкретной практической задачи и численном решении полученной задачи по выбранному алгоритму.
Требования к отчету по курсовой работе
Отчет по курсовой работе содержит
1) введение;
2) теоретическую часть;
3) расчетную часть;
4) список литературы.
Во введении необходимо указать параметры управления, характеризующие варианты решения задачи, и обосновать выбор этих параметров. Условия моделируемой задачи необходимо разделить на условия, определяющие ограничения задачи, и на условия, задающие критерий эффективности решения задачи.
Особо следует выделить и проанализировать неопределенные факторы, чтобы в дальнейшем учесть их влияние на модель по имеющейся о них информации.
Введение завершается записью математической модели для общего случая и выделением класса задач, к которому относится данная модель.
В теоретической части необходимо прогости обзор методов решения данного класса задач. Затем необходимо выбрать подходящий для решения метод, обосновать этот выбор и привести алгоритм метода.
Расчетная часть начинается c численного решения тестового примера, подготовленного студентом. Затем по указанию руководителя курсовой работы численно решается более сложная задача (большей размерности, с учетом большего числа факторов).
Полученные результаты числовых расчетов подвергаются качественному анализу;
- раскрывается содержательный смысл найденного оптимального решения;
- проводится анализ параметров модели на чувствительность;
- выделяются факторы, ограничивающие увеличение критерия эффективности, и факторы, способствующие увеличению критерия.
НЕКОТОРЫЕ КЛАССЫ ЗАДАЧ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
И РЕКОМЕНДУЕМЫЕ МЕТОДЫ ИХ РЕШЕНИЙ.
I. Задача линейного программирования (лп)
Найти вектор минимизируюший (максимизирующий) линейную функцию:
(1)
переменные которой подчинены следующим линейным ограничениям:
(2)
Для численного решения задачи ЛП в общей виде (1)-(2) требуется предварительно привести задачу к каноническому виду (1):
минимизировать
(3)
при условиях
(4)
Для решения задачи (3)-(4) можно использовать прямой или двойственной симплекс-метод (2-8). При выполнении условия задачу (3)-(4) можно решать графически (1, 3-8).
2. Классическая транспортная задача линейного программирования
Математическая модель классической транспортной задачи ЛП имеет вид
(5)
Транспортная задача, в которой суммарные запасы и суммарные потребности совпадают, т.е. выполняется условие , называется закрытой моделью, в противном случае - открытой. Открытая модель решается приведением к закрытой модели (2-5,8). Решение закрытой модели классической транспортной задачи (5) находят по методу потенциалов (2-5,7,8).
3. Транспортная задача до критерию времени
Математическая модель транспортной задачи при минимизации максимального времени перевозки продуктов от пунктов отправления к пунктам назначения имеет вид
(6)
Решение задачи (6) можно получить по методу "запрещенных клеток"(4).
4. Задача параметрического линейного программирования
Требуется найти решение задачи
(7)
при значениях параметра t , принадлежащих заданному конечному или бесконечному интервалу. Решение задачи (7) для случаев, когда от параметра t зависит либо функция (), либо система ограничений () находят с помощью методов, основанных на применении симплекс-метода или двойственного симплекс-метода (3,7).
5. Задача квадратичного программирования
Задача квадратичного программирования состоит в минимизации квадратичной функции
(8)
при линейных ограничениях (2), где - симметричная положительно полуопределенная матрица размерностью . Симметричностъ матрицы С следует из квадратности функции (8), так как . Положительная полуопределенность матрицы С.
следует из неотрицательности главных миноров матрицы С. Линейные ограничения (2) в произвольной форме можно свести к ограничениям в канонической форме (4), но при этом увеличивается размерность задачи n, а значит, и размерность матрицы С.
Для решения задачи квадратичного программирования предлагаются два типа методов. Методы первого типа (Била, Баранкина и Дорфмана, Франка и Вульфа (3,7)) основаны на симплексных преобразованиях условий Куна-Таккера для задачи (8), (2) или для задачи (8),(4). Основная сложность использования этих методов состоит в умения правильно выписать условия Куна-Таккера.
Методы второго типа - это специальные методы. К ним можно отнести метод сопряженных градиентов (9) и метод проекции градиента Розена (10).