- •1. Экономико-математическая модель транспортной задачи.
- •2. Обща формулировка тз
- •3. Теорема (о ранге системы ограничений закрытой тз) и следствие из неё. Открытая тз.
- •4. Оценка свободной клетки, ее экономический смысл, критерий оптимальности базисного распределения поставок.
- •5. Теорема о потенциалах свободных клеток. Вычисление оценок свободных клеток методом потенциалов.
- •6. Понятие об игровых моделях.
- •7. Классификация игр.
- •8. Формальное представление игр.
- •9 .Принцип минимакса для антагонистических игр.
- •10.Фунд-ое нер-во для цен антагонистических игр.
- •11. Седловая точка. Теорема о седловой точке.
- •12. Понятие смешанной стратегии, чистой стратегии, активной стратегии.
- •14.Граф.Метод реш-ия игры 2х2 (формулы).
- •15.Доминирущие стратегии, заведомо невыгодные стратегии, упрощение игр.
- •16. Сведение игры mxn к двойственной задаче лп
- •17.Игры с природой: постановка задачи, матрица рисков.
- •18. Критерий принятия решений в условиях риска (Байеса 1 и 2). Лемма (показатели эффективности и неэффективности стратегии). Теорема об эквивалентности критериев Байеса.
- •19. Критерий принятия решений в условиях неопределенности: критерий Лапласа и Сэвиджа
- •20. Критерий принятия решений в условиях неопределенности: критерий Вальда и Гурвица
- •21.Общая постановка задачи динамического программирования (дп). Особенности задачи дп
- •22. Принцип оптимальности и уравнение Бэллмана
- •23. Задача о распределении средств между n предприятиями (основные уравнения)
- •25. Понятие маршрута, цепи, простой цепи, цикла для графа. Связные, несвязные графы. Дерево, лес.
- •26. Планарные и плоские графы. Изоморфные графы. Полные графы.
- •27. Эйлеровы графы. Критерий существования эйлерова цикла в графе. Полуэйлеров граф. Задача о Кенигсбергских мостах.
- •28. Гамильтонов граф. Достаточные признаки существования гамильтонова цикла (связь с полнотой цикла, теоремы Оре и Дирака). Полугамильтонов граф.
- •29.Орграфы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.
- •30.Комбинаторная постановка задачи коммивояжера.
- •31. Постановка задачи коммивояжера в виде задачи целочисленного программирования. Условие наличия одного цикла.
- •32. Постановка задачи коммивояжера на языке теории графов.
- •33. Теорема о приведения матрицы расстояний в зк. Оценка маршрута снизу (нижняя граница).
- •34. Ветвление, оценки нулевых переходов, уточнение нижней границы маршрута.
- •35. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.
1. Экономико-математическая модель транспортной задачи.
Переменными (неизвестными) транспортной задачи являются xij , i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок:
Так как произведение Cij*Xij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:
По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция задачи имеет вид:
Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид:
Вторая группа из n уравнений выражает требование удовлетворить запросы всех n потребителей полностью и имеет вид:
Учитывая условие неотрицательности объемов перевозок математическая модель выглядит следующим образом:
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарынм запросам потребителей, т.е.:
Такая задача называется задачей с правильным балансом, а модель задачи закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а модель задачи — открытой.
Математическая формулировка транспортной задачи такова: найти переменные задачи X=(xij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (цифра 2 на математической модели) , (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1)
2. Обща формулировка тз
Условие: Однородный груз сосредоточен у m поставщиков в объемах a1, a2, ... am. Данный груз необходимо доставить n потребителям в объемах b1, b2 ... bn. Известны Cij , i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.
Исходные данные транспортной задачи записываются в виде таблицы:
Исходные данные задачи могут быть представлены в виде:
вектора А=(a1,a2,...,am) запасов поставщиков
вектора B=(b1,b2,...,bn) запросов потребителей
матрицы стоимостей:
3. Теорема (о ранге системы ограничений закрытой тз) и следствие из неё. Открытая тз.
Теорема 6.2. Ранг системы векторов-условий транспортной задачи равен r = m+n-1.
Доказательство. Как известно из линейной алгебры, для нахождения базиса системы векторов необходимо составить однородную систему уравнений.
Эту систему с помощью преобразований Жордана приводят к равносильной разрешенной; в базис включают векторы, соответствующие разрешенным неизвестным. Ранг системы векторов равен числу векторов, входящих в базис, т.е. числу разрешенных неизвестных этой системы.
Системе векторов – условий транспортной задачи Aij , i=1,2,,…,m, j=1,2,…,n соответствует однородная система уравнений, где =(0,0,…,0)т – нулевой вектор (транспонированный).
Транспортная задача называется открытой транспортной задачей, если условие баланса нарушаются; в случае выполнения условия баланса она называется сбалансированной транспортной задачей.