Математ постановка ТЗ. Открытая и закрытая модели
Клас-ция моделей и методов мат модел.
Линейное программирование: общая задача ЛП, транспортная задача, блочное программирование, параметрическое программирование. Нелинейное программирование: выпуклое, вогнутое, квадратичное, стохастическое.
Линейное программирование: целевая функция j(x) и ограничения gi(x) и hi (х) линейны; выпуклое программирование: целевая функция и допустимое множество выпуклы; квадратичное программирование: целевая функция квадратична и выпукла, допустимое множество определяется линейными равенствами и неравенствами; стохастическое программирование: входная информация носит элементы неопределённости;
Классификация транспортных задач (ТЗ).
Классическая транспортная задача (Предназначена для выбора оптимального плана перевозок товаров из т станций отправления (пунктов производства) к п станциям назначения (пунктам сбыта).)
Построение допустимого план ( Метод минимальной стоимости
Метод двойного предпочтения, Метод Мюллера-Мербаха, Метод Фогеля) Метод потенциалов, МОДИ, Метод разрешающих слагаемых, Метод дифференциальных рент, Параметрическая ТЗ, Сетевая транспортная задача (прежде чем попасть на конечную станцию назначения, товары могут транзитом следовать через другие узлы или пункты сбыта.) Многоэтапная транспортная задача , ТЗ по критерию времени Распределительная транспортная задача (Распределительные задачи связаны с распределением ресурсов по работам, которые необходимо выполнить. Задачи этого класса
возникают тогда, когда имеющихся в наличии ресурсов не хватает для выполнения каждой работы наиболее эффективным образом. Поэтому целью решения задачи, является отыскания такого распределения ресурсов по работам, при котором либо минимизируются общие затраты, связанные с выполнением работ, либо максимизируется получаемый в результате общий доход.)
Задача о назначении Модифицированный метод потенциалов
Метод разрешающих множителей
4. Методы построения допустимого плана ТЗ.
1) метод северо-западного угла 2)метод минимальной стоимости (отыскивается наименьшее значение критерия оптимальности, куда помещаем максимально возможную перевозку) 3) Метод двойного предпочтения (В каждой строке отыскивается наименьшее значение критерия оптимальности, и производится метка клетки (х), затем выполняем тот же поиск по столбцам, и снова метим соответствующие клетки (х). они совпадают - (хх). Помещаем в найденные клетки максимально возможные перевозки, затем снова находим наименьшее значение показателя, куда помещаем максимально возможную перевозку в клетку с одной меткой (х)) 4) Метод Мюллера-Мербаха(Среди поставщиков и потребителей отыскивается max(ai, bj).В матрице отыскивается наименьшее значение критерия оптимальности, куда помещаем максимально возможную перевозку, затем в столбцах с max(ai, bj) отыскиваем максимальные значения, снова находим наименьшее значение показателя, куда помещаем максимально возможные перевозки. 5) Метод Фогеляв каждой строке отыскивается наименьшее значение критерия оптимальности, и затем следующее за ней наименьшее значение,и находится разность между ними: и помещается в столбец справа от таблицы. Аналогичные действия выполняются по столбцам: Из рассчитанных разностей отыскивается наибольшая. В клетку, относительно которой найдена эта разность заносится максимальная поставка. Во второй таблице по каждому столбцу снова подсчитываются разности Теперь вычеркивается столбец, поскольку потребность его удовлетворена. Надо пересчитывать разности по строкам.
Математ постановка ТЗ. Открытая и закрытая модели.
Классическая транспортная задача (ТЗ) предназначена для выбора оптимального плана перевозок товаров из т станций отправления (пунктов производства) к п станциям назначения (пунктам сбыта). Возможная величина поставок от станции отправления i равна ai; единиц, а спрос на товар в j пункте сбыта равен bj единиц. Стоимость перевозки единицы товара из источника i к станции назначения j равна cij Таким образом, если xij — соответствующий уровень производственной деятельности, т. е. в данном случае объем перевозок от источника i к пункту j, то математическая формулировка модели принимает следующий вид:
Если условие (3) задано в виде неравенства (>), то ТЗ называется открытой.
Открытые задачи часто используются на практике для решения задач перспективного планирования: оптимизация развития предприятий, фирм, корпораций, отраслей.
Откр. задачи часто исп-тся на практике для решения задач перспективного планирования: оптимизация развития предприятий, фирм, корпораций, отраслей. Реш.этих задач практически ничем не отличается от закрытых. При оптимизации перевозок по методам последовательного сокращения невязок, в последнем оптимальном и допустимом плане перевозок, имеем сумму небалансов больше нуля, поскольку ресурсы больше потребностей. Для методов последовательного улучшения планов (метод потенциалов, МОДИ) существует другой подход. Обозначим соответствующую разность как bj,n+1 и введем ее в условие задачи как фиктивный пункт сбыта.
Очевидное обобщение приведенной модели
включает рассмотрение и транспортной сети, допускающей существование промежуточных транспортных узлов; при этом, прежде чем попасть на конечную станцию назначения, товары могут транзитом следовать через другие узлы (станции отправления – источники) или пункты сбыта. Сформулированная при этих условиях задача называется сетевой транспортной задачей. В ней особенно просто можно учитывать ограничения на пропускную способность.
Мюллера-Мербаха
Один из лучших результатов. 1. Из всех чисел ( потребностей и ресурсов, выбираем наибольшее) 2. Значит распределяем ресурсы второй строки, затем начинаем распределять с наименьших затрат.
Фогеля.
1. рассматриваем в каждой строке 2 клетки с наименьшими затратами и разность между ними записываем справа.,2. столбцы так же. 3. Из всех величин выбираем наибольшую. Т.к. если мы её не заполним, то понесём наибольший ущерб.
4. пересчит прав столбец; если вычёркиваем строку, пересчитываем по столбцу. Если вычёркиваем столбец, вычёрк строку.