- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
18. Параметрический анализ. Параметрирование вектора ограничениий
Для практического внедрения результатов оптимизации полученное решение должно быть дополнено всесторонним анализом, который позволяет предсказать поведение оптимального решения при тех или иных возможных изменениях в модели.
Анализ чувствительности по переменным проводится по относительным оценкам. Оценка показывает скорость ухудшения значения критерия при отклонении значения переменной от оптимального. Очевидно, что точность реализации оптимальных значений должна быть тем выше, чем больше по абсолютной величине относительная оценка.
Влияние изменения отдельного ресурса в окрестности исходного значения устанавливается по двойственным переменным в оптимальном решении.
Вариантный анализ заключается в исследовании поведения оптимального решения при измнении состава модели (смена критерия, снятие или добаление одного ограничения и т.п.).
Параметрический анализ (параметрическое программирование) применяется для определения изменения оптимального решения в общем случае при одновременном и непрерывном изменении нескольких коэффициентов модели (в частном случае может изменяться только один). При этом характер изменения коэффициентов задается параметрически как функция одного параметра, а интересуемый диапазон изменения значительно шире окрестности исходных значений. В параметрическом программировании рассматривается параметрирование правой части, коэффициентов линейной формы, совместно коэффициентов критерия и правых частей, параметрирование отдельных столбцов или строк матрицы условий и другие более общие случаи совместного изменения коэффициентов.
Наибольший интерес представляют первые две задачи параметрирования, так как на практике нередки ситуации с изменением ресурсов (правых частей), цен или удельных затрат (кэффициентов критерия). Для них параметрическое решение можно найти в общем виде при линейной зависимости именений от параметра, а в отдельных случаях – и при нелинейной.
Параметрирование вектора ограничениий
Пусть оптимальное решение X* получено для вектора . Поставим вопрос: как будет изменяться оптимальное решение при изменении правой части, заданном параметрически B()?
Рассмотрим только случай линейной зависимости
B()=B+V, (4.41)
где 0 – параметр, определяющий величину изменения вектора ограничений;
V – вектор размерности m, определяющий направление и относительную скорость изменения компонентов вектора ограничений. Этот вектор задается ЛПР исходя из прогноза возможных изменений ресурсов.
Например, для трехмерного вектора B изменения могут быть заданы в виде
,
то есть ожидается одновременное уменьшение первого и третьего ресурсов и увеличение второго ресурса. При этом абсолютная величина изменения первого ресурса в три раза, а второго в полтора раза больше, чем третьего.
Для любого базисного решения условия задачи
AX=B
можно записать в виде
ABXB+AHXH=B,
где индексы “B” и “H” обозначают базисные и небазисные векторы (матрицы). Так как небазисные переменные равны нулю, то отсюда следует
ABXB=В
и, в частности, для оптимального решения
A*BX*B=В. (4.42)
Так как мы исходим из наличия решения X*, то базисная матрица - неособенная и существует обратная к ней матрица , умножая на которую слева равенство (4.42), получаем.
. (4.43)
Очевидно, что если заменить в (4.42) B на B() при =0, то ничего не изменится. При невырожденном оптимальном решении малое изменение B (>0 мало) не изменяет базис: оптимальная вершина хотя и смещается, но образуется теми же ограничениями. Поэтому в данном случае изменяется только оптимальное решение. Оптимальное решение при >0 обозначим X**. Тогда для малых равенство (4.42) запишется в виде
,
откуда находим изменяемое оптимальное решение
С учетом (4.43) окончательно имеем
(4.44)
где
(4.45)
Таким образом, при линейном характере изменений ресурсов оптимальные значения переменных также меняются линейно. Однако это справедливо до тех пор, пока не происходит смена базиса. В невырожденном решении всегда найдется >0, при котором базис не меняется. Из выражения (4.44) следует, что при неотрицательном векторе P возрастание не может привести к уменьшению какой-либо базисной переменной и, значит, к смене базиса. В этом случае формула (4.44) справедлива для любых >0. Такая ситуация показана на рис. 4.12, где изменение b1 и b2 в направлении стрелок не приводит к смене базиса (вершины, в которой достигается оптимальное решение).
Е сли же среди компонент вектора Р есть отрицательные, то соответствующие базисные переменные с увеличением будут уменьшаться. Если хотя бы одна из переменных обратится в нуль, то произойдет смена базиса и, следовательно, изменится обратная матрица. Формула (4.44) с исходными базисным решением и вектором P становится несправедливой. Этот случай иллюстрируется рис. 4.13., где оптимальная вершина сначала образована ограничениями по b1 и b2, а затем – ограничениями по b1 и b3.
Значение , при котором происходит смена базиса (базисного решения), называется критическим. Оно определяется по очевидной формуле
(4.46)
где pi – компоненты вектора Р.
Таким образом, исходное решение можно использовать для определения изменяемых решений по формуле (4.44) только в диапазоне
.
Отсюда получаем максимальное изменение правой части
Е сли диапазон изменения правой части недостаточен, то для его расширения необходимо заново решить задачу с вектором B1=B+ΔBmax. Тогда получим новое оптимальное решение, новую обратную матрицу и на их основе снова проводится параметрирование для B()=B1+1V. Повторяя эти действия, можно охватить весь желаемый диапазон изменения ресурсов. При этом соотношение компонент (но не знаков!) в векторе V может остаться исходным или измениться. В последнем случае зависимость от параметра на всем исследованном диапазоне будет кусочно-линейной.
Пример 4.7. Параметрируем задачу, решенную симплекс-методом в разд. 4.9.7 (пример 4.2) в предположении изменения 1-го и 4-го ресурсов.
Анализ поступления этих ресурсов показал, что первый может возрастать, а четвертый – уменьшаться, причем изменение четвертого может быть по абсолютной величине в два раза больше, чем первого. На этом основании записываем вектор изменений V=(1,0,0,-2).
Взяв обратную матрицу из оптимальной симплекс-таблицы (в столбцах начального базиса), по формуле (4.45) вычисляем вектор P:
Выписываем исходное оптимальное решение, соблюдая порядок базисных переменных в последней таблице:
Из данного порядка следует, что первый компонент вектора P соответствует 6-й переменной, а последний – первой. Таким образом, параметрическое решение запишется в виде
Так как вектор P имеет отрицательные компоненты, вычисляем критическое значение
Оно позволяет определить критические отклонения ресурсов от исходных значений:
Следовательно, полученное параметрическое решение будет спаведливо при одновременном изменении ресурсов в диапазонах
19 b1 < 20,6; 13,8 < b4 17.
Чтобы расширить эти диапазоны, в задаче нужно заменить вектор B=(19; 13; 12;17) вектором B1=(20,6;13;12;13,8) и снова решить ее. Новое решение параметрируется аналогичным образом.
Замечания. 1) Вместо принятого в примере вектора V можно брать kV, где k – любое положительное число. При этом будет изменяться в k раз только а диапазоны изменения bi останутся прежними. 2) Очевидно, что если изменяется правая часть только в одном условии и в векторе V соответствующий компонент взят равным единице, то коэффициент при в параметрической записи L** должен равняться двойственной переменной. При этом параметрический анализ позволяет определить диапазон изменения ресурса, в котором это значение двойственной переменной не меняется.