Транспортная задача линейного программирования

Сентябрь 3, 2022

Главная
Алгебра
Транспортная задача линейного программирования

Содержание

2. Постановка транспортной задачи Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно
3. Математическая модель транспортной задачи Будем называть любой план перевозок допустимым, если он удовлетворяет системам ограничений и
4. Методы решения транспортных задач Так как транспортная задача является задачей линейного программирования, то её можно решать
5. Методы решения транспортных задач Затем решение задачи разбивается на два этапа: Определение опорного плана Нахождение оптимального
6. Метод северо-западного угла Начнем заполнение с клетки, расположенной вверху слева, то есть с "северо-западного угла". Вместо
7. Метод северо-западного угла Наша таблица примет вид:
8. Метод северо-западного угла min(a1, b1)=b1, то есть b1 Ну, а в первом складе еще останется a1-b1
9. Метод северо-западного угла Наша таблица примет вид:
10. Метод северо-западного угла У нас всего в таблице m строк и n столбцов. Каждый раз исчезает,
11. Метод северо-западного угла Рассмотрим задачу. Фирма должна отправить некоторое количество кроватей с трёх складов в пять
12. Решение Построим опорный план для рассмотренной выше задачи. В начале построим его с помощью метода "северно-западного
13. Метод минимального (максимального) элемента Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую
14. Задание Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:
16. Скачать презентацию

Слайд 2

Постановка транспортной задачи
Однородный груз, имеющийся в 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

Математическая модель транспортной задачи
Будем называть любой план перевозок допустимым, если

он удовлетворяет системам ограничений и требованием неотрицательности.
Допустимый план, будем называть опорным , если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.
План будет называться оптимальным , если он, среди всех допустимых планов, приводит к максимальной суммарной стоимости перевозок.

Слайд 4

Методы решения транспортных задач
Так как транспортная задача является задачей линейного программирования,

то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.
Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij>=0, а в маленькие клетки - соответствующие тарифы Cij.

Слайд 5

Методы решения транспортных задач
Затем решение задачи разбивается на два этапа:
Определение опорного

плана
Нахождение оптимального решения, путем последовательных операций
Найдем в начале допустимое (опорное) решение транспортной задачи. Это решение можно находить, используя метод "северо-западного угла" или метод "минимального элемента".
Метод северо-западного угла (диагональный). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, что найденные компоненты плана Хij удовлетворяют горизонтальным и вертикальным уравнениям.
Метод наименьшего элемента. Сущность способа в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.

Слайд 6

Метод северо-западного угла
Начнем заполнение с клетки, расположенной вверху слева, то

есть с "северо-западного угла". Вместо x11 впишем число x11=min(a1, b1). Возможны два варианта.
min(a1, b1)=a1, то есть a1Обратите внимание на то, что оставшаяся незаполненной часть таблицы вновь по структуре та же, что и исходная таблица, только в ней на одну строку меньше.

Слайд 7

Метод северо-западного угла
Наша таблица примет вид:

Слайд 8

Метод северо-западного угла
min(a1, b1)=b1, то есть b1

первого склада в первый пункт потребления в объеме b1, мы полностью удовлетворим его потребности. Перевозить туда больше будет ничего не надо, поэтому остальные перевозки туда будут равны нулю.
Ну, а в первом складе еще останется a1-b1 запасов продукта. Обратите внимание на то, что оставшаяся незаполненной часть таблицы вновь по структуре та же, что и исходная таблица, только в ней на один столбец меньше.
Ну, а дальше все можно повторить, продолжая заполнять оставшуюся часть таблицы перевозок начиная с левого верхнего, "северо-западного" угла, пока не будут исчерпаны запасы всех складов и не удовлетворены потребности всех пунктов потребления.

Слайд 9

Метод северо-западного угла
Наша таблица примет вид:

Слайд 10

Метод северо-западного угла
У нас всего в таблице m строк и n

столбцов. Каждый раз исчезает, как минимум, либо строка, либо столбец (могут исчезнуть сразу и строка, и столбец, если запасы какого-то подмножества складов полностью удовлетворят потребности какого-то подмножества пунктов потребления). Однако при последней перевозке исчезает сразу и последняя строка, и последний столбец. Поэтому получающийся план перевозок содержит не более m+n-1 компонент.
Мы не будем доказывать, что план, полученный методом северо-западного угла, является опорным. Заметим лишь, что если получающийся план содержит ровно m+n-1 компоненту, то он называется невырожденным. Если число положительных компонент плана перевозок меньше, то он называется вырожденным.

Слайд 11

Метод северо-западного угла
Рассмотрим задачу.
Фирма должна отправить некоторое количество кроватей с

трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице.

Слайд 12

Решение
Построим опорный план для рассмотренной выше задачи. В начале построим его

с помощью метода "северно-западного угла"
Исходная транспортная таблица:

Слайд 13

Метод минимального (максимального) элемента
Суть метода заключается в том, что из

всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Слайд 14

Транспортная задача линейного программирования

Содержание

Постановка транспортной задачи Однородный груз, имеющийся в m пунктах отправления (производства)

Математическая модель транспортной задачи Будем называть любой план перевозок допустимым, если

Методы решения транспортных задачТак как транспортная задача является задачей линейного программирования,

Методы решения транспортных задачЗатем решение задачи разбивается на два этапа:Определение опорного

Метод северо-западного угла Начнем заполнение с клетки, расположенной вверху слева, то

Метод северо-западного углаНаша таблица примет вид:

Метод северо-западного углаmin(a1, b1)=b1, то есть b1

Метод северо-западного углаНаша таблица примет вид:

Метод северо-западного углаУ нас всего в таблице m строк и n

Метод северо-западного угла Рассмотрим задачу.Фирма должна отправить некоторое количество кроватей с

РешениеПостроим опорный план для рассмотренной выше задачи. В начале построим его

Метод минимального (максимального) элемента Суть метода заключается в том, что из

ЗаданиеСоставить первоначальный опорный план методом минимального элемента для транспортной задачи вида:

Похожие презентации

Постановка транспортной задачи
Однородный груз, имеющийся в m пунктах отправления (производства)

Математическая модель транспортной задачи
Будем называть любой план перевозок допустимым, если

Методы решения транспортных задач
Так как транспортная задача является задачей линейного программирования,

Методы решения транспортных задач
Затем решение задачи разбивается на два этапа:
Определение опорного

Метод северо-западного угла
Начнем заполнение с клетки, расположенной вверху слева, то

Метод северо-западного угла
Наша таблица примет вид:

Метод северо-западного угла
min(a1, b1)=b1, то есть b1

Метод северо-западного угла
Наша таблица примет вид:

Метод северо-западного угла
У нас всего в таблице m строк и n

Метод северо-западного угла
Рассмотрим задачу.
Фирма должна отправить некоторое количество кроватей с

Решение
Построим опорный план для рассмотренной выше задачи. В начале построим его

Метод минимального (максимального) элемента
Суть метода заключается в том, что из

Задание
Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида: