Учебная работа № 5231. «Контрольная Математическое программирование, задание 6, вариант 9
Учебная работа № 5231. «Контрольная Математическое программирование, задание 6, вариант 9
Содержание:
«Задание 6. Сеть задана матрицей пропускных способ¬ностей дуг (dij = 0 означает, что в сети отсутствует дуга, ведущая из вершины 1 в вершину j). Требуется по матрице D построить сеть и найти в ней максимальный поток из вершины 1 в вершину 10, опреде-лив при этом минимальный разрез.
»
Выдержка из похожей работы
(1) называетсясистемой ограничений
(областью
допустимых решений), Функция (2)
называетсяцелевой функцией,
Оптимальным
решением задачи ЛП называется решениесистемы ограничений (2), при котором
целевая функция принимает оптимальное
значение,
Рассмотрим задачу
ЛП в стандартной форме для случая двух
переменных
:(9)(10)
Пусть система
неравенств (10) совместна (имеет хотя бы
одно решение), Любое неравенство этой
системы геометрически определяет
полуплоскость с граничной прямой
Условия не отрицательности определяют
полуплоскости с соответственными
граничными прямыми
и,
Так как система
совместна, то полуплоскости, как выпуклые
множества, пересекаясь, образуют общую
часть, которая является выпуклым
множеством и представляет собой
совокупность точек, координаты каждой
из которых являются решением данной
системы, Совокупность всех этих точек
называется многоугольником решений,
Это может быть точка, отрезок, луч,
прямая, замкнутый многоугольник,
неограниченная многоугольная область,
Решение ЗЛП
геометрически представляет собой поиск
такой точки ногоугольника решений,
координаты которой доставляют целевой
функции наибольшее (наименьшее) значение,
Причем допустимым решением являются
все точки многогранника,
Алгоритм решения
задачи линейного программирования
графическим методом (число переменных
), 1,
Строится многоугольная область допустимых
решений на плоскости
соответствующая ограничениям, Затем
строится вектор-градиентцелевой
функции zв любой точкеобласть допустимых решений, 2,
Прямая(линия уровня функцииz), перпендикулярная
вектору-градиенту, передвигается
параллельно самой себе в направлении
вектора-градиента в случае задачи на
максимум (и в противоположном направлении
— в случае задачи на минимум) до тех пор,
пока она не покинет область допустимых
решений, Предельная точка (или точки)
области являются оптимальными точками,
3, Для нахождения
координат оптимальной точки, надо решить
систему уравнений, которая соответствует
прямым, пересечение которых образует
эту точку, Значение целевой функции в
этой точке будет оптимальным, а сами
координаты точки будут являться решением
задачи ЛП
