Студопедия
МОТОСАФАРИ и МОТОТУРЫ АФРИКА !!!


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

Математическая модель задачи. Ведем переменные xij принимающие два значения:




1) Переменные задачи.

Ведем переменные xij принимающие два значения:

xij=0, если i-й претендент (Pi) не принимается на j-ю вакансию (Vj).

xij=1, если i-й претендент (Pi) принимается на вакансию (Vj).

i=1,2,...7; j=1,2,...5.

2) Ограничения на переменные задачи.

Очевидно, что все переменные задачи неотрицательные и целые числа: xij 0 и xij - целые.

Кроме того, так как каждый претендент может занять только одну вакансию и все вакансии должны быть заняты, должны удовлетворяться следующие ограничения:

, j=1,2,...7 ,

, i=1,2,...5 ,

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

3) Целевая функция в задаче о назначениях.

Необходимо выбрать претендентов так, чтобы суммарное число очков, набранное ими было бы максимальным. Суммарное число набранных очков вычисляется по формуле:

;

Z=c11x11+c12x12+...+c75x75=7x11+5x12+...+4x75;

Окончательная математическая модель задачи записывается так:

найти max ;при ограничениях:

xij 0 и xij - целые числа, i=1,2,...7; j=1,2,...5;

, j=1,2,...7 ;

, i=1,2,...5 .

Таким образом, задача о назначениях есть частный случай транспортной задачи

Решение задачи о назначениях при помощи преобразования матрицы (С).

Рассмотрим решение задачи о назначениях, в которой нужно найти min функции Z. Предварительно задачу о назначениях нужно сбалансировать. В рассматриваемом примере эта процедура выполняется добавлением двух столбцов (две фиктивные вакансии) с нулевыми результатами тестирования:

Задача нахождения минимального значения функции Z эквивалентна задаче нахождения минимума для функции , матрица (-С) имеет вид:

-

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

В рассматриваемом примере в каждой строке матрицы (С) нули есть (они появились в результате добавления фиктивных вакансий). Чтобы образовать нули в первых пяти столбцах матрицы (-С), определяем минимальные элементы в этих столбцах: -8, -9, -8, -9, -9 и вычитаем эти элементы из соответствующих столбцов матрицы. В результате получим следующую матрицу :




С1=
0

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

a) минимальным количеством горизонтальных и вертикальных прямых вычеркиваем все нули.

b) среди не вычеркнутых элементов находим минимальный элемент;

c) вычитаем минимальный элемент из всех вычеркнутых элементов;

d)к элементам, стоящим на пересечении вертикальных и горизонтальных прямых, прибавляем минимальный элемент.

Среди множества получаемых нулевых элементов определяем допустимое решение. Если допустимое решение найти нельзя, повторяем шаги a, b, c, d снова.

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



2
3

Рис.1

Рис.2

Перенеся полученное решение на исходную матрицу (С):

получим, что претенденты Р1 и Р7 попадают на фиктивные вакансии и не принимаются на работу. Р2 принимается на пятую вакансию, Р3 - на первую, Р4 - на третью, Р5 - на четвертую, Р6 - на вторую. Сумма баллов, полученная при данном решении равна: 9+8+8+9+8=42.





Дата добавления: 2015-04-17; просмотров: 1221; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. 9433 - | 7321 - или читать все...

Читайте также:

  1. А. Задачи. 1. Построить гистограмму частот по данной выборке
  2. А. Задачи. 1.Найти доверительный интервал для оценки с надёжностью 0,95 неизвестного математического ожидания нормально распределённого признака X генеральной
  3. Билет 20. 1.структура и динамика издержек в краткосрочном периоде деятельности фирмы: постоянные, переменные, средние
  4. Блокирующие переменные
  5. Внутренние переменные организации
  6. Внутренняя среда организации, ее основные переменные
  7. Внутренняя среда организации. Основные переменные в самой организации это цели, структура, задачи, технология и люди
  8. ВОПРОСЫ И ЗАДАЧИ. От каких причин может происходить дымление печи при се топке?
  9. ВОПРОСЫ И ЗАДАЧИ. Чем объяснить, что теплоотдача 1 м2 различных частей поверхности иагрева одной и той же печи (свободной поверхности
  10. ВОПРОСЫ И ЗАДАЧИ. Что такое коэфициент общей теплопередачи и в каких мерах он выражается ?
  11. Генетика человека и медицинская генетика, их цели и задачи. Человек как специфический объект генетических исследований
  12. Глобальные переменные и константы


 

3.95.131.208 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.003 сек.