- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
28. Задача о максимальном потоке
Наибольший интерес представляет постановка задачи, в которой критерием является поток сети:
Z max; (5.34)
kt, ks; (5.35) (5.36)
0xijdij. (5.37)
Задача (5.34) – (5.37) называется задачей о максимальном потоке. Она имеет большое практическое значение. Для нее разработаны алгоритмы, которые эффективнее методов решения транспортных задач. Они работают непосредственно с сетью как разновидностью графов.
В связи с этим напомним понятие разреза графа (сети), которое используется в основополагающей теореме Форда-Фалкерсона.
Пусть дан ориентированный граф G=(V,U), где V и U - множества вершин и дуг соответственно. Разрезом сети на подмножестве вершин AV, A, AV, tA, sV\A называется множество дуг ijU таких, что iA jV\A. Обозначим его P(A). Сумма пропускных способностей дуг разреза называется величиной (пропускной способностью) разреза:
Пример 5.5. Построим один из разрезов сети, приведенной на рис.5.7.
Е сли A={t,1,2,3}, то разрезом будет множество дуг P(A)={1,4; 1,6; 2,5; 3,6}, а его величина определяется как d(A)=d14+d16+d25+d36. Дуги, составляющие этот разрез, выделены жирными линиями.▲
Разрез сети, имеющий минимальную пропускную способность, называется минимальным разрезом.
Можно показать, что задачи максимизации потока и минимизации величины разреза являются двойственной парой. Из этого факта следует Теорема Форда и Фалкерсона:
Величина потока сети (от истока к стоку) не превосходит пропускной способности минимального разреза и существует максимальный поток, величина которого равна пропускной способности минимального разреза.
Методы решения задачи о максимальном потоке основаны на последовательном увеличении потока при соблюдении условий (5.35)-(5.37). При этом легко увидеть аналогию с перемещением по циклу в методах решения транспортных задач.
Аналогом цикла пересчета является увеличивающая цепь. Это цепь, соединяющая исток и сток, все дуги которой допустимые. Дуга является допустимой увеличивающей, если ее направление совпадает с направлением потока и поток на ней меньше пропускной способности, то есть xij<dij. Дуга считается допустимой уменьшающей, если направление дуги противоположно потоку и xij >0.
На увеличивающей дуге поток может возрасти на величину ij=dij-xij, а на уменьшающей дуге возможно снижение потока, равное ij=xij. Следовательно, максимальное допустимое изменение величины потока по увеличивающей цепи определяется как минимальное из возможных:
0= (5.38)
Таким образом, максимальный поток сети может быть определен по следующему алгоритму.
Задать начальную величину потока, обеспечиваемую потоками дуг при выполнении условий (5.35)-(5.37).
Примечание. Очевидно, что в качестве начального всегда можно взять нулевой поток.
Построить увеличивающую цепь. Если построить невозможно, то решение завершено.
По формуле (5.38) вычислить 0.
Переместить вдоль цепи 0, прибавляя к потокам на увеличивающих дугах и вычитая из потоков уменьшающих дуг. В результате поток сети увеличивается на 0. Перейти на шаг 2.
П ример 5.6. Определить максимальный поток сети на рис. 5.8. Пропускные способности дуг показаны у стрелок перед косой чертой.
Задаем начальный поток. Значения начальных потоков дуг даны за косой чертой, они удовлетворяют условиям задачи. Величина потока сети Z(0)=7.
Первая итерация.
Строим увеличивающую цепь. Она показана на рис. 5.8 утолщенными линиями. Определяем приращение потока: 0 = min(7-3, 5-1, 6-4)=2. Увеличиваем потоки дуг цепи на 2 (рис. 5.9). Z(1)= Z(0) + 0=7+2=9.В торая итерация.
С троим увеличивающую цепь {t,1; 1,4; 4,s} (рис. 5.9). 0 = min(7-5, 3-2, 5-1)=1.Увеличиваем потоки по дугам цепи на 0 (рис. 5.10). Z(2)= Z(1) + 0 = 9+1=10.
Третья итерация.
Новая цепь состоит из увеличивающих дуг t,3 и 4,s и уменьшающей дуги 4,3 (рис. 5.10). 0 = min(4-2, 1, 5-2)=1. Изменяем потоки: на дугах t,3 и 4,s увеличиваем, а на дуге 4,3 уменьшаем на величину 0. Тогда получаем Z(3)= Z(2) + 0 = 10+1=11 (рис. 5.11).
Т ак как увеличивающую цепь построить нельзя, последнее решение является оптимальным. Максимальный поток сети равен 11.Минимальный разрез рассмотренной сети соответствует множеству вершин А={t,1,2,3,5,6}, то есть P(A)={1,4; 5,s; 6,s}. Его пропускная способность d(A)=d14+d5s+d6s=3+2+6=11 равна величине максимального потока, что согласно теореме Форда-Фалкерсона также является признаком оптимальности найденного решения.