Оптимизация процесса назначения

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

Целью данной курсовой работы является описание метода решения задачи, оптимизации процесса назначения. Для реализации поставленной цели в работе необходимо решить следующие задачи: раскрыть теоретические основы касающихся, темы курсовой работы; описать методы решения задачи; решить задачу оптимизации процесса назначения.Объектом является возможность решения задачи оптимизации процесса назначения, на производственном примере.

Предметом исследования является возможность решения производственной задачи о назначении в среде Microsoft Excel. Теоретической основой курсовой работы послужили труды: Н.Б. Бабаевой, А.В. Белобродского, Т.В. Алесинской, В.И. Максимова, а также ряд других источников.Курсовая работа или её элементы могут представлять интерес для руководителей предприятий, заинтересованных выборе оптимального назначения каких-либо ресурсов для производства. 1 Теоретические основы задачи о назначении 1.1 Постановка задачи Среди задач управления организациями весьма распространена задача распределения прав, обязанностей, работ, благ между членами коллектива, в решении которой участвует руководитель, ответственный за это распределение.

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

Желательно заполнить все вакантные места. Необходимо найти наилучшие (с точки зрения обеих сторон) назначения. Через отдел подготовки крупного издательства проходит множество рукописей книг. Эти рукописи необходимо распределять между сотрудниками. Каждая рукопись может быть охарактеризована оценками по таким критериям, как важность, срочность выполнения, тематика.В свою очередь, сотрудники могут быть охарактеризованы оценками по таким критериям, как качество работы, индивидуальная «пропускная способность», предпочитаемая тематика и т.д. Необходимо так распределить рукописи среди сотрудников, чтобы получить приемлемое качество выполнения всех работ при минимальных ресурсных затратах.

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

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

Предъявляя требования к качеству назначений, т.е. к степени соответствия характеристик элементов двух множеств, допустимой при образовании пар, ЛПР формирует область допустимых решений (ОДР), определяя обязательные назначения или исключая недопустимые с его точки зрения пары. ЛПР, формируя назначения в ОДР, стремится к одному из возможных решений, при котором нельзя улучшить качество назначения для какой-либо пары элементов, не ухудшив при этом качество назначений для других пар. Назовем такие решения эффективными.

Среди эффективных решений ЛПР стремится отыскать такое, которое позволяет получить максимальное количество наилучших возможных назначений.Учитывая описанные выше особенности, сформулируем содержательную постановку МЗН в следующем виде. Дано: элементы двух множеств, n субъектов и n объектов, каждый из которых характеризуется совокупностью оценок по N критериям; Требуется: на основе предпочтений ЛПР сформировать область допустимых решений и найти в этой области эффективное решение с максимально возможным числом наилучших, с точки зрения ЛПР, назначений.

Чтобы сформулировать формальную постановку МЗН, введем следующие понятия, термины и обозначения.Имеются два исходных множества по n элементов: С{n} и O{n}. Обозначим: { …,…,} – первое множество, элементы которого назовем субъектами; { …,…,}– второе множество, элементы которого назовем объектами.

Имеется множество из N критериев оценки субъектов и объектов. Каждая оценка на шкале критерия имеет две формулировки, отражая взаимные требования и возможности элементов двух множеств. Шкалы критериев — порядковые, с небольшим, как правило, числом оценок, упорядоченных от лучшей к худшей. Лучшая оценка имеет ранг, равный единице. Оценки могут быть как словесные, так и численные.Часть критериев отражает требования субъектов и возможности объектов, другая часть – требования объектов и возможности субъектов.

Введем следующие обозначения: { } – множество оценок на шкале k-го критерия; – m-я по порядку оценка на шкале k-го критерия; – р-я по порядку оценка на шкале требований i-го элемента по k-му критерию; – t-я оценка на шкале возможностей j-го элемента по u-му критерию.Назовем критериальным соответствием (КС) различие по одному из критериев между требованиями субъекта (объекта) и возможностями объекта (субъекта). Требования i-го элемента по k-му критерию () удовлетворены возможностями j-го элемента по k-му критерию (), если р > t. При этом критериальное соответствие идеально.

Назовем назначением любую пару {, }, образованную двумя элементами, принадлежащими разным исходным множествам.Имеется множество из (n*n) назначений {, }, i, j = 1,2 n, для двух исходных множеств по n элементов: С{n} и O{n}. Идеальным назначением назовем пару {, }, для которой взаимные требования полностью удовлетворены по всем критериям, т.е. все КС идеальны.

Назовем решением многокритериальной задачи о назначениях единичную диагональную матрицу MS(n*n), диагональные элементы которой соответствуют назначениям, формирующим решение. Заметим, что количество возможных решений для размерности исходных множеств С{n} и O{n} равно n что и вызывает (в общем случае) существенные трудности при решении МЗН большой размерности. Идеальным решением назовем решение МЗН, все назначения которого идеальны.Руководителя, ответственного за решение задачи, будем, как и ранее, называть ЛПР. Предположим, что назначения могут быть проранжированы, т.е. каждому возможному назначению может быть присвоен ранг, отражающий его качество с точки зрения ЛПР. Тогда любое решение МЗН может быть охарактеризовано совокупностью рангов отдельных назначений, сформировавших решение.

Теперь можно сформулировать МЗН в следующем виде. Дано: два множества: (i=l,2 n) и (j=l,2 n); оценка каждого элемента двух множеств по N критериям (,…,). Требуется: на основе предпочтения ЛПР определить и выбрать из множества эффективных решений такое, для которого сумма рангов лучших S назначений (S ( n) минимальна). В однокритериальной задаче о назначениях задана стоимость образования той или иной пары, например стоимость исполнения каждой из работ каждым из исполнителей. Задан также целостный критерий – минимум стоимости выполнения всей совокупности работ.

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

Далее мы будем использовать однокритериальную задачу о назначениях как вспомогательное средство при решении существенно более сложной многокритериальной задачи, изложенной выше. МЗН занимает промежуточное положение между задачами принятия индивидуальных и коллективных решений. Действительно, ЛПР стремится найти наибольшее число максимально удовлетворенных субъектов и объектов, основываясь на характеристиках, отражающих интересы и индивидуальные предпочтения субъектов и объектов.

Но в ситуациях, требующих выбора, ЛПР руководствуется своими предпочтениями. Рассмотрим задачу назначения трех сотрудников организации на три вакантные должности. С одной стороны, претендент на каждую должность обязан соответствовать определенным требованиям. С другой стороны, руководитель стремится предоставить каждому сотруднику должность, соответствующую его возможностям.Предположим, что эксперты совместно с ЛПР, ответственным за назначения, разработали следующие критерии для оценки соответствия субъектов (назначаемых) и объектов (должностей). Профессиональная подготовленность: 1)высокая; 2) удовлетворительная.

Умение руководить коллективом: 1) хорошее; 2) удовлетворительное. Практический опыт: 1) большой; 2) небольшой; 3) отсутствует.Приведем для примера формулировку оценок на «зеркальных» шкалах критерия «Профессиональная подготовленность». Шкала требований: 1) требуются работники с высокой профессиональной подготовкой. 2) достаточна удовлетворительная профессиональная подготовка. Шкала возможностей: 1) претендент обладает высокой профессиональной подготовкой. 2) профессиональная подготовка претендента удовлетворительна.

Предположим, что эксперты охарактеризовали возможности субъектов следующими оценками по выбранным критериям: =(2; 1; 2); =(2; 2; 2); =(2; 2; 3). (Цифры в скобках обозначают номера вербальных оценок на приведенных выше шкалах критериев.) Например, второй субъект () имеет удовлетворительную профессиональную подготовку, удовлетворительное умение руководить коллективом и небольшой практический опыт. Характеристики объектов: =(l; 1; 2); =(2; 1; 2); =(2; 2; 2). Эти характеристики выражают должностные требования.

Так, для занятия должности требуется субъект, для которого достаточно иметь удовлетворительную профессиональную подготовку, необходимо хорошее умение руководить коллективом и достаточен небольшой практический опыт. Возникает вопрос: как найти наилучшее решение МЗН в данных условиях? 1.2 Методы решения задач, оптимизации процесса назначения Для решения задач существуют множество различных методов, вот некоторые из них: венгерский метод, симплекс-метод, модифицированный симплекс-метод.

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

Если в исходной системе ограничений присутствовали знаки «равно» или «больше либо равно», то в указанные ограничения добавляются искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума. Формируется симплекс-таблица. Рассчитываются симплекс-разности. Принимается решение об окончании либо продолжении счёта. При необходимости выполняются итерации.На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса.

Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом. В основу модифицированного симплекс-метода положены такие особенности линейной алгебры, которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы. В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам.Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Хорош для ситуаций, когда число переменных n значительно превышает число ограничений m. В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс-разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана-Гаусса.

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

Суть венгерского метода состоит в следующем: путем прибавления определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так называемых независимых нулей.Набор нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные xij равными 1, а все остальные – равными 0, согласно утверждению 2, получим оптимальный план назначения. Алгоритм венгерского метода состоит из предварительного шага и не более, чем (n-2) последовательно повторяющихся итераций.

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

Как только число независимых нулей k станет равным размерности матрицы (k=n), задача решена. Оптимальный план назначения определится положением независимых нулей на последней итерации.  1.3 Экономико-математическая модель Задача о назначениях – это РЗ, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе.

То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем ТЗ. Задача о назначениях имеет место при назначении людей на должности или работы, автомашин на маршруты, водителей на машины, при распределении групп по аудиториям, научных тем по научно-исследовательским лабораториям и т.п. Исходные параметры модели задачи о назначениях 1. n – количество ресурсов, m – количество работ. 2.  – единичное количество ресурса , например: один работник; одно транспортное средство; одна научная тема и т.д. 3.  – единичное количество работы , например: одна должность; один маршрут; одна лаборатория. 4. – характеристика качества выполнения работы с помощью ресурса . Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой.

Искомые параметры: 1.  – факт назначения или неназначения ресурса на работу: 2. L(X) – общая (суммарная) характеристика качества распределения ресурсов по работам.

Общий вид транспортной матрицы задачи о назначениях приведён ниже (см. таблицу 1.1). Таблица 1.1 – Матрица задачи о назначениях Ресурсы, Работы, Bj Количество ресурсов …… …… 1 …… 1 …… …… …… …… …… …… …… 1 Количество работ 1 1 …… 1 Модель задачи о назначениях: (1.1) … Специфическая структура задачи о назначениях позволила разработать так называемый «Венгерский метод» ее решения.

Поэтому, хотя в Excel такие задачи решаются обычным симплекс-методом, требуется построить модель задачи о назначениях вида (1.1). В некоторых случаях, например, когда  – это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ, в отличие от (1.1). В этом случае ЦФ L(X) заменяют на и решают задачу с ЦФ , что равносильно решению задачи с ЦФ. 2 Практическая реализация задачи оптимизации процесса назначения 2.1 Постановка задачи оптимизации процесса назначения Компания Beta Motor Company имеет 4 различных сборочных линии на своём главном заводе.

Управляющий производством имеет 5 служащих и желает назначить по одному служащему к каждой из сборочных линий. Каждый из этих служащих может работать на любой сборочной линии, но с различными затратами, связанными с индивидуальным опытом и мастерством.Эти затраты приведены ниже в таблице (см. таблицу 2.1). Таблица 2.1- Условие задачи Сборочная линия 1 2 3 4 Служащий 1 23 19 22 27 Служащий 2 18 22 20 18 Служащий 3 25 20 22 30 Служащий 4 20 24 24 28 Служащий 5 16 18 20 25 Необходимо управляющему производством прикрепить служащих к сборочным линиям таким образом, чтобы минимизировать общие затраты. 2.2 Разработка экономико-математической модели задачи оптимизации процесса назначения Введем переменные следующим образом: , если i-тый служащий назначается на k-тую производственную линию, в противном случае.

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

Тогда ограничения задачи будут выглядеть следующим образом: – сотрудник не может быть назначен на две линии одновременно, кроме того, один из сотрудников останется не назначенным; – на каждую линию будет назначен обязательно один сотрудник; – ограничения на переменные по условию. Задача состоит в минимизации общих затрат на производство.Поэтому в качестве целевой функции получаем следующее выражение: Теперь мы имеем все, что было необходимо и можем приступить к решению задачи в Excel. 2.3 Решение задачи оптимизации процесса назначения Для поиска оптимального решения задачи воспользуемся Microsoft Excel. Excel – универсальное программное средство, предназначенное для электронной обработки данных.

Для поиска решения необходимо: 1)ввести данные в ячейки рабочего листа Excel. 2)разместить блоки ячеек на рабочем листе Excel, необходимые для моделирования назначения служащих, а так же для формирования математической модели и целевой функции. 3)сформировать на рабочем листе Excel элементы математической модели и целевую функцию. 4)настроить программу «Поиск решения» и выполнить её. В начале создём блок в 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). Рисунок 2.8 – Решение Самым оптимальным решением задачи будут следующие назначения: 1)на линию 1 – Служащий 5; 2)на линию 2 – Служащий 1; 3)на линию 3 – Служащий 3; 4)на линию 4 – Служащий 2; 5)Служащий 4 не будет назначен ни на одну линию.

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

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

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

Библиографический список 1) Акулич И.Л. Математические методы и компьютерные технологии решения оптимизационных задач. – М.: «Высшая школа», 2000. – 243с. 2) Акулич  И.А. Математическое программирование в примерах и задачах. – М.: «Высшая школа», 1986. – 319с. 3) Бронштейн И.Н. Справочник по математике для инженеров и учащихся вузов. – М.: «Наука», 1981. – 722с. 4) Гольштейн Е.Г. «Задачи линейного программирования транспортного типа». – М.: «Москва», 1993. – 253с. 5) Кравец О.Я. Основы математической экономики: практикум. – Воронеж: «Научная книга», 2007. – 188с. 6) Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. – Мн.: «Выш. шк.», 1984. – 256с. 7) Таха Х. Введение в исследование операций: в двух книгах. – М.: «Мир», 1985. – 321с. 8) Фролькис В,А. Введение в теорию и методы оптимизации для экономистов. – СПб.: «Питер», 2002. – 320с. 9) Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 1998. – 141с.