EMMUP(var7)

Шаг 3. Доли приростов численностей работников по категориям (табл. 3.4).

оценивая отношения cik к суммам cik>0 в столбцах.

Доли общего прироста			Таблица 3.4.
Категории работников \ Годы	10/11	11/12	12/13
Производственные рабочие	0	0,78	0,13
Вспомогательные рабочие	0	0	1
Инженерно-технические работники	0,55	0	0,28
Служащие и МОП	0	0	0
Итого:	1,00	1,00	1,00

Шаг 4. Матрицы D(k) изменений соседних пар лет, фиксирующие изменения

в структуре работников по категориям в k-ом периоде от j-го к (j+1) -му году, используя табл. 3.3 и 3.4.

Матрицы D(k) формируем для всех пар лет.

Таблица 3.5.	Таблица 3.6.
Матрица D(1) для 2010/2011 г.	Матрица D(2) для 2011/2012 г.

38,61	0	0	0	38,61
	37,66	0	0	37,66
1,83	0	13,68		15,51
1,36	0	0	6,87	8,23
41,92	37,66	13,68	6,75	100

Таблица 3.7.

Матрица D(3) для 2012/2013 г.

40,46	0	0	0,23	40,69
0	36,64		1,06	37,70
0		16,03	0,51	16,54
0	0	0	5,07	5,07
40,46	36,64	16,03	6,87	100

38,61	1,02	0	0,83	40,46
0	36,64	0	0	36,64
0	0	15,51	0,52	16,03
0	0	0	6,87	6,87
38,61	37,66	15,51	8,23	100

Таблица 3.8.

Матрица Sij за 2010-2013 г.г.

117,67	1,02	0	1,06
0	110,9	0	1,06
2	0	45,21	1,03
1,36	0	0	18,81
120,86	111,96	45,21	21,96

Шаг 5. Матрицу кумулятивных изменений (табл. 3.8) за 2010-2013 г.г.

Sij = d(1)ij + d(2)ij + … +d(n-1)ij; j=1,…,m; j=1,…,m

Шаг 6.	Матрицу тенденций переходов Eij				Таблица 3.9.
		Матрица Sij		за 2010-2013 г.г.
	(табл. 3.9) Eij = Sij / Sm+1j; i=1,…,m; j=1,…,m		0,9736	0,0091	0,0000	0,0483
			0,0000	0,9909	0,0000	0,0483
Шаг 7.	Ретропрогноз tij (табл.3.10), умножая		0,015	0,0000	1,0000	0,0469
	Eij на табл. 3.2.		0,0113	0,0000	0,0000	0,8565
			1,0000	1,0000	1,0000	1,0000

Ретропрогноз tij		Таблица 3.10.
Категории работников \ Годы	2010	2011	2012	2013
Производственные рабочие	41,48	38,33	40,06	40,20
Вспомогательные рабочие	37,64	37,71	36,64	37,61
Инженерно-технические работники	14,63	16,48	16,97	17,40
Служащие и МОП	6,25	7,48	6,34	4,80

Шаг 8. Точность воспроизведения структуры 2010-2013, вычитая табл. 3.2

	из табл. 3.10 (см. табл. 3.11).		Таблица 3.11.
	Ошибки ретропрогноза tij
	Категории работников \ Годы	2010	2011	2012	2013
	Производственные рабочие	-0,44	-0,28	-0,40	-0,49
	Вспомогательные рабочие	-0,02	0,05	0,00	-0,10
	Инженерно-технические работники	0,95	0,97	0,93	0,85
	Служащие и МОП	-0,50	-0,75	-0,53	-0,27
Шаг 9. Средние ошибки по годам: D0 = {		0,48	0,51	0,47	0,43	}

Шаг 10.		Min Dij =	0,00 и Max Dij=	0,97 из табл. 3.11.
		Сложив все Dij и разделив их сумму на число наблюдений,
		найдем Dij =	0,47 %
Шаг 11.		Прогноз структуры на 2014 г., умножив Е на вектор ретро
		прогноза % 2013 г. (табл. 3.11). Результаты в табл. 3.12.
			Прогноз на 2014 г.		Таблица 3.12.
	Категории работников \ Годы			% 2014		Прогноз
	Производственные рабочие			39,71		270
	Вспомогательные рабочие			37,51		255
	Инженерно-технические работники			18,25		124
	Служащие и МОП			4,53		31
	Итого:			100,00		679
Шаг 12.		Прогноз на 2014 год - 679		человек (см. табл. 3.12).

Задача 2.1

Оптимизация использования целочисленных ресурсов

Постановка задачи

Найти число рейсов xj (j=1,n) m ВС по n ВЛ; если известны: bi - запасы ресурсов i=1,m; pj - прибыль от выполнения рейса по j-ой ВЛ; aij - нормы расхода i-го ресурса. Множество xj должно обеспечить max прибыли Z.

Модель задачи имеет вид:

Z =	2	x +	5	x +	9	x → max
		1		2		3
при	0	x1 +	1	x2 +	2	x3 ≥ 12
	0 x1 +		2	x2 +	-1	x3 = 8
	5 x1 +		1	x2 +	1	x3 ≤ 15
x1 ≥ 0,	x2 ≥ 0,		x3 ≥ 0, −		целые числа

Шаг 1.							Алгоритм решения задачи:
		Вводим х4, х5, х6 ≥ 0 в ограничения и в Z
			Z = 2 x1 +				5 x2 +9			x3 + 0(x4 + x5 + x6 )→ max
				0 x1 + 1 x2 +2						x3 +			x4			≥ 12
				0 x1 + 2 x2 +-1						x3 +		+		x5		= 8
				5 x1 + 1 x2 +1						x3				+		x6 ≤ 15
Шаг 2.		Преобразуем
			Z − 2 x1 − 5 x2 − 9 x3 −0(x4 + x5 + x6 )= 0
Шаг 3.		Заполняем опорный план 1 симплекс-таблицы (табл. 4.1).
						Опорный план						Таблица 4.2.
	Базис			a0		x1	x2		x3		x4		x5	x6
	(≥) х4			12,00		0	1		2		1		0	0
	(=) х5			8,00		0	2		-1		0		1	0
	(≤) х6			15,00		5	1		1		0		0	1
	Z			0		-2	-5		-9		0		0	0

Шаг 4. Формируем строку -Wj=-∑aij , складывая aij , стоящие на пересечении

опорного столбца и строк симплекс-таблицы со знаками (≥) и (=).

Опорный столбец ищем по минимуму -W.

Таблица 4.2.

Формирование строки -W

Базис	a0	x1	x2	x3	x4	x5	x6	Өi
(≥) х4	12,00	0	1	2	1	0	0	12,00	min
(=) х5	8,00	0	2	-1	0	1	0	4,00
(≤) х6	15,00	5	1	1	0	0	1
Z	0,00	-2	-5	-9	0	0	0
-W	-20,00	0	-3	-1	-1	-1	0

Шаг 5. В W ищем min элемент, определяющий опорный столбец (выделен). При j = 2

Шаг 6. По min Өi = ai0 / aj=p =		4,00	находим опорную строку i = 2
На пересечении	i =	2	и j = 2	находим опорный элемент
x[2	, 2 ]=	2,00	(табл. 4.2).

Шаг 7. Выполняем преобразования Жордана-Гаусса.

Из базиса вышел х4

				Итерация 1				Таблица 4.3.
Базис	a0	x1	x2	x3	x4	x5	x6	Өi	min
(≥) х4	8,00	0,00	0,00	2,50	1,00	-0,50	0,00	3,20
х2	4,00	0,00	1,00	-0,50	0,00	0,50	0,00
(≤) х6	11,00	5,00	0,00	1,50	0,00	-0,50	1,00
Z	20,00	-2,00	0,00	-11,50	0,00	2,50	0,00
-W	-8,00	0,00	0,00	-2,50	-1,00	0,50	0,00

Шаг 8. По min в строке W находим			j =	3
По min в столбце Ө находим			i =	1
На пересечении	i =	1	и	j = 3	находим опорный элемент
x[1	, 3 ]=	2,50	(табл. 4.3).

Шаг 9. С вновь найденным опорным элементом снова выполняем преобразования Жордана-Гаусса (табл. 4.4).

				Итерация 2			Таблица 4.3.
Базис	a0	x1	x2	x3	x4	x5	x6
х3	3,20	0,00	0,00	1,00	0,40	-0,20	0,00
х2	5,60	0,00	1,00	0,00	0,20	0,40	0,00
(≤) х6	6,20	5,00	0,00	0,00	-0,60	-0,20	1,00
Z	56,80	-2,00	0,00	0,00	4,60	0,20	0,00

Поскольку в базисе нет xi со знаками (=) или (≥), строку -W не вычисляем. Переменные х4 и х5, ушедшие из базиса, удаляем из симплекс-таблицы.

Так как в Z есть числа < 0, - план не оптимален и опоpный столбец ищем по Z (таблица 4.4).

Таблица 4.4.

Удаление векторов х4 и х5

Базис	a0	x1	x2	x3	x6	Өi
х3	3,20	0,00	0,00	1,00	0,00
х2	5,60	0,00	1,00	0,00	0,00		min
(≤) х6	6,20	5,00	0,00	0,00	1,00	1,24
Z	56,80	-2,00	0,00	0,00	0,00	0,00

Шаг 10.По min в строке Z находим			j =	1
По min в столбце Ө находим			i =	3
На пересечении	i =	3	и	j = 1	находим опорный элемент
x[3	, 1 ]=	5,00	(табл. 4.4).

Шаг 11.С вновь найденным опорным элементом снова выполняем преобразования Жордана-Гаусса (табл. 4.5).

Таблица 4.5.

Удаление векторов х4 и х5

Базис	a0	x1	x2	x3	x6	Өi
х3	1,24	1,00	0,00	0,00	0,20
х2	1,24	1,00	0,00	0,00	0,20
х1	1,24	1,00	0,00	0,00	0,20
Z	0,00	0,00	0,00	0,00	0,00	0,00

Преобразования Жордана-Гаусса не привели ни к какому результату, так как в опорном столбце стоят нулевые значения.

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

Из второго уравнения исходной системы получим:	х3 = 2х2 - 8
Подставив этот результат в первое неравенство, получим:	5х2 ≥ 28
или х2 ≥ 5,6

Подставив выражение х3 через х2		в третье уравнение системы, получим:
5 х1 + 3 х2 ≤ 7 или	5 х1 ≤ 7 - 3 х2
Таким образом, при	х2 ≥ 5,6	правая часть последнего неравенства

всегда отрицательна. Следовательно, решение исходной системы при неотрица

Задача 2.2

Расстановка парка ВС по критерию max прибыли

Постановка задачи

АК летает по m ВЛ на n типах ВС. Известны: 1) pij - прибыль с 1 ткм на i-м

типе ВС по j-й ВЛ (руб/ткм); 2) аi - потенциал i-го типа ВС (млн.ткм); 3) bij -

прогноз спроса по j-й ВЛ (млн.ткм). Исходные данные в табл. 5.1. Таблица 5.1.

		Исходные данные
Типы ВС	ВЛ1	ВЛ2	ВЛ3	ВЛ4	ВЛ5	ВЛ6	ai
1	-6	4	13	-5	11	13	35
2	-4	13	5	-10	-6	-14	32
3	9	14	-5	4	-7	-3	28
4	7	12	-3	3	7	3	25
bj	25	14	12	18	15	34	118	120

Надо оценить xij (i=1,n; j=1,m) - объемы перевозок на i-м типе ВС по j-й ВЛ

m n

(млн. ткм), дающие P = ∑∑pij xij → max при ограничениях:

i=1 j=1

∑xij = ai i=1; ∑xij =bj j=1; ∑ai =∑bj

Алгоритм решения задачи:

Шаг 1. Преобразуем "открытую" задачу в "закрытую" - вводим столбец с bдоп= 2 уравнивая суммы потенциалов aij и спроса bj

Таблица 5.2.

Преобразование"закрытой" задачи в "открытую"

Типы ВС	ВЛ1	ВЛ2	ВЛ3	ВЛ4	ВЛ5	ВЛ6	ВЛ7	ai
1	-6	4	13	-5	11	13	0	35
2	-4	13	5	-10	-6	-14	0	32
3	9	14	-5	4	-7	-3	0	28
4	7	12	-3	3	7	3	0	25
bj	25	14	12	18	15	34	2	120	120

Шаг 2. Строим опорный план методом минимальной стоимости, стараясь распределить величины потенциала по клеткам с минимальной стоимостью:

							Таблица 5.2.
	Построение опорного плана
Типы ВС	ВЛ1	ВЛ2	ВЛ3	ВЛ4	ВЛ5		ВЛ6	ВЛ7	ai	-110
1	-6	4	13	-5		11	13	0	35
	25	10								-376
2	-4	13	5	-10		-6	-14	0	32
				18			14			-168
3	9	14	-5	4		-7	-3	0	28
			12		15		1			105
4	7	12	-3	3		7	3	0	25
		4					19	2
bj	25	14	12	18		15	34	2	120
					m	n				-549
Прибыль плана равна			−P = −∑∑pij xij =					-549
					i=1	j=1

Шаг 3. Строим систему потенциалов и проверяем условия оптимальности

1)ui + vj = cij для "занятых" клеток

2)ui + vj ≤ cij для "незанятых" клеток

Построение системы потенциалов ведем в соответствии с [1, стр.17]. Таблица 5.3.

Построение системы потенциалов

	ui	-1	9	-2	-4	-4	0	-3		vj
	Типы ВС	ВЛ1	ВЛ2	ВЛ3	ВЛ4	ВЛ5	ВЛ6	ВЛ7	ai
	1	-6	4	13	-5	11	13	0	35	-5
		25	10
	2	-4	13	5	-10	-6	-14	0	32	-14
					18		14
	3	9	14	-5	4	-7	-3	0	28	-3
				12		15	1
	4	7	12	-3	3	7	3	0	25	3
			4				19	2
	bj	25	14	12	18	15	34	2	120

Шаг 4. Проверяем условие оптимальности для незанятых клеток.

При невыполнении условия в клетки впишем δij = ui + vj - cij

(они выделены цветом).

				Опорный план							Таблица 5.4.
	ui	-1	9	-2		-4	-4	0		-3		vj
	Типы ВС	ВЛ1	ВЛ2	ВЛ3		ВЛ4	ВЛ5	ВЛ6		ВЛ7	ai		-110
	1	-6	4	13		-5	11	13		0	35	-5
		25	10										-376
	2	-4	13	5		-10	-6	-14		0	32	-14
						18		14					-168
	3	9	14	-5		4	-7	-3		0	28	-3
				12			15	1					93
	4	7	12		-3	3	7		3	0	25	3
			4	4				19		2
	bj	25	14	12		18	15	34		2	120
													-561

Полученный план оказался не оптимальным.

Находим клетку с максимальным δij. Двигаясь по занятым клеткам и

поворачивая в них на 90°, строим замкнутый контур (см. табл. 5.4). Передвигаем по этому контуру минимальное число единиц, находившихся в занятых клетках, формируем новый опорный план (см. табл. 5.5)

Таблица 5.5.

				Опорный план
	ui	2	12	-3	1	-1	3	0		vj
	Типы ВС	ВЛ1	ВЛ2	ВЛ3	ВЛ4	ВЛ5	ВЛ6	ВЛ7	ai		-110
	1	-6	4	13	-5	11	13	0	35	-8
		25	10								-376
	2	-4	13	5	-10	-6	-14	0	32	-11
					18		14				-144
	3	9	14	-5	4	-7	-3	0	28	-6
						15	13				21
	4	7	12	-3	3	7	3	0	25	0
			4	12			7	2
	bj	25	14	12	18	15	34	2	120		-609
	Так как для всех точек выполнено условие оптимальности, то построен
	оптимальный план.					m n
	Прибыль плана равна				P =	∑∑pij xij =		609

i=1 j=1

Задача 2.3

Оптимизация графика оборота самолетов

Постановка задачи

Задано расписание полетов. Надо сформировать оптимальный график оборота ВС и найти минимальное число ВС, необходимое для выполне-

ния расписания. Время нахождения ВС на земле Тмин ≤ 1 час. Число рейсов в сутки nrsu = 10.

		Исходные данные
Рейс	Вылет из А	Прилет в В	Рейс	Вылет из В	Прилет в А
1	8,00	13,00	11	7,00	12,00
2	9,00	14,00	12	10,00	15,00
3	10,00	15,00	13	12,00	17,00
4	11,00	16,00	14	14,00	19,00
5	12,00	17,00	15	16,00	21,00

Шаг 1. Находим Тij время нахождения ВС на земле каждой пары рейсов:

Таблица 6.0.

Время нахождения ВС на земле для любой пары рейсов

B	11	12	13	14	15	A	1	2	3	4	5
1	18	21	23	1	3	11	20	21	22	23	24
2	17	20	22	24	2	12	17	18	19	20	21
3	16	19	21	23	1	13	15	16	17	18	19
4	15	18	20	22	24	14	13	14	15	16	17
5	14	17	19	21	23	15	11	12	13	14	15

Шаг 2. Решаем дважды задачу о назначениях по правой и левой частям таблицы 6.0.

Постановка задачи о "назначениях"

АК выполняет n рейсов на n ВС.Известна матрица C={cij} себестоимостей

рейса на i-м ВС (I,j=1,n) - табл. 6.1. Надо найти матрицу назначений Х=хij
		m	n
n ВС на n рейсов, минимизируя		Z = ∑∑cij xij → min
		i=1 j=1
	n	n
при ограничениях	∑xij =1;	∑xij =1;	xij = 0 или xij =1
	i=1	j=1