Мат постановка и решение ТЗ в открытой форме
Если условие (3) задано в виде неравенства (>), то ТЗ называется открытой.
Откр. задачи часто исп-тся на практике для решения задач перспективного планирования: оптимизация развития предприятий, фирм, корпораций, отраслей. Реш.этих задач практически ничем не отличается от закрытых. При оптимизации перевозок по методам последовательного сокращения невязок, в последнем оптимальном и допустимом плане перевозок, имеем сумму небалансов больше нуля, поскольку ресурсы больше потребностей. Для методов
последовательного улучшения планов (метод потенциалов, МОДИ) существует другой подход. Обозначим соответствующую разность как bj,n+1 и введем ее в условие задачи как фиктивный пункт сбыта. Очевидное обобщение приведенной модели включает рассмотрение и транспортной сети, допускающей существование промежуточных транспортных узлов; при этом, прежде чем попасть на конечную станцию назначения, товары могут транзитом следовать через другие
узлы (станции отправления – источники) или пункты сбыта. Сформулированная при этих условиях задача называется сетевой транспортной задачей. В ней особенно просто можно учитывать ограничения на пропускную способность.
16. решение задачи о назначении. Пусть i -номер исполнителя работы, j - номер исполняемой работы,xij- переменная, означающая возможность прикрепления работы к исполнителю. Если работа прикреплена значение переменной равно 1, в противном случае оно равно нулю. Построенный план должен удовлетворять условиям постановки транспортной задачи: Zxij=1, i=1,2,3......m (1) Zxij=1 j=1,2,3......n (2) xij=0,1
Целевая функция задачи состоит в том, чтобы найти максимум эффекта от деятельности исполнителей.
Шаг 1,2. В каждом столбце (строке) матрицы производительности отыскивается наибольшее значение показателя, из которого вычитаются все остальные .Шаг 3. Выделение независимых нулей (элементов 0*) - единственных в строке и столбце одновременно. Шаг 4. Проверка: получен ли оптимальный план. количество нулей равно размерности матрицы задачи. Нет - переход к шагу 5.Шаг 5. Метка столбцов. Каждый столбец, имеющий 0* закрывается и получает метку "+" вверху.Шаг 6. Поиск невыделенных нулей. Если в открытом столбце имеется невыделенный нуль, он получает метку - 0'. Если строка, содержащая 0' не имеет 0* - переход к шагу 8. Иначе, строка закрывается справа меткой "+" и открывается столбец, содержащий 0*, и так далее до окончания просмотра всей матрицы и выделения нулей 0' , переход к шагу 7. Шаг7. Из совокупности элементов матрицы, состоящих на пересечении открытых столбцов и строк, находится минимальное значение. Эта величина вычитается из элементов указанной совокупности, и добавляется к элементам, стоящим на пересечении закрытых столбцов и строк. Значения остальных элементов матрицы сохраняются. Все метки строк 0', 0* переносятся из предыдущей таблицы в данную, переход к шагу 6 .Шаг 8. Формирование цепочки типа: 0'-0*-0' . Все элементы 0' данной цепочки заменяются на элементы вида 0*, Также убираются все метки строк и столбцов и метки 0'. Переход к шагу 4.
Решение многоэтапной ТЗ.
В России она известна как задача с фиктивной диагональю. Постановка ее была предложена В.Машем, в США - Орденом. Потребность в ней возникает при одновременном решении взаимосвязанных транспортных задач. При решении каждой из них независимо друг от друга сумма целевых функций оптимальных планов обычно больше, чем если такую задачу решать, включив все ограничения вместе.
Необходимо составить оптимальный план перевозок продуктов, производимых на трех предприятиях. В процессе обращения продукты вначале попадают на оптовые базы, потом в магазины и затем, доставляются потребителям.
Потребность в ней возникает при одновременном решении взаимосвязанных транспортных задач. При решении каждой из них независимо друг от друга сумма целевых функций оптимальных планов обычно больше, чем если такую задачу решать, включив все ограничения вместе. Решение многоэтапной ТЗ выполняется также как и обычной. ее можно решать любым методом, например. потенциалов. Форма ее представления - с нулевой диагональю для указанных выше условий представлена. Числа М обозначают запрещение транспортировки в соответствующих клетках.
Шаг1. Построение допустимого плана Шаг2. Построение потенциалов. Шаг3. Проверка плана на оптимальность (Vj -Ui <= cij)
Шаг4. Корректировка базисного плана Анализ оптимального плана