Реферат на тему Тема: Транспортная задача в матричной постановке. Венгерский метод.

Содержание:

Введение 3
1. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей 4
1.1. Постановка задачи и ее математическая модель 8
1.2. Определение оптимального и опорного плана транспортной задачи 11
2. Метод дифференциальных рент 12
2.1. Венгерский метод 13
2.2. Метод потенциалов 14
Заключение 15
Список использованной литературы 16

Введение:

Под названием «транспортная проблема» широкий спектр задач объединяется с единой математической моделью. Классическая проблема транспортировки — проблема наиболее экономичного плана транспортировки однородного продукта или взаимозаменяемых продуктов из точек производства в точки потребления, чаще всего встречается при практическом применении линейного программирования. Линейное программирование является одной из областей математического программирования — области математики, которая развивает теорию и численные методы для решения экстремальных многомерных задач с ограничениями.
Огромное количество возможных вариантов транспортировки затрудняет получение достаточно экономичного плана опытным путем или опытным путем. Использование математических и вычислительных методов в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом, однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплекс-метод, позволяют найти начальное решение для поддержки, а затем, улучшив его, получить оптимальное решение.
Цель работы: Транспортная задача в матричной постановке. Венгерский метод.
Задачи: 1. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей;
2. Постановка задачи и ее математическая модель;
3. Определение оптимального и опорного плана транспортной задачи;
4. Методы определения оптимального плана;
5. Венгерский метод;
6. Метод потенциалов.

Заключение:

В результате разработки курса были изучены методы решения транспортных задач, более подробно изучен венгерский метод. Венгерский метод решения транспортной проблемы относительно прост и может найти широкое применение в компаниях, где необходимо рассчитать минимальную стоимость перевозки товаров, например, от заводов до пунктов потребления. Дана экономическая интерпретация вопроса, построена его математическая модель. Используя венгерский алгоритм, был получен оптимальный транспортный план и вычислено оптимальное значение целевой функции.
Алгоритм венгерского метода был реализован программно в среде C ++ Builder. Используя разработанную программу, модель была проанализирована на чувствительность. В ходе этого анализа выяснилось, что стоимость перевозки товаров, которая в идеале составляла 87 974 евро в месяц, может быть снижена на 3520 евро, если в самой дорогой точке производства уменьшить объем выпускаемой продукции на 2200 кг и по самой низкой цене, чтобы увеличить его. В то же время общая стоимость транспортных расходов составит 84 454 евро в месяц. Внедренная программа имеет простой и удобный интерфейс, графически представляет решение проблемы венгерским методом и может быть использована для дополнительных расчетов транспортных расходов и для построения идеальных планов.
Транспортная проблема линейного программирования в настоящее время широко используется в теоретической обработке и практическом применении в транспорте и промышленности. Это особенно важно при рационализации производства важнейших видов промышленной и сельскохозяйственной продукции, а также при оптимальном планировании товарных потоков и функционировании различных видов транспорта.
Кроме того, многие другие проблемы линейного программирования сводятся к проблемам транспортного типа — задачам распределения, сетевым задачам и планированию.

Фрагмент текста работы:

Под названием «транспортная проблема» широкий спектр задач объединяется с единой математической моделью. Эти проблемы связаны с задачами линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплекс-метод, позволяют найти начальное решение поддержки и, улучшая его, получить идеальное решение.
В общем, проблема с перевозкой заключается в поиске идеального плана перевозки однородного груза с m баз A1, A2,…Am потребителям B1, B2,…Bn.
Различают два типа транспортных задач: однако, согласно критерию стоимости (транспортный план является оптимальным, если достигнуты минимальные затраты на его реализацию) и критерию времени (план является оптимальным, если затрачивается минимальное время на его выполнение).
Укажите количество груза, доступного на каждой из m баз (запасов), и общее a1, a2,…am количество доступного груза — a:

заказы каждого из потребителей (потребности) обозначим соот-ветственно , а общее количество потребностей – b:
,

мы имеем закрытую модель, а при условии
– открытую модель транспортной задачи.
Очевидно, что в случае закрытой модели весь доступный груз транспортируется полностью, и все потребности клиента полностью удовлетворяются; в случае открытой модели либо все клиенты удовлетворены, и в то же время избыточный груз остается на некоторых базах , либо весь груз израсходован, хотя потребности не полностью удовлетворены .
Существуют также одноэтапные модели задач, в которых транспортировка осуществляется напрямую, например, с базы или фабрики производителя до потребителя, и двухэтапная, где между ними имеется «перевалочный пункт», например, склад [8].
Удобно записать план транспортировки с указанием запасов и потребностей в виде следующей таблицы, которая называется таблицей транспортировки: