- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
5.2.3. Признак оптимальности
При перемещении по циклу пересчета увеличиваются на эту величину значения переменных Xij в четных вершинах, а следовательно, увеличиваются и затраты на перевозку на Cij. Одновременно уменьшаются на переменные в нечетных вершинах и на Cij соответствующие им затраты. Отсюда следует, что значение критерия в новом, (k+1)-м решении можно определить по критерию в исходном решении и изменениям в клетках цикла:
или
, (5.15)
где
(5.16)
Здесь, как и в симплекс-методе, Δij – относительная оценка переменной Xij, на которой построен цикл. Для базисных переменных оценка всегда равна нулю. Согласно (5.15) Δij показывает, как изменится критерий (в какую сторону и насколько) при перемещении по циклу единицы груза ( =1).
Если Δij>0, то введение Xij в число базисных приведет к уменьшению суммарных затрат. Если же Δij<0, критерий возрастет, что противоречит цели. Следовательно, решение нельзя улучшить, когда среди оценок нет положительных, и поэтому признак оптимальности имеет вид
Δij0. (5.17)
Если признак не выполняется, то новое решение целесообразно строить на основе клетки с максимальной оценкой (аналогично выбору в симплекс-методе при минимизации).
Вычисление оценок по формуле (5.16) требует построения цикла пересчета для каждой свободной клетки. Такой способ неэффективен для задач реальной размерности. Покажем, что возможен другой путь, исключающий построение циклов.
Поставим в соответствие каждому пункту отправления сбалансированной задачи некоторую величину Ui, i=1, 2,…, m, а каждому пункту назначения – Vj, j=1, 2,…, n так, чтобы для базисных клеток выполнялись равенства
Vj -Ui=Cij, i jбаз. (5.18)
Система (5.18) содержит m+ n-1 уравнений с m+ n неизвестными. Присвоив одной из неизвестных некоторое произвольное значение, например, нуль, легко найти значения остальных. В таких случаях говорят о получении решения системы с точностью до постоянной величины. Дальше мы увидим, что произвольный выбор неизвестной и ее значения не влияет на конечный результат.
З ная Ui и Vj, можно вычислить относительную оценку для любого цикла в текущем плане перевозок. Покажем это на произвольно взятом цикле (рис. 5.3).
В скобках указаны индексы клеток (переменных), в которых расположены вершины цикла. Вычисляем относительную оценку свободной клетки i0j0 ( небазисной переменной Xiojo) по формуле (5.16):
Δiоjо=Ciоj1 - Ci1j1+ Ci1j2 - Ci2j2+ Ci2jо - Ciоjо.
Заменим в этом выражении затраты в базисных клетках согласно (5.18). Тогда получим
Δiоjо =Vj1 -U iо -Vj1+Ui1+Vj2 -Ui1 -Vj2+Ui2+Vjо -Ui2 -Ciоjо =Vjo-Uio-Ciojo.
Выполненные сокращения не зависят от конфигурации цикла, так как все индексы кроме начальных входят в выражение два раза. Поэтому в итоге остаются только Vjo, Uio и Ciojo. Таким образом, для любой свододной клетки ij относительная оценка может быть вычислена без построения цикла пересчета по формуле
Δij=Vj-Ui-Cij. (5.19)
Из сравнения (5.18) и (5.19) видно, что для базисных клеток Δij=0.
Новые переменные Ui и Vj называются потенциалами пунктов отправления и назначения соответственно, отсюда происходит название метода. Из формулы (5.19) следует, что значение постоянной величины при нахождении потенциалов из системы (5.18) не влияет на оценки.
Потенциалы можно интерпретировать как локальные цены. Если цена в пункте отправления i равна Ui и груз из него доставляется в пункт назначения j по коммуникации ij, то локальная цена в ПН возрастет по отношению к ПО на величину транспортных затрат:
Vj=Ui+ Cij. (5.20)
Из этого соотношения также следует, что в оптимальном решении не может иметь место неравенство
Vj >Ui+ Cij,
так как оно означает, что локальная цена в пункте j выше, чем в случае прямой доставки из i в j.▲
Приведенный способ определения оценок через потенциалы пригоден для любого опорного плана перевозок. Однако учитывая структуру матрицы оценок (нули в базисных клетках), можно оценки нового плана получить минуя вычисления потенциалов простым преобразованием матрицы оценок предшествующего плана.
Рассмотрим конкретно преобразование матрицы (k) в матрицу (k+1) на основе нового решения X(k+1). Как отмечалось выше, новое решение получено вводом небазисной переменной с максимальной оценкой в (k). Пусть max ij=kr. В матрице (k) отмечаем элементы, соответствующие базисным в новом решении X(k+1) (на рис. 5.4 помечены символом *), максимальную оценку отмечаем особо. Далее строим цепочку выделения. Она строится с особо отмеченного элемента, который соединяют с отмеченными в этой строке. Затем отмеченные элементы, попавшие в цепочку, соединяют с отмеченными в их столбцах. Далее снова проводим соединение по строкам, и так до тех пор, пока не оборвутся все ветви.
Рис.5.4
Элементы, попавшие в цепочку выделения, выделяют строку и столбец за исключением особо отмеченного элемента, который выделяет только строку. К выделенным столбцам прибавляем, а из выделенной строки вычитаем . Нетрудно увидеть, что при этом переменной Xkr будет соответствовать нулевая оценка, как и тем перменным из решения X(k), которые сохранили статус базисных. Таким образом, преобразованная матрица соответствует новому опорному плану.
Провести выделение можно и иначе: сначала вычеркивать строку с максимальным элементом, затем вычеркивать столбцы, где есть элементы, отмеченные в этой строке, и т.д. Вычеркнутые строки и столбцы являются выделенными.