Как использовать решатель solver в calc

В open office calc: сервис / поиск решения.

Информатика, информационные технологии

Цель работы: Изучение возможностей пакета Ms Excel при решении задач линейного программирования. Приобретение навыков решения задач линейного программирования.

В задачах линейного программирования всегда необходимо найти минимум (или максимум) линейной функции многих переменных при линейных ограничениях в виде равенств или неравенств.

В задачи целочисленного программирования добавляется ограничение, что всеxi должны быть целыми.

1. Проверьте, если у вас установлена надстройка «Поиск решения» (рис. 2), пропустите этот пункт.

Рис. 2. Надстройка Поиск решения установлена; вкладка «Данные», группа «Анализ»

Если надстройки «Поиск решения» вы на ленте Excel не обнаружили, щелкните на кнопку Microsoft Office, а затем Параметры Excel (рис. 3).

Рис. 3. Параметры Excel

Выберите строку Надстройки, а затем в самом низу окна «Управление надстройками Microsoft Excel» выберите «Перейти» (рис. 4).

Рис. 4. Надстройки Excel

В окне «Надстройки» установите флажок «Поиск решения» и нажмите Ok (рис. 5). (Если «Поиск решения» отсутствует в списке поля «Надстройки», чтобы найти надстройку, нажмите кнопку Обзор. В случае появления сообщения о том, что надстройка для поиска решения не установлена на компьютере, нажмите кнопку Да, чтобы установить ее.)

Рис. 5. Активация надстройки «Поиск решения»

После загрузки надстройки для поиска решения в группе Анализ на вкладке Данные становится доступна команда Поиск решения (рис. 2).

2. Пример.Решить задачу линейного программирования:

L = 5×1 — 2x3min
— 5×1 — x2 + 2×3 ? 2
— x 1+x3 + x4 ? 5
— 3×1 + 5×4 ? 7

Пусть значения x1, x2, x3, x4 хранятся в ячейках A1:A4, a значение функции L — в ячейке С1 = =5*A1-2*A3.

С2 = -5*A1 — A2 + 2*A3
С3 = -А1 +А3 + А4
С4 = -3*А1 + 5*А4.

Таким образом, было задано условие исходной задачи линейного программирования.

Выполним команду из главного вкладка «Данные»Поиск решения (рис. 6.1).

В Open Office Calc: Сервис / Поиск решения.

Назначение основных кнопок и окон диалогового окна Поиск решения:

Поле Установить целевую ячейку — определяет целевую ячейку, значение которой необходимо максимизировать или минимизировать, или сделать равным конкретному значению.
Опции минимальному значению, максимальному значению и значению, определяют, что необходимо сделать со значением целевой ячейки — максимизировать, минимизировать или сделать равным конкретному значению.
Поле Изменяя ячейки определяет изменяемые ячейки. Изменяемая ячейка — это ячейка, которая может быть изменена в процессе поиска решения для достижения нужного результата в ячейке из окна Установить целевую ячейку с удовлетворением поставленных ограничений.
Кнопка Предположить отыскивает все неформульные ячейки, прямо или непрямо зависящие от формулы в окне Установить целевую ячейку, и помещает их ссылки в окно Изменяя ячейки.
Окно Ограничения перечисляет текущие ограничения в данной задаче. Ограничение есть условие, которое должно удовлетворяться решением; ограничения перечисляются в виде ячеек или интервалов ячеек, обычно содержащих формулу, которая зависит от одной или нескольких изменяемых ячеек, чье значение должно попадать внутрь определенных границ или удовлетворять равенству.
кнопки Добавить, Изменить, Удалить позволяют добавить, изменить или удалить ограничение.
Кнопка Выполнить запускает процесс решения определенной задачи.
Кнопка Закрыть закрывает окно диалога, не решая проблемы. Сохраняются лишь изменения, сделанные при помощи кнопок Параметры, Добавить, Изменить и Удалить. Не сохраняются изменения, произведенные после использования данных кнопок.
Кнопка Параметры выводит окно диалога Параметры поиска решения, в котором можно контролировать различные аспекты процесса отыскания решения, а также загрузить или сохранить некоторые параметры, такие, как выделение ячеек и ограничений, для какойто конкретной задачи на рабочем листе.
Кнопка Сбросить очищает все текущие установки задачи и возвращает все параметры к их значениям по умолчанию.

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

Устремим целевую функцию в ячейке C1 к минимуму. Для этого введем в поле Установить целевую функцию значение С1 и установим опцию равной минимальному значению.

В поле Изменяя ячейки необходимо указать адреса ячеек, в которых хранятся изменяемые значения. В нашем случае это ячейки А1:А4.

Для добавления ограничений необходимо щелкнуть по кнопке Добавить, появится диалоговое окно Добавить ограничение (рис. 6.2).

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

Щелчок по кнопке OK означает ввод очередного ограничения и возврат к диалоговому окну Поиск решения.

Щелчок по кнопке Добавить вводить очередное ограничение, находясь в окне Добавить ограничение.

В нашем случае окно будет иметь вид, изображенный на рис. 6.3. Щелчок по кнопке Выполнить начнет процесс решения задачи, завершится который появлением диалогового окна, изображенного на рис. 6.4.

Щелчок по кнопке OK приведет к появлению в ячейке С1 значения целевой функции L, а в ячейках A1:A4 — значений переменных x1-x4, при которых целевая функция достигает минимального значения.

Если задача не имеет решения или неверно были заданы исходные данные, в окне Результаты поиска решения может появиться сообщение о том, что решение не найдено.

Если вместо окна «Результат поиска решения» появилось что-то иное, Excel`ю найти решение не удалось. Проверьте правильность заполнения окна «Поиск решения». И еще одна маленькая хитрость. Попробуйте уменьшить точность поиска решения. Для этого в окне «Поиск решения» щелкните на Параметры (рис.) и увеличьте погрешность вычисления, например, до 0,001. Иногда из-за высокой точности Excel не успевает за 100 итераций найти решение. Можно так же увеличить предельное число итераций.

Увеличение погрешности вычислений

В Open Office Calc:

Статьи к прочтению:

В ответе укажите только число, без каких-либо знаков препинания, например 100
V. порядок проведения конкурса

Подбор параметра

Практическое применение алгоритма решения задачи коммивояжера Текст научной статьи по специальности «Математика»

ЛОГИСТИКА / LOGISTICS / ЛОГИСТИЧЕСКИЙ ПОДХОД / LOGISTIC APPROACH / ЗАДАЧА КОММИВОЯЖЕРА / TRAVELING SALESMAN PROBLEM / ЗАДАЧА СТРАНСТВУЮЩЕГО ТОРГОВЦА / NP-DIFFICULT TASK / NP-СЛОЖНАЯ ЗАДАЧА / ОПТИМАЛЬНЫЙ МАРШРУТ / BEST ROUTE / ОПТИМИЗАЦИЯ ПЕРЕВОЗОК / OPTIMIZATION OF TRANSPORT / МИНИМИЗАЦИЯ ТРАНСПОРТНЫХ РАСХОДОВ / MINIMIZATION OF TRANSPORTATION COSTS / OPENOFFICE CALC / НАДСТРОЙКА «РЕШАТЕЛЬ» / COMPONENT «SOLVER» / THE OBJECTIVE OF THE TRAVELING SALESMAN

Аннотация научной статьи по математике, автор научной работы — Володина Е.В., Студентова Е.А.

Рассматривается возможность снижения логистических затрат на транспортировку посредством решения задачи коммивояжера . Предлагается алгоритм решения задачи с использованием вычислительной мощности надстройки «Решатель» OpenOffice Calc . На основании предложенного алгоритма прорешивается практическая ситуация и составляется оптимальный маршрут для ООО «Молоко Зауралья».

i Надоели баннеры? Вы всегда можете отключить рекламу.

Practical application of the algorythm for solving the traveling salesman problem

The possibility of reducing logistic costs for transportation by solving the traveling salesman problem is considered. The algirythm for solving the problem using computational power of OpenOffice Calc »s component «Solver» is suggested. On the basis of the proposed algorythm practical situatuion is solved and best route is formed. The conclusion about expediency of application of this method to solve practical problems is given.

Текст научной работы на тему «Практическое применение алгоритма решения задачи коммивояжера»

Практическое применение алгоритма решения задачи коммивояжера

Е.В. Володина, Е.А. Студентова Курганский государственный университет

Аннотация: Рассматривается возможность снижения логистических затрат на транспортировку посредством решения задачи коммивояжера. Предлагается алгоритм решения задачи с использованием вычислительной мощности надстройки «Решатель» ОрепОШсе Са1с. На основании предложенного алгоритма прорешивается практическая ситуация и составляется оптимальный маршрут для ООО «Молоко Зауралья». Ключевые слова: логистика, логистический подход, задача коммивояжера, задача странствующего торговца, КР-сложная задача, оптимальный маршрут, оптимизация перевозок, минимизация транспортных расходов, ОрепОГйсе Са1с, надстройка «Решатель».

Первоочередной задачей любого предприятия является поиск резервов снижения затрат на осуществляемую деятельность и как следствие повышение собственной конкурентоспособности и рентабельности. В современных условиях поиск таких резервов строится на основе логистического подхода, что связано с расширением содержания логистики, превращающейся из вспомогательного элемента, обеспечивающего реализацию хозяйственных процессов, в важный инструмент организации и ведения хозяйственной деятельности [1]. При этом одним из приоритетных направлений совершенствования с точки зрения логистического подхода является оптимизация перевозок. Это связано в первую очередь со структурой логистических затрат, значительную долю в которых (20-40% и более) составляют именно расходы на транспортную составляющую [2].

Существуют различные теоретические алгоритмы оптимизации таких затрат, но они довольно трудоемки и долговременны, а современный уровень развития техники и технологий открывает новые возможности решения различного рода задач. Поэтому мы предлагаем решить задачу странствующего торговца, или коммивояжера (ЗК) посредством использования программы ОрепОГйсе Са1с. Задача коммивояжера

заключается в нахождении оптимального маршрута, который проходит через все указанные пункты (города) хотя бы по одному разу с последующим возвращением в исходный пункт (город). В условиях задачи задаются критерий оптимальности маршрута (кратчайший, дешевый и т.п.) и соответствующие матрицы расстояний, стоимости и т.п. [3] Задачу странствующего торговца начали изучать еще в XVIII веке математик из Ирландии сэр Уильям Р. Гамильтон и британский математик Томас П. Киркман. Считается, что общая формулировка задачи коммивояжера впервые была изучена Карлом Менгером в Вене и Гарварде. Позже проблема исследовалась Хасслером, Уитни и Мерриллом в Принстоне [4]. За многие годы исследований было предложено множество вариантов решения ЗК, среди которых выделяют: алгоритм полного перебора, метод ветвей и границ, метод включения дальнего, BV-метод, генетический алгоритм, «Система муравьев» и некоторые другие [5]. Современный уровень развития технологий предлагает более широкие возможности для решения ЗК и определения наилучшего маршрута. Тем не менее, классическая задача коммивояжера относится к числу КР-сложных задач и требует для решения значительных вычислительных ресурсов [6]. Требуемое для решения задачи время пропорционально (п-1)! (где п — количество пунктов), в связи с чем можно сделать вывод о нецелесообразности попытки решения задачи странствующего торговца с числом городов более 50, т.к. для нахождения оптимального маршрута потребуется вычислительная мощность компьютеров всего мира [7]. Однако при более «скромном» количестве пунктов, в которых необходимо побывать, решение ЗК посредством компьютерных вычислительных мощностей представляется наиболее эффективным, в частности в данной статье предлагается использовать надстройку ОрепОГйсе Са1с «Решатель» для целей минимизации затрат предприятия ООО «Молоко Зауралья» на доставку продукции.

Практическая ситуация: ООО «Молоко Зауралья» осуществляет поставку собственной продукции, общее количество пунктов 19, необходимо решить задачу коммивояжера для ответа на вопрос является ли принятый на предприятии маршрут оптимальным.

Т.к. количество пунктов доставки не слишком велико для решения задачи воспользуемся возможностями надстройки «Решатель» программы OpenOffice Ca1c, который после задания ему условий задачи осуществит полный перебор всех возможных вариантов решения с целью планирования наилучшего маршрута. Алгоритм решения задачи коммивояжера посредством использования программного продукта OpenOffice Ca1c представлен на рис. 1 (на основании источника [8]).

Рис. 1. — Алгоритм решения задачи коммивояжера с использованием надстройки «Решатель» OpenOffice Ca1c

ООО «Молоко Зауралья» (обозначим как пункт №1) осуществляет поставку продукции для следующих учреждений: ЗАО «Одиссей» (№2), школа №7 (№3), дом ребенка (№4), продовольственный магазин «Трио» (№5), ООО «Вира» (№6), детские сады 116 (№7), 122 (№8), 124 (№9), 126 (№10), 127 (№11), 129 (№12), 130 (№13), 131 (№14), 133 (№15), 134 (№16), 135 (№17), 138 (№18), 141 (№19). На основании данных сайта 2Гис (Курган) [9] была составлена матрица расстояний Су (в км) между перечисленными выше пунктами (табл. 1 и табл. 2).

Матрица расстояний, в км (пункты 1-9)

Пункты №2 №3 №4 №5 №6 №7 №8 №9

№1 7,63 8 7,06 7,1 8,46 8,52 7,95 7,96

№2 0,31 1,9 1,33 1,28 1,34 0,78 0,78

№3 1,4 0,65 1,59 1,66 1,09 1,09

№4 1,43 1,86 1,42 0,51 0,31

Решатель

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

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.

Frequently asked questions — Calc

Решатель интегрирован в LibreOffice и активируется из пункта меню Сервис ▸ Решатель. .

Окно решателя

Встроенный в LibreOffice решатель поддерживает только линейные уравнения. Но есть расширение NLPSolver, позволяющее обрабатывать нелинейные задачи. Информация о функциональности NLPSolver доступна по этой ссылке.

Также вы можете использовать инструмент Подбор параметра, который позволит вам подобрать параметр для решения.

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.

Можно использовать другие инструменты, такие как макрос Fitoo, инструмент нелинейной корреляции, созданный Laurent Godard и доступный по ссылке [1].

Для полиномиальных корреляций, есть следующее расширение the CorelPolyGUI .