Из математической модели задачи видно, что целевая функция имеет линейную зависимость от переменных, значит решаемая задача является задачей линейного программирования.
На рабочем листе книги MS Excel создадим экранную форму для ввода условий задачи, рис.1.1
Рис. 1.1. Экранная форма задачи 1
В экранной форме на рис. 1.1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи линейного программирования. Переменным задачи соответствуют ячейки ВЗ:D3, коэффициентам целевой функции (ЦФ) соответствуют ячейки В6:D6, правым частям ограничений соответствуют ячейки G10:G12.
В ячейку Е6, в которой будет отображаться значение ЦФ, необходимо ввести формулу, по которой это значение будет рассчитано. В экранной форме значение целевой функции можно вычислить по формуле:
Формулы для расчета левых частей системы ограничений (1.2) разместим в ячейках Е10:Е12. Для экранной формы, представленной на рис.1.1, они могут быть рассчитаны по следующим формулам
Е11 =СУММПРОИЗВ(B3:D3;B11:D11) Е12 =СУММПРОИЗВ(B3:D3;B12:D12)
Экранная форма готова для решения задачи линейного программирования.
В качестве начального приближения значений искомых переменных примем нулевые значения, для чего введем в ячейки В3:D3 нули.
Для решения задачи линейного программирования средствами MS Excel в меню СЕРВИС нужно выбрать команду ПОИСК РЕШЕНИЯ.
Примечание. При первоначальном обращении к инструменту поиска решения в главном меню СЕРВИС можно не обнаружить операции ПОИСК РЕШЕНИЯ. Это означает, что компонент поиска решения в программе MS Excel не установлен. Для установки компонента необходимо выбрать в меню СЕРВИС команду НАДСТРОЙКИ и в открывшемся диалоговом окне установить галочку в строке ПОИСК РЕШЕНИЯ, рис.1.2.
Рис.1.2. Диалоговое окно установки дополнительных компонент MS Excel
При установке дополнительных компонент программы MS Excel может потребоваться установочный диск пакета MS Office.
Параметры решения задачи устанавливаются в диалоговом окне «Поиск решения», представленном на рис. 1..3
Рис.1.3. Диалоговое окно «Поиск решения» задачи 1
В открывшемся диалоговом окне необходимо выбрать целевую ячейку (в нашей задаче Е6), установить переключатель характера решаемой задачи в требуемое положение (в нашем случае «максимальное значение»), в поле «Изменяя ячейки» указать ячейки, которые должны изменяться в процессе поиска решения задачи (в нашей задаче В3:D3). После этого в поле «Ограничения» нужно ввести ограничения и граничные условия решаемой задачи оптимизации.
Для того, чтобы добавить ограничение, нужно нажать кнопку ДОБАВИТЬ, и в отрывшемся диалоговом окне «Добавление ограничения» установить ссылку на требуемую ячейку, вид и значение ограничения (рис.1.4).
Рис.1.4. Диалоговое окно «Добавление ограничения»
В соответствиями с заданными условиями и экранной формой решаемой нами задачи в нашем случае требуется ввести 4 ограничения:
· значения ячеек Е10:Е12 должны быть меньше или равны значениям ячеек G10:G12 соответственно (система ограничений 1.2 );
· значения ячеек В3:D3 должны быть больше или равны нулю (граничные условия 1.3).
Для решения задач оптимизации определенного класса необходима установка конкретных параметров поиска решения. Для этого нужно нажать кнопку ПАРАМЕТРЫ и заполнить некоторые поля окна «Параметры поиска решения» (рис. 1.5).
Рис.1.5. Диалоговое окно «Параметры поиска решения»
Параметр «Максимальное время» служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).
Параметр «Предельное число итераций» служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767.
Параметр «Относительная погрешность» служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.
Параметр «Допустимое отклонение» служит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большего допуска поиск решения заканчивается быстрее.
Параметр «Сходимость» применяется только при решении нелинейных задач.
Установка флажка «Линейная модель» обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.
Установленные по умолчанию значения параметров подходят для большинства решаемых задач. Оставим их без изменения, отметив галочкой «Линейная модель», так как наша задача линейная.
Подтвердим установленные параметры нажатием кнопки ОК.
Запуск задачи на решение производится из окна «Поиск решения» путем нажатия кнопки ВЫПОЛНИТЬ.
На экране появляется окно «Результаты поиска решения», представленное на рис.1.6.
Рис.1.6. Диалоговое окно «Результаты поиска решения»
Примечание. Иногда при решении оптимизационных задач характер выводимых в диалоговом окне «Результаты поиска решения» сообщений может быть другим: «Поиск не может найти подходящего решения» или «Значения целевой ячейки не сходятся». Вывод таких сообщений не всегда свидетельствуют о характере оптимального решения задачи, а чаще о том, что при вводе условий задачи в Excel были допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует.
Если решение оптимизационной задачи найдено, мы можем сохранить его в ячейках экранной формы и просмотреть три типа отчетов «Результаты», «Устойчивость», «Пределы», которые предлагает Excel для анализа полученного решения. Нажмем в диалоговом окне «Результаты поиска решения» кнопку ОК и сохраним результаты решения в экранной форме.
Экранная форма с результатами решения задачи представлена на рис.1.7.
Рис. 1.7. Экранная форма задачи 1 с результатом решения
Из результатов решения задачи, представленных на рис.1.7, следует, что для получения максимальной прибыли в планируемом производственном периоде а размере 2050 у.е. мы должны произвести 25 стульев и 2,5 стола. При этом запасы всех наших ресурсов (ткани, досок и фурнитуры) будут израсходованы полностью без остатка.
С практической точки зрения полученное решение не имеет смысла, так как производство 0,5 стола если теоретически и возможно, то получение прибыли от его реализации крайне затруднительно.
С математической точки зрения при решении задачи мы допустили ошибку, выполнив решение без учета того, что наша задача относится к классу задач целочисленного программирования – переменные: табуретки, столы и стулья могут быть только целыми числами. Для исправления ошибки выберем в меню СЕРВИС команду ПОИСК РЕШЕНИЯ и в поле «Ограничения» добавим еще одно ограничение – ячейки В3:D3 должны быть целыми числами (рис.1.8).
Рис.1.8. Диалоговое окно «Поиск решения» целочисленной задачи 1
Экранная форма с результатами решения задачи линейного целочисленного программирования представлена на рис.1.9.
Рис. 1.9. Экранная форма задачи 1 с результатом решения
Выберем в диалоговом окне «Результаты поиска решения» (рис.1.6) тип отчета «Результаты» и нажмем кнопку ОК.
Система ограничений
Е10 =СУММПРОИЗВ(B3:D3;B10:D10)