- •Тезисы лекций Содержание
- •Лекция 1
- •2) Математическое моделирование.
- •3) Автоматизация проектирования. Понятие сапр,
- •Лекция 2
- •2) Особенности проектирования с/х производства.
- •Лекция 3
- •2) Построение упорядоченного (оптимизированного) сетево-
- •2) Временные параметры сг.
- •Лекция 4
- •Лекция 5
- •2) Контрольный пример.
- •Лекция 6
- •2) Методы решения тз.
- •Лекция 7
- •2) Решение контрольного примера.
- •Лекция 8
- •2) Аппроксимация Фогеля.
- •3) Метод двойного предпочтения.
- •Лекция 9
- •2) Интерфейс программы «компас».
- •Лекция 10
- •2) Постановка размеров.
- •Секущая рамка
- •Секущая ломанная
- •Удаление объектов
- •Лекция 11
- •2) Ломанные, штриховка.
- •3) Симметрия.
- •Лекция 12
- •2) Заполнение основной надписи чертежа.
- •Лекция 13
- •2) Особенности при печати.
- •Вывод документа на печать
- •Лекция 14
- •2) Пример создания деталировки.
- •Лекция 15
- •2) Пример создания сборки.
- •3) Тонкие настройки системы.
- •Создание копии документа
- •Литература: 1, 1-15
Лекция 8
Тема: Другие методы построения опорного плана.
Цель: Ознакомиться с другими методами построения опорных
планов.
План: 1) Метод минимального элемента
2) Аппроксимация Фогеля.
3) Метод двойного предпочтения.
Метод минимального элемента
Суть метода – из всех тарифов перевозок сij выбирают минимальный и в эту клетку помещают наименьшее значение Аi или Вj. Затем из рассмотрения исключают строку (столбец), где запасы (потребности) израсходованы, или строку (столбец) если запасы поставщика удовлетворили потребности потребителя. Из оставшейся части таблицы снова выбирают клетку с минимальным сij и процесс распределения запасов продолжается до тех пор, пока все запасы не будут распределены, а все потребности не будут удовлетворены.
Например:
Таблица 4 – Пример распределения методом
минимального элемента
-
потреб. полей, тонн
120
50
190
110
запасы складов, тонн
160
160
7
8
1
2
140
120
20
4
5
9
8
170
30
30
110
9
2
3
6
Аппроксимация Фогеля.
Суть метода – при каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специальные графы таблицы. Среди указанных разностей выбирают минимальную. В строке (столбце), которой данная разность соответствует определяют минимальный тариф. Клетку, которой соответствует этот тариф заполняют на данной итерации. Если минимальный тариф одинаков для нескольких клеток дпнной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в строке (столбце) соответствующей наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце.
Способ двойного предпочтения.
Применяется при больших таблицах, когда перебор всех элементов затруднен.
Суть метода – в каждом столбце помечают знаком V клетку с наименьшим тарифом. Затем тоже самое проделывают с каждой строкой. В результате некоторые клетки оказываются помеченными дважды VV.
В них находится минимальный тариф как по строке, так и по столбцу. В эти клетки (VV) помещают максимальный возможный объемы перевозок (исключая из дальнейшего рассмотрения соответствующие строки и столбцы).
Затем в оставшейся части таблицы производят распределение грузов по клетка помеченным одним знаком V.
Далее, среди непомеченных клеток, распределение производят просто по наименьшей стоимости тарифа.
Как видно из всего сказанного, каждый план имеет свои преимущества и недостатки, которые учитываются при каждом конкретном случае выбора.
В современных условия, конечно, все описанные алгоритмы легли в основу различных оптимизационных программ, работая с которыми конкретный пользователь подчас и не догадывается, что решение идет по алгоритму транспортной задачи, или что здесь применяется метод двойного предпочтения и т.д.
Литература: 2, 35-39 с.
Контрольные вопросы:
Какие методы оптимизации опорных планов вы узнали?
Какой из них предпочтительнее на Ваш взгляд?
Какой самый сложный?