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

Страницы работы

Содержание работы

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

и науки РФ

НГТУ

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

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

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

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

Вариант: 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

            |    повторять

            |     | если Si(oil) ≤ Ak(ri) & Si(cls1) ≥ Ak(cls) & Ak(ntek) < Ak(nmax)

            |     | то Ak(airA(ntek)) = i, v= 1, Ak(ntek) = Ak(ntek)+1

            |     |

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

            |

 |пока i < S(n)

i = 0

повторять

           |если vi = 0,

           |         то k = 0

           |          повторять

           |          |  если (Si(oil) ≤ Ak(ri) & Si(cls1) ≥ Ak(cls)),

           |          |то f = 0

           |          |

           |          |  повторять

           |          | |  f1=Ak(airf)

           |          | |  m = 0

           |          | |

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

           |          | |    |  если(Sf1(oil) ≤ Am(rf1) & Sf1(cls1) ≥ Am(cls) & Am(ntek) < Am(nmax))

           |          | |    |  то(Am(airA(ntek)) = f1, v= 1,Ak(airf) = i, Am(ntek) = Am(ntek)+1,vi=1)

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

           |          | |

           |          | |пока (f < Ak(ntek) и vi = 0)

           |          |

           |          |пока (k < A(n) и vi = 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

Похожие материалы

Информация о работе

Предмет:
Информатика
Тип:
Расчетно-графические работы
Размер файла:
1 Mb
Скачали:
0