Симплекс метод в форме презентации

курсовая работа

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

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных 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) двойственный симплекс - метод.

Делись добром ;)