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

Решение задач линейного программирования с помощью надстройки «Поиск решения» в Microsoft Excel «Поиск решения» предназначен для решения задач математического программирования. Если задача разрешима, то в общем случае будет найдено приближенное решение. Для линейной задачи, если она разрешима, всегда можно получить точное решение с использованием симплекс-метода. Для линейных задач с целочисленными переменными «Поиск решения» также использует метод ветвей и границ в сочетании с симплекс-методом. Надстройка «Поиск решения» находится на вкладке «Данные». Если она отсутствует, следует подключить ее через «Надстройки» MSExcel. Работа с диалоговыми окнами «Поиск решения» и «Добавление ограничения» Вид диалоговых окон «Поиска решения» может несколько различаться в разных версиях электронной таблицы, но ключевые элементы остаются примерно одинаковыми. Пример диалогового окна «Поиска решения» представлен на рисунке ниже. В поле «Оптимизировать целевую функцию» указывают адрес ячейки электронной таблицы, в которой находится соответствующая формула, содержащая ссылки на изменяемые ячейки (ячейки, в которых будут находиться значения переменных). По умолчанию в этом поле находится адрес той ячейки, в которой стоял курсор в момент обращения к «Поиску». Ниже с помощью переключателя можно выбрать направление экстремизации, т.е. определить, будет задача решаться на максимум или на минимум. Если установить целевую функцию равной некоторому фиксированному значению, то «Поиск решения» дает возможность решить систему уравнений и неравенств. По умолчанию задача решается на максимум. В поле «Изменяя ячейки переменных» указывается одна или диапазон изменяемых ячеек (переменных). Их еще называют влияющими ячейками. Они должны быть расположены на активном листе таблицы. При решении линейных задач во влияющих ячейках можно устанавливать любые исходные значения, но только числовые. Перечисленные действия (установление целевой функции, содержащей формулу, и влияющих ячеек) являются обязательными и, вообще говоря, достаточными для использования «Поиска решения». Кроме того, задача, решаемая с помощью «Поиска решения», обычно содержит систему ограничений, которые вводятся ниже. Нажатием на кнопку «Добавить» вызывается диалоговое окно «Добавление ограничения», представленное на рисунке ниже. Центральную часть этого окна занимает поле с раскрывающимся списком, в котором перечислены операторы, доступные при задании ограничений. Они приведены в таблице ниже. Слева и справа от поля со списком этих операторов расположены поля, в которых указываются соответственно левая и правая части ограничений. При этом в левой части обязательно должна находиться ссылка на ячейку или диапазон ячеек. В правой части могут находиться ссылка на ячейку или диапазон, число или формула. Если в обеих частях введены диапазоны, число ячеек в них должно совпадать, чтобы они сравнивались попарно. При выборе последних трех операторов в правой части окна появляются соответственно слова «целое», «бинарное», или «все разные», и она становится недоступной. После того, как ограничение введено, нажатием кнопки «ОК» можно вернуться в диалоговое окно «Поиск решения», после чего в окне «Ограничения» будет стоять введенное выражение. Однако если необходимо ввести другие ограничения системы, можно сразу же воспользоваться кнопкой «Добавить», не нажимая перед этим «ОК». Введенные ограничения можно изменять и удалять с помощью соответствующих кнопок. Как следует из изложенного, перед тем, как обратиться к «Поиску решения», следует осуществить некоторые подготовительные действия в электронной таблице, как минимум, ввести формулу для целевой функции. После обращения к этой надстройке формулы в ячейки таблицы ввести уже не удастся, пока она не будет закрыта. Нажатием кнопки «Сбросить» можно очистить содержание «Поиска решения». Чтобы начать решение задачи, следует нажать кнопку «Найти решение». Ввод исходных данных, который необходимо провести до обращения к «Поиску», рассмотрим на примере задачи о кондитерской фабрике. Пример постановки задачи для «Поиска решения» Решим задачу производственного планирования (о кондитерской фабрике) с помощью «Поиска решения». Подготовить исходные данные задачи для обращения к «Поиску» можно различными способами. Ниже приводится один из них. Для этого необходимо, во-первых, решить, где именно на листе электронной таблицы будут находиться переменные задачи. Отведем для них, например, ячейки В6 (для x1) и С6 (для х2). Вначале можно оставить эти ячейки пустыми, а можно ввести в них какое-нибудь число (на всякий случай, чтобы быть уверенными, что в них нет невидимого текста). Например, введем в них 0. Слева от этого диапазона – в А6 – введем текст «Производство карамели». Сверху в В5 введем текст ««Снежинка», т», и в С5 – ««Яблочная, т». Результат приведен в таблице 26. Это делается для того, чтобы переменные получили правильные названия. «Поиск решения» впоследствии составит имя ячейки из двух частей - из содержания ближайших к данной ячейке слева и сверху ячеек, содержание которых начинается с текстового символа (воспринимаемых Excel как текст). Если таких ячеек нет, имя ячейки может отсутствовать или состоять из одной части. Таким образом, переменная x1 получит имя «Производство карамели «Снежинка», т», а переменная x2 - «Производство карамели «Яблочная», т». Затем подготовим ограничения. Для удобства ввода формул, запишем в диапазоне В1:С4 коэффициенты в левых частях ограничений и в целевой функции. Затем в ячейку В8 введем формулу =СУММПРОИЗВ(B1:C1;B$6:C$6). Поскольку в ячейках B1:C1 находятся числа 0,8 и 0,5, а в B6:C6 – переменные, то в результате в ячейке В8 будет находиться левая часть первого ограничения, т.е. (0,8х1 + 0,5х2). Ссылки на строку изменяемых ячеек сделаны абсолютными (со знаком «$») для того, чтобы удобно было ввести остальные формулы. А именно, скопируем формулу в В8 на ячейки B9:В11. В результате копирования на ячейки с переменными (B6:C6) будут поочередно умножаться коэффициенты второго, третьего ограничения и целевой функции. Например, в В11 появится формула =СУММПРОИЗВ(B4:C4;B$6:C$6), т.е. (108х1 + 140х2). Разумеется, при нулевых значениях переменных результатом вычислений по всем этим формулам будет 0. Если в B6:C6 находятся другие значения, не нулевые, то и результат вычислений будет другим. Затем расположим введенные формулы в одну строку (для удобства оформления). Для этого формулу в В9 перенесем в С8, а формулу в В10 – в D8*. Ячейки В9 и В10 в результате переноса останутся пустыми. Теперь формулы для левых частей ограничений находятся в диапазоне В8:D8. Чтобы ограничения получили правильные имена, слева от этого диапазона (в А8) введем текст «Расход»; а сверху в В7 – «сахарного песка, т», в С7 – «патоки, т», в D7 – «фруктового пюре, т». В ячейки В9:D9 введем свободные члены ограничений – 800, 600 и 120. В ячейке В11 осталась формула для целевой функции. Этой ячейке тоже надо дать имя. Для этого в А11 введем текст «Прибыль от производства», а в В10 – «карамели, ден.ед.». Подготовленные данные представлены в таблице ниже. А B C D 1 Коэффициенты 0,8 0,5 2 0,2 0,4 3 0,01 0,1 4 108 140 5 «Снежинка», т «Яблочная», т 6 Производство карамели 7 сахарного песка, т патоки, т фруктового пюре, т 8 Расход 9 800 600 120 10 карамели, ден.ед. 11 Прибыль от производства В диалоговое окно «Поиска» данные здесь следует ввести так, как показано на рисунке ниже: Можно вводить ограничения и по отдельности. Тогда вид поля «Ограничения» будет другим (представлен на рисунке ниже). В случае, когда знаки в ограничениях разные, ограничения никогда не удастся ввести в одну строчку. Однако, если они одинаковые, то лучше пользоваться вариантом, когда их вводят одновременно. Флажок «Сделать переменные без ограничений неотрицательными» используется в том распространенном случае, когда переменные задачи не могут быть отрицательными (как в рассматриваемом примере). Этот флажок также должен быть установлен. Во многих задачах производственного планирования, если он не установлен, программа предлагает произвести отрицательное количество какой-либо продукции, «сэкономить» за счет этого ресурсы, и выпустить значительное количество более дорогой продукции. В поле «Выберите метод решения» надо установить «Поиск решения линейных задач симплекс-методом». Это делается для ускорения поиска решения линейной задачи оптимизации. Допустимо, но по ряду причин нежелательно решение линейной задачи как частного случая нелинейной, т.е. не устанавливая этот флажок. Для получения полного отчета о решении обязательно надо использовать симплекс-метод. Кнопка «Загрузить/сохранить модель» предусмотрена для хранения на листе более одной модели оптимизации, так как одна модель сохраняется автоматически. Способ использования этой кнопки студентам предлагается изучить самостоятельно. Результаты решения задачи После окончания работы «Поиска решения» оптимальный план и оптимум, если они получены, находятся в тех ячейках, которые были выбраны в качестве влияющих и целевой. В рассмотренном примере после нажатия кнопки «Найти решение» в ячейке В6 появится число 266,7 (х1 = 266,7), в С6 – 1173,3 (х2 = 1173,3), а в В11 – 193066,7 (оптимальное значение прибыли). Кроме того, выводится диалоговое окно «Результаты поиска решения», представленное на рисунке ниже: С помощью переключателей в этом окне по желанию пользователя найденное решение может быть сохранено в соответствующих ячейках, либо в них восстанавливаются исходные значения (в нашем примере – нулевые). По умолчанию при нажатии кнопки «ОК» решение сохраняется, а если закрыть окно или воспользоваться «Отменой», будут восстановлены исходные значения. Поле «Отчеты» служит для того, чтобы пользователь мог получить отчеты о решении задачи, которые будут подробно изучены на лабораторном практикуме. Для этого необходимые типы отчетов надо выделить до нажатия кнопки «ОК». Каждый отчет размещается на отдельном листе книги Microsoft Excel. Эти листы программа также вставляет непосредственно перед активным листом. Если «Поиск решения» использовался несколько раз, и при этом создавались отчеты, названия отчетов автоматически нумеруются. Если решение не было найдено, обратиться к «Типу отчета» невозможно. Кроме того, для целочисленных задач не выдаются отчеты по устойчивости и пределам. Кроме того, в окне результатов выводится итоговое сообщение (наверху – краткое, внизу – подробное), которое может быть различным по содержанию. При успешном окончании процедуры поиска решения для линейной модели выдается сообщение: «Решение найдено. Все ограничения и условия оптимальности выполнены». Если поиск не получил оптимального решения, выдается сообщение о причинах такой ситуации. Наиболее важные из них приведены в таблице ниже: Итоговое сообщение Характеристика результата поиска Рекомендуемые действия (для линейной задачи) Значения целевой ячейки не сходятся. Целевая функция задачи не ограничена. Если необходимо поставить задачу так, чтобы она была разрешима, следует изменить и/или добавить ограничения и запустить задачу снова. Возможно (исходя из смысла задачи), ошибка допущена и при построении целевой функции. Поиск не может найти подходящего решения. В процессе поиска решения нельзя сделать итерацию, которая удовлетворяла бы всем ограничениям (ОДП задачи пуста)*. Если необходимо поставить задачу так, чтобы она была разрешима, следует исключить противоречия в ограничениях. Возможно, следует в задаче снять одно ограничение или сразу несколько. Условия для линейной модели не удовлетворяются. Установлен флажок “Линейная модель”, однако итоговый пересчет порождает такие значения, которые не согласуются с линейной моделью (попытка решить нелинейную задачу, как линейную). Следует исправить ошибки в исходных данных, чтобы задача стала линейной. При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения. При пересчете значений ячеек обнаружена ошибка в одной формуле или в нескольких сразу. Следует найти целевую ячейку или ячейку ограничения, порождающие ошибку, и изменить формулы в них так, чтобы они возвращали подходящее числовое значение. Сохраните построенный отчет, так как он понадобится на последующих занятиях.