Линейного программирования
Данный метод применяется для решения задач, содержащих не более трех переменных, чаще всего для задач с двумя переменными. Он базируется на следующих моментах: § множество допустимых решений задачи выпукло, в линейном случае оно представляет собой конечный или простирающийся в бесконечность многоугольник; § целевая функция достигает своего оптимального значения в вершине области. Если она принимает это значение в двух вершинах области, то оптимум достигается в любой точке отрезка, соединяющего эти вершины; § направляющий вектор (вектор нормали) перпендикулярен прямой функции цели и всегда указывает направление ее возрастания. Схему применения графического метода проиллюстрируем на конкретном примере, рассматривая три этапа: § построение области допустимых решений; § построение направляющего вектора и определение оптимальных точек; § нахождение оптимальных значений переменных и целевой функции. Найти максимальное и минимальное значение функции при ограничениях І этап. Построение области допустимых решений 1. Каждому неравенству ставим в соответствие равенство, геометрическим образом которого является прямая линия. Для ее построения достаточно двух точек. §
§
§
§
2. Каждая прямая делит плоскость на две полуплоскости, в одной из которых будет справедливо соответствующее неравенство. Чтобы установить, точки какой полуплоскости будут обеспечивать выполнение неравенства, необходимо взять произвольную точку и ее координаты подставить в неравенство. Если для этой точки неравенство выполнилось, то решением неравенства будет та полуплоскость, в которой брали точку. Если неравенство для выбранной точки не выполнилось, то его решением будут точки второй полуплоскости. Рассматривая поочередно все ограничения, получим область, в которой будут справедливы все неравенства, - это и есть область допустимых решений.
Неравенства ІІ этап. Определение оптимальных точек 1. Направляющий вектор проводят из начала координат в точку с координатами, равными коэффициентам целевой функции, то есть в точку 2. Перпендикулярно направляющему вектору на области допустимых решений проводят прямую 3. Если в задаче требуется найти максимум, прямую 4. Если требуется найти минимум, то прямую ІІІ этап. Нахождение оптимальных значений Чтобы найти переменные, обеспечивающие экстремум, необходимо решить систему уравнений тех прямых, на пересечении которых располагается точка экстремума
Таким образом, найдены максимальное и минимальное значение функции, все промежуточные значения будут достигаться в других точках области допустимых значений.
Замечание 1. Если прямая функции Замечание 2. Если область решений не ограничена, то задача или не имеет решения, или целевая функция может принять только максимальное или только минимальное значение, или задача имеет бесконечное множество решений. Симплексный метод
Симплексный метод является универсальным методом решения задач линейного программирования. Его алгоритм в той или иной интерпретации содержится практически во всех учебниках и учебных пособиях по этой дисциплине. Следует при этом учесть, что решение нужно начинать с приведения задачи к каноническому виду. Решение осуществляется в три этапа: а) строится начальное решение; 6) проводится оценка найденного решения по соответствующему критерию оптимальности; в) если условие оптимальности не выполняется, переходят к новому решению. Этапы б) и в) выполняются до тех пор, пока будет получено оптимальное решение. Все правила проиллюстрируем на примере: Найти I этап. Построение начального решения. а) Приводим задачу к каноническому виду. 1. Необходимо перейти к нахождению минимума, чтобы все правила рассмотреть для этого случая. Если в условии требуется найти максимум, то переходят к минимуму противоположной функции, а, решив задачу, возвращаются к заданной функции цели. В указанном примере: 2. Если среди свободных членов в системе ограничений есть отрицательные, то соответствующие ограничения умножают на (–1). В нашем случае это правило относится к ІІІ-му ограничению. В результате его применения система станет такой: 3. Если среди ограничений есть неравенства, то, вводя дополнительные переменные, преобразуют их в уравнения. В нашем случае:
Получили канонический вид задачи. б) В ограничения, где дополнительные переменные вычитаются, добавляют искусственные переменные с последующими номерами. Эти искусственные неизвестные вносят и в целевую функцию с коэффициентом
где
Все переменные – неотрицательны. в) Выписывают векторы коэффициентов при неизвестных и вектор свободных членов.
г) строят первую симплексную таблицу следующего вида: Таблица 1
Заполняют таблицу по правилам: 1. Вносят все векторы 2. В самую верхнюю строку записывают коэффициенты целевой функции при соответствующих неизвестных. 3. В качестве первоначального базиса берут векторы, образующие единичную матрицу, - в данном случае это векторы 4. В столбец 5. Чтобы получить элементы двух последних строк, вектор
В д) После того, как составлена симплекс-таблица, можно записать решение. Оно всегда содержится в столбце
ІІ этап. Проверка оптимальности решения а) Критерий оптимальности: функция достигает минимума, если среди элементов Следуя данному критерию, можем заключить, что полученное из таблицы 1 решение не является оптимальным: в б) В случае, когда критерий оптимальности не выполняется, выбирают ключевой столбец – по наибольшему положительному числу в
в) Определяют симплексные отношения, для этого элементы г) Ключевую строку выбирают по наименьшему симплексному отношению (С.О.), она показывает, какой вектор выйдет из базиса. Наименьшее симплексное отношение равно 1, ключевой будет вторая строка, из базиса уйдет искусственный вектор д) Элемент, стоящий на пересечении ключевой строки и ключевого столбца, называется генеральным. В построенной таблице генеральный элемент равен 5.
III этап. Построение нового решения (таблицы 2). а) Формируют новый базис, заменяя вектор б) Столбец Таблица 2
в) Вычисления ведут по таким правилам. 1. Элементы ключевой строки делят на генеральный элемент и записывают в новую таблицу. 2. Ключевой столбец дополняют нулями. 3. Если в ключевой строке есть нули, то соответствующие им столбцы переносят без изменения – это 4. Остальные элементы определяют по правилу прямоугольника. Для его построения в предыдущей таблице старый элемент соединяют с ключевой строкой и ключевым столбцом, а затем по строке и столбцу ведут к генеральному элементу, (см. табл. 1)
Новый элемент находят так: вычисляют произведение элементов диагонали, содержащей генеральный элемент, из него вычитают произведение элементов другой диагонали; полученною разность делят на генеральный элемент, и результат вносят в новую таблицу (см. табл. 2). Например, для столбца
Для столбца
Решение, соответствующее ІІ-й таблице, берем из
Для анализа второго решения повторяют все действия, начиная со II этапа. Проверка показала, что во II таблице условие оптимальности не выполняется: есть два положительных числа – это 9/5 и 1/5. Берут наибольшее и выделяют ключевой столбец Таблица 3
Решение в соответствии с таблицей 3 имеет вид:
Данное решение оптимальным не является – проверку ведем по Таблица 4
В
Дадим геометрическую интерпретацию симплексному решению. Для этого построим область допустимых решений и проанализируем, каким точкам соответствует каждая симплекс-таблица. В расчет берем только значения основных переменных Область решений не является конечной, а простирается в бесконечность и содержит бесчисленное множество точек, для которых выполняются все ограничения. Первой симплекс-таблице соответствуют значения
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|