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

Стр 1 из 3Следующая ⇒

Кафедра информатики

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

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

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

Коломна 2014

Содержание

Содержание. 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 Формирование собственного варианта транспортной задачи. 25

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задания к ЛАБОРАТОРНЫМ работАМ

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

А, вот оно и задание. Очень простое, хотя «с непривычки» может показаться и сложным. Но трудности ограничиваются только освоением инструмента Excel, называемого поиском решения.

Решить три задачи оптимизации по следующим темам.

1 Планирование производства

2 Транспортная задача

3 Планирование персонала

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

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

О таком можно только мечтать: сами себе выбираем: что будем делать. Как в супермаркете: хотим берём, не хотим не берём.

Собственный вариант задачи «Планирование производства» создаётся на основе варианта образца путём следующих возможных изменений:

1) изменения значений констант;

2) изменения состава комплектующих деталей и производимых изделий;

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

Количество изменений выбирается самостоятельно. Степень отличия от образца будет влиять на выставляемую оценку.

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

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

Собственный вариант «Транспортной задачи» создаётся из варианта образца путём следующих возможных изменений:

1) изменения значений констант;

2) изменения состава заводов-производителей;

3) изменения состава складов-получателей.

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

Эта задача очень проста. Для неё трудно придумать возможные направления «удаления» от образца. Изменение целевой функции кажется сложным, но требует только знания стандартной функции МАКС().

Собственный вариант задачи «Планирование персонала» создаётся из варианта образца путём следующих возможных изменений:

1) изменения значений констант;

2) изменение целевой функции – вместо «Общая недельная зарплата» использовать «Максимальное количество лишних работников».

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

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

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

Служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу.

Равно

Служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить число, введите его в поле.

Изменяя ячейки

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

Предположить

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

Ограничения

Служит для отображения списка граничных условий поставленной задачи.

Добавить

Служит для отображения диалогового окна «Добавить ограничение».

Изменить

Служит для отображения диалоговое окна Изменить ограничение.

Удалить

Служит для снятия указанного ограничения.

Выполнить

Служит для запуска поиска решения поставленной задачи.

Закрыть

Служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки сделанные в окнах диалога, появлявшихся после нажатий на кнопки «Параметры», «Добавить», «Изменить» или «Удалить».

Параметры

Служит для отображения диалогового окна «Параметры поиска решения», в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.

Восстановить

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

Настройка надстройки

Если вы не можете найти в системе меню Excel пункт «Поиск решения», то не расстраивайтесь. Если вы используете Microsoft Office Excel 2003, то вам повезло: идите в пункт меню «Сервис», и далее выбирайте пункт «Надстройки …» (этот-то пункт уж точно будет присутствовать). После этого появится диалоговое окно «Надстройки». В нём-то и поставьте галочку рядом со строкой «Поиск решения». После это давите не кнопку OK, и желаемый пункт «Поиск решения» появится в пункте меню «Сервис».

Если вы используете Microsoft Office Excel 2007 и выше, то вам повезло ещё больше: вы получаете шанс получше освоить современный (видимо, для оригиналов придуманный) интерфейс от Microsoft. А чтобы не лишать вас возможности получить удовольствие в полном объёме, я не буду описывать правило подключения надстройки «Поиск решения» по шагам, а только скажу, как это можно сделать: наберите в строке подсказки «Надстройки Поиск решения», и далее следуйте полученным инструкциям.

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

Суть задачи

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

Искомыми переменными в задаче планирования производства являются объёмы каждого вида продукции, подлежащие выпуску в течение планового промежутка времени; можно считать, что искомые переменные организованы в вектор , где – количество видов выпускаемой продукции.

Целевой функцией является ожидаемый доход – суммарная цена всех видов продукции, выпущенной в течение планового промежутка времени:
, где – доход от продукции -го вида, т. е. цена всего объёма выпущенной продукции -го вида, вычисляемая по формуле , , где – цена единицы продукции -го вида.

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

Целью планирования является максимизация целевой функции.

Константами задачи являются:

1) запасы каждого вида деталей на складе; предполагается, что в планируемом промежутке времени количество запасов не изменяется; математически совокупность запасов представляет собой вектор , где – количество видов комплектующих деталей, используемых в производстве, в Excel предстá вим столбцом данных;

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

3) цены на единицу каждого вида продукции; математически цены представляют собой вектор .

Вспомогательные функции задачи в текущем рассмотрении следующие:

1) количества использованных в процессе производства комплектующих деталей, вычисляемые по формуле: , , входящие в ограничения задачи; можно считать, что вычисляемые значения указанных функций организованы в вектор .

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

Ограничения в рассматриваемом варианте задачи планирования имеют следующую семантику:

· количества деталей , использованных в процессе производства, не должны превышать запасы этих деталей на складе предприятия: , ;

· производимые объёмы продукции, конечно же, должны иметь положительные значения: , ( ).

Суть задачи

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

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

Скорее всего, решение задачи составления плана не единственно, и возможно создание нескольких таких планов. Отличаться они будут не только конкретикой объёмов перевозок от конкретного производителя к конкретному потребителю, но и суммарными затратами на перевозки. Естественно, очень желательно найти такой план, чтобы суммарные затраты на перевозки были бы минимально возможными.

Искомыми переменными в задаче планирования перевозок являются объёмы каждого вида продукции, подлежащие перевозу в течение планового промежутка времени от каждого производителя к каждому потребителю; можно считать, что искомые переменные организованы в матрицу , где – объём (точнее масса, измеряемая килограммами или тоннами) продукции, перевозимой от –го производителя –му потребителю; – количество заводов – производителей продукции; – количество складов потребителей.

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

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

Константами задачи являются:

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

2) производственные возможности заводов – объёмы продукции, которые могут произвести заводы в планируемом промежутке времени; объёмы производимой продукции представляют собой вектор , где – количество заводов; в Excel этот вектор предстá вим столбцом данных;

3) цены на перевозку единицы объёма продукции от производителей к потребителям; математически цены на перевозку продукции представляют собой матрицу , где – стоимость доставки единицы объёма (массы) продукции от –го производителя –му потребителю; в Excel матрицу предстá вим блоком (прямоугольником) данных.

Вспомогательные функции задачи в текущем рассмотрении следующие:

1) вывезенные с заводов объёмы продукции, вычисляемые по формуле: , ; осознаем, что это сумма поставок от -го производителя всем потребителям; можно считать, что вычисляемые значения указанных функций организованы в вектор ; в Excel этот вектор предстá вим столбцом данных;

2) количества доставленных объёмов продукции потребителям, вычисляемые по формуле: , ; осознаем, что это сумма поставок -му потребителю от всех производителей; можно считать, что вычисляемые значения указанных функций организованы в вектор ; в Excel этот вектор предстá вим строкой данных;

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

Ограничения в рассматриваемом варианте транспортной задачи имеют следующую семантику:

· вывезенные с заводов объёмы продукции не должны превышать производственные возможности этих заводов : , ;

· количества фактически доставленных объёмов продукции потребителям должны обеспечивать потребности потребителей : , ;

· все перевозимые объёмы продукции, конечно же, должны иметь положительные значения: , ( ; ).

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

Суть задачи

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

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

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

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

Формат отчёта

Оформлять отчёт можно по той же форме, что и отчёт по Информатике.

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

Содержание отчета может быть следующим.

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

Приводится текст:

«Решить три задачи оптимизации по следующим темам.

1 Планирование производства

2 Транспортная задача

3 Планирование персонала

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

Кавычки в текст не включайте.

2. Задача планирования производства

2.1 Формулировка задачи оптимального планирования производства

Формулируем задачу, как сможем

2.2 Образец решения задачи планирования производства

Приводятся картинка (screenshot) рабочего листа Excel с образцом задачи, и рассказывается всё про все элементы таблицы.

Рассказывается о том, как запускается процедура поиска решения.

Затем приводятся результаты решения задачи-образца в виде screenshot рабочего листа.

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

Излагаете изменения, вносимые вами в задачу-образец. Приводите screenshots с исходными данными, ограничениями и результатами решения. Комментируете полученные результаты.

Далее по аналогии излагаются ещё две задачи

Транспортная задача

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

Если вы не успеваете выполнить задание полностью, не переживайте! Сделайте и изложите то, что сможете. Главное – не отнеситесь равнодушно, хотя и это прощено будет.

Кафедра информатики

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

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

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

Коломна 2014

Содержание

Содержание. 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 Формирование собственного варианта транспортной задачи. 25

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

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

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

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

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

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

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

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

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

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

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

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

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

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

12 3 Следующая ⇒