Решение задач в Excel

«Поиск решений» — функция Excel, которую используют для оптимизации параметров: прибыли, плана продаж, схемы доставки грузов, маркетингового бюджета или рентабельности. Она помогает составить расписание сотрудников, распределить расходы в бизнес-плане или инвестиционные вложения. Знание этой функции экономит много времени и сил. Рассказываем, как освоить функцию поиска решений.

Основные параметры поиска решений

Найти решение задачи можно тремя способами. Во-первых, вручную перебирать параметры, пока не найдется оптимальное соотношение. Во-вторых, составить уравнение с большим количеством неизвестных. В-третьих, вбить данные в Excel и использовать «Поиск решений». Последний способ самый быстрый и покажет максимально точное решение, если знать, как использовать функцию.

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

Константы — исходная информация. К ней относится удельная маржинальная прибыль, стоимость каждой перевозки, нормы расхода товарно-материальных ценностей. В нашем случае — производительность работников, их оплата и норма в 1000 изделий. Также константа отражает ограничения и условия математической модели: например, только неотрицательные или целые значения. Мы вносим константы в таблицу цифрами или с помощью элементарных формул (СУММ, СРЗНАЧ).

Изменяемые ячейки — переменные, которые в итоге нужно найти. В задаче это распределение 1000 изделий между работниками с минимальными затратами. В разных случаях бывает одна изменяемая ячейка или диапазон. При заполнении функции «Поиск решений» важно оставить ячейки пустыми — программа сама найдет значения.

Целевая функция — результирующий показатель, для которого Excel подбирает наилучшие показатели. Чтобы программа понимала, какие данные наилучшие, мы задаем функцию в виде формулы. Эту формулу мы отображаем в отдельной ячейке. Результирующий показатель может принимать максимальное или минимальное значения, а также быть конкретным числом.

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

Пример использования поиска решений

Теперь перейдем к самой функции.

1) Чтобы включить «Поиск решений», выполните следующие шаги:

  • нажмите «Параметры Excel», а затем выберите категорию «Надстройки»;
  • в поле «Управление» выберите значение «Надстройки Excel» и нажмите кнопку «Перейти»;
  • в поле «Доступные надстройки» установите флажок рядом с пунктом «Поиск решения» и нажмите кнопку ОК.

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

Не забудьте ввести формулы. Стоимость заказа рассчитывается как «Оплата труда за 1 изделие» умножить на «Число заготовок, передаваемых в работу». Для того, чтобы узнать «Время на выполнение заказа», нужно «Число заготовок, передаваемых в работу» разделить на «Производительность».


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

4) Заполните параметры «Поиска решений» и нажмите «Найти решение».

Совокупная стоимость 1000 изделий рассчитывается как сумма стоимостей количества изделий от каждого работника. Данная ячейка (Е13) — это целевая функция. D9:D12 — изменяемые ячейки. «Поиск решений» определяет их оптимальные значения, чтобы целевая функция достигла минимума при заданных ограничениях.

В нашем примере следующие ограничения:

5) В конце проверьте полученные данные на соответствие заданному целевому значению. Если что-то не сходится — нужно пересмотреть исходные данные, введенные формулы и ограничения.

Использование этой функций поможет вам быстро оптимизировать работу и найти нужный результат. На онлайн-курсе «ToolKit Plus» мы делимся только теми функциями, которые действительно нужны на практике. Присоединяйтесь к обучению, чтобы работать эффективно.

Узнать о курсе

2.2. Процессоры электронных таблиц

2.2.7. Решение уравнений и задач оптимизации

Для решения задач оптимизации широкое променение находят различные средства Excel.

В этом разделе рассмотрим команды:

  1. Подбор параметров для нахождения значения, приводящего к требуемому результату.
  2. Надстройку Поиск решения для расчета оптимальной величины по нескольким переменным и ограничениям;
  3. Диспетчер сценариев для создания и оценки наборов сценариев «что – если» с несколькими вариантами исходных данных.

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

Основной командой для решения оптимизационных задач в Excel является команда Сервис/Подбор параметра. Эта команда определяет неизвестную величину, приводящую к требуемому результату.

Если команда Подбор параметра отсутствует в меню Сервис, выполните команду Сервис/Надстройка и установите флажок Пакет анализа в окне диалога Надстройка

Для работы с командой Подбор параметра необходимо подготовить лист, чтобы в листе находились:

  • формула для расчета;
  • пустая ячейка для искомого значения;
  • другие величины, которые используются в формуле.

Ссылка на пустую ячейку должна обязательно присутствовать в формуле, так как именно она является переменной, значение которой ищет Excel.

Во время подбора параметра в переменную ячейку непрерывно заносятся новые значения, пока не будет найдено решение поставленной задачи.

Такой процесс называется итерацией, и продолжается он до тех пор, пока редактор не выполнит 100 попыток или не найдет решения, лежащее в пределах точности 0,001 от точного значения (настройка этих параметров осуществляется с помощью команды Сервис/Параметры, вкладка Вычисления)

Оптимизация с помощью команды Подбор параметров выполняется так:

1. Создайте лист, например, с формулой =B1*B2 в ячейке B3, пустой (переменной) ячейкой (B2) и другими данными (B1), которые могут понадобиться при вычислениях. Например, необходимо определить количество книг по цене 23,75 грн., которые необходимо продать, чтобы объем продаж составил 10000,00 грн.


Рис. 1.

2. Выделите ячейку листа (B3), в которой содержится формула (эта ячейка появится в поле «Установить в ячейке» в окне диалога Подбор параметра). Выполните команду Сервис/Подбор параметра. Открывается окно диалога Подбор параметра.


Рис. 2.

3. Введите в текстовое поле Значение число, соответствующее объему продаж — 10000. Переместите курсор в текстовом поле Изменяя значения ячейки. Выделите ту ячейку, в которой должен содержаться ответ (переменная ячейка). Ее содержимое будет подобрано и подставлено в формулу командой Подбор параметра. Выделенная ячейка (B2) выделяется на листе рамкой. Нажмите кнопку ОК, чтобы найти решение.


Рис. 3.

После завершения итерационного цикла в окне диалога Результат подбора параметра появляется сообщение, а результат заносится в ячейку листа. Решение показывает, что для достижения объема продаж 10000 грн. необходимо продать 421 книгу по цене 23,75 грн. Для закрытия окна диалога Результат подбора параметра щелкните на кнопке ОК.

Команда Поиск решения

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

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

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

Общие свойства, которые характерны для задач, решаемых с помощью надстройки Поиск решения:

  1. Существует единственная целевая ячейка, содержащая формулу, значение которой должно быть сделано максимальным, минимальным или же равным, какому-то конкретному значению.
  2. Формула в этой целевой ячейке содержит ссылки на ряд изменяемых ячеек. Поиск решения заключается в том, чтобы подобрать такие значения переменных в изменяемых ячейках, которые бы обеспечили оптимальное значение для формулы в целевой ячейке.
  3. Может быть задано некоторое количество ограничений — условий или соотношений, которым должны удовлетворять некоторые из изменяемых ячеек.

Постановка задачи

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

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

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

  1. Выделите на листе целевую ячейку, в которую введена формула.
  2. Выполните команду Сервис/Поиск решения. Открывается окно диалога Поиск решения (Рис. 3.). Поскольку была выделена ячейка, в текстовом поле «Установить целевую ячейку» появится правильная ссылка на ячейку. В группе «Равной» переключатель по умолчанию устанавливается в положение «Максимальному значению».
  3. Перейдите к полю «Изменяя ячейки» и введите переменные ячейки листа.
  4. Добавьте ограничения на переменные в изменяемых ячейках. Для ввода ограничений нажмите кнопку Добавить, чтобы задать первое ограничение в окне диалога, затем можно ввести второе, третье и т.д.
  5. Когда оптимизационная задача будет готова к выполнению, можно нажать кнопку Выполнить для получения ответа. Появится окно диалога с описанием результатов процесса оптимизации.
  6. Чтобы отобразить найденное решение в ячейках листа, установите переключатель «Сохранить найденное решение» и нажмите кнопку ОК. Найденная максимальная величина помещается в целевую ячейку, а переменные ячейки заполняются оптимальными значениями переменных, которые удовлетворяют установленным ограничениям.


Рис. 4.

Диспетчер сценариев «что – если»

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

Чтобы устранить эти ограничения, разработчики Excel создали Диспетчер сценариев, помогающий работать с несколькими моделями «что – если». Командой Сервис/Сценарии можно создавать новые и просматривать существующие сценарии для решения задач, и отображать консолидированные отчеты.

Создание сценария

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

Создание сценариев происходит следующим образом:

  1. Выполните команду Сервис/Сценарии. Открывается изображение окна диалога Диспетчер сценариев.
  2. Нажмите кнопку Добавить, чтобы создать первый сценарий. Откроется окно диалога Добавление сценария.
  3. Введите Лучший вариант (или любое другое имя) в поле Название сценария, затем с помощью окон диалога введите изменяемые ячейки. Когда этот сценарий будет готов, введите следующий.
  4. Нажмите кнопку Добавить, чтобы создать второй сценарий. Введите название Худший вариант. После завершения создания двух сценарием можно приступить к просмотру результатов.
  5. Закройте окно диалога Диспетчер сценариев кнопкой Закрыть.


Рис. 5.

Рис. 6.

Просмотр сценария

Excel сохраняет сценарии вместе с листом текущей книги, и просмотр их командой Сервис /Сценарии возможен только при открытии данного листа. Просмотр сценария выполняется следующим образом:

  1. Выполните команду Сервис/Сценарии. Открывается окно диалога.
  2. Выберите из списка сценарий для просмотра.
  3. Нажмите кнопку Вывести. Excel заменяет содержимое ячеек листа значениями из сценария и отображает результаты на листе.
  4. Выберите из списка другие сценарии и воспользуйтесь кнопкой Вывести для сравнения результатов моделей «что – если». После завершения нажмите кнопку Закрыть. Значения последнего активного сценария остаются в ячейках листа.

Создание отчетов по сценарию

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

Эту задачу можно выполнить с помощью кнопки Отчет в окне диалога Диспетчер сценариев. Созданный сводный отчет будет автоматически отформатирован и скопирован на новый лист текущей книги.

Создание отчета по сценарию происходит следующим образом:

  1. Выполните команду Сервис/Сценарии. Откроется окно диалога Диспетчер сценариев.
  2. Нажмите кнопку Отчет. Открывается окно диалога Отчет по сценарию, в котором предлагается выбрать ячейки, входящие в отчет, а также его тип. Отчет типа структура представляет собой форматированную таблицу, которая выводится на отдельном листе. Отчет сводная таблица является специальной таблицей, которую можно настраивать за счет перестановки столбцов и строк.

Далее …>>> Тема: 2.3.1. Современные способы организации презентаций средствами PowerPoіnt

Оптимизация значений таблицы Excel, удовлетворяющих определенным критериям, может быть сложным процессом. К счастью, Microsoft предлагает надстройку Решение проблем для численной оптимизации. Хотя данный сервис не может решить всех проблем, он может быть полезным в качестве инструмента что-если. Данный пост посвящен надстройке Решение проблем в Excel.

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

Что такое Поиск решений

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

Где в Excel поиск решений

Надстройка Поиск решений поставляется вместе с Excel, но по умолчанию отключена. Чтобы включить его, перейдите по вкладке Файл в группу Параметры. В появившемся диалоговом окне Параметры, выберите Надстройки -> Управление: Надстройки Excel -> Перейти. В окне Надстройки устанавливаем галочку напротив поля Поиск решения, жмем ОК.

Теперь во вкладке Данные появилась новая группа Анализ с кнопкой Поиск решения.

Пример использования Поиска решения

Данный пост основан на примере использования Надстройки Поиск решения. Файл совместим со всеми версиями Excel.

Определение проблемы

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

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

Для начала требуется определить каждый пункт к какой-нибудь группе.

Чтобы указать привязанность пункта к группе, будем помечать их единицей (1), в противном случае нулем (0).

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

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

Наконец, нам необходимо свести сумму групп и работать с разницей между ними.

Наша задача минимизировать разницу между суммами групп.

Теперь мы можем присвоить каждой группе пункты, для этого вручную проставляем единицы в столбцах С и D. Excel отобразит разницу сумм групп в ячейке G11.

Для большей наглядности я добавил условное форматирование для ячеек, имеющих значение >0.

Проблема в том, что количество возможных комбинаций 28, т.е. 256 вероятных ответов на вопрос. Если на каждый из них тратить по 5 секунд, это займет у нас 21,3 минуты, предполагая, что мы сможем выдержать темп и запомнить лучшую комбинацию.

Вот где Поиск решения находит применение.

Поиск оптимального решения в Excel

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

Наши правила

Наше основное требование – это минимизировать разницу между двумя группами. В нашем примере она находится в ячейке G11 – Группа B минус Группа A. Нам нужно, чтобы значение в ячейке G11 было настолько малым насколько это возможно, но больше или равно 0.

Мы также знаем, что пункт может находиться либо в Группе A, либо в Группе B, к тому он не может быть дробным. Таким образом у нас два ограничения для каждого элемента:

Во-первых: Значение элемента в колонке Итог должна равняться единице.

Во-вторых: Значения элементов в группах должны быть целыми.

Мы также знаем, что общее количество элементов 8, это еще одно ограничение. Как использовать эти ограничения мы обсудим в следующем разделе.

Диалоговое окно Поиска решения

В этом разделе описано окно надстройки Поиск решения и его использования для определения проблемы.

Пустое окно Поиска решения

Заполненное окно Поиска решения

Оптимизировать целевую функцию

Это целевая ячейка, в которой мы пытаемся решить проблему. Наша целевая ячейка G11 – разница в группах.

До

Здесь мы указываем, каких результатов хотим добиться от целевой функции.

Мы хотим, чтобы суммы обоих групп совпадали, т.е. чтобы разница сумм была равна 0. Это может показаться странным, но нам не требуется минимизировать разницу, потому что при этом все элементы будут помещены в Группу A, что приведет к значению ячейки G11 меньше нуля.

Другой способ наложения ограничения – изменить G11 на =ABS(G10-F10). При этом мы сможем установить маркер на Минимум, как результат достижения целевой функции.

Но пока мы остановимся на формуле =G10-F10 и установим маркер в значение равным 0.

Изменяя ячейки переменных

Изменяемые ячейки – ячейки, которые надстройка попытается изменить, чтобы решить задачу. В нашем случае это привязка элемента к конкретной группе: $C$2:$D$9.

В соответствии с ограничениями

Ограничения – это правила, которые лимитируют возможные решения проблемы.

Нам необходимо добавить несколько ограничений в наш список:

  1. В колонке Итого каждый элемент должен равняться 1
  2. Элементы групп должны быть целым числом
  3. Сумма значений столбца Итого должна равняться 8

Чтобы наложить ограничения, жмем кнопку Добавить

  1. Для каждой ячейки диапазона E2:E9 устанавливаем ограничение значения равным 1
  2. Для каждой ячейки диапазона C2:D9 устанавливаем ограничение значение целое число.
  3. Необходимо добавить ограничение на сумму обоих групп, ячейка E10 = 8.

Вы можете Изменить или Удалить ограничение, если допустили ошибку, выбрав конкретное ограничение и нажав соответствующие кнопки в диалоговом окне.

Загрузить/сохранить параметры поиска решений

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

Запуск поиска оптимального решения в Excel

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

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

Два параметра, которые необходимо будет менять время от времени:

Точность ограничения: значение от 0 до 1, где, чем больше цифра, тем больше ограничение

Целочисленная оптимальность: показывает насколько далеко от целого числа ограничение имеет право быть.

Запуск модели

Чтобы запустить надстройку нажмите кнопку Найти решение в основном окне.

В строке состояния вы увидите ряд статических данных, которые будут отображать внутреннюю работу надстройки. Как правило, они быстро меняются, и читать их сложно. Если модель сложная, то работа может остановится на некоторое время, надстройка обычно восстанавливается от этих проблем сама.

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

Теперь у вас есть 4 варианта на выбор:

— Запустить отчет

— Сохранить сценарий

— Восстановить исходные значения

— Сохранить найденное решение

Запустить отчет

Вы можете создать отчет, выбрав доступные из списка отчетов. Будет создан новый лист Отчет о результатах1.

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

Сохранить сценарий

Если вы нажмете кнопку Сохранить сценарий, Excel откроет следующее диалоговое окно:

Где необходимо ввести название вашего сценария модели и нажать кнопку ОК.

Все сценарии доступны в Диспетчере сценариев, который находится во вкладке Данные в группе Работа с данными –> Анализ что-если -> Диспетчер сценариев.

Вернуться к модели

К тому же, вы можете вернуться к модели и:

— Восстановить исходные значения

— Сохранить найденное решение

Проверка результатов

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

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

— Являются ли результаты примерно похожими на ваши ожидания?

— Не нарушены ли максимумы и минимумы?

УДК 519.87

Вестник СПбГУ. Сер. 1. Т. 3(61). 2016. Вып. 4

ИСПОЛЬЗОВАНИЕ ТРОПИЧЕСКОЙ ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ МИНИМАКСНЫХ ЗАДАЧ РАЗМЕЩЕНИЯ С ПРЯМОУГОЛЬНОЙ МЕТРИКОЙ НА ПРЯМОЙ*

Н. К. Кривулин, П. В. Плотников

Санкт-Петербургский государственный университет,

Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7—9

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

Ключевые слова: тропическая оптимизация, идемпотентное полуполе, прямоугольная метрика, задача Ролса о размещении с ограничениями.

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

Методы тропической оптимизации успешно применяются для решения ряда задач размещения , включая минимаксную задачу размещения одиночного объекта на плоскости с прямоугольной метрикой. Указанная задача, которую также называют задачей Ролса или задачей посыльного, имеет при отсутствии ограничений на допустимую область размещения известное геометрическое решение . На основе представления в виде задачи тропической оптимизации в работах было дано алгебраическое решение этой задачи, полученное в явном виде в замкнутой форме.

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

* Работа выполнена при финансовой поддержке РГНФ в рамках научного проекта №16-02-00059.

(¡5 Санкт-Петербургский государственный университет, 2016

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

Операция возведения в степень с целым показателем вводится стандартным образом. Для любого ненулевого числа x G Ж и натурального числа n определим x0 = 1, xn = x ( xn-1, x-n = (x-1 )n и 0n = 0. Будем предполагать, что операция возведения в целую степень ненулевого числа x может быть распространена на случай произвольного показателя степени. В частности, для любого x < 1 при n = 0 положим x1/n = 0.

Далее знак умножения ( в алгебраических выражениях, как обычно, опускается.

В силу того, что сложение идемпотентно, можно определить отношение частичного порядка < так: x < у тогда и только тогда, когда xфy = у. Из этого определения следует пара неравенств x < x ф у и у < x ф у, а также равносильность неравенства x ф у < z и системы неравенств x < z и у < z для любых x,y,z G Ж. Кроме того, нетрудно проверить свойства монотонности операций сложения и умножения, по которым при условии x < у для любого z выполняются неравенства x ф z < у ф z и xz < yz. Наконец, для любых x,у = 0 из неравенства x < у следует x-1 > у-1. В дальнейшем будем дополнительно предполагать, что введенный частичный порядок является линейным.

Примерами алгебраических структур рассмотренного типа являются идемпо-тентные полуполя вещественных чисел:

Rmax,+ = {R и {-то}, -то, 0, max, +}, Rmin,+ = {R U {+то}, +TO, 0, min, +},

Rmax,x = {R+ и {0}, 0,1, max, x}, Rmin,x = {R+ U {+то}, +то, 1, min, x},

где R — множество вещественных чисел и R+ = {x G R| x > 0}.

Нулевым элементом для полуполя Rmax,+ является -то, единичным — число 0. В этом полуполе любому числу x G R можно сопоставить обратный x-1, который совпадает с противоположным числом -x в обычной алгебре. Для любой пары чисел x,y G R можно определить степень xy, значение которой равно арифметическому произведению xy. Порядок, порожденный операцией идемпотентного сложения, совпадает с обычным линейным порядком на множестве R.

3. Задача тропической оптимизации с ограничениями. В этом разделе рассматривается задача тропической оптимизации, сформулированная в терминах общего идемпотентного полуполя, для которой находится аналитическое решение в явном виде. Сначала вводится параметр для обозначения минимума целевой функции, а затем задача сводится к решению параметризованной системы неравенств. Условия существования решений системы используются для определения величины

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

Пусть заданы числа a, b, c, d, f,g € X, а также вещественное число к. Требуется найти ненулевые решения t € X задачи

min atk-1 е bt-(k-1) е ct-(k+1) е dtk+1,

f < t < g. (1)

Следующий результат описывает все решения рассматриваемой задачи.

Теорема 1. Пусть a,b,c,d,f,g > 0 и к — вещественное число. Справедливы следующие утверждения:

1) если к < — 1, то минимум в задаче (1) равен

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

(Л = a1’2b1’2 е a(k+1)/2kc(k-1)/2k е b(k+1)/2kd(k-1)/2k е c1/2d1/2е

е agk-1 е bf-(k-1) е cf-(k+1) е dgk+1

и достигается тогда и только тогда, когда

t = (i(a-1)1/(k-1)е((d-1)1/(k+1)еf)1-a {i(b-1)1/(k-1)е(c-1)1/(k+1)еg-1)-;

2) если — 1 < к < 1, то минимум равен

( = a1’2b1’2 е a(k+1)/2d-(k-1)/2 е b(k+1)/2c-(k-1)/2 е c1l2d1l2е

е agk-1 е bf-(k-1) е cg-(k+1) е dfk+1

и достигается тогда и только тогда, когда

t = (i(a-1)1/(k-1)е((-1c)1/(k+1)е f)1-a {i(b-1)1/(k-1)е(-1d)1/(k+1)еg-1)-a;

3) если к > 1, то минимум равен

( = a1’2b1’2 е a(k+1)/2kc(k-1)/2k е b(k+1)/2kd(k-1)/2k е c1/2d1/2е

е afk-1 е bg-(k-1) е cg-(k+1) е dfk+1

и достигается тогда и только тогда, когда

t = (((-1b)1/(k-1)е((-1c)1/(k+1)е f)1-a {i(-1a)1/(k-1)е(-1d)1/(k+1)еg-1)-a;

где а —любое вещественное число, удовлетворяющее условию 0 < а < 1.

Доказательство. Обозначим минимум целевой функции в задаче (1) через Тогда все решения задачи определяются системой, состоящей из уравнения и неравенства:

агк-1 е ы-(к-1) е еь-(к+1) е dtk+1 = / < г < д.

В силу того, что л — минимальное значение целевой функции, равенство в системе можно заменить на неравенство, что приводит к системе

агк-1 е ьг-(к-1) е сг-(к+1) е ¿гк+1 < л, / < г < д.

Полученная система неравенств эквивалентна системе

агк-1 < ц, Ьг-(к-1) < ц, сЬ-(к+1) < ц, <Ик+1 < ц, / < г, г < д. (2)

Заметим, что перемножение соответствующих частей первых двух неравенств дает неравенство аЬ < ц2, откуда с учетом условия леммы следует ц > а1/2Ь1/2 > 0.

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

Записывая вместе оба неравенства для г, получим двойное неравенство

(¡а-1)1/(к-1) е ы-1)1/(к+1) е / < г < ь-1)1/(к-1) е (¡с-1)1/(к+1) е д-1) . (3)

((ла-1)1/(к-1) е ¡3-1 )1/(к+1) е /) ((лЬ-1)1/(к-1) е (¡с-1)1/(к+1) е д-1) < 1.

Раскроем скобки в левой части, а затем заменим полученное неравенство эквивалентной системой неравенств, включая /д-1 < 1, которое прямо следует из условия / < д. Решение остальных неравенств системы относительно ¡л дает

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Л > а1/2Ь1/2, л > а(к+1)/2кс(к-1)/2к, л > Ь(к+1)/2к3(к-1)/2к, л > с1/231/2, Л > адк-1, л > Ь/-(к-1), л > с/-(к+1), л > ¿дк+1.

Полученная система равносильна одному неравенству

л > а1/2Ь1/2 е а(к+1)/2кс(к-1)/2к е Ь(к+1)/2кз(к-1)/2к е с1/2з1/2е

е адк-1 е ь/-(к-1) е с/-(к+1) е 3дк+1.

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

Осталось представить неравенство (3) для t в параметрической форме

t = {i(a-1)1/(k-1) е ((d-1)1/(k+1) е f) 1-а (((b-1)1/(k-1) е (-1 )1/(k+1) е g-1)

где вещественный параметр а в показателе степени удовлетворяет условию 0 < а < 1.

Перейдем к исследованию задачи в случае, когда выполняется условие — 1 < к < 1.

В результате объединения полученных неравенств, к которым добавляются неравенства t > f и t-1 > g-1 , имеем двойное неравенство

((a-1)1/(k-1) е ((-1c)1/(k+1) е f < t < ((мb-1)1/(k-1) е (-1d)1/(k+1) е g-1)-1.

( = a1/2b1/2 е a(k+1)/2d-(k-1)/2 е b(k+1)/2c-(k-1)/2 е c1/2d1/2е

е agk-1 е bf-(k-1) е cg-(k+1) е dfk+1.

С помощью параметра а такого, что 0 < а < 1, множество решений t задачи записывается в виде

t = (((a-1)1/(k-1) е (p-1c)1/(k+1) е f) 1-a (((b-1)1/(k-1) е (ß-1d)1/(k+1) е g-1) -a.

Построение решения задачи для случая, когда к > 1, осуществляется таким же образом, как в случае к < —1, и здесь для краткости опускается. ■

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

Предположим, что заданы числа a,b,c, f,g € X и необходимо найти ненулевые значения неизвестного t € X, которые решают задачу

min at-2 е bt2 е c,

(4)

f < t < g.

Нетрудно видеть, что эта задача имеет форму задачи (1), в которой необходимо положить к = —1 и d = c. Тогда применение теоремы 1 дает следующее утверждение.

Следствие 1. Пусть a,b,c,f,g > С. Минимум в задаче (4) равен

ц = a1/2b1/2 © ag-2 © bf2 и достигается тогда и только тогда, когда

t = (^-1/2a1/2 © f) — (^-1/2b1/2 © g-1) -0 , 0 < а < 1. Теперь получим решение задачи, которая формулируется так:

min at-1 © bt, f < t < g.

(5)

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Следствие 2. Пусть a,b,f,g > С. Минимум в задаче (5) равен

р = a1/2b1/2 ® ag-1 © bf и достигается тогда и только тогда, когда

t = (р-1a ® f)1-a (р-1b ® g-1)-a , 0 < а < 1.

4. Приложения к задачам размещения на прямой. Рассмотрим минимаксную задачу размещения на плоскости с прямоугольной метрикой и ограничениями на допустимую область размещения. Предположим, что на множестве R2 задан набор точек и определено некоторое допустимое подмножество S С R2. Требуется разместить новую точку на множестве S так, чтобы минимизировать расстояние от этой точки до самой удаленной от нее из числа заданных точек.

Пусть на плоскости R2 имеются два вектора х = (х1 ,Х2)T и y = (У1,У2)т. Расстояние между этими векторами в прямоугольной метрике вычисляется по формуле

Р(х, У) = \Х1 — У1\ + \ХХ2 — У2 \.

Ф(х) = max (р(гг, х) + Wi) = max (\ти — Х1\ + \т2г — Х2 \ + Wi) = ф(хьх2),

которая определяет максимальное по всем i расстояние в прямоугольной метрике от точки х до точки vi с учетом дополнительного слагаемого wi.

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

mn ф(х). (6)

Для решения задачи при условии, что допустимое множество S задается на плоскости в виде отрезка прямой, применим разработанные выше методы. Для этого

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

Сначала запишем целевую функцию задачи (6) в терминах идемпотентного полуполя Rmax,+ . Учитывая, что с помощью операций этого полуполя прямоугольную метрику для векторов x = (x\,Х2)T и y = (yi,y2)t можно представить в форме

P(x, y) = (x-V © y-1xi)(x-1y2 © y-1×2),

целевая функция задачи принимает следующий вид:

, x2 ) = ф Wi (x-1rii © r—lxi )(x-1r2i © r-1 x2). (7)

i=1

Ниже решение задачи (6) будет получено для различных случаев расположения на плоскости прямой, на которой выполняется размещение.

4-1- Размещение на горизонтальной прямой. Предположим, что заданы числа f,g,q € R при условии f < g. Рассмотрим задачу размещения на отрезке горизонтальной прямой, для которой определим множество

S = {(x!,x2)t \f < x1 < g, x2 = q}. (8)

Для решения задачи в терминах полуполя RmaXj+ введем обозначения

а = 0 wir1i(q-1T2i © r-i1q), Ь = 0 wiт—1 (q-1T2i © r-lq). i=1 i=1

Запишем целевую функцию (7), используя введенные обозначения, в виде

ф^1 ,x2) = ф (Wiru(q-1r2i © r-^qYx-1 © Wir-1 (q-1r2i © qr-)x^ = ax-1 © bx1.

i=1

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Теперь рассматриваемая задача сводится к задаче (5), в которой t заменяется на x1. Применяя следствие 2, находим, что минимум в задаче (6) при условии (8) равен Л = а1/2Ь1/2 © ag-1 © bf и достигается тогда и только тогда, когда

x1 = (л-1а © f)1 а {¡-1Ь © g-1) а , x2 = q, 0 < а < 1. Представление решения в обычных обозначениях дает минимум задачи в виде

fa+b u.t

¡л = max I — , a- g,b+ /

который достигается тогда и только тогда, когда

x1 = (1 — a) max(—л + a, f) — аmax(-¡л + b, -g), x2 = q, где а удовлетворяет условию 0 < а < 1 и справедливы равенства a = max (wi + ru + r2i — q,Wi + Гц — r2i + q),

b = max (wi — rii + тц — q,Wi — ru — тц + q).

4.2. Размещение на прямой, наклоненной под углом 45°. Перейдем к решению задачи размещения на отрезке прямой, наклоненной к горизонтальной оси координат под углом 45°. Пусть заданы числа /, д,р€ К, где / < д. Тогда отрезок прямой можно определить при помощи параметра Ь в виде

Б = {(хЛ,х2)т \х1 = р + Ь, х2 = q + Ь, / < Ь < д}. (9)

Чтобы записать целевую функцию в компактном виде, введем обозначения

а = @ wip lq lrur2i, b = ф wipqru r2i1> c = ф wi(P 1qrur2i1 ® Pq lriir2i).

г=1 г=1 г=1

Записывая равенства х1 = р + Ь и = q + Ь в терминах тропических операций, будем иметь х1 = рЬ и х2 = qí. В результате подстановки в целевую функцию (7) с учетом введенных обозначений а, Ь и с получим

т

ф{хЛ,х2) = 0 Wi(p- 1тцЬ-1 © т-1 рЬ)(д-1 Т2гг-1 © т-дЬ) = аЬ-2 © ЬЬ2 ® с.

г=1

1-аг, ,-1/21,1/2 ^ -1ч-а

X! = p(^-1’2a1’2 )1-a^-1/2b1/2 ® g-1)-a,

а

X2 = q(^-1/2a1/2 ® f )1-a{^-1’2b1’2 ® g-1)-a, 0 < а < 1.

С использованием обычных обозначений полученный результат можно представить в следующей форме. Минимум в задаче равен

Л = max((a + b)/2, c,a- 2g, b + 2f)

и достигается тогда и только тогда, когда

x1 = (1 — а) max((a — ¡л)/2, f) — а max((b — л)/2, -g) + p, x2 = (1 — а) max((a — л)/2, f) — аmax((b — л)/2, -g) + q,

где а удовлетворяет условию 0 < а < 1 и справедливы равенства

a = max (wi + Гц + r2i — p — q), b = max (wi — ru — r2i + p + q),

Ikikm Ikikm

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

c = max (wi + Гц — T2i — p + q,wi — Гц + T2i + p — q).

Нетрудно видеть, что допустимое множество для задачи размещения на отрезке прямой, наклоненной под углом 135° к горизонтальной оси, может быть представлено

4.3. Размещение на произвольной прямой. Рассмотрим задачу размещения на отрезке произвольной прямой, который для фиксированных чисел /, д,д,к € К, где / < д, описывается при помощи множества

Б = {(х1 ,Х2)т \/ < х1 < д, Х2 = кх! + д}. (10)

Сначала также, как при решении предыдущих задач, введем обозначения

т т т т

а = @ шгиr-l1q, Ь = @ шг-^г2гЯ-1, с = @ ‘ш^ц^Я-1, ( = @ шг-^г-д.

1=1 г=1 г=1 г=1

Заменим равенство Х2 = кХ1 + д на эквивалентное ему равенство в терминах тропических операций в виде Х2 = дХк. После подстановки в целевую функцию (7) получим

т

-1— — г—1—

Ф(Х1 ,Х2) = ф тг(Х- 1 ги © г^х^ )(д 1Х1 к Г2г © г- дхк)

г=1

Л т Ьх-(к-1) т сх-(к+1) т 3хк+1

ЬХ -I сх (Х -I .

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

к

дает оптимальные значения для Х1, после чего остается вычислить Х2 = дхк.

В результате для задачи (6) при условии (10) оказываются справедливыми следующие утверждения:

1) если к < —1, то минимум в задаче равен

( = а1’2Ь1’2 © а(к+1)/2кс(к-1)/2к © Ь(к+1)/2к((к-1)/2к © с1/2(1/2©

© адк-1 © Ь/-(к-1) © с/-(к+1) © (дк+1

и достигается тогда и только тогда, когда

\ 1 — а

е (и(-1)1/(к+1) е п ®

Х1 = ((Ма-1)1/(к-1) © (((-1)1/(к+1) © /)

® (((Ь-1)1/(к-1) © ((с-1)1/(к+1) © д-1)

Х2 = д {(а-1 )1/(к-1) © ((-1)1/(к+1) © /)(1 а)к ®

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

® (((Ь-1)1/(к-1) © (с-1)1/(к+1) © д-1)

-ак

2) если —1 < к < 1, то минимум равен

( = а1’2Ь1’2 © а(к+1)/2сГ(к-1)/2 © Ь(к+1)/2с-(к-1)/2 © с1/2(1/2©

© адк-1 © Ь/-(к-1) © сд-(к+1) © /к+1

к

а

> 1 — а

-1)1/(к-1) ^ (л-1 с)1/(к+1)

х1 = ((ла-1)1/(к-1) © (Л-1 с)1/(к+1) © /) » ®

® ((лЬ-1)1/(к-1) © (л-1 ¿)1/(к+1) © д-1] х2 = д ((ла-1 )1/(к-1) © (л-1 с)1/(к+1) © /)(1-а)к ®

® ((лЬ-1)1/(к-1) © —Т> кТТ>f) — amax U^T’ FTT’ ~9) ) +q;

где а удовлетворяет условию 0 < a < 1 и справедливы равенства

a = max (w — Гц + r^i + q), b = max (wi + Гц — r^i — q),

ikikm ikikm

с = max (wi + Гц + r^i — q), d = max (wi — Гц — r^i + q).

ikikm ikikm

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

Литература

3. Маслов В. П., Колокольцов В. Н. Идемпотентный анализ и его применение в оптимальном управлении. М.: Физматлит, 1994. 144 с.

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

14. Elzinga J., Hearn D. W. Geometrical solutions for some minimax location problems // Transport. Sci. 1972. Vol. 6, N 4. P. 379-394.

16. Krivulin N. Algebraic solutions of tropical optimization problems // Lobachevskii J. Math. 2015. Vol. 36, N 4. P. 363-374.

Статья поступила в редакцию 4 мая 2016 г. Сведения об авторах

Кривулин Николай Кимович —доктор физико-математических наук, доцент; nkk@math.spbu.ru Плотников Павел Владимирович — аспирант; pavplot@gmail.com

USING TROPICAL OPTIMIZATION TO SOLVE MINIMAX LOCATION PROBLEMS WITH RECTILINEAR METRIC ON THE LINE

Nikolai K. Krivulin, Pavel V. Plotnikov

Keywords: tropical optimization, idempotent semifield, rectilinear metric, Rawls location problem with constraints.

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

14. Elzinga J., Hearn D. W., «Geometrical solutions for some minimax location problems», Transport. Sci. 6(4), 379-394 (1972).

16. Krivulin N., «Algebraic solutions of tropical optimization problems», Lobachevskii J. Math. 36(4), 363-374 (2015).

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *