Использование модуля «Solver» в OpenOffice.org Calc
В современных коммерческих офисных пакетах имеется модуль электронной таблицы (ЭТ), называемый «Solver» (или «Поиск решения»), который используется для решения задач, относящихся к классу «линейной оптимизации».
Однако в свободном офисном пакете OpenOffice.org начиная с версии 2.3 такой модуль также имеется (либо как расширение, устанавливаемое пользователями дополнительно, либо прямо в составе сборки пакета). Таким образом, решение задач линейной оптимизации вполне возможно и с использованием свободно распространяемых офисных пакетов (аналогичный модуль есть в составе свободной электронной таблицы Gnumeric).
Задача линейной оптимизации.
Для разбора предлагается задача, взятая из учебного пособия «Математическое программирование», авторы Э.Ф.Брыжина и Э.А.Худобина, издательство СПбГИЭА, 1997 год.
Задача: Имеется три вида сырья в количествах 45 ед., 19 ед. и 10 ед. Из этого сырья нужно изготовить продукцию двух видов. Задан расход сырья каждого вида на производство единицы каждого вида продукции и прибыть от единицы продукции (см. таблицу). Требуется найти такой вариант выпуска каждого вида продукции, при котором прибыль будет наибольшей.
Таблица исходных данных для задачи.
(Далее – абзац по тексту источника) Обозначим через x1 количество единиц продукции первого вида, через x2 – второго вида. Тогда на выпуск этой продукции будет израсходовано 5x1 +9x2 ед. сырья первого вида, 3x1 +3x2 ед сырья второго вида и 2x1 +x2 — третьего. Суммарная прибыль составит 5x1 +6x2 денежных единиц. Т.к. нельзя израсходовать сырья больше, чем имеется, а суммарная прибыль зависит от количества выпущенной продукции, то получим следующую математическую модель данной задачи.
Решение задачи с использованием модуля «Solver».
Для решения задачи в ЭТ прежде всего нужно определиться с расположением исходных данных и составить необходимые формулы. Пусть таблица будет скомпонована в соответствии с рис. 1.
Рисунок 1. Исходные данные и формулы для поиска решения
Количества продукции 1-го и 2-го вида (которые предстоит вычислить) располагаются в ячейках A3 и B3 соответственно. В C3 – формула для вычисления прибыли, в B6:B8 – формулы для левых частей ограничений (см. математическую модель). Соответствующие формулы, реализующие математическую модель, показаны на сером фоне справа от ячеек, в которые они должны быть записаны. Когда решение будет найдено, нули в ячейках ЭТ и пустые ячейки для параметров модели будут заменены какими-то другими значениями.
Вызов модуля «Solver» обеспечивается пунктом главного меню «Данные» (рис. 2).
Рисунок 2. Меню «Данные» пакета OpenOffice.org Calc
При выборе пункта «Solver» открывается диалог настройки поиска решения (рис. 3).
Рисунок 3. Диалог настройки поиска решения
В диалоге настройки поиска решения несколько полей ввода, и в них потребуется устанавливать адреса ячеек. Для поля «Целевая функция» требуется указать адрес ячейки, содержащей формулу для расчёта прибыли f(x) (в рассматриваемом примере — ячейка C3). Адрес можно ввести прямо в поле ввода, а можно нажать на кнопку сворачивания диалога справа от поля ввода и в получившуюся строку ввода (рис. 4) ввести адрес ячейки «методом указания», то есть щёлкнув левой кнопкой мыши по нужной ячейке (рис. 5).
Рисунок 4. Строка ввода для указания адреса ячейки или диапазона
Рисунок 5. Адрес указан выбором ячейки мышью
Для восстановления вида диалога снова воспользуемся кнопкой права от строки ввода.
Поскольку требуется найти максимум прибыли, переключатель «Цель» должен быть установлен в позицию «Максимум».
В поле ввода «Параметры функции» требуется указать ячейки, в которых должны вычисляться параметры (в нашем случае x1 и x2, то есть диапазон A3:B3). для заполнения этой строки опять используем соответствующую кнопку сворачивания диалога и метод указания, только теперь для выбора ячеек выделим нужный диапазон (рис. 6).
Рисунок 6. Выбор диапазона ячеек с параметрами целевой функции
Кнопка «Настройки» в диалоге позволяет ввести дополнительные ограничения модели (рис. 7).
Рисунок 7. Дополнительные ограничения модели
По самой природе рассматриваемой задачи должен быть включён режим «Линейная модель». Кроме того, в математической модели указано, что значения параметров должны быть неотрицательными (т.к. количество продукции не может быть отрицательным), поэтому включаем ещё и режим «Только положительные значения».
Далее, нужно добавить ограничения. Для этого нажимаем на кнопку «Добавить» и в появившемся мини-диалоге (рис. 8) определяем левую и правую части, а также вид (знак) ограничения.
Рисунок 8. Диалог добавления ограничения
В левой части каждого ограничения должен быть адрес одной ячейки (в которой записана формула для ограничения), а в правой части может быть как адрес ячейки, так и число (значение для ограничения), как, например, на рис. 9. В нашем случае для всех ограничений нужно устанавливать знак «не меньше» (<=), хотя возможны варианты «не больше» (>=) и «равно» (=). Для ввода адресов ячеек в левую часть ограничения тоже можно использовать «метод указания».
Рисунок 9. Ограничение с числом в правой части
Последовательно добавим все три ограничения и получим заполненный диалог настройки поиска решения (рис. 10).
Рисунок 10. Настройка поиска решения завершена
Нажатие на кнопку «Решить» приводит к появлению сообщения об успешно найденном решении (рис. 11), а в электронной таблице появляются значения параметров, целевой функции и ограничений, соответствующие найденному решению (рис. 12).
Рисунок 11. Сообщение об успехе
Рисунок 12. Результаты работы модуля «Solver»
Нужно отметить, что результаты полностью соответствуют приведённым в первоисточнике значениям 3 и 10/3.
Frequently asked questions — Calc
The multivariable solver integrated into LibreOffice is activated by the Menu Tools ▸ Solver .
The solver engine by default supports only linear equations, but the NLPSolver extension allows you to handle non-linear problems. You will find a full explanation of its functioning on [1].
Yous can also use the tool Goal seek :
- Set out the equations for your problem, with a cell to contain the initial value that is to be determined, and another containing the formula whose result needs to reach a certain value (the target value).
- Go to Tools ▸ Goal Seek .
- In Formula Cell, indicate the coordinates of the cell containing the formula which needs to attain the target value.
- In Target Value, indicate the value that should be reached in the preceding case.
- In Variable Cell, indicate the coordinates of the cell whose value is unknown and will be modified.
- Click OK.
The spreadsheet will show you if it has reached the target value and will suggest inserting a suitable value into the variable cell. Failing that, it will suggest a value for the variable cell which gets you as close as possible to the target value.
It is possible to use other tools, such as the Fitoo macro, a non-linear correlation tool, created by Laurent Godard, available at [2].
Как использовать решатель solver в calc
С = 
Opens the Solver dialog. A solver allows you to solve mathematical problems with multiple unknown variables and a set of constraints on the variables by goal-seeking methods.
Choose Tools — Solver .
Solver settings
The dialog settings are retained until you close the current document.
Target Cell
Enter or click the cell reference of the target cell. This field takes the address of the cell whose value is to be optimized.
Optimize results to
Maximum: Try to solve the equation for a maximum value of the target cell.
Minimum: Try to solve the equation for a minimum value of the target cell.
Value of: Try to solve the equation to approach a given value of the target cell.
Enter the value or a cell reference in the text field.
By Changing Cells
Enter the cell range that can be changed. These are the variables of the equations.
Limiting Conditions
Add the set of constraints for the mathematical problem. Each constraint is represented by a cell reference (a variable), an operator, and a value.
Cell reference: Enter a cell reference of the variable.
Click the Shrink button to shrink or restore the dialog. You can click or select cells in the sheet. You can enter a cell reference manually in the input box.
Operator: Select an operator from the list. Use Binary operator to restrict your variable to 0 or 1. Use the Integer operator to restrict your variable to take only integer values (no decimal part).
Value: Enter a value or a cell reference. This field is ignored when the operator is Binary or Integer.
Remove button: Click to remove the row from the list. Any rows from below this row move up.
You can set multiple conditions for a variable. For example, a variable in cell A1 that must be an integer less than 10. In that case, set two limiting conditions for A1.
Options
The Solver Options dialog let you select the different solver algorithms for either linear and non-linear problems and set their solving parameters.
Solve
Click to solve the problem with the current settings. The dialog settings are retained until you close the current document.
Using Non-Linear solvers
Regardless whether you use DEPS or SCO, you start by going to Tools — Solver and set the Cell to be optimized, the direction to go (minimization, maximization) and the cells to be modified to reach the goal. Then you go to the Options and specify the solver to be used and if necessary adjust the according parameters.
There is also a list of constraints you can use to restrict the possible range of solutions or to penalize certain conditions. However, in case of the evolutionary solvers DEPS and SCO, these constraints are also used to specify bounds on the variables of the problem. Due to the random nature of the algorithms, it is highly recommended to do so and give upper (and in case «Assume Non-Negative Variables» is turned off also lower) bounds for all variables. They don’t have to be near the actual solution (which is probably unknown) but should give a rough indication of the expected size (0 ≤ var ≤ 1 or maybe -1000000 ≤ var ≤ 1000000).
Bounds are specified by selecting one or more variables (as range) on the left side and entering a numerical value (not a cell or a formula) on the right side. That way you can also choose one or more variables to be Integer or Binary only.
Решатель
Opens the Solver dialog. A solver allows you to solve mathematical problems with multiple unknown variables and a set of constraints on the variables by goal-seeking methods.
Доступ к этой команде
Выберите Сервис — Решатель .
Solver settings
Solver settings are not saved to the file by LibreOffice Calc. Closing and reopening the file will reset the solver dialog to default settings.
Target Cell
Enter or click the cell reference of the target cell. This field takes the address of the cell whose value is to be optimized.
Optimize results to
Maximum: Try to solve the equation for a maximum value of the target cell.
Minimum: Try to solve the equation for a minimum value of the target cell.
Value of: Try to solve the equation to approach a given value of the target cell.
Enter the value or a cell reference in the text field.
By Changing Cells
Enter the cell range that can be changed. These are the variables of the equations.
Limiting Conditions
Add the set of constraints for the mathematical problem. Each constraint is represented by a cell reference (a variable), an operator, and a value.
Cell reference: Enter a cell reference of the variable.
Click the Shrink button to shrink or restore the dialog. You can click or select cells in the sheet. You can enter a cell reference manually in the input box.
Operator: Select an operator from the list. Use Binary operator to restrict your variable to 0 or 1. Use the Integer operator to restrict your variable to take only integer values (no decimal part).
Value: Enter a value or a cell reference. This field is ignored when the operator is Binary or Integer.
Remove button: Click to remove the row from the list. Any rows from below this row move up.
You can set multiple conditions for a variable. For example, a variable in cell A1 that must be an integer less than 10. In that case, set two limiting conditions for A1.
Параметры
The Solver Options dialog let you select the different solver algorithms for either linear and non-linear problems and set their solving parameters.
Решить
Click to solve the problem with the current settings. The dialog settings are retained until you close the current document.
Решение уравнений с помощью решателя
Цель процесса решателя состоит в том, чтобы найти те значения переменных уравнения, которые приводят к оптимизированному значению в целевой ячейке , также называемой «цель». Можно выбрать, должно ли значение в целевой ячейке быть максимальным, минимальным или оно должно быть приближением данного значения.
Начальные значения переменной вставляются в прямоугольный диапазон ячеек, вводимый в поле По изменяющимся ячейкам .
Можно определить ряд условий, устанавливающих ограничения для некоторых ячеек. Например, можно установить следующее ограничение: одна из переменных или ячеек не должна быть больше другой переменной или определённого значения. Также можно ввести следующее ограничение: одна или более переменных должны быть целыми числами (значения без знаков после запятой) или двоичными числами (разрешены только значения 1 и 0).
Using Non-Linear solvers
Regardless whether you use DEPS or SCO, you start by going to Tools — Solver and set the Cell to be optimized, the direction to go (minimization, maximization) and the cells to be modified to reach the goal. Then you go to the Options and specify the solver to be used and if necessary adjust the according parameters.
There is also a list of constraints you can use to restrict the possible range of solutions or to penalize certain conditions. However, in case of the evolutionary solvers DEPS and SCO, these constraints are also used to specify bounds on the variables of the problem. Due to the random nature of the algorithms, it is highly recommended to do so and give upper (and in case «Assume Non-Negative Variables» is turned off also lower) bounds for all variables. They don’t have to be near the actual solution (which is probably unknown) but should give a rough indication of the expected size (0 ≤ var ≤ 1 or maybe -1000000 ≤ var ≤ 1000000).
Bounds are specified by selecting one or more variables (as range) on the left side and entering a numerical value (not a cell or a formula) on the right side. That way you can also choose one or more variables to be Integer or Binary only.