Решение задачи по управлению самолетами и аэродромами

Министерство образования

и науки РФ

НГТУ

Кафедра прикладной математики

Расчетно-графическое задание

по информатике

Факультет: ПМИ

Вариант: 7

Группа: ПМ-72

Студент: Щеголев В. С.

Преподаватель: Шапошникова Т. А.

Новосибирск

2008

1)  Анализ задачи:

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

Метод решения:

<airport>::=<n><air><cls><ntek><nmax><r>|<>;

<air>::=<N>;

<r>::=<N>;

<craft>::=<N><cls1><oil>;

<v>::=<N>.

airport-аэропорт с аэродромами, где n - количество аэродромов, air -ячейка с принятыми самолетами, cls - класс выше которого аэродром не может принять самолет, ntek - число принятых самолетов, nmax – максимальное число самолетов которое может принять аэродром.

r-расстояния до каждого самолета, где N- количество ячеек соответствующее количеству самолетов.

craft- N- количество самолетов, cls1 – класс самолета, oil – расстояние которое может пролететь самолет на имеющемся горючем.

Данно: Aаэродром, Scraft

i = 0

повторять

 |

            |    k = 0

            |    повторять

            |     | если S_i(oil) ≤ A_k(r_i) & S_i(cls1) ≥ A_k(cls) & A_k(ntek) < A_k(nmax)

            |     | то A_k(air_A(ntek)) = i, v_i  = 1, A_k(ntek) = A_k(ntek)+1

            |     |

            |     | пока k < A(n)

            |

 |пока i < S(n)

i = 0

повторять

           |если v_i = 0,

           |         то k = 0

           |          повторять

           |          |  если (S_i(oil) ≤ A_k(r_i) & S_i(cls1) ≥ A_k(cls)),

           |          |то f = 0

           |          |

           |          |  повторять

           |          | |  f1=A_k(air_f)

           |          | |  m = 0

           |          | |

           |          | |    повторять

           |          | |    |  если(S_f1(oil) ≤ A_m(r_f1) & S_f1(cls1) ≥ A_m(cls) & A_m(ntek) < A_m(nmax))

           |          | |    |  то(A_m(air_A(ntek)) = f1, v_i  = 1,A_k(air_f) = i, A_m(ntek) = A_m(ntek)+1,v_i=1)

           |          | |    |пока (m < A(n) и v_i = 0)

           |          | |

           |          | |пока (f < A_k(ntek) и v_i = 0)

           |          |

           |          |пока (k < A(n) и v_i = 0)

           |пока (i < S(n))

Тесты:

№1

№	класс	расстояние
0	1	5
1	2	3
2	2	7
3	4	10
4	3	15
5	5	3
6	1	5

№	Принятые самолеты							Кол-во принятых	класс	Макс-е кол-во	Расстояния до самолетов
											0	1	2	3	4	5	6
0	4	1						2	3	2	5	3	9	2	15	2	4
1	2	0						2	2	2	4	7	5	9	9	1	7
2	3							1	5	1	2	2	5	8	7	2	11

№2

№	класс	расстояние
0	1	5
1	2	3
2	2	7
3	4	10
4	3	3
5	5	3
6	1	5

№	Принятые самолеты							Кол-во принятых	класс	Макс-е кол-во	Расстояния до самолетов
											0	1	2	3	4	5	6
0	6	1						2	3	2	5	3	9	2	15	2	4
1	2	0						2	2	2	4	7	5	9	9	1	7
2	3							1	5	1	2	2	5	8	7	2	11

№3

№	класс	расстояние
0	1	5
1	2	3
2	2	7
3	4	10
4	3	1
5	5	3
6	1	2

№	Принятые самолеты							Кол-во принятых	класс	Макс-е кол-во	Расстояния до самолетов
											0	1	2	3	4	5	6
0	0	1						2	3	2	5	3	9	2	15	2	4
1	2							2	2	2	4	7	5	9	9	1	7
2	3							1	5	1	2	2	5	8	7	2	11