Книги по разным темам Pages:     | 1 | 2 | 3 | 4 | 5 | 4. РЕШЕНИЕ СТРУКТУРИРУЕМЫХ ЗАДАЧ РАЗРАБОТКИ УПРАВЛЕНЧЕСКОГО РЕШЕНИЯ 4.1. Решение задач поиска экстремума средствами пакета Excel С развитием средств вычислительной техники большинство разработанных методов решения задач поиска экстремума было алгоритмизировано, переведено на машинный язык и включено в состав специализированного или универсального программного обеспечения [30]. К их числу относится, например, задача математического программирования, которая может быть сформулирована выражениями (2.3), (2.4). В каждом конкретном случае в строке системы ограничений сохраняется только один из знаков (либо, либо =, либо ), причем разные ограничения могут иметь разные знаки. Величины m и n удовлетворяют условиям n 1 и m0, причем значения m и n никак не связаны между собой за исключением случая, когда все m ограничений являются строгими равенствами (тогда должно обеспечиваться 0 m n).

Методы решения задач математического программирования существенно зависят от вида функций E и gi. На практике наиболее разработаны методы решения задач линейного программирования, базирующиеся, в частности, на работах Л.В. Канторовича. В этих задачах функции E и gi представляются линейными полиномами (3.1), (3.2). Наиболее удобным методом решения задачи линейного программирования является так называемый симплекс-метод, предусматривающий последовательное преобразование переменных задачи по определенным правилам вплоть до отыскания оптимального решения.

Кроме этого, на ЭВМ реализованы чисто алгоритмические методы поиска экстремумов, основанные на определении изменения значения функции E при изменении значения аргументов. Манипулируя по разным правилам аргументами и многократно рассчитывая значение функции E (что реализуемо на ЭВМ и невозможно вручную), добиваются уменьшения относительного приращения экстремума на неком k-м шаге за какое-то фиксированное число шагов ниже некоторого наперед заданного числа (Сходимость):

Ek+1 - Ek.

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

Дискретные методы вычисления приводят к отказу от общепринятого понятия производной и замене его на так называемую конечную разность. Существует два определения конечной разности[22] - односторонняя, которая определяется разностью значений функции в точках k и k+1 и центральная, определяемая значением в середине интервала между значениями функции Ek = 1 = Ek+1 - Ek, ( ) k Ek+0,5 = 1 +0,5 = Ek+1 - Ek.

( ) k Конечные разности первого порядка совпадают между собой. Отличие начинается при определении конечных разностей второго порядка и выше 2 = 1 - 1 = Fk+2 - 2Fk+1 + Fk, k k+1 k 2 = 1 - 1 = Fk+1 - 2Fk + Fk-1.

k k+0,5 k-0,Центральные разности дают несмещенную оценку по отношению к текущему положению аргумента, однако их использование требует большего числа вычислений в алгоритме поиска экстремума, чем при использовании односторонних разностей.

Электронные таблицы Excel фирмы Microsoft имеют встроенные средства решения задач поиска экстремума, оформленные в виде так называемой надстройки. Перед началом работы надо убедиться, что в составе сгенерированного на вашей ЭВМ пакета Excel требуемая надстройка установлена. Для этого выберите режим Сервис главного меню и убедитесь, что в открывшемся ниспадающем меню есть пункт Поиск решения (рис. 4.1). Если режим Поиск решения отсутствует, то выберите пункт меню Сервис/Надстройки и в открывшемся окне включите режим Поиск решения (рис. 4.2). Если в этом окне пункт Поиск решения отсутствует, произведите переустановку пакета Excel.

Рис.4.1. Пункт меню Поиск решения Рис. 4.2. Включение надстройки Поиск решения Режим Поиск решения (рис. 4.3) позволяет, задавая некоторую ячейку в виде целевой при условии обеспечения зависимости результата вычислений в ней от значений некоторых изменяемых ячеек, с учетом заданных ограничений получить или максимальное, или минимальное, или заданное значение целевой ячейки. В качестве параметров режима (рис. 4.4) задаются ограничение по времени поиска решения в секундах (Максимальное время) (максимально 32767), количеству итераций (Предельное число итераций), точности соответствия результата заданному значению (Относительная погрешность), допустимого отклонения экстремума от оптимального значения при использовании режима целочисленной математики (Допустимое отклонение), а также условие прекращения поиска экстремума (Сходимость), задающее величину относительного приращения экстремума за последние пять итераций.

Рис. 4.3. Режим Поиск решения Кроме этого, в виде флажков могут задаваться отдельные режимы работы, например Линейная модель, определяющая класс методов решения задачи. При установке параметра Линейная модель Excel ищет экстремум симплекс-методом. Если флажок Линейная модель выключен, решение задачи ведется методом Ньютона или градиентным с использованием прямых или центральных конечных разностей на основе линейной или квадратичной оценки уменьшения приращения экстремума в зависимости от установленных флажков.

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

Флажок Значения не отрицательны позволяет задать диапазон значения аргумента. Его установка эквивалентна введению ограничения xi 0. Режим Автоматическое масштабирование позволяет перейти к отображению данных в относительных единицах, а при установке флажка Показывать результаты итераций включается пошаговый режим.

Вариант настройки параметров может быть сохранен.

В математической постановке задача линейного программирования записывается в виде линейной целевой функции и линейных ограничений. Напомним, что задаче линейного программирования (3.1, 3.2) соответствует двойственная задача (3.4, 3.5).

Решение задачи линейного программирования средствами табличного процессора Excel осуществляется в режиме Сервис/Поиск решения. Для работы в этом режиме требуется предварительно разместить в рабочем листе коэффициенты cj целевой функции (коэффициенты значимости), матрицу коэффициентов aij, ограничения в виде количества имеющихся ресурсов bi и выделить ячейки для расчета значения целевой функции E и значений вектора управления X = (x1, x2,Е, x ). Решениn ем задачи является рассчитываемый надстройкой Поиск решения набор переменных X = (x1, x2,..., xn ), обеспечивающий максимальное (минимальное, заданное) значение целевой функции E(x1, x2,..., xn).

На рис. 4.5 изображен рабочий лист Excel и набор числовых данных, сгенерированных с помощью датчика случайных чисел. Дополнительно для всех числовых ячеек листа cj, aij, bi, УЦелевая функция EФ, УX = (x1, x2,Е, x )Ф, УРасход ресурсаФ, УИтого расход ресурсаФ задан n числовой формат с двумя знаками после запятой режимом Формат/ ЯчейкиЕ/Число. Отметим, что непосредственно на решение задачи оказывают влияние только числовые данные, а показанные текстовые сообщения и формулы используются только в качестве комментария и могут быть опущены.

Следующим этапом при подготовке задачи к решению является программирование математических выражений, связывающих между собой исходные числовые данные и вычисляемые выражения. Напомним, что целевая функция нашей задачи определяется выражением (3.1). Электронные таблицы Excel позволяют записывать в выбранную ячейку не только числа, но и математические выражения, составленные по общим правилам языков программирования с использованием символа присваивания =, знаков операций (+,Ц,*,/) и встроенных функций. В качестве операндов в таких выражениях могут использоваться константы или имена ячеек Excel. В рассматриваемом примере ячейки для хранения cj имеют имена B5, C5, D5 и E5, а для хранения вектора управления используются ячейки B3, C3, D3 и E3. Результат вычислений критериальной функции E должен храниться в ячейке F5. Для программирования выражения в этой ячейке ее необходимо сделать активной, щелкнув по ней мышью.

После этого в строке формул листа Excel надо нажать кнопку = и начать набор математического выражения. Применительно к рассматриваемому примеру это удобнее делать не непосредственно с использованием операций * и +, а воспользовавшись встроенной математической функцией Excel СУММПРОИЗВ(). Для вызова мастера построения этой функции надо нажать кнопку fx стандартной панели инструментов Excel (предварительно нажимать кнопку = в этом случае не надо) и отыскать ее в категории Математические. ЗапуРис.4.5. Исходные данные контрольной задачи стившись, мастер построения функции предложит указать первый массив (в нашем случае ячейки B5, C5, D5 и E5) и второй (в нашем случае ячейки B3, C3, D3 и E3). Программирование завершается нажатием кнопки OK мастера функций. Если программирование ячейки было успешным, то в самой ячейки появится результат вычислений, а в строке формул - запрограммированное в выбранной ячейке выражение.

Аналогично предыдущему осуществляется программирование формулы для левой части первого неравенства из (3.2) в ячейке F8.

Как и в предыдущем случае оказывается удобным воспользоваться функцией СУММПРОИЗВ(). Очевидно, что первый массив аргументов функции в этом случае представляет набор значений первой строки матрицы ограничений (в нашем случае ячейки B8, C8, D8 и E8), а второй сохраняется (ячейки B3, C3, D3 и E3). Для программирования левой части второго и последующих неравенств в ячейках F9, F10 и т.д. можно повторить ранее приведенные действия по вызову функции СУММПРОИЗВ(), вводя в первый массив соответственно группы ячеек B9:E9, B10:E10 и т.д. При большом числе неравенств (в нашем случае их девять), удобно воспользоваться имеющейся в Excel возможностью копирования формул за счет протаскивания мышкой ячейки F8 вниз. Особенностью программируемых формул является участие в них набора ячеек соответствующей строки матрицы aij и одних и тех же ячеек B3, C3, D3 и E3, хранящих вектор управления. Поэтому при программировании выражения для ячейки F8 целесообразно при задании второго массива указать его элементы с абсолютной адресацией, что достигается с помощью клавиши F4. Напомним, что символом абсолютной адресации является знак $, а положение ячейки $B$4 при протаскивании формулы не изменится. Наконец, дополнительно в ячейке F17 запрограммирована формула для вычисления общей суммы израсходованных ресурсов, результаты расчетов по которой могут быть использованы в приложениях. Отметим, что эта формула имеет смысл только в том случае, когда значения величин представлены в одинаковых единицах измерения.

Выполнение перечисленных выше операций (заполнение таблиц данными и программирование формул) позволяет полностью подготовиться собственно к решению задачи оптимизации. Теперь нам необходимо щелкнуть мышкой по целевой ячейке F5 и вызвать режим Сервис/Поиск решения. В открывшейся таблице Поиск решения должен быть указан адрес нашей целевой ячейки F5. Проверьте задание типа экстремума (Установить целевую ячейку равной максимальному значению). Откройте окно Изменяя ячейки и задайте в нем адреса ячеек вектора управления X = (x1,x2,Е,x ) ( в наn шем случае B3:F3). Нажмите кнопку Добавить и в открывшейся таблице на рис. 4.6. Добавление ограничения в поле Ссылка на ячейку введите адреса левых частей неравенств (3.2) (в нашем случае F8:F16).

Установите требуемые знаки неравенств (в нашем случае ). Войдите в окно Ограничение и задайте адреса ячеек, содержащих значения bi (в нашем случае G8:G16) и нажмите кнопку OK. Наконец нажмите кнопку Параметры и в открывшейся таблице на рис.4.4 задайте режим Линейная модель и Неотрицательные значения. Нажмите кнопку OK.

Результат этих действий отображен на рис. 4.7.

Рис.4.6. Добавление ограничений Нажмите кнопку Выполнить и получите решение задачи, показанное на рис. 4.8. В результате выполнения команды Поиск решения в таблице Результаты поиска решения могут быть выданы следующие диагностические сообщения:

Решение найдено. Все ограничения и условия оптимальности выполнены (имеет место в рассматриваемом случае);

Поиск не может найти подходящего решения;

Значения целевой ячейки не сходятся.

В первом случае на рабочем листе Excel в ячейках вектора управления находятся конкретные значения переменных xi, обеспечивающие значение целевой функции, величина которого находится в соответствующей ячейке. По результатам решения в случае установки режима Линейная модель могут быть представлены три типа отчетов: по результатам, по устойчивости и по пределам. Отчет по результатам (рис. 4.9) Рис. 4.7. Подготовленная к решению контрольная задача Рис. 4.8. Результат решения контрольной задачи содержит начальные (Исходно) и конечные (Результат) значения целевой функции и изменяемых ячеек, а также сводку результатов использования ресурсов. В этой сводке в столбце Cостояние символами связанное или несвязанное обозначаются соответственно полное или неполное использование соответствующего ресурса. В рассматриваемом примере полностью израсходованы Ресурс 3 и Ресурс 4.

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

Кроме этого, в отчете содержатся величины использованных ресурсов, их теневые цены (множители Лагранжа), показывающие насколько изменится целевая функция при увеличении соответствующего ресурса на единицу.

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

Если в результате решения задачи оптимизации выдается сообщение Поиск не может найти подходящего решения, то это означает, что условия задачи несовместны, т. е. не существует такого значения вектора управления X = (x1,x2,Е,x ), которое удовлетворяло бы имеюn щимся ограничениям. В результате решения такой задачи могут быть определены величины необходимых ресурсов, обеспечивающих возможность нахождения X в области допустимых значений. Введем m дополнительных переменных ti, имеющих смысл величины недостающего ресурса (m - количество ограничений).

Pages:     | 1 | 2 | 3 | 4 | 5 |    Книги по разным темам