Общая постановка и разновидности задач математического программирования

Оптимальный план оптимальный план

Исходная ЗЦЛП №1

(оптимальный план )

оптимальный план ОДР пуста.

х₁=1, х₂=1, f_max=32 х₁=, х₂=2, f_max=37

A=32

оптимальный план ОДР пуста

х₁=0, х₂=, f_max=35,75

Оптимальный план ОДР пуста

х₁=0, х₂=3, f_max=33>A

Оптимальный план ЗЦЛП: х₁=0, х₂=3, f_max=33.

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

Общая математическая схема задачи математического программирования такова: дана некоторая функция

z = f(x₁, x₂,..., x_n) (7.1)

и некоторая система ограничений, наложенных на переменные x₁, x₂,..., x_n:

Требуется найти такой набор значений переменных x₁, x₂,..., x_n, который удовлетворяет ограничениям (7.2), и при этом условии минимизирует или максимизирует функцию (7.1).

Если все фигурирующие в (7.1) и (7.2) функции линейны, то мы имеем ЗЛП. В противном случае получается задача нелинейного программирования.

Для задач нелинейного программирования нет такого универсального метода решения, каким является симплекс-метод для ЗЛП. Только для узких классов задач нелинейного программирования разработаны точные методы, основная масса решается приближенно.

В некоторых задачах математического программирования ОДР состоит из дискретного множества точек. Такие задачи называются дискретными оптимизационными задачами. Например, если в ЗЛП потребовать, чтобы переменные принимали только целые значения, то получится дискретная оптимизационная задача - задача целочисленно­го линейного программирования. Дискретные задачи, как правило, сложнее непрерывных. По задачам дискретной оптимизации в настоящее время проводятся интенсивные научные исследования.

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

Наконец отметим, что встречаются задачи математического программирования, в которых исходные данные являются случайными величинами. Такие задачи изучает стохастическое программирование. Стохастическое программирование использует теоретико-вероятностные, статистические и оптимизационные методы.

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