Задача на пошук найкоротшої відстані, маршруту і шляху холостого пробігу машин. Обгрунтування вибору методу та алгоритм розв"язання задачі. Опис математичної моделі задачі. Інтерфейс та лістинг программи. Заповнення таблиці суміжності для заданого графу.
Оптимізація в широкому значенні слова знаходить застосування в науці, техніці i у будь-який іншій області людської діяльності. Оптимізація - цілеспрямована діяльність, що полягає в одержанні найкращих результатів при відповідних умовах. Пошуки оптимальних розвязків привели до створення спеціальних математичних методів i вже в 18 столітті були закладені математичні основи оптимізації (варіаційне числення, чисельні методи й інші).Необхідно знайти найкоротшу відстань і маршрут від заводу збірного залізобетону, що знаходиться в пункті 1 до будівельних майданчиків 2-9 при заданій схемі автомобільних шляхів (рис.1). Знайти також найкоротший шлях холостого пробігу машин за умови, що частина доріг має односторонній напрямок руху (вказано стрілками на схемі). В даній задачі стоїть завдання знайти найкоротшу відстань і маршрут від заводу збірного залізобетону до будівельних майданчиків, а це є алгоритм Дейкстри (задача про найкоротший ланцюг). Вирішення цієї задачі (за алгоритмом Дейксти) базується на наступному принципі: якщо відомо найкоротший ланцюг з Х в Y і на цьому ланцюзі знаходиться вершина Z, то найкоротший ланцюг з XZ співпадає з ZY . Графом G(V,E) називається сукупність двох множин - не порожньої множини V (множини його вершин) та множини Е невпорядкованих пар елементів в множині V, Е - множина ребер графа.begin for i:=1 to G.COLCOUNT do for j:=1 to G.COLCOUNT do begin begin n:=STRTOINT(Edit1.Text); begin for i := 1 to n do for j := 1 to n do begin p[i, j] := i; if G2.Cells[i,j][1] in ["1".."9"] then begin path(j,i); memo1.Lines.Add(INTTOSTR(i) "->" str INTTOSTR(j)); end; end;В результаті ми отримуємо дві матриці - матрицю мінімальних відстаней між заводом залізобетону та будівельними майданчиками: Враховуючи те, що деяка частина доріг має односторонній напрямок руху, для прикладу наведемо такі данні: · Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 2 (буд. майданчик )становить 22 , проте якщо ми будемо рухатись від пункту 2 до пункту 1, відстань між ними буде становити 2. · Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 3 (буд. майданчик )становить 15, проте якщо ми будемо рухатись від пункту 3 до пункту 1, відстань між ними буде становити 7. і т.д. · Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 4 (буд. майданчик ) становить 10, проте якщо ми будемо рухатись від пункту 4 до пункту 1, відстань між ними збільшиться і буде становити 11. · Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 5 (буд. майданчик ) становить 9. · Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 6 (буд. майданчик ) становить 4.
План
Зміст
Вступ
1. Постановка задачі
2. Обґрунтування вибору методу та алгоритм розвязання задачі
3. Опис математичної моделі задачі
4. Інтерфейс програми
5. Лістинг програми
6. Контрольний приклад
Список використаної літератури
Список литературы
1. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. - М.: Мир, 1972.
2. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. - М.: Наука, 1986.
3. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986.
Размещено на
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
