- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
24. Двойственная пара транспортных задач
Построим двойственную задачу простейшей транспортной задачи (Т-задачи). Предварительно изменим знаки в выражении критерия и в условиях по пунктам назначения. Тогда модель прямой задачи примет вид:
Здесь слева от равенств записаны сопоставленные им двойственные переменные. Модель двойственной задачи запишем по правилам, приведенным в разд. 4.11.3:
;
Если Cij перенести в левую часть, то согласно (5.19) условия двойственной задачи приобретают смысл признака оптимальности Δij0.
Итак, если выполняются условия прямой и двойственной задач, решение оптимально. Теперь понятно, что потенциалы представляют собой переменные двойственной задачи.
Из теорем двойственности известно, что в оптимальном решении критерии прямой и двойственной задач равны. Для рассматриваемой двойственной пары это означает, что
(5.21)
Отсюда находим:
Учитывая линейность (5.21), полный дифференциал запишем в виде
Изменения ai и bj могут быть только равными, иначе нарушится сбалансированность задачи. Если положить ai= bj =1, то получим
Следовательно, разность потенциалов показывает, как изменится оптимальное значение критерия при одновременном изменении соответствующих потребностей и возможностей на единицу.
25. Метод потенциалов для Td-задачи
Транспортная задача с ограниченными пропускными способностями (5.7)-(5.10) отличается от T-задачи наличием ограничений сверху на перевозки:
0 xij dij.
Они существенно усложняют решение задачи. В плане перевозок не все положительные переменные являются базисными. В невырожденном решении базисные переменные могут принимать только значения больше нуля и меньше пропускной способности:
0 < xij <dij. (5.24)
В вырожденном решении некоторые базисные переменные равны граничным значениям (0 или dij).
Если задача не сбалансирована, то, как и в Т-задаче, добавляют столбец или строку с нулевыми затратами, но с бесконечной пропускной способностью.
Правило северо-западного угла непригодно для построения начального решения. Его строят по одному из вариантов правила минимального элемента. При этом принцип определения значений переменных сохраняется: на каждом шаге присваивается максимальное допустимое значение согласно формуле
Xij=min(остаток от ai, остаток до bj, dij).
Если минимум достигается на dij, то не закрывается ни строка, ни столбец, и следует продолжать движение по строке или столбцу (если двигались по столбцу). Однако может оказаться, что в строке (столбце) больше нет открытых клеток, а она не закрыта. Это значит, что начальный план получается недопустимым. Если часть строк (столбцов) не закрыта, то обязательно не закроются и некоторые столбцы (строки). Так как задача сбалансированная, то суммарная величина незакрытия строк будет равна суммарному незакрытию столбцов . Обозначим эту величину . Чтобы в этом случае завершить построение начального плана, добавляют фиктивного потребителя (столбец) и фиктивного поставщика (строку) с одинаковой потребностью и возможностью . Так как их клетки соответствуют искусственным переменным, которые в разрешимой задаче должны стать равными нулю, затраты в них полагают бесконечно большими (М), а в клетке на пересечении фиктивного столбца с фиктивной строкой – равными нулю. Пропускные способности в фиктивных клетках не лимитируются. В процессе работы алгоритма план станет допустимым, когда все искусственные переменные обнулятся, то есть в юго-восточной клетке перевозка станет равна (фиктивный поставщик замкнется на фиктивного потребителя).
После построения начального плана определяются базисные клетки по условию (5.24). Если таких клеток окажется меньше m+n-1(вырожденный план), то в число базисных включают переменные (клетки), равные нулю или dij. При этом на базисных клетках не должен строиться замкнутый цикл, иначе клетки добавлены неверно.
Пример 5.4. Исходные данные задачи приведены в табл. 5.6. В клетках слева даны пропускные способности (красным цветом), справа – затраты на перевозки (синим цветом). Задача сбалансированная. Начальный план строим по правилу минимального элемента, порядок построения показан стрелками (табл. 5.7). Строка 4 и столбцы 2 и 3 не закрылись: =3.
Таблица 5.6 Таблица 5.7
bj ai |
15 |
33 |
25 |
|
bj ai |
15 |
33 |
25 |
12 |
8 3 |
5 1 |
10 5 |
|
12 |
8 3 |
5 1 5 |
10 5 7 |
6 |
5 2 |
9 4 |
4 7 |
|
6 |
5 2 |
9 4 6 |
4 7 |
20 |
12 6 |
11 2 |
10 3 |
|
20 |
12 6 |
11 2 11 |
10 3 9 |
35 |
20 4 |
10 5 |
7 9 |
|
35 |
20 4 15 |
10 5 10 |
7 9 7 |
Поэтому добавляем фиктивные строку и столбец, и в клетки незакрытых столбцов и строки записываем недостающие перевозки. В результате выполняется баланс по всем строкам и столбцам. Построенный искусственный (недопустимый) начальный план приведен в табл. 5.8
Так как общее число пунктов равно 9, то базисных переменных должно быть 8. Из сравнения значений xij и dij находим только 7 базисных переменных (базисные клетки закрашены), то есть план вырожденный. В качестве недостающей базисной клетки возьмем клетку 4,2 (закрашена более темным цветом), в которой значение переменной находится на верхней границе.
Нетрудно убедиться, что ни из каких базисных клеток нельзя построить замкнутый цикл. (Чтобы соблюдалось это требование в случае вырожденности плана, можно рекомендовать рассматривать в качестве кандидатов на включение в число базисных в первую очередь те клетки, в которых происходит поворот на 90 градусов при построении плана. Так, в данном примере такими являются клетки 4,2 и 4,3.) ▲
Таблица 5.8
bj ai |
15 |
33 |
25 |
=3 |
12 |
8 3 |
5 1 5 |
10 5 7 |
М |
6 |
5 2 |
9 4 6 |
4 7 |
М |
20 |
12 6 |
11 2 11 |
10 3 9 |
М |
35 |
20 4 15 |
10 5 10 |
7 9 7 |
М 3 |
=3 |
М |
М 1 |
М 2 |
0 |
Т еперь рассмотрим изменения на основном этапе алгоритма. Признак оптимальности в Td-задаче расширяется. Согласно (5.15) при введении в решение небазисной переменной xij=0, то есть ее увеличении, критерий уменьшается при ij>0 и увеличивается при ij<0. Если же вводить переменную xij=dij, а это означает ее уменьшение, то критерий уменьшится при ij<0 и возрастет при ij>0. Этот характер изменения критерия показан на рис. 5.5. Поэтому решение не может быть улучшено, если выполняются условия, составляющие признак оптимальности задачи с ограниченными пропускными способностями:
(5.25)
Если условия не выполняются хотя бы для одной небазисной клетки, решение может быть улучшено. В связи с этим введем два множества:
- множество индексов переменных на нижней границе
;
- множество индексов переменных на верхней границе
.
Очевидно, что объединенное множество G= является множеством индексов перспективных переменных (клеток): введение любой из них приведет к улучшению критерия. В Т-задаче имеется только множество , и выбор производится из него. Здесь же выбор переменной, вводимой в базис, осуществляется на множестве G:
(5.26)
Так как переменная вводится по-разному, увеличивается с нижней границы и уменьшается с верхней, вычисление 0 и перемещение по циклу выполняется иначе, чем в Т-задаче. При определении 0 теперь необходимо учитывать обе границы: при вычитании нельзя вычесть больше, чем имеется, а при добавлении недопустимо превысить пропускную способность.
Из (5.26) следует, что возможны 2 варианта при выборе вводимой переменной и соответственно 2 варианта перехода к новому плану:
1. Если , то цикл строится на клетке, в которой перевозка равна нулю. Новый план получается прибавлением 0 в четных вершинах цикла и вычитанием в нечетных. Поэтому
. (5.27)
2. Если , цикл строится на клетке, в которой перевозка равна dij. В этом случае вводимая переменная должна уменьшаться. Поэтому перемещение по циклу состоит в вычитании 0 в четных вершинах и прибавлении в нечетных. Отсюда следует, что
. (5.28)
В обоих вариантах значение критерия улучшается на величину 0|kr|.
Таким образом, алгоритм решения сбалансированной Тd-задачи включает следующие шаги:
Построение начального плана перевозок. План может получиться как допустимый, так и искусственный (недопустимый).
Выделение базисных клеток. Если их меньше m+n-1, то добавляются клетки на границе.
Нахождение потенциалов из системы (5.18).
Вычисление оценок по формуле (5.19)
Начало цикла. Определение множества G по матрицам плана и оценок.
Проверка признака оптимальности: если G= (эквивалент (5.25)), переход на шаг 10.
Определение вводимой переменной (клетки kr) по (5.26) и построение цикла пересчета.
Построение нового плана: вычисление 0 в зависимости от принадлежности kr по (5.27) или (5.28) и соответствующее перемещение по циклу.
Получение матрицы оценок нового плана с помощью преобразования матрицы оценок старого плана (как в Т-задаче). Переход на шаг 5.
Конец. Полученный план является оптимальным, если не содержит запрещенных перевозок (с затратами М).
Когда решение начинается с искусственного плана, то после достижения допустимого решения можно сократить матрицы перевозок и оценок за счет отбрасывания фиктивных столбца и строки. Если в них было ровно две базисные клетки, то пересчитывать матрицу оценок не надо. Иначе она рассчитывается через потенциалы для сокращенного плана. Однако сокращение матриц не является обязательным.