Задача о распределении специалистов, как пример альтернативной экономической интерпретации транспортной задачи

Рассмотрим пример использования транспортной модели в ситуации, не связанной с перевозкой продукции.

Например, рассмотрим следующую экономическую ситуацию:

Специалистов n различных групп нужно распределить наиболее эффективным образом по m видам работ. Задана матрица эффективности использования специалиста i-й группы на j-м виде работ c_ij. Кроме того, задано общее количество специалистов каждой группы a_i, и общая потребность в работниках по каждому виду работ b_j, .

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

(8)

Например, НИИ разрабатывает 2 научные программы для молодых ученых, к которым необходимо привлечь соответственно 10 и 7 человек. На участие в них претендуют выпускники аспирантуры 4 учебных заведений, по 5 человек из каждого. Экспертная комиссия пришла к выводу, что эффективность использования одного выпускника каждого учебного заведения в программе № 1 может быть оценена по 5-балльной шкале соответственно в 2, 3, 5 и 1 балл. Для программы № 2 эти оценки составят 3, 1, 5 и 2 балла. Необходимо распределить молодых ученых по научным программам наиболее эффективным образом.

Для построения модели введем переменные x_ij - количество выпускников i-го учебного заведения, направляемых на j-ю программу. Модель примет вид:

min (2x₁₁ + 3x₁₂ + 3x₂₁ + x₂₂ + 5x₃₁ + 5x₃₂ + x₄₁ + 2x₄₂)

x₁₁ + x₁₂ 5

x₂₁ + x₂₂ 5

x₃₁ + x₃₂ 5

x₄₁ + x₄₂ 5

x₁₁ + x₂₁+ x₃₁ + x₄₁ 10

x₁₂ + x₂₂+ x₃₂ + x₄₂ 7

Задача (8) разрешима при тех же условиях, что и модель (1). Действительно, если общая потребность в работниках не превышает общего числа специалистов, то ее ОДП не пуста (система ограничений здесь такая же, как в модели (1)). Однако целевая функция здесь не минимизируется, а максимизируется. Может ли она быть не ограничена сверху? Нет, не может. Если выбрать в матрице коэффициентов целевой функции самый большой элемент {c_ij} и предположить, что каждого специалиста каким-то образом удалось устроить на работу с этой самой большой эффективностью, то мы получим суммарную величину эффективности путем умножения {c_ij} на общее число специалистов . Значение целевой функции не может быть больше этой величины. В рассмотренном примере самая большая оценка – 5 баллов, а молодых ученых – 20 человек. Следовательно, суммарная эффективность не может превысить 20 * 5 = 100.

Взяв коэффициенты целевой функции с противоположным знаком, эту задачу можно поставить на min, и тогда очевидна ее эквивалентность транспортной задаче (1).

Транспортная задача в традиционной интерпретации (о перевозках) также может быть поставлена на максимум. Предположим, что коэффициенты целевой функции c_ij представляют собой не затраты на перевозку единицы продукции от i-го поставщика к j-му потребителю, а прибыль от реализации единицы продукции i-го поставщика у j-го потребителя. Целью операции будет получение наибольшей прибыли, т.е. max .

Особый класс транспортных задач представляют собой задачи о назначениях*.

3.5 Опорный план транспортной задачи

Метод решения транспортной задачи представляет собой развитие идеи симплекс-метода [3] и тоже основан на переборе опорных планов этой задачи. Опорный план должен включать столько базисных переменных, сколько в задаче линейного программирования независимых уравнений.

Если бы система ограничений закрытой транспортной задачи была линейно независимой, то базисных переменных было бы m+n. Но из задач (6) и (7) видно, что такая система линейных уравнений является линейно зависимой (например, если сложить все ограничения из первой и все из второй группы, а затем вычесть из одной суммы другую, в левой части получится ноль). Можно доказать, что если удалить из системы одно ограничение, то она станет независимой (одно ограничение является лишним, оно следует из остальных). Следовательно, базисных переменных должно быть m+n-1.

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

3.5.1 Метод северо-западного угла построения опорного плана транспортной задачи

Этот метод принято сокращенно обозначать МСЗУ.

Представим опорный план транспортной задачи в виде таблицы, строки которой будут соответствовать поставщикам (с их запасами a_i), столбцы – потребителям (с их потребностями b_j), а ячейки – компонентам опорного плана (например, в первой строке первого столбца будет стоять значение переменной x₁₁). Будем заполнять лишь те ячейки, которые будут соответствовать базисным компонентам, переменные в незаполненных ячейках равны нулю.

	x11					a1
						a2
						an
	b1	b2			bm

Применение метода начинают с того, что рассматривают левый верхний («северо-западный») угол таблицы, который соответствует переменной x₁₁, т.е. перевозкам от первого поставщика к первому потребителю. Сравнивают их запас и потребность - a₁ и b₁.

1). Если a₁ < b₁, то x₁₁ = a₁, т.е. всю продукцию первого поставщика отправляют к первому потребителю.

После этого первую строку исключают из рассмотрения (все остальные x_1j = 0). В самом деле, ведь запасы первого поставщика уже закончились. Следовательно, больше никому ничего везти от него нельзя.

Первому столбцу вместо b₁ ставят в соответствие b₁`= b₁ - a₁, поскольку потребность первого потребителя снизилась (она уже частично удовлетворена).

Затем снова рассматривают левый верхний угол оставшейся части таблицы (без первой строки), т.е. х₂₁.

2). Если a₁ > b₁, то x₁₁ = b₁., т.е. первого потребителя полностью удовлетворяют за счет запасов первого поставщика, после чего этого потребителя (первый столбец) исключают. Запасы первого поставщика уменьшаются a₁`= a₁ - b ₁.

Затем рассматривают левый верхний угол оставшейся части таблицы (без первого столбца), т.е. х₁₂.

3). Если a₁ = b₁, то можно исключить либо столбец, либо строку.

Далее действуют аналогично, т.е. либо принимают х₂₁ = min {b₁`;a<sub>2</sub>}, либо принимают х<sub>12</sub> = min {b<sub>2</sub>; a<sub>1</sub>`}. Процесс продолжается до тех пор, пока не будут исключены из рассмотрения все ячейки. При этом окажется заполненной m+n-1 клетка таблицы.

Рассмотрим применение данного метода к задаче о холодильных установках. Для этого необходимо построить таблицу из трех строк и столбцов, соответствующих шести центрам производства и сбыта (включая дополнительный). Чтобы построить опорный план, необходимо заполнить
3 + 3 – 1 = 5 клеток этой таблицы.

Ее левый верхний угол будет соответствовать поставкам холодильных установок из Стокгольма в Лейпциг (переменной x₁₁). Так как в Стокгольме производится меньше установок, чем необходимо поставить в Лейпциг
(a₁ < b₁, 120 < 150), то направим все эти 120 установок в Лейпциг (x₁₁ = 120). После этого Стокгольм (первую строку таблицы) можно исключить из рассмотрения, так как холодильных установок в этом центре сбыта больше не осталось. В Лейпциг же необходимо поставить еще 150 – 120 = 30 установок, поэтому Лейпцигу (первый столбец) ставится в соответствие новое значение потребностей – 30:

	Лейпциг	Лион	дополнительный центр сбыта
Стокгольм
Триест
Руан
	150 30

Левый верхний угол новой таблицы соответствует поставкам продукции из Триеста в Лейпциг. Так как min{30; 40} = 30, в Лейпциг направляется 30 установок (x₂₁ = 30), после чего потребности Лейпцига удовлетворены полностью, и второй столбец можно исключить из рассмотрения. В Триесте осталось 10 установок:

	Лейпциг	Лион	дополнительный центр сбыта
Стокгольм
Триест				40 10
Руан
	150 30

Аналогично поставки продукции из Триеста в Лион принимают равными 10 (x₂₂ = 10), а из Руана в Лион – 80 (x₃₂ = 80). После этого в Руане остается еще 10 установок, которые следует перевезти в дополнительный центр сбыта (т.е. потребность в них в рамках данной модели на самом деле отсутствует) - x₃₃ = 10. После этого можно будет исключить из рассмотрения и последний столбец:

	Лейпциг	Лион	дополнительный центр сбыта
Стокгольм
Триест				40 10
Руан				90 10
	150 30	90 80

Итак, заполнены пять клеток таблицы, соответствующие базисным переменным. Остальные четыре переменные являются небазисными и равны нулю (x₁₂ = x₃₁ = x₁₃ = x₂₃ = 0), т.е. при таком плане перевозок из Стокгольма в Лион и из Руана в Лейпциг холодильные установки не перевозятся, при этом из Стокгольма и Триеста вывозятся все установки, излишков не остается.

Получен допустимый план, который можно использовать в качестве опорного и начать с него решение задачи. Впоследствии от этого плана мы будем переходить к другим, более дешевым. Чтобы наглядно убедиться, что впоследствии мы получим более выгодные планы перевозок, можно подсчитать, во сколько обойдется оплата перевозок по плану, построенному МСЗУ. Для этого подставим его в целевую функцию задачи: 25x₁₁ + 14x₁₂ +
+ 18x₂₁ + 8x₂₂ + 12x₃₁ + 6x₃₂ = 25*120 + 18*30 + 8*10 + 6*80 = 4100 (ф.ст.)