Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 185 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

Составители: 

Рубрика: 

185
Глава 5. УСЛОЖНЕННЫЕ И ВИДЕОИЗМЕНЕННЫЕ
ПОСТАНОВКИ ТРАНСПОРТНОЙ ЗАДАЧИ.
Транспортная задача линейного программирования в 4 главе рассматривалась в
простейшем общем варианте и вместе с тем в ее естественном виде (в канонической
форме).
В то же время довольно широкая сфера применения транспортных алгоритмов
обусловливает необходимость более сложных постановок транспортной задачи и ее
видоизменения. Иная постановка задачи может потребовать и иные способы ее решения.
Однако в большинстве случаев изменения формулировки транспортной задачи вызывают
необходимость преобразования первоначальной модели и исходной матрицы, а сами
алгоритмы решения остаются теми же.
В этой главе будут рассмотрены наиболее важные примеры усложненной
постановки транспортной задачи применительно к вопросам оптимизации перевозок, а
также планирования и управления производством и рассмотрена методика приведения
поставленных задач к типу и форме транспортных с тем, чтобы решение могло быть
выполнено с помощью транспортных алгоритмов.
Для решения целого ряда экономических задач транспортные алгоритмы
оказываются неприемлемыми, а симплексный метод приводит к довольно трудоемким
вычислениям. В этих случаях могут оказаться полезными и более рациональные
видоизмененные постановки транспортной задачи. Одна из таких видоизмененных
постановок получила название обобщенной транспортной задачи (или ламбда-задачи).
Алгоритм ламбда-задачи оказался наиболее удобным для решения разного вида
распределительных задач. Поэтому он также будет рассмотрен в этой главе.
5.1. Транспортная задача с вырожденным опорным планом
Как в постановке транспортной задачи 1.3, так и в примерах, рассмотренных нами
в 4.1, 4.2, мы всюду встречались с опорными планами, в которых число базисных клеток,
занятых числами x
ij
>0, было равно рангу системы ограничительных уравнений r=m+n-1.
Это позволяло беспрепятственно выполнять проверку планов на оптимальность
посредством вычисления оценок и характеристик всех свободных клеток.
Опорные планы, в которых число положительных поставок x
ij
>0 равно рангу
системы ограничительных уравнений, считаются невырожденными.
В практике решения задач нередки случаи распределения, при которых число
положительных поставок x
ij
>0 оказывается меньше, чем m+n-1. Такие планы считаются
вырожденными.
Вырожденным может оказаться исходный опорный план или любой
промежуточный.
Вырожденность плана вытекает непосредственно из условия задачи, когда при
записи поставки в какую-то клетку мощность окажется равной спросу, т. е.
x
ij
=min(a
i
,b
j
) при a
i
= b
j.
В этом случае из. дальнейшего распределения одновременно будут исключены и
строка и столбец. Тогда число базисных клеток получится меньше, чем т+п-1, и не все
они лучем могут быть связаны между собой, поэтому нельзя будет построить циклы для
всех свободных клеток.
В таких случаях, прежде чем допустимый опорный план проверять на
оптимальность, надо преодолеть вырожденность. Для этого в одну из свободных клеток
следует записать поставку x
ij
=0. Если же до ранга системы не хватает двух базисных
клеток, нулевые поставки записываются в две свободные клетки и т. д.

Страницы