Решение задач линейного программирования с помощью надстройки «Поиск решения» в Microsoft Excel

6 Решение задач линейного программирования с помощью надстройки «Поиск решения» в Microsoft Excel 106

6.1 Работа с диалоговыми окнами «Поиск решения» и «Добавление ограничения». 106

6.2 Пример постановки задачи для «Поиска решения». 108

6.3 Параметры «Поиска решения». 111

6.4 Сценарии «Поиска решения». 114

6.5 Результаты решения задачи. 116

6.6 Типы отчетов. 119

6.6.1 Отчет по результатам.. 119

6.6.2 Отчет по устойчивости. 120

6.6.3 Отчет по пределам.. 124

6.7 Пример задачи с множественным решением.. 125

6.8 Пример задачи с ненулевым значением дополнительной двойственной переменной. 127

6.9 Вопросы и упражнения. 129

6 Решение задач линейного программирования с помощью надстройки «Поиск решения» в Microsoft Excel

«Поиск решения» предназначен для решения задач математического программирования. Если задача разрешима, то в общем случае будет найдено приближенное решение. Для линейной задачи, если она разрешима, всегда можно получить точное решение с использованием симплекс-метода. Для линейных задач с целочисленными переменными «Поиск решения» также использует метод ветвей и границ в сочетании с симплекс-методом [2].

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

6.1 Работа с диалоговыми окнами «Поиск решения» и «Добавление ограничения»

Диалоговое окно «Поиска решения» представлено на рисунке 28.

Рисунок 28 - Диалоговое окно «Поиск решения»

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

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

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

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

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

При первоначальной постановке задачи здесь доступна только кнопка «Добавить». При попытке нажать кнопки «Изменить» или «Удалить» будут выданы соответствующие сообщения об ошибках (отсутствии ограничений). Нажатием на кнопку «Добавить» вызывается диалоговое окно «Добавление ограничения», представленное на рисунке 29.

Рисунок 29 - Диалоговое окно «Добавление ограничения»

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

По умолчанию предполагается, что задача приведена к стандартной форме, т.е. если она ставится на максимум, то в ограничениях предлагается использовать знак «>=», а если на минимум, то «<=». При постановке задачи в смешанной форме эти знаки следует изменить.

Таблица 25 – Операторы, доступные при задании ограничений

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