Шпаргалка по Математическому программированию (стр. 5 из 8)
6. признаком получения оптимального решения двойственным симплекс-методом является критерий оптимальности обычного симплекс-метода.
41. Открытые и закрытые транспортные модели. Переход от открытой транспортной модели к закрытой.
Типы транспортных задач.
Имеются m поставщиков однородной продукции с известными запасами продукции и n потребителей этой продукции с заданными объёмами потребностей. Известны так же удельные затраты на перевозку.
Если сумма объёмов запасов продукции равна объёму потребностей всех потребителей, то такая задача называется закрытой транспортной задачей
(т. е. если ∑ Ai = ∑ Bj), в противном случае транспортная задача называется открытой. Для решения транспортной задачи необходимо, чтобы она была закрытой.
Открытую транспортную задачу можно преобразовать к закрытой следующим образом.
Пусть ∑Ai > ∑Bj. В этом случае необходимо ввести фиктивного n+1 потребителя с объёмом потребностей ∑Ai – ∑Bj Удельные затраты на перевозку от поставщиков к фиктивному потребителю полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторая часть продукции останется у поставщиков.
Если ∑Bj > ∑Ai . В этом случае необходимо ввести фиктивного m+1 поставщика с объёмом запасов∑Bj – ∑Ai . Удельные затраты на перевозку от фиктивного поставщика к потребителям полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторую часть продукции потребители недополучат.
42. Способы построения первоначального распределения в транспортной задаче: метод северо-западного угла и метод наименьшего элемента в матрице.
Северо-западный прием построения опорного плана. Согласно этому приему формирование величин перевозок начинается с с.-з. уголка таблицы, т.е. с клетки x11. По этому приему прежде всего распределяется товар первого поставщика. Причем первый поставщик сначала предельно возможно удовлетворяет первого потребителя. Затем, если у поставщика товар еще остался,
Метод наименьшего элемента в матрице.
Сущность метода заключается в том, что максимально возможная поставка всегда проставляется в клетку, которой соответствует наименьший тариф матрицы.
Сначала делаем пометки (например, знаком ▼ ) в тех клетках строк, в которых наблюдается самая меньшая цена по строке. Затем обходим таблицу по столбикам и делаем такие же пометки в клетках, в которых самая маленькая цена по столбикам.
Дальнейшее распределение делается сначала предельно возможно по клеткам с двумя отметками, потом - с одной, а затем делается добалансировка задачи до (m + n – 1) заполнений. Заполнения организуем при прохождении таблицы слева направо и сверху вниз.
43. Свойства транспортных задач
Транспортная задача обладает некоторыми свойствами, которые можно отразить следующими теоремами.
Теорема 1. Закрытая транспортная задача всегда имеет решение.
Теорема 2. Если объёмы запасов продукции и объёмы потребностей является целыми числами, то и решение транспортной задачи также будет целочисленным.
Теорема 3. система ограничений закрытой транспортной задачи всегда линейно-зависима.
Из этой теоремы следует, что распределение закрытой транспортной задачи всегда имеет m + n – 1 базисную переменную и (m – 1) (n – 1) свободные временные.
44. Вырожденное распределение в транспортных задачах, избавление от вырожденности. Вычеркиваемая комбинация.
Распределение называется вырожденным, если количество клеток меньше чем m + n – 1.
45. Теорем оптимальности транспортной задачи.
Теорема. Если для некоторого распределения транспортной задачи вы-
полняются условия:
а). ui+vj = сij для занятых клеток
б) ui+vj ≤ сij,, для свободных клеток,
то данное распределение является оптимальным.
Величины ui называют потенциалами строк, а величины vj называют потенциалами столбцов.
46. Потенциалы и способы их расчета.
Для нахождения потенциалов строк и столбцов пользуются следующими рассуждениями, исходя из условия а) теоремы оптимальности.
Количество уравнений исходя из этого условия равняется m + n – 1, а количество неизвестных ui и vj равняется m + n. Т.о. количество переменных больше количества уравнений, причем все уравнения линейно независимы. Решение такой системы линейных уравнений является неопределенным, поэтому одному из потенциалов нужно присвоить любое значение. На практике ui = 0. получается система из m + n – 1 уравнений с m + n – 1 неизвестными переменными. Эту систему можно решить любым методом. На практике для расчета потенциалов рассматриваются занятые клетки, для которых один их потенциалов известен, и исходя из условия а) теоремы вычисляются значения остальных неизвестных потенциалов.
47. расчет оценок оптимальности распределения транспортных задач и критерий оптимальности.
Исходя из соотношения б) теоремы можно записать следующую формулу для вычисления оценок: δ ij = ui +vj – сij. Для того, чтобы оценки не перепутать с объёмами перевозок, они (оценки) заключаются в круги.
Оценки оптимальности в свободных клетках ТЗ представляют собой критерий оптимальности, с помощью которого осуществляется проверка распределения на оптимальность. Если оценки всех свободных клеток меньше или равны нулю, то данное распределение является оптимальным.
48. перераспределение поставок в транспортной задаче
Если распределение не является оптимальным, то необходимо осуществить перераспределение поставок.
Для перераспределения осуществляют построение цикла пересчета. В качестве клетки выбирается клетка с наибольшей положительной оценкой. Эта клетка помечается знаком «+», то есть в неё необходимо записать некоторый объём поставки. Но тогда нарушится баланс по данному столбцу, следовательно, одну из занятых клеток данного столбца необходимо пометить знаком «-», то есть уменьшить объём поставки на такую же величину. Но тогда изменится баланс по данной строке, следовательно, какую-то занятую клетку данной строки необходимо пометить знаком «+». Данный процесс продолжается до тех пор, пока не поставлен знак «-» в строке, где находилась исходная клетка.
Для любой свободной клетки существует цикл пересчета и притом единственный.
49. цепочки перераспределения, их виды.
Пусть рассматриваемый план перевозок не оптимальный, т.е. имеются положительные относительные оценки. Тогда берется неблагоприятная клетка (одна из неблагоприятных) и для нее строится цикл пересчета, согласно которому потом делается перераспределение намеченных перевозок. Цикл строится в виде ломаной замкнутой линии, отрезки которой идут либо вдоль столбика, либо вдоль строки. В одном из углов ломаной претендующая на товар неблагоприятная клетка, а в остальных углах клетки заполненные, т.е. при построении цикла мы исходим из претендующей клетки и возвращаемся в нее по ломаной, но повороты мы можем делать только в клетках заполненных (соответствующих базисным переменным). Пусть неблагоприятная клетка претендует на товар Q. Чтобы не произошел разбаланс в таблице, надо в переходах по циклу по очереди
прибавлять и отнимать Q к имеющимся перевозкам. Так как углов чётное количество, в половине клеток Q прибавится, а в другой половине - отнимется. Обход цикла начинают по часовой стрелке или против с претендующей клетки, помещая туда товар Q, затем из соседней клетки вычитают Q, затем прибавляют и т.д. Сама величина Q выбирается так, чтобы одна из клеток опустошалась, но ни одна из поставок не стала бы отрицательной.
Для этого Q надо выбрать равным наименьшему уменьшаемому из клеток, в которых Q вычитается. На следующих рис. 7.1 и 7.2 покажем примеры циклов и правило вычисления.
При этом опустошаются две клетки. Но надо, чтобы взаимно пустой стала лишь одна клетка. Поступают так: одну из опустошающихся клеток делают пустой в новой таблице, а в другой опустошающейся клетке ставят нуль. Эта клетка считается в новой таблице базисной (заполненной).
50. Выбор объема перераспределения.
Определение объёма перемещаемой продукции. При определении объёма продукции, перемещаемого по циклу пересчёта, мы должны исходить из следующих двух соображений:
а) после преобразования в клетках таблицы не должны получиться отрицательные числа;
б) одна из занятых клеток должна стать свободной.
Для того, чтобы эти условия выполнялись, необходимо объём перемещаемой продукции выбрать следующим: θ=min {хij} -, где {хij} – объёмы перевозок из клеток цикла пересчёта, помеченных знаком «-».
θ = min{20;30}=20
К значениям клеток, помеченных знаком «+»прибавляется θ. От значений клеток, помеченных знаком «-», вычитается θ. Значение поставок остальных клеток переписывается без изменений. В результате получим следующую таблицу.
53. Алгоритм метода потенциалов.
Алгоритм:
1. Проверить, выполняется ли для задачи рав-во
если нет, то в задачу вводится фиктивный поставщик или потребитель2. Условие задачи записывается в форме транспорт.таблицы
3. Строится начальный опорный план
4. Определяются потенциалы пост-ков и потреб-лей
5. Вычисляются оценки свободных клеток. Если все они не отрицательные – план оптимальный и нужно выписать ответ. Матрицу перевозок Х и определить величину затрат на транспортировку. Если план не явл-ся оптимальным, т.е.среди оценок есть отриц-ые, то выбир-т перспективную клетку с наибольшей по величине отриц. оценкой и переходят по величине к след.