Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
15 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
101.50 kB
Просмотров:
86
Скачиваний:
1
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Транспортная задача линейного](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img0.jpg)
Содержание слайда: Транспортная задача линейного программирования
№2 слайд![Постановка транспортной](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img1.jpg)
Содержание слайда: Постановка транспортной задачи
Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов AiBj и cij (i=1..m; j=1..n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е.
а суммарные транспортные расходы минимальны.
№3 слайд![Математическая модель](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img2.jpg)
Содержание слайда: Математическая модель транспортной задачи
Будем называть любой план перевозок допустимым, если он удовлетворяет системам ограничений и требованием неотрицательности.
Допустимый план, будем называть опорным , если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.
План будет называться оптимальным , если он, среди всех допустимых планов, приводит к максимальной суммарной стоимости перевозок.
№4 слайд![Методы решения транспортных](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img3.jpg)
Содержание слайда: Методы решения транспортных задач
Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.
Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij>=0, а в маленькие клетки - соответствующие тарифы Cij.
№5 слайд![Методы решения транспортных](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img4.jpg)
Содержание слайда: Методы решения транспортных задач
Затем решение задачи разбивается на два этапа:
Определение опорного плана
Нахождение оптимального решения, путем последовательных операций
Найдем в начале допустимое (опорное) решение транспортной задачи. Это решение можно находить, используя метод "северо-западного угла" или метод "минимального элемента".
Метод северо-западного угла (диагональный). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, что найденные компоненты плана Хij удовлетворяют горизонтальным и вертикальным уравнениям.
Метод наименьшего элемента. Сущность способа в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.
№6 слайд![Метод северо-западного угла](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img5.jpg)
Содержание слайда: Метод северо-западного угла
Начнем заполнение с клетки, расположенной вверху слева, то есть с "северо-западного угла". Вместо x11 впишем число x11=min(a1, b1). Возможны два варианта.
min(a1, b1)=a1, то есть a1<b1. Тогда, запланировав перевозку из первого склада в первый пункт потребления в объеме a1 мы полностью опустошим первый склад и там ничего не останется. Поэтому все остальные перевозки из первого склада могут быть только нулевые. Ну, а потребность в первом пункте потребления останется в объеме b1-a1.
Обратите внимание на то, что оставшаяся незаполненной часть таблицы вновь по структуре та же, что и исходная таблица, только в ней на одну строку меньше.
№7 слайд![Метод северо-западного угла](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img6.jpg)
Содержание слайда: Метод северо-западного угла
Наша таблица примет вид:
№8 слайд![Метод северо-западного угла](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img7.jpg)
Содержание слайда: Метод северо-западного угла
min(a1, b1)=b1, то есть b1<a1. Тогда, запланировав перевозку из первого склада в первый пункт потребления в объеме b1, мы полностью удовлетворим его потребности. Перевозить туда больше будет ничего не надо, поэтому остальные перевозки туда будут равны нулю.
Ну, а в первом складе еще останется a1-b1 запасов продукта. Обратите внимание на то, что оставшаяся незаполненной часть таблицы вновь по структуре та же, что и исходная таблица, только в ней на один столбец меньше.
Ну, а дальше все можно повторить, продолжая заполнять оставшуюся часть таблицы перевозок начиная с левого верхнего, "северо-западного" угла, пока не будут исчерпаны запасы всех складов и не удовлетворены потребности всех пунктов потребления.
№9 слайд![Метод северо-западного угла](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img8.jpg)
Содержание слайда: Метод северо-западного угла
Наша таблица примет вид:
№10 слайд![Метод северо-западного угла У](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img9.jpg)
Содержание слайда: Метод северо-западного угла
У нас всего в таблице m строк и n столбцов. Каждый раз исчезает, как минимум, либо строка, либо столбец (могут исчезнуть сразу и строка, и столбец, если запасы какого-то подмножества складов полностью удовлетворят потребности какого-то подмножества пунктов потребления). Однако при последней перевозке исчезает сразу и последняя строка, и последний столбец. Поэтому получающийся план перевозок содержит не более m+n-1 компонент.
Мы не будем доказывать, что план, полученный методом северо-западного угла, является опорным. Заметим лишь, что если получающийся план содержит ровно m+n-1 компоненту, то он называется невырожденным. Если число положительных компонент плана перевозок меньше, то он называется вырожденным.
№11 слайд![Метод северо-западного угла](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img10.jpg)
Содержание слайда: Метод северо-западного угла
Рассмотрим задачу.
Фирма должна отправить некоторое количество кроватей с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице.
№12 слайд![Решение Построим опорный план](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img11.jpg)
Содержание слайда: Решение
Построим опорный план для рассмотренной выше задачи. В начале построим его с помощью метода "северно-западного угла"
Исходная транспортная таблица:
№13 слайд![Метод минимального](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img12.jpg)
Содержание слайда: Метод минимального (максимального) элемента
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
№14 слайд![Задание Составить](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img13.jpg)
Содержание слайда: Задание
Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:
№15 слайд![Задание Найти опорный план](/documents_5/5ad92041aa111910fa6aea5629aeb2fd/img14.jpg)
Содержание слайда: Задание
Найти опорный план для задачи