Математическое моделирование систем и процессов

Работа из раздела: «Экономико-математическое моделирование»

ФГБОУ ВПО

ДВГУПС

Кафедра «Управление эксплуатационной работой».

КОНТРОЛЬНАЯ РАБОТА

Математическое моделирование систем и процессов

Гр.232

Выполнил: Илларионова Е.В

Проверил: Широков А.П.

ХАБАРОВСК

2013

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

Условие: Для заданного варианта транспортной задачи в матричной форме с ограничениями пропускной способности необходимо найти оптимальный план, при котором будет выполняться условие наименьшего суммарного пробега порожних вагонов. Для этого необходимо:

1) Составить математическую модель задачи;

2) Составить начальный план, проверить по условию вырождения, рассчитать суммарные вагоно-километры порожнего пробега;

3) Решить задачу методом потенциалов, рассчитать суммарные вагоно-километры порожнего пробега оптимального плана;

4) Сравнить начальный и оптимальный варианты.

Исходные данные транспортной задачи с ограничениями

Станция отправления	Ресурсы, тыс.т	Станция назначения(потребности)
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс.т
		18	20	12	15	10	15	20	25	15
А1	40	25 10	30 7	45	60	35	55	60	90	75
А2	25	45	58	46	75	48	54	65	58	95
А3	25	35 8	35	40	65	40	80	35	65	55
А4	15	48	50	30 6	55	45	45	55	50	40
А5	45	40	52	38	40	70	37 8	30 10	75	45

математическое моделирование транспортная задача

Транспортная задача является закрытой, так как суммарные запасы ресурсов равны суммарным потребностям:

40+25+25+15+45=18+20+12+15+10+15+20+25+15

150=150

Математическая модель задачи:

1. Целевая функция:

2. Система ограничения

3. Условие не отрицательности

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

Начальный опорный план, построенный методом наименьшего критерия в столбце.

Станция отправления	Ресурсы, тыс.т	Станция назначения(потребности)
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс.т
		18	20	12	15	10	15	20	25	15
А1	40	25 10 10	30 7 7	45	60	35 10	55	60 4	90	75 9
А2	25	45	58	46	75	48	54	65	58 25	95
А3	25	35 8 8	35 13	40	65	40	80	35 4	65	55
А4	15	48	50	30 6 6	55	45	45 7	55 2	50	40
А5	45	40	52	38 6	40 15	70	37 8 8	30 10 10	75	45 6

Значение целевой функции составит:

F=25*10+30*7+35*10+60*4+75*9+58*25+35*8+35*13+35*4+30*6+45*7+55*2+38*6+40*15+37*8+30*10+45*6=6349 (ваг-км)

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

Станция отправления	Ресурсы тыс.т	Станция назначения (потребности)	Ui
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Недостаток порожних вагонов
		18	20	12	15	10	15	20	25	15
А1	40	25 10 10	30 7 7	45Н23	60Н10	35 10	55	60 4	90	75 9	50
А2	25	45 Н3	58	46 0	75	48	54	65	58 25	95	72
А3	25	35 8 8	35 13	40 Н3	65	40	80	35 4	65	55	75
А4	15	48Н17	50 Н5	30 6 6	55Н10	45	45 7	55 2	50Н25	40Н30	55
А5	45	40 0	52	38 6	40 15	70	37Н17 8 8	30 10 10	75	45 6	80
Vj	120	110	118	120	85	100	110	130	125

1.F=25*10+30*7+35*10+60*4+75*9+46*0+58*25+35*8+35*13+35*4+30*6+45*7+55*2+40*0+38*6+40*15+37*8+30*10+45*6=6349 (ваг-км)

2.Проверка исходного опорного плана на условие «вырождения».

К_зб?m+n-1

Где К_зб - число занятых базисных клеток; m- число строк матрицы (пунктов отправления); n-число столбцов (пунктов назначения).

11? 5+9-1

11?13

Условие вырождения выполняется, но план является «вырожденным». Для устранения «вырождения» назначаются фиктивные перевозки х₅₁=0,х₂₃=0.

3. Потенциалы столбцов определяются следующим образом:

V_i=U_i+c_ij

Где c_ij- критерий расстояния в заданной клетке.

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

U_i=V_j - c_ij

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

V_i - U_i ? c_ij, при x_ij=0 (клетка свободна)

V_i - U_i = c_ij, при (клетка базисная).

V_i - U_i ?c_ij, при x_ij= (насыщенная клетка)

Формальное правило улучшения плана:

а) начиная с клетки с нарушением, двигаясь по горизонталям и вертикалям ходом «шахматной ладьи», строят замкнутый контур с вершинами в базисных клетках;

б) начиная с клетки с нарушением, нумеруют вершины контура (направление обхода контура значения не имеет);

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

г) для балансировки матрицы в нечетных вершинах контура найденное значение прибавляется к значениям перевозок в этих клетках (с учетом возможных ограничений в этих клетках), в четных вершинах - вычитается из значений перевозок.

Формальное правило улучшения плана при нарушении условия оптимальности для насыщенных клеток:

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

б) начиная с клетки с нарушением, нумеруют вершины контура (направление обхода контура значения не имеет);

в) в нечетных вершинах находится минимальная перевозка;

г) для балансировки матрицы в четных вершинах контура найденное значение прибавляется к значениям перевозок в этих клетках (с учетом возможных ограничений в этих клетках), в нечетных вершинах-вычитается из значений перевозок.

Станция отправления	Ресурсы тыс.т	Станция назначения (потребности)	Ui
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Недостаток порожних вагонов
		18	20	12	15	10	15	20	25	15
А1	40	25 10 10	30 7 7	45Н23	60Н10	35 10	55Н25	60 6	90	75 7	20
А2	25	45 Н3	58	46 0	75	48	54Н4	65	58 25	95	42
А3	25	35 8 8	35 13	40	65	40	80	35 4	65	55	45
А4	15	48	50	30 6 6	55	45	45 7	55	50	40 2	55
А5	45	40 0	52	38 6	40 15	70	37 8 8	30 10 10	75	45 6	50
Vj	90	80	88	90	55	100	80	100	95

Скорректированный план перевозок (первая итерация)

F=25*10+30*7+35*10+60*6+75*7+46*0+58*25+35*8+35*13+35*4+30*6+45*7+40*2+40*0+38*6+40*15+37*8+30*10+45*6=6289 (ваг-км)

Проверка на условие «вырождения»:

13?5+9-1

13=13

Скорректированный план перевозок (вторая итерация)

Станция отправления	Ресурсы тыс.т	Станция назначения (потребности)	Ui
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Недостаток порожних вагонов
		18	20	12	15	10	15	20	25	15
А1	40	25 10 10	30 7 7	45Н20	60Н7	35 10	55 7	60 6	90	75	50
А2	25	45 Н3	58	46 0	75	48	54	65	58 25	95	69
А3	25	35 8 8	35 13	40 0	65	40	80	35 4	65	55	75
А4	15	48	50	30 6 6	55	45	45	55	50	40 9	82
А5	45	40 0	52	38 6	40 15	70	37 8 8	30 10 10	75	45 6	77
Vj	117	110	115	117	85	105	110	127	122

F=25*10+30*7+35*10+55*7+60*6+46*0+58*25+35*8+35*13+40*0+35*4+30*6+40*9+40*0+38*6+40*15+37*8+30*10+45*6=6114 (ваг-км)

Проверка на условие «вырождения»:

12?5+9-1

12?13

Условие вырождения выполняется, но план является «вырожденным». Для устранения «вырождения» назначаются фиктивные перевозки х₃₃=0.

Скорректированный план перевозок (третья итерация)

Станция отправления	Ресурсы тыс.т	Станция назначения (потребности)	Ui
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Недостаток порожних вагонов
		18	20	12	15	10	15	20	25	15
А1	40	25 10 10	30 7 7	45 0	60	35 10	55 7	60 6	90	75	50
А2	25	45 Н3	58 Н3	46 0	75	48	54	65	58 25	95	49
А3	25	35Н13 8 8	35 13	40	65	40	80	35 4	65	55	75
А4	15	48	50	30 6 6	55	45	45	55	50	40 9	62
А5	45	40 0	52 Н1	38 6	40 15	70	37 8 8	30 10 10	75	45 6	57
Vj	97	110	95	97	85	105	110	107	102

F=25*10+30*7+35*10+55*7+60*6+46*0+58*25+35*8+35*13+40*0+35*4+30*6+40*9+40*0+38*6+40*15+37*8+30*10+45*6=6114 (ваг-км)

Проверка на условие «вырождения»:

13?5+9-1

13=13

Скорректированный план перевозок (четвертая итерация)

Станция отправления	Ресурсы тыс.т	Станция назначения (потребности)	Ui
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Недостаток порожних вагонов
		18	20	12	15	10	15	20	25	15
А1	40	25 10 10	30 7 7	45 6	60	35 10	55 7	60	90	75	51
А2	25	45	58	46 0	75	48	54 Н2	65	58 25	95	50
А3	25	35 8 2	35 13	40 0	65	40	80	35 10	65	55	56
А4	15	48	50	30 6 6	55	45	45 Н5	55	50 Н2	40 9	56
А5	45	40 6	52	38 Н7	40 15	70	37 8 8	30 10 10	75	45 6	51
Vj	91	91	96	91	86	106	91	108	96

F=25*10+30*7+45*6+35*10+55*7+46*0+58*25+35*2+35*13+40*0+35*10+30*6+40*9+40*6+40*15+37*8+30*10+45*6=6036 (ваг-км)

Проверка на условие «вырождения»:

13?5+9-1

13=13

Скорректированный план перевозок (пятая итерация)

Станция отправления	Ресурсы тыс.т	Станция назначения (потребности)	Ui
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Недостаток порожних вагонов
		18	20	12	15	10	15	20	25	15
А1	40	25 10 10	30 7 7	45 6	60	35 10	55 7	60	90	75	51
А2	25	45 Н3	58	46 0	75	48	54 Н2	65	58 25	95	50
А3	25	35 8 2	35 13	40 0	65	40	80	35 10	65	55	63
А4	15	48	50	30 6 6	55	45	45	55	50	40 9	63
А5	45	40 6	52	38 0	40 15	70	37 8 8	30 10 10	75	45 6	58
Vj	98	98	96	98	86	106	98	108	103

F=25*10+30*7+45*6+35*10+55*7+46*0+58*25+35*2+35*13+40*0+35*10+30*6+40*9+40*6+38*0+40*15+37*8+30*10+45*6=6036 (ваг-км)

Проверка на условие «вырождения»:

13?5+9-1

13=13

Скорректированный план перевозок (шестая итерация)

Станция отправления	Ресурсы тыс.т	Станция назначения (потребности)	Ui
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Недостаток порожних вагонов
		18	20	12	15	10	15	20	25	15
А1	40	25 10 10	30 7 7	45 6	60	35 10	55 7	60	90	75	48
А2	25	45 0	58	46	75	48	54	65	58 25	95	50
А3	25	35 8 2	35 13	40	65	40	80	35 10	65	55	60
А4	15	48	50	30 6 6	55	45	45	55	50	40 9	60
А5	45	40 6	52	38 0	40 15	70	37 8 8	30 10 10	75	45 6	55
Vj	95	95	93	95	83	103	95	108	100

F=25*10+30*7+45*6+35*10+55*7+45*0+58*25+35*2+35*13+35*10+30*6+40*9+40*6+38*0+40*15+37*8+30*10+45*6=6036 (ваг-км)

Скорректированный опорный план проверяется на условие «вырождения»:

К_зб?m+n-1

13?5+9-1

13=13

После присвоения потенциалов всем столбцам и строкам матрицы проверяются условия оптимальности.

В полученном плане нет нарушений условий оптимальности. План оптимальный.

Значение целевой функции уменьшилось по сравнению с начальным планом на 313 ваг.-км(6349-6036=313) или на 313/6349*100%=4,9%

Условие.

На 4 станциях А₁, А₂, А₃ и А₄ имеется избыток порожних вагонов в размере соответственно а₁, а₂, а₃ и а₄ (табл.1) вагонов. Необходимо распределить данные вагоны по 7 станциям В₁, В₂, В₃, В₄, В₅, В₆ и В₇ с недостатком порожняка соответственно в количестве b₁, b₂, b₃, b₄, b_5, b₆ и b₇ вагонов (табл. 2). Расстояние между каждой станцией отправления (избытка вагонов) и каждой станцией назначения (недостатка порожняка) представлено в виде матрицы (табл.3).

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

Ресурсы станций отправления

Таблица 1.

Станция отправления	А1	А2	А3	А4
Избыток порожних вагонов	100	100	60	40

Потребности станции назначения

Таблица 2.

Станция назначения	В1	В2	В3	В4	В5	В6	В7
Избыток порожних вагонов	55	50	45	35	45	25	45

Матрица расстояний между станциями, км

Таблица 3.

Станция отправления	Станция назначения
	В1	В2	В3	В4	В5	В6	В7
А1	25	33	18	43	32	54	41
А2	24	37	29	42	34	25	29
А3	38	28	40	34	37	57	36
А4	22	48	38	26	21	30	42

Исходный план транспортной задачи.

Станция отправлен ия	Избыток порожних вагонов	Станция назначения
		1	2	3	4	5	6	7
		Недостаток порожних вагонов
		55	50	45	35	45	25	45
1	100	25	33	18	43	32	54	41
2	100	24	37	29	42	34	25	29
3	60	38	28	40	34	37	57	36
4	40	22	48	38	26	21	30	42

Данная задача является, задачей транспортного вида ( так как суммарный объем производства а а_i равен суммарному объему потребления а b_i):

а₁+а₂+а₃+а₄=b₁+b₂+b₃+b₄

300=300

Целевая функция (суммарный пробег порожних вагонов) определяется по формуле:

где с_ij- расстояние перевозки от i-ой станции отправления до j-ой станции назначения; x_ij - величина перевозки из пункта отправления i-ой станции отправления до j-ой станции назначения.

Система ограничений

где a_i - ресурсы i-ой станции отправления; b_j - потребность j-ой станции назначения.

Условие формирования закрытой транспортной задачи:

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

Исходный опорный план перевозок может быть построен различными методами.

1.Метод северо-западного угла.

Станция отправлен ия	Избыток порожних вагонов	Станция назначения
		1	2	3	4	5	6	7
		Недостаток порожних вагонов
		55	50	45	35	45	25	45
1	100	25 55	33 45	18	43	32	54	41
2	100	24	37 5	29 45	42 35	34 15	25	29
3	60	38	28	40	34	37 30	57 25	36 5
4	40	22	48	38	26	21	30	42 40

Значение целевой функции составит:

F = 25*55+33*45+37*5+29*45+42*35+34*15+37*30+57*25+36*5+42*40= 10725(ваг-км)

2. Метод наименьшего критерия в строке.

Станция отправлен ия	Избыток порожних вагонов	Станция назначения
		1	2	3	4	5	6	7
		Недостаток порожних вагонов
		55	50	45	35	45	25	45
1	100	25 55	33	18 45	43	32	54	41
2	100	24	37 0	29	42	34 30	25 25	29 45
3	60	38	28 50	40	34 10	37	57	36
4	40	22	48	38	26 25	21 15	30	42

Значение целевой функции составит:

F=25*55+28*50+18*45+34*10+26*25+34*30+21*15+25*25+29*45=7840 (ваг-км)

3.Метод наименьшего критерия в столбце.

Станция отправлен ия	Избыток порожних вагонов	Станция назначения
		1	2	3	4	5	6	7
		Недостаток порожних вагонов
		55	50	45	35	45	25	45
1	100	25	33	18 45	43	32 45	54	41 10
2	100	24 15	37	29	42 25	34	25 25	29 45
3	60	38	28 50	40	34 10	37	57	36
4	40	22 40	48	38	26	21	30	42

Значение целевой функции составит:

F=24*15+22*40+28*50+18*45+42*25+34*10+32*45+25*25+41*10+29*35=8330 (ваг-км)

4.Метод двойного предпочтения

Станция отправлен ия	Избыток порожних вагонов	Станция назначения
		1	2	3	4	5	6	7
		Недостаток порожних вагонов
		55	50	45	35	45	25	45
1	100	25	33 15	18 45	43	32 40	54	41
2	100	24 30	37	29	42	34	25 25	29 45
3	60	38 25	28 35	40	34	37	57	36
4	40	22	48	38	26 35	21 5	30	42

Значение целевой функции составит:

F=24*30+38*25+33*15+28*35+18*45+26*35+32*40+21*5+25*25+29*45=8180 (ваг-км)

5. Метод минимального элемента.

Станция отправлен ия	Избыток порожних вагонов	Станция назначения
		1	2	3	4	5	6	7
		Недостаток порожних вагонов
		55	50	45	35	45	25	45
1	100	25	33	18 45	43 25	32 5	54	41 25
2	100	24 55	37	29	42	34	25 25	29 20
3	60	38	28 50	40	34 10	37	57	36
4	40	22	48	38	26	21 40	30	42

Значение целевой функции составит:

F=18*45+43*25+32*5+41*25+24*55+25*25+29*20+28*50+34*10+21*40=8175 (ваг-км)

Как видно из приведенных расчетов наименьшее значение целевой функции (суммарный пробег порожних вагонов) получено при построении начального опорного плана методом наименьшего критерия в строке (F=7840 ваг-км).

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

Станция отправления	Ресурсы, тыс.т	Станция назначения(потребности)
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс.т
		18	20	12	15	10	15	20	25	15
А1	40	25 10	30 7	45	60	35	55	60	90	75
А2	25	45	58	46	75	48	54	65	58	95
А3	25	35 8	35	40	65	40	80	35	65	55
А4	15	48	50	30 6	55	45	45	55	50	40
А5	45	40	52	38	40	70	37 8	30 10	75	45
Станция отправления	Ресурсы, тыс.т	Станция назначения(потребности)
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс.т
		18	20	12	15	10	15	20	25	15
А1	40	25 10	30 7	45	60	35	55	60	90	75
А2	25	45	58	46	75	48	54	65	58	95
А3	25	35 8	35	40	65	40	80	35	65	55
А4	15	48	50	30 6	55	45	45	55	50	40
А5	45	40	52	38	40	70	37 8	30 10	75	45
Станция отправления	Ресурсы, тыс.т	Станция назначения(потребности)
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс.т
		18	20	12	15	10	15	20	25	15
А1	40	25 10	30 7	45	60	35	55	60	90	75
А2	25	45	58	46	75	48	54	65	58	95
А3	25	35 8	35	40	65	40	80	35	65	55
А4	15	48	50	30 6	55	45	45	55	50	40
А5	45	40	52	38	40	70	37 8	30 10	75	45
Станция отправления	Ресурсы, тыс.т	Станция назначения(потребности)
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс.т
		18	20	12	15	10	15	20	25	15
А1	40	25 10	30 7	45	60	35	55	60	90	75
А2	25	45	58	46	75	48	54	65	58	95
А3	25	35 8	35	40	65	40	80	35	65	55
А4	15	48	50	30 6	55	45	45	55	50	40
А5	45	40	52	38	40	70	37 8	30 10	75	45
Станция отправления	Ресурсы, тыс.т	Станция назначения(потребности)
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс.т
		18	20	12	15	10	15	20	25	15
А1	40	25 10	30 7	45	60	35	55	60	90	75
А2	25	45	58	46	75	48	54	65	58	95
А3	25	35 8	35	40	65	40	80	35	65	55
А4	15	48	50	30 6	55	45	45	55	50	40
А5	45	40	52	38	40	70	37 8	30 10	75	45
Станция отправления	Ресурсы, тыс.т	Станция назначения(потребности)
		В1	В2	В3	В4	В5	В6	В7	В8	В9
		Объем потребления, тыс.т
		18	20	12	15	10	15	20	25	15
А1	40	25 10	30 7	45	60	35	55	60	90	75
А2	25	45	58	46	75	48	54	65	58	95
А3	25	35 8	35	40	65	40	80	35	65	55
А4	15	48	50	30 6	55	45	45	55	50	40
А5	45	40	52	38	40	70	37 8	30 10	75	45