Презентация ТРАНСПОРТНАЯ ЗАДАЧА Лекции 10,11 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему ТРАНСПОРТНАЯ ЗАДАЧА Лекции 10,11 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 66 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:66 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.46 MB
- Просмотров:120
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: ТРАНСПОРТНАЯ ЗАДАЧА
Лекции 10,11
№2 слайд
Содержание слайда: Транспортная задача является частным случаем задачи линейного программирования и может быть решена симплекс-методом. Однако, в силу особенностей этой задачи, она решается с помощью так называемого распределительного метода и его модификаций
№3 слайд
Содержание слайда: Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А1, А2,…, Аm в
n пунктов назначения B1, B2,…,Bn.
При этом в качестве критерия оптимальности берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.
№4 слайд
Содержание слайда: Рассмотрим транспортную задачу, в которой в качестве критерия оптимальности берется минимальная стоимость перевозок всего груза. Обозначим через тарифы или стоимости перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе j-ым пунктом назначения, через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения (перевозки).
№5 слайд
Содержание слайда: Математическая модель транспортной задачи
Найти
при ограничениях
№6 слайд
Содержание слайда: Первое ограничение
означает, что все потребности должны быть удовлетворены , а второе -
,
что все запасы должны быть перевезены.
№7 слайд
Содержание слайда: Определение. Всякое неотрицательное решение системы ограничений транспортной задачи, определяемое матрицей размера m×n
,
называют допустимым решением (или планом) транспортной задачи.
№8 слайд
Содержание слайда: Определение.
План ,
при котором целевая функция принимает минимальное значение, называется оптимальным.
№9 слайд
Содержание слайда: Тарифы или стоимости перевозок единицы груза также задаются матрицей, которая называется матрицей транспортных издержек или матрицей стоимостей
№10 слайд
Содержание слайда: Транспортная таблица
№11 слайд
Содержание слайда: Необходимое и достаточное условие разрешимости
транспортной задачи
Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, то есть, чтобы выполнялось равенство
--балансовые условия.
№12 слайд
Содержание слайда: При выполнении этого условия модель транспортной задачи называется закрытой. Если балансовое условие не выполняется, то есть
,
то модель транспортной задачи называется открытой.
№13 слайд
Содержание слайда: В случае открытой транспортной задачи выполнение балансового условия достигается введением фиктивного поставщика или фиктивного потребителя с соответствующими тарифами, равными нулю.
№14 слайд
Содержание слайда: Любое решение транспортной задачи представляет собой распределение перевозок в транспортной таблице. Оптимальному решению транспортной задачи соответствует оптимальное распределение перевозок. Перераспределение перевозок в транспортной таблице осуществляется до тех пор, пока не будет найдено оптимальное распределение перевозок.
№15 слайд
Содержание слайда: Пример
№16 слайд
Содержание слайда: Все грузы должны быть перевезены, поэтому
Это три первых уравнения.
Все потребности должны быть удовлетворены и, значит,
Это четыре последних уравнения.
Здесь закрытая модель: сумма запасов равна сумме потребностей.
№17 слайд
Содержание слайда: А целевую функцию составили по матрице С - матрице тарифов перевозок.
№18 слайд
Содержание слайда: Пример. Задача организации оптимального снабжения .
Три фермерских хозяйства ежедневно могут доставлять в город соответственно 60, 60 и 50 ц молока для обеспечения пяти торговых точек :
Стоимость перевозки 1ц молока и потребности торговых точек в молоке указаны в таблице
№19 слайд
Содержание слайда: Таблица
№20 слайд
Содержание слайда: Экономико-математическая модель задачи.
Переменные :
- количество молока , поставляемое i-м фермерским хозяйством в j-ю торговую точку.
Целевая функция –суммарные транспортные издержки, которые необходимо минимизировать
№21 слайд
Содержание слайда: Эта задача является задачей открытого типа, так как запасы молока у фермерских хозяйств (поставщиков) больше потребностей в молоке у торговых точек. В этом случае изменяется вид системы ограничений.
№22 слайд
Содержание слайда: Функциональные ограничения:
По поставщикам (их 3)
№23 слайд
Содержание слайда: Этапы решения транспортной задачи
Составляют математическую модель задачи.
Находят исходное опорное решение.
Проверяют это решение на оптимальность.
Переходят от одного опорного решения к другому.
№24 слайд
Содержание слайда: Будем называть переменные , стоящие в занятых клетках распределительной или транспортной таблицы, базисными, а переменные находящиеся в пустых клетках, свободными.
№25 слайд
Содержание слайда: Определение исходного допустимого решения
1. Метод «северо-западного угла»
Метод заключается в том, что заполнение клеток таблицы начинают с левой верхней клетки (северо-западная часть таблицы) для перевозки и продолжают вниз и вправо, заканчивая клеткой для перевозки .
При этом способе распределения на тарифы не обращают внимания.
№26 слайд
Содержание слайда: 2. Метод «наименьшей стоимости»
Метод заключается в том, что заполнение клеток таблицы начинают с клетки, имеющей наименьшую стоимость перевозки. Если таких клеток несколько, то следует выбрать любую из них.
№27 слайд
Содержание слайда: Найти опорный план транспортной задачи методом наименьшей стоимости
№28 слайд
Содержание слайда: Минимальный тариф, равный 1 , находится в клетке .
Положим . Запишем это значение в соответствующую клетку и временно исключим из рассмотрения строку .
Потребности пункта назначения считаем временно равными 30 ед.
№29 слайд
Содержание слайда: В оставшейся части таблицы с двумя строками и и c четырьмя столбцами клетка с наименьшим тарифом находится на пересечении строки и столбца , где Положим Внесем это значение в соответствующую клетку таблицы.
№30 слайд
Содержание слайда: Временно исключим из рассмотрения столбец и будем считать запасы пункта равными 120 ед. После этого рассмотрим оставшуюся часть таблицы с двумя строками и и тремя столбцами , и . В ней минимальный тариф находится в клетке на пересечении строки и столбца и равен 3.
№31 слайд
Содержание слайда: Заполним описанным выше способом эту клетку и аналогично заполним ( в определенном порядке) клетки, находящиеся на пересечении строки и столбца .
№32 слайд
Содержание слайда: В результате получим опорный план
При данном плане перевозок общая стоимость перевозок составляет .
№33 слайд
Содержание слайда: Условие невырожденности плана
Если число заполненных клеток равно
m + n – 1, то план является невырожденным. Если число заполненных клеток меньше этого значения, то план (решение) называется вырожденным. В случае вырожденности плана условно считают одну (или несколько) из пустых клеток занятой, записывая в нее нулевую перевозку так, чтобы число занятых клеток стало равным
m + n – 1.
№34 слайд
Содержание слайда: В нашей задаче число заполненных клеток равно m + n – 1=3 + 4 – 1 = 6,
а пустых клеток – m × n – (m + n – 1), где m – количество пунктов отправления, n – количество пунктов назначения, что в нашем случае 3 × 4 – 6 = 6.
Значит, найденный план является невырожденным.
№35 слайд
Содержание слайда: Метод потенциалов проверки решения на оптимальность
Предположим, что каждый пункт отправления Ai вносит за перевозку единицы груза какую-то сумму , а каждый пункт назначения вносит
сумму . Эти платежи передаются некоторому третьему лицу, например, перевозчику. Величины и свяжем равенствами , где – тарифы для базисных клеток.
№36 слайд
Содержание слайда: Совокупность уравнений , составленных для всех базисных переменных, представляет совместную систему линейных уравнений, причем одну из переменных можно задавать произвольно и тогда остальные переменные из системы уравнений находятся однозначно.
№37 слайд
Содержание слайда: Обозначим через , где назовем псевдостоимостями или косвенными стоимостями (тарифами). Псевдостоимости находятся для всех свободных клеток.
Платежи и не обязательно должны быть положительны, поскольку не исключено, что «перевозчик» сам платит тому или иному пункту какую-то премию за перевозку.
№38 слайд
Содержание слайда: Теорема «о платежах».
Для заданной совокупности платежей
и суммарная косвенная стоимость перевозок при любом допустимом плане сохраняет одно и тоже значение
В этой формуле с зависит только от совокупности платежей и не зависит от того, каким именно допустимым планом пользуемся.
№39 слайд
Содержание слайда: Теорема оптимальности.
Если для всех базисных клеток
а для всех свободных клеток
,
то допустимый план является оптимальным и никаким способом улучшен быть не может.
№40 слайд
Содержание слайда: Пример
Найти опорное решение методом минимальной стоимости
и проверить оптимальность решения методом потенциалов.
№41 слайд
Содержание слайда:
№42 слайд
Содержание слайда:
№43 слайд
Содержание слайда: Находим потенциалы базисных клеток
№44 слайд
Содержание слайда: Положим и решим систему.
Получим
Найдем псевдостоимости пустых клеток
План перевозок оптимален
№45 слайд
Содержание слайда: Пример 2.
На складах имеются запасы продукции 90, 400 и 110 тонн соответственно. Потребители должны получить эту продукцию в количествах 140, 300 и 160 тонн соответственно. Найти такой план закрепления поставщиков к потребителям, при котором суммы затрат на перевозки минимальны.
№46 слайд
Содержание слайда: Расходы на перевозки 1 т продукции заданы матрицей (у.е.)
Сумма потребностей и сумма запасов равны 140+300+160=90+400+110=600. Модель закрытая.
№47 слайд
Содержание слайда:
№48 слайд
Содержание слайда: План
№49 слайд
Содержание слайда: 2)Проверим план на оптимальность методом потенциалов.
В таблице занято клеток
Для них найдем потенциалы.
№50 слайд
Содержание слайда: Положим
Решим систему:
№51 слайд
Содержание слайда: Внесем в таблицу потенциалы занятых клеток
№52 слайд
Содержание слайда: Найдем оценки свободных клеток.
Решение не оптимально, т.к. имеется отрицательная оценка.
№53 слайд
Содержание слайда: 3)Переход к другому решению.
Перераспределим грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а занятая- свободной.
Для свободной клетки с отрицательной оценкой строится цикл(цепь, многоугольник), все вершины которого, кроме одной находятся в занятых клетках. Углы прямые, число вершин четное
№54 слайд
Содержание слайда: Около свободной клетки цикла ставится (+), а затем поочередно(-) , (+).У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+) и отнимают от грузов у вершин со знаком (-). В результате перемещения получают новый опорный план. Это решение проверяют на оптимальность и т. д. до тех пор ,пока не получится оптимальное решение.
№55 слайд
Содержание слайда:
№56 слайд
Содержание слайда:
№57 слайд
Содержание слайда:
№58 слайд
Содержание слайда: Получили новое решение
Проверим его на оптимальность, вычислив потенциалы базисных клеток.
№59 слайд
Содержание слайда: Потенциалы заполненных клеток
№60 слайд
Содержание слайда: Оценки свободных клеток
План не оптимален, т.к. оценка клетки (21) отрицательна.
№61 слайд
Содержание слайда:
№62 слайд
Содержание слайда:
№63 слайд
Содержание слайда: Новый план
Снова проверяем его на оптимальность. Для занятых клеток
Находим
№64 слайд
Содержание слайда: Для свободных клеток псевдостоимости равны
№65 слайд
Содержание слайда: Оценки свободных клеток
№66 слайд
Содержание слайда: Все оценки положительны, поэтому план оптимален.
Ответ:
.
При этом
По сравнению с первоначальным планом расходы уменьшились на величину
1610-1280=330у.е.
Скачать все slide презентации ТРАНСПОРТНАЯ ЗАДАЧА Лекции 10,11 одним архивом:
