Система m линейных уравнений с n неизвестными

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

1.86M

Category: $mathematics$ mathematics

Система m линейных уравнений с n неизвестными

1. Система m линейных уравнений с n неизвестными

2.

Система m линейных уравнений с n
переменными имеет вид
a11 x1 a12 x2 a1n xn b1 ,
a x a x a x b ,
21 1 22 2
2n n
2
,
.............................................
am1 x1 am 2 x2 amn xn bm

В задачах линейного программирования
представляют интерес системы, в
которых ранг матрицы r системы A=(aij),
i=1,2…m, j=1,2…n, или, что то же самое,
максимальное число независимых
уравнений меньше числа переменных

4.

Любые m переменных системы m
линейных уравнений с n переменными
(m<n) называются основными (или
базисными), если определитель
матрицы коэффициентов при них
отличен от нуля.
Тогда остальные n - m переменных
называются неосновными ( или
свободными)

5.

Базисным решением системы m линейных
уравнений с n переменными называется
решение, в котором все n-m неосновных
переменных равны нулю.
В задачах линейного программирования
особый интерес представляют допустимые
базисные решения (опорные планы).
Число базисных решений является
конечным.
Базисное решение, в котором хотя бы одна
из основных переменных равна нулю,
называется вырожденным.

6.

Основными могут быть разные группы из
n переменных. Максимальное число
групп основных переменных
C
m
n

7.

Пример. Найти все возможные группы
основных переменных в системе
x1 x2 2 x3 x4 0
2 x1 x2 2 x3 x4 2

8.

Решение системы называется
допустимым, если оно содержит только
неотрицательные компоненты, в
противном случае – решение
допустимое.

9.

Базисным решением системы m линейных
уравнений с n переменными называется
решение, в котором все n-m
неосновных переменных равны нулю

10.

Пример. Найти все базисные решения
системы
x1 x2 2 x3 x4 0
2 x1 x2 2 x3 x4 2

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

12.

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

13.

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

14.

Для реализации симплексного метода
необходимо освоить три основных элемента:
Способ определения какого-либо
первоначального допустимого базисного
решения задачи (опорного плана)
Правило перехода к лучшему (не худшему)
решению
Критерий проверки оптимальности найденного
решения.

15.

Пусть требуется найти максимальное
(минимальное) значение функции
F с1 x1 с2 x2 ... сn xn max(min)

16.

при условиях
а11 x1 а12 x2 ... а1п хn b1
a x a x ... a x b
21 1
22 2
2n n
2
..........
..........
..........
..........
........
am1 х1 am 2 x2 ... amn xn bm

17.

x1 0
..........
x
n 0

18.

Алгоритм решения задачи симплексным
методом:
привести задачу линейного
программирования к стандартному виду.
найти начальное базисное решение
(опорный план). Если базисное решение
отсутствует, задача не имеет решения в виду
несовместности системы ограничений
проверить полученное базисное решение на
оптимальность с помощью критерия
оптимальности

19.

если выполняется критерий оптимальности
решения, то решение задачи заканчивается
если выполняется условие существования
множества оптимальных решений, то путем
простого перебора найти все оптимальные
решения
если имеют место условия неограниченности
целевой функции, то задача не имеет решения
если пункты 4 - 6 алгоритма не выполняются,
найти новое опорное решение и перейти к
пункту 3

20.

Для нахождения первоначального
базисного плана все переменные
разбиваются на две группы:
основные(базисные) и неосновные.
Положив неосновные переменные
равными нулю, получаем базисное
решение.

21.

Критерий оптимальности решения
при отыскании
максимума(минимума) линейной
функции:
Если в выражении линейной функции
через неосновные переменные
отсутствуют положительные
(отрицательные) коэффициенты при
неосновных переменных, то решение
оптимально.

22.

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

23.

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

24.

Алгоритм:
1. Систему линейных неравенств
записываем в каноническом виде. Для
этого в каждое неравенство добавляем
дополнительную переменную со знаком
«+», если неравенство имеет знак
меньше или равно и со знаком «-» в
противном случае

25.

После введения добавочных переменных
систему уравнений и линейную
функцию записываем в виде:

26.

а11 x1 а12 x2 ... а1п хn хn 1 b1
a x a x ... a x x b
21 1
22 2
2n n
n 2
2
................................................
a х a x ... a x x
m1 1
m2 2
mn n
n m bm
F c1 x1 c2 x2 ... cn xn 0

27.

2.
Исходную расширенную систему
заносим в первую симплексную таблицу.

28.

Базис
Свобо
дный
член
Переменные
х1
х2
…… хn
Оценочные
отношения

29.

3. Проверяем выполнение критерия
оптимальности при решении задач на
максимум- наличие в последней
строке отрицательных коэффициентов.
Если таковых нет, то полученное
решение оптимально.

30.

4 Если критерий оптимальности не
выполнен, то наибольший по модулю
отрицательный элемент в последней
строке определяет разрешающий
столбец s

31.

Составляем оценочные отношения каждой
строки по правилам:
1) ∞, если bi и ais имеют разные знаки;
2) ∞, если bi=0 и ais <0
3) ∞, если ais =0
4)
, если bi и ais имеют одинаковые
bi
ais
знаки

32.

Определяем
bi
min
i
ais
.

33.

Если конечного минимума нет, то
задача не имеет конечного оптимума
(Fmax=∞)
Если минимум конечен, то выбираем
строку, в которой он достигается и
называем ее разрешающей строкой
q.
На пересечении разрешающей строки
и разрешающего столбца находится
разрешающий элемент аqs

34.

5. Переходим к следующей таблице по
правилам:
в левом столбце записываем новый
базис: вместо основной переменной хqпеременную xs
в столбцах, соответствующим основным
переменным проставляем нули и
единицы: 1 – против «своей» основной
переменной 0- против «чужой»
основной переменной. 0 в последней
строке для всех основных переменных.