Настройка и порядок решения задачи

Программные средства оптимизации

 

Программы, предназначенные для решения оптимизационных задач условно можно разделить на два класса:

1) универсальные программные средства, включающие в свой состав комплекс методов детерминированного и стохастического моделирования и составные элементы универсальных пакетов для обработки табличной информации (электронные таблицы): STATGRAFT, SYSTAT, MATLAB, Supercalcs, Lotus, MS Excel и др.;

2) специальные программы, предназначенные для решения узкого круга задач. Для целей линейного программирования такими программами являются пакеты LPR-88, LINDO, LO-4.

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

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

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

Таблица

Сравнительная характеристика LO-4, LPR-88 и MS Excel

Характеристика	LO-4	LPR-88	MS Excel
1. Метод решения задачи	Модифицированный симплексный метод	Обычный симплексный метод	Градиентный метод, метод Ньютона с решением как линейных, так и нелинейных задач
2. Размеры	1000 переменных / 1000 ограничений	100 переменных / 250 ограничений	Ограничены размерами рабочего листа программы: 230 столбцов / 120 строк
3. Сервисные услуги	4 выходные формы, возможность указания имен на русском языке	2 выходные формы, длина имен <= 6 символов, макс. точность 8 знаков	3 выходные формы (+ исходная и результатная матрицы), длина имен – произвольная, точность в числовом формате до 30 знаков
4. Тип компьютера	IBM PC/AT – 486 и выше

 

Ввод матрицы ЭММ в ЭВМ

 

Порядок ввода матрицы в программе MS Excel:

1) в ячейки строки «Наименование переменных» ввести наименования используемых переменных;

2) в ячейки строки «Обозначения переменных» ввести обозначения переменных;

3) в ячейки строки «Значения переменных» ввести нули;

4) выделить блок ячеек (массив), содержащих значения переменных. Выполнить команду Вставка -> Имя -> Присвоить. В поле «Имя» ввести текст «Переменные».

5) в ячейки столбца «Наименование и тип ограничения» ввести наименования используемых в модели ограничений, предварительно разделенных по типу (<=, >=, =, прочие) на группы;

6) в ячейки столбца «№ п.п.» ввести порядковые снизу вверх номера ограничений;

7) в ячейки столбцов «Нормативы» по каждому ограничению ввести коэффициенты при переменных;

8) в ячейках столбца «Потребности» записать формулу (или внести функцию) =СУММПРОИЗВ(Переменные; «Массив ячеек, содержащих коэффициенты при переменных в соответствующем ограничении» ).

Примечание: а) перемножаемый массив ячеек должен иметь одинаковую размерность, равную числу переменных; б) достаточно ввести формулу один раз в одну из ячеек столбца «Потребности», после чего ее следует скопировать в остальные ячейки указанного столбца методом автозаполнения; в)после ввода формул во всех ячейках столбца «Потребности» должны стоять нули;

9) в ячейках столбца «Знак ограничения» ввести знаки ограничений;

10) в ячейках столбца «Размер ограничения» ввести размеры ограничений;

11) в столбце «Потребности» блоку ячеек с ограничением типа «<=» присвоить имя «Потребности1», с ограничением типа «>=» - имя «Потребности2», типа «=» - «Потребности3». В столбце «Размер ограничения» соответствующим блокам ячеек присвоить имена «Ограничения1», «Ограничения2» и «Ограничения3»;

12) в ячейки строки «Функция цели» ввести коэффициенты целевой функции, а блоку ячеек содержащих коэффициенты присвоить имя «Коэффициенты»;

13) в ячейку «Значение функции цели» ввести формулу =СУММПРОИЗВ(Переменные; Коэффициенты). Примечание: а)размерность массивов «Переменные» и «Коэффициенты» должна быть равна числу переменных; б)после ввода формулы значение функции цели должно быть равно нулю.

 

Настройка и порядок решения задачи

1. Выполнить команду Сервис -> Поиск решения.

2. В окне Поиск решения нажать командную кнопку Параметры. В окне Параметры поиска решения в поле ввода «Предельное число итераций» установить число итераций (не менее 1000). В этом же окне в поле выбора (квадратики) «Линейная модель» поставить знак √ (галочка). Если остальные поля выбора содержат знак галочки, их следует отменить). Здесь же установить следующие переключатели: «Оценки» - линейная, «Разности» - положительные, «Метод поиска» - метод Ньютона. После изменения параметров поиска решения нажать командную кнопку «Ок».

3. В окне «Поиск решения» в поле ввода «Установить целевую ячейку» ввести имя ячейки, содержащей значение целевой функции. Из группы переключателей «Равной» выбрать, отвечающий цели задачи: минимизация, максимизация, достижение какого-либо конкретного значения. В поле ввода «Изменяя ячейки» ввести текст Переменные (либо выбрать блок ячеек, содержащих значения переменных). В поле ввода «Ограничения», используя кнопку «Добавить», ввести неравенства, отвечающие заданным типам ограничениям.

4. Решить задачу оптимизации ЭММ:

1) в окне «Поиск решения» нажать командную кнопку «Выполнить»;

2) если в окне «Результаты поиска решения» сказано, что подходящее решение не найдено, необходимо сделать следующее: а)не закрывая указанное окно, проанализировать соответствие полученных потребностей (возможностей) заданным знакам и размерам ограничений; б)выйти из окна «Результаты поиска решения», нажав командную кнопку «Отмена»; в)произвести необходимые корректировки ЭММ и матрицы; г)предпринять дальнейшие попытки решения. Проводя корректировку размеров и типов ограничений необходимо учитывать следующие (сверху вниз по степени важности) требования: а)должен быть получен оптимальный план; б)должны выполняться предельно допустимые размеры ограничений (например, минимальные планы производства продукции, существующие договора по ее реализации и т.д.); в)значение функции цели должно быть наиболее максимальным (минимальным); г)ресурсы хозяйства должны быть максимально использованы. Примечание: в процессе решения задачи после корректировки размеров и типов одних ограничений может возникать несоответствие потребностей (возможностей) размерам и типам других ограничений, что следует преодолевать в указанном выше порядке;

3) если в окне «Результаты поиска решения» сказано, что решение найдено, то следует в поле выбора «Тип отчета» выделить все три типа отчета: «Результаты», «Устойчивость» и «Пределы», а затем нажать кнопку «Ок». В книге MS Excel появятся дополнительные листы: «Отчет по результатам», «Отчет по пределам» и «Отчет по устойчивости». Примечание: найденное оптимальное решение может не удовлетворять перечисленным выше требованиям (например, ресурсы хозяйства могут быть недоиспользованы), что может стать поводом для дальнейших корректировок ЭММ и поиска решения, в большей степени удовлетворяющего заданной цели и условиям задачи.

8. Вывести на принтер результаты решения (матрицу с полученным решением) и полученные три отчета. Примечание: предварительно результаты решения и данные отчетов следует отформатировать (изменить ширину столбцов и высоту строк, числовой формат ячеек и т. д.)