Решение задач линейного программирования с помощью надстройки «Поиск решения» в Microsoft Excel , страница 5
Структура сценария вставляется в виде отдельного листа непосредственно перед активным листом. Если отчеты по сценарию создавались несколько раз, названия листов автоматически нумеруются («Структура сценария 1», «Структура сценария 2» и т.д.).
Рисунок 37 – Диалоговое окно «Диспетчер сценариев»
Полученное решение также может быть сохранено в виде сценария. Таким образом, можно запомнить результаты решения задачи для различных вариантов исходных данных, провести вариантный анализ.
Рисунок 38 – Диалоговое окно «Отчет по сценарию»
После сохранения сценария продолжается работа в том же окне, из которого это сохранение осуществлялось («Текущее состояние поиска решения» или «Результаты поиска решения»).
С помощью соответствующих кнопок в «Диспетчере сценариев» сохраненные сценарии можно изменять и удалять; можно добавлять новые (при этом необходимо указать изменяемые ячейки, и их значения, которые необходимо запомнить); объединять список сценариев со сценариями, находящимися на другом листе; выводить сохраненные значения изменяемых ячеек на рабочий лист (в те же ячейки).
6.5 Результаты решения задачи
После окончания работы «Поиска решения» оптимальный план и оптимум, если они получены, находятся в тех ячейках, которые были выбраны в качестве влияющих и целевой.
В рассмотренном примере (см. таблицу 26, раздел 6.2) после нажатия кнопки «Выполнить» в ячейке В6 появится число 266,7 (х1 = 266,7), в С6 – 1173,3 (х2 = 1173,3), а в В11 – 193066,7 (оптимальное значение прибыли).
Кроме того, выводится диалоговое окно «Результаты поиска решения», представленное на рисунке 39.
Рисунок 39 — Диалоговое окно «Результаты поиска решения»
С помощью переключателей в этом окне по желанию пользователя найденное решение может быть сохранено в соответствующих ячейках, либо в них восстанавливаются исходные значения (в примере из раздела 6.2 – нулевые). По умолчанию при нажатии кнопки «ОК» решение сохраняется, а если закрыть окно или воспользоваться «Отменой», будут восстановлены исходные значения.
Поле «Тип отчета» служит для того, чтобы пользователь мог получить отчеты о решении задачи (см. раздел 6.6). Для этого необходимые типы отчетов надо выделить до нажатия кнопки «ОК». Каждый отчет размещается на отдельном листе книги Microsoft Excel (как и «Структура сценария»). Эти листы программа также вставляет непосредственно перед активным листом. Если «Поиск решения» использовался несколько раз, и при этом создавались отчеты, названия отчетов автоматически нумеруются. Если решение не было найдено, обратиться к «Типу отчета» невозможно. Кроме того, для целочисленных задач не выдаются отчеты по устойчивости и пределам.
Нажатием кнопки «Сохранить сценарий» полученное решение может быть сохранено в виде сценария.
Первые строки окна результатов занимает итоговое сообщение, которое может быть различным по содержанию. При успешном окончании процедуры поиска решения для линейной модели выдается сообщение: «Решение найдено. Все ограничения и условия оптимальности выполнены» (см. рисунок 38). Если поиск не получил оптимального решения, выдается одно из сообщений, приведенных в таблице 28.
Таблица 28 – Итоговые сообщения «Поиска решения»
Характеристика результата поиска
(для линейной задачи)
Поиск остановлен (истекло заданное на поиск время).
Время, отпущенное на решение задачи, исчерпано, но достичь удовлетворительного решения не удалось.
Следует увеличить максимальное время.
Поиск остановлен (достигнуто максимальное число итераций).
Произведено разрешенное число итераций, но достичь удовлетворительного решения не удалось.
Следует увеличить предельное число итераций.
Значения целевой ячейки не сходятся.
Целевая функция задачи не ограничена.
Если необходимо поставить задачу так, чтобы она была разрешима, следует изменить и/или добавить ограничения и запустить задачу снова. Возможно (исходя из смысла задачи), ошибка допущена и при построении целевой функции.
Поиск остановлен по требованию пользователя.
Нажата кнопка “Стоп” в окне диалога «Текущее состояние поиска решения» после прерывания поиска решения или в процессе пошагового выполнения итераций (которое устанавливается через «Параметры» «Поиска решения»).
Поиск решения MS EXCEL. Каноническая задача линейного программирования
Стандартная задача линейного программирования (ограничения на переменные выражены неравенствами) решена нами с помощью Поиска решения в предыдущей статье. Пример записи ограничений в такой задаче приведен ниже:
Как видно из картинки выше в задаче задано 3 ограничения (неравенства). Есть еще 4 ограничения (по числу переменных) — все переменные должны больше 0.
Примечание: В стандартной задаче все переменные больше 0. На то она и стандартная.
В этой статье сведем стандартную задачу к каноническому виду и решим ее с помощью Поиска решения (Solver) в MS EXCEL.
Дадим определение.
Канонической называется задача линейного программирования, которая состоит в нахождении максимального или минимального значения целевой функции при условии, что все ограничения являются равенствами.
Примечание: Каноническая форма необходима для решения задачи симплекс методом (SIMPLEX LP).
Теперь задача.
Примечание: Ограничения задачи заданы выше.
Для приведения задачи к канонической форме введем дополнительные (свободные) переменные (т.е. произведем эквивалентные преобразования). Так как у нас три ограничения, то и дополнительных переменных должно быть 3. Введение этих переменных позволяет избавиться от неравенств в ограничениях и заменить их на равенства.
Совет: для знакомства с Поиском решения см. эту статью.
Решение
Сначала на лист EXCEL поместим все коэффициенты из 3-х неравенств (3х4) и добавим еще коэффициенты для 3-х свободных переменных (в форме единичной матрицы 3х3).
Также нужно заполнить столбец свободных членов (правая часть неравенств, синие ячейки).
Теперь определим ячейки для хранения значений переменных х, выделим их зеленым цветом и расположим их в одном столбце (а не в строке). Значения этих ячеек Поиск решения будет изменять, чтобы максимизировать функцию F.
Напомним, что в задаче 4 переменных (x1, x2, x3, x4) и 3 дополнительных переменных (x5, x6, x7), необходимых для сведения задачи к каноническому виду, поэтому нам потребовалось 7 ячеек.
Теперь вычислим значения левых частей наших 3-х ограничений, то есть умножим коэффициенты Матрицы А на столбец переменных (Матрица Х, или просто столбец с переменными). Это можно сделать с помощью формулы = МУМНОЖ(B21:H23;B28:B34) , т.е. использовав умножение матриц. Формулу нужно вводить как формулу массива, возвращающим сразу несколько значений.
Примечание. Альтернативным и интуитивно более понятным подходом является использование формулы = СУММПРОИЗВ(B21:H21;ТРАНСП($B$28:$B$34)) Это реализовано в файле примера . Формулу тоже нужно ввести как формулу массива, т.к. СУММПРОИЗВ() работает с массивами (векторами), которые оба размещены по строкам или по столбцам. В нашем случае это не так: коэффициенты размещены в одной строке, а значения х в столбце, поэтому использована функция ТРАНСП() для транспонирования столбца с переменными. Можно, конечно, предварительно транспонировать столбец в строку, в этом случае функцию СУММПРОИЗВ() можно вводить как обычную формулу.
Итак, у нас полностью сформировалось 3 ограничения: левая часть выражения (элементы Матрицы В) и правая часть (дано). Выделим эти ячейки синим цветом, чтобы было удобнее вводить условия в окно Поиска решения. Т.к. мы ввели дополнительные переменные, то ограничения теперь заданы в виде равенств — это канонический вид.
Осталось задать целевую функцию, умножив коэффициенты на ячейки с переменными (дополнительные переменные использовать не нужно). Это проще всего сделать формулой = СУММПРОИЗВ(B40:B43;B28:B31)
В окне Поиска решения задайте параметры оптимизации.
Совет: О том как установить Поиск решения см. эту статью.
Поиск решения сам предложил решить задачу Симплекс-методом, а также сделать переменные неотрицательными.
После запуска Поиска решения решение будет найдено и оно, конечно, совпадет с решением задачи, которая была решена в стандартной форме.
Методические указания по содержанию и организации выполнения курсовой работы по дисциплине «Маркетинг» для студентов всех форм обучения специальности 060800 Экономика и управление на предприятии
Для целевой функции (ЦФ): курсор в G5; активизировать Мастер функций; в Категории вызвать Математические; в Функциях найти и вызвать СУММПРОИЗВ. Далее. После этого должно появиться новое диалоговое окно: в 1-е окно (массив 1) ввести адреса ячеек оптимальных переменных (А, Б, В, Г, Д) — B$2:F$2; во 2-е окно (массив 2) ввести адреса ячеек целевой функции – B5:F5. Знак $ описывает переменную величину. Готово. В результате в ячейке G5 (результат расчета целевой функции) должна появиться следующая формула: =СУММАПРОИЗВ(B$2:F$2;B5:F5)
Для левых частей ограничений: курсор в G5; Копировать в буфер; курсор в G8; Вставить из буфера. На экране в ячейке G8 должна появиться следующая формула: =СУММАПРОИЗВ(B$2:F$2;B8:F8)
Чтобы ввести расчетные формулы (аналогичные той, что введена в ячейку G8) для других ресурсов достаточно произвести Копирование содержимого ячейки G8 в соответствующие адреса G9, G10, G12, G13, G14, G15, G17, G18, G19, G20.
в) Поиск решения
Для нахождения оптимального решения необходимо в МЕНЮ Excel Сервис вызвать Поиск решения. На экране монитора появится окно — Поиск решения. Ввести адрес в окно Поиск решения ($G$5). После этого задать направление поиска — Максимальное значение. Ввести адреса искомых переменных $B$2:$F$2 в окне Изменяя ячейки. Остается ввести граничные условия на переменные и на ограничения. Активизировать в этом окне клавишу Добавить. Появится новое окно Добавление ограничений.
Ввести граничные условия на переменные (B2=B3, C2=>C3, D2 E3, E2 F3). Для этого в окне Ссылка на ячейку ввести $B$2, затем указать тип ограничения = и ввести $B$3. Добавить. Аналогично вводятся остальные граничные условия: $C$2=>$C$3, $D$2 $E3$, $F$2=>$F$3.