/>/>/>/>/>Аннотация
Транспортнаязадача с правильным балансом состоит в том, чтобы найти оптимальный план позаданной таблице перевозок, при котором стоимость перевозок будет минимальна.
Такаязадача актуальна в областях связанных с транспортировкой грузов.
САРОВСКИЙ ГОСУДАРСТВЕННЫЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ КАФЕДРА МАТЕМАТИЧЕСКИХ МЕТОДОВ И ИССЛЕДОВАНИЙ ОПЕРАЦИЙ В ЭКОНОМИКЕ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ на тему:
Решение транспортной задачи с правильным балансом Студента руководитель работы консультанты работы Зав. кафедрой
г. Саров
2005 г /> /> /> /> /> /> /> /> /> /> />
Оглавление
Введение. 3
Постановка задачи. 4
Метод решения. 5
Язык программирования. 7
Описание алгоритма. 8
Описание основных структурданных. 12
Описание интерфейса спользователем. 14
Заключение. 16
Литература. 17
Текст программы… 18
/>/>/>/>/>Введение
Задачасостоит в том, чтобы наитии такой способ перевозки при котором затратысвязанные с перевозкой были бы минимальны
Этазадача заинтересовала меня потому, что её решение напрямую связанно с экономиейсредств. Важно нахождение такого алгоритма, который позволит наиболееоптимально решить задачу.
/>/>/>/>/>Постановка задачи
Транспортнаязадача ставится следующим образом: имеется mпунктовотправления А1, А2, ..., Аm, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственноа1, а2,…, аm. Имеется nпунктовназначения В1, В2,…, Вnподавшиезаявки соответственно на b1, b2,…, bnгруза.Известны стоимости Сi,jперевозкиот каждого пункта отправления Аiдокаждого пункта назначения Вj. Все числа Сi,j,образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок(откуда, куда и сколько поставить), чтобы все заявки были выполнены, а общая стоимостьвсех перевозок была минимальна.
/>/>/>/>/>Метод решения
/>/>/>
1.Составление опорного плана.
Решениетранспортной задачи начинается с нахождения опорного плана. Для этого существуютразличные способы. Например, способ “северо-западного угла” Рассмотрим конкретныйпримере:
Условиятранспортной задачи заданы транспортной таблицей.
/> ПН
ПО В1 В2 В3 В4 В5
Запасы
аi А1 10 8 5 6 9 48 А2 6 7 8 6 5 30 А3 8 7 10 8 7 27 А4 7 5 4 6 8 20
Заявки
bj 18 27 42 12 26 125
Будемзаполнять таблицу перевозками постепенно начиная с левой верхней ячейки(“северо-западного угла“ таблицы). Будем рассуждать при этом следующим образом.Пункт В1 подал заявку на 18 единиц груза. Удовлетворим эту заявку за счётзапаса 48, имеющегося в пункте А1, и запишем перевозку 18 в клетке (1,1).После этого заявка пункта В1 удовлетворена, а в пункте А1 осталось ещё 30 единицгруза. Удовлетворим за счёт них заявку пункта В2 (27 единиц), запишем 27 в клетке(1,2); оставшиеся 3 единицы пункта А1 назначим пункту В3. В составе заявки пунктаВ3 остались неудовлетворёнными 39 единиц. Из них 30 покроем за счёт пункта А2,чем его запас будет исчерпан, и ещё 9 возьмём из пункта А3. Из оставшихся 18 единицпункта А3 12 выделим пункту В4; оставшиеся 6 единиц назначим пункту В5, что вместесо всеми 20 единицами пункта А4 покроет его заявку. На этом распределение запасовзакончено; каждый пункт назначения получил груз согласно своей заявки. Это выражаетсяв том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце— заявке. Таким образом, нами сразу же составлен план перевозок, удовлетворяющийбалансовым условиям. Полученное решение является опорным решением транспортной задачи:
/> ПН
ПО В1 В2 В3 В4 В5
Запасы
аi А1
10
18
8
27
5
3 6 9 48 А2 6 7
8
30 6 5 30 А3 8 7
10
9
8
12
7
6 27 А4 7 5 4 6
8
20 20
Заявки
bj 18 27 42 12 26 125
Составленныйнами план перевозок, не является оптимальным по стоимости, так как при его построениимы совсем не учитывали стоимость перевозок Сi,j.
2.Распределительный метод достижения оптимальногоплана
Теперьпопробуем улучшить план, составленный способом “северо-западного угла”.Перенесем, например, 18 единиц из клетки (1,1) в клетку (2,1) и чтобы не нарушитьбаланса перенесём те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новыйплан. Подсчитав стоимость опорного плана (она ровняется 1039) и стоимость новогоплана (она ровняется 913) нетрудно убедиться что стоимость нового плана на 126 единицменьше. Таким образом за счёт циклической перестановки 18 единиц груза из однихклеток в другие нам удалось понизить стоимость плана:
/> ПН
ПО В1 В2 В3 В4 В5
Запасы
аi А1
10
8
27
5
21 6 9 48 А2
6
18 7
8
12 6 5 30 А3 8 7
10
9
8
12
7
6 27 А4 7 5 4 6
8
20 20
Заявки
bj 18 27 42 12 26 125
Наэтом способе уменьшения стоимости в дальнейшем и будет основан алгоритмоптимизации плана перевозок. Циклом в транспортной задаче мы будем называть несколькозанятых клеток, соединённых замкнутой ломанной линией, которая в каждой клетке совершаетповорот на 90°.
Существуетнесколько вариантов цикла:
/>1.) 2.) 3.)/> /> /> /> /> /> /> /> /> /> /> /> /> />
Нетрудноубедиться, что каждый цикл имеет чётное число вершин и значит, чётное число звеньев(стрелок). Условимся отмечать знаком “+” те вершины цикла, в которых перевозкинеобходимо увеличить, а знаком “-“ те вершины, в которых перевозки необходимоуменьшить. Цикл с отмеченными вершинами будем называть “означенным”. Перенести какое-токоличество единиц груза по означенному циклу — это значит увеличить перевозки,стоящие в положительных вершинах цикла, на это количество единиц, а перевозки,стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переноселюбого числа единиц по циклу равновесие между запасами и заявками не меняется:по прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозокв каждом столбце — заявке этого столбца. Таким образом при любом циклическомпереносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым.Стоимость же плана при этом может меняться: увеличиваться или уменьшатся.Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицыгруза по означенному циклу. Очевидно цена цикла ровна алгебраической сумме стоимостей,стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком“+”, а в отрицательных со знаком “-“. Вершины чередуются начиная с “+”. Обозначимцену цикла через g. При перемещении одной единицы груза поциклу стоимость перевозок увеличивается на величину g.При перемещении по нему kединиц груза стоимость перевозок увеличиться на kg.Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам,цена которых отрицательна. Каждый раз, когда нам удаётся совершить такоеперемещение стоимость плана уменьшается на соответствующую величину kg.Так как перевозки не могут быть отрицательными, мы будем пользоваться только такимициклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоятположительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось,это означает, что дальнейшее улучшение плана невозможно, то есть оптимальныйплан достигнут.
Методпоследовательного улучшения плана перевозок и состоит в том, что в таблице отыскиваютсяциклы с отрицательной ценой, по ним перемещаются перевозки, и план улучшается дотех пор пока циклов с отрицательной ценой уже не останется. Можно доказать, чтодля любой свободной клетке транспортной таблице всегда существует цикл и притомединственный, одна из вершин которого лежит в этой свободной клетке, а все остальныев базисных клетках. Если цена такого цикла, с плюсом в свободной клетке,отрицательна, то план можно улучшить перемещением перевозок по данному циклу.Количество единиц груза k,которое можно переместить, определяется минимальным значением перевозок,стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза,возникнут отрицательные перевозки).
Применённыйвыше метод отыскания оптимального решения транспортной задачи называется распределённым;он состоит в непосредственном отыскании свободных клеток с отрицательной ценой циклаи в перемещении перевозок по этому циклу.
Языкпрограммирования
Длянаписания программы был выбран язык VBAпо следующим причинам:
1.Visual Basicfor Applicationsбыл написан специально для 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. БеляевС.П. Курс лекций по «Исследованию операций».