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

Лабораторная работа №16

Решение задач линейного программирования

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

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

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

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

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

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

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

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

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

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

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

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

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

L = 5x₁ - 2x₃ min
- 5x₁ - x₂ + 2x₃ ≤ 2
- x ₁+x₃ + x₄ ≤ 5
- 3x₁ + 5x₄ ≤ 7

Пусть значения x₁, x₂, x₃, x₄ хранятся в ячейках 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: Сервис / Поиск решения.

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

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

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

Рис. 6.1

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

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

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

Рис. 6.2

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

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

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

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

Рис. 6.3

 

Рис. 6.4

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

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

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

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

В Open Office Calc: