Общая задача линейного программирования и формы ее записи

В общей постановке задача линейного программирования выглядит следующим образом:

Имеются какие-то переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х₁ , х₂ , … х_n
б) область G определяется системой линейных равенств или неравенств.

Математическая модель любой задачи линейного программирования включает в себя:

максимум или минимум целевой функции (критерий оптимальности);

систему ограничений в форме линейных уравнений и неравенств;

требование неотрицательности переменных.

Наиболее важными формами задачи линейного программирования являются каноническая и стандартная.

Конечные и итеративные методы решения задач линейного программирования

Конечные методы гарантируют нахождение точного решения за конечное число шагов; Конечные методы, в свою очередь, можно разделить на три группы: последовательного улучшения плана (симплекс- метод); последовательного уточнения оценок; последовательного сокращения невязок.

ИТЕРАЦИЯ

 1. Проверка оптимальности или нахождение ведущего столбца С-Т. ƒ Если все коэффициенты в выделенной строке при небазисных переменных неотрицательны (коэффициенты в z-уравнении), то текущее базисное решение является оптимальным. ƒ В противном случае на следующей итерации в число базисных переменных вводим небазисную переменную xs, номер которой находится по правилу: j c s c c j 0 min< = . Столбец под номером s называется ведущим столбцом симплексной таблицы.

2. Проверка условия неограниченности решения задачи ЛП и нахождение ведущей строки (ведущего элемента) С-Т. ƒ Если в ведущем столбце симплексной таблицы s нет положительных коэффициентов, то значение задачи ЛП неограниченно (нет оптимального решения) ƒ В противном случае (в ведущем столбце имеются положительные элементы) в качестве базисной переменной, которая исключается из числа базисных, выбирается та переменная xr, для которой is i a rs r a b a b is 0 min> = . Строка под номером r называется ведущей строкой С-Т, а элемент ars>0 – ведущим элементом С-Т.

 3. Преобразование симплексной таблицы. ƒ Используя эквивалентные преобразования таблицы (процедуру Гаусса) пересчитываем таблицу так, чтобы ведущий элемент новой С-Т стал равным 1, а все остальные элементы ведущего столбца – равными 0. Обозначим верхним индексом 1 элементы новой симплексной таблицы. Тогда формулы пересчета коэффициентов примут вид:

Универсальные и специальные методы решения задач линейного программирования

Линейное программирование — раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.

Симплексный метод.

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Сущность метода: построение базисных решений, на которых монотонно убывает линейный функционал, до ситуации, когда выполняются необходимые условия локальной оптимальности.

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

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

· нахождение исходной вершины множества допустимых решений,

· последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции.

При этом в некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, например, когда все ограничения представлены неравенствами вида «меньше или равно» (тогда нулевой вектор совершенно точно является допустимым решением, хотя и, скорее всего, далеко не самым оптимальным). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод, соответственно, делится на однофазный и двухфазный.

⇐ Предыдущая12345Следующая ⇒

Поделиться: