- •1. Понятие задачи математического программирования. Задачи линейного программирования.
- •2. Допустимые и оптимальные решения задачи математического программирования.
- •4.Примеры задач линейного программирования: задача о диете
- •5. Примеры задач линейного программирования: транспортная задача.
- •6.Различные формы записи задачи линейного программирования и их эквивалентность
- •7. Понятие выпуклого множества. Теорема о выпуклости множества допустимых решений задачи линейного программирования
- •9. Геометрическая интерпретация и графический метод решения задачи линейного программирования
- •10. Метод Жордана-Гауса. Понятия базисного и опорного решения системы линейных уравнений.
- •11. Понятие и структура симплексной таблицы. Алгоритм симплекс-метода и его обоснование на простейшем примере
- •12. Проблема нахождения начального опорного решения
- •Метод искусственного базиса (м-метод)
- •13.Понятие двойственной задачи линейного программирования
- •14. Простейшие связи между прямой и двойственной задачами
- •15. Теоремы двойственности.
- •16.Экономическая интерпретация прямой и двойственной задачи.
- •17. Пример нахождения двойственной задачи исходя из оптимального решения прямой задачи.
- •18. Транспортная задача. Закрытая и открытая транспортная задача. Условие допустимости.
- •19.Методы нахождения начального допустимого базисного решения транспортной задачи: метод «северо-западного угла», метод минимального элемента, метод Фогеля.
- •20. Метод потенциалов решения транспортной задачи. Вырожденная транспортная задача.
- •21.Основные понятия и определения теории игр. Классификация игр.
- •22.Антагонические игры. Решение матричных игр в чистых стратегиях.
- •23.Решение матричных игр в смешанных стратегиях. Мажорирование.
- •24. Игры с «природой». Основные понятия и критерии максимакса, Вальда, Сэвиджа и Гурвица.
- •25. Позиционные игры. Дерево решений.
18. Транспортная задача. Закрытая и открытая транспортная задача. Условие допустимости.
Транспортная задача(ТЗ)-одна из распространенных задач линейного программирования. Цель-разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием.
Общий вид:
поставщики |
Потребители |
Мощность поставщиков |
|||
В1 |
В2 |
В3 |
В4 |
||
А1 |
c11 х11 |
c12 х12 |
c13 х13 |
c14 х14 |
M1 |
А2 |
c21 х21 |
c22 х22 |
c23 х23 |
c24 х24 |
M2 |
А3 |
c31 х31 |
c32 х32 |
c33х33 |
c34 х34 |
M3 |
Спрос потребителей |
N1 |
N2 |
N3 |
N4 |
|
В верхнем левом углу каждой ячейки стоит коэф-т затрат(тарифы) – затраты на перевозку ед.груза от i-ого поставщика к j-ому потребителю.
Мощности поставщиков А1,А2,А3 соответственно равны M1, M2, M3. Спрос потребителей В1,В2,В3,В4 соответственно равны N1, N2, N3, N4.
Составим эк-математ. модель транспортной задачи.
Учтем следующие условия:
мощности всех поставщиков должны быть полностью реализованы
спросы всех потребителей д.б. удовлетворены
суммарные затраты на перевозку д.б минимальны.
Определить суммарные и минимальные затраты на перевозку всех грузов.
Введем переменные: пусть хij – кол-во перевезенного груза от i-го поставщика к j-му потребителю (i=1,2…m; j=1,2…n), где m – число поставщиков, n – число потребителей.
Тогда эк-мат модель задачи примет вид:
(1)
Суммарные затраты F на перевозку выражаются через коэф-ты затрат и поставки следующим образом: F(x)= min (2)
Математическая интерпретация модели транспортной задачи: на множество неотрицательных (допустимых) решений системы ограничений (1) найти такое решение Х=(х11,х12…хij), при котором линейная функция (2) принимает минимальное значение.
Особенность экономико-мат.модели транспортной задачи:
- распределение только однородных ресурсов
-система ограничений-есть система уравнений
-все переменные выражаются в одинаковых ед.измерения
-во всех уравнениях коф-ты при переменных равны 1
-каждая переменная входит в систему ограничений 2 раза
В зависимости от соотношения между суммарными мощностями пост-в и суммарными спросами потр-й тр.задачи делятся на открытые и закрытые.
Если суммарная мощность поставщиков равна суммарному спросу потребителей то тр.задача – закрытая
Если суммарная мощность поставщиков не равна суммарному спросу потребителей – открытая.
Алгоритм (этапы) решения тр.задачи
1.нахождение начального опорного плана перевозок(опорное решение).-метод сев-зап угла, наим-х стоимостей
2. построение системы потенциалов и проверка начального опорного плана перевозок на оптимальность
3. переход к новому опорному решению, суть кот.заключается в реализации циклов пересчета. Процедура будет проводиться несколько раз, пока не будет найдено оптимальное решение.