1. Подготовка задачи к решению в MS Excel Подключение надстройки «Поиск решения» в электронной таблице Excel (версии 5-10) осуществляется через меню «Сервис/Надстройки». В выпадающем списке необходимо отметить соответствующий пункт. Если в списке надстроек пункт «Поиск решения» отсутствует, то нужно переустановить пакет Microsoft Office, отметив надстройку «Поиск решения» в разделе «Дополнительные средства Office». Прежде чем запускать надстройку следует подготовить задачу к решению. Для этого необходимо проделать следующие шаги.Составить на бумаге математическую модель задачи, определив переменные, записав целевую функцию и ограничения (см. введение).Создать табличную (электронную) модель задачи, для чего надо:ввести исходные данные в ячейки таблицы;задать диапазоны ячеек, в которых будут находиться переменные (искомые параметры) задачи. В дальнейшем эти ячейки будем называть изменяемыми ячейками;ввести формулы для вычисления левых частей ограничений и целевой функции задачи ЛП через исходные данные и адреса изменяемых ячеек. Ячейку, содержащую формулу для подсчета целевой функции, будем называть целевой ячейкой. Только после этого можно решать задачу оптимизации с помощью надстройки «Поиск решения». Заметим, что для решения задач линейного программирования надстройка использует хорошо известный студентам второго курса симплекс-метод, причем в итоге решения выводятся не только оптимальные значения переменных и целевой функции, но и результаты постоптимального анализа. Рассмотрим подробнее процедуру решения задачи линейного программирования в Excel на конкретном примере.^ 2. Построение математической модели Производственная задача. Фирма специализируется на производстве компьютерных столов трех видов А, В, С, что требует различных затрат труда на каждой стадии производства: Производственный участок Затраты труда (чел.-час.) на стол А В С Лесопилка 1 2 4 Сборочный цех 2 4 2 Отделочный цех 1 1 2 В течение недели можно планировать работу на лесопилке на 360 чел.-час., в сборочном цехе – на 520 чел.-час. и в отделочном цехе – на 220 чел.-час. Цены реализации одного стола типа А, В, С составляют 9, 11, 15 долларов соответственно. Сколько столов каждой модели надо производить в неделю, чтобы максимизировать суммарный недельный доход? Требуется также провести постоптимальный анализ полученного решения. Составим математическую модель задачи, выбрав в качестве переменных – количество компьютерных столов каждого из трех видов A, B, C, планируемых к выпуску. Тогда ожидаемый суммарный доход может быть подсчитан по формуле (1) Переменные задачи удовлетворяют ограничениям (2) в левых частях которых вычислены затраты трудовых ресурсов на лесопилке, в сборочном и отделочном цехах, а в правых частях записаны максимально возможные запасы этих ресурсов. Учитывая, что переменные задачи по своему экономическому смыслу не могут принимать отрицательные значения, получаем математическую модель задачи оптимального распределения трудовых ресурсов с целью получения максимального дохода от реализации изготовленных компьютерных столов..Очевидно, что построенная модель имеет линейную структуру и, следовательно, является задачей линейного программирования.^ 3. Создание электронной модели Чтобы привлечь компьютер к решению этой задачи необходимо ввести исходные данные на лист Excel. Это можно сделать, например, так, как изображено на рис.1. Сначала заносим в таблицу неизменяемые данные: цены продукции, удельные расходы труда на выпуск каждого вида столов и их наличные запасы в каждом цехе.Рис. 1. Затем заполняем изменяемые ячейки B3:D3, в которых расположены компоненты плана . На этапе ввода исходных данных сюда заносятся любые числа, например, единицы. После решения в этих ячейках будут находиться оптимальные значения переменных. Целевая функция (суммарный доход) и левые части ограничений (затраты труда в каждом цехе) подсчитываются в соответствие с составленной моделью по формуле (1) и левым частям (2). Содержимое соответствующих ячеек приведено ниже = СУММПРОИЗВ(B4:D4;B$3:D$3) – вычисление суммарного дохода. = СУММПРОИЗВ(B8:D8;B$3:D$3), = СУММПРОИЗВ(B9:D9;B$3:D$3), = СУММПРОИЗВ(B10:D10;B$3:D$3) – вычисление затрат труда в каждом цехе на выпуск всей продукции. Функция СУММПРОИЗВ(массив1, массив2) относится к разряду математических функций. Она вычисляет произведения соответствующих элементов массивов, после чего суммирует полученные произведения. Вставку функции можно осуществить через одноименный пункт меню Вставка, или с помощью кнопки . Если ссылку на диапазон изменяемых ячеек B3:D3 в формуле для сделать абсолютной B$3:D$3, для чего можно воспользоваться клавишей F4, то ячейки E8:E10 легко заполнить с помощью операции копирования ячейки E4. Ячейка Е4, содержащая формулу для вычисления целевой функции является целевой ячейкой.^ 4. Использование надстройки «Поиск решения» После активации строки Поиск решения в меню Cервис, мы увидим следующее окно:Рис. 2. В поле Установить целевую ячейку надо ввести адрес (или имя) ячейки, в которой находится формула для вычисления целевой функции, в нашей задаче это адрес E4. Если перед вызовом надстройки целевую ячейку сделать активной, щелкнув по ней мышкой, то требуемый адрес появится автоматически. Имеется возможность максимизировать, минимизировать значение целевой ячейки, или установить значение в целевой ячейке равным некоторому числу путем установки переключателя в соответствующее положение. В поле Изменяя ячейки вводятся имена или адреса изменяемых ячеек. Их можно вводить либо единым массивом, либо разделенные запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Их значения изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку. Допускается установка до 200 изменяемых ячеек. Кнопка Предположить должна помочь автоматически найти все ячейки, влияющие на формулу модели, однако результат часто бывает неточным, поэтому внесем адреса изменяемых ячеек, выделив их на листе мышкой. В поле Ограничения необходимо указать условия, накладываемые на переменные (изменяемые ячейки). Для ввода ограничений используются кнопки Добавить и Изменить, которые вызывают окно Добавление ограничения (рис.3), служащее для установки между ячейками соотношений типа , или , а также наложения ограничений на целочисленность и бинарность (возможность для переменных принимать только два значения 0 или 1) .Рис. 3. Поле Ссылка на ячейку служит для указания ячейки или диапазона, на значения которых необходимо наложить ограничение. Внесем туда диапазон ячеек E8:E10, содержащий левые части ограничений, выделив их в листе мышкой. Поле Ограничение служит для задания условия, которое накладывается на значения ячейки или диапазона, указанного в поле Ссылка на ячейку. Выбор необходимого условного оператора ( , , , цел или двоич ) производится из выпадающего списка в центре окна. В правое поле окна вводится ограничение - число, формула, ссылка на ячейку или диапазон. В нашем примере укажем диапазон F8:F10, содержащий правые части ограничений (2) – наличные запасы трудоресурсов. Кнопка Добавить используется для ввода новых ограничений без возврата в окно ^ Поиск решения. Нам эта кнопка не понадобится, так как все ограничения мы ввели с помощью одного диапазона. В принципе, в этом же окне можно ввести условия неотрицательности переменных, однако для этой цели в программе предусмотрена специальная возможность, которой мы воспользуемся позже. Завершается ввод ограничений нажатием кнопки OK и возвратом в главное окно Поиск решения. В этом окне также присутствуют кнопки Выполнить и Параметры. Первая служит для запуска алгоритма поиска оптимального решения. Вторая – предлагает настроить поиск более конкретно. Можно изменять условия и варианты поиска решения для линейных и нелинейных задач, а также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач. Нажатие кнопки Параметры выводит на экран одноименное окно:Рис. 4. Опишем элементы окна параметров поиска решения:Максимальное время Служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.Итерации Служит для управления временем решения задачи, путем ограничения числа промежуточных вычислений. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.Точность Служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 (нуля) до 1. Низкая точность соответствует введенному числу, содержащему меньшее количество десятичных знаков, чем число, используемое по умолчанию – например, 0,0001. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.Допустимое отклонение Служит для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел. При указании большего допуска поиск решения заканчивается быстрее.Сходимость Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует близость значения к нулю. Лучшая сходимость требует больше времени на поиск оптимального решения.Линейная модель Служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи. Инициализация этой опции определяет использование в алгоритме поиска симплекс-метода.Показывать результаты итераций Служит для приостановки поиска решения для просмотра результатов отдельных итераций. Позволяет отслеживать процесс поиска.Автоматическое масштабирование Служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине – например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.Значения не отрицательны Позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение.Оценка Служит для указания метода экстраполяции – линейная или квадратичная – используемого для получения исходных оценок значений переменных в каждом одномерном поиске. Линейная служит для использования линейной экстраполяции вдоль касательного вектора. Квадратичная служит для использования квадратичной экстраполяции, которая дает лучшие результаты при решении нелинейных задач.Производные Служит для указания метода численного дифференцирования – прямые или центральные производные – который используется для вычисления частных производных целевых и ограничивающих функций. Прямые используются для гладких непрерывных функций. Центральные используются для функций, имеющих разрывную производную. Не смотря на то, что данный способ требует больше вычислений, он может помочь, если выводится итоговое сообщение о том, что процедура поиска решения не может улучшить текущий набор влияющих ячеек.Метод Служит для выбора алгоритма оптимизации – метод Ньютона или сопряженных градиентов – для указания направление поиска. Метод Ньютона служит для реализации квазиньютоновского метода, в котором запрашивается больше памяти, но выполняется меньше итераций, чем в методе сопряженных градиентов. Метод Сопряженных градиентов служит для реализации метода сопряженных градиентов, в котором запрашивается меньше памяти, но выполняется больше итераций, чем в методе Ньютона. Данный метод следует использовать, если задача достаточно велика и необходимо экономить память, а также если итерации дают слишком малое отличие в последовательных приближениях.Сохранить модель Служит для отображения на экране диалогового окна ^ Сохранить модель, в котором можно задать ссылку на область ячеек, предназначенную для хранения модели оптимизации. Данный вариант предусмотрен для хранения на листе более одной модели оптимизации – первая модель сохраняется автоматически.Загрузить модель Служит для отображения на экране диалогового окна Загрузить модель, в котором можно задать ссылку на область ячеек, содержащих загружаемую модель. Для решения нашей задачи мы должны отметить в окне ^ Параметры решения пункты Линейная модель и Неотрицательные значения, задавая тем самым в качестве метода решения симплекс-метод. Можно также отметить пункт Показывать результаты итераций, что позволит наблюдать за процессом решения. Нажатие кнопки OK вернет нас в исходное окно надстройки Поиск решения, которое после ввода всей информации о задаче будет иметь вид.Рис. 5. Нажав кнопку Выполнить, запускаем задачу на решение.^ 5. Анализ результатов решения Если все условия задачи и параметры решения указаны верно, то после нажатия кнопки Выполнить главное окно надстройки Поиск решения закрывается и появляется окно Результаты поиска решения (рис. 6) с текстом «Решение найдено. Все ограничения и условия оптимальности выполнены». Однако возможны и другие сообщения, свидетельствующие об отсутствии решения задачи. Текст «значения целевой ячейки не сходятся» говорит о неограниченности целевой функции на допустимом множестве, а сообщение «Поиск не может найти подходящего решения» означает, что ограничения задачи не совместны (Множество допустимых планов пусто). Такие ситуации могут быть следствием неверно построенной математической модели, либо результатом ошибок при заполнении полей диалоговых окон надстройки.Рис. 6. Опишем остальные элементы окна:Сохранить найденное решение Служит для сохранения найденного решения в изменяемых ячейках табличной модели на листе Excel (В нашем примере эти ячейки выделены серым цветом).Восстановить исходные значения Служит для восстановления исходных значений изменяемых ячеек табличной модели. Отчеты Служит для указания типа отчета, размещаемого на отдельном листе книги. Для вывода нужных отчетов надо щелкнуть мышью их названия.Результаты. Используется для создания отчета, состоящего из целевой ячейки и списка изменяемых ячеек модели (переменных задачи), их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.Устойчивость. Используется для создания отчета, содержащего сведения о чувствительности решения к малым изменениям в формуле целевой функции (поле Установить целевую ячейку, диалоговое окно Поиск решения) или в формулах ограничений. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. В случае нелинейных моделей отчет содержит данные для градиентов и множителей Лагранжа. Пределы. Используется для создания отчета, состоящего из целевой ячейки и списка изменяемых ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. Нижним пределом является наименьшее значение, которое может содержать изменяемая ячейка, в то время как значения остальных изменяемых ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно, верхним пределом называется наибольшее значение.Сохранить сценарий Служит для отображения диалогового окна Сохранение сценария, в котором можно сохранить сценарий решения задачи, чтобы использовать его в дальнейшем с помощью диспетчера сценариев Microsoft Excel. Вернемся к задаче о производстве компьютерных столов. Если в диалоговом окне ^ Результаты поиска решения (рис. 6) был отмечен первый пункт Сохранить найденное решение, то исходная таблица с электронной моделью задачи примет видРис. 7. Изменившиеся ячейки выделены серым фоном. Перед листом с электронной моделью появятся листы с выбранными отчетами. Содержимое отчетов можно редактировать также как любые данные электронной таблицы – изменять формат ячеек, размер шрифта, корректировать имена ячеек. Рассмотрим все отчеты подробнее.^ 5.1. Отчет по результатам Отчет состоит из трех таблиц, расположенных на одном листе книги Excel (рис. 8). Рис. 8. В первой таблице выводятся сведения о целевой функции. В столбце ^ Исходное значение приведено значение целевой функции до начала вычислений, в столбце Результат – после оптимизации. Следующая таблица содержит значения искомых переменных (изменяемых ячеек) до и после решения задачи. Последняя таблица показывает значения левых частей ограничений на оптимальном решении задачи. В столбце ^ Формула приведены зависимости, которые были введены в диалоговом окне Поиск решения, в столбце Разница показано количество неиспользованного ресурса. Если ресурс дефицитен, т.е. используется полностью, то в столбце Статус указывается связанное (соответствующее ограничение активно); при неполном использовании ресурса в этом столбце указывается не связанное (ограничение не активно). Из отчета по результатам применительно к нашей задаче видим, что оптимальный план производства состоит в еженедельном выпуске 180 столов типа А и 40 столов типа В, а столы вида С выпускать не выгодно. Таким образом , и максимальный суммарный доход долл. При этом трудовые ресурсы в сборочном и отделочном цехах используются полностью, т.е. являются дефицитными, а на лесопилке наблюдается избыток трудоресурсов в объеме 100 чел.-час. в неделю.^ 5.2. Отчет по устойчивости Отчет по устойчивости содержит информацию, позволяющую провести постоптимальный анализ решения задачи. Цель анализа заключается в определении таких границ изменения исходных данных задачи (коэффициентов целевой функции и правых частей ограничений), при которых ранее найденный оптимальный план сохраняет свою оптимальность и в изменившихся условиях. Отчет состоит из двух таблиц, изображенных на рисунке 9. Рис. 9. В первой таблице (Изменяемые ячейки) приводится следующая информация о переменных:результирующее значение – оптимальные значения переменных;нормированная стоимость – ее величина равна значению соответствующей симплексной оценки с противоположным знаком. Для невыпускаемой продукции нормированная стоимость показывает, на сколько изменится целевая функция при принудительном включении единицы этой продукции в оптимальное решение; коэффициенты целевой функции;предельные значения приращения коэффициентов целевой функции, которые показывают на сколько можно увеличить и уменьшить каждый целевой коэффициент в отдельности, сохраняя при этом оптимальные значения переменных. Во второй таблице (ограничения) приводятся аналогичные значения для ограничений задачи:величины использованных ресурсов (левые части ограничений) при оптимальном плане выпуска продукции;теневые цены, т.е. оптимальные значения двойственных переменных, которые показывают, как изменится целевая функция при изменении соответствующего запаса ресурса на единицу;исходные запасы ресурсов (правые части ограничений);предельные значения приращений ресурсов (их допустимое увеличение и уменьшение), при которых сохраняется оптимальный план двойственной задачи и базисный набор переменных, входящих в оптимальное решение исходной задачи (ассортимент выпускаемой продукции). Используем результаты отчета по устойчивости для проведения постоптимального анализа в нашей задаче:. Исследуем сначала влияние на оптимальный план изменений коэффициентов целевой функции – цен реализации продукции. Из первой таблицы следует, что оптимальный план производства компьютерных столов не изменится, если первоначальная цена долл. стола типа А возрастет на 2 доллара или уменьшится на 0,333 доллара. Другими словами, условие сохранения оптимального плана при изменении цены стола А имеет вид: , т.е. . Аналогично, условие сохранения оптимального плана при изменении цены стола В имеет вид: или . Наконец, при изменении цены стола типа С ранее найденный план останется оптимальным, если исходная цена возрастет не более чем на 1 доллар. В то же время любое уменьшение цены не влияет на оптимальный план , так как число равно , т.е. практически является бесконечно большим числом. Таким образом, условие сохранения оптимальности плана при изменении цены примет вид . Это означает, что столы вида С не выгодно выпускать (), если цена на них будет не выше 16 долларов. Если же цена превысит 16 долларов за стол, то план перестанет быть оптимальным, и в новом оптимальном решении будет положительным т.е. производство столов типа С станет выгодным. Оценим теперь влияние на оптимальный план изменений правых частей ограничений – запасов трудовых ресурсов на разных производственных участках. Интерпретация данных второй таблицы отчета зависит от того, является ли исследуемое ограничение связанным (активным), или не связанным. Если ограничение не связанное, то соответствующий ему ресурс недефицитен и уменьшение его запаса на величину, не превышающую избытка, не влияет на план выпуска . Тем более не изменяет оптимальный план увеличение запаса недефицитного ресурса, приводя только к возрастанию неизрасходованного остатка. Если же ограничение - связанное, т.е. соответствующий ресурс дефицитен и расходуется полностью, то любое изменение его запаса изменяет объем выпускаемой продукции. Единственное, что можно определить в данном случае, это диапазон изменения запаса ресурса, гарантирующий сохранение прежнего ассортимента выпускаемой продукции. О дефицитности ресурса можно судить либо по статусу ограничения в третьей таблице отчета о результатах, либо по значению теневой цены из второй таблицы отчета по устойчивости – дефицитный ресурс имеет положительную теневую цену, а недефицитный – нулевую. Из первой строки второй таблицы видим, что на лесопилке трудоресурсы избыточны, так как их теневая цена . Следовательно, оптимальный план выпуска продукции не изменится, если запас трудовых ресурсов уменьшится на величину избытка в 100 чел.-час., или увеличится на любое сколь угодно большое число. Таким образом, условие сохранения оптимального плана при изменении объема трудоресурсов на лесопилке имеет вид: . Во второй и третьей строках таблицы теневые цены положительны, значит трудоресурсы в сборочном и отделочном цехах дефицитны – при оптимальных объемах производства используются полностью. Следовательно, любое изменение их количества приведет к изменению оптимального плана . В этом случае числа из столбцов ^ Допустимое увеличение и Допустимое уменьшение дают границы изменения запасов ресурса, обеспечивающие сохранение прежнего состава базисных (положительных) переменных оптимального плана – ассортимента выпуска продукции. Итак, при изменении объемов ресурсов в сборочном цехе в пределах , т.е. при ассортимент выпуска не изменится. Аналогично, если объем трудоресурсов в отделочном цехе будет находится в пределах , т.е. при , то ассортимент выпуска не изменится. На экономическом языке это означает, что если запасы ресурсов изменяются в указанных пределах, то по оптимальному плану по-прежнему надо выпускать только столы типа А и В, но уже в новых объемах. Напомним, что теневая цена ресурса численно равна изменению оптимального значения целевой функции при увеличении (уменьшении) запаса данного ресурса на единицу. Как видно из таблицы, теневая цена трудоресурса в сборочном цехе , а в отделочном цехе . Условие сохранения теневых цен (оптимальных значений двойственных переменных ) совпадает с условиями сохранения базиса оптимального плана. Следовательно, привлечение одной дополнительной единицы ресурса в сборочный цех приведет к увеличению суммарного дохода на 1 доллар, а одна дополнительная единица ресурса в отделочном цехе увеличит суммарный доход на 7 долларов. Отсюда ясно, что если появится возможность вовлечь в производство дополнительные ресурсы в количестве, например, 30 человеко-часов, то направить их надо в отделочный цех, так как это увеличит прибыль на долларов. Заметим, что при этом оптимальный план производства компьютерных столов изменится, но сохранится его структура – ассортимент выпускаемой продукции.^ 5.3. Отчет по пределам Третий отчет для нашей задачи, называемый отчетом по пределам, состоит из двух таблиц (рис.10). Первая таблица в комментариях не нуждается. Рис.10. Во второй таблице показано, в каких пределах может изменяться выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального плана выпуска:приводятся значения в оптимальном решении;приводятся нижние и верхние пределы изменения значений и значения целевой функции при выпуске данного типа продукции на нижнем и верхнем пределах. Так например, если из оптимального плана исключить выпуск столов типа А, положив и сохранить оптимальные значения остальных переменных, то доход от реализации продукции будет равен Значения целевой функции – дохода от реализации продукции, вошедшей в оптимальное решение на верхних пределах везде равно максимальной величине 2060 долларов.