презентация_Л2-3
.pdf
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. СИМПЛЕКС-МЕТОД
Л.В. Канторович (1938), Дж. Данциг (1947)
ПОСТАНОВКА ЗАДАЧИ ЛП
Выбрать среди n-мерных векторов x (x1, x2 ,..., xn ), ( xi 0 для i 1,2,...n), удовлетворяющих системе
a11x1 |
a12 x2 |
... a1n xn |
b1 |
|||||
|
|
|
a22 x2 |
... a2n xn |
b2 |
|||
a21x1 |
||||||||
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
|
|
a |
x a |
x |
... a |
mn |
x |
b |
||
|
m1 |
1 |
m2 |
2 |
|
n |
m |
|
такой, для которого достигается минимум ЦФ min F 1x1 2 x2 ... ... n xn
(1)
(2)
Переход к неравенствам <= с помощью эквивалентных соотношений
|
a |
j1 |
x a |
j 2 |
x |
... a |
jn |
x |
b |
j |
a j1x1 a j 2 x2 a jn xn bj |
|
1 |
2 |
|
n |
|
||||
|
|
x a |
|
x |
... a |
|
x |
b |
|
|
|
a |
j1 |
j 2 |
jn |
j |
|||||
|
|
1 |
2 |
|
n |
|
aj1x1 a j 2 x2 ... a jn xn bj a j1x1 a j 2 x2 ... a jn xn bj
max F (x) min F (x)
x
Основная сложность задачи ЛП:
отсутствие экстремума внутри области ограничений из-за линейности ЦФ F(x) (производные не равны нулю);
минимум (максимум) ЦФ F(x) достигается в точках границы области ограничений (1)
Основная идея метода ЛП:
целенаправленный перебор некоторых вариантов решения с его последовательным улучшением.
Решение задачи ЛП симплекс-методом:
аналитическое определение одной из вершин многогранника решений
последовательный переход к его соседним вершинам, каждая из которых ближе к оптимальному решению (с меньшим значением ЦФ)
Основная идея метода ЛП (в 3D)
Вывод канонической формы задачи ЛП
Пусть дана система m линейных неравенств с n переменными (1):
a11x1 |
a12 x2 |
... a1n xn |
b1 |
|||||
|
|
|
a22 x2 |
... a2n xn |
b2 |
|||
a21x1 |
||||||||
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
|
|
a |
x a |
x |
... a |
mn |
x |
b |
||
|
m1 |
1 |
m2 |
2 |
|
n |
m |
|
Систему (1) преобразуем в систему линейных алгебраических уравнений (СЛАУ) прибавлением к левой части каждого неравенства неотрицательных допол-
нительных переменных xn 1 |
0, i 1,2,...,m: |
|
|||||
|
a11x1 a12 x2 |
... a1n xn xn 1 |
b1 |
|
|||
|
|
|
... a2n xn xn 2 |
b2 |
|
||
a21x1 a22 x2 |
(3) |
||||||
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
|
|
a |
x a |
x |
... a |
x |
x |
b |
|
|
m1 1 |
m2 2 |
|
mn n |
n m |
m |
|
Всякому решению системы неравенств (1) соответствует определенное решение системы линейных уравнений (3), у которого те же самые значения основных переменных x1, x2 ,..., xn .
Каноническая форма задачи ЛП
При условиях
n |
|
|
|
aij x j |
bi , i 1,2,...,m |
(4) |
|
j 1 |
|
|
|
x j 0, |
j 1, 2,...,n |
(5) |
|
найти минимум ЦФ
n |
|
F (x) j x j |
(6) |
j 1