Теоремы двойственности. Виды математических моделей двойственных задач. Транспортная задача. Задача выбора (о назначениях). Нахождение опорного плана. Метод потенциалов

19Теоремы двойственности

20  иды математических моделей двойственных задач

21Транспортная задача

23Задача выбора (о назначениях)

24Нахождение опорного плана

25Метод потенциалов

19.Теоремы двойственности. Если из двух задач прямой и двойственной одна обладает оптимальным решением, то и вторая имеет оптимальное решение, причем для экстремальных значений линейных форм выполняется соотношение min L=max L′.

Если линейная форма одной из задач не ограничена для прямой снизу для двойственной сверху, то др. задача не имеет решения.

20.Виды математических моделей двойственных задач. Математические модели пар двойственных задач могут иметь след. виды:

Таким образом прежде чем записывать двойственную задачу по известной прямой необходимо ограничения прямой задачи привести к виду как указано в таблице.

21.Транспортная задача. Транспортная задача рассматривается при условии ∑ a_i =∑ b_j .Ранг системы ограничен 2 и3 r=(n+m)-1. для оптимального решения по крайней мере k значений x_ij должны быть равны 0. Кол- во ед. груза направляемого из пункта a_j в b_j называются перевозки. Любая совокупность перевозок x_ij называется планом перевозок. Если план удовлетворяет пунктам2 и 3 балансовым условиям, то это допустимый план. Если из всех опорных планов один приводит к min стоимости, то это оптимальный план.

22.Математическая постановка основной ТЗ по критерию стоимости. xi_j – кол-во груза.  Отправляемое из a_i в b_j, j от 1 до n. 1.Суммарная стоимость всех перевозок должна быть min. L= ∑∑ c_ij x_ij →min.  2.Суммарное кол-во грузов отправляемое из данного пункта во все пункты должно быть равно запасу груза в данном пункте ∑x_ij = a_i ,i=1,m.  3.Суммарное кол-во грузов доставляемых в каждый пункт из всех пунктов должно быть = заявки поддонной этим пунктом  ∑x_ij =b_i. i от 1 до m, j от 1 до n. ТЗ рассматривается при условии ∑a_i  = ∑ b_j. Ранг системы ограничен 2 и3. n+m-1. уравнение 2и3 можно решить относительно R базисных переменных, выраженных через свободные R= (n-1)*(m-1). Для оптимального решения R значений x_ij должны быть = 0. кол- во ед-ц груза направляемого из a_i в b_j – перевозки. Любая совокупность значений перевозок x_ij – план перевозки. Если план удовлетворяет 2 и 3 балансовых условий – план допустим. Если в допустимом плане не = 0 не более R  базисных перевозок, а основные перевозки = 0, то план опорно допустимый. Если среди опорных планов один приводит к min стоимости – план оптимальный.

23.Задача выбора (о назначениях). Имеется n работ которые необходимо распределить  между n исполнителей известно, что i,j это рабочие массы затраченные на i-ю работу j-м исполнителем, требуется так распред-ть  n исполнителей на работ, чтобы число рабочих часов на выполнение всех работ было min. x_ij= 1? Если на i-ю работу j-й исполнитель x_ij=0, если на i-ю работу не назначен j-й исполнитель. Время на выполнение всех работ L= ∑ ∑ t_ij x_ij→min. Ограничения: на любую работу назначен только один исполнитель, тоесть ∑ x_ij=1, j от 1 до n. x_ij >= 0. j от 1 до n, i от 1 до n.

!!!24.Нахождение опорного плана. (не хватает 2-х словечек)

 Решение ТЗ начинается с нахождения допустимого опорного решения. Для ТЗ решение всегда сущ-т. Для отыскания опорного плана ТЗ применяются несколько способов: диагональный, наименьшей стоимости и модифицированный диагональный. Методы для нахождения оптимального плана ТЗ: распределительный, потенциалов, венгерский. Распред метод: базируется на симплексе алгоритме . Нахождение оптимального решения в данном методе заключается в последовательном улучшении путем преобразования транспортных таблиц. Число базисных переменных R=m+n-1, а число свободных k= (m-1)*(n-1). Допустим, опорное решение определено. В таблицу занесены все базисные перевозки, в том числе и нулевые. В таблице должно быть заполнено не менее R клеток. Далее переходим от опорного плана к оптимальному. Циклом ТЗ называется несколько клеток соединенных замкнутой линей, которая в каждой клетке в вершине совершает поворот на 90 градусов. Цикл с 4-я вершинами стрелки указывает направление хода цикла. Каждый цикл имеет четное число вершин или звеньев. Цикл называется                     если в вершинах есть зраки +-.Ценой цикла называется алгебраическая сумма стоимостей стоящих на вершине цикла, стоимость, стоящая в положительных вершинах берется с +, а в отрицат с -. Если таких циклов таблице не осталось, значит получен оптимальный план. Цикл все вершины которого кроме 1 находятся в базисных клетках наз-ся циклом пересчета. Если цена цикла пересчета γ отриц-я, то план можно улучшить на k_γ , перемещением на k единиц груза по k-циклу. k = min значению перевозок.