Слайд 2
![Под названием транспортная задача объединяется широкий круг задач с единой математической моделью.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-1.jpg)
Под названием транспортная задача объединяется широкий круг задач с единой математической
моделью.
Слайд 3
![Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-2.jpg)
Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования
специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.
Слайд 4
![Для простоты понимания рассматривается как задача об оптимальном плане перевозок](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-3.jpg)
Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов
из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача по теории сложности вычислений входит в класс сложности P. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).
Слайд 5
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-4.jpg)
Слайд 6
![Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-5.jpg)
Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта
из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи
Слайд 7
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-6.jpg)
Слайд 8
![Исторический поиск методы решения Проблема была впервые формализована французским математиком](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-7.jpg)
Исторический поиск методы решения
Проблема была впервые формализована французским математиком Гаспаром
Монжем в 1781 году. Прогресс в решении проблемы был достигнут во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.
Слайд 9
![Гаспар Монж (Французский математик, геометр, государственный деятель, морской министр) Канторович](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-8.jpg)
Гаспар Монж
(Французский математик, геометр, государственный деятель, морской министр)
Канторович Леонид Витальевич
(Советский математик
и экономист, пионер и один из создателей линейного программирования.)
Слайд 10
![Методы решения Классическую транспортную задачу можно решить симплекс-методом, но в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-9.jpg)
Методы решения
Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда
особенностей её можно решить проще (для задач малой размерности).
Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из ~A_i в ~B_j груза ~X_ij больше либо равно 0, а в маленькие клетки — соответствующие тарифы ~C_ij.
Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: «северо-западного угла», «наименьшего элемента», двойного предпочтения и аппроксимации Фогеля.
Слайд 11
![Метод северо-западного угла (диагональный или улучшенный) На каждом этапе максимально](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-10.jpg)
Метод северо-западного угла (диагональный или улучшенный)
На каждом этапе максимально возможным
числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из ~A_i или полностью удовлетворяется потребность ~B_j
Слайд 12
![Метод наименьшего элемента. Одним из способов решения задачи является метод](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-11.jpg)
Метод наименьшего элемента.
Одним из способов решения задачи является метод минимального (наименьшего)
элемента. Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями.
Алгоритм:
1.Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.
2.Проверяются строки поставщиков на наличие строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
3.Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.
Слайд 13
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/319729/slide-12.jpg)