Смекни!
smekni.com

Решение задач транспортного типа методом потенциалов (стр. 1 из 4)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ

Факультет заочно-послевузовского обучения

КУРСОВАЯ РАБОТА

По дисциплине: "Методы оптимизации"

На тему: " Решение задач транспортного типа методом потенциалов "

Воронеж 2003 г.

СОДЕРЖАНИЕ

1. Линейная транспортная задача. 3

2. Математическая модель транспортной задачи. 4

3. Составление опорного плана. 5

4. Распределительный метод достижения оптимального плана. 8

5. Решение транспортной задачи методом потенциалов. 11

Список использованной литературы.. 16

1. Линейная транспортная задача.

Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k С i j.

Далее, предполагается, что

где ai есть количество продукции, находящееся на складе i, и bj – потребность потребителя j.

Замечание.

1. Если сумма запасов в пунктах отправления превышает сумму поданных заявок

то количество продукции, равное
остается на складах. В этом случае мы введем "фиктивного" потребителя n +1 с потребностью
и положим транспортные расходы pi,n+1 равными 0 для всех i.

2. Если сумма поданных заявок превышает наличные запасы

то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m + 1 с запасом
и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

2. Математическая модель транспортной задачи.

где xij количество продукции, поставляемое со склада i потребителю j, а С i j издержки (стоимость перевозок со склада i потребителю j).

3. Составление опорного плана.

Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ северо-западного угла, способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы.

Рассмотрим простейший, так называемый способ северо-западного угла. Пояснить его проще всего будет на конкретном примере:

Условия транспортной задачи заданы транспортной таблицей.

Таблица № 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 покроет его заявку. На этом распределение запасов закончено; каждый пункт назначения получил груз, согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце - заявке. Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи:

Таблица № 2

ПН

ПО

В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

Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сij .

Другой способ - способ минимальной стоимости по строке - основан на том, что мы распределяем продукцию от пункта Ai не в любой из пунктов Bj, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов Bj. Во всем остальном этот метод схож с методом северо-западного угла. В результате, опорный план, составленный способом минимальной стоимости по строке выглядит, так как показано в таблице № 3.

При этом методе может получиться, что стоимости перевозок Cij и Cikот пункта Ai к пунктам Bjи Bk равны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2: C21 = C24, но заявка b1 больше заявки b4, поэтому 4 единицы продукции мы распределим в клетку (2,1).