УЧЕБНИКИ 3 Экономика / Управленческие решения / Степанов А.Г. Разработка управленческого решения средствами пакета Excel. 2001

честве bi (1 ≤ i≤ m) . Имеющиеся ресурсы используются для выпуска n видов продукции, причем для выпуска единицы j-го вида продукции необходимо aij единиц i-го вида ресурса. Кроме этого, известен вклад единицы продукции ci в целевую функцию. Требуется определить сколько какого вида продукции следует произвести, чтобы обеспечить максимум критерия оптимальности (3.1). Так, например, если m = 9, n = 4, количество имеющихся ресурсов описывается набором значений b = {30,52; 51,11; 31,23; 26,28; 39,40; 57,47; 53,61; 44,30; 84,54}; матрица коэффициентов aij имеет вид табл. 3.2. в которой столбцы имеют смысл вида соответствующей продукции, а строки – вида ресурса. Коэффициенты значимости каждого вида продукции ci имеют значения {9,20; 7,15; 6,01; 7,61}; решением задачи является набор переменных X = {1,13; 0,00; 0,00; 3,10}, обеспечивающий оптимальное значение целевой функции округленно равное 33,97 при общем суммарном расходе ресурсов равном 185,59. Здесь и далее в этом подразделе для непосредственных вычислений использованы средства надстройки Поиск решения табличного процессора Excel, методы работы с которой подробно описаны ниже.

Таблица 3.2

Расход ресурса на производство единицы продукции

aij	1	2	3	4
1	1,10	6,09	6,56	2,63
2	7,08	7,02	8,95	5,93
3	1,45	7,49	6,51	9,56
4	9,81	9,60	9,14	4,91
5	1,44	3,38	3,06	8,15
6	7,42	1,92	3,66	2,03
7	9,83	2,22	8,62	5,82
8	6,78	5,43	5,19	1,07
9	6,35	5,14	3,81	1,13

Существует и другая постановка задачи – при заданном результате С минимизировать используемые ресурсы, выраженные в одинаковых единицах измерения

51

		m	n
	E = ∑∑		aij x j → min,
		i=1 j=1
		n
		gi = ∑ c j x j ≥ C.
		j=1

Результатом решения этой задачи при тех же исходных данных в

допущении C=33,0 является набор переменных X = {1,01; 0,00; 0,00; 3,11}, обеспечивающий расход ресурсов равный 180,14. Если задать C = 33,97, результат решения второй задачи совпадает с первым.

Примером практических задач распределения ресурсов могут быть задачи, связанные с производством продукции на основе спецификаций и учета дополнительных ограничений, например трудовых затрат, расхода электроэнергии, производственных и складских площадей и т.п. Строки ограничений рассматриваются как наличие соответствующего ресурса, коэффициенты aij имеют смысл его расхода на выпуск единицы продукции, а сами переменные xj – количество продукции j-го вида. Коэффициенты ci могут определять доходность соответствующего вида продукции. Вариантами подобных задач могут быть задачи планирования загрузки оборудования, составления продуктовых наборов и меню комплексных обедов, определения объема выпуска продукции, в состав которой входят ингредиенты в соответствии с рецептурой.

Задача о назначениях

Задача о назначениях обычно рассматривается как задача выбора наилучшей комбинации распределения ресурсов. Пусть имеется n работ и n кандидатов для выполнения этих работ [15]. Назначению i-го кандидата на j-ю работу соответствует определенная прибыль cij. Каждого кандидата можно назначить только на одну должность и только один раз, а каждая работа может быть выполнена только один раз. Из сказанного следуют два ограничения

∑n	xij = 1, ∑	n	xij = 1.	(3.9)
i=1		j=1

Переменные xij принимают значение 1 в том случае, когда кандидат i назначается на работу j и равны нулю во всех остальных случаях, что

52

переводит задачу в категорию дискретных задач математического программирования. Целевая функция задачи в этом случае может быть записана как

n	n
E = ∑∑	cij xij → max,	(3.10)

j=1 i=1

а выражения (3.9) формулируются в виде ограничений. Так, например, если n = 4, матрица весовых коэффициентов cij. имеет вид табл. 3.3, в которой столбцы соответствуют кандидатам на должности, а строки – самим должностям. Результат решения X представлен в табл. 3.4, а показатель эффективности имеет значение 2,93. Очевидно, что все кандидаты получили предложение занять должность.

Таблица 3.3

Таблица 3.4

Значения прибыли

от назначения кандидата на соответствующую работу

cij	1	2	3	4
1	0,00	0,72	0,73	0,78
2	0,55	0,58	0,86	0,96
3	0,02	0,90	0,68	0,68
4	0,00	0,92	0,48	0,05

Оптимальный вариант назначения кандидатов на должности (решение)

			1	2	3	4
X
1			0	0	0	1
2			1	0	0	0
3			0	0	1	0
4			0	1	0	0

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

m			n		{0,1}.
∑	x	≤ 1,	x = 1, x =
	ij	∑	ij	ij
i=1			j=1

Решение открытой задачи о назначениях позволяет формализовать процедуру отбора кандидатов на имеющиеся вакантные места. В этом случае матрица весовых коэффициентов cij имеет вид табл. 3.5, резуль-

тат решения X представлен в табл. 3.6 из которой следует, что кандидат 1 должности не получает, а показатель эффективности имеет значение 2,93.

53

Таблица 3.5

Таблица 3.6

Значения прибыли

от назначения кандидата

на соответствующую работу в открытой задаче

cij	1	2	3	4	5
1	0,00	0,72	0,73	0,78	0,29
2	0,55	0,58	0,86	0,96	0,37
3	0,02	0,90	0,68	0,68	0,33
4	0,00	0,92	0,48	0,05	0,58

Оптимальный вариант

назначения кандидатов

на должности (решение) в открытой задаче

					!	"	#
:
!
"

Примерами практических задач о назначениях могут быть задачи размещения туристов в гостинице, распределения отпусков сотрудников, составления графика дежурств.

Транспортная задача

Транспортной задачей обычно называют задачу о выборе плана перевозок из m пунктов отправления в n пунктов назначения [15]. В качестве условиязадачизадаетсянаборкоэффициентов cij,определяющийстоимость доставки продукции из пункта i в пункт j. Ресурсы продукта в пунктах отправления обозначим ai, а потребность продуктов в пунктах назначения bj. Обычно предполагается, что должна быть выполнена вся программа

перевозок, которая задается в виде ограничений

∑m ai =∑ n b j . i=1 j=1

Целевая функция задачи имеет вид

m	n
E = ∑∑	cij xij → min,

i=1 j=1

где xij – расчетная программа перевозки из пункта i в пункт j. Так, например, если m = 4, n = 5, количество имеющихся ресурсов в пунктах отправления описывается набором значений a ={3,43; 6,56; 1,31; 6,43}; потребность в ресурсах в пунктах назначения описывается набором значений b ={1,72; 4,92; 3,38; 1,89; 5,83}; матрица коэффициентов cij имеет вид табл. 3.7, в которой столбцы соответствуют номерам пунктов отправления, а строки – номерам пунктов назначения. Тогда решением

54

задачи X является набор переменных табл. 3.8, обеспечивающий значение целевой функции округленно равное 71,08, смысл которого сводится к оптимальному объему перевозки из соответствующего пункта отправления в соответствующий пункт назначения.

Таблица 3.7

Стоимость перевозки

cij	1	2	3	4
1	2,31	5,85	7,87	6,75
2	1,78	7,14	8,39	1,65
3	8,87	7,14	4,57	4,52
4	6,24	6,63	2,91	4,30
5	6,70	3,12	7,96	1,21

Таблица 3.8

Оптимальный план перевозок

(решение)

X	1	2	3	4
1	0,00	0,41	1,31	0,00
2	3,43	1,49	0,00	0,00
3	0,00	0,00	0,00	3,38
4	0,00	0,00	0,00	1,89
5	0,00	4,66	0,00	1,16

Задача составления смесей

При формулировке задачи [15] составляется набор исходных материалов, характеризующий содержание контролируемых компонент, где aij – содержание i-го компонента в j-м виде исходного материала. Необходимо определить набор xj при условиях

∑n	x j ≤ b1∑,	n	aij x j≥ bi ,1≤ ≤i m,	(3.11)
j=1		j=1

где b1 – общее ограничение массы смеси, bi – минимально необходимое содержание i-го компонента в конечном продукте, обеспечивая

E = ∑n	c j x j → min,
j=1

где cj – расходы на единицу j-го материала. В качестве варианта может рассматриваться задача приготовления заданного объема смеси (в этом случае первое неравенство в (3.11) записывается как строгое равенство). Так, например, если m = 3, n = 6, ограничения описываются набором значений b ={3,78; 2,64; 1,28}; расходы на единицу материала составляют соответственно cj ={7,35; 3,73; 1,87; 6,92; 5,53; 5,83}; матрица коэффициентов aij имеет вид табл. 3.9, в которой столбцы соответству-

55

ют номерам исходных материалов, а строки – номерам ограничений. Тогда решением задачи является набор переменных X = {0,00; 0,00; 2,61; 0,00; 1,17; 0,00}, обеспечивающий значение целевой функции округленно равное 11,36, смысл которого сводится к величине расходов на составление смеси.

Таблица 3.9

Содержание компонентов в исходных материалах

aij	1	2	3	4	5	6
1	1,00	1,00	1,00	1,00	1,00	1,00
2	0,38	0,32	0,73	0,76	0,63	0,49
3	0,89	0,07	0,08	0,76	0,91	0,34

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

Задача о ранце

Как следует из названия, исходно задача рассматривалась как метод выбора набора из имеющегося множества предметов, который может разместиться в некотором заранее заданном объеме (ранце). Пусть имеется некий объем V, который необходимо заполнить различными предметами n типов объемом vj и ценностью cj так, чтобы их суммарная ценность оказалась наибольшей [15]. Тогда в качестве ограничения можно рассматривать выражение

∑n	v j x j	≤	V ,
j=1
а целевая функция
E = ∑n	c j x j	→	max .
j=1

Так, например, если n = 6, объемы предметов определяются значениями vj ={23,49; 43,15; 7,47; 13,46; 41,96; 37,14; 47,86}, ценность предметов значениями cj ={3,45; 2,16; 0,34; 3,30; 5,62; 9,08}, а V = 50, решение задачи будет иметь вид X = {0,00; 0,00; 1,00; 3,00; 0,00; 0,00} при достигнутом значении ограничения 47,86 и целевой функции 10,25.

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

56

Задача банковского взаимозачета

Задача банковского взаимозачета возникает в том случае, когда из имеющегося набора n платежных поручений стоимостью cj, (1 ≤ j≤ n) следует отобрать тот набор платежных поручений, который максимально приблизил бы их к сумме взаимозачета V при наличии ограничения

∑n с j x j ≤ V. j=1

Переменные в этом случае принимают только дискретные значения xj {0,1}, а целевая функция имеет вид

∑n	с j x j → max .
j=1

Задача представляет особый интерес, когда n достаточно велико. Так, например, при n = 25 и значениях cj ={12,07; 15,98; 10,19; 80,79; 46,19; 57,84; 31,08; 41,45; 6,13; 16,46; 47,13; 95,83; 0,46; 65,96; 86,51; 58,11; 40,55; 60,41; 72,52; 51,59; 26,88; 37,24; 26,11; 63,63; 96,62} результат решения X = {0; 0; 0; 1; 1; 1; 0; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 0; 1; 1} обеспечивает значение суммы взаимозачета 965,59 при заданной величине V = 1000.

Задача банковского взаимозачета может рассматриваться как упрощенный вариант открытой задачи о назначениях.

Задача коммивояжера

Имеется n пунктов, связанных между собой дорогами так, что известны затраты на проезд из одного пункта в другой cij. Требуется найти такой маршрут, чтобы стоимость поездки была бы минимальной. Задача имеет много аналогий с транспортной задачей и отличается от нее в первую очередь тем, что искомые переменные принимают только два возможных значения – 1, если перевозка производится и 0, если нет.

Отметим, что каждый пункт маршрута, кроме исходного, должен быть
посещен только один раз. Введем n2 переменных x			{0,1}, удовлетво-
		ij
ряющих ограничениям
∑n	xij = 1, 1 ≤ j≤ n, ∑ n	xij= 1, 1≤ ≤i n.
i=1	j=1

57

Целевая функция задачи имеет вид

n	n
E = ∑∑	cij xij → min.

j=1 i=1

Рассмотрим теперь некоторые дополнительные ограничения. Очевидно, что перевозка внутри одного пункта не требуется. Формально это означает, что

x jj ≡ 0, 1≤ ≤j n.

В табл. 3.10 представлена стоимость перевозки между различными пунктами cij, а в табл. 3.11 – рассчитанный оптимальный маршрут перевозок X , обеспечивающий значение целевой функции 12,38.

Рассчитанный оптимальный маршрут поездок начинается в пункте 1. Затем следует поездка в пункт 2, возвращение в пункт 1, поездка в пункт 6, поездка в пункт 5, поездка в пункт 3. Маршрут завершается в пункте 4. Обычно в задаче коммивояжера рассматривается дополнительное условие: маршрут должен начинаться и заканчиваться в пункте 1. Формально это условие может быть записано как

xi1	0,1	≤ i< n,
	=	= n.
	1, j

В табл. 3.12 представлен оптимальный маршрут перевозок X , начинающихся и заканчивающихся в пункте 1 при тех же исходных данных табл. 3.10. Значение целевой функции в этом случае увеличилось и составляет 15,25.

Таблица 3.10

Стоимость перевозки между пунктами

cij	1	2	3	4	5	6
1	0,00	7,15	7,59	5,55	9,96	8,43
2	3,22	0,00	7,74	9,58	6,01	1,33
3	5,06	9,32	0,00	0,41	9,91	0,10
4	8,55	5,86	1,77	0,00	0,04	9,31
5	7,77	0,64	0,99	7,01	0,00	8,73
6	5,34	4,55	7,22	0,89	2,13	0,00

58

Таблица 3.11

Оптимальный маршрут перевозок

			1		2	3	4		5	6
X
1			0		1	0	0		0	0
2			1		0	0	0		0	0
3			0		0	0	0		0	1
4			0		0	0	0		1	0
5			0		0	1	0		0	0
6			0		0	0	1		0	0
									Таблица 3.12
				Оптимальный маршрут перевозок,
			начинающихся и заканчивающихся в пункте 1
X			1		2	3	4		5	6
1			0		1	0	0		0	0
2			0		0	0	0		0	1
3			0		0	0	1		0	0
4			0		0	0	0		1	0
5			0		0	1	0		0	0
6			1		0	0	0		0	0

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

3.5. Динамические задачи разработки управленческого решения

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

59

кой особенностью которого является то обстоятельство, что расходом этого ресурса невозможно управлять. Учет времени как ресурса оказывается принципиальным для целого класса задач, в основе которых лежит требование минимизации времени, затрачиваемого на выполнение работы. К числу таких задач следует отнести в первую очередь задачи управления проектами [16, 17], а также задачи, описываемые методами теории массового обслуживания [18].

Другой класс динамических задач представляют задачи, требующие учета меняющихся во времени параметров для отыскания решений, в общем случае являющихся также функциями времени. Методы решения подобных задач опираются на теорию вариационного исчисления, теорию оптимального управления [19–21], в основе которых лежит предположение о возможности описания поведения объекта системой дифференциальных уравнений. Подобная гипотеза бывает допустимой в тех случаях, когда в роли объекта управления выступает так называемое физическое тело с конечной массой, обладающее свойством инерционности. Это допущение невсегда справедливо в менеджменте, объектом которого являются социально-экономические системы. Тем не менее, и в этом случае можно выделить достаточно много задач, решение которых может быть осуществлено упомянутыми способами.

Специфической особенностью динамических задач в менеджменте часто является их дискретность. Методы исследования поведения объектов управления при дискретном их описании достаточно хорошо разработаны применительно к бесконечным выборкам [22].

Особенности задач менеджмента часто заставляют учитывать принципиальную конечность числа отсчетов временных функций. В этом случае приходится принимать во внимание положения теории дискретных конечных выборок [23].

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

еемоделирования [13].

Отметим, что строгая классификация методов решения динамичес-

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

60