Примеры решения оптимизационных задач средствами Excel

Лабораторная работа и контрольные задания ОКТ

1. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ EXCEL

1. 1. Ввод условий задачи

1. 2. Работа в диалоговом окне "Поиск решения"

2. ПРИМЕРЫ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ EXCEL

2. 1. Получение требуемого сплава

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

2. 3. Рациональное использование имеющихся площадей

2. 4. Рациональное использование технологических участков

2. 5. Закрепление самолетов за воздушными линиями

2. 6. Задача о ранце

2. 7. Назначение механизмов на работы

2. 8. Задача коммивояжера

2. 9. Задача о доставке

3. ВАРИАНТЫ ЗАДАНИЙ

Вариант контрольной работы выбирается по последней цифре № зачетной книжки.

Вариант										10(0)
Номера заданий

Решение задач линейного программирования с помощью Excel

Ввод условий задачи

Ввод условий задачи состоит из следующих основных шагов:

1). Создание формы для ввода условий задачи.

2). Ввод исходных данных (коэффициентов математической модели).

3). Ввод целевой функции, ограничений и граничных условий.

Последовательность работ рассмотрим на примере задачи распределения ресурсов.

Фирма выпускает продукцию четырех типов Продукт1, Продукт2, Продукт3, Продукт4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье, финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Норма расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в табл., там же приведено наличие располагаемого ресурса. Требуется определить, в каком количестве надо выпускать продукцию каждого типа, чтобы суммарная прибыль была максимальной.

Ресурс	Продукт1	Продукт2	Продукт3	Продукт4	Наличие
Трудовые
Сырье
Финансы
Прибыль

Составим математическую модель, для чего введем следующие обозначения:

x_j- количество выпускаемой продукции j-го типа j=1,2,3,4;

b_i- количество располагаемого ресурса i-го вида i=1,2,3;

a_ij- норма расхода i-го ресурса для выпуска единицы продукции j-го типа;

c_j- прибыль, получаемая от реализации единицы продукции j-го типа.

Из табл. видно, что для выпуска единицы Продукта1 требуется 6 единиц сырья, значит, для выпуска всей продукции первого типа требуется 6x₁ единиц сырья, где x₁- количество выпускаемой продукции Продукт1. С учетом того, что для других видов продукции зависимости будут аналогичны, ограничение по сырью будет иметь вид:

6× x₁+5× x₂+4× x₃+3× x₄ £ 110.

В этом ограничении левая часть равна величине требуемого ресурса, а правая показывает количество имеющегося ресурса.

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

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

60× x₁+70× x₂+120× x₃+130× x_4® max

Ограничения имеют вид:

x₁+x₂+x₃+x_4£ 16

6× x₁+5× x₂+4× x₃+3× x_4£ 110

4× x₁+6× x₂+10× x₃+13× x_4£ 100

x_j³ 0; j= .

Рис. 6

1). Форма ввода условий задачи представлена на рис. 6. Весь текст на рисунке (и в дальнейшем) является комментарием и на решение задачи не влияет.

2). Необходимые исходные данные приведены на рис. 7.

Рис. 7

3). Рассмотрим алгоритмы ввода уравнений целевой функции и ограничений:

• Установить курсор в ячейку, содержащую целевую функцию (F6).
• Щелкнуть мышью по кнопке -Мастер функций (на панели инструментов). На экране: диалоговое окно "Мастер функций шаг 1 из 2" (рис. 8).
• Выбрать категорию Мат. и тригонометрия
• Выбрать функцию СУММПРОИЗВ
• Щелкнуть по кнопке Шаг >. На экране: диалоговое окно "Мастер функций шаг 2 из 2" (рис. 9).
• В массив 1 ввести $B$3:$E$3.

Рис. 8

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

• В массив 2 ввести B6:E6.
• Щелкнуть по кнопке Закончить.

Рис. 9

В ячейке F6 отображается значение целевой функции, оно равно 0.

Ввод ограничений (в ячейки F9, F10, F11) осуществляется аналогичным образом, с заданием соответствующих адресов. Однако значительно проще можно выполнить данную процедуру используя мышь. Для этого подведите курсор мыши к ячейке с целевой функцией (F6), нажмите клавишу <Ctrl> (при этом рядом с изображением курсора мыши должен появиться знак "+"). Удерживая <Ctrl> перетащите содержимое ячейки F6 в ячейку F9. Содержимое F6 скопировано в F9. Ячейка F9 стала активной, об этом свидетельствует черная рамка вокруг нее, также называемая курсором. В правом нижнем углу курсора-рамки имеется маленький квадрат. Подведите курсор мыши к нему (курсор мыши превратится в черный крестик), "ухватите" мышью квадрат и тяните вниз до ячейки F11 включительно. Таким образом вы скопируете формулу из F9 в ячейки F10 и F11.

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

Рис. 10

Рис. 11

Все необходимые условия внесены в таблицу в виде формул. Следующим этапом будет поиск решения задачи средствами Excel.

1. 2. Работа в диалоговом окне "Поиск решения"

1). Выберите последовательно опции меню Сервис, Поиск решения. На экране появится соответствующее окно (рис. 12).

Рис. 12

Поясним смысл элементов окна.

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

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

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

Ограничения- перечисляет текущие ограничения в данной проблеме.

Добавить- выводит окно диалога “Добавить ограничение”, в котором можно добавить ограничения к текущей проблеме.

Изменить- выводит окно диалога “Изменить ограничение”, в котором можно модифицировать имеющиеся ограничения.

Удалить- удалить выделенное ограничение.

Выполнить- запускает процесс решения определенной проблемы.

Закрыть- закрывает окно диалога, не решая проблемы. Сохраняются лишь изменения, сделанные при помощи кнопок Параметры, Добавить, Изменить и Удалить. Не сохраняются изменения, произведенные после использования данных кнопок.

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

Восстановить- очищает все текущие установки проблемы и возвращает все параметры к их значениям по умолчанию.

Курсор ввода с клавиатуры установлен в поле Установить целевую ячейку. Сюда необходимо внести адрес ячейки, содержащей целевую функцию. Для того чтобы сделать это щелкните мышью на той ячейке рабочего листа, где содержится ЦФ (F6). Вокруг F6 появился движущийся пунктирный контур, а в поле окна- соответствующий адрес. Следует отметить, что подобным способом можно вносить все остальные необходимые данные, это удобнее, чем вводить их с клавиатуры.

2). В поле Равной выберите флажок Максимальному значению.

3). Введите адреса искомых переменных, для этого выделите мышью область таблицы B3:E3.

4). Ввод ограничений задачи. Щелкните на кнопке Добавить. На экране появилось окно "Добавление ограничения" (рис. 13). Excel воспринимает ограничения в виде ссылок на ячейки в которых содержатся соответствующие формулы, при этом левая часть ограничения представляет собой, как правило, ссылку на формулу, а правая- значение: число или ссылку на ячейку, содержащую значение. Адреса ячеек должны содержать символ $. Если определяется интервал ячеек, то он должен быть той же формы и тех же размеров, что и интервал в окне Ссылка на ячейку. Некоторые из ограничений примера представлены на рис. 12.

Рис. 13

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

Ограничение- определяет условие, налагаемое на содержимое окна Ссылка на ячейку. Выберите из списка отношение, которое нужно установить между ячейкой или интервалом и ограничением, которое нужно ввести в окне справа от списка. Можно выбрать <=, =, >=, или "цел". Если Вы выбрали "цел" для указания на то. что переменная должна быть целочисленной, то слово "Целое" появляется в окне справа от списка.

Добавить- в окне диалога “Добавить ограничение” можно добавить новое ограничение без возврата в диалог “Параметры поиска решений”.

Если при вводе задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делается с помощью кнопок Изменить, Удалить (рис. 12). На этом ввод условий задачи закончен.

5). Установка параметров решения. Щелкните мышью по кнопке Параметры. На экране появится окно "Параметры поиска решения" (рис. 14).

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

Рис. 14

Поясним элементы окна.

Максимальное время- ограничивает время, требующееся для процесса отыскания решения. Это значение должно быть положительным целым числом. Значение по умолчанию равно 100 (секунд), что вполне годится для большинства малых задач, хотя Вы можете ввести любое значение до 32767.

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

Точность- контролирует точность ответов, получаемых при поиске решений. Число, вводимое в поле Точность:

• используется при определении того, удовлетворяет ли значение ячейки ограничения нужному равенству или находится ли оно в указанных границах.
• должно быть дробным числом от 0 до 1 (не включая концы).
• имеет значение по умолчанию равно 0,000001.

указывает на меньшую точность, если число введено с меньшим количеством десятичных знаков; например, 0,0001.

Вообще говоря, чем большая точность определяется (чем меньше число), тем больше времени понадобится для поиска решения. Методы, используемые Поиском Решения, позволяют существенно ускорить поиск, если установить исходное значение, достаточно близкое к искомому решению.

Допустимое отклонение- проблемы, связанные с изменяемыми ячейками, которые должны содержать целые значения, могут требовать большого количества времени, так как при этом необходимо решать несколько подпроблем, каждая из которых есть задача для Поиска Решений с целочисленными ограничениями. Можно подобрать величину отклонения, которая представляет процент допустимого отклонения от оптимального решения при целочисленных ограничениях для всех элементов задачи. Чем выше отклонение (допустимое отклонение в процентах), тем быстрее процесс решения. Установка отклонения не играет роли, если не введены целочисленные ограничения.

Линейная модель- ускоряет процесс отыскания решения. Команда может быть использована только, если все связи в модели линейны.

Показать результаты итераций- прерывает Поиск Решения и показывает результаты после каждой итерации.

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

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

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

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

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

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

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

Загрузить модель- выводит окно диалога "Загрузить Модель", в котором можно указать, какую именно модель нужно загрузить.

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

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

6). Нажмите OK, затем кнопку Выполнить в окне "Поиск решения". Через некоторое время на экране появится окно "Результаты поиска решения" (рис. 15).

Рис. 15

Окно диалога "Результаты поиска решения" выводит результаты последнего вычисления, используя значения ячеек, наиболее близкие к нужному решению.

Когда Поиск Решения завершает попытки отыскания решения, то на экран в верху окна диалога "Результаты поиска решений" выводится сообщение о завершении.

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

Восстановить исходные значения- восстанавливает исходные значения в изменяемых ячейках.

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

Отчеты- создает указанный тип отчета. Каждый отчет появляется на отдельном листе рабочей книги.

• Результаты- перечисляет изменяемые ячейки и ячейку в окне Установить целевую ячейку вместе с исходным и конечным значением. Также показывает ограничения и информацию о них.
• Устойчивость- предоставляет информацию о том, насколько чувствительно решение к малым изменениям в формуле окна Установить целевую ячейку или ограничениях. Для нелинейных моделей, отчет предоставляет двойственные значения (нормированные градиенты и множители Лагранжа). Для линейных моделей отчет включает редуцированную стоимость, теневые цены, objective coefficient (с допустимыми отклонениями в обе стороны), и ограничения на изменение правой стороны равенства.
• Пределы- перечисляет изменяемые ячейки вместе с соответствующими значениями, ячейку в окне Установить целевую ячейку, верхние и нижние пределы и целевые значения. Нижний предел есть наименьшее значение, которое может находиться в изменяемой ячейке, если фиксировать остальные ячейки и удовлетворить все ограничения. Верхний предел есть наибольшее значение. Целевое значение есть значение ячейки в окне Установить целевую ячейку, когда значение изменяемой ячейки достигает наименьшего или наибольшего предела.

Результаты поиска появятся в таблице (рис. 16).

Рис. 16

На рис. 16 видно, что в оптимальном решении Продукт1=B3=10; Продукт2=C3=0; Продукт3=D3=6; Продукт4=E3=0. При этом максимальная прибыль будет составлять F6=1320, а количество использованных ресурсов равно: трудовых=F9=16, сырья=F10=84, финансов=F11=100.

Таково оптимальное решение рассматриваемой задачи распределения ресурсов. Однако решение задачи находится не всегда. Если условия задачи несовместны, на экране появится диалоговое окно (рис. 17):

Рис. 17

Если целевая функция неограничена, то на экране появится диалоговое окно (рис. 18):

Рис. 18

Примеры решения оптимизационных задач средствами Excel