Решение транспортной задачи с правильным балансом (стр. 1 из 2)

Аннотация

Транспортная задача с правильным балансом состоит в том, чтобы найти оптимальный план по заданной таблице перевозок, при котором стоимость перевозок будет минимальна.

Такая задача актуальна в областях связанных с транспортировкой грузов.

САРОВСКИЙ ГОСУДАРСТВЕННЫЙ

ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА МАТЕМАТИЧЕСКИХ МЕТОДОВ И

ИССЛЕДОВАНИЙ ОПЕРАЦИЙ В ЭКОНОМИКЕ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОЙ РАБОТЕ

на тему:

Решение транспортной задачи с правильным балансом

Студента

руководитель работы

консультанты работы

Зав. кафедрой

г. Саров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, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки).