УО «ВГУ имени П.М. Машерова» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Курсовая  работа 

     По  методике преподавания информатики

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

                             Выполнил:  студент 4 курса

  математического факультета 

   заочного отделения

     Змушко Роман Николаевич 
 

     Номер зачетки: 1221

     Преподаватель:  Чиркина А.А. 
 
 
 
 
 
 
 
 
 
 
 
 

Витебск

2011 

содержание

 

Введение………………………………………………………………………..3

1 Теоретические основы задачи о назначении……………....4

1.1 Постановка  задачи…………………………………………………………...4

1.2 Методы  решения задач, оптимизации процесса назначения……………..7

1.3 Экономико-математическая  модель…………………………………………8 

2 Практическая реализация задачи назначения……………………………………………………………………..9

2.1 Алгоритм решения задачи о назначениях …………………………………9

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

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

Заключение…………………………………………………………………....21

Библиографический список…………………………………………....22

  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

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

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

       Предметом исследования является решения задачи о назначении в среде

        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) удовлетворительная.