Построение оптимального плана перевозок для транспортной задачи

Для получения оптимального плана перевозок существует несколько методов. Один из них - распределительный

Вы уже знаете о суперспособностях современного учителя?

Тратить минимум сил на подготовку и проведение уроков.

Быстро и объективно проверять знания учащихся.

Сделать изучение нового материала максимально понятным.

Избавить себя от подбора заданий и их проверки после уроков.

Наладить дисциплину на своих уроках.

Получить возможность работать творчески.

=> ПОЛУЧИТЬ СУПЕРСПОСОБНОСТИ УЧИТЕЛЯ <=

Просмотр содержимого документа
«Построение оптимального плана перевозок для транспортной задачи»

Занятие 5. Создание оптимального плана перевозок.

Цель образования: Изучение распределительного метода для построения оптимального плана перевозок

Цель развития: Развитие логического мышления

Цель воспитания: Воспитание интереса к предмету, к экономическим процессам.

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

Распределительный метод.

Суть распределительного метода состоит в том, что ресурсы, назначенные потребителям по опорному плану, перераспределяются. Алгоритм перераспределения ресурсов:

1. Выбирается свободный (незаполненный) элемент опорного плана.

2. От выбранного свободного элемента строится кратчайший прямоугольный замкнутый контур. Остальные вершины замкнутого контура (кроме первой) проходят через заполненные элементы опорного плана перевозок. Поворот осуществляется только на 90⁰ и только в заполненных элементах.

3. Каждой вершине контура присваивается коэффициент, равный соответствующему значению элемента из матрицы стоимости.

4. Каждому коэффициенту в вершинах контура строго поочерёдно присваивается знак «+» или «-», начиная с пустой клетки.

5. Выполняется алгебраическое суммирование коэффициентов по всему контуру.

6. Пункты с 1 по 5 выполняются для каждого нулевого (пустого) элемента опорного плана.

7. Проверяются результаты суммирования по всем контурам на оптимальность.

8. Если план перевозок не оптимален, то выполняется перераспределение ресурсов и возвращаются к п. 1.

Если при решении транспортной задачи оптимальное решение должно быть минимальным, то алгебраические суммы по всем контурам должны быть положительными или равными нулю.

Если при решении задачи оптимальное решение должно быть максимальным, то алгебраические суммы по всем контурам должны быть отрицательными или равными нулю.

Если план перевозок не оптимален, то перераспределение ресурсов выполняется следующим способом:

Выбирается контур, для которого нарушено условие оптимальности. Если транспортная задача искалась на отыскание минимума затрат, то выбирается контур с отрицательным значением алгебраической суммы. Если таких контуров несколько, то выбирается тот, у которого большая по модулю отрицательная алгебраическая сумма.
В вершинах выбранного контура расставляются фактические перевозки с теми знаками, которые были указаны при вычислении коэффициентов. Рассматриваются только вершины с отрицательными значениями. Выбирается вершина с минимальным по модулю отрицательным значением. Значение этой вершины алгебраически вычитается из всех вершин контура.
Проверяется сохранение баланса по строкам и столбцам
Заново рассчитываются алгебраические суммы (по стоимости) для всех контуров.
Проверяется условие оптимальности

Построить оптимальный план перевозок