Оптимизация процессов на водном транспорте. MS EXCEL — система обработки электронных таблиц

Лекция 7 Ms Excel — система обработки электронных таблиц оптимизация процессов на водном транспорте В Ms Excel имеется модуль расширения “Принятие решений”, который позволяет решать определенный класс задач оптимизации. Данный модуль представляет собой надстройку и по умолчанию не включен в состав табличного процессора, если выполняется стандартная установка пакета Microsoft Office. Это же касается и более поздних версий пакета. Алгоритм поиска решений основан на процедуре анализа, которая получила название “что, если”. Критерий оптимизации задается в виде формулы и помещается в так называемую целевую ячейку. В таблице выделяется специальная область, которая изменяется в процессе поиска решения и значения переменных в которой являются аргументами критерия оптимизации (переменными в целевой ячейке). Для отражения реальных условий, накладываемых на переменные, используются ограничения. Ограничения могут иметь различную природу. Это могут быть как ограничения на норму или область изменения переменной, так и некоторая функциональная зависимость, задающая ограничивающую область, которая может изменяться в процессе поиска решения. Для запуска модуля “Принятие решений” необходимо выполнить следующие действия. 1. В меню Сервис выбрать команду Поиск решения. 2. Если команда Поиск решения отсутствует в меню Сервис, то: • надо запустить команду Надстройки из меню Сервис; • в открывшемся диалоговом окне Надстройки в списке Список надстроек установить флажок напротив компоненты Поиск решения (рис. 1); • нажать кнопку ОК. В результате этих действий команда Поиск решения появится в меню Сервис. Перед запуском надстройки Поиск решения необходимо решить следующие проблемы: сформулировать математическую постановку задачи; задать начальный план решения и ограничения; сформулировать критерий оптимизации; составить табличную модель записи исходных условий, начального плана решения задачи и вывода результатов. Прежде чем приводить последовательность реализации описанных проблем на примере решения транспортной задачи, рассмотрим основные параметры, которые необходимо задать в процессе работы с надстройкой Поиск решения. 1. Основные параметры надстройки Поиск решения А. Задание параметров в диалоговом окне Поиск решения После запуска команды Поиск решения из меню Сервис на экране откроется диалоговое окно Поиск решения (рис. 2). Рис. 2. Диалоговое окно Поиск решения Окно содержит следующие разделы и кнопки. Разделы: • установить целевую ячейку — область для задания целевой ячейки (формулы вычисления критерия оптимизации), значение которой необходимо максимизировать, минимизировать или установить равным некоторому значению (заданному числу). Для этого надо щелкнуть мышью по одной из радиокнопок в области Равной;  Замечание. Целевая ячейка должна всегда содержать формулу. • изменяя ячейки — служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку. Значения можно ввести вручную или выделить область в таблице решения задачи (см. п. 2.5.3.2). Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается задание до 200 изменяемых ячеек. Кнопка Предположить используется для автоматического поиска ячеек, влияющих на критерий оптимизации, вычисление которого задано в виде ссылки в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки; • ограничения — содержит ограничения, сформулированные в постановке задачи. Для задания ограничений применяется кнопка Добавить, а для изменения или удаления — кнопки Изменить и Удалить. Кнопки: • Выполнить, Закрыть и Справка выполняют стандартные функции; • Восстановить служит для возвращения к начальной табличной модели, которая задается перед решением задачи оптимизации; • Параметры — служит для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения. Б. Задание ограничений Для задания ограничений в соответствии с условиями задачи (см., например, рис. 3) необходимо выполнить следующие действия. 1. В диалоговом окне Поиск решения в разделе Ограничения нажать кнопку Добавить. На экране откроется диалоговое окно Добавление ог-раничений (рис. 3). 2. В поле Ссылка на ячейку ввести адрес или имя ячейки, на значение которой накладываются ограничения. 3. Затем в средней части окна из раскрывающегося списка выбрать операцию (<=, =, >=, цел или двоич), которая будет применяться для сравнения значений из списков Ссылка на ячейку и Ограни-чения. Если выбрано условие цел, в поле Ограничение появится слово «целое». Если выбрано условие двоич, в поле Ограничение появится слово «двоичное». 4. В поле Ограничение можно ввести число, формулу, ссылку на ячейку или ее имя. 5. Если ввод ограничений на этом заканчивается, то следует нажать кнопку ОК, чтобы ввести ограничения в действие и вернуться к окну Поиск решения. В противном случае щелкнуть по кнопке Добавить и выполнить шаги 2 - 4.  Примечание. Условные операторы типа цел и двоич можно применять только при наложении ограничений на изменяемые ячейки. В. Изменение или удаление ограничений В процессе решения задачи может возникнуть необходимость в из-менении ограничений. Для этого надо выполнить следующие действия. 1. В диалоговом окне Поиск решения в разделе Ограничения в списке выделить ограничение, которое требуется изменить или удалить. 2. Для изменения ограничения нажать кнопку Изменить и в открывшемся диалоговом окне Изменение ограничений (окно имеет та-кой же вид, как и окно Добавление ограничений) выполнить требуемые действия. Активизация кпопки Удалить приводит к исключению выделенного ограничения. Г. Задание вычислительных параметров поиска решения Кроме условий задачи необходимо выбрать численные характеристики и метод поиска решения. Для этого в диалоговом окне Поиск решения необходимо щелкнуть по кнопке Параметры. На экране откроется диалоговое окно Параметры поиска решения (рис. 4). Рис. 4. Диалоговое окно Параметры поиска решения Для решения примеров, которые будут рассматриваться ниже, достаточно ограничиться применением линейной модели, которая обладает наибольшей скоростью сходимости. Все остальные установки в этом окне можно не менять. Флажок Показать результаты итераций позволяет просмотреть промежуточные результаты поиска решений и в случае необходимости внести корректировку в применяемый численный метод. Перейдем теперь к решению конкретных задач оптимизации. 2. Транспортная задача А. Постановка задачи Имеются производители продукции в г. Курске, Калуге, Воронеже и Орле, которые выпускают товар соответственно в объеме ai (i=1,…,4). Продукция доставляется на склады или предприятия в г. Москве, Смоленске, Кирове, Твери, причем потребности каждого потребителя равны bj (j=1,…,4). Требуется минимизировать затраты на перевозку товаров от предприятий-производи-телей на торговые склады в г. Москве, Смоленске, Кирове, Твери. При этом необходимо учесть возможности поставок каждого из производителей при максимальном удовлетворении запросов потребителей. Б. Задание исходных условий Перейдем к построению табличной модели задачи. Б1. Задание начального плана Обозначим через xij поставку товара от i-го производителя на j-й склад (предприятие). Так как задача решается итерационным методом, то зададим начальный план перевозок, например, положим, что каждый производитель поставляет по одному товару на каждый склад, и поместим эти значения в ячейки С9:F12. Так как план должен быть допустимым, то количество товара ai от i-го поставщика должно полностью поступить на конечные пункты, а суммарное количество на каждом складе не должно превышать его потребности bj, т. е. , . Соответствующие значение по указанным формулам заносим в ячейки B9:B12 и С14:F14. Итак, составлен начальный план в виде матрицы X: . Б2. Задание исходных объемов поставок Укажем теперь в ячейках С16:F16 мощности, отражающие возмож-ности складов по приему продукции: 240; 180; 300; 190т. В ячейки B18:B21 введем возможности поставщиков товара: 250; 210; 280; 311т. Б.3. Стоимость перевозок Выразим транспортные издержки, приходящиеся на перевозку единицы продукции от поставщика к потребителю (на склад), в условных единицах. В ячейки С18:F21 введем матрицу С с элементами cij: .  Замечание. В отличие от начального плана данные по объемам поставок, мощностям складов и стоимости перевозок в процессе решения задачи не меняются. Б.4. Целевая функция и ограничения Нам осталось задать еще целевую функцию и ограничения на пере-менные. По условию необходимо минимизировать стоимость перевозок, т.е. . (3.1) Для этого вычисляем стоимость zj текущих перевозок по доставке грузов на каждый склад, полагая сначала j=1 (для Москвы) и помещая в ячейку С23 формулу =C9×C18+C10×C19+C11×C20+C12×C21c11×x11+c21×x21+c31×x31+c41×x41. Аналогичным образом получаем транспортные издержки для складов 2 (Смоленск), 3 (Киров), 4 (Тверь) и помещаем их в ячейки D23, E23, F23. Текущее значение целевой функции в соответствии с (3.1) заносим в ячейку В23 =СУММ(C23:F23). В соответствии с теорией выпишем ограничения: а) количество перевезенных грузов не может превышать возможности потребителя. В нашем случае это условие записывается следующим образом: B9:B12 <= B18:B21; б) количество доставляемых грузов должно быть не ниже (меньше) потребностей склада: C14:F14>= C16:F16; в) число перевозок не может быть отрицательным: C9:F12 > 0. После выполнения указанных выше действий таблица должна иметь вид, показанный на рис. 5. В. Решение задачи Процесс поиска решения сводится к выполнению следующих действий. 1. Запустить команду Поиск решения из меню Сервис. 2. В открывшемся диалоговом окне Поиск решения (см. рис. 2) задать параметры, указанные в параграфе Б: • целевую ячейку задать в виде $В$23 (символ “$” указывать обязательно, так как работа идет с абсолютными адресами ячейки и результат должен храниться в ней); • изменяемые ячейки — $C$9:$F$12 — это область, куда должен помещаться окончательный план решения задачи; • ввод ограничений осуществляется в соответствии с описанной процедурой (см. п. Б части 2.6.1) и должен иметь вид, показанный на рис. 4. Рис. 5. Табличная модель транспортной задачи 3. Нажать кнопку Параметры и задать требования к численной процедуре поиска решения (они должны соответствовать данным, показанным на рис. 6). Активизировать кнопку ОК, чтобы вернуться в диалоговое окно Поиск решения. Рис. 6. Требования к численному методу решения транспортной задачи 4. Нажать кнопку Выполнить для поиска решения. В случае существования решения на экране появится диалоговое окно Результаты поиска решения (рис. 7). Рис. 7. Диалоговое окно Результаты поиска решения Рис. 8. Оптимальное решение транспортной задачи 5. В диалоговом окне Результаты поиска решения щелкуть по радиокнопке опции Сохранить найденное решение, и, если необходимо, в списке Тип отчета указать те дополнительные разделы (Результаты, Устойчивость или Пределы), которые необходимо сохранить для последующей оценки выбранного численного метода решения. Все результаты будут сохранены в текущей книге на отдельных листах.  Предупреждение. Так как найденное оптимальное решение сохраняется на текущем листе, на котором создавалась табличная модель задачи, то перед поиском решения необходимо сделать копию исходной постановки задачи на диске и работать с ней. Оптимальное решение транспортной задачи в табличной форме показано на рис. 8. Для транспортной задачи должно выполняться условие баланса: . Вычисления показывают, что решение является оптимальным и усло-вие баланса выполняется. Оптимальный план доставки грузов показан на рис. 9. На нем отражены только маршруты с ненулевым количеством доставляемых грузов. Рис. 9. Оптимальный план перевозок Рис. 10. План отгрузки продукции поставщиками и их потенциальные возможности Полученные результаты позволяют оценить некоторые экономические проблемы. Так, на рис. 10 показано, насколько эффективно используются возможности заводов по отгрузке продукции, если реализовать принятый план. Из диаграммы видно, что производители продукции в г. Воронеже и Орле терпят убытки. Это объясняются стоимостью перевозок товаров из этих городов, например, в г. Киров. Сделанные выводы подтверждает диаграмма, приведенная на рис. 11. Рис. 11. Гистограмма, отражающая издержки по доставке груза (обозначения Кур— Курск, М —Москва, Смо — Смоленск, Ки — Киров, Кал — Калуга, Тв — Тверь, Ор — Орел, Вор — Воронеж) Варианты затрат поставщиков продукции в стоимостном выражении по сравнению с оптимальными показаны на рис. 12. Пример работы итерационной процедуры поиска оптимального решения транспортной задачи для случая доставки грузов по маршрутам Курск — Тверь и Воронеж — Смоленск показан на рис. 13. Рис. 12. Сравнение затрат при использовании оптимального и неоптимального планов перевозки Рис. 13. Поиск оптимального решения транспортной задачи 3. Составление графика работы сотрудников отдела сбыта А. Постановка задачи В отделе сбыта продукции фирмы работают 5 человек по пятидневной неделе. Дневная зарплата сотрудника составляет 150 руб. Необходимо составить график работы, обеспечивающий требуемый уровень обслуживания при наименьших затратах на оплату труда. Б. Задание исходных условий Прежде всего необходимо составить варианты расписания — план — с учетом выходных дней. Таких вариантов может быть 7. Представим их в виде таблицы, поместив соответствующие варианты в ячейки A7:C13 столбцов A – C: График Выходные дни A Воскрес., понедельник Б Понедельник, вторник В Вторник, среда Г Среда, четверг Д Четверг, пятница Е Пятница, суббота Ж Суббота, воскресенье Теперь в соответствии с вариантами составляем план расписания на каждый день, применяя следующую кодировку: 0 — группа работников не работает, 1 — группа работников работает. В столбце Работники задаем начальный план распределения количества человек в группе на каждый вариант (при этом необходимо учесть, что общее количество работников для каждого варианта расписания не должно превышать величины 10=2×5): Работники Вс Пн Вт Ср Чт Пт Сб 3 1 1 1 1 4 1 1 1 1 1 5 1 1 1 1 1 9 1 1 1 1 1 1 9 1 1 1 1 1 1 4 1 1 1 1 1 1 5 1 1 1 1 Размещаем предполагаемый начальный план решения задачи в ячейках D6:L13. Итак, первая часть табличной модели должна иметь вид (рис. 14, ячейки А6:L13) : График Выходные дни Работники Вс Пн Вт Ср Чт Пт Сб A Воскрес., понед. 3 1 1 1 1 Б Понедельник, втор. 4 1 1 1 1 1 В Вторник, среда 5 1 1 1 1 1 Г Среда, четверг 9 1 1 1 1 1 1 Д Четверг, пятница 9 1 1 1 1 1 1 Е Пятница, суббота 4 1 1 1 1 1 1 Ж Суббота, воскрес. 5 1 1 1 1 Затем в следующей строке таблицы вычисляем количество работа-ющих по формуле (ячейки F15:L15) =Раб.АВс.А + …+ Раб.ЖВс.Ж = $D$7F7 + $D$8F8 + $D$9F9 + + $D$10F10 + $D$11F11 + $D$12F12 + $D$13F13, где Раб.А — ячейка столбца Работники для варианта А, Вс.А — ячейка столбца Вс для варианта А, и размещаем эти значения непосредственно под соответствующим столбцом (ячейки F15:L15). Под столбцом Работники (ячейка D15) выводим общее количество работников, просуммировав все ячейки столбца =СУММ(D7:D13). Итак, получаем табличную модель, показанную на рис. 15. Рис. 14. Табличная модель задачи поиска оптимального расписания В ячейках F17:L17 задаем то минимальное количество работающих, которое должно работать в течение недели в отделе фирмы. Например вве-дем 22; 20; 20; 18; 20; 18; 17. В ячейке D19 вводим 150р. — дневную ставку оплаты труда, принятую в фирме. Ячейку D20 используем в качестве целевой для расчета расходов на оплату труда по формуле =D15×D19. Итак, условия задачи и начальный план заданы. Перейдем теперь к формированию ограничений. В. Формирование ограничений Ограничения основные: D7:D13 >= 0 — число работников в группе не может быть отрицательным; D7:D13 = Целое — число работников должно быть целым; F15:L15 >= F17:L17 — число ежедневно занятых работников не должно быть меньше ежедневной потребности. Дополнительные ограничения: D8:D12 <= 10 — число работников в рабочие дни <=10; D13 <= 5 — число работников в группе в субботу и воскресенье не должно превышать 5. Для поиска решения применяется линейная модель. Область изменяемых ячеек — D7:D13. Г. Решение задачи в MS Excel Процесс поиска решения сводится к выполнению следующих действий. Рис. 15. Диалоговое окно Поиск решения для задачи составления расписания 1. Запустить команду Поиск решения из меню Сервис. Рис. 16. Оптимальный план расписания 2. В открывшемся диалоговом окне (рис. 15) задать параметры, указанные в пунктах А — В этого раздела (они показаны на рис. 15), т. е.: • целевую ячейку задать в виде $D$20 (символ “$” указывать обязательно, так как работа идет с абсолютными адресами ячейки и результат должен храниться в ней); • изменяемые ячейки — $D$7:$D$13 — в эту область должен помещаться окончательный план решения задачи; • ввести ограничения в соответствии с процедурой, описанной в части 2.6.1 данной главы; • вычислительные параметры алгоритма решения задачи должны совпадать с параметрами, показанными на рис. 6. 3. Для поиска решения щелкнуть по кнопке Выполнить в диалоговом окне Поиск решения. 4. Если решение существует, то в ячейках D7:D13 будет выведен полученный оптимальный план расписания, а в ячейке D20 — минимальное значение целевой функции (рис. 16). Оптимальное распределение сотрудников отдела сбыта по вариантам показано на рис. 17. На рис. 18 приведена гистограмма распределения недельной оплаты сотрудников отдела сбыта по вариантам. Рис. 17. Оптимальное распределение сотрудников отдела сбыта по вариантам Рис. 18. Гистограмма распределения недельной зарплаты сотрудников отдела сбыта по вариантам