Решение задач линейного программирования.
Для решения задач линейного программирования в Excel имеется надстройка Поиск решения. Эта надстройка вызывается из меню Сервис. Если ее там нет, то необходимо в окне Надстройки, появляющемся после выполнения команд Рассмотрим использование данной надстройки для решения задач линейного программирования на примере решения следующей задачи.
Постановка задачи Предприятие изготавливает и реализует два вида продукции – P1 и P2. Для производства продукции используются два вида ресурсов – сырье и труд. Максимальные запасы этих ресурсов в сутки составляют 14 и 26 единиц соответственно. Расход ресурсов на изготовление каждого вида продукции, запасы и оптовые цены продукции приведены в таблице.
Известно, что суточный спрос на продукцию P1, никогда не превышает спроса на продукцию P2 более чем на 5 ед., а спрос на продукцию P2 никогда не превышает 4 ед. в сутки. Как спланировать выпуск продукции предприятия, чтобы доход от ее реализации был максимальным?
Математическая модель задачи
Математическая модель этой задачи имеет следующий вид. Максимизировать целевую функцию
при следующих ограничениях:
Нулевые и единичные коэффициенты явно указаны в формулах ограничений для удобства ввода формул в Excel.
Решение задачи
Для решения этой задачи с помощью табличного процессора необходимы следующие действия. 1. Создать в Excel таблицу вида:
В затененных областях необходимо будет ввести формулы для целевой функции и линейных ограничений. Значения переменных опорного плана (Количество) для P1 и P2 могут быть заданы вручную, что позволит ускорить процесс поиска решения. Если значения опорного плана не заданы, то программа определяет их автоматически.
2. В ячейке B9 для вычисления значения целевой функции ввести формулу “=СУММПРОИЗВ(B8:C8;$B$7:$C$7)”, которая находит сумму попарных произведений ячеек с ценами (B8:C8) на ячейки со значениями искомых параметров ($B$7:$C$7). Координаты ячеек с количественными значениями параметров P1 и P2 преобразуются к абсолютному виду для удобства дальнейшего копирования формулы в ячейки с ограничениями. Для такого преобразования необходимо при наборе формулы после выделения нужного диапазона ячеек в таблице (B7:C7) нажать клафишу <F4>.
3. Для задания ограничений по ресурсу Сырье в ячейку D3 скопировать формулу из ячейки B9, заменив диапазон цен (B8:C8) на диапазон параметров расхода сырья (B3:C3). В результате в ячейке D3 получится формула “=СУММПРОИЗВ(B3:C3;$B$7:$C$7)”. Для задания остальных ограничений скопировать вновь введенную формулу в ячейки D4, D5 и D6.
4. После создания таблицы с исходными данными установить курсор в ячейку с формулой целевой функции B9 и выбрать в меню Сервис функцию Поиск решения. Затем заполнить поля в появившемся окне
· в поле Установить целевую ячейку должен появиться адрес ячейки с формулой целевой функции (в данном случае $B$9); · установить переключатель вида оптимизации в поле Равной в положение максимальное (минимальное) значение при необходимости найти максимум или минимум целевой функции, либо установить точное значение целевой функции; · в поле Изменяя ячейки указать диапазон ячеек со значениями параметров задачи, выделив его в таблице. В данном примере это ячейки ($B$7:$C$7); · в поле Ограничения задать вид и значения ограничений. Для этого установить курсор в поле ввода ограничений и нажать кнопку Добавить. После чего в появившемся окне Добавление ограничения ввести в поле Ссылка на ячейку адрес ячейки с формулой соответствующего ограничения (например, D3 для ресурса Сырье). Затем ввести в поле Ограничение предельное значение соответствующего запаса (для ресурса Сырье оно находится в ячейке F3) и выбрать вид отношения (<, >, = и т.п.).
После нажатия кнопки Добавить (или OK для ввода последнего значения) данное ограничение попадает в список ограничений задачи. С помощью кнопок Удалить и Изменить можно удалять выделенные в списке ограничения или вносить в них исправления.
5. После заполнения всех полей окна нажать кнопку Параметры и в открывшемся окне Параметры поиска решения установить флажки Линейная модель для решения задачи линейного программирования и Неотрицательные значения, если такие ограничения накладываются на все переменные задачи. В этом окне можно так же определить параметры процесса решения: предельное время поиска решения, максимальное количество итераций, точность и т.п. Флажок Показывать результаты итераций позволяет по шагам следить за поиском решения. Флажок Автоматическое масштабирование включается в том случае, когда разброс значений параметров очень велик.
6. Задав все параметры, нажать кнопку Выполнить для поиска решения задачи. Если решение найдено, то появляется окно с соответствующим сообщением.
Результаты решения могут быть сохранены в файле задачи в виде сценария или добавлены в виде отдельных листов Отчет по результатам, Отчет по устойчивости и Отчет по пределам. Для сохранения результатов в виде листов необходимо предварительно в поле Тип отчета выделить требуемые типы отчетов. В этом же окне можно отказаться от полученных решений и восстановить исходные значения переменных.
Отчет по результатам приведен в табл. 1. В данном отчете в графах Результат выводятся значения целевой функции и оптимального плана, а также значения исходного опорного плана (графа Исходное значение). Кроме того, указывается, какие ограничения являются связанными, т.е. ограничения с дефицитным ресурсом, а какие – нет (графа Статус), и приведены значения соответствующих дефицитов по всем ограничениям (графа Разница).
Таблица 1
Отчет по устойчивости выводится в форме табл. 2. В этом отчете выводятся допустимые отклонения (графы Допустимое увеличение и Допустимое уменьшение) от заданных значений ресурсов (графа Ограничения Правая часть) и целевых коэффициентов (графа Целевой коэффициент). В этих пределах изменения ресурсов можно производить оценку изменения целевой функции с помощью двойственных оценок. Сами значения двойственных оценок ресурсов приведены в графе Теневая цена. Пределы изменения целевых коэффициентов задают области неизменности оптимального значения целевой функции. Большие значения пределов изменения значений, например 1E+30 (т.е. 1030) для верхней границы на спрос, означают фактическое отсутствие верхней границы. Это характерно для недефицитных ресурсов, значение которых можно увеличивать до бесконечности. Таблица 2
Отчет по пределам имеет вид табл. 3. Таблица 3
В этом отчете приведены значения нижних и верхних пределов изменения переменных оптимального плана (графы Нижний предел и Верхний предел) и для них даны соответствующие оптимальные значения целевой функции (графы Целевой результат).
|
Надстройки установить флажок Поиск решения. В этом случае, когда данный флажок отсутствует, нужно переустановить Excel заново в режиме выборочной установки с указанием включения данной функции.
