Програмне забезпечення ЕОМ

Модуль метода ветвей и границ: при передаче управления данному модулю осуществляется составления поиск кратчайшего пути по методу ветвей и границ.

Модуль вывода результатов: осуществляется вывод результатов работы программы на экран.

На рис.1 показана схема взаимодействия модулей.

 

3.2 Форматы исходных данных и результатов решения задачи

 

Приведем описание форматов исходных данных и результатов работы программы.

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

Модуль сравнения и управления: здесь осуществляется присвоение каждому городу своего номера. В данном модуле данные представляются уже в виде двумерного массива чисел, списка номеров городов, а также длинны кратчайшего пути для каждого из методов.

Модули метода динамического программирования и метода ветвей и границ: на входе – двумерный массив данных, а после выполнения поиска кратчайшего пути получаем список номеров городов и длину кратчайшего пути.

Модуль вывода результатов: результаты выводятся в виде списка городов и длинны кратчайшего пути.

 

 

 

3.  Требования к программному изделию

      

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

        Требования к технических средствам:

• процессор не ниже Pentium II,
• частота – не менее 133Мгц,
• ОЗУ -  не менее 16 Мб.  

  Требования к программным средствам:

• OC Windows 98/NT/ME/2000/XP/7.
• Borland Delphi 7

Состав программного продукта:

• подпрограмма получения данных;
• подпрограмма сравнения и управления;

• подпрограмма решения математической задачи методом ветвей и границ и методом динамического программирования;

• подпрограмма вывода результатов.

4.  Требования к программной документации

Перечень программных  документов:

• Техническое задание;
• Пояснительная записка;
• Эскизный проект;
• Руководство пользователя.

 

 

 

4. Руководство пользователя

Пользовательский интерфейс  разработан, используя язык объектно-ориентированного программирования Delphi 7. Запускается программа с помощью файла Project1.exe. Исходя из этого, пользователю рекомендуется установить среду BorlandDelphi 7.

При запуске программы  открывается окно, представленное на рис.1.

Рис.1 Главное окно

В этом окне пользователь из выпадающего списка должен выбрать города, которые нужно посетить. После выбора каждого из городов он появляется в списке выбранных городов(Рис.2).

Затем для подсчета оптимального маршрута необходимо нажать кнопку “Calculate”.

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

На экране появляется еще 2 окна, первое из которых это  форма в которой отображается платежная матрица(Рис.3), а второе окно – это окно

                          

вывода результатов(Рис.4). Оно содержит два поля: первое - отображает оптимальный маршрут, второе – стоимость данного маршрута.                               

Рис.2. Выбор  городов

Рис.3 Платежная  матрица

 

 

 

 

 

 

 

 

Рис.4 Окно вывода результатов

 

Если пользователю необходимо изменить платежную матрицу, то он должен в главном окне нажать кнопку “Change Data”, при этом произойдет открытие окна с платежной матрицей(Рис.5). В ней можно произвольно изменять стоимости путей, названия городов и их количество.

         Рис.5 Окно изменения данных.

 

После корректировки  таблицы для сохранения изменений  необходимо жать кнопку “Save Data”, в случае если пользователь хочет восстановить данные не закрывая при этом окно необходимо нажать кнопку “Load Data”.

Необходимо также упомянуть  что считывание всех данных в таблицу происходит из файла “temp.txt”, по этому необходимо что бы он размещался в одной папке с программой.

 

2. ЭКСПЕРИМЕНТАЛЬНЫЕ РАСЧЕТЫ

5.1 Контрольные примеры для решения на ЭВМ

Контроль пример №1

 

j i	1	2	3	4
1	∞	4	3	4
2	2	∞	5	2
3	6	2	∞	1
4	1	5	4	∞

 

 

 

 

 

 

Сначала определяем значения В(i, {j}):

В(2, {3}) = 5 + 6 = 11;    В(3, {2}) = 2 + 2 = 4;        В(4, {2}) = 5 + 2 = 7;

      В(2, {4}) = 2 + 1 = 3;       В(3, {4}) = 1 + 1 = 2;        В(4, {3}) = 4 + 6 = 10.

Далее по формуле последовательно получаем (в левой части каждого из ниже записанных равенств выделены те значения параметра j, на которых при подсчете реализуется указанный в правой части минимум):

В(2, {3, 4}) = min [s₂₃ + B(3,{4}); s₂₄ + B(4,{3})] = min(5 + 2; 2 + 10)=7;

В(3, {2, 4}) = min [s₃₂ +B(2,{ 4}); s₃₄ + B(4,{ 2})] = min(2 + 3; 1 + 7 )=5;

В(4, {2, 3}) = min [s₄₂ + B(2,{ 3}); s₄₃ + B(3,{ 2})] = min(5 + 11; 4 +4)=8;

В(1, {2, 3, 4}) = min [s₁₂ + B(2,{3,4}) s₁₃ + B(3,{ 2,4}) s₁₄ + B(4,{2,3 })] =

                         = min (4 +7; 3 +5; 4 + 8 ) = 8.

Итак, оптимальное значение критерия в рассматриваемом примере равно 8.

Выполненные выделения позволяют  определить оптимальный маршрут. Он следующий:

1 ®® 3 ®® 2 ®® 4 ®® 1.

 

 

 

 

 

 

j i	1	2	3	4	5	6
1	∞	26	42	15	29	25
2	7	∞	16	1	30	25
3	20	13	∞	35	5	0
4	21	16	25	∞	18	18
5	12	46	27	48	∞	5
6	23	5	5	9	5	∞

 

Контроль пример №2

 

 

 

 

 

 

 

 

 

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r₁=15, r₂=1, r₃=0, r₄=16, r₅=5, r₆=5.

После их вычитания по строкам получим:

	1	2	3	4	5	6
1	∞	11	27	0	14	10
2	6	∞	15	0	29	24
3	20	13	∞	35	5	0
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

 

 

Минимумы по столбцам: h₁=5, h₂=h₃=h₄=h₅=h₆.

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

 

 

 

	1	2	3	4	5	6
1	∞	11	27	0	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

 

Найдем нижнюю границу φ(Z) = 15+1+0+16+5+5+5 = 47.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени Θ_ij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ₁₄ = 10 + 0,  
Θ₂₄ = 1 + 0, Θ₃₆ = 5+0, Θ₄₁ = 0 + 1, Θ₄₂ = 0 + 0, Θ₅₆ = 2 + 0, Θ₆₂ = 0 + 0,  
Θ₆₃ = 0 + 9, Θ₆₅ = 0 + 2. Наибольшая степень Θ₁₄ = 10. Ветвление проводим по дуге (1, 4).

Нижняя граница для множества  остается равной 47. Для всех маршрутов множества из города A мы не перемещаемся в город D. В матрице это обозначается выставлением в ячейку (1, 4) знака ∞. В этом случае выход из города A добавляет к оценке нижней границы по крайней мере наименьший элемент первой строки. φ ( ) = 47 + 10.

В матрице, соответствующей  полагаем c₁₄= ∞.

	1	2	3	4	5	6
1	∞	11	27	∞	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

 

 

 

 

После проведения процедуры  приведения с r₁=10 получим новую нижнюю границу 57 + 10 = 67.

В матрице, соответствующей , вычеркиваем первую строку и четвертый столбец и положим c₄₁= ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c¹_ij}:

 

	1	2	3	5	6
2	1	∞	15	29	24
3	15	13	∞	5	0
4	∞	0	9	2	2
5	2	41	22	∞	0
6	13	0	0	0	∞