Лесотранспортная логистика. Решение задач

На данном этапе мы можем осуществить только 4 нулевых назначения, тогда как требуемое их количество равно 5. Полученное распределение является недопустимым. Переходим к этапу 3.

Этап 3. Проводим наименьшее число прямых, проходящих через все нули таблицы.

5 0* 3 2 1

4 1 5 6 0*

4 6 5 6 0΄

0* 3 1 0΄ 2

Наименьшим элементом, через который не проходит ни одна из прямых, является число 2. Скорректируем таблицу так, как это описано выше в соответствии с этапом 3, т.е. вычтем 2 из каждого элемента, через который не проходит ни одна прямая, и добавим 2 ко всем элементам, лежащим на пересечении трех прямых, оставив без изменения все прочие элементы, через которые проходит только одна прямая. Теперь получим:

Переходим к этапу 2 и повторяем все пункты 1-6. Получаем, опять 4 нулевых назначения, значит необходимо, повторить все операции третьего этапа

Выполнив пункты 1-6, второго этапа в конечном итоге получим:

Теперь требование о размещении пяти назначений в клетки с нулевым расстоянием выполняется, следовательно, полученное решение является оптимальным. Перевозки осуществляются от базы 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).

5.4. Решение транспортной задачи венгерским методом на ЭВМ.

Для решения данной задачи используем программу Excel. Создаем в Excel две матрицы рис. 5.1. В первой таблице введены исходные данные, а также формула для определения суммарной эффективности. Во второй таблице создаем матрицу результатов решения и ограничений решения транспортной задачи.

Рис. 5.1. Исходные матрицы для решения транспортной задачи.

Для решения транспортной задачи венгерским методом в таблице результатов решения задаются проверки ограничений:

3.Определяются суммы по строкам (СУММ С17:G17).

4.Определяются суммы по столбцам (СУММ С17:С21).

Для решения транспортной задачи в Microsoft Excel воспользуемся функцией «Поиск решений». В меню «Сервис», переходим в пункт «Надстройки», в доступных надстройках выбираем «Поиск решения».

При выполнении функции «Поиск решения» необходимо установить целевую ячейку.

Целевая ячейка для примера 1 будет равна максимальному значению, а для примера 2 -минимальному значению. Целевая ячейка задается в ячейке, где определяется суммарная эффективность решения задачи. Далее, указываем диапазон ячеек, где подбирается возможный вариант решений ($C$176: $G$21). Задаем ограничения, согласно условиям транспортной задачи

(рис.5.2.).

Рис. 5.2. Поиск решения транспортной задачи для примера 1.

Выполнив функцию «Поиск решения», получаем оптимальное решение транспортной задачи венгерским методом. Рисунок 5.3. - для примера 1 (определение максимальной суммарной эффективности), а рисунок 5.4. – для примера 2 (определение минимальной суммарной эффективности).

Рис. 5.3. Результаты решения транспортной задачи (пример 1).

Рис. 5.4. Результаты решения транспортной задачи (пример 2).

5.5. Варианты заданий.

Задача: Имеются 5 лесопунктов и 5 комплектов лесозаготовительного оборудования (5 технологических линий). Каждая технологическая линия может дать производительность С(ij).

Выполнить: Распределить технологические линии по лесопунктам, чтобы общая производительность была максимальной или минимальной.

5.Сформулировать задачу. Привести математическую постановку задачи.

6.Решить задачу с краткими пояснениями.

7.Решить задачу на ЭВМ.

8.Сделать выводы по полученному результату.

Задание выбирается по последней и предпоследней цифре зачетной книжки. Исходные данные берутся в таблице по последнему номеру зачетной книжки (таблица 5.1). Если предпоследняя цифра зачетной книжки четнаято производительность должна быть максимальной, если -нечетная, то производительность должна быть минимальной.

Таблица 5.1.

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

6. ЛАБОРАТОРНАЯ РАБОТА. ОПРЕДЕЛЕНИЕ МЕСТОРАСПОЛОЖЕНИЯ ДЕРЕВООБРАБАТЫВАЮЩЕГО ПРЕДПРИЯТИЯ

Цель работы. Освоить решение задач по оптимальному размещению производительных сил.

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

6.1. Определение месторасположения предприятия.

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

Для этого используется метод наложения сетки координат на карту потенциальных мест расположения складов. Система сетки дает возможность оценить стоимость доставки от каждого поставщика до предполагаемого склада и от склада до конечного потребителя, а выбор останавливается на варианте, который определяется как центр массы, или центр равновесной системы транспортных затрат: