КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

имени А.Н.Туполева

Мурга О.К.

Методические указания

для выполнения расчетно-графической работы

по дисциплине

ЕН.Ф.01.7 «Методы оптимизации»

Казань 2009

Содержание

Введение………………………………………………………...……………..……..3

1. Содержание и порядок выполнения расчетно-графической работы………....4

2. Разбор типового задания………………………………………………………...7

3. Индивидуальные задания………………………………………………………35

Список литературы…………………..………………………………………..........50

Введение

Методические указания предназначены в помощь студентам, обучающимся по направлению "Информатика и вычислительная техника", учебные планы которых предусматривают выполнение курсового проекта по дисциплине "Методы оптимизации".

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

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

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

1. Содержание и порядок выполнения расчетно – графической работы

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

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

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

Обязательной составной частью математической модели оптимизации

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

В результате этих действий будет построена математическая модель оптимизации предложенного объекта в виде задачи линейного программирования (ЗЛП).

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

3. Построить начальный опорный план ЗЛП. Для этого сформулировать вспомогательную L-задачу, обосновав необходимость её рассмотрения. Решить L-задачу с применением первого алгоритма метода последовательного улучшения опорного плана. Получив оптимальный опорный план L-задачи сформировать начальный опорный план исходной ЗЛП.

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

5. Решить исходную ЗЛП в канонической форме с односторонними ограничениями с применением алгоритма обратной матрицы. На этом этапе предварительно свести исходную ЗЛП к расширенной, так называемой M-задаче. Располагая найденным оптимальным опорным планом, выписать решение основной исходной задачи.

6. Провести экспертную проверку полученных результатов, сравнив их с качественным описанием рассматриваемой прикладной задачи. Если при этом будет установлена адекватность решенной ЗЛП и рассмотренной прикладной задачи, то работу завершить. Иначе, по согласованию с преподавателем уточнить исходную информацию о данной прикладной задаче и в случае необходимости уточнить постановку ЗЛП и повторить вычисления.

7. Оформить пояснительную записку по расчетно-графической работе. Она должна содержать выданное студенту индивидуальное задание и подробное описание выполненных им разделов, указанных выше. Нумерация страниц отчета сквозная, первой страницей является титульный лист, второй – содержание и т.д. Разделы пояснительной записки нумеруются арабскими цифрами. Номер подраздела состоит из номера раздела и номера подраздела, разделенных точкой. Таблицы также нумеруются и снабжаются содержательными заголовками. Формулы, на которые имеются ссылки в тексте, нумеруются в пределах раздела. Номер формулы состоит из номера раздела и порядкового номера формулы, заключенных в круглые скобки.

В конце пояснительной записки приводится список использованной литературы с указанием фамилии и инициалов автора, заглавия книги, издательства и года издания.