- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
29. Метод декомпозиции Данцига - Вулфа
При решении задач большой размерности значительная часть времени тратится на обращения к внешней памяти и это является главным препятствием на пути увеличения размерности задач. Уменьшить число обращений к внешней памяти можно, если удается большую задачу заменить рядом задач существенно меньшей размерности. Приемы и методы, позволяющие выполнять такие преобразования, составляют предмет блочного программирования.
Одним из эффективных методов блочного программирования применительно к линейным задачам является метод декомпозиции Данцига – Вулфа. По данным авторов метод позволяет решать задачи с размерностью n106, m105.
Сначала рассмотрим математические преобразования, приводящие к разбиению исходной задачи, а затем покажем, в каких случаях это дает эффект по сравнению с непосредственным решением большой задачи.
Пусть имеется следующая модель задачи:
L=CTXmax; (6.1)
AX=B; (6.2)
X0, (6.3)
где вектор X имеет размерность n, а вектор B – m.
Условия (6.2), (6.3) определяют допустимое множество задачи D. Представим матрицу А и вектор В в виде двух подматриц:
Тогда условия задачи (6.2)-(6.3) записываются следующим образом:
А(0)Х=В(0); (6.4)
А(1)Х=В(1); (6.5)
Х0 (6.6)
Условия (6.4), включающие m0 равенств, порождают допустимое множество D0, а система (6.5) содержит m1 равенств и вместе с (6.6) задает множество D1. Очевидно, что m=m0+m1, D= D0 D1. При этом выделение подматриц выполняется так, что m1>>m0.
Далее будем полагать, что множество D1 ограниченное и, значит, является выпуклым многогранником. В противном случае его легко сделать ограниченным добавлением ограничений сверху на переменные так, что они не повлияют на исходное множество D.
Предположим, что нам известны вершины множества D1. Обозначим их координаты через Х1, Х2,…, ХN, где N – число вершин. Поскольку D1 – выпуклый многогранник, то любую его точку можно представить в виде линейной комбинации вершин:
Х= zX; (6.7)
z=1; (6.8)
z0, v. (6.9)
Так как все решения Х, определяемые по (6.7)-(6.9), принадлежат D1, то описание (6.7)-(6.9) эквивалентно (6.5), (6.6).
Подставим Х в виде (6.7) в (6.1) и (6.4):
L = CT zX;
A(0)Xz=B(0).
Считая X известными, введем обозначения:
СТХ=; (6.10)
А(0)Х=Р. (6.11)
Тогда преобразованная модель задачи запишется в виде
L= zmax;
Pz=B(0);
z=1;
z0.
В этой модели неизвестными являются z, число которых равно числу вершин многогранника D1. Последнее равенство модели можно объединить со всеми остальными, используя обозначения расширенных векторов
. (6.12)
Тогда окончательно получим:
L= zmax; (6.13)
z = ; (6.14)
z0. (6.15)
Задача в виде (6.13) – (6.15) называется координирующей или основной задачей. Главное отличие этой задачи от исходной в несравнимо меньшем числе условий (m0+1<<m).
Если мы сможем ее решить, то есть найти Z*, то получим решение и исходной задачи, воспользовавшись (6.7):
Х*= z*X. (6.16)
Для решения основной задачи применим модифицированный симплекс-метод. Начальное решение можно построить, не зная ни одной вершины, с помощью искусственных переменных zN+i.
Согласно модифицированному методу после получения очередного базисного решения вычисляются относительные оценки. В разд. 4.10 получены формулы:
Перепишем их в обозначениях координирующей задачи:
(6.17)
или окончательно
(6.18)
Мы не можем вычислить все оценки, так как нам не известно даже их число. Но этого и не требуется, достаточно только определить: есть или нет среди них отрицательные. Для ответа на этот вопрос будем искать наименьшую оценку. Если она отрицательная, текущее решение координирующей задачи может быть улучшено введением переменной с этой оценкой. В противном случае констатируется выполнение признака оптимальности.
Итак, задача состоит в следующем:
min.
Отбросив в (6.18) константу, запишем ее в виде
(TA(0)-CT)X (6.19)
Решение задачи (6.19) проблематично, так как минимум ищется на дискретном множестве вершин многогранника D1. Учитывая, что минимизируемая функция линейная, будем искать решение не на вершинах, а на всем многограннике. Известно, что если решение существует, то оно будет достигаться в вершине. Поэтому решение на всем (непрерывном) множестве D1 совпадет с решением задачи (6.19).
Таким образом, задачу (6.19) заменяем эквивалентной:
Lвсп= (TA(0)-CT)X (6.20)
A(1)X = B(1); (6.21)
X 0. (6.22)
Эта задача называется вспомогательной. Если она неразрешима, то и исходная задача не имеет решения. Пусть оптимальное решение вспомогательной задачи (6.20)-(6.22) достигается в вершине r. Это означает, что нам становятся известны координаты вершины Xr и оптимальное значение критерия . Тогда согласно формуле (6.18) вычисляем минимальную оценку
(6.23)
Очевидно, что если r0, то и все оценки неотрицательны, и решение координирующей задачи завершено. При отрицательной r решение продолжается. В базис основной задачи вводится вектор , определяемый по формуле
(6.30)
Направляющий столбец находится разложением этого вектора по текущему базису:
. (6.31)
После определения направляющего элемента и симплекс-преобразования получаем новое решение основной задачи. Коэффициент критерия (6.13) при переменной, введенной в базисное решение, вычисляется согласно (6.10):
r =CTXr. (6.32)
Теперь по формуле (6.17) находим новый вектор , снова решаем вспомогательную задачу и по полученной минимальной оценке делаем вывод о дальнейших действиях.
Таким образом, решение исходной задачи заменяется многократным решением основной и вспомогательной задач. При этом порядок размерности вспомогательной задачи такой же, как у исходной. Поэтому естественнен вопрос: в каких случаях такой метод эффективен?
Ответ очевиден: в тех случаях, когда сложность решения вспомогательной задачи намного ниже, чем исходной. Такие случаи имеют место, когда матрица условий задачи (после упорядочения строк и столбцов) оказывается почти-блочно-диагональной, как показано на рис. 6.1. Примером может служить задача планирования производства продукции в крупной фирме или холдинге, когда у каждого предприятия своя номенклатура продукции, а некоторые ресурсы являются общими. Подматрица А(0), входящая в параметры координирующей задачи, соответствует ограничениям по общим ресурсам. Такие условия называют связующими. Их относят к основной задаче.
О стальные условия образуют вспомогательную задачу. При этом подматрица А(1) имеет блочно-диагональную структуру, что позволяет разбить вспомогательную задачу на p независимых задач:
После решения этих задач определяется критерий вспомогательной задачи по очевидной формуле
Таким образом, решение вспомогательной задачи существенно упрощается, если структура матрица условий может быть приведена к блочно-диагональной.
В следующем разделе декомпозиция вспомогательной задачи будет показана на примере решения транспортной задачи.
Применение рассмотренного метода может быть целесообразно и тогда, когда вспомогательная задача имеет особенности, позволяющие решать ее специальными методами.