- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
23. Алгоритм метода потенциалов.
Алгоритм включает предварительный и основной этапы.
Предварительный этап:
В матрице перевозок построить начальный план X(0).
Решением системы (5.18) определить потенциалы всех пунктов в начальном плане.
Вычислить оценки небазисных переменных (свободных клеток) по формуле (5.19) и записать матрицу (0).
Основной этап (получены X(k) и (k)):
Проверить оценки в (k). Если нет положительных, то перейти на п. 9.
Определить максимальную оценку kr = max ij.
В матрице X(k) построить цикл пересчета на клетке kr.
В построенном цикле вычислить 0=min Xij, ij нечет.
Прибавить 0 в четных вершинах цикла и вычесть в нечетных, результат – матрица перевозок X(k+1).
В матрице (k)) провести выделение строк и столбцов по решению X(k+1).
К выделенным столбцам прибавить , а из выделенных строк вычесть kr, результат – матрица (k+1).
Перейти на п.1 основного этапа.
Конец.
Примечание. Если имелись запрещенные перевозки (некоторые Cij=M), то соответствующие переменные в последнем решении должны равняться нулю. В противном случае задача неразрешима.
Пример 5.3. Решить методом потенциалов транспортную задачу, представленную в табл. 5.4.
Таблица 5.4
Поставщик (ПО) |
Потребитель (ПН) |
Количество груза |
|||
B1 |
B2 |
B3 |
B4 |
||
A1 |
3 |
8 |
2 |
1 |
10 |
A2 |
1 |
4 |
3 |
5 |
30 |
A3 |
7 |
2 |
1 |
6 |
40 |
Потребность в грузе |
20 |
5 |
30 |
25 |
=80 |
Решение. Задача сбалансированная. Начальный опорный план перевозок строим по правилу северо-западного угла. Полученный план невырожденный (табл. 5.5). Число базисных переменных (занятых клеток) r=m+n-1=3+4-1=6, они выделены цветом.
Таблица 5.5
Поставщик (ПО) |
Потребитель (ПН) |
Количество груза |
|||
B1 |
B2 |
B3 |
B4 |
||
A1 |
3 10 -
|
8
|
2 |
1 + |
10 |
A2 |
1 10 + |
4 5 |
3 15 - |
5
|
30 |
A3 |
7 |
2
|
1 15 + |
6 25 -
|
40 |
Потребность в грузе |
20 |
5 |
30 |
25 |
=80 |
Значение критерия в начальном плане
Вводим потенциалы для ПО и для ПН так, чтобы для базисных клеток выполнялись равенства:
Полагая последовательно находим остальные потенциалы:
Вычисляем для свободных клеток:
Записываем матрицу оценок для начального плана перевозок:
В начальном плане строим цикл на клетке с максимальной оценкой. Это клетка (1,4). Находим значение вводимой переменной:
=min(10,15,25)=10.
Переместив 0 по циклу, получаем новый план перевозок
для которого первая итерация улучшила критерий на 90 единиц.
Для выяснения статуса нового решения находим матрицу оценок. С этой целью в (0) отмечаем элементы, соответствующие базисным в X(1), и строим цепочку выделения. Так как в строке с максимальной оценкой других отмеченных элементов нет, выделенной оказывается только первая строка. Вычитая из нее kr, получаем матрицу
.
Как следует из анализа матрицы (1), решение X(1) не является оптимальным. Следующее решение получаем с помощью построенного в X(1) цикла, перемещая по нему :
Мы получили новый план перевозок с критерием
.
Матрицу оценок этого плана находим преобразованием матрицы (1) аналогично описанному выше. В результате имеем
В матрице есть положительный элемент, поэтому на клетке (3,2) строим цикл пересчета. Определяем и, перемещая 5 по циклу, находим очередной план перевозок
которому соответствует значение критерия . Преобразуя матрицу (II), получаем
.
Эта матрица не содержит положительных оценок, следовательно, план является оптимальным. Согласно этому плану от 1-го поставщика надо поставить 10 ед. продукции 4-му потребителю, от 2-го поставщика - 20 ед. первому и 10 ед. четвертому потребителям, от 3-го поставщика - 5, 30 и 5 ед. соответственно 2, 3 и 4 потребителям. Такая схема перевозок обеспечивает минимум суммарных затрат, которые равны 150.▲
Примечания. 1).Метод потенциалов применим и для решения трипланарных задач. Отличие лишь в том, что циклы пересчета и цепочки выделения строятся не на плоскости, а в трехмерном пространстве. 2).Если на каждой итерации оценки вычислять непосредственно по построенным циклам (на всех свободных клетках), то получим распределительный метод. Поэтому метод потенциалов называют также модифицированным распределительным методом. Однако метод потенциалов значительно эффективнее распределительного на задачах средней и большой размерности.