Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А
c) |
|
(x, y) |
(1 |
x )3 |
x |
|
0, |
|
|||
|
|
2 |
|
||||||||
|
|
|
|||||||||
|
|
y1 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
d ) |
(x, y) |
y |
((1 |
x )3 |
|
x |
|
) y |
0 |
||
|
|
2 |
|||||||||
|
|
y1 |
1 |
|
1 |
|
|
1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
Вточке (1,0) первое условие уже нарушается, т.к. –2 + 6 >
0.Следовательно, точка оптимума не удовлетворяет системе а) - d). Это произошло потому, что градиенты ограничений невыпуклой задачи оказались линейно зависимы в точке (1,0). ( Активными
ограничениями являются f1 |
и условие |
|
f 2 |
x2 |
0 . |
f1 (1,0) |
(0, 1) , |
|
83
Задачи для самостоятельного решения
3.3.1.Найти условный экстремум в задачах
2) x1 max
(1 x1 )3 x2 0
|
|
|
|
|
|
x2 |
0 |
|
3) (x1 |
) 2 |
x22 |
|
max |
|
|||
x12 |
x22 |
1 |
|
|
|
|
|
|
x1 |
0 |
|
|
|
|
|
|
|
при |
2, |
1, |
|
1 |
, |
0, |
1 |
|
2 |
||||||||
|
|
|
|
|
|
|||
3.3.2.Доказать, что определения 2 и 2' эквивалентны.
3.3.3.Доказать, что определения 3 и 3' эквивалентны.
3.3.4.Доказать замечание 2 к теореме 5.
3.3.5.Сформулировать и доказать теоремы, соответствующие диагональным связям приведенной таблицы.
4.ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
4.1.Общая постановка задачи линейного программирования. Разные формы записи задач линейного программирования
Вобщем виде постановка задача линейного программирования (ЗЛП) выглядит следующим образом:
найти вектор x* |
(x* ,..., x* ) , обеспечивающий критическое |
|
|
1 |
n |
(минимальное или максимальное) значение линейной функции |
||
|
n |
|
z(x) |
c j x j |
|
j1
иудовлетворяющий линейным ограничениям
84
a11x1 |
a12 x 2 |
... |
a1n x n |
( |
)b1, |
|
|
... |
|
|
|
a m1x1 |
a m2 x 2 |
... |
a mn x n |
( |
)bm , |
x1 0;...; x n |
0 ( , нет требования на знак). |
||||
Векторная форма записи:
CT X min
A1X1 ... A n X n B, x 0.
Функцию z(x) называют целевой функцией ЗЛП, ее
критическое значение обозначают z* . Систему ограничений называют допустимым множеством, его элементы – планами задачи.
План x* на котором целевая функция принимает критическое значение называют решением задачи (оптимальной планом).
Рассмотрим наиболее часто используемые формы записи задачи линейного программирования.
Стандартная (симметричная):
n |
|
|
|
|
|
|
|
c j x j |
|
max |
|
j |
1 |
|
|
|
|
n |
|
|
|
|
|
|
|
aij x j |
|
bi , i |
1,..., m , |
j |
1 |
|
|
|
|
x j |
0, |
j |
1,..., n. |
||
Каноническая: |
|
|
|
|
|
n |
|
|
|
|
|
|
|
c j x j |
|
max |
|
j |
1 |
|
|
|
|
n |
|
|
|
|
|
|
|
aij x j |
|
bi , bi |
0, i 1,..., m , |
j |
1 |
|
|
|
|
x j |
0, |
j |
1,..., n. |
||
Независимо от того, как записана исходная задача, ее можно
85
эквивалентно переписать в любой желаемой форме. При этом используется понятие эквивалентности задач.
Две задачи оптимизации называются эквивалентными, если они имеют одно и то же множество оптимальных точек.
Однако, так как при переходе от одного вида задачи к другому возможно изменение размерности задачи (увеличение числа переменных, увеличение числа ограничений), то следует в каждом конкретном случае аккуратно формулировать, как понимается эквивалентность данных задач. Существуют правила, позволяющие осуществить эквивалентные перезаписи задач.
1.Изменение цели критерия оптимизации возможно путѐм умножения исходной целевой функции на -1.
2.Изменение знака неравенства также возможно умножением
|
|
|
n |
его на -1. Ограничение-равенство |
aij x j bi можно записать в |
||
|
|
j |
1 |
виде системы двух неравенств: |
|
||
|
n |
|
|
|
aij x j |
bi , |
|
j |
1 |
|
|
|
n |
|
|
|
aij x j |
bi . |
|
j |
1 |
|
|
4.От ограничений неравенств можно перейти к равенствам, добавляя или отнимая неотрицательные новые переменные (далее –
|
|
|
|
|
|
n |
дополнительные переменные). |
Так, |
неравенство |
aij x j bi |
|||
|
|
|
|
|
j |
1 |
эквивалентно системе |
|
|
|
|
||
|
n |
|
|
|
|
|
|
|
aij x j |
ui |
bi , ui |
0 . |
|
|
j |
1 |
|
|
|
|
|
n |
|
|
|
|
|
Аналогично |
aij x j |
bi |
эквивалентно системе |
|
||
j |
1 |
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
aij x j |
ui |
bi , ui |
0 . |
|
|
j |
1 |
|
|
|
|
5.Обеспечить условие неотрицательности переменных можно, используя очевидный факт: любое число может быть представлено в виде разности двух неотрицательных чисел:
86
x |
j |
x' |
x'' , x' |
0 , |
x'' |
0 . |
|
|
|
j |
j |
j |
|
j |
|
|
|
Если в задаче |
присутствовало требование |
xj 0 , |
||||||
осуществляется замена x j |
x'j , |
x'j |
|
0 . |
|
|
||
В связи с тем, что основной метод решения ЗЛП - симплексный метод предназначен для решения задач в канонической форме, проиллюстрируем работу описанных выше правил на примере приведения задачи к канонической форме.
Пример 1. Привести ЗЛП к канонической форме:
3x1 |
2x 2 |
x 3 |
max, |
|
x1 |
x 2 |
2x 3 |
x 4 |
10, |
2x1 |
x 2 |
|
x 4 |
5, |
x1 |
x 2 |
x 3 |
|
16, |
x1 |
0, x 2 |
0, x 3 |
0. |
|
1. К левой части первого неравенства добавим неотрицательную переменную u1 и перейдем к ограничениям
|
|
|
x1 |
x 2 |
2x3 |
x 4 |
u1 |
10 , u1 |
0 . |
||
2. Умножим обе части второго равенства на –1, к левой части |
|||||||||||
добавим |
|
неотрицательную |
переменную |
u2 |
и |
перейдем к |
|||||
ограничениям |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
2x1 |
x 2 |
x 4 |
u 2 |
5 , u2 |
0 . |
|
|
3. Осуществим замену переменных: |
|
|
|
||||||||
x |
4 |
x' |
x'' |
, x ' |
0 , |
x'' |
0 , x |
|
x' , x' |
0 . |
|
|
4 |
4 |
4 |
|
4 |
1 |
|
1 |
1 |
|
|
В результате задача принимает канонический вид:
3x1' |
2x 2 x 3 |
max |
|
|
|
x1' |
x 2 |
2x 3 x '4 |
x '4' |
u1 |
10, |
2x1' |
x 2 |
x '4 |
x '4' |
u 2 |
5, |
x1' |
x 2 |
x 3 |
|
|
16, |
x1' |
0, x '4 |
0, x '4' |
0, u1 |
0, u 2 0. |
|
87