Транспортная задача (задача Монжа – Канторовича)

ОГЛАВЛЕНИЕ  

ВВЕДЕНИЕ   3

ГЛАВА 1. Основные понятия решения транспортной задачи   6

1.1 Постановка транспортной задачи   6

1.2. Методы решения транспортной задачи   8

1.3. Решение транспортной задачи в Excel   13

ГЛАВА 2. Задача Монжа-Канторовича   18

2.1. Задача Монжа   18

2.2. Обобщение, двойственность   20

2.3. Задача Монжа-Канторовича с заданной маргинальной разностью   22

2.4. Сравнение задач Монжа и Канторовича   25

ЗАКЛЮЧЕНИЕ   27

СПИСОК ЛИТЕРАТУРЫ  29

ВВЕДЕНИЕ

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так.Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся примерно. В середине XX века был создан специальный математический аппарат, помогающий это делать согласно научным данным. Соответствующий раздел математики называется математическим программированием.Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.Задача Монжа-Канторовича, второе название задача об оптимальной транспортировке мер, пользуется большим вниманием специалистов из различных областей математики: теории вероятностей, анализа, геометрии, динамических систем. Также задача представляет большой интерес для экономических и технических приложений. В этом заключается актуальность выбранной темы.Основа классической теории, связанной с этой задачей, была разработана Л.В. Канторовичем в 1940-е годы и сильно развита во второй половине ХХ-го века такими известными учёными, как В.Н. Судаков, С. Виллани, Л. Амброзио, A.M. Вершик и многими другими. Канторович предложил рассматривать задачу поиска меры на прямом произведении двух пространств с фиксированными проекциями меры (маргиналами) на каждое из них, которая была бы оптимальной относительно некоторого линейного критерия. Используя линейность задачи и свои результаты в этой области, Канторович нашел достаточные условия существования решения и сформулировал в их предположении фундаментальный принцип двойственности [11].Рассматриваемая Канторовичем задача тесно связана с классической задачей "о перемещении масс", которая была предложена Г. Монжем [20] в 1781 году ("задача Монжа"): имеется куча песка и яма одинаковых объемов. Как засыпать песком яму, потратив наименьшие усилия на транспортировку массы? В формулировке Канторовича фиксированные маргиналы – это распределение куч песка и ям на плоскости, а оптимальная мера – это обобщение понятия транспортировки, называемое транспортным планом.В современном понимание задача Монжа-Канторовича звучит так: пространства, на которых определены маргинальные меры, предполагаются полными, метрическими, сами меры – борелевскими вероятностными, а функция стоимости, задающая критерий оптимальности – произвольной полунепрерывной снизу.Предмет исследования – транспортные задачи Монжа - Канторовича. Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.Цель работы состоит в исследовании свойств задачи Монжа-Канторовича.Задачи:1. Рассмотреть понятие транспортно задачи. 2. Рассмотреть методы решения транспортных задач. 3. Изучить решение транспортных задач методами Монжа-Канторовича4. Рассмотреть примеры решение транспортных задач методами Монжа-Канторовича.В работе используются методы теории вероятностей, общей теории меры и функционального анализа.Работа имеет теоретический характер и может быть полезна для специалистов в области теории вероятностей.ГЛАВА 1. Основные понятия решения транспортной задачи

СПИСОК ЛИТЕРАТУРЫ

Богачев В. И., Колесников А. В. Задача Монжи Канторовичи: достижения, связи и перспективы // УМН. — 2012. — Т. 67, № 5. — С. 3—110.

Бронштейн И.Н., Семендяев К.А. Справочник по математике. - М.; Наука, 1986гВ ершик А. М. Метрика Канторовича: начальная история и малоизвестные применения // Зап. научн. сем. ПОМИ. — 2004. — Т. 312. — С. 69 85.

В ершик А. Л/.. Затицкий П. Б., Пет,ров Ф. В. Виртуальная непрерывность измеримых функций многих переменных и теоремы вложения // Функц. анализ и его прил. — 2013. — Т. 47, № 3. — С. 1 11.

Голубков Е.П. Технология принятия управленческих решений. – М.: Издательство «Дело и Сервис», 2005. – 544 с.

Добрушин Р. Л. Задание системы случайных величин при помощи условных распределений // ТВП. — 1970. — Т. 15, № 3. — С. 469 497.

Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976 г.

Заев Д. А. О задаче Монжи Кииторовичи с дополнительными линейными ограничениями // Математические заметки. — 2015. — Т. 98. — С. 664 683.

Заев Д. А. Тезисы доклада: "Задача Монжи Канторовичи с дополнительными ограничениями" // Тезисы международной конференции "Бесконечномерный анализ, стохастика, математическое моделирование: новые задачи и методы", Москва. — 2014. — С. 44.

Канторович Л. В. О перемещении масс // Зап. научн. сем. ПОМИ. — 2004. - Т. 312, № XI. - С. 11—14

Иванов Ю.П., Лотов А.В. Математические модели в экономике. - М.; Наука, 1979г.

Карманов В.Г. Математическое программирование. - М.; Наука, 1986г.

Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование ”, Минск, Вышейшая школа, 2001г.

Левин В. Л. О теоремах двойственности в задаче Монжи Канторовичи // УМН. - 1977. - Т. 32, 3(195). - С. 171-172.

Левин В. Л., Милютин А. А. Задача о перемещении масс с разрывной функцией стоимости и массовая постановка проблемы двойственности выпуклых экстремальных задач // УМН. - 1979. - Т. 34, 3(207). - С. 3 68.

Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. - М.; Наука, 1978г.

Поспелова Л.Я., Шананин А.А. Показатели нерациональности потребительского поведения и обобщенный непараметрический метод // Математическое моделирование, 1998, Т.10, №4, с.105-116.

Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. Москва, "Наука", 1983.