Теория графов и оптимизация

Один из разделов дискретной арифметики, нередко применяемый при принятии решений - теория графов (см., к примеру, учебные пособия [3,4]). Граф - это совокупа точек, именуемых верхушками графа, некие из которых соединены дугами (дуги назыыают также ребрами). Примеры графов приведены на рис.5.

Рис.5. Примеры графов.


На только-только введенное понятие графа "навешиваются" новые характеристики. Начальному объекту Теория графов и оптимизация приписывают новые свойства. К примеру, вводится и употребляется понятие нацеленного графа. В таком графе дуги имеют стрелки, направленные от одной верхушки к другой. Примеры нацеленных графов даны на рис.6.


Рис.6. Примеры нацеленных графов.

Направленный граф был бы полезен, к примеру, для иллюстрации организации перевозок в транспортной задачке. В Теория графов и оптимизация экономике дугам нацеленного либо обыденного графа нередко приписывают числа, к примеру, цена проезда либо перевозки груза из пт А (исходная верхушка дуги) в пункт Б (конечная верхушка дуги).

Разглядим несколько обычных задач принятия решений, связанных с оптимизацией на графах.

Задачка коммивояжера. Требуется посетить все верхушки графа и возвратиться Теория графов и оптимизация в начальную верхушку, минимизировав издержки на проезд (либо минимизировав время).

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

Многие постановки экономического содержания сводятся к задачке коммивояжера. К примеру:

- составить более прибыльный маршрут обхода наладчика в цехе (контролера, сторожа, милиционера), отвечающего Теория графов и оптимизация за подабающее функционирование данного огромного количества объектов (любой из этих объектов моделируется верхушкой графа);

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

Задачка о кратчайшем пути. Как кратчайшим методом попасть из одной верхушки графа Теория графов и оптимизация в другую? В определениях производственного менеджмента: как кратчайшим методом (и, как следует, с минимальным расходом горючего и времени, более недорого) попасть из пт А в пункт Б? Для решения этой задачки каждой дуге нацеленного графа должно быть сопоставлено число - время движения по этой дуге от исходной верхушки до конечной. Разглядим пример Теория графов и оптимизация (рис.7).


5 1

2 3

1

Рис.7. Начальные данные к задачке о кратчайшем пути.

Ситуацию можно обрисовать не только лишь нацеленным графом с весами, приписанными дугам, да и таблицей (табл.7). В этой таблице двум верхушкам – началу пути и концу пути – ставится в соответствие время в пути. В табл.7 рассматриваются пути без промежных остановок. Более Теория графов и оптимизация сложные маршруты составляются из простых отрезков, перечисленных в табл.4.

Таблица 4.

Начальные данные к задачке о кратчайшем пути.

Начало дуги Конец дуги Время в пути

Спрашивается в задачке: как кратчайшим методом попасть из верхушки 1 в верхушку 4?

Решение.Введем обозначение: С(Т) - длина кратчайшего пути из верхушки 1 в верхушку Т. (Так Теория графов и оптимизация как хоть какой путь, который нужно разглядеть, состоит из дуг, а дуг конечное число, и любая заходит менее 1-го раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа частей всегда достигается.) Рассматриваемая задачка состоит в вычислении С(4) и указании пути, на котором этот минимум Теория графов и оптимизация достигается.

Для начальных данных, представленных на рис.7 и в табл.4, в верхушку 3 заходит только одна стрелка, как раз из верхушки 1, и около этой стрелки стоит ее длина, равная 1, потому С(3) = 1. Не считая того, разумеется, что С(1) = 0.

В верхушку 4 можно попасть или из верхушки 2, пройдя путь, равный 4, или из верхушки 5, пройдя Теория графов и оптимизация путь, равный 5. Потому справедливо соотношение

С(4) = min {С(2) + 4; С(5) + 5}.

Таким макаром, проведена реструктуризация (упрощение) задачки - нахождение С(4) сведено к нахождению С(2) и С(5).

В верхушку 5 можно попасть или из верхушки 3, пройдя путь, равный 2, или из верхушки 6, пройдя путь, равный 3. Потому справедливо соотношение

С(5) = min {С(3) + 2; С(6) + 3}.

Мы знаем, что С(3) = 1. Потому

С Теория графов и оптимизация(5) = min {3; С(6) + 3}.

Так как разумеется, что С(6) - положительное число, то из последнего соотношения вытекает, что С(5) = 3.

В верхушку 2 можно попасть или из верхушки 1, пройдя путь, равный 7, или из верхушки 3, пройдя путь, равный 5, или из верхушки 5, пройдя путь, равный 2. Потому справедливо соотношение

С(2) = min {С(1) + 7; С(3) + 5; С(5) + 2}.

Нам Теория графов и оптимизация понятно, что С(1) = 0, С(3) = 1, С(5) = 3. Потому

С(2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Сейчас мы можем отыскать С(4):

С(4) = min {С(2) + 4; С(5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким макаром, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в верхушку 4 нужно идти через верхушку 5. Ворачиваясь к вычислению С(5), лицезреем, что в верхушку 5 нужно идти через верхушку 3. А в верхушку 3 можно попасть Теория графов и оптимизация только из верхушки 1. Итак, кратчайший путь такой:

1 → 3 → 5 → 4 .

Задачка о кратчайшем пути для определенных начальных данных (рис.7 и табл.4) стопроцентно решена.

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

Задачка о наивысшем потоке Теория графов и оптимизация.Как (т.е. по каким маршрутам) отправить очень вероятное количество грузов из исходного пт в конечный пункт, если пропускная способность путей меж пт ограничена?

Для решения этой задачки каждой дуге нацеленного графа, соответственного транспортной системе, должно быть сопоставлено число - пропускная способность этой дуги. Разглядим пример (рис.8).


Рис.8. Начальные Теория графов и оптимизация данные к задачке о наивысшем потоке

Начальные данные о транспортной системе, к примеру, внутризаводской, приведенные на рис.8, можно также задать таблицей (табл.5).

Решение задачки о наивысшем потоке может быть получено из последующих суждений.

Разумеется, наибольшая пропускная способность транспортной системы не превосходит 6, так как менее 6 единиц грузов можно навести из исходного Теория графов и оптимизация пт 0, а конкретно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.

Таблица 5.

Начальные данные к задачке о наивысшем потоке

Пункт отправления Пункт предназначения Пропускная способность

Дальше нужно достигнуть, чтоб все 6 вышедших из пт 0 единиц груза достигнули конечного пт 4. Разумеется, 2 единицы груза, пришедшие в пункт 1, можно конкретно навести в пункт Теория графов и оптимизация 4. Пришедшие в пункт 2 грузы придется поделить: 2 единицы сходу навести в пункт 4, а 1 единицу - в промежный пункт 3 (из-за ограниченной пропускной возможности участка меж пт 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пт 0 и 1 единица из пт 2. Их направляем в пункт 4.

Итак, наибольшая пропускная способность рассматриваемой транспортной системы - 6 единиц Теория графов и оптимизация груза. При всем этом не употребляются внутренние участки (ветки) меж пт 1 и 2, также меж пт 1 и 3. Не догружена ветка меж пт 1 и 4 - по ней ориентированы 2 единицы груза при пропускной возможности в 3 единицы.

Решение можно представить в виде таблицы (табл.6).

Таблица 6.

Решение задачки о наивысшем потоке

Пункт отправления Пункт предназначения План перевозок Пропускная Теория графов и оптимизация способность

Задачка линейного программирования при максимизации потока.Дадим формулировку задачки о наивысшем потоке в определениях линейного программирования. Пусть ХKM - объем перевозок из пт К в пункт М. Согласно рис.8 К = 0,1,2,3, М = 1,2,3,4, при этом перевозки вероятны только в пункт с огромным номером. Означает, всего имеется 9 переменных ХKM Теория графов и оптимизация , а конкретно, Х01 , Х02 , Х03 , Х12 , Х13 , Х14 , Х23 , Х24 , Х34 . Задачка линейного программирования, нацеленная на максимизацию потока, имеет вид:

F → max ,

Х01 +Х02 +Х03 =F (0)

-Х01 +Х12 +Х13 +Х14 = 0 (1)

-Х02 -Х12 +Х23 +Х24 = 0 (2)

-Х03 -Х13 -Х23 +Х34 = 0 (3)

-Х14 -Х24 -Х34 = - F (4)

Х01 ≤ 2

Х02 ≤ 3

Х03 ≤ 1

Х12 ≤ 4

Х13 ≤ 1

Х14 ≤ 3

Х Теория графов и оптимизация23 ≤ 1

Х24 ≤ 2

Х34 ≤ 2

ХКМ ≥ 0 , К, М = 0, 1, 2, 3, 4

F ≥ 0 .

Тут F - мотивированная функция, условие (0) обрисовывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему сгустку, грузы не накапливаются снутри и системы и не "появляются" в ней. Условие (4) - это Теория графов и оптимизация условие "выхода" грузов из системы. Вкупе с условием (0) оно составляет балансовое соотношение для системы в целом ("вход" равен "выходу"). Последующие девять неравенств задают ограничения на пропускную способность отдельных "ветвей" транспортной системы. Потом в системе ограничений задачки линейного программирования указана неотрицательность объемов перевозок и мотивированной функции. Ясно, что последнее Теория графов и оптимизация неравенство вытекает из вида мотивированной функции (соотношения (0) либо (4)) и неотрицательности объемов перевозок. Но последнее неравенство несет некую общую информацию - через систему может быть пропущен или положительный объем грузов, или нулевой (к примеру, если снутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая Теория графов и оптимизация модель об этом "не знает").

О обилии оптимизационных задач.В разных дилеммах принятия решений появляются самые различные задачки оптимизации. Для их решения используются те либо другие способы, четкие либо приближенные. Задачки оптимизации нередко употребляются в теоретико-экономических исследовательских работах. Довольно вспомнить оптимизацию экономического роста страны при помощи матрицы Теория графов и оптимизация межотраслевого баланса Василия Леонтьева либо микроэкономические задачки определения рационального объема выпуска по функции издержек при фиксированной стоимости (либо в критериях монополии) либо минимизации издержек при данном объеме выпуска методом выбора рационального соотношения причин производства (с учетом платы за их).

Не считая затронутых выше способов решения задач оптимизации, напомним о том, что Теория графов и оптимизация гладкие функции улучшают, приравнивая 0 производную (для функций нескольких переменных - личные производные). При наличии ограничений употребляют множители Лагранжа. Эти способы обычно излагаются в курсах высшей арифметики и поэтому опущены тут.

Представляют энтузиазм задачки оптимизации с нечеткими переменными [5], также задачки оптимизации, возникающие в эконометрике [6]. Они рассматриваются в соответственной литературе.

Литература

1. Гасс Теория графов и оптимизация С. Путешествие в страну линейного программирования / Пер. с англ. - М.: Мир, 1973. - 176 с.

2. Кофман А., Фор Р. Займемся исследованием операций / Пер. с франц.. - М,: Мир, 1966. -280 с.

3. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: Высшая школа, 1976. - 392 с.

4. Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория Теория графов и оптимизация графов в управлении организационными системами. – М.: Синтег, 2001. – 124 с.

5. Орлов А.И. Задачки оптимизации и нечеткие переменные. – М.: Познание, 1980. – 64 с.

6. Орлов А.И. Эконометрика. – М.: Изд-во «Экзамен», 2002. – 576 с.


teoriya-frejmov-referat.html
teoriya-gedonizma-kak-chasti-etiki.html
teoriya-gigienicheskih-i-motiviruyushih-faktorov-fgercberga.html