Экономико-математическая модель транспортной задачи

Н.Е. Гучек

Доцент, кандидат технических наук

КОНСПЕКТ ЛЕКЦИЙ

по дисциплине

Методы оптимальных решений

Направление подготовки: 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. Если сумма запасов груза равна суммарной потребности в нем:

Экономико-математическая модель транспортной задачи - student2.ru ,

то транспортная задача называется закрытой.

Определение 2. Если сумма запасов груза не равна суммарной потребности в нем:

Экономико-математическая модель транспортной задачи - student2.ru ,

то транспортная задача называется открытой.

Рассмотрим закрытую транспортную задачу. Обозначим xij – количество груза, перевозимого из пункта Аi в пункт Bj.

Математическая модель транспортной задачи имеет вид

Экономико-математическая модель транспортной задачи - student2.ru

при ограничениях:

Экономико-математическая модель транспортной задачи - student2.ru

Экономико-математическая модель транспортной задачи - student2.ru .

Оптимальным решением является матрица

Экономико-математическая модель транспортной задачи - student2.ru ,

удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

Транспортная задача как задача линейного программирования, может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Поэтому для решения транспортных задач разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:

1) нахождение исходного опорного решения;

2) проверка этого решения на оптимальность;

3) переход от одного опорного решения к другому.

Рассмотри каждый из этапов.

Наши рекомендации