- •Э.О. Салминен, л.Э. Еремеева, т.С. Антонова, н.А. Тюрин, в.Н. Язов
- •Введение
- •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.Лабораторная работа. Прогнозирование
4.2. Общий алгоритм решения транспортной задачи
В настоящее время разработано несколько методов (алгоритмов) решения транспортной задачи линейного программирования. Одна группа этих методов основана на принципе последовательного улучшения плана, когда выбранный определенным образом первоначальный план при помощи расчетов улучшается до тех пор, пока не станет оптимальным.
Алгоритм заключается в том, что сначала, строится какой-либо первоначальный допустимый план, затем проверяется, является ли план оптимальным, если план оптимальный — задача решена, если не оптимальный— отыскивается другой, но обязательно улучшенный и вновь проверяется на оптимальность. Шаги 2 и 3 повторяются до тех пор, пока очередной улучшенный план не будет оптимальным.
Среди группы методов последовательного улучшения плана можно выделить распределительный метод линейного программирования. Сущность этого метода заключается в том, что на основании известных линейных зависимостей между отдельными факторами составляются матрицы и в результате применения специальных правил подбираются определенные сочетания факторов для получения оптимального решения.
4.3. Методы построения начального плана
Существует несколько методов построения начального плана, который иногда называют опорным решением. Наиболее распространенные из них: метод северо-западного угла, метод наименьшей стоимости, двойного предпочтения, по приоритету ближайших пунктов, способ Фогеля, способ Лебедева— Тихомирова и др. Рассмотрим простейшие из них.
Метод северо-западного угла, или диагональный, появился одним из первых. Название он получил потому, что распределение поставок (корреспонденции) начинается слева сверху (с северо-западного угла матрицы). Это формальный способ, приводящий к решению обычно далекому от оптимального, но зато простой и легко реализуемый на ЭВМ.
Решение удобно выполнять в табличной форме. Для этого составляется рабочая таблица в которой в строке слева указываются поставщики (А1, А2, ..., Аm) и их мощности, в верхней строке указываются потребители (В1, В2, ..., Вn) и их спрос. В клетках таблицы в верхних левых углах указываются единичные стоимости (С11С12 …….. Сmn), т. е. затраты на доставку единицы продукции от соответствующего поставщика Аi (i=1, 2, .... m) соответствующему потребителю Bj (j=1,2,..:,n).
Рассмотрим конкретный пример решения задачи. Три лесозаготовительных предприятия (А1, A2, А3) заготовляют пиловочник в объемах соответственно 300, 600 и 500 тыс. м3 в год и поставляют четырем деревообрабатывающим предприятиям (В1, В2, В3, В4). Годовой объем потребления пиловочника деревообрабатывающими предприятиями равен 450, 400, 200 и 350 тыс. м3. Стоимость доставки сырья от ЛЗП к деревообрабатывающим предприятиям представлена матрицей стоимостей, показанной в табл. 4.1. цифрами Сij в левых верхних углах клеток рабочей таблицы.
Таблица 4.1.
Исходные данные для решения транспортной задачи линейного программирования (рабочая таблица).
Поставщики и их мощности, тыс.куб. м. |
Потребители и их спрос, тыс.куб.м. | ||||
В1 |
В2 |
В3 |
В4 | ||
450 |
400 |
200 |
350 | ||
А1 |
300 |
6 |
8 |
7 |
10 |
А2 |
600 |
4 |
7 |
6 |
8 |
А3 |
500 |
9 |
8 |
5 |
12 |
Согласно методу северо-западного угла распределение поставок от поставщиков к потребителям начинается с клетки А1B1 Сравниваем мощность первого поставщика А1 (300) с потребностью потребителя B1 (450). Меньшую величину (300) помещаем в клетку А1B1 и вычитаем ее из обеих сравниваемых величин. В итоге в остатке первой строки проставляется 0, а в итоге первого столбца остаток 450—300=150 (табл.4.2.). Первую строку из дальнейшего рассмотрения исключаем. Поскольку остаток оказался в первом столбце, следующую поставку назначаем в соседнюю клетку А2B1. Сравнивая итоги второй строки (600) и первого столбца (остаток 150), устанавливаем величину поставки, равную 150. Вычтя эту поставку из сравниваемых величин, в итоге первого столбца проставляем 0, а в итоге второй строки записываем разницу 600—150 = 450. На третьей итерации, сравнивая потребность потребителя второго столбца B2=400 и остаток мощности второго поставщика А2 = 450, меньшее значение записываем в клетку А2B2. В остатке второго столбца остается 400—400 = 0, а второй строки 450—400 = 50, что и записываем в остаток по строке в результате третьей итерации. Продолжая этот процесс, распределяем поставки по всей таблице. Итог распределения поставок приведен в табл. 4.2.
Таблица 4.2.