Математическое программирование

Математическое программирование — математическая дисциплина, изучающая методы и теорию ответа задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и неравенствами ограничениями (и нелинейными равенствами). Формально задача математического программирования формулируется так:

В зависимости от природы множества X задачи математического программирования классифицируются как задачи дискретного программирования (либо комбинаторной оптимизации) — в случае если X само собой разумеется либо счетно; задачи целочисленного программирования — в случае если X есть подмножеством множества целых чисел; задачей нелинейного программирования, в случае если ограничения и/либо целевая функция содержат нелинейные функции и X есть подмножеством конечномерного векторного пространства. В случае если же все ограничения и целевая функция содержат только линейные функции, то это — задача линейного программирования. Математическое программирование употребляется при ответе оптимизационных задач изучения операций.

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

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

В некоторых задачах целочисленные значения могут быть равны лишь 0 либо 1, тогда такие задачи именуются задачами с булевыми переменными.

Задачу целочисленного линейного программирования возможно решить как задачу линейного программирования, а после этого округлить полученное ответ. Но таковой метод допустим лишь при условии, что значения переменных такие большие, что погрешностью, вызываемой округлением возможно пренебречь. В случае если же в следствии ответа переменная принимает малое значение, то ее округление может привести к весьма далекому от оптимального ответа. Используются два метода ответа задач ЦЛП – метод ветвей и метод отсечений и границ.

Ответ задачи ЦЛП способом отсечения:

1. Ответ задачи как задачи ЛП.

2. В случае если мы взяли целочисленное ответ, то оно и есть ответом задачи ЦЛП.

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

Ответ задачи ЦЛП способом границ и ветвей:

1. Решаем задачу как задачу ЛП.

2. В случае если мы возьмём оптимальные целочисленные ответы задачи ЛП, то они являются кроме этого и оптимальными ответами задачи ЦЛП.

3. В случае если мы не возьмём целочисленных ответов, то целевая функция Z1 задачи ЛП делается верхней границей оптимального значения Z задачи ЦЛП, по причине того, что значение целевой функции Z при введении в будущем новых ограничений для получения оптимальных целочисленных ответов значительно уменьшается.

4. После этого производится ветвление по одному из нецелочисленных оптимальных ответов задачи ЛП. Ветвление осуществляется с применением некоторых правил по следующей схеме: в случае если n x n+1, то 1) x n; 2) x n+1, где х – нецелочисленное оптимальное ответ задачи ЛП, по которому мы осуществляем ветвление, n – ближайшее целое к х не превышающее х.

Правила ветвления:

1) Выбирается переменная, у которой дробная часть самый близка к 0,5.

2) Выбирается переменная с громаднейшим приоритетом по какому — или качественному либо количественному значению.

3) Переменная выбирается произвольно.

Ограничения введенные при ветвлении добавляются к ограничениям задачи ЛП.

В каждой из вершин находим оптимальные ответы взятых методом добавления новых ограничений задач ЛП – 2 и ЛП – 3. Если не у одной из них мы не взяли целочисленных оптимальных ответов, то мы выбираем ту вершину, в которой получено громаднейшее значение целевой функции и производим предстоящее ветвление. Так длится до получения целочисленного оптимального ответа одной из задач ЛП.

Вершина именуется прозондированной, в случае если:

1) Мы нашли в ней оптимальное целочисленное ответ – ответ задачи ЦЛП.

2) В данной вершине нет оптимальных ответов задачи ЛП.

3) Значение Z в оптимальном ответе задачи ЛП не больше текущей нижней границы.

Другие вершины именуются висящими.

Лекция 1 | Линейное программирование | Максим Бабенко | Лекториум


Также читать:

Понравилась статья? Поделиться с друзьями: