Цикл. Перестановка по циклу.

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

В таблице выбираем свободную клетку с максимальной положительной оценкой и формируем цикл, одной из вершин которого является выбранная клетка, а остальные клетки занятые. Кроме того, сопоставим каждой вершине цикла знак и перевозку, при этом свободной клетке сопоставляем знак «+», а для остальных клеток знаки чередуются. Дальше делаем перестановку по циклу, а именно: из всех вершин, отмеченных минусом, вычтем минимум из всех перевозок, означенных этим знаком, т.е вычитаем Δ, а ко всем вершинам с «+» прибавим Δ. Таким образом с помощью цикла получаем новый опорный план.

10. Yandex.RTB R-A-252273-3
    Содержание

    • Постановка транспортной задачи (тз)
    • Открытая и закрытая модели.
    • Методы построения опорного плана – метод минимального тарифа.
    • Метод Фогеля.
    • Занятые и свободные клетки.
    • Вырожденные и невырожденные планы.
    • Метод потенциалов решения тз.
    • Оценки опорного плана. Условия оптимальности опорного плана.
    • Цикл. Перестановка по циклу.
    • Открытая модель тз. Сведения открытой модели к закрытой.
    • Фиктивные потребитель и поставщик.
    • Дополнительные ограничения в транспортной задаче.
    • Постановка задачи многокритериальной оптимизации.
    • Доминирование и оптимальность по Парето. Эффективные решения и Парето –оптимальная (Парето –эффективная ) граница.
    • Метод построения Парето-оптимальной границы.
    • Методы решения задач многокритериальной оптимизации – метод приоритетов.
    • Методы решения задач многокритериальной оптимизации – метод обобщенного критерия (метод свертки).
    • Методы решения задач многокритериальной оптимизации – метод идеальной точки.
    • Основные понятия в игровых моделях: стратегии, матрица выигрышей.
    • Принцип максимина и минимакса, верхняя и нижняя цена игры, седловая точка, оптимальные стратегии, цена игры.
    • Доминируемые стратегии.
    • Решение игр в смешанных стратегиях.
    • Графическое решение игр вида 2n и m2.
    • Метод динамического программирования. Принцип оптимальности и уравнение Беллмана.
    • Задача о распределении средств между предприятиями. Непрерывный случай.
    • Задача о распределении средств между предприятиями. Дискретный случай.

    Yandex.RTB R-A-252273-4