Решение задачи назначения с помощью электронных таблиц

Минимальный (наибольший по абсолютной величине) элемент  вычитается из всех элементов соответствующей  строки. 
 

 

Минимальный элемент вычитается из всех элементов  соответствующего столбца.

НЕДОПУСТИМЫЕ  НАЗНАЧЕНИЯ

Данную  проблему можно решить так же, как  и транспортную задачу. Если по той  или иной причине некоторое назначение является недопустимым, то в соответствующей  клетке проставляется значение стоимости, которое заведомо больше любого другого  значения. После этого в ходе реализации алгоритма мы сможем избежать данного  назначения автоматически.

НЕСООТВЕТСТВИЕ  ЧИСЛА ПУНКТОВ ПРОИЗВОДСТВА И  НАЗНАЧЕНИЯ

Если  исходная таблица не является квадратной, в нее следует включить дополнительные фиктивные строки и столбцы, необходимые  для приведения ее к квадратной форме. Значения стоимости, соответствующие  фиктивным клеткам, как правило, равны нулю.

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

 

       

    2.2 Разработка экономико-математической  модели задачи  оптимизации процесса  назначения

       Компания Beta Motor Company имеет 4 различных сборочных  линии на своём 

главном заводе. Управляющий производством  имеет 5 служащих и желает назначить  по одному служащему к каждой из сборочных линий. Каждый из этих служащих может работать на любой сборочной  линии, но с различными затратами, связанными с индивидуальным опытом и мастерством. Эти затраты приведены ниже в  таблице (см. таблицу 2.1).

Таблица 2.1- Условие задачи

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

    Данная  задача не является сбалансированной - количество служащих больше количества производственных линий. Тогда ограничения  задачи будут выглядеть следующим  образом:

– сотрудник не может быть назначен на две линии одновременно, кроме того, один из сотрудников останется не назначенным;

       – на каждую линию будет назначен обязательно один сотрудник;

       – ограничения на переменные по условию.

Задача  состоит в минимизации общих  затрат на производство.

            Теперь мы имеем все, что  было необходимо и можем приступить  к решению задачи в Excel. 
 
 
 
 

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

    Для поиска оптимального решения задачи воспользуемся 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 – Матрица назначения служащих

       Затем создаём «Целевую ячейку» в которой  будут моделироваться итоговое значения задачи. В целевую ячейку введём следующие параметры «=СУММПРОИЗВ(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).

     Рисунок 2.8 – Решение 
 
 

    Самым оптимальным решением задачи будут  следующие назначения:

на линию 1 – Служащий 5;

на линию 2 – Служащий 1;

на линию 3 – Служащий 3;

на линию 4 – Служащий 2;

Служащий 4 не будет назначен ни на одну линию. 
 

Разработки компьютерной технологии решения задач о назначениях смотреть в приложении на диске. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  Заключение 

    При написании данной курсовой работы были рассмотрены теоретические основы и методы решения задач назначения. А так же решение задачи о назначении с помощью пакета прикладных программ Microsoft Excel.

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