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

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

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

Воронеж 2003 г.

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

Замечание.

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

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

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

где x_ij количество продукции, поставляемое со склада 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

Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать при этом следующим образом. Пункт В₁ подал заявку на 18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте А₁ , и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В₁ удовлетворена, а в пункте А₁ осталось ещё 30 единиц груза. Удовлетворим за счёт них заявку пункта В₂ (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта А₁ назначим пункту В₃ . В составе заявки пункта В₃ остались неудовлетворёнными 39 единиц. Из них 30 покроем за счёт пункта А₂ , чем его запас будет исчерпан, и ещё 9 возьмём из пункта А₃ . Из оставшихся 18 единиц пункта А₃ 12 выделим пункту В₄ ; оставшиеся 6 единиц назначим пункту В₅ , что вместе со всеми 20 единицами пункта А₄ покроет его заявку. На этом распределение запасов закончено; каждый пункт назначения получил груз, согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце - заявке. Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи:

Таблица № 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 .

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

При этом методе может получиться, что стоимости перевозок C_ij и C_ik от пункта A_i к пунктам B_j и B_k равны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2: C₂₁ = C₂₄ , но заявка b₁ больше заявки b₄ , поэтому 4 единицы продукции мы распределим в клетку (2,1).

Таблица № 3

ПН ПО	В1	В2	В3	В4	В5	Запасы а i
А1	10	8	5 42	6 6	9	48
А2	6 4	7	8	6	5 26	30
А3	8	7 27	10	8	7 0	27
А4	7 14	5	4	6 6	8	20
Заявки bj	18	27	42	12	26	125

Способ минимальной стоимости по столбцу аналогичен предыдущему способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию от пунктов B_i к пунктам A_j по минимальной стоимости C_ji .

Опорный план, составленный способами минимальных стоимостей, обычно более близок к оптимальному решению. Так в нашем примере общие затраты на транспортировку по плану, составленному первым способом F₀ = 1039, а по второму F₀ = 723.

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными . Их число должно равняться m + n - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю. Так, например, в таблице № 3:

m + n - 1 = 4 + 5 - 1 = 8,

а базисных клеток 7, поэтому нужно в одну из клеток строки 3 или столбца 2 поставить значение “0”. Например в клетку (3,5).

Составляя план по способам минимальных стоимостей в отличии от плана по способу северо-западного угла мы учитываем стоимости перевозок C_ij , но все же не можем утверждать, что составленный нами план является оптимальным.

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

Теперь попробуем улучшить план, составленный способом северо-западного угла. Перенесем, например, 18 единиц из клетки (1,1) в клетку (2,1) и чтобы не нарушить баланса перенесём те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новый план. Подсчитав стоимость опорного плана (она ровняется 1039) и стоимость нового плана (она ровняется 913) нетрудно убедиться, что стоимость нового плана на 126 единиц меньше. Таким образом, за счёт циклической перестановки 18 единиц груза из одних клеток в другие нам удалось понизить стоимость плана:

Таблица №4

ПН ПО	В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

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