- •Э.О. Салминен, л.Э. Еремеева, т.С. Антонова, н.А. Тюрин, в.Н. Язов
- •Введение
- •1. Расчетно - графическая работа логистический анализ
- •Изменение структуры водного транспорта леса
- •Изменение объемов плотового сплава
- •Расчет параметров для системы нормальных уравнений
- •Вычисление значений yx
- •2. Лабораторная работа. Прогнозирование развития материалопотока лесопромышленного предприятия
- •2.1. Методы прогнозирования
- •2.2. Пример прогнозирования развития материального потока.
- •2.2.1. Прогнозирование развития методом наименьших квадратов.
- •Данные зависимости спроса от времени по методу наименьших квадратов с учетом погрешности с вероятностями 0,95 и 0,98.
- •2.2.2. Применение метода Чебышева для прогнозирования спроса.
- •Варианты заданий.
- •3. Лабораторная работа прогноз развития транспортных средств лесопромышленного предприятия
- •3.1. Прогнозирование развития транспортных средств леспромхоза.
- •3.2. Пример прогнозирования развития транспортных средств лесопромышленного предприятия.
- •3.3. Варианты заданий.
- •4. Лабораторная работа формирование оптимальных грузопотоков в лесопромышленном комплексе
- •Транспортная задача линейного программирования
- •4.1. Общая постановка транспортной задачи.
- •4.2. Общий алгоритм решения транспортной задачи
- •4.3. Методы построения начального плана
- •Исходные данные для решения транспортной задачи линейного программирования (рабочая таблица).
- •Построение опорного плана методом северо-западного угла.
- •Построение опорного плана по методу минимального элемента.
- •4.5. Проверка решения на оптимальность
- •4.6. Переход от неоптимального решения к лучшему.
- •Результат решения после первой итерации.
- •Результат решения после второй итерации.
- •Альтернативное решение.
- •4.7. Решение транспортной задачи на эвм.
- •4.8. Варианты заданий.
- •Исходные данные для решения транспортной задачи.
- •Исходные данные для решения транспортной задачи.
- •5. Лабораторная работа оптимальное распределение технологического оборудования лесопромышленных предприятий
- •5.1. Описание алгоритма венгерского метода.
- •5.2. Пример решения транспортной задачи венгерским методом.
- •5.3. Алгоритм венгерского метода при определении минимальных
- •5.4. Решение транспортной задачи венгерским методом на эвм.
- •5.5. Варианты заданий.
- •Исходные данные для решения транспортной задачи венгерским методом.
- •6. Лабораторная работа. Определение месторасположения деревообрабатывающего предприятия
- •6.1. Определение месторасположения предприятия.
- •6.2. Пример определение месторасположения деревообрабатывающего предприятия
- •6.3. Варианты заданий:
- •Исходные данные для решения задачи.
- •Исходные данные для решения задачи.
- •7. Лабораторная работа. Микрологистическая система планирования mpr-1
- •7.1. Планирование потребности в материалах.
- •7.2. Разработка микрологистической системы планирования производства mrp I.
- •Исходные данные для решения задачи.
- •Пример решения mrp I.
- •7.3. Варианты заданий:
- •Исходные данные для решения задачи.
- •8. Лабораторная работа. Определение границ рынка лесопродукции
- •8.1. Определение границ рынка.
- •8.2. Пример определение границ рынка.
- •8.3. Варианты заданий:
- •Исходные данные для решения задачи.
- •Лабораторная работа. Управление запасами на складе лесопродукции
- •9.1. Управление запасами на складе лесопродукции
- •9.2. Пример управления запасами на складе.
- •9.3. Варианты заданий:
- •Исходные данные для решения задачи.
- •Содержание
- •2.Лабораторная работа. Прогнозирование
5.3. Алгоритм венгерского метода при определении минимальных
суммарных затрат.
Транспортная модель - это частный случай модели линейного программирования. Стандартная задача включает в себя некоторое множество пунктов производства, например, несколько лесозаготовительных предприятий, которые осуществляют поставки в некоторое множество пунктов назначения, например, в несколько деревоперерабатывающих предприятий. Цель состоит в минимизации общей стоимости транспортировки в рамках ограничений на спрос и предложение. Решение этой задачи может быть найдено с помощью традиционных методов линейного программирования. Относительно простая структура задачи позволяет, однако, разработать специальные алгоритмы, применение которых оказывается более трудоемким, чем применение обычных методов решения задач линейного программирования со множеством переменных. Для решения этой модифицированной транспортной задачи был разработан Венгерский метод.
Алгоритм венгерского метода состоит из 3 этапов:
Этап 1:
1. Формализация проблемы в виде транспортной таблицы по аналогии с решением транспортной задачи.
2. В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки.
3. Повторить ту же самую процедуру для столбцов.
Теперь в каждой строке и в каждом столбце таблицы есть по крайней мере один нулевой элемент. Представленная в полученной с помощью описанного выше приема "приведенной" транспортной таблице задача о назначениях эквивалентна исходной задаче, и оптимальное решение для обеих задач будет одним и тем же. Сущность Венгерского метода заключается в продолжении процесса приведения матрицы до тех пор, пока все подлежащие распределению единицы не попадут в клетки с нулевой стоимостью. Это означает, что итоговое значение приведенной целевой функции будет равно нулю. Так как существует ограничение на неотрицательность переменных, нулевое значение целевой функции является оптимальным.
Этап 2.
Если некоторое решение является допустимым, то каждой строке и каждому столбцу соответствует только один элемент. Если процесс распределения элементов осуществляется только в клетки с нулевой стоимостью, он приведет к получению минимального значения целевой функции.
1. Найти строку, содержащую только одно нулевое значение стоимости, и в клетку, соответствующую данному значению, поместить один элемент. Если такие строки отсутствуют, допустимо начать с любого нулевого значения стоимости.
2. Зачеркнуть оставшиеся нулевые значения данного столбца.
3. Пункты 1 и 2 повторять до тех пор, пока продолжение описанной процедуры окажется невозможным.
Если на данном этапе окажется, что есть несколько нулей, которым не соответствуют назначения и которые являются не зачеркнутыми, то необходимо:
4. Найти столбец, содержащий только одно нулевое значение, и в соответствующую клетку поместить один элемент.
5. Зачеркнуть оставшиеся нули в данной строке.
6. Повторять пункты 4 и 5 до тех пор, пока дальнейшая их реализация окажется невозможной.
Если окажется, что таблица содержит неучтенные нули, повторить операции 1-6. Если решение является допустимым, т.е. все элементы распределены в клетки, которым соответствует нулевая стоимость, то полученное решение одновременно является оптимальным. Если решение является недопустимым, осуществляется переход к этапу 3.
Этап 3.
1. Провести минимальное число прямых через строки и столбцы матрицы (но не по диагоналям) таким образом, чтобы они проходили через все нули, содержащиеся в таблице.
2. Найти наименьший среди элементов, через которые не проходит ни одна из проведенных прямых.
3. Вычесть его из всех элементов, через которые не проходят прямые.
4. Прибавить найденный элемент ко всем элементам таблицы, которые лежат на пересечении проведенных ранее прямых
5. Все элементы матрицы, через которые проходит только одна прямая, оставить без изменения.
В результате применения данной процедуры в таблице появляется по крайней мере один новый ноль. Необходимо возвратиться к этапу 2 и повторять алгоритм до тех пор, пока не будет получено оптимальное решение.
Пример 2:
Некоторое предприятие имеет 5 лесосырьевых складов и 5 потребителей лесопродукции, заказы которых необходимо выполнить. В таблице содержится расстояния между лесосырьевыми складами и потребителями. Как распределить заказы потребителям, чтобы общая дальность транспортировки была минимальной.
-
7
2
5
4
3
6
3
7
8
2
5
7
6
7
1
8
5
3
6
4
3
6
4
3
5
Этап 1 Венгерского метода: В каждой строке находится наименьший элемент.
-
Н.Э.строки
7
2
5
4
3
2
6
3
7
8
2
2
5
7
6
7
1
1
8
5
3
6
4
3
3
6
4
3
5
3
Наименьший элемент вычитается из всех элементов соответствующей строки
-
5
0
3
2
1
4
1
5
6
0
4
6
5
6
0
5
2
0
3
1
0
3
1
0
2
0
0
0
0
0
Н.Э. столбца
Найденный наименьший элемент вычитается из всех элементов соответствующего столбца.
-
5
0
3
2
1
4
1
5
6
0
4
6
5
6
0
5
2
0
3
1
0
3
1
0
2
Этап 2. В соответствии с процедурой, описанной в этапе 2, осуществляются назначения. Наличие назначения обозначается через 0*
-
5
0*
3
2
1
4
1
5
6
0*
4
6
5
6
0΄
5
2
0*
3
1
0*
3
1
0΄
2
1.Находим строку, содержащее только одно нулевое значение, и в клетку соответствующую данному значению, помещаем один элемент (строка 1, столбец 2). Если такие строки отсутствуют, то допустимо начать с любого значения нулевой стоимости.
2. Затем отметить штрихом оставшиеся нулевые значения данного столбца.
3. Пункты 1 и 2 продолжаем до тех пор, пока продолжение описанной процедуры окажется невозможным.
После выполнения пунктов 1-3 оказалось, что есть несколько нулей, которым не соответствуют назначения и которые не отмечены штрихом. Следовательно, выполняем следующие операции:
4. Находим столбец, содержащий только одно нулевое значение, и в соответствующую клетку помещаем один элемент (столбец 1, строка 5).
5. Отмечаем штрихом оставшиеся нули в данной строке (столбец 4, строка 5). Повторяем пункты 4-5 до тех пор, пока не останется неучтенных нулей.
На данном этапе мы можем осуществить только 4 нулевых назначения, тогда как требуемое их количество равно 5. Полученное распределение является недопустимым. Переходим к этапу 3.
Этап 3. Проводим наименьшее число прямых, проходящих через все нули таблицы.
-
5
0*
3
2
1
4
1
5
6
0*
4
6
5
6
0΄
5
2
0*
3
1
0*
3
1
0΄
2
Наименьшим элементом, через который не проходит ни одна из прямых, является число 2. Скорректируем таблицу так, как это описано выше в соответствии с этапом 3, т.е. вычтем 2 из каждого элемента, через который не проходит ни одна прямая, и добавим 2 ко всем элементам, лежащим на пересечении трех прямых, оставив без изменения все прочие элементы, через которые проходит только одна прямая. Теперь получим:
-
3
0*
3
0′
1
2
1
5
4
0*
2
6
5
4
0′
3
2
0*
1
1
0*
5
3
0′
4
Переходим к этапу 2 и повторяем все пункты 1-6. Получаем, опять 4 нулевых назначения, значит необходимо, повторить все операции третьего этапа
-
3
0*
3
0′
1
2
1
5
4
0*
2
6
5
4
0′
3
2
0*
1
1
0*
5
3
0′
4
Выполнив пункты 1-6, второго этапа в конечном итоге получим:
-
3
0′
3
0*
2
1
0*
4
3
0′
1
5
4
3
0*
3
2
0*
1
2
0*
5
3
0′
5
Теперь требование о размещении пяти назначений в клетки с нулевым расстоянием выполняется, следовательно, полученное решение является оптимальным. Перевозки осуществляются от базы 5 к потребителю 1, от базы 2 к потребителю 2, с базы 4 к потребителю 3, с базы 1 — к потребителю 4 и с базы 3 — к потребителю 5. Хотя данное решение и является оптимальным, однако оно не единственное.
Суммарная эффективность будет равняться 3+3+3+4+1=14
Примечание: в задачах большей размерности, чем задача из примера убедиться в том, что проведенное в соответствии с пунктом 1 этапа 3 число прямых является минимальным, гораздо труднее. В этой связи может оказаться полезным так называемое "правило правой руки":
1. Выбирается любая строка или столбец, содержащие только один нулевой элемент.
2. Если выбрана строка, прямая проводится через столбец, в котором находился данный нулевой элемент.
3. Если выбран столбец, прямая проводится через строку, содержащую данный нулевой элемент.
4. Пункты 1-3 повторяются до тех пор, пока не будут учтены все входящие в таблицу нули.
Алгоритм решения задачи о назначениях предполагает минимизацию ее целевой функции. Если имеется задача о назначениях, целевую функцию которой нужно максимизировать, то поступают таким же образом, как и в алгоритме решения транспортной задачи: после окончания формирования первой таблицы все ее элементы умножаются на (-1).