Симплекс метод в форме презентации
Математическое программирование
Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2, ... , xn ) bi , где gi - функция, описывающая ограничения, - один из следующих знаков , , , а bi - действительное число, i = 1, ... , m. f называется целевой функцией.
Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные.
Задачу линейного программирования можно сформулировать так. Найти max
при условии: a11 x1 + a12 x2 + . . . + a1n xn b1;
a21 x1 + a22 x2 + . . . + a2n xn b2;
. . . . . . . . . . . . . . . . . . . . . . . . . . .
am1 x1 + am2 x2 + . . . + amn xn bm;
x1 0, x2 0, . . . , xn 0 .
Эти ограничения называются условиями не отрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.
В матричной форме задачу линейного программирования записывают следующим образом.
Найти:
max cT x
при условии:
A x b;
x 0 ,
где А - матрица ограничений размером (mn),
b(m1) - вектор-столбец свободных членов,
x(n 1) - вектор переменных,
сТ = (c1, c2, ... , cn) - вектор-строка коэффициентов целевой функции.
Решение х0 называется оптимальным, если для него выполняется условие:
сТ х0 сТ х , для всех х R(x).
Поскольку min f(x) эквивалентен max [- f(x)], то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.
Для решения задач данного типа применяются методы:
1) графический;
2) табличный (прямой, простой) симплекс - метод;
3) метод искусственного базиса;
4) модифицированный симплекс - метод;
5) двойственный симплекс - метод.