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

Посмотреть архив целиком

Аннотация


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

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






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

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




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




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

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




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

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


на тему:


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





Студента



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






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









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







г. Саров

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.


Случайные файлы

Файл
26737.rtf
49774.rtf
54088.doc
90825.rtf
179888.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.