Линейная оптимизация в Excel (стр. 2 из 2)
Рис.1.Пункт меню Поиск решения
Рис. 2. Включение надстройки Поиск решения
Режим Поиск решения (рис. 4.3) позволяет, задавая некоторую ячейку в виде целевой при условии обеспечения зависимости результата вычислений в ней от значений некоторых изменяемых ячеек, с учетом заданных ограничений получить или максимальное, или минимальное, или заданное значение целевой ячейки.
Рис. 3. Режим Поиск решения
В качестве параметров режима (рис. 4) задаются ограничение по времени поиска решения в секундах (Максимальное время) (максимально 32767), количеству итераций (Предельное число итераций), точности соответствия результата заданному значению (Относительная погрешность), допустимого отклонения экстремума от оптимального значения при использовании режима целочисленной математики (Допустимое отклонение), а также условие прекращения поиска экстремума (Сходимость), задающее величину относительного приращения экстремума за последние пять итераций.
Рис. 4. Параметры режима Поиск решения
Кроме этого, в виде флажков могут задаваться отдельные режимы работы, например Линейная модель, определяющая класс методов решения задачи. При установке параметра Линейная модель Excel ищет экстремум симплекс-методом. Если флажок Линейная модель выключен, решение задачи ведется методом Ньютона или градиентным с использованием прямых или центральных конечных разностей на основе линейной или квадратичной оценки уменьшения приращения экстремума в зависимости от установленных флажков.
Флажок Неотрицательные значения накладывает дополнительное ограничение на значения переменных задачи. Другие флажки (например, Линейная, Квадратичная) определяют способ экстраполяции данных, метод вычисления конечных разностей (Прямые, Центральные), и метод поиска экстремума (Ньютона, Сопряженных градиентов).
Флажок Значения не отрицательны позволяет задать диапазон значения аргумента. Его установка эквивалентна введению ограничения xi ≥0. Режим Автоматическое масштабирование позволяет перейти к отображению данных в относительных единицах, а при установке флажка Показывать результаты итераций включается пошаговый режим. Вариант настройки параметров может быть сохранен.
Решение задачи линейного программирования средствами табличного процессора Excel осуществляется в режиме Сервис/Поиск решения. Для работы в этом режиме требуется предварительно разместить в рабочем листе коэффициенты cj целевой функции (коэффициенты значимости), матрицу коэффициентов aij, ограничения в виде количества имеющихся ресурсов bi и выделить ячейки для расчета значения целевой функции E и значений вектора управления X = (x1, x2,…, xn). Решением задачи является рассчитываемый надстройкой Поиск решения набор переменных X = (x1, x2 ,..., xn ) , обеспечивающий максимальное (минимальное, заданное) значение целевой функции E(x1, x2 ,..., xn ) .
Следующим этапом при подготовке задачи к решению является программирование математических выражений, связывающих между собой исходные числовые данные и вычисляемые выражения. Электронные таблицы Excel позволяют записывать в выбранную ячейку не только числа, но и математические выражения, составленные по общим правилам языков программирования с использованием символа присваивания =, знаков операций (+,–,*,/) и встроенных функций. В качестве операндов в таких выражениях могут использоваться константы или имена ячеек Excel. [3,c.113]
Задача .Отделы кредитования коммерческого банка К1, К2, К3, К4 , выделяют кредиты фирмам Ф1, Ф2, Ф3 , Ф4 . Дана матрица Р, в которой на позиции (i,j) указана процентная ставка, под которую i-тый отдел может выделить деньги j-й фирме. Даны также векторы А и В; i-тая координата вектора А равна общей сумме кредита, который может выделить отдел Кi, j-я координата вектора В равна потребности в кредитах фирмы Фj. Найти оптимальное распределение банковских кредитов между фирмами, максимизирующее общую прибыль банка при дополнительном условии, что спрос фирм Ф1 и Ф3 должен выполнен полностью.
Представим данные в табличной форме:
| Банки | Фирмы и спрос | Возможности банков | |||
| Ф1 | Ф2 | Ф3 | Ф4 | ||
| К1 | 8 | 13 | 9 | 6 | 170 |
| К2 | 2 | 16 | 8 | 5 | 124 |
| К3 | 7 | 8 | 14 | 9 | 96 |
| К4 | 11 | 4 | 8 | 3 | 75 |
| Спрос ∑ | 184 | 99 | 156 | 75 | 465514 |
Так как сумма потребностей фирм превышают суммарную возможность банков по предоставлению кредита введем фиктивный банк с нулевыми процентными ставками и возможностью предоставить кредит на сумму 514-465 =49.
| Банки | Фирмы и спрос | Возможности банков | |||
| Ф1 | Ф2 | Ф3 | Ф4 | ||
| К1 | 8 | 13 | 9 | 6 | 170 |
| К2 | 2 | 16 | 8 | 5 | 124 |
| К3 | 7 | 8 | 14 | 9 | 96 |
| К4 | 11 | 4 | 8 | 3 | 75 |
| К5 | 0 | 0 | 0 | 0 | 49 |
| Спрос ∑ | 184 | 99 | 156 | 75 | 514514 |
Составим математическую модель задачи.
Обозначим хi,j – сумма кредита i-го банка j-той фирме, тогда целевая функция примет вид:
8*х11+13*х12 + 9*х13+6*х14 + 2*х21 + 16*х22 + 8*х23 + 5*х24 + 7*х31 + 8*х32 + 14*х33 + 9*х34 + 11*х41 + 4*х42 + 8*х43 + 3*х44→ max
При следующих ограничениях:
х11+х12+х13+х14=170х21+х22+х23+х24=124
х31+х32+х33+х34=96
х41+х42+х43+х44=75
х51+х52+х53+х54=49
х11+х21+х31+х41=184
х12+х22+х32+х42+х52<=99
х13+х23+х33+х43=156
х14+х24+х34+х44+х54<=75
хi,j > 0.
Задачу решаем в MSExcel. Предварительно заполним данными матрицы кредитов и процентов. Введем формулы расчета ограничений в ячейки В12:Е12 по фирмам и F5:F9 по кредитам.
Воспользуемся надстройкой «Поиск решения» для решения задачи:
Введем адрес ячейки для целевой функции Н12, выберем максимальное значение. Далее в окне ограничения введем все ограничения из условия задачи:
Введем дополнительные ограничения:
Установим диапазон ячеек для изменения:
Получаем результат:
Таким образом, если не учитывать фиктивный банк К5 имеем решение задачи:
Для получения максимальной выгоды:
Банк К1 должен дать кредит фирмам- Ф1 -109, Ф3- 48, Ф4 – 13;
Банк К2 кредит фирмам – Ф2 -99, Ф3 -12, Ф4 -13;
Банк К3 кредит банкам – Ф3 – 96;
Банк К4 кредит банкам – Ф1 – 75.
Тогда общий доход составит – 5296.
Невыполненным останется спрос фирмы Ф4 - 26 при спросе - 75.
Если не учитывать фиктивный банк К5, решение будет выглядеть следующим образом:
Получаем решение ЦФ=3978
Традиционный способ изучения экономико-математических методов заключается не только в определении их назначения и сути, но и в освоении техники реализации, причем, чтобы сделать доступной «ручную» реализацию, объем обрабатываемых данных приходится максимально сокращать, что, с одной стороны, часто удаляет построенную модель от реальной жизни, а с другой – снижает эффективность применения изучаемых методов.
Использование компьютерных технологий освобождает от рутинной вычислительной работы по реализации математических методов и позволяет сконцентрировать внимание не на алгоритме вычисления, а непосредственно на анализе результатов моделирования, что заметно повышает «коэффициент полезного действия» затраченного времени. [1]
1. http://exsolver.narod.ru/LM/index.html
2.MicrosoftExcel2003. , БХВ - Санкт-Петербург, 2005 г.
3. А. Г. Степанов. Разработка управленческого решения средствами пакета Еxcel., Учебное пособие.,Санкт-Петербург-2001 г.
4.Е.В.Бережная, В.И.Бережной., Математические методы моделирования экономических систем., Москва. «Финансы и статистика»-2008 г.