Модуль "Математические и статистические методы анализа данных в MS Excel", страница 4

Надстройка MS Excel "Поиск решения" устанавливается с помощью команды Сервис, Надстройки, она позволяет решать как прямую, так и двойственную задачу ЛП, а также задачи нелинейного программирования (целевая функция или  ограничения нелинейные). В "Поиске решения" используются алгоритмы нелинейной оптимизации, симплекс–метод, метод ветвей и границ для решения линейных и целочисленных задач с ограничениями.  

Команда Сервис, Поиск решения вызывает одноименное диалоговое окно для формирования модели и  настройки параметров оптимизации (кнопка Параметры). В диалоговом окне «Параметры поиска решения» задаются следующие параметры:

§  максимальное время решения задачи, измеряется в секундах (до 10 час.);

§  число итераций для подбора (до 10000);

§ точность (разность между искомым и модельным значением);

§  допустимое отклонение (точность для задач поиска целочисленного программирования);

§ сходимость (условие прекращения поиска решения для задач нелинейного программирования, допустимое отклонение целевой функции за 5 последовательных итераций);

§ признак линейной модели задачи;

§ признак показа результатов итераций;

§ автоматическое масштабирование для учета размерности входных и выходных значений;

§ неотрицательные значения ограничений;

§ метод оценки при экстраполяции: линейная — для линейной модели, квадратичная — для нелинейной модели;

§ метод вычисления производных: прямые — скорость изменения ограничений невысокая, центральные — более точное вычисление частных производных целевой функции и ограничений;

§ метод решения: Ньютона — более быстрое решение, больший расход памяти; градиентов — для задач большой размерности при нехватке памяти.

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

первая ячейка	=МАКС($A$1)
вторая ячейка (количество переменных)	=СЧЁТ($C$1:$F$1)
третья и последующие ячейки (по числу строк ограничений)
	=$J$5:$J$9<=Лист1!$H$5:$H$9
	=$C$1:$F$1>=0
	=$C$1:$F$1=ЦЕЛОЕ($C$1:$F$1)
последняя ячейка - параметры вычисления:   максимальное время (сек);   предельное число итераций;   относительная погрешность;   допустимое отклонение;   линейная модель;   неотрицательные значения;   автоматическое масштабирование;   оценка линейная (1)/ квадратичная (2);   разности прямые (1)/ центральные (2);   метод поиска Ньютона (1) / сопряженных градиентов (2)   сходимость;   показывать результаты итераций	={100: 100 :0,000001 :0,05 :ЛОЖЬ :ЛОЖЬ :ЛОЖЬ :1 :1 :1 :0,0001 :ЛОЖЬ}

MS Excel не использует имена блоков при записи модели.

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

Для анализа результатов решения задачи можно вывести отчеты:

1.  Результаты — отчет содержит целевую ячейку и список влияющих ячеек модели, исходные и конечные значения, формулы для расчета ограничений.

2.  Устойчивость — отчет содержит сведения о чувствительности решения к малым изменениям в формуле целевой ячейкиили в формулах ограничений. Для нелинейных моделей отчет содержит данные для градиентов и множителей Лагранжа (ограниченные затраты, фиктивные цены, объективный коэффициент с некоторым допуском, а также диапазоны ограничений справа). Если указано ограничение целочисленности переменных, отчет Устойчивость не выводится.

3.  Ограничения — отчет состоит из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно, верхним пределом называется наибольшее значение. Если указано ограничение целочисленности переменных, отчет Ограничения не выводится.

Ограничение на размерность оптимизационных задач для "Поиска решения":
  Число переменных + количество уравнений ограничений <= 200

Пример задачи ОЗЛП - "Расчет оптимальной производственной программы"

В задаче выбора производственной программы определяется объем выпуска продукции (работ, услуг) определенной номенклатуры, обеспечивающего максимум прибыли (дохода). Коэффициенты целевой функции соответствуют понятиям «цена» или «доход/прибыль» для единицы продукции.

Выпуск продукции осуществляется с учетом ограничений на расход и запас различных по своей природе  "ресурсов". Нормы расхода ресурсов на единицу продукции известны, а объем выпуска не может быть отрицательным. В ряде постановок задач также известно, что продукция не допускает деления на части.

Для решения задачи рекомендуется определенная схема расположения исходных данных (рис.1) и использование именованных блоков для диапазонов ячеек  (табл.1).

Таблица 1

№ п/п	Название блока	Тип блока	Примечание
1	РЕЗУЛЬТАТЫ	Вектор-столбец или вектор-строка	Размерность блока - число переменных
2	КОЭФФИЦИЕНТЫ	Вектор-столбец или вектор-строка	Размерность блока - число переменных
3	НОРМЫ	Сведение о нормативах затрат ресурсов различных видов на единицу продукции	Размерность блока - число видов ресурсов * число переменных
4	ПОТРЕБНОСТИ	Вектор-столбец или вектор-строка	Размерность  блока  -  число видов ресурсов
5	ЗАПАСЫ	Вектор-столбец или вектор-строка	Размерность блока - число видов ресурсов
6	Цель (целевая функция)	Ячейка	Только 1 ячейка