Настройка и порядок решения задачи
Программные средства оптимизации
Программы, предназначенные для решения оптимизационных задач условно можно разделить на два класса:
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. Вывести на принтер результаты решения (матрицу с полученным решением) и полученные три отчета. Примечание: предварительно результаты решения и данные отчетов следует отформатировать (изменить ширину столбцов и высоту строк, числовой формат ячеек и т. д.)