- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Транспортная задача с ограниченными пропускными способностями (Td - задача)
Отличается от предыдущей задачи учетом ограничений на пропускные возможности коммуникаций. В реальных условиях пропускные способности дорог, воздушных коридоров, линий связи и т.п. всегда ограничены сверху. Если известно, что фактическая загрузка будет заведомо меньше, задача рассматривается как простейшая. В противном случае учет этих ограничений приводит к более сложной транспортной задаче, называемой Тd-задачей. Ее модель имеет вид
(5.7)
(5.8)
(5.9)
0 Xij dij, i,j, (5.10)
где dij –пропускная способность коммуникации i j.
Ограничения (5.10) вносят существенные коррективы в свойства задачи. Из особенностей модели, присущих Т-задаче, сохраняются все, кроме последней. В Тd-задаче условие сбалансированности не является достаточным для разрешимости задачи. Более того, в число необходимых условий существования решения помимо его входят еще две группы условий, отражающих физическую реализуемость решения:
(5.11)
(5.12)
О ни требуют, чтобы суммарная пропускная способность коммуникаций, входящих в каждый ПН была не меньше объема поставок, а выходящих из ПО – не меньше количества вывозимого груза. Если хотя бы одно из них нарушается, задача заведомо неразрешима.
Однако и выполнение всех необходимых условий не гарантирует разрешимость Тd-задачи. Например, условия (5.1), (5.11) и (5.12) выполняются для транспортной сети, показанной на рис. 5.1, что легко проверить. Но задача неразрешима, так как невозможно поставить во второй пункт назначения 8 единиц груза.
Задачи с неоднородным грузом
В рассмотренных задачах по умолчанию предполагалось, что для отправителей и получателей грузы неразличимы – это задачи с однородным грузом. Если в перевозках участвуют несколько видов груза с одинаковыми или различными транспортными затратами, исходную многопродуктовую задачу можно разбить на задачи с однородным грузом (по числу видов).
Если же имеет место взаимозаменяемость грузов у получателей, то исходную задачу нельзя разделить на отдельные задачи. Например, получателю нужен каменный и бурый уголь. Известна потребность в том и другом и, кроме того, есть потребность, которая может быть удовлетворена любым из них. Последняя измеряется в единицах либо каменного, либо бурого угля. Такие задачи называют задачами с неоднородным грузом. В случае отсутствия ограничений на пропускные способности они легко преобразуются к задачам с однородным грузом.
Взаимозаменяемость грузов характеризуется коэффициентом взаимозаменяемости . Например, если 1 т. каменного угля заменяет потребителю 2 т. бурого, то Зная все грузы можно привести к одному виду. Затем вместо одного исходного ПО вводится столько, сколько в нем видов груза. Аналогично каждый исходный ПН заменяется новыми, число которых равно числу видов потребностей. Наконец, определяются приведенные затраты на перевозки между всеми новыми пунктами. Если виды грузов в ПО и ПН совпадают, затраты на перевозку равны исходным Cij; если же они разные, то перевозка запрещается (Cij=М). Между ПО с пересчитанным грузом и ПН с взаимозаменяемой потребностью затраты равны
После таких преобразований модель задачи записывается аналогично случаю с однородным грузом, а ее размерность определяется числом пунктов, заменяющих исходные.
Для разрешимости задачи необходимо кроме сбалансированности, чтобы по каждому виду груза суммарные возможности были не меньше суммарной потребности (без учета взаимозаменяемой). Однако и при выполнении всех необходимых условий возможна неразрешимость задачи из-за присутствия запрещенных перевозок.
Многоиндексные задачи
Для учета дополнительных условий перевозки вводятся переменные с числом индексов более двух. В таких случаях говорят о многоиндексных транспортных задачах. Например, если существенное значение имеет вид транспорта, то в модели используются переменные Xijk, означающие количество груза, перевозимое из i-го пункта в j-й k-ым видом транспорта. Модель трехиндексной задачи зависит от конкретных условий. Если в исходных данных имеем производительность каждого вида транспорта pk и не учитываются пропускные способности, то задача описывается трипланарной моделью:
Она идентична Т-задаче. Отличие лишь в числе переменных и групп условий. Поэтому каждая переменная входит в модель ровно три раза, а сбалансированность, как необходимое и достаточное условие разрешимости задачи, записывается в виде
Если транспортные средства принадлежат разным перевозчикам, то в модели будут фигурировать четырехиндексные переменные Xijkl, где l – индекс перевозчика.
Дальнейшая детализация условий транспортировки может потребовать переменных с пятью и более индексами. В ряде случаев многоиндексные задачи удается свести к двухиндексным.