Экономико-математическая модель транспортной задачи
Н.Е. Гучек
Доцент, кандидат технических наук
КОНСПЕКТ ЛЕКЦИЙ
по дисциплине
Методы оптимальных решений
Направление подготовки: 38.03.01 «Экономика»
Профили подготовки: «Финансы и кредит», «Бухгалтерский учет, анализ и
аудит», «Налоги и налогообложение», «Мировая экономика»
Форма обучения: заочная
4 семестр
Тула 2016 г.
Конспект лекций подготовлен доцентом Н.Е. Гучек и утвержден на заседании кафедры «Финансы и менеджмент» института права и управления
протокол № 1 от 30 августа 2016 г.
Зав. кафедрой __________________________А.Л.Сабинина
Содержание
Лекция 9. Транспортная задача. 82
9.1.Экономико-математическая модель транспортной задачи. 82
9.2. Нахождение первоначального базисного распределения поставок. 84
9.3. Решение транспортной задачи методом потенциалов. 85
Лекция 10. Особые случаи транспортной задачи. 91
10.1. Вырожденность в транспортных задачах. 91
10.2. Открытая транспортная задача. 93
Лекция 11. Элементы теории игр. 98
11.1. Основные понятия теории игр. 98
11.2. Примеры игр. 100
11.3. Классификация игр. 105
Лекция 12. Игры двух лиц с нулевой суммой. 107
12.1. Основные предположения для игр двух лиц с нулевой суммой. 107
12.2. Смешанные стратегии. 110
12.3. Аналитическое решение игры 2´2. 112
12.4. Доминирование стратегий. 115
Лекция 13. Графическое решение игр. 117
13.1. Графическое решение игр размерности 2´n. 117
13.2. Графическое решение игр размерности m´2. 120
Лекция 14. Решение матричных игр с помощью линейного программирования. 122
14.1. Связь матричных игр и линейного программирования. 122
14.2. Алгоритм решения матричных игр с помощью линейного программирования. 124
Лекция 15. Игры с природой. 126
15.1. Критерии оптимальности в играх с природой. 126
15.2. Пример игры с природой. 128
Лекция 16. Применение теории игр в экономике. 132
16.1. Кооперативные игры.. 132
16.2. Позиционные игры.. 135
Лекция 17. Целочисленное программирование. 138
17.1. Математическая модель задачи. 138
17.2. Графический метод решения. 138
17.3. Метод Гомори и его применение в экономических задачах. 141
Лекция 18. Динамическое программирование. 145
18.1. Общая постановка задачи динамического программирования. 145
Лекция 19. Применение динамического программирования в экономике. 153
19.1. Задача об инвестировании предприятий. 153
19.2. Задача о замене оборудования. 158
.
Лекция 9. Транспортная задача
План.
9.1.Экономико-математическая модель транспортной задачи.
9.2. Нахождение первоначального базисного распределения поставок.
9.3. Решение транспортной задачи методом потенциалов.
6.4. Вырожденность в транспортных задачах.
6.5. Открытая модель транспортной задачи.
Экономико-математическая модель транспортной задачи
Транспортная задача – одна из распространенных задач линейного программирования. Ее цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
В общем виде транспортную задачу можно представить следующим образом: в m пунктах производства А1, А2, ¼, Аm имеется однородный груз в количествах соответственно а1, а2, ¼, аm. Этот груз необходимо доставить в n пунктов назначения В1, В2, ¼, Вn в количествах, соответственно b1, b2, ¼, bn. Стоимость перевозки 1 ед. груза (тариф) из пункта Аi в пункт Bj равна сij ден. ед.
Требуется составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребителей, и имеющий минимальную стоимость.
В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.
Определение 1. Если сумма запасов груза равна суммарной потребности в нем:
,
то транспортная задача называется закрытой.
Определение 2. Если сумма запасов груза не равна суммарной потребности в нем:
,
то транспортная задача называется открытой.
Рассмотрим закрытую транспортную задачу. Обозначим xij – количество груза, перевозимого из пункта Аi в пункт Bj.
Математическая модель транспортной задачи имеет вид
при ограничениях:
.
Оптимальным решением является матрица
,
удовлетворяющая системе ограничений и доставляющая минимум целевой функции.
Транспортная задача как задача линейного программирования, может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Поэтому для решения транспортных задач разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:
1) нахождение исходного опорного решения;
2) проверка этого решения на оптимальность;
3) переход от одного опорного решения к другому.
Рассмотри каждый из этапов.