13) Оптимизационные методы получения детерминированных оценок. Методы линейного программирования

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

Эти методы используются для решения однокритериальных задач оптимизации, целевая функция которых отвечает условиям детерминированности и линейности, а на значения переменных накладываются линейные ограничения. Линейность предполагает наличие двух свойств: пропорциональности и аддитивности. Пропорциональность означает, что вклад каждой переменной в целевую функцию прямо пропорционален величине этой переметши, а аддитивность заключается в представлении целевой функции в виде суммы вкладов от различных переменных.

К особенностям использования данных методов лин. прогр. относится то, что оптимальному решению всегда соответствует одна из экстремальных точек пространства решений (это является следствием такого важного свойства задач линейного программирования, как выпуклость пространства решений). К ним относятся: метод простого перебора, метод направленного перебора, симплекс метод, графический метод и др. Рассмотрим некоторые из них. Графический метод предполагает последовательное выполнение ряда шагов:

1. Сформулировать ЗЛП.

2. Построить на плоскости {х₁, х₂} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

3. Найти полуплоскости, определяемые каждым из ограничений задачи.

4. Найти область допустимых решений.

5. Построить прямую c₁x₁ + c₂x₂ = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.

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

7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.

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

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

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

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

Янка, с 14 по 19 я не успела найти. Попробуй найти что-нибудь сама. Диктуй пока другое, или я пока буду со шпоры писать. Если смогу достать, отключусь, потом перезвоню.

14) Оптимизационные методы получения детерминированных оценок. Методы квадратичного программирования

К задачам квадратичного программирования относят специальный класс задач НП, для

которых целевая функция f(x)- квадратичная и вогнутая (или выпуклая), а все ограничения линейны.

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

Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.

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

Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.

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

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

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

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

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

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

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

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

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