Содержание1 Постановка задач линейногопрограммирования (ЗЛП). Примеры экономических задач, сводящихся к ЗЛП. Допустимыеи оптимальные решения
2 Алгоритм Флойда. Постановка задачи
1 Постановка задач линейногопрограммирования (ЗЛП). Примеры экономических задач, сводящихся к ЗЛП.Допустимые и оптимальные решения
В общем виде задача линейного программирования (в дальнейшем ЗЛП)может быть сформулирована как задача нахождения наибольшего значения линейнойфункции
/> (1)
на некотором множестве D Ì Rn, где x Î D удовлетворяют системеограничений
/>
/>
/>
/>
/> (2)
и, возможно, ограничениям
/> (3)
He умаляя общности, можно считать, что в системе (2) первые т ограниченийявляются неравенствами, а последующие — l-уравнениями. Очевидно,этого всегда можно добиться за счет простого переупорядочения ограничений.Относительно направления знака неравенства будем предполагать, что левая частьменьше или равна правой. Добиться этого можно, умножив на (-1) обе части технеравенств, которые имеют противоположный знак. Ограничения (3), вообще говоря,могут быть рассмотрены как частный случай ограничений в форме неравенств, но всилу особой структуры их обычно выделяют отдельно и называют условияминеотрицательности (или тривиальными ограничениями).
Дополнительно следует заметить, что выбор типа искомого экстремума(максимума или минимума) также носит относительный характер. Так, задача поискамаксимума функции
/>
эквивалентна задаче поиска минимума функции
/>
Часто условия задачи (1) — (3), содержащей ограничения только типанеравенств, бывает удобно записывать в сокращенной матричной форме
/>
где с и x — векторы из пространства Rn, b — вектор из пространства Rm, a А — матрица размерности m ´ п.
Задачу линейного программирования, записанную в форме (1) — (3),называют общей задачей линейного программирования (ОЗЛП).
Если все ограничения в задаче линейного программирования являютсяуравнениями и на все переменные xj наложены условиянеотрицательности, то она называется задачей линейного программирования вканонической форме, или канонической задачей линейного программирования (КЗЛП).В матричной форме КЗЛП можно записать в следующем виде:
/>
Поскольку любая оптимизационная задача однозначно определяетсяцелевой функцией f и областью D, на которой отыскивается оптимум (максимум), будем обозначать этузадачу парой (D,f).
Условимся относительно терминологии, которая используется вдальнейшем и является общепринятой в теории линейного программирования.
Планом ЗЛП называется всякий вектор х из пространства Rn.
Допустимым планом называется такой план ЗЛП, который удовлетворяетограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областьюдопустимых планов. Оптимальным планом х* называется такой допустимыйплан, при котором целевая функция достигает оптимального (в нашем случае —максимального) значения, т. е. план, удовлетворяющий условию
max f(x) = f(x*).
Величина f* = f(x*)называется оптимальным значением целевой функции.
Решением задачи называется пара (х*, f*), состоящая изоптимального плана и оптимального значения целевой функции, а процесс решения заключаетсяв отыскании множества всех решений ЗЛП.Примеры экономическихзадач, сводящихся к ЗЛП.
Несмотря на многообразие задач математического программирования,при их решении можно выделить некоторую общую последовательность этапов, черезкоторые проходит любое операционное исследование. Как правило, это:
1.Постановка задачи.
2.Построение содержательной(вербальной) модели рассматриваемого объекта (процесса). На данном этапепроисходит формализация цели управления объектом, выделение возможныхуправляющих воздействий, влияющих на достижение сформулированной цели, а такжеописание системы ограничений на управляющие воздействия.
3.Построение математической модели, т. е. перевод сконструированнойвербальной модели в ту форму, в которой для ее изучения может быть использованматематический аппарат.
4.Решение задач, сформулированных на базе построенной математическоймодели.
5.Проверка полученных результатов на их адекватность природеизучаемой системы, включая исследование влияния так называемых внемодельныхфакторов, и возможная корректировка первоначальной модели.
6.Реализация полученного решения на практике.
Математическое моделирование в исследовании операций является, с однойстороны, очень важным и сложным, а с другой — практически не поддающимсянаучной формализации процессом. Заметим, что неоднократно предпринимавшиесяпопытки выделить общие принципы создания математических моделей приводили либок декларированию рекомендаций самого общего характера, трудноприложимых длярешения конкретных проблем, либо, наоборот, к появлению рецептов, применимых вдействительности только к узкому кругу задач. Поэтому более полезнымпредставляется знакомство с техникой математического моделирования наконкретных примерах.
В качестве таких примеров приведем несколько классическихэкономико-математических моделей и задач, которые могут быть сформулированы наих основе.
Управление портфелем активов. Рассмотрим проблемупринятия инвестором решения о вложении имеющегося у него капитала. Наборхарактеристик потенциальных объектов для инвестирования, имеющих условные именаот А до F,задается следующей таблицей.Название Доходность (в %) Срок выкупа (год) Надежность (в баллах) А 5,5 2001 5 В 6,0 2005 4 С 8,0 2010 2 D 7,5 2002 3 Е 5,5 2000 5 F 7,0 2003 4
Предположим, что при принятии решения о приобретении активовдолжны быть соблюдены условия:
a. суммарный объем капитала,который должен быть вложен, составляет $ 100 000;
b.доля средств, вложенная в один объект, не может превышать четвертиот всего объема;
c. более половины всехсредств должны быть вложены в долгосрочные активы (допустим, на рассматриваемыймомент к таковым относятся активы со сроком погашения после 2004 г.);
d.доля активов, имеющих надежность менее чем 4 балла, не можетпревышать трети от суммарного объема.
Приступим к составлению экономико-математической модели для даннойситуации. Целесообразно начать процесс с определения структуры управляемыхпеременных. В рассматриваемом примере в качестве таких переменных выступаютобъемы средств, вложенные в активы той или иной фирмы. Обозначим их как хА,хВ, хС, хD, хE, хF. Тогда суммарная прибыль от размещенных активов, которуюполучит инвестор, может быть представлена в виде
/> (1)
На следующем этапе моделирования мы должны формально описатьперечисленные выше ограничения a-d на структуру портфеля.
a) Ограничение на суммарный объем активов:
xA+ xB+ xС + xD+ xE+ xF£100 000. (2)
b) Ограничение на размер доли каждого актива:
хА £ 25 000, хВ £ 25 000, хС £ 25 000,
xd £ 25 000, хе £ 25 000, xf £ 25 000. (3)
c) Ограничение, связанное с необходимостью вкладывать половинусредств в долгосрочные активы:
хВ + хС ³ 50 000 (4)
d) Ограничение на долю ненадежных активов:
xC+ xD£ 30 000. (5)
Наконец, система ограничений в соответствии с экономическим смысломзадачи должна быть дополнена условиями неотрицательности для искомыхпеременных:
хА ³ 0, хB³0, хC³ 0, xD³0, хЕ ³0, xF³ 0. (6)
Выражения (1)-(6) образуют математическую модель поведенияинвестора. В рамках этой модели может быть поставлена задача поиска такихзначений переменных ха, хB, хC, xd, xe,хF,при которыхдостигается наибольшее значение прибыли (т. е. функции (1)) и одновременновыполняются ограничения на структуру портфеля активов (2)-(6).
Перейдем теперь к рассмотрению более общих моделей и задач.
Простейшая задача производственного планирования. Пусть имеется некоторыйэкономический объект (предприятие, цех, артель и т. п.), который можетпроизводить некоторую продукцию п видов. В процессе производства допустимоиспользование т видов ресурсов (сырья). Применяемые технологии характеризуютсянормами затрат единицы сырья на единицу производимого продукта. Обозначим черезai,j количество i-го ресурса (iÎ 1: m),которое тратится на производство единицы j-го продукта (jÎ1:n). Весь набор технологических затрат в производстве j-го продукта можнопредставить в виде вектора-столбца
/>
а технологию рассматриваемого предприятия (объекта) в видепрямоугольной матрицы размерности т на п:
/>
Если 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,nxn £ bl,
o2,l xl+a2,2 x2+...+a2,nxn £ b2,
am,l xl+am,2 x2+...+am,nxn £ 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 k путем i -> j -> k. Такая замена (далее еебудем условно называть треугольным оператором) выполняется систематически впроцессе выполнения алгоритма Флойда.
/>
Рис.1. Треугольныйоператор
Определяемначальную матрицу расстояния D0 и матрицу последовательности узлов S0.Диагональные элементы обеих матриц помечаются знаком "-",показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1:
/>
/>
Рис.2. Начальная ситуация
Основной шагk. Задаем строку k и столбец k как ведущую строку и ведущий столбец.Рассматриваем возможность применения треугольного оператора ко всем элементамdij матрицы Dk-1. Если выполняется неравенство dik + dkj 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:
/>
Рис.9. Матрицы D4 и S4
Полагаем k =5, ведущие строка и столбец в матрице D4 выделены. Никаких действий на этомшаге не выполняем; вычисления закончены.
Конечныематрицы D4 и S4 содержат всю информацию, необходимую для определения кратчайшихпутей между любыми двумя узлами сети. Например, кратчайшее расстояние междуузлами 1 и 5 равно d15 = 12.
Длянахождения соответствующих маршрутов напомним, что сегмент маршрута (i, j)состоит из ребра (i, j) только в том случае, когда sij = j. В противном случаеузлы i и j связаны, по крайней мере, через один промежуточный узел. Например,поскольку s15 = 4 и s45 = 5, сначала кратчайший маршрут между узлами 1 и 5будет иметь вид 1->4->5. Но так как s14 не равно 4, узлы 1 и 4 в определенномпути не связаны одним ребром (но в исходной сети они могут быть связанынепосредственно). Далее следует определить промежуточный узел (узлы) междупервым и четвертым узлами. Имеем s14 = 2 и s24 = 4, поэтому маршрут 1->4заменяем 1->2->4. Поскольку s12 = 2 и s24 = 4, других промежуточных узловнет. Комбинируя определенные сегменты маршрута, окончательно получаем следующийкратчайший путь от узла 1 до узла 5: 1->2->4->5. Длина этого путиравна 12 километрам.
Списоклитературы
1. Ляшенко И.Н. Линейное инелинейное программирование. Киев, 1975г.
2. Моисеев Н.Н.Математические задачи системного анализа. Москва, 1981г.
3. Крушевский А.В.Справочник по экономико-математическим моделям и методам. Киев, 1982г.