Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Исследование операций Пример решения транспортной задачи (закрытая модель)
Содержание
- 1. Исследование операций Пример решения транспортной задачи (закрытая модель)
- 2. ЗадачаСоставить оптимальный план перевозок груза из трех
- 3. Рассмотрим методы построения опорных планов (опорного решения) ТЗ
- 4. Метод северо-западного углаЗаполняют клетку A1B1, (левый верхний
- 5. Решение задачи методом северо-западного угла102181шаг122 шаг153 шаг334 шаг95 шаг156 шагХХХХХХ121533915
- 6. Опорное решение задачи
- 7. Метод аппроксимации Фогеля1. На каждом шаге находят
- 8. Решение задачи методом аппроксимации Фогеля102ХХХХХХ156 шаг152 шаг273 шаг214 шаг181 шаг65 шаг51122136В21115В452В21ВВВВ111312
- 9. Опорное решение задачи
- 10. Метод минимальной стоимости для нахождения опорного планаПредполагает
- 11. Решение задачи методом наименьшей стоимости102153 шаг124 шаг366 шаг65 шагХХХХХ182 шаг151 шагХ156123636
- 12. Опорное решение задачи
- 13. Метод потенциаловбазируется на следующей теореме (признак оптимальности
- 14. Проверим план, полученный с помощью метода наименьшей
- 15. Составим систему уравнений для заполненных ячеек:u1 +
- 16. Проверим второе условие теоремы для незаполненных ячеекu1
- 17. осуществляется с помощью циклического сдвигаПерераспределение грузовЦикл -
- 18. Построим цикл:Построение циклаu1 + v3 = 12
- 19. В свободную клетку помещаем груз величиной ,
- 20. Составим систему уравнений для заполненных ячеек:u1 +
- 21. Проверим второе условие теоремы для незаполненных ячеекu1
- 22. Оптимальное решение:Zmin=15*11+15*5+27*8+21*13+18*6+6*12=909
- 23. Используемая литература:Борзунова Т.Л., Барыкин М.П. , Данилов
- 24. Скачать презентанцию
ЗадачаСоставить оптимальный план перевозок груза из трех пунктов отправления с запасами 30, 48, 24 т в четыре пункта назначения с потребностями 18, 27, 42, 15 т. Тарифы перевозок сij (в ден/ед.)
Слайды и текст этой презентации
Слайд 4Метод северо-западного угла
Заполняют клетку A1B1, (левый верхний угол), поставив в
него min(a1b1). Если min совпадает с A1, то запасы пункта
A1 считают исчерпанными и переходят к удовлетворению потребностей b1 начиная с ячейки А2В1.Затем переходят к заполнению клетки А2В2. Перемещаясь так по диагонали, доходят до последней клетки АmВn. При этом все грузы будут исчерпаны, и потребности пунктов удовлетворены.
Замечание: если на некотором шаге исчерпаны запасы, то переходим к удовлетворению потребностей как это было описано выше. Если же были удовлетворены потребности, то приступают к исчерпыванию запасов аналогичным способом.
Слайд 5Решение задачи методом
северо-западного угла
102
18
1шаг
12
2 шаг
15
3 шаг
33
4 шаг
9
5 шаг
15
6 шаг
Х
Х
Х
Х
Х
Х
12
15
33
9
15
Слайд 7Метод аппроксимации Фогеля
1. На каждом шаге находят разности между двумя
наименьшими тарифами (даже если они одинаковые) во всех строках и
столбцах, записывая их в дополнительные столбец и строку таблицы;2. Из найденных разностей выбирают максимальную и заполняют клетку, которой соответствует данная разность.
Процесс продолжается до тех пор, пока все грузы не будут развезены по потребителям.
Слайд 8Решение задачи методом аппроксимации Фогеля
102
Х
Х
Х
Х
Х
Х
15
6 шаг
15
2 шаг
27
3 шаг
21
4 шаг
18
1 шаг
6
5
шаг
5
1
1
2
2
1
3
6
В
2
1
1
15
В
4
5
2
В
21
В
В
В
В
11
13
12
Слайд 10Метод минимальной стоимости для нахождения опорного плана
Предполагает заполнение на каждом
шаге клеток с минимальным тарифом, что даст, очевидно, меньшие суммарные
затраты на перевозку груза.
Слайд 11Решение задачи методом наименьшей стоимости
102
15
3 шаг
12
4 шаг
36
6 шаг
6
5 шаг
Х
Х
Х
Х
Х
18
2 шаг
15
1
шаг
Х
15
6
12
36
36
Слайд 13Метод потенциалов
базируется на следующей теореме
(признак оптимальности решения):
Для заполненных ячеек таблицы
должно выполняться условие:
Для незаполненных ячеек условие:
(причем количество заполненных ячеек в
опорном плане должно быть равно n+m-1, где m – число поставщиков, n – число потребителей)
Слайд 14Проверим план, полученный с помощью метода наименьшей стоимости, на оптимальность
n+m-1=4+3-1=6
Должно
быть заполнено 6 ячеек.
Реально заполненных ячеек тоже 6.
Слайд 15Составим систему уравнений
для заполненных ячеек:
u1 + v2 = 7
u1 +
v4 = 5
u2 + v2 = 8
u2 + v3 =
13u3 + v1 = 6
u3 + v3 = 12
Полагая u1 = 0, найдем:
Так как v2 = 7, то
v2 = 7
v4 = 5
u2 = 1
Так как u2 = 1, то
v3 = 12
Так как v3 = 12, то
u3 = 0
Так как u3 = 0, то
v1 = 6
Итак, u1 = 0, u2 = 1, u3 = 0, v1 = 6, v2 = 7, v3 = 12, v4 = 5
Слайд 16Проверим второе условие теоремы
для незаполненных ячеек
u1 + v1 = 6
≤ C11 = 13 +
План X1 не оптимальный, поэтому
необходимо перераспределение грузовu1 = 0, u2 = 1, u3 = 0,
v1 = 6, v2 = 7, v3 = 12, v4 = 5
u1 + v3 = 12 > C13 = 11 (1)
u2 + v1 = 7 ≤ C21 = 11 +
u2 + v4 = 6 ≤ C24 = 7 +
u3 + v2 = 7 ≤ C32 = 10 +
u3 + v4 = 5 ≤ C34 = 9 +
Слайд 17осуществляется с помощью циклического сдвига
Перераспределение грузов
Цикл - ломанная, вершины которой
находятся в заполненных ячейках, кроме одной. Это одна вершина должна
находиться в незаполненной ячейке, для которой ui + vj > Cij.При этом звенья ломанной должны удовлетворять следующим условиям:
Параллельность строкам и столбцам
В каждой строке и каждом столбце не более двух вершин
Слайд 18Построим цикл:
Построение цикла
u1 + v3 = 12 > C13 =
11
Всем вершинам ломанной припишем + или –,
начиная с проблемной ячейки:
Слайд 19В свободную клетку помещаем груз величиной , равной минимальному значению
из всех чисел в отрицательных клетках цикла.
Циклический сдвиг
Min (15,36)=15
Новый план:
Сдвиг
по циклу: Во все положительные клетки прибавляем , из отрицательных – вычитаем .Проверим новый план на оптимальность
Слайд 20Составим систему уравнений
для заполненных ячеек:
u1 + v3 = 11
u1 +
v4 = 5
u2 + v2 = 8
u2 + v3 =
13u3 + v1 = 6
u3 + v3 = 12
Полагая u1 = 0, найдем:
Так как v3 = 11, то
v3 = 11
v4 = 5
u2 = 2
Так как u2 = 2, то
v2 = 6
Так как v3 = 11, то
u3 = 1
Так как u3 = 1, то
v1 = 5
Итак, u1 = 0, u2 = 2, u3 = 1, v1 = 5, v2 = 6, v3 = 11, v4 = 5
Слайд 21Проверим второе условие теоремы
для незаполненных ячеек
u1 + v1 = 5
≤ C11 = 13 +
План X2 оптимальный
u1 = 0,
u2 = 2, u3 = 1,v1 = 5, v2 = 6, v3 = 11, v4 = 5
u1 + v2 = 6 ≤ C12 = 7 +
u2 + v1 = 7 ≤ C21 = 11 +
u2 + v4 = 7 ≤ C24 = 7 +
u3 + v2 = 7 ≤ C32 = 10 +
u3 + v4 = 6 ≤ C34 = 9 +
Слайд 23Используемая литература:
Борзунова Т.Л., Барыкин М.П. , Данилов Е.А. Соловьева О.Ю.
- Математическое моделирование: учебное пособие/ВолгГТУ, - Волгоград, 2008.
Конюховский П.В. Математические
методы исследования операций в экономике – СПб: Питер, 2000. 
