Техника решения транспортной задачи вручную

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 10Следующая ⇒

(МЕТОД ПОТЕНЦИАЛОВ)

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

Сумма потенциалов строки и столбца должна быть равна показателю оптимальности c_ij, т.е.

где - потенциал строки;

- потенциал столбца;

- критерий оптимальности (равный показателю c_ij из условия задачи для вошедших в опорный план клеток).

Рассмотрим технику транспортной задачи вручную на конкретном примере, заданном таблицей.

Решение:

1.Составляем первый опорный план методом Северо-Западного угла.

Целевая функция для этого плана F=1880.

2. Определяем потенциалы из первого опорного плана для заполненных клеток.

Значения в выделенных клетках переносятся из условий задачи и равны c_ij.

3. Заполняем свободные клетки таблицы потенциалов.

Рассмотрим более подробно фрагмент:

Показатель Е называется характеристикой свободных переменных.

Если Е<0 для всех свободных переменных, то исходный план определяет оптимальное решение.

Если Е>0, то можно путем перераспределения поставок улучшить значение функции цели (F). Для этого следует отметить, что перераспределение поставок цепи к этой клетке уменьшает функционал (в расчете на единицу перераспределяемой продукции) на величину характеристики (Е).

Вся таблица имеет вид

4. Находим max значение характеристики свободных переменных (E=max). В нашем примере она находится в клетке S₂ - D₅, и равна 10.

5. Вводим свободную переменную +Q в клетку S₂ - D₅ (см. первый опорный план).

Запомните:

Абсолютная величина поставки Q должна быть в точности равна величине возможных ликвидируемых поставок (в нашем случае +Q=20).

Баланс по столбцам и строкам не должен нарушаться (в нашем примере из-за введения свободной переменной +Q=20 нарушен баланс по строке S₂).

Чтобы сохранить баланс в строке S₂, вводим в клетку S₂ - D₃ свободную переменную -Q=20. Этим самым баланс по строке S₂ восстановлен, но нарушен баланс по столбцу D₃. Восстанавливая его, в клетку S₃ - D₃ введем переменную +Q=20 и в клетку S₃ – D₅ – переменную -Q=20. Эта процедура носит название построение цепей. Очевидно, что цепи должны быть замкнуты.

6. Составляем следующий план перевозок:

7.

	D1	D2	D3	D4	D5	Мощность
S1
S2
S3
S4

Для этого плана целевая функция F=1680 (сравн. с первым планом). Приращение функции цели всегда равно .

Вновь составляем таблицу потенциалов и далее – новый план. Всего для решения рассматриваемой задачи составляется 8 планов перевозок. В итоге 8-й итерации получаем следующее оптимальное решение, для которого целевая функция F=1450→min:

Проверьте себя.

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

Исходные данные - в следующей таблице:

Вариант 13

Примечание

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

Доказательство:

Формула для расчета величины функции цели имеет вид

.

Так как в пустых клетках величина х_ij = 0, то формулу можно записать иначе:

.

но . Отсюда

.

Вспомнив, что и , получим

.

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

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии