• Введение 3
• Постановка задачи 4
• Метод решения 5
• Язык программирования 7
• Описание алгоритма 8
• Описание основных структур данных 12
• Описание интерфейса с пользователем 14
• Заключение 16
• Литература 17
• Текст программы 18

Введение

Теперь попробуем улучшить план, составленный способом “северо-западного угла”. Перенесем, например, 18 единиц из клетки (1,1) в клетку (2,1) и чтобы не нарушить баланса перенесём те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новый план. Подсчитав стоимость опорного плана (она ровняется 1039) и стоимость нового плана (она ровняется 913) нетрудно убедиться что стоимость нового плана на 126 единиц меньше. Таким образом за счёт циклической перестановки 18 единиц груза из одних клеток в другие нам удалось понизить стоимость плана:

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

Существует несколько вариантов цикла :

1.) 2.) 3.)

Нетрудно убедиться, что каждый цикл имеет чётное число вершин и значит, чётное число звеньев (стрелок). Условимся отмечать знаком “+” те вершины цикла, в которых перевозки необходимо увеличить, а знаком “-“ те вершины, в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть “означенным”. Перенести какое-то количество единиц груза по означенному циклу -- это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце -- заявке этого столбца. Таким образом при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно цена цикла ровна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком “+”, а в отрицательных со знаком “-“. Вершины чередуются начиная с “+”. Обозначим цену цикла через . При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину . При перемещении по нему k единиц груза стоимость перевозок увеличиться на k. Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удаётся совершить такое перемещение стоимость плана уменьшается на соответствующую величину k. Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут.

Метод последовательного улучшения плана перевозок и состоит в том, что в таблице отыскиваются циклы с отрицательной ценой, по ним перемещаются перевозки, и план улучшается до тех пор пока циклов с отрицательной ценой уже не останется. Можно доказать, что для любой свободной клетке транспортной таблице всегда существует цикл и притом единственный, одна из вершин которого лежит в этой свободной клетке, а все остальные в базисных клетках. Если цена такого цикла, с плюсом в свободной клетке, отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза k, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки).

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

Язык программирования

Для написания программы был выбран язык VBA по следующим причинам:

1. Visual Basic for Applications был написан специально для Office приложений то есть потенциальному заказчику достаточно установит Office и запустить Ms Excel чтобы программы работала

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).

Описание основных структур данных