Средние ошибки по годам Dij

Категории работников \ Годы	2010	2011	2012	2013
Производственные рабочие	0,48	0,32	0,44	0,53
Вспомогательные рабочие	0,02	0,06	0	0,1
Инженерно-технические работники	0,95	0,97	0,94	0,85
Служащие и МОП	0,46	0,71	0,49	0,23
Среднее	0,4775	0,515	0,4675	0,43

Шаг 10. Min D_ij=0% и max D_ij=0,97% в (Таблица 1 .21). Сложив D_ij. и разделив их сумму на число наблюдений, находим D_ij=0,47%.

Шаг 11. Прогноз структуры на 2014 г., получим умножением матрицы Е (Таблица 1 .18) на вектор ретро прогноза за 2013 г. (Таблица 1 .19, столбец за 2013 год). Результаты прогноза представлены в таблице (Таблица 1 .22).

Таблица 1.22

Прогноз на 2014 г.

Категории работников /Год	2014, %	Прогноз
Производственные рабочие	39,64	208
Вспомогательные рабочие	37,50	197
Инженерно-технические работники	18,23	96
Служащие и МОП	4,63	24
Итого:	100	525

Шаг 12. Прогноз на 2014 г. - 525 чел. умножаем на соответствующие доли (Таблица 1 .22) и получаем прогноз численности в абсолютных величинах.

2. Контрольная работа 2

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

(2.0)

при ограничениях:

(2.0)

Решение.

Шаг 1. Преобразуем ограничения к основной задаче линейного программирования [1]:

	(2.0)
	(2.0)

Где - некоторое бесконечно большое число.

Решим симплекс-методом исходную задачу ( 2 .0), ( 2 .0). Среди всех решений системы уравнений, удовлетворяющих условию неотрицательности:

(2.0)

нужно найти то решение, при котором целевая функция ( 2 .0) примет наибольшее значение. Процесс решения записан в виде последовательности симплексных таблиц (Таблица 2 .23).

Таблица 2.23

	Базис			2	5	9	0	-М	-М	0	Пояснения
-M		12	12	0	1	2	-1	1
-M		8	4	0	2	-1	0	0	1
0		15	15	5	1	1				1
				-2	-3M-5	-M-9	M	0	0	0
-M		8	3,2	0	0	2,5	-1	1	-0,5	0
5		4	-	0	1	-0,5	0	0	0,5	0
0		11	22/3	5	0	1,5	0	0	-0,5	1
				-2	0	-2,5M-11,5	M	0	1,5M+2,5	0
9		3,2	-	0	0	1	-0,4	0,4	-0,2	0
5		5,6	-	0	1	0	-0,2	0,2	0,4	0
0		6,2	31/3	5	0	0	0,6	-0,6	-0,2	1
				-2	0	0	-4,6	M+4,6	M+0,2	0
9		22/3		10/3	0	1	0	0	-1/3	2/3	Все
5		23/3		5/3	1	0	0	0	1/3	1/3
0		31/3		25/3	0	0	1	-1	-1/3	5/3
				109/3	0	0	0	M	M-4/3	23/3

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

Шаг 2. Дробный оптимальный план преобразуем в целочисленный алгоритмом Гомори.

Поскольку в базисе нет x_i со знаками (=) и (≥), то x_5’и x_6’, ушедшие из базиса, удаляем из симплекс-таблицы. Дробный оптимальный план имеет вид (Таблица 2 .24).

Таблица 2.24

	Базис		2	5	9	0	0
9		22/3	10/3	0	1	0	2/3
5		23/3	5/3	1	0	0	1/3
0		31/3	25/3	0	0	1	5/3
			109/3	0	0	0	23/3

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

Св.член
23/3-7=2/3	5/3-1=2/3	1-1=0	0-0=0	0-0=0	1/3-0=1/3

Формируем неравенство

(2.0)

Умножаем ( 2 .0) на -1:

(2.0)

Вводим и преобразуем неравенство:

(2.0)

Включаем ( 2 .0) и новый в таблицу (Таблица 2 .24). Так как, применим двой­ственный симплекс-метод (Таблица 2 .25). Опорная строка i=4. Опорный элемент находим по:

Столбец :-2/3: (-2/3) = 1

Столбец : -1/3: (-2/3) =0,5

Получим .

Таблица 2.25

	Базис		2	5	9	0	0	0
9		22/3	10/3	0	1	0	0	2/3
5		23/3	5/3	1	0	0	0	1/3
0		31/3	25/3	0	0	1	0	5/3
0		-2/3	-2/3	0	0	0	1	-1/3
			109/3	0	0	0	0	23/3

Проводим процедуру Жордана-Гаусса. Получим новый план (Таблица 2 .26).

Таблица 2.26

	Базис		2	5	9	0	0	0
9		6	2	0	1	0	2	0
5		7	1	1	0	0	1	0
0		7	5	0	0	1	5	0
0		2	2	0	0	0	-3	1
			109/3	0	0	0	0	23/3

Получили оптимальный целочисленный план: ,,, при котором значение функции:ден. ед.

АК летает по m ВЛ на n типах ВС. Известно:

1) р_ij- прибыль с 1 ткм на i-м типе ВС по j-й ВЛ (руб./ткм.);

2) a_i- потенциал i-го типа ВС (млн.ткм.);

3) b_j- прогноз спроса по j-й ВЛ (млн.ткм.).

Исходные данные в таблице (Таблица 2 .27).

Таблица 2.27

Типы ВС	ВЛ 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

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

или /ден.ед/,

(2.0)

при ограничениях:

(2.0)

Решение.

1. Проверим задачу на замкнутость:

Так как сумма , то добавляем.

Исходная задача примет вид:

	-6	4	13	-5	11	13	0	35
	-4	13	5	-10	-6	-14	0	32
	9	14	-5	4	-7	-3	0	28
	7	12	-3	3	7	3	0	25
	25	14	12	18	15	34	2	120

2. Найдем опорный план методом Фогеля. Находим разность между двумя наименьшими элементами в каждой строке и каждом столбце. Из найденных разностей определяем наибольшую и в соответствующей строке (столбце) находим минимальный элемент и устанавливаем значение в этой клетке. Процесс определения опорного плана методом Фогеля представлен в таблице (Таблица 2 .28).

На первой итерации разности по строкам:

-5 – (-6) = 1

-4 – (-6) = 2

-5 – (-7) = 2

0 – (-3) = 3

Разности по столбцам:

-4 – (-6) = 2

12 – 4 = 8

-3 – (-5) = 2

-5 – (-10) = 5

-6 – (-7) = 1

-3 – (-14) = 11

0 – 0 = 0

Таблица 2.28

									Разность по строкам
	-6 25	4 10	13	-5	11	13	0	35	-5+6=1	1	1	5
	-4	13	5	-10	-6	-14 32	0	32	-4+6=2
	9	14	-5 11	4	-7 15	-3 2	0	28	-5+7=2	2	2	2	2	5
	7	12 4	-3 1	3 18	7	3	0 2	25	0+3=3	3	3	3	3	3
	25	14	12	18	15	34	2	120
Разность по столбцам	-4+6=2	12-4=8	-3+5=2	-5+10=5	-6+7=1	-3+14=11	0-0=0
	13	8	2	8	14	6	0
	13	8	2	8		6	0
		8	2	8		6	0
		2	2	1		6	0
		2	2	1

Максимальная разность равна 11 и соответствует столбцу . Ищем в столбце минимальный элемент. Устанавливаем значение в эту ячейку, тогда новые значения,. Следовательно, столбецисключаем из дальнейшего рассмотрения. Повторяем описанные шаги с учётом новых значений (,).

По условию транспортной задачи количество заполненных клеток должно составлять . Так как заняты 10 клеток, то опорный план найден:

	-6 25	4 10	13	-5	11	13	0	35
	-4	13	5	-10	-6	-14 32	0	32
	9	14	-5 11	4	-7 15	-3 2	0	28
	7	12 4	-3 1	3 18	7	3	0 2	25
	25	14	12	18	15	34	2	120

Итерация 1. Проверяем опорный план на оптимальность. Находим потенциалы. Для этого составим систему уравнений для занятых клеток:

Полученная система содержит 10 уравнений и 11 неизвестных. Полагаем , тогда:

Для каждой свободной клетки определяем число :

Так как среди чисел нет положительных, то полученный план – оптимальный. Таким образом, оптимальный план перевозок имеет вид:

	-6 25	4 10	13	-5	11	13	35
	-4	13	5	-10	-6	-14 32	32
	9	14	-5 11	4	-7 15	-3 2	28
	7	12 4	-3 1	3 18	7	3	25
	25	14	12	18	15	34

Прибыль от полученных перевозок:

Задано расписание полетов (Таблица 2 .29). Надо сформировать оптимальный график оборота ВС и найти min число ВС, необходимое для выполнения расписания. Время нахождения ВС на земле T_min≤ 1 час. Число рейсов в сутки nr_SU=10.

Таблица 2.29

Pейс	Вылет-Прилет из А в В	Pейс	Вылет-Прилет из В в А
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. Находим T_ijнахождения ВС на земле каждой пары рейсов.

Пара 1, 11:

ВС из А, улетающее в 8.00 и прибывающее в B в 13.00, сможет улететь из В рейсом 11 в 7.00 на другой день: 24.00 - 13.00 + 7.00 = 18 ч.

Ищем T_ijдля каждой пары рейсов (Таблица 2 .30, Таблица 2 .31).

Таблица 2.30

Рейс	11	12	13	14	15
1	18	21	23	1	3
2	17	20	22	24	2
3	16	19	21	23	1
4	15	18	20	22	24
5	14	17	19	21	23

Таблица 2.31

Рейс	1	2	3	4	5
11	20	21	22	23	24
12	17	18	19	20	21
13	15	16	17	18	19
14	13	14	15	16	17
15	11	12	13	14	15

Шаг 2. Решаем задачу о назначениях для таблицы (Таблица 2 .30).

Находим минимальный элемент в каждой строке:

	11	12	13	14	15	Мин.
1	18	21	23	1	3	1
2	17	20	22	24	2	2
3	16	19	21	23	1	1
4	15	18	20	22	24	15
5	14	17	19	21	23	14

Вычитаем его из каждого элемента строки. Находим минимальный элемент в каждом столбце:

	11	12	13	14	15
1	17	20	22	0	2
2	15	18	20	22	0
3	15	18	20	22	0
4	0	3	5	7	9
5	0	3	5	7	9
Мин.	0	3	5	0	0

Вычитаем минимальный элемент из каждого элемента столбца:

	11	12	13	14	15
1	17	17	17	0	2
2	15	15	15	22	0
3	15	15	15	22	0
4	0	0	0	7	9
5	0	0	0	7	9

Проводим назначения.

	11	12	13	14	15
1	17	17	17	0	2
2	15	15	15	22	
3	15	15	15	22	0
4	0			7	9
5		0		7	9

Количество нулей равно 4, и меньше порядка матрицы. Проводим улучшение плана.

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

	11	12	13	14	15
1	17	17	17	0	2
2	15	15	15	22	0
3	15	15	15	22	0
4	0	0	0	7	9
5	0	0	0	7	9

Найти наименьший из элементов, через которые не проходит ни одна прямая 15. Вычесть его из всех элементов, через которые не проходят прямые. Прибавить его ко всем элементам, лежащим на пересечении прямых (элементы, через которые проходит только одна прямая, оставить неизменными):

	11	12	13	14	15
1	17	17	17	0	17
2	0	0	0	7	0
3	0	0	0	7	0
4	0	0	0	7	24
5	0	0	0	7	24

Проводим назначения.

	11	12	13	14	15
1	17	17	17	0	17
2			0	7	
3				7	0
4	0			7	24
5		0		7	24

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

Таблица 2.32

Рейс	11	12	13	14	15
1	18	21	23	1	3
2	17	20	22	24	2
3	16	19	21	23	1
4	15	18	20	22	24
5	14	17	19	21	23

Минимальное время:

15 + 17 + 22 + 1+ 1 = 56

Шаг 3. Решаем задачу о назначениях для таблицы (Таблица 2 .31).

Находим минимальный элемент в каждой строке:

Рейс	1	2	3	4	5	Мин.
11	20	21	22	23	24	20
12	17	18	19	20	21	17
13	15	16	17	18	19	15
14	13	14	15	16	17	13
15	11	12	13	14	15	11

Вычитаем его из каждого элемента строки. Находим минимальный элемент в каждом столбце:

Рейс	1	2	3	4	5
11	0	1	2	3	4
12	0	1	2	3	4
13	0	1	2	3	4
14	0	1	2	3	4
15	0	1	2	3	4
Мин.	0	1	2	3	4

Вычитаем минимальный элемент из каждого элемента столбца:

Рейс	1	2	3	4	5
11	0	0	0	0	0
12	0	0	0	0	0
13	0	0	0	0	0
14	0	0	0	0	0
15	0	0	0	0	0

Проводим назначения.

Рейс	1	2	3	4	5
11					0
12	0				
13			0		
14		0			
15				0	

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

Таблица 2.33

Рейс	1	2	3	4	5
11	20	21	22	23	24
12	17	18	19	20	21
13	15	16	17	18	19
14	13	14	15	16	17
15	11	12	13	14	15

Минимальное время:

17+ 14 +17 +14 + 24 = 86

Шаг 3. По матрицам назначений (Таблица 2 .32, Таблица 2 .33) находим пары оп­тимально спариваемых рейсов:

а) 1-14; 2-13; 3-15; 4-11; 5-12;

б) 11-5; 12-1; 13-3; 14-2; 15-4.

Шаг 4. Используя шаг 3, находим цепочку рей­сов, дающую min сумму t нахождения каждого ВС на земле:

1 – 14 – 2 – 13 – 3 – 15 – 4 – 11 – 5 – 12 – 1

Шаг 5. ВС, вылетающее из А в понедельник в 8.00 выпол­нит все рейсы цепочки за 7 дней в воскресенье в 15.00. В понедельник ВС может начать новую цепочку.

Шаг 6. Определяем число ВС:

Nbc=Nr_SU*n_tc/ Nr_SU =10*7/10 = 7 ВС.