Математическое программирование. Математическое программирование занимается изучение экстремальных задач и поиском

 

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f ( x₁, x₂, ..., x_n ) при ограничениях g_i ( x₁, x₂, ..., x_n ) * b_i , где g_i - функция, описывающая ограничения, * - один из следующих знаков £, =, ³, а b_i - действительное число, i = 1, ..., m. f называется целевой функцией.

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

Задачу линейного программирования можно сформулировать так. Найти max

 

при условии: a₁₁ x₁ + a₁₂ x₂ +... + a_1n x_n £ b₁;

a₂₁ x₁ + a₂₂ x₂ +... + a_2n x_n £ b₂;

...........................

a_m1 x₁ + a_m2 x₂ +... + a_mn x_n £ b_m;

x₁ ³ 0, x₂ ³ 0, ..., x_n ³ 0.

 

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

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

Найти:

max c_T x

при условии:

 

A x £ b;

x ³ 0,

 

где А - матрица ограничений размером (m´ n),

b(m´ 1) - вектор-столбец свободных членов,

x(n ´ 1) - вектор переменных,

с_Т = (c₁, c₂, ..., c_n) - вектор-строка коэффициентов целевой функции.

Решение х₀ называется оптимальным, если для него выполняется условие:

 

с_Т х₀ ³ сТ х, для всех х Î R(x).

 

Поскольку min f(x) эквивалентен max [- f(x)], то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.

Для решения задач данного типа применяются методы:

1) графический;

2) табличный (прямой, простой) симплекс - метод;

3) метод искусственного базиса;

4) модифицированный симплекс - метод;

5) двойственный симплекс - метод.

 

Графический метод

 

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

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

 

Табличный симплекс – метод

 

Для его применения необходимо, чтобы знаки в ограничениях были вида “меньше либо равно”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему:

1. Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

Если в исходной системе ограничений присутствовали знаки “ равно ”

или “ больше либо равно ”, то в указанные ограничения добавляются

искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

2. Формируется симплекс-таблица.

3. Рассчитываются симплекс – разности.

4. Принимается решение об окончании либо продолжении счёта.

5. При необходимости выполняются итерации.

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

 

Метод искусственного базиса

 

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

“равно”, “больше либо равно”, “меньше либо равно” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m, а в задачи минимизации - с положительными m. Таким образом, из исходной получается новая m - задача.

Если в оптимальном решении m - задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении m - задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.

 

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

Поделиться: