Диссертация (1172887), страница 17

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 17)

Вершина i первого уровня соединена дугой (i, j) с вершиной j второго уровня, если сотрудник i может занимать должность j.121Числа у дуг равны уровню 2 компетентности сотрудника на соответствующей должности.Обозначим xij = 1, если сотрудник i назначен на должность j, xij = 0 впротивном случае.Задача 1. Определить x  ( xij ), i  1, n, j  1, n , минимизирующиеB  x   xij cij ,(3.8)i, jaij , если iЄPi ,где сij  bij , если iЄRi ,при ограниченияхx 1,(3.9)ij 1,(3.10)ijМ ,(3.11)ijixjx Kiji, j1, если iЄPi ,где Kij   2, если iЄRi .Если бы не было ограничения (3.11), то это была бы обычная задачаназначения [4]. C учетом (3.11) задача становится сложной задачей дискретной оптимизации.Рассмотрим сначала частный случай, когда при любом назначении надолжность сотрудников с высоким уровнем компетентности на остальныедолжности всегда можно назначит сотрудников с нормальным уровнем компетенции.

В этом случае задача сводится к задаче назначения сотрудников свысоким уровнем компетенции, то есть к задаче минимизации:x iji iЄRiпри ограничениях (3.9)j(3.12)122xij 1,(3.13)jx kij ijM n N .(3.14)i iЄRiЭта задача определения потока заданной величины и минимальнойстоимости.Сначала удаляем из графа все дуги, соответствующие нормальномууровню компетенции. При этом исключаем вершины первого уровня, из которых не исходит ни одной дуги с kij = 2, и вершины второго уровня, в которые не заходит ни одна дуга с kij = 2.

Полученный граф приведен на рис. 3.7.Пусть вершины пронумерованы в порядке возрастания ∆j.Определение. Чередующейся цепью (i, j) называется цепь, соединяющая вершину i первого уровня с вершиной j второго уровня, причем длиныребер (k, s), где k – вершина второго уровня, а s – вершина первого уровня,равны (-∆k).Лемма 1. Длина любой чередующейся цепи µ(i, j) равна ∆j.Доказательство. Пусть (s, k), (k, r) два смежных ребра цепи, причем k –вершина второго уровня.Длина в цепи (s, k, r) равна l (s, k, r) = ∆k + (-∆k) = 0.Поэтому длина всей цепи µ(i, j) равна ∆j.12311234455Рис.

3.7Описание алгоритмаРассматриваем вершины второго уровня в порядке возрастания номеров. Пусть уже рассмотрены m вершин, причем число назначенных специалистов второго уровня компетентности равно Nm < N.(k + 1)-шаг. Рассматриваем вершину (m + 1). Находим любую чередующуюся цепь из вершин первого уровня в вершину (m + 1). Если такая цепьсуществует, то величина Nm увеличивается на 1, а затраты увеличиваются наΔj . Если Nm + 1 < N, то переходим к следующему шагу. Если такой цепи нет,то переходим к следующему шагу.За конечное число шагов q либо будет получено Nq = N, либо послерассмотрения всех вершин числа N достичь не удается.

В этом случае задачане имеет решения. Меняя N, можно получить зависимость минимальногофонда заработной платы от числа специалистов с высоким уровнем компетентности.Пример 3. Рассмотрим граф (рис. 3.7).Пусть N = 3.1 шаг. Рассматриваем вершину 1.124Цепь (1, 1) существует: N1 = 1 < 3.2 шаг. Рассматриваем вершину 3.Цепь (2, 1, 1, 3) существует: N3 = 2 < 3.3 шаг.

Рассматриваем вершину 4.Цепь (4, 3, 1, 4) существует: N4 = 3 = N.Задача решена. Минимальные затраты составила 8 единиц.Рассмотрим трехбалльную шкалу оценок компетентности и соответственно трехставочную систему оплаты труда. Обозначим aj, bj, dj ставкиоплаты при уровнях компетентности 1, 2 и 3 соответственно. Определимтакже три уровня компетентности подразделения (организации) в целом.Пусть А1, А2 граничные значения взвешенной суммы компетентностей:N  n1  2n2  3n3.Рассмотрим приближенный алгоритм решения задачи, в основе которого лежит метод множителей Лагранжа.

Обозначим λ – множитель Лагранжа ирассмотрим функцию Лагранжа:Ф( x,  )   cij xij    kij xij  N   ,i, j  i, j (3.15)где N = А1, если поставлена задача обеспечить повышенный уровень компетентности персонала подразделения, и N = А2, если поставлена задача обеспечить высокий уровень компетентности персонала подразделения.Рассмотрим задачу максимизации:£     min Ф( x,  )x(3.16)при ограничениях (3.9), (3.10).Как известно, £    является оценкой снизу для исходной задачи.Наилучшую оценку дает решение задачи максимизации £    .

Заметим теперь, что при фиксированном  мы получаем обычную задачу назначения[4].Лемма 2. £    - кусочно-линейная вогнутая функция  .125Доказательство. Рассмотрим все решения задачи назначения в зависимости от  .Оптимальные решения определяются нижней огибающей всех линейных графиков решений.Очевидно, что это кусочно-линейная вогнутая функция  .Лемма 3. Если при   0 в оптимальном решении задачи назначениявыполняется неравенство (3.11), то полученное решение является оптимальным для исходной задачи.Доказательство очевидно, поскольку увеличение  приводит только куменьшению £    .

Поэтому нижняя оценка совпадает с целевой функциейзадачи, является достижимой, а само решение является оптимальным.Обозначим Δj1 = bj- aj; Δj2 = (dj- aj); Δj3 = dj - bj.При λ = Δj1 имеет место aj - λ = bj - 2 .При λ = Δj2 имеет место aj - λ = dj - 3 .При λ = Δj3 имеет место bj - 2λ = dj - 3 .При этих значениях λ происходит смена приоритетов. Так, при λ > Δj1на должность j становится более выгодным назначать сотрудника с повышенным уровнем компетентности, чем с нормальным.

При λ > Δj2 становитсяболее выгодным назначать сотрудника с высоким уровнем компетентности,чем с нормальным, а при λ > Δj3 выгоднее назначать сотрудника с высокимуровнем компетентности, чем с повышенным.Описание алгоритма1 шаг. Решаем задачу назначения при λ = 0.Если ограничение (3.11) выполнено, то задача решена. В противномслучае переходим к шагу 2.2 шаг. Пусть все Δj1, Δj2, Δj3 упорядочены по возрастанию. ОбозначимY  0   kij xij ,i, jгде x(0) - оптимальное решение задачи назначения при λ1 = 0.(3.17)126Определяем δ = N – Y0. Рассматриваем упорядоченный по возрастаниюряд Δj и определяем сумму si, добавляя 1, если это Δj1 или Δj3 , и добавляя 2,если это Δj2 .Пусть k - минимальный номер в упорядоченном ряде Δj, такой, чтоsk ≥ δ .

Полагаем λ2 равной соответствующей Δj.Замечание. Вычислительные эксперименты показали, что такой выборобеспечивает достаточно быстрое определение оптимального . Во многихпримерах полученная величинабыла оптимальной.Если Y (λ2) ≥ δ , то задача решена.Если Y (λ2) < δ , то полагаемравной следующей величине Δj и повторя-ем шаг 2. За конечное число шагов либо будет получено оптимальное решение,либо будет показано, что требуемый уровень компетентности недостижим.Пример 4. Рассмотрим граф возможных назначений (рис. 3.8).11 2121215433211232462315Рис. 3.8У дуг указаны уровни компетентности. Таблица ставок оплаты приведена ниже (табл.

3.1).Таблица 3.1Примем N = 9.j12345aj12342bj34563dj657841271 шаг. Решаем задачу назначения при λ1 = 0.Первый шаг решения представлен в табл. 3.2.Таблица 3.2ij1211н24345614н3343н8554н3832нВ клетках таблицы записаны ставки оплаты. Буквой «н» обозначеныназначения первого шага. Сразу получено оптимальное решение. Вычисляем:Y  0   1  2  1  1  1  6  9.Вычисляем Δj1, Δj2 , Δj32 шаг. Из табл. 3.3 выбираем λ2 = 1. Значения cij  kij для всех i, j приведены в табл. 3.4.Таблица 3.3jkΔj1Δj2Δj312222,5 1,531322242225111Таблица 3.4ij110н223452345602н22н533н151н1128Оптимальное решение также получено на первом шаге.

Вычисляем:Y 1  1  2  1  1  2  7  9.3 шаг. Берем λ3 = 1,5. Однако при этом λ3 только на одну работу 2 выгоднее назначать специалиста с высоким уровнем компетентности. Но такихспециалистов нет. Поэтому берем λ3 = 2. Значения cij  2 kij для всех i, j приведены в табл. 3.5.Таблица 3.5ij1234512-1н00н13-11н245612-12н-1н 0Вычисляем: Y  2   1  2  1  3  2  9.Посколькуk xij ij 9 , то получено оптимальное решение.i, jРассмотрим непрерывный случай, когда xij могут принимать значенияот 0 до 1. Содержательно это соответствует работе специалиста на определенную долю ставки.

В этом случае задача становится задачей линейногопрограммирования и может быть решена стандартными программами. Однако описанный выше подход к приближенному решению целочисленной задачи на основе применения метода множителей Лагранжа и решения небольшого числа задач назначения можно использовать для определения решениянепрерывной задачи.Опишем соответствующий алгоритм. Пусть λ* - оптимальное значениеλ в задаче нахождения максимина функции Лагранжа, а x1(λ*) - соответствующее решение задачи назначения.129**Если K ( x1 ( ))  ( )) k x ( )  N , то задача решена и x (λ ) - оп**ij ij1i, jтимальное решение исходной задачи.

Характеристики

Список файлов диссертации