Коломна 2013

Кафедра автоматизации производства и информационных технологий

Задачи оптимизации

Методические указания к контрольной работе
по дисциплине «Информационные технологии»

Составили: д-р техн. наук, профессор
Белов В.В.
канд. техн. наук, доцент
Чистякова В.И.

Коломна 2013

Содержание

Содержание. 2

1 Задачи оптимизации: начальные понятия. 4

1.1 Семантика термина «оптимальный». Критерий оптимальности. 4

1.2 Задача оптимизации: суть задачи и её элементы.. 4

1.3 Формальная постановка задачи оптимизации. 6

2 Задания к контрольной работе. 8

2.1 Формулировка задания. 8

2.2 Собственный вариант задачи «Планирование производства». 8

2.3 Собственный вариант «Транспортной задачи». 8

2.4 Собственный вариант задачи «Планирование персонала». 8

3 Использование надстройки «Поиск решения» Excel для решения задач оптимизации 9

3.1 Функциональность надстройки «Поиск решения». 9

3.2 Начальные значения искомых переменных – специфика процедуры поиска решения. 9

3.3 Способ использования файла Smpls.xls с образцами решения задач. 10

3.4 Элементы окна «Поиск решения». 10

3.4.1 Установить целевую ячейку. 10

3.4.2 Равно. 10

3.4.3 Изменяя ячейки. 10

3.4.4 Предположить. 11

3.4.5 Ограничения. 11

3.4.6 Добавить. 11

3.4.7 Изменить. 11

3.4.8 Удалить. 11

3.4.9 Выполнить. 11

3.4.10 Закрыть. 11

3.4.11 Параметры.. 11

3.4.12 Восстановить. 11

3.5 Авторы надстройки «Поиск решения». 11

4 Пояснения к решаемым задачам. 12

4.1 Настройка надстройки. 12

4.2 Задача «Планирование производства». 12

4.2.1 Суть задачи. 12

4.2.2 Ознакомление с образцом решения задачи. 13

4.2.3 Формирование собственного варианта задачи планирования производства 16

4.3 Транспортная задача, или задача планирования перевозок. 19

4.3.1 Суть задачи. 19

4.3.2 Ознакомление с образцом решения задачи. 21

4.3.3 Формирование собственного варианта транспортной задачи. 24

4.4 Задача «Планирование персонала». 24

4.4.1 Суть задачи. 24

4.4.1.1. Предметная область. 24

4.4.1.2. Предварительные соображения о методике решения. 25

4.4.1.3. Элементы задачи планирования работников. 26

4.4.2 Ознакомление с образцом решения задачи. 27

4.4.3 Формирование собственного варианта задачи планирования персонала 30

5 Рекомендации по оформлению отчета по контрольной работе. 31

5.1 Формат отчёта. 31

5.2 Содержание отчёта. 31

5.3 Замечание заключительное. 32

1 Задачи оптимизации: начальные понятия

1.1 Семантика термина «оптимальный».
Критерий оптимальности

Узнаём научное понятие оптимальности, запоминаем понятие
критерия оптимальности.

Слово «оптимальный» в бытовом разговорном языке является синонимом терминов «наилучший», «наиболее подходящий», «наиболее качественный», «рациональный (умный)», «целесообразный» (способствующий достижению желаемой цели). Обычно слово «оптимальный» используется в сочетании с существительным, выражающим некоторый вариант – тем, что выбирается из некоторой совокупности возможностей. Например, часто ведут речь об оптимальной покупке, оптимальном вложении средств, оптимальном плане, оптимальной программе, оптимальном решении и т.п.

В научной лексике слово «оптимальный» сохраняет тот же смысл, но к нему добавляется ёще один термин: «критерий оптимальности» – это числовой показатель, выражающий степень рациональности и целесообразности варианта, т.е. показывающего насколько лучшим, подходящим, качественным является вариант. Поэтому термин «оптимальный вариант» считается неполным, условным. Правильно говорить так: «оптимальный по такому-то критерию вариант». Например: оптимальная по соотношению цена/качество покупка, оптимальный по максимуму прибыли производственный план, оптимальный по суммарным затратам план перевозок.

Сам смысл понятия критерия оптимальности как показателя качественности варианта указывает на то, что он представляет собой величину, значение которой желательно либо максимизировать, либо минимизировать. Действительно, если критерием оптимальности является величина суммарных затрат, тот этот критерий желательно минимизировать. Если же критерием является ожидаемая прибыль, то его следует максимизировать. Гораздо реже, но всё же имеет место и такая ситуация, когда желательным является достижение конкретного (желаемого) значения критерия. Например, при выборе оптимального по критерию калорийности состава блюд для питания здорового человека желательно обеспечить некоторую конкретную калорийность, а не максимизировать или минимизировать её.

1.2 Задача оптимизации: суть задачи и её элементы

Запоминаем основные элементы задачи оптимизации: «искомые переменные», «целевая функция», «ограничения», «константы задачи».

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

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

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

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

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

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

Итак, запоминаем основные элементы задачи оптимизации:

1) искомые переменные – это переменные, значения которых отыскиваются в процессе решения задачи оптимизации; эти переменные обычно организуются в вектор или матрицу;

2) целевая функция – это функция, зависящая от искомых переменных, представляющая собой критерий качества решения задачи оптимизации; как математический объект целевая функция является функционалом; в процессе решения задачи оптимизации отыскивается такой набор значений искомых переменных, при котором целевая функция имеет экстремальное (максимальное или минимальное) значение либо равна заданному (желательному) значению;

3) цель решения задачи оптимизации – нахождение значений искомых переменных, при которых целевая функция имеет максимальное либо минимальное, либо заданное значение; кратко цель формулируется так: «максимизация либо минимизация целевой функции» или «поиск экстремума целевой функции»;

4) константы задачи – это заданные значения (исходные данные), характеризующие предметную область, используемые в формулах, определяющих целевую функцию и ограничения задачи;

5) ограничения – это представляемые в виде системы отношений (неравенств и/или равенств) физические и логические особенности предметной области, в рамках которой решается задача оптимизации; по сути дела, ограничения определяют множество допустимых значений для каждой искомой переменной; в ограничениях операции отношения () соединяют некоторые выражения, в которые входят искомые переменные;

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