- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
20. Модели транспортных задач и их характеристика, условия разрешимости.
Задачи, называемые транспортными, составляют большой подкласс распределительных задач. С содержательной стороны они не обязательно связаны с доставкой или перевозкой грузов, а выделяются из других задач особой структурой математической модели. Поэтому правильнее говорить о моделях транспортного типа.
Если удельные затраты на перевозку не зависят от количества перевозимого груза, транспортная задача описывается линейной моделью. При этом ее особенности позволяют применять специальные методы линейного программирования, которые более эффективны, чем универсальные. Ниже рассматриваются только линейные задачи.
Простейшая транспортная задача (т-задача)
Эта задача является основополагающей для всех транспортных задач. Пример такой задачи приведен в разд. 4.9.
В общем случае исходными данными являются:
m – число пунктов отправления (ПО) или производства;
n – число пунктов назначения (ПН) или потребления;
Cij – затраты на перевозку единицы груза из пункта i в пункт j, ij;
ai – количество груза в пункте i, i (возможности ПО);
bj – потребность в грузе в пункте j, j.
Критерием задачи являются суммарные затраты на перевозку. Безотносительно к значениям ai и bj модель записывается в виде
Однако такая запись модели корректна только тогда, когда Напомним, что задача, в которой суммарные потребности равны суммарной возможности, то есть
(5.1)
называется сбалансированной или закрытой. Как будет показано в этой главе, любая несбалансированная задача легко приводится к закрытой. Поэтому здесь рассмотрим только сбалансированную задачу:
(5.2)
(5.3)
(5.4)
Xij 0. (5.5)
Элементы модели:
– матрица перевозок;
– матрица транспортных затрат;
a=(a1, a2, . . . , am) – вектор возможностей ПО;
b=(b1, b2, . . . , bn) – вектор потребностей ПН.
Отметим особенности рассматриваемой задачи:
Модель содержит две группы условий, размерность которых равна соответствующему числу ПО и ПН; число переменных равно произведению mn;
Все коэффициенты при переменных в условиях (5.3), (5.4) равны единице;
Каждая переменная входит в условия ровно 2 раза, один и только один раз в группу (5.3) и также один раз в группу (5.4);
Задача имеет простые условия разрешимости, которые определяются следующей теоремой.
Теорема.
Для разрешимости Т-задачи необходимо и достаточно, чтобы она была сбалансированной.
Замечание. Теорема справедлива при конечных значениях Сij.
Приведем доказательство.
Необходимость доказывается исходя из того, что задача (5.2)-(5.5) разрешима. В этом случае все условия задачи выполняются. Просуммируем условия (5.3) по i, а условия (5.4) по j:
Так как левые части равенств равны, то равны и правые. Таким образом, в разрешимой задаче всегда имеет место формальный баланс возможностей и потребностей.
Достаточность доказывается конструктивным способом.
Вспомним, что задача линейного программирования всегда разрешима, если допустимое множество – выпуклый многогранник, то есть непустое и ограниченное.
Ограниченность переменных снизу задана явно, а ограничение сверху следует из конечности всех ai и bj, больше которых переменные быть не могут. Следовательно, множество ограничено.
Теперь покажем, что оно непустое. Для этого достаточно найти хотя бы одно допустимое решение. Одно из таких решений всегда можно построить, если задача сбалансирована, следующим образом:
(5.6)
Очевидно, что оно неотрицательно. Остается проверить выполнение основных условий задачи. Подставив (5.6) в левую часть(5.3), получим:
решение удовлетворяет условиям (5.3).
Подставив первый вариант (5.6) в (5.4), также убеждаемся в выполнении этих условий:
.
Таким образом, допустимое множество сбалансированной задачи непустое и ограниченное, а, значит, задача всегда разрешима. ▲
Условия (5.3), (5.4) – линейно зависимы из-за сбалансированности задачи. Действительно, пусть известны все равенства (5.3) и (n-1) равенство (5.4). Просуммируем отдельно первые и вторые и затем из первой суммы вычтем вторую. В результате получим недостающее равенство, описывающее пункт потребления, не включенный в исходную систему (5.4). Можно строго показать, что число линейно-независимых уравнений или, иначе, ранг системы (5.3), (5.4) равен m+n-1. Следовательно, такую размерность имеют базис и базисное решение Т-задачи.