Орлов А.И. Менеджмент (2003) (1142166), страница 59
Текст из файла (страница 59)
(Поскольку любой путь, который надо рассмотреть, состоит из дуг,а дуг конечное число, и каждая входит не более одного раза, то претендентов накратчайший путь конечное число, и минимум из конечного числа элементоввсегда достигается.) Рассматриваемая задача состоит в вычислении С(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).4122231134Рис.8. Исходные данные к задаче о максимальном потокеИсходные данные о транспортной системе, например, внутризаводской,приведенные на рис.8, можно также задать таблицей (табл.5).Пункт отправления000111223Таблица 5.Исходные данные к задаче о максимальном потокеПункт назначенияПропускная способность122331243143314242Решение задачи о максимальном потоке может быть получено изследующих соображений.Очевидно, максимальная пропускная способность транспортной системыне превышает 6, поскольку не более 6 единиц грузов можно направить изначального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1единицу в пункт 3.Далее надо добиться, чтобы все 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).000111ПунктотправленияТаблица 6.Решение задачи о максимальном потокеПункт назначенияПлан перевозокПропускнаяспособность122233311204301423223344122122Задача линейного программирования при максимизации потока.Дадим формулировку задачи о максимальном потоке в терминах линейногопрограммирования. Пусть Х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]. Например, методнаименьших квадратов, разобранный в следующей главе, основан на решениизадачи оптимизации. Итоговое мнение комиссии экспертов часто вычисляют какрешение задачи оптимизации (глава 3.4). Конкретные виды задач оптимизации иметоды их решения рассматриваются в соответствующей литературе.Литература1. Гасс С. Путешествие в страну линейного программирования / Пер.
с англ. - М.:Мир, 1973. - 176 с.2. Кофман А., Фор Р. Займемся исследованием операций / Пер. с франц.. - М,:Мир, 1966. -280 с.3. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: Высшая школа,1976. - 392 с.4. Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управленииорганизационными системами. – М.: Синтег, 2001. – 124 с.5. Орлов А.И. Задачи оптимизации и нечеткие переменные. – М.: Знание, 1980. –64 с.6.
Орлов А.И. Эконометрика. – М.: Изд-во «Экзамен», 2002. – 576 с.Задачи по методам принятия решений1. Изобразите на плоскости ограничения задачи линейного программирования ирешите (графически) эту задачу:400 W1 + 450 W2 → min ,5 W1 + 10 W2 ≥ 45,20 W1 + 15 W2 ≥ 80,W1 ≥ 0,W2 ≥ 0.2. Решите задачу линейного программирования:W1 + 5 W2 → max ,0,1 W1 + W2 ≤ 3,8 ,0,25 W1 + 0,25 W2 ≤ 4,2 ,W1 ≥ 0 ,W2 ≥ 0 .3. Решите задачу целочисленного программирования:10 Х + 5 У → max .8 Х + 3 У ≤ 40,3 Х + 10 У ≤ 30,Х ≥ 0 , У ≥ 0 , Х и У - целые числа.4.
Решите задачу о ранце:Х1 + Х2 + 2 Х3 + 2Х4 + Х5 + Х6 → max ,0,5 Х1 + Х2 + 1,5 Х3 + 2Х4 + 2,5Х5 + 3Х6 ≤ 3.Управляющие параметры Хk, k = 1,2,…, 6 , принимают значения из множества,содержащего два элемента - 0 и 1.5. Решите задачу коммивояжера для четырех городов (маршрут должен бытьзамкнутым и не содержать повторных посещений). Затраты на проезд приведены втабл.7.Таблица 7.Исходные данные к задаче коммивояжераГород назначенияЗатраты на проездБ2В1Д5А3В2Д1А4Б1Д2А5Б3В3Город отправленияАААБББВВВДДД6.
Транспортная сеть (с указанием расстояний) приведена на рис.9.кратчайший путь из пункта 1 в пункт 4.2Найдите65143284Рис.9. Исходные данные к задаче о кратчайшем пути.37. Как послать максимальное количествогрузов из начального пункта 1 вконечный пункт 8, если пропускная способность путей между пунктамитранспортной сети (рис.10) ограничена (табл.8)?231568Рис.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
