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

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х₃₅ ;

Такие задачи целесообразно решать при помощи особого варианта симплекс-метода – так называемого метода потенциалов .

Все транспортные задачи имеют оптимальное решение . Если все значение a_j и b_i в условиях транспортной задачи целочисленные, то переменныеx_ij во всех базисных решениях (а так же и в любом оптимальном базисном решении) имеют целочисленные значения.

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

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

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

а b	20	5	10	10	5
15	5	6	3	5	9
15	6	4	7	3	5
20	2	5	3	1	8

Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать при этом следующим образом. Пункт а₁ подал заявку на 20 единиц груза. Удовлетворим эту заявку за счёт запаса 15, имеющегося в пункте b ₁ , и запишем перевозку 15 в клетке (1,1). После этого дополним заявку за счет заявка пункта b ₂ , и запишем5 в клетке (1,2), теперь заявка удовлетворена, но в пункте b ₂ осталось ещё 10 единиц груза. Удовлетворим за счёт них заявку пунктов а₂ (5 единиц клетка 2,2) и а₃ (5 единиц клетка 2,3). На складе b ₃ есть запас в 20 единиц, за счет его мы удовлетворим оставшиеся заявки а₃ (оставшиеся 5 единиц клетка 3,3), а₃ (10 единиц клетка 3,4) и а₅ (5 единиц клетка 3,5).

5
6	4	7
3	1	8

--> ЧИТАТЬ ПОЛНОСТЬЮ <--