- •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.5. Решение задачи по критерию времени
Как было показано в разд. 5.1.5, такая задача исходно является нелинейной, но может быть легко преобразована к линейной. Однако получаемая линейная модель громоздка и для нахождения решения требует применения универсальных методов линейного программирования.
Поэтому может оказаться целесообразным обратиться к приближенным, но более простым методам решения. Один из них рассмотрен ниже. Он использует идеи методов решения обычных транспортных задач и заключается в следующем.
Любым из способов строится начальный план перевозок. Затем определяется текущее значение критерия Т(0) как максимальное время в занятых клетках (xij>0). Далее рассмотрим действия в цикле.
Пусть на k-й итерации получен план со значением критерия Т(k). Оно может быть уменьшено, если освободить клетку с tij= Т(k). С этой целью на клетке строится разгрузочный цикл так, чтобы в нечетных вершинах выполнялось неравенство tij<Т(k), а в четных – xij>0 (исходная вершина – четная). Очевидно, что такие правила позволяют в общем случае строить более одного цикла на выбранной клетки. В цикле вычисляется 0 как минимальная перевозка в четных вершинах. Вычитая 0 в четных вершинах и прибавляя в нечетных, получаем новый план. Если клетка с максимальным временем была единственной и перевозка в ней стала равна нулю, новый план улучшил значение критерия. Если клетка не обнулилась, то на ней строится другой разгрузочный цикл. В случае нескольких клеток со временем Т(k) для улучшения критерия необходимо разгрузить все. Решение завершается, когда нельзя разгрузить клетку (клетки), определяющую значение критерия.
Естественно, что рассмотренный метод не гарантирует получение оптимального решения.
26. Приведение открытой транспортной задачи к закрытой
В открытой или несбалансированной задаче имеет место неравенство
.
Прежде чем решать такую задачу, необходимо привести ее к сбалансированному виду. В зависимости от ситуации сбалансировать задачу можно формальным способом без обращения к ЛПР или с привлечением дополнительной информации от ЛПР.
Рассмотрим формальные приемы. Пусть в исходной задаче предложение превышает спрос:
Тогда условия задачи имеют вид
(5.22)
(5.23)
В каждое неравенство (5.22) введем дополнительную переменную xi,n+1. В сумме эти переменные должны равняться величине дебаланса:
Добавляя это равенство к условиям (5.23), получаем закрытую задачу:
Потребность bn+1 называют фиктивной. Таким образом, чтобы сбалансировать задачу, достаточно ввести фиктивного потребителя с потребностью, равной дебалансу. Практически это означает, что к исходной таблице добавляется один столбец с потребностью bn+1 и затратами Ci,n+1=0. Ненулевые дополнительные переменные в оптимальном решении будут показывать количество груза, остающееся в соответствующих ПО.
Второй случай несбалансированности задачи имеет место, когда спрос превышает предложение:
.
При этом исходные условия записываются в виде:
Поступаем аналогично первому случаю. Введем в каждое неравенство дополнительную переменную xm+1,j. Очевидно, что сумма этих переменных равна величине дебаланса:
С учетом этого равенства сбалансированная модель принимает вид:
Такое преобразование соответствует введению фиктивного поставщика (дополнительной строки) с возможностью am+1 и нулевыми затратами Cm+1,j. Дополнительная переменная xm+1,j имеет смысл количества груза, недопоставленного j-му ПН.
Рассмотренный формальный способ будет неприемлем, если потребители по-разному реагируют на недопоставки. Тогда возможны два варианта решения задачи:
ЛПР корректирует потребности, обеспечивая баланс.
Выявляется и учитывается влияние недопоставок для каждого потребителя. Если зависимость потерь от величины недопоставки линейная, то задача остается в классе линейных. В этом случае задача балансируется как при формальном подходе, но в дополнительной строке в качестве затрат берутся удельные потери от недопоставки.
Если ожидается, что спрос будет длительное время превышать существующие возможности на величину am+1, то встает вопрос о расширении производства. Он может решаться в рамках транспортной модели следующим образом. Проектируются варианты увеличения производства, каждый на величину am+1. В исходную таблицу добавляется столько строк, сколько предлагается вариантов. При k вариантах это приведет к противоположному дебалансу, равному (k–1)·am+1. Поэтому для сбалансированности модели добавляется фиктивный потребитель с такой потребностью. А в качестве затрат во всех клетках таблицы принимаются суммарные затраты на перевозку и производство С’ij=Cij+Ci, где Ci – себестоимость в i-м ПО. Исключение составляет фиктивный столбец: в первых m клетках затраты равны M, а в остальных – нулю. Те варианты, которые в оптимальном решении закрепятся за фиктивным потребителем, должны быть отброшены.
При прогнозировании длительного превышения возможностей над спросом может возникнуть вопрос о сокращении производства. Он также может быть представлен в виде транспортной задачи. Достаточно в затраты включить себестоимость, как в предыдущем случае, и добавить фиктивного потребителя с потребностью bn+1 и нулевыми затратами. Оптимальные значения дополнительных переменных в фиктивном столбце дадут величину сокращения производства в соответствующих ПО с учетом полных затрат.