- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Правило минимального элемента.
В приведенном способе построения плана не участвовали затраты на перевозку. Следует ожидать, что учет затрат позволит получить начальный план, более близкий к оптимальному. Этим и отличается расматриваемое правило.
Первой заполняется клетка с минимальными затратами. Пусть minCij=Ckp. Тогда Xkp=min(ak, bp). Если при этом закрывается строка k, то в столбце p ищем клетку с минимальными затратами и определяем значение соответствующей переменной согласно (5.13). При закрытии столбца p действуем аналогично в строке k. В общем случае клетка, лежащая в закрытом столбце и/или закрытой строке является закрытой, иначе – открытой. На каждом шаге движение идет либо по столбцу, либо по строке и при этом отыскивается среди открытых клетка с минимальным значением Cij.
Пример 5.2. Построим начальный план по правилу минимального элемента для задачи из примера 1. Результат представлен в табл. 5.3.
Таблица 5.3
Поставщик |
Потребитель |
Запасы груза |
|||
B1 |
B2 |
B3 |
B4 |
||
A1 |
6
|
7 5 |
3 60 |
5 35 |
100 |
A2 |
1 75 |
2 75 |
5
|
6
|
150 |
A3 |
3 |
10 |
20 |
1 50 |
50 |
Потребность в грузе |
75 |
80 |
60 |
85 |
300 |
При таком начальном плане L=665, что меньше чем в примере 1. Однако нельзя утверждать, что для любых данных этот способ дает лучший план. Правильнеее говорить, что правило минимального элемента эффективнее в среднем (на множестве задач). В то же время алгоритм реализации этого правила сложнее, чем правила северо-западного угла.
Применяется также вариант, в котором на каждом шаге ищется клетка с минимальными затратами среди всех открытых клеток. Такой способ еще сложнее, но в среднем дает планы, более близкие к оптимальным.
22.Обоснование метода потенциалов
Как и в симплекс-методе, новый план можно получить из исходного заменой одной базисной переменной. Клетки с базисными переменными будем называть базисными или занятыми, остальные – небазисными или свободными. Для перехода к новому плану используется замкнутая цепь, которая строится в матрице перевозок по следующим правилам.
Построение начинается со свободной клетки, которую соединяют с базисной в строке (столбце). Последнюю соединяют с базисной в столбце (строке). Далее, чередуя движение по строкам и столбцам, продолжаем соединение занятых клеток так, чтобы вернуться в начальную. При этом не требуется, чтобы цепь включала все базисные клетки. Угловые клетки цепи назовем вершинами цепи. Тогда правило построения замкнутой цепи можно сформулировать проще: начальная вершина должна быть в свободной клетке, остальные – в занятых.
Т акая цепь называется циклом пересчета. Он является геометрическим представлением разложения небазисного вектора условий при переменной в свободной клетке по векторам текущего базиса. Если базисная клетка не попала в цикл пересчета, то соответствующий базисный вектор имеет в этом разложении нулевой коэффициент. Так как любой небазисный вектор выражается через базис единственным образом, то для любой небазисной (свободной) клетки можно построить один и только один цикл пересчета. Примеры конфигурации циклов показаны на рис. 5.2.
Кружком выделена начальная (небазисная) клетка цикла. Нумеровать вершины можно в любом направлении. И начинать можно с любой вершины. На рисунке нумерация проведена с клетки, смежной начальной. В этом случае начальная клетка всегда будет четной.
Теперь становится очевидным, что в каждой строке и каждом столбце, по которым проходит цикл пересчета, будет две и только две вершины: одна четная и одна нечетная. Если бы оказалось вершин больше двух, то из базисных клеток образовался бы цикл, что невозможно. В этом легко убедиться на примере: допустим, в правом цикле на рис. 5.2 отрезки 1-8 и 5-4 лежат в одной строке, тогда вершины 1, 4, 3 и 2 образуют цикл.
В результате цикл пересчета, построенный в допустимой матрице перевозок, обладает замечательным свойством: если перемещать по нему некоторое количество груза >0, прибавляя его к Xij в четных вершинах и вычитая из Xij в нечетных, то условия задачи (5.3) и (5.4) не нарушатся. Чтобы новое решение было допустимым, то есть выполнялось и условие неотрицательности переменных, необходимо ограничить значение :
0=min Xij, ij нечет. (5.14)
Здесь нечет – множество индексов переменных в нечетных вершинах цикла.
Для получения базисного решения (нового опорного плана) достаточно взять =0. При этом переменная свободной клетки, на которой строился цикл, становится базисной со значением 0, а переменная, доставляющая минимум в (5.14), обнуляется и переходит в небазисные.
Таким образом, переход от одного плана к другому в методе потенциалов заключается в построении цикла пересчета, определении 0 с последующим прибавлением к значениям переменных в четных вершинах и вычитанием в нечетных. Очевидно, что это значительно проще, чем в аналогичной процедуре симплекс-метода.