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

Лекция №7. Решение задач линейного программирования в MS Excel. 10 20 Зная теоретическую основу решения ЗЛП геометрическим методом, мы можем значительно упростить себе задачу, освоив решения этих же задач в офисной программе Microsoft Excel. Прежде всего, необходимо научиться выполнять установку специальных надстроек, позволяющих решать оптимизационные задачи. С этой целью проделаем следующие действия, предполагая, что работа ведется в MS Excel версии не ниже 2007 (для более ранних версий процедуру добавления специальных надстроек опишем дополнительно). Во-первых, откроем MS Excel, далее последовательно выполним следующее: 1. Во вкладке «Файл» необходимо нажать на кнопку «Параметры»; 2. В появившемся окне «Параметры Excel» в меню, расположенном слева, необходимо выбрать пункт меню «Надстройки»; 3. В разделе «Управление надстройками Microsoft Office» среди «Неактивных надстроек приложения» необходимо выделить строку «Поиск решения», единожды нажав на ней левой кнопкой мыши; 4. Внизу окна «Параметры Excel» необходимо нажать на кнопку «Перейти» и в новом появившемся окне «Надстройки» нужно отметить строку «Поиск решения» и нажать на кнопку «OK»; 5. Надстройка позволяющая выполнять решение оптимизационных задач находится на вкладке «Данные» в конце ленты инструментов в блоке «Анализ». В MS Excel 2003 и более ранних выпусках окно надстроек находится в меню «Сервис», далее пункт меню «Надстройки». В появившемся окне «Надстройки» необходимо отметить «Поиск решения» и нажать на кнопку «OK». После того, как проделаны описанные выше действия, надстройка «Поиск решения» появится дополнительным пунктом меню «Сервис». Прежде чем перейти к использованию надстройки «Поиск решения» выполним предварительную подготовку исходных данных задачи и запишем их удобным способ в таблице Excel. В качестве примера рассмотрим задачу о производстве двух товаров из лекций №2 и №3. Условия задачи, технологический процесс производства, представленный в таблице из лекции №2, запишем в таблицу Excel. В результате мы должны получить следующего вида таблицу: Рисунок 1. Исходные данные задачи о производстве двух товаров в таблице Excel. 1 30 Дадим пояснения. Можно заметить, что в ячейках, начиная с B3 и заканчивая С6, находятся коэффициенты при неизвестных x1 и x2 в ограничениях. В строке 7, в ячейках B7 и C7, находятся значения x1 и x2 , но поскольку заранее мы не знаем, в каком оптимальном количестве производить товары Р_1 и Р_2, то в начале решения приравниваем их значения к 0. В дальнейшем, надстройке «Поиск решения» мы укажем именно диапазон количества, в качестве диапазон, в котором можно производить изменения с целью поиска экстремума функции (максимум или минимум). В 8 строке, в ячейках B8 и C8, находятся коэффициенты целевой функции при соответствующих переменных x1 и x2 , а, как мы помним из постановки задачи, эти 40 коэффициенты ничто иное, как цены за одну единицу товаров Р_1 и Р_2. Графа E будет играть роль подсказки и фактически никакой реальной функциональной нагрузки для решения задачи не имеет. Немного позднее мы убедимся в этом на деле. Графа F имеет вполне очевидное толкование – это запасы ресурсов (те значения, которыми мы ограничены в соответствующих ресурсах), в системе ограничений – правая часть неравенств. Теперь перейдем к заданию целевой функции и системы ограничений математической модели задачи средствами MS Excel. В ячейке B9 напротив F  x  , запишем целевую функцию задачи, пользуясь специальной встроенной функцией MS Excel СУММПРОИЗВ(массив1;массив2;…). Упомянутая функция выполняет попарное произведение элементов массивов, а затем последовательно складывает результаты этих произведений. Если внимательно посмотреть на целевую функцию задачи из лекции №2, то можно заметить, что в ней выполняется умножение цены первого товара на объем соответствующего производства ( x1 ) и 50 умножение цены второго товара на объем соответствующего производства ( x2 ). Затем результаты произведений складываются. Перечисленные сейчас действия в точности соответствуют действиям, которое выполняет функция СУММПРОИЗВ(массив1;массив2;…). Для нашей задачи массив1 – это массив количества производимых товаров ( x1 и x2 или ячейки B7 и C7), а массив2 – это массив цен, то есть диапазон ячеек B8 и C8. Зная о возможностях функции СУММПРОИЗВ, запишем в ячейку B9 целевую функцию и, в дальнейшем, эту ячейку будем называть целевой ячейкой. Формула в целевой ячейке примет вид: 60 70 =СУММПРОИЗВ($B$7:$C$7;B8:C8) Читатель, хорошо владеющий навыками работы в Excel, заметит, что первый диапазон – диапазон количества, зафиксирован, то есть при копировании этой формулы в другие ячейки диапазон количества останется прежним и не собьѐтся на другой диапазон. Когда мы перейдем к заданию ограничений, станет ясно, зачем это сделано, а пока это просто нужно выполнить и записать так, как есть. Следующим этапом подготовки для использования надстройки «Поиск решения» является задание ограничений. Для этого в нашей таблице отведена специальная графа – графа D. Внимательный студент наверняка уже успел обратить внимание на то, что с точки зрения математических действий целевая функция и левая часть ограничений-неравенств одинакова. Действительно, как и в целевой функции, так и в неравенствах системы ограничений выполняется попарное произведение элементов и их сложение. Единственным отличием целевой функции и левой части неравенств является наличие других коэффициентов в неравенствах. При этом количество производимого товара (неизвестные x1 и x2 ) – это единственная неизменная часть и в целевой функции и в системе ограничений-неравенств. Фактически мы можем скопировать записанную в целевой ячейке B9 функцию и вставить в ячейки соответствующих ограничений: ячейки D3, D4, D5 и D6. Давайте вместе выполним следующие действия: 1. Переместимся в целевую ячейку B9 и нажмем на кнопку «Копировать»; 2. Переместимся в ячейку первого ограничения: D3. Нажмем на кнопку «Вставить»; 2 80 3. Обратите внимание! Если мы сейчас нажмем на строку формул, то увидим, что диапазон количества остался на своем прежнем месте, а второй диапазон сместился в название граф таблицы (см. рисунок 2). Это обстоятельство объясняется тем, что ранее мы зафиксировали ячейки количества и куда бы мы ни копировали существующую формулы – диапазон количества всегда будет оставаться на своем месте: B7:C7. Рисунок 2. Задание правых частей ограничений-неравенств. Отклонение в задании. Сейчас наша задача состоит в том, чтобы вернуть сместившийся диапазон на нужные нам коэффициенты. Поскольку мы задаем первое ограничений, то и нужны нам коэффициенты первого ограничения, которые находятся в строке 3 в ячейках B и C. Для того, чтобы переместить этот диапазон (отмечен зеленой рамкой) на коэффициенты 1 и 3 – наведем курсор мышки на соответствующую рамку и, зажав левую кнопку мыши, будем перетаскивать этот диапазон на ячейки B3:C3. Результат изложенных действий представлен на рисунке 3. Рисунок 3. Задание правых частей ограничений-неравенств. Верное определение диапазонов. 3 90 Эти действия необходимо проделать и для оставшихся трех ограничений, однако, можно просто скопировать уже готовую заданную функцию из ячейки D3 в оставшиеся ограничения. Зеленый диапазон уже будет двигаться в верном направлении, последовательно переходя от верхних к нижним коэффициентам. На рисунке 4 показана уже готовая верно подготовленная таблица. Рисунок 4. Окончательный вид таблицы, подготовленной к «Поиску решения». 100 На рисунке 4 показан таблица, которая подготовлена к использованию надстройки «Поиск решения» и выполнению оптимизации. Можете заметить, что этот самый процесс подготовки включает в себя множество разнородных действий и, на первый взгляд, может показаться запутанным и сложным. Но смею заверить читателя, что при неоднократном проделывании этих операций, появляется сноровка и подготовка занимает не так уж и много времени. Теперь перейдем на вкладку «Данные» и в конце ленты инструментов в блоке «Анализ» нажмем на кнопку «Поиск решения». В зависимости от выпуска Microsoft Office в существующей лекции может появиться окно «Поиска решения» отличное от того окна, которое есть у читателя, но по сути они абсолютно одинаковы. На рисунке 5 показано это самое окно. 4 5 Рисунок 5. Окно надстройки «Поиск решения». 110 120 И так, поясним основное содержание этого окна. В строке «Оптимизировать целевую функцию» необходимо указать ячейку, в которой находится наша целевая функция, то есть ячейку B9. Изначально в эту строку подставляется та ячейка, в которую последний раз переместился пользователь. Для того, чтобы облегчить себе задачу перед тем, как открыть поиск решения можно сразу переместиться в целевую ячейку – это позволит миновать первый шаг, на котором нужно указывать точное расположение ячейки с целевой функцией. Чуть ниже размещаются варианты оптимизации, которые естественным образом зависят от того, какую задачу решает пользователь. В задаче, которую решаем мы, напомню, - необходимо отыскать максимум целевой функции. В строке «Изменяя ячейки переменных» указывается диапазон количества, то есть B7:C7. Рассуждая логически, можно прийти к выводу, что количество производимого товара – это единственный параметр, на который можно повлиять в данный момент. В действительности, технологический процесс производства – процесс, сопряженный с высокими затратами времени; рыночные оптовые цены продиктованы рынком и изменению не подлежат; запасы определены, а их изменение может повлиять лишь на увеличение или уменьшение производимого товара. Значит, для поиска максимума функции можно изменять только переменные x1 и x2 . Собственно, надстройке «Поиск решения» нужно указать именно их для того, чтобы подбирая по определенному алгоритму эти значения можно было определить максимум целевой функции. Далее необходимо рассмотреть одну из самых важных процедур: задание ограничений-неравенств в надстройке «Поиск решения». Для этого необходимо нажать на кнопку «Добавить» справа, после чего появится окно следующего вида: Рисунок 6. Добавление ограничений в надстройке «Поиск решения». Структура этого окна отдаленно напоминает математическую запись ограничения: здесь в левой части указывается математическое выражение, а в правой части отмечается, то чем ограничен тот или иной ресурс, каким значением. Задавая первое ограничение в левой части, мы должны отметить ячейку D3, просто нажав на ней в режиме задания добавления ограничения. Соответственно, для того, чтобы задать правую часть первого ограничения необходимо нажать на ячейку F3. Важно! Не забывайте о виде отношения. В существующей задаче мы не изменяем знак отношения, потому что в математической модели ограничения всюду заданы со знаком «меньше либо равно». Естественно, что не во всякой задаче такой тип отношения имеет место быть. Тогда, после проделанных действий, мы получим следующего вида окно: 6 Рисунок 7. Заданное ограничение в надстройке «Поиск решения». 130 После необходимо нажать на кнопку «Добавить». Программа добавит ограничение, очистит поле окна и перейдет к добавлению следующего ограничения. Те же самые действия необходимо проделать и в отношении оставшихся трех ограничений. Важно! После того, как пользователем задано последнее ограничение, необходимо нажать на кнопку «OK», дабы вернуться в окно надстройки «Поиск решения». Если же случайно была нажата кнопка «Добавить» и программа перешла в режим задания нового лишнего ограничения, то достаточно нажать на кнопку «Отмена». После того, как все ограничения заданы, необходимо выполнить последнее действие. Под списком ограничений находится выпадающий список, который необходимо раскрыть и выбрать второй пункт – «Поиск решения линейных задач симплекс-методом». На рисунке 8 изображен окончательный вид окна надстройки «Поиск решения» перед нажатием кнопки «Найти решение». 7 Рисунок 8. Окончательный вид окна надстройки «Поиск решения» перед нажатием на кнопку «Найти решение». Теперь можно нажать на кнопку «Найти решение» и, если пользователем были выполнены все действия корректно, то программа выведет окно «Результаты поиска решения» следующего вида: Рисунок 9. Окно «Результаты поиска решения». 140 Для того, чтобы просмотреть отчет о результатах оптимального решения, достаточно один раз нажать левой кнопкой мыши на нужно виде отчета и нажать кнопку «OK». После этого в левом нижнем углу среди вкладок «Лист 1», «Лист 2», «Лист 3» появится дополнительная вкладка «Отчет о результатах 1» со следующим содержанием: Рисунок 9. Оптимальное решение. Результат. В первой таблице этого отчета указан максимум целевой функции, а во второй, при каких значениях переменных x1 и x2 достигается этот максимум. Напомним, что эти переменные соответствуют объемам производимого товара. Из отчета следует, что товар Р_1 необходимо 8 производить в количестве 5 единиц, а товар Р_2 – в количестве 3 единицы при этом максимальный доход, который получит производитель составит 24 денежных единицы. Этот вывод полностью совпадает с результатами, которые мы получили, решая ту же самую задачу геометрическим методом. 150 На этом все! Четвертая лекция окончена. Бесспорно, что проделанная работа будет лучше воспринята на деле – сидя перед компьютером и следя за ходом выполнения работы. Поэтому предлагаю студентам сочетать эту изучение этого материала с видео-лекцией, которая вскоре появится в видеолекуториуме нашего университета. Успехов! 9