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

Курсовая работа

на тему:

"Решение транспортных задач

методом потенциалов"

Содержание.

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

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

3. Метод потенциалов

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

1. Транспортная задача.

Транспортная задача ставится следующим образом: имеется m пунктов отправления_, в которых сосредоточены запасы каких-то однородных грузов. Имеется n пунктов назначения подавшие заявки соответственно на груза. Известны стоимости р _{i j} перевозки единицы груза от каждого пункта отправления до каждого пункта назначения. Все числа р _{i j ,} образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

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

1

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

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

Если то потребность не может быть покрыта. В этом случае начальные условия должны быть изменены таким образом, чтобы потребность в продукции могла быть обеспечена.

Обозначим через x_ij количество продукции, поставляемое со склада i потребителю j . В предложении (1) нам нужно решить следующую задачу (математическая модель транспортной задачи):

2

Транспортную задачу мы можем характеризовать транспортной таблицей и таблицей издержек :

а1		…		а n
b1 bm

p11	…	p1n
pm1	…	pmn

Допустимый план перевозок будем представлять в виде транспортной таблицы:

а1	…	а n
b bm	…
	…

Cумма элементов строки i должна быть равна b_i , а сумма элементов столбца j должна быть равна a_j , и все должны быть неотрицательными.

Пример 1.

20	5	10	10	5
15
15
20

5	6	3	5	9
6	4	7	3	5
2	5	3	1	8

Мы получаем следующую задачу:

х₁₁ +х₁₂ +х₁₃ +х₁₄ +х₁₅ =15,

х₂₁ +х₂₂ +х₂₃ +х₂₄ +х₅₅ =15,

х₃₁ +х₃₂ +х₃₃ +х₃₄ +х₃₅ =20,

х₁₁ +х₂₁ +х₃₁ =20,

х₁₂ +х₂₂ +х₃₂ =5,

х₁₃ +х₂₃ +х₃₃ =10,

х₁₄ +х₂₄ +х₃₄ =10,

х₁₅ +х₂₅ +х₃₅ =5;

х _ij 0 для i = 1,2,3; j = 1,2,3,4,5;

К _min = 5х₁₁ +6х₁₂ +3х₁₃ +5х₁₄ +9х₁₅ +6х₂₁ +4х₂₂ +7х₂₃ +3х₂₄ +5х₂₅ +2х₃₁ +5х₃₂ +3х₃₃ +х₃₄ +8х₃₅ ;

Такие задачи ц

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать