Применённый выше метод отыскания оптимального решения транспортной задачи называется распределённым; он состоит в непосредственном отыскании свободных клеток с отрицательной ценой цикла и в перемещении перевозок по этому циклу.
Для написания программы был выбран язык VBA по следующим причинам:
1. VisualBasicforApplications был написан специально для Office приложений то есть потенциальному заказчику достаточно установит Officeи запустить MsExcelчтобы программы работала
2. Так как Транспортная задача заданна в виде таблицы то удобнее решать ее использую возможности табличного редактора
3 . Это один из языков, в котором я неплохо разбираюсь. Поэтому мне удобнее писать программу с помощью VBA.
1.При запуске программы пользователю предлагается ввести количество запасов и запросов
А) Выполняется проверка на правильность ввода. Если введены числа то
Б) Рисуется таблица
2. После прорисовки таблицы пользователю предлагается заполнить таблицу стоимости перевозок
А) После подтверждения заполнения пользователем происходи проверка на правильность ввода
Б) Суммируется строка Запросы и столбец Запасы выполняется проверка на равенство. Если равны то
3. Выполняем построение опорного плана методом Северо-западного угла
A) Cтроим нулевую матрицу заданного размера на “листе2”
Б) Затем методом северо-западного угла исходя из данных на листе “Данные”
В) Переносим получившуюся таблицу на лист “Циклы”
4.Используем метод распределения следующим образом
Из приведенного примера уже можно выделить, как алгоритм перебирает пути. Он действует по следующей схеме:
0. Начальное значение j = 1 (первое место в маршруте).
1. Мы находимся в городе k.
2. Для каждого города (i = от 1 до n)
3. Рассматриваем город i.
4. Если этот город еще не посещен,
4.1. тогда переходим в город i; j увеличиваем на единицу. Добавляем номер города в маршрут на место j. Помечаем город как посещенный. Переходим к пункту 1 (k = i).
4.2. иначе идти некуда, т.е. все города мы посетили.
4.2.1. если j = количеству городов (n), т.е мы добрались до последнего пункта в маршруте и наш путь сформирован,
тогда сравниваем длину пути с длиной минимального маршрута.
4.2.2. Помечаем город как не посещенный и выходим из него. Уменьшаем j на единицу.
5. Берем следующий город (i=i+1).
Описание основных структур данных
Теперь рассмотрим структуру приложения, опишем классы и процедуры, которые были изменены и наполнены кодом.
Программа состоит из 4 классов:
1. CAboutDlg связан со встроенным диалоговым окном «О программе».
2. CKurs_LipinApp управляет запуском приложения и не связан с каким-либо диалоговым окном. [1]
3. CKurs_LipinDlg связансокном IDD_KURS_LIPIN_DIALOG. Этот класс организует постановку и решение задачи.
4. CSetting связан с окном IDD_DIALOG1. В окне вводятся параметры к задаче – расстояния между городами.
Класс CKurs_LipinDlg.
В начале при вызове функции OnInitDialog() переменные заполняются начальными данными. Затем из файла «table.ini» считывается таблица расстояний между городами. И теперь диалоговое окно готово к работе с пользователем.
Функция OnPaint() выводит на экран карту, позволяет выделять города, выбранные пользователем, а также соединяет города линиями-путями, когда задача решена. Кроме того, обеспечивается вывод информации для пользователя: пояснения, длина минимального пути и список расстояний между городами, составляющие минимальный путь.
При нажатии левой кнопкой мыши вызывается функция
OnLButtonDown(). Она определяет по какому городу щелкнул пользователь и ставит/снимает выделение с него. Также здесь осуществляется проверка на количество выделенных городов, т.к. время ожидания решения задачи для количества более 13 городов станет не удовлетворительным (от 1,5 минут и более). Поэтому программа выдаст сообщение, если мы попытаемся выйти за допустимые пределы.
Кнопка «Выбрать стандартные города» выделяет города, которые требуется соединить в условии задачи, а именно Москва, Ярославль, Нижний Новгород, Самара, Саратов, Волгоград, Воронеж, Пенза, Липецк, Тамбов, Орел, Курск, Тула.
Кнопка «Очистить» снимает выделение со всех городов и задает начальные значения ряду необходимых переменных.
Функция OnButton3() связана с кнопкой «Задать пункт отправления». После нажатия кнопки пользователь может щелчком мыши выбрать пункт отправления коммивояжера.
Кнопка «Параметры» вызывает диалоговое окно «Параметры», где пользователь может редактировать таблицу расстояний между городами.
Функция OnOK() обрабатывает нажатие кнопки «Рассчитать путь». Она подготавливает начальные значения для вызова рекурсивной функции: создается таблица расстояний только для выделенных городов, заполняется первоначальный минимальный путь, выводится поясняющая информация. Затем вызывается функция recursiv(), которая перебирает варианты маршрутов, отсекает лишние ветви путей и находит минимальный.
Класс CSetting.
Функция OnInitDialog() программным путем создает и выводит поля ввода, имитируя таблицу расстояний между городами. Затем считывается файл «table.ini», и заполняются поля ввода полученными значениями. Вызывается функция Proverka(), которая сканирует полученные данные на ошибки, т.е. определяет введены ли только цифры, и если нет, тогда удаляет все лишние символы.
По нажатию кнопки «Сохранить» программа передает данные в родительское окно, записывает данные из полей ввода в файл и закрывает диалоговое окно.
При загрузке приложения появляется основное диалоговое окно (рис. 3).
Здесь пользователь может выбрать несколько городов и рассчитать для них минимальный путь.
Чтобы отменить выделение городов нужно щелкнуть по кнопке «Очистить». Нажав кнопку «Рассчитать путь», мы получим результат: города соединены минимальным путем, его длина дана в окне информации, в списке показаны расстояния между городами, входящими в полученный путь (рис. 4).
Кнопка «Выбрать стандартные города» выделяет города, требуемые в задании.
Чтобы выделить пункт отправления коммивояжера нужно выбрать «Задать пункт отправления».
Кнопка «Параметры» вызывает диалоговое окно для ввода расстояний между городами (рис. 5). Это окно является модальным и его особенностью является то, что нет возможности перехода к родительскому окну.
Здесь пользователь может отредактировать расстояния между городами. Для этого нужно щелкнуть в поле ввода, и ввести другое значение. Перемещаться по этой «таблице» можно по строкам при помощи клавиш Tab или Shift+Tab.
По завершении ввода нужно нажать кнопку «Сохранить», чтобы программа записала измененные данные в файл. При этом автоматически проверится правильность введенный информации и все ошибки будут исправлены.
Кнопка «Отмена» позволяет не сохранять введенные изменения, если пользователь ошибся во введенной информации.
По нажатии любой из кнопок диалоговое окно «Параметры» закрывается и мы возвращаемся к главному окну .
Если в строке заголовка главного окна щелкнуть правой кнопкой мыши и выбрать пункт «О программе», то появится диалоговое окно, содержащее сведения о программе и об авторе (рис. 6). Нажав кнопку «OK» возвращаемся к главному окну.
Был разработан алгоритм, позволяющий быстро найти кратчайший путь между городами. По алгоритму разработано приложение, решающее задачу о коммивояжере.
1. Круглински Д., Программирование на Microsoft Visual C++ 6.0 для профессионалов/Пер.с англ. –СПб:Питер; 2004г. – 861 с.: ил.
2. Беляев С.П. Курс лекций по «Исследованию операций».