21. Распределительный метод решения транспортной задачи (метод потенциалов). Алгоритм распределительного метода.

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

Оценки строк и столбцов: V_i + U_j + C _{i j} = 0, где V_i –оценка i строки, U_j–оценка j столбца, C _{i j}-оценка перевозки ед.груза.

Нахождение оценок строк и столбцов осуществляется только по заполненным клеткам в которых имеются поставки. Оценки всех остальных клеток: q_nm= V_i + U_j + C _{i j} . Если матрица оценок не содержит отрицательных оценок, то план оптимальный. Для оптимизации планов поставок необходимо составить цикл пересчета: находят клетку с самым отрицательным значением. Его заключают в квадрат и клетку называют отмечаной. Двигаясь от отмечаной клетки по горизон. или вертикал. линиям составляют замкнутый цикл вершины которого проходят через нулевые значения (через клетки, где поставщики). Если получается оценка клетки с нулевым значением, то отмечают 0* . внутри цикла перераспределяются поставки. Для этого необходимо определить макс.возможное кол-во товара, которое можно перераспределить по заданному циклу. После перераспределения поставок получается новая таблица для которой составляется новая матрица оценок. Первоначальная оценка выставляется произвольно для любой строки либо столбца. Кол-во перераспределяемого товара определяется по отрицательным клеткам цикла.

22. Алгоритм решения задачи о назначениях (Венгерский метод). Минимизация целевой функции. Максимизация целевой функции.

Постановка задачи: предположим, что имеется n-различных работ – A1, A2,..An и n-механизмов – В1, В2, …Вn. Каждый из которых может выполнять любую работу, но не долговой эффективностью. Производительность механизма Вi работы Аj обозначим: Вi → Аj : Сij. Требуется так распределить механизмы от работы, чтобы их суммарный эффект от их использования был максимальным. Особенность решения: равенство число строк и число столбцов исходных данных.

Минимизация целевой ф-ции : Алгоритм: мощность поставщика и потребителя =1 (1 поездка). 1. каждой строке матрицы находим мин.элемент и вычитаем его из каждого элемента строки. 2. в каждом столбце полученной матрицы находим мин.элемент и вычитаем его из элементов столбца. 3. находим строку с ОДНИМ нулем. Его заключаем в квадрат и называем отмечанным. В столбце, где находится отмечанный нуль все остальные нули зачеркиваем и в дальнейшем не рассматриваем. Продолжаем пока возможно. 4. находим столбец с 1 нулем и его отмечаем. В строке, где он находится зачеркиваем и в дальнейшем не рассматриваем. 5. если после шагов 3, 4 есть не отмечанные нули, то отмечаем любой из них, а в строке и в столбце где он находится все остальные нули зачеркиваем. 6. если каждая строка и столбец содержит ровно 1 нуль, то полученное решение оптимально. Каждый из отмечанных нулей указывает оптимальное прикрепление поставщика к потребителю. В противном случае проводим минимальное число вертикальных и горизонтальных пересекающих линий через все отмечаные нули. Среди не зачеркнутых этими прямыми чисел находим минимум. Этот минимум вычитаем из всех не зачеркнутых чисел и прибавляем его ко всем числам на пересечении прямых. К полученной матрице применяем алгоритм с шага 3.

Максимизация целевой ф-ции: 0* пункт: случай максимизации сводиться к максимизации целевой функции для матрицы , полученной из исходной путем умножения каждого элемента на -1 остальные пункты выполняются также.

23. Нелинейное программирование. Основные понятия оптимальных экономико-математических моделей. Особенности нелинейного программирования (целевая функция, ограничения, ОР, ОДР, оптимум, глобальный оптимум).

Относится задачи у которых либо целевая функция, либо хотя бы 1 из ограничений носит не линейный характер. Особенности: 1. оптимальное решение может не принадлежать одной из вершин ОДР. 2. градиентный метод чаще всего не применим. 3. для графических моделей ОДР может быть не единственной. 4. экстремальных (оптимальных) решений может быть несколько. 5. найденное оптимальное значение целевой функции в ряде задач нелинейного программирования необходимо квалифицировать как максимум или минимум.

*Область допустимых решений—область решения системы и плюс условия не отрицательности.

*Оптимум — экстремальное значение функции или показателя, применяемого в качестве критерия оптимальности. Различают глобальный О. и локальный О. Глобальный О. отражает эффективность организации общественного производства с позиций интересов, присущих системе как целостному явлению, и интересов отдельных подсистем. Локальный О. отражает оптимальность организации какого-либо звена (подсистемы) общественного производства. Локальный О. должен быть согласован с глобальным О. и подчинен ему как часть целому.

*Целевая функция — 1) функция переменных, от которых зависит достижение критерия оптимальности; 2) скалярная функция одной или нескольких переменных, называемых управляемыми переменными (управляемыми параметрами), характеризующая качество оптимизируемого объекта. Формирование целевой функции выполняется с учетом выходных параметров объекта.

*ограничения - ?

* область решения- это пересечение полуплоскостей, каждая из которых определяется неравенством системы.