Задачи линейного программирования. Алгоритм Флойда (стр. 2 из 3)
Если j-й продукт производится в количестве xj, то в рамках описанных выше технологий мы должны потратить a1,jxjпервого ресурса, a2,jxj— второго, и так далее, amjxj — т-го. Сводный план производства по всем продуктам может быть представлен в виде n-мерного вектора-строки x = (x1,x2,...,xj,...,xn) . Тогда общие затраты по i-му ресурсу на производство всех продуктов можно выразить в виде суммы
представляющей собой скалярное произведение векторов аjи х. Очевидно, что всякая реальная производственная система имеет ограничения на ресурсы, которые она тратит в процессе производства. В рамках излагаемой модели эти ограничения порождаются m-мерным вектором b = (b1,b2,...,bm), где bi — максимальное количество i-го ресурса, которое можно потратить в производственном процессе. В математической форме данные ограничения представляются в виде системы т неравенств:
a1,1 xl+al,2x2+...+al,n xn £ bl,
o2,l xl+a2,2 x2+...+a2,n xn £ b2,
am,l xl+am,2 x2+...+am,n xn£ bn.(7)
Применяя правила матричной алгебры, систему (7) можно записать в краткой форме, представив левую часть как произведение матрицы А на вектор х, а правую — как вектор b:
Ах £ b. (8)
К системе (8) также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства: x1, ³ 0,..., xj³0, ..., хп³0, или, что то же самое,
x³ 0. (9)
Обозначив через сjцену единицы j-го продукта, получим выражение суммарного дохода от выполнения плана производства, задаваемого вектором х:
(10)Формулы (8)-(10) являются не чем иным, как простейшей математической моделью, описывающей отдельные стороны функционирования некоторого экономического объекта, поведением которого мы хотим управлять. В рамках данной модели, вообще говоря, можно поставить различные задачи, но, скорее всего, самой «естественной» будет задача поиска такого плана производства xÎRn, который дает наибольшее значение суммарного дохода, т. е. функции (10), и одновременно удовлетворяет системе ограничений (8)-(9). Кратко такую задачу можно записать в следующем виде:
где 
(11)Несмотря на явную условность рассматриваемой ситуации и кажущуюся простоту задачи (11), ее решение является далеко не тривиальным и во многом стало практически возможным только после разработки специального математического аппарата. Существенным достоинством используемых здесь методов решения является их универсальность, поскольку к модели (11) могут быть сведены очень многие как экономические, так и неэкономические проблемы.
Поскольку любая научная модель содержит упрощающие предпосылки, для корректного применения полученных с ее помощью результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее «сильным» упрощением в рассмотренной модели является предположение о прямо пропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат аi,j. Очевидно, что это допущение далеко не всегда выполняется. Так, объемы расхода многих ресурсов (например, основных фондов) изменяются скачкообразно в зависимости от изменения компонентов объема производства х. К другим упрощающим предпосылкам относятся предположения о независимости цен сj от объемов хj, что справедливо лишь для определенных пределов их изменения, пренебрежение эффектом кооперации в технологиях и т. п. Данные «уязвимые» места важно знать еще и потому, что они указывают принципиальные направления совершенствования модели.
2 Алгоритм Флойда. Постановка задачи
Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.
Основная идея метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 1). Если выполняется неравенство dij + djk < dik, то целесообразно заменить путь i -> k путем i -> j -> k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.
Рис.1. Треугольный оператор
Определяем начальную матрицу расстояния D0 и матрицу последовательности узлов S0. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1:
Рис.2. Начальная ситуация
Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам dij матрицы Dk-1. Если выполняется неравенство dik + dkj < dij, (i <> k, j <> k, i <> j), тогда выполняем следующие действия:
создаем матрицу Dk путем замены в матрице Dk-1 элемента dij на сумму dik + dkj,
создаем матрицу Sk путем замены в матрице Sk-1 элемента sij на k. Полагаем k = k + 1 и повторяем шаг k.
Поясним действия, выполняемые на k-м шаге алгоритма, представив матрицу Dk-1 так, как она показана на рисунке 3. На этом рисунке строка k и столбец k являются ведущими. Строка i - любая строка с номером от 1 до k - 1, а строка p - произвольная строка с номером от k + 1 до n. Аналогично столбец j представляет любой столбец с номером от 1 до k - 1, столбец q - произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:
Рис.3. Иллюстрация алгоритма Флойда
После реализации n шагов алгоритма определение по матрицам Dn и Sn кратчайшего пути между узлами i и j выполняется по следующим правилам.
Расстояние между узлами i и j равно элементу dij в матрице Dn.
Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i -> k -> j. Если далее sik = k и skj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.
Пример. Найдем для сети, показанной на рисунке 4, кратчайшие пути между любыми двумя узлами. Расстояние между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3, 5) ориентированно, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны:
Рис.4. Пример сети
Начальные матрицы D0 и S0 строятся непосредственно по заданной схеме сети. Матрица D0 симметрична, за исключением пары элементов d35 и d53, где d53 равно бесконечности, поскольку невозможен переход от узла 5 к узлу 3:
Рис.5. Начальное состояние
В матрице D0 выделены ведущие строка и столбец (k = 1). Двойной рамкой представлены элементы d23 и d32, единственные среди элементов матрицы D0, значения которых можно улучшить с помощью треугольного оператора. Таким образом, чтобы на основе матриц D0 и S0 получить матрицы D1 и S1, выполняем следующие действия.
Заменяем d23 на d21 + d13 = 3 + 10 = 13 и устанавливаем s23 = 1.
Заменяем d32 на d31 + d12 = 10 + 3 = 13 и устанавливаем s32 = 1.
Матрицы D1 и S1 имеют следующий вид:
Рис.6. Матрицы D1 и S1
Полагаем k = 2; в матрице D1 выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D1 и S1, выделенным двойной рамкой.
В результате получаем матрицы D2 и S2:
Рис.7. Матрицы D2 и S2
Полагаем k = 3; в матрице D2 выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D2 и S2, выделенным двойной рамкой. В результате получаем матрицы D3 и S3:
Рис.8. Матрицы D3 и S3
Полагаем k = 4, ведущие строка и столбец в матрице D3 выделены. Получаем новые матрицы D4 и S4:
