Линейное программирование с пакетом MS Excel

В реальном мире существует огромный класс практических задач, которые хорошо решаются в рамках линейного программирования.

Это задачи на оптимизацию процессов, кадровые задачи, управление запасами, транспортная логистика и т.д.

puzzle11 Линейное программирование с пакетом MS Excel

Упрощенный пример такой задачи может быть таким: «Фабрика выпускает мебель разных наименований с разной прибылью. Как можно обеспечить максимальную прибыль, если удастся получить дополнительные ресурсы для производства. Спланировать производство».

Вполне жизненная задача, а вместо мебели можно подставить что угодно.

В незапамятные времена такие задачи решались методом перебора вариантов.

Интересно, что и сегодня компьютеры занимаются чаще всего именно перебором.

К примеру, в задачах оптимальной резки металла, кройки ткани или дерева, перевозки грузов разного размера.

Грубо говоря, проще найти миллион вариантов, а затем выбрать из них самый оптимальный.

В любом случае, сегодня по таким условиям строится математическая модель, которая описывает действия с реальным объектом и которую можно разработать на простой рабочей станции HP.

Важнее всего в модели определить и выделить целевую функцию, завязанную на изменяемый набор переменных.

В примере выше – это ассортимент мебели и прибыль. Целевая функция может стремиться к максимуму, минимуму или определенному значению.

Чтобы результат был практичен и верен с небольшой долей погрешности, важно оградить модель системой ограничений.

В примере это складские ресурсы, а в других задачах – люди, время, деньги и т.д.

В модель часто добавляют полезные указания насчет того, нужно ли вычислять целые или дробные значения.

Обычно составлением моделей обучение и ограничивается, но их же нужно применять на практике.

В высшей математике для этого используются графические и табличные методы, алгоритмы Ньютона и других умных товарищей, «жадные» и «экономные» алгоритмы.

На практике проще использовать для расчета обычный пакет MS Excel: в его меню Сервис есть пункт «Поиск решения».

Если такого пункта нет, то нужно установить данный модуль из дистрибутива MS Office.

Для версий до Excel 2007 включение данного  пункта меню доступено  через команду меню Сервис --> Надстройки.

Excel poisk reshenija 0 163x350 Линейное программирование с пакетом MS Excel

Начиная с Excel 2007 через диалоговое окно Файл - Параметры Excel --> Надстройки.

Excel poisk reshenija 11 450x324 Линейное программирование с пакетом MS Excel

 

В выпадающем списке Управление оставляем значение "Надстройки Excel" b cправа нажимаем кнопку "Перейти".

Excel poisk reshenija 2 Линейное программирование с пакетом MS Excel

В открывшемся окошке ставим галочку рядом с параметром "Поиск решения" и нажимаем ОК.

После чего в закладке "Данные" появится опция "Поиск решения".

Excel poisk reshenija 3 1024x175 Линейное программирование с пакетом MS Excel

 

В версиях, более ранних, чем Excel 2007, аналогичная команда появится в меню Сервис - Поиск решения.

Переменные, целевая функция и ограничения в свободном виде записываются в ячейки таблицы, после чего указываются в окне «Поиска решения».

Нужно указать точно те ячейки, где будет меняться информация, где записана целевая функция и набор ограничений.

После этого нужно запустить запуск расчета.

Если решение будет найдено, указанные в ячейках формулы будут заменены на найденные значения, а также сформируются отчеты по поиску.

Допустим, Вы бригадир бригады комбайнеров, и Вам нужно распределить вырученные за зерно 500 000 руб. между работниками пропорционально отработанным часам.

Т.е. надо подобрать коэффициент пропорциональности для вычисления размера зарплаты по отработанному времени.

Сначала создаём табличку с исходными данными и формулами, с помощью которых должен быть получен результат.

Excel poisk reshenija 4 450x173 Линейное программирование с пакетом MS Excel

 

В данном примере результат - это общая сумма выручки 500 тыс. рублей..

Нужно, чтобы целевая ячейка С6  формулой была связана с нужной нам изменяемой ячейкой F2 (коэффициент пропорциональности).

В примере они связаны через промежуточные формулы, вычисляющие размер зарплаты для каждого работника (С2:С5).

Excel poisk reshenija 51 450x161 Линейное программирование с пакетом MS Excel

 

Потом запускаем "Поиск решения" и в открывшемся окне устанавливаем необходимые параметры.

Внешний вид окна в разных версиях Excel несколько различается:

Там задаем - Оптимизировать целевую функцию $C$6 (можно поставить курсор в это окошком и щелкнуть по ячейке целевой функции С6)

Ставим точку "Значения" и вводим наши 500000 руб выручки.

В "Изменяя ячейки переменных" ставим наш искомый коэффициент $F$2 (можно поставить курсор в это окошком и щелкнуть по ячейке целевой функции F2).

Excel poisk reshenija 6 348x350 Линейное программирование с пакетом MS Excel

И потом нажимаем на кнопку "Найти решение".

И раз - получаем результат.

Excel poisk reshenija 7 450x264 Линейное программирование с пакетом MS Excel

Который можно либо сохранить, либо отменить.

В некоторых случаях полезно вызывать окно «Параметры» в этом же окне, где можно настроить погрешность и задать количество итераций и времени поиска.

При нажатии кнопки «Сохранить» решение сохраняется вместе с файлом, и его потом можно многократно открывать и использовать с разными видами начальных значений и условий.

Скачать файл примера можно по ссылке http://ds-release.ru/primer-poisk-reshenija.xlsx

 

googleplus Линейное программирование с пакетом MS Excel
livejournal Линейное программирование с пакетом MS Excel
  Метки:
  admin
  Просмотров: 2 616
  Запись опубликована в 12:11

Есть что сказать? Тогда действуй!


:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-o :-P :-D :-? :) :( :!: 8-O 8)