Решение задачи оптимизации процесса назначения

Для поиска оптимального решения задачи воспользуемся Microsoft Excel. Excel – универсальное программное средство, предназначенное для электронной обработки данных.

Для поиска решения необходимо:

1) ввести данные в ячейки рабочего листа Excel.

разместить блоки ячеек на рабочем листе Excel, необходимые для моделирования назначения служащих, а так же для формирования математической модели и целевой функции.

сформировать на рабочем листе Excel элементы математической модели и целевую функцию.

2) настроить программу «Поиск решения» и выполнить её.

В начале создём блок в Excel, исходные данные, содержащий значения заданные в условии задачи (см. рисунок 2.1)

Рисунок 2.1 – Исходные данные

Затем создаём блок ячеек матрица назначения служащих, в которой будут моделироваться назначения служащих, заполненная нулями, которая будет размещаться в диапазоне ячеек «B13:E17» (см. рисунок 2.2).

Последний столбец «Матрицы назначений служащих» содержит сумму значений по всем строкам, которая по условию должен быть равен 0, либо 1 (см. рисунок 2.2). Последняя строка, содержит сумму значений по каждому столбцу и должна по условию ровняться единице (см. рисунок 2.3).

Рисунок 2.2 – Матрица назначения служащих

Рисунок 2.3 – Матрица назначения служащих 2

Затем создаём «Целевую ячейку» в которой будут моделироваться итоговое значения задачи. В целевую ячейку введём следующие параметры «=СУММПРОИЗВ(B3:E7;B13:E17)», она будет располагаться в ячейке «E23» (см. рисунок 2.4).

Рисунок 2.4 – Целевая функция

Далее нужно настроить программу «Поиск решения» (см. рисунок 2.5). Нажимаем в главном меню на надпись «Сервис» и в выпадающем списке выбираем «Поиск решения». Если в меню «Сервис» нет «Поиск решения», тогда в этом же меню нужно нажать «Надстройки» и выбрать в появившемся меню «Поиск решения».

Чтобы настроить программу «Поиск решения», нужно в начале указать ….

Рисунок 2.5 – Поиск решения

целевую ячейку «E23». Далее в поле «изменяя ячейки» указать диапазон «B13:E17». Так как наше выражение стремиться к минимуму, выбираем «Равной: минимальному значению».

Далее нужно ввести ограничения, для этого нужно нажать копку «Добавить», откроется форма для добавления ограничений (см. рисунок 2.6).

Далее нужно ввести ограничения, для этого нужно нажать копку «Добавить», откроется форма для добавления ограничений (см. рисунок 2.6).

Рисунок 2.6 – Ввод ограничений

Первое ограничение будет таким: диапазон ячеек «B13:E17<=1», т.е. только один служащий может быть назначен на одну линию. Для ввода ограничения нажимаем кнопку справа от поля «Ссылка на ячейку» (см. рисунок 2.6). Открывается новая форма ввода (см. рисунок 2.7).

Рисунок 2.7 – Добавление ограничения

Выбираем или пишем диапазон ячеек «B13:E17» и нажимаем кнопку справа от поля (см. рисунок 2.7). Значение <=, оставляем как есть (см. рисунок 2.6), а поле «Ограничение» (см. рисунок 2.6) пишем цифру 1.

Теперь программа не введёт не в одну ячейку значение более единицы.

Т.к. значение «x» может быть 0 или 1, тогда следующее ограничение будет «B13:E17>=0», вводим его тем же способом, который был описан выше. Чтобы не было дробных значений, вводим следующее ограничения «B13:E17=целое», для этого после ввода диапазона значений в центральном поле формы добавления ограничения нужно выбрать вместо «<=», значение «цел» (см. рисунок 2.6).

Следующие ограничения затронут «суммарные ячейки» (см. рисунок 2.4), строка «Итого» каждого столбца, должно быть равно 1, т.к. только один служащий может быть назначен на одну линию. Вводим следующие ограничения: «$B$18=1», «$C$18=1», «$D$18=1», «$E$18=1».

Следующее ограничения затронут «Служащих», т.к. только четверо из пяти могут быть назначены на линии, то каждая строка суммарного столбца «Итого», может быть равна нулю или единице, поэтому вводим следующие ограничения: «$F$13<=1», «$F$13>=0», «$F$14<=1», «$F$14>=0», «$F$15<=1», «$F$15>=0», «$F$16<=1», «$F$16>=0», «$F$17<=1», «$F$17>=0».

Все ограничения были введены, теперь необходимо нажать кнопку «Выполнить» (см. рисунок 2.5).

Далее Excel вычисляет целевую функцию, и матрицу назначений, где целевая функция равна 75, а в «матрице назначения служащих» найдены наилучшие назначения служащих (см. рисунок 2.8).

Перейти на страницу: 1 2