Лекция_1_merged. Лекция 1. Предмет и задачи методов оптимизации

• Название: Лекция 1. Предмет и задачи методов оптимизации
• Дата: 05.02.2022
• Размер: 3.42 Mb.
• Имя файла: Лекция_1_merged.pdf
• Тип: Лекция; #352185
• страница: 8 из 9

целевой функцией (или линейной формой) задачи (1)-(4), а условия (2)-(4) – ограничениями данной задачи.
Определение 1. Вектор-столбец


)
,...,
(
1
n
x
x
X
, координаты которого удовлетворяют всем ограничениям задачи, называется допустимым
вектором или планом ЗЛП.
План


)
,...,
,
(
*
*
2
*
1
n
x
x
x
X
, при котором целевая функция задачи (1) принимает свое максимальное значение, называется оптимальным.
Вектор
)
,...,
(
1
n
c
c
C

- вектор-строка коэффициентов линейной формы задачи. Вектор


)
,...,
(
1
m
b
b
B
- вектор ограничений ЗЛП. Вектора

n
j
a
a
a
A
mj
j
j
j
,
1
,
)
,...,
,
(
2 1



- вектора условий. Матрица
)
,...,
,
(
2 1
n
A
A
A
A

-
матрица условий размерности
n
m

.
Определение
2.
Множество векторов
X, удовлетворяющих ограничениям задачи, составляет множество допустимых планов данной задачи
M=


0
,



X
B
AX
E
X
n
В теории линейной оптимизации доказано, что множество
допустимых планов ЗЛП
M
является выпуклым, замкнутым
многогранным множеством (без доказательства).
Определение 3. Точка
0
X называется угловой точкой множества M, если никакой отрезок, содержащий
0
X в качестве своей внутренней точки, не содержится целиком во множестве M.
Х
0
М
Х
1
Х
2
Определение 4. План ЗЛП, соответствующий угловой точке множества планов называется опорным планом.
Определение 5. Базисом опорного плана называется любая система из
r (где
rangA
r

) линейно независимых столбцов
A
, включающая все столбцы, соответствующие положительным координатам
0

i
x
. Столбцы, входящие в базис, называются базисными. Составляющие опорного плана,

соответствующие базисным столбцам называются
базисными
компонентами.
Определение 6. Опорный план называется невырожденным, если число положительных компонент равно рангу матрицы условий. Опорный план называется вырожденным, если число положительных координат меньше ранга матрицы условий.
Канонической или основной задачей линейного программирования называется задача, которая состоит в определении максимального значения функции max
)
(
1





n
j
j
j
x
c
X
f
( 5) при выполнении условий только типа равенств:




n
j
i
j
ij
m
i
b
x
a
1
,
1
,
;
( 6)
n
j
x
j
,
1
,
0


,
( 7) где
m
i
b
i
,
1
,
0


Каноническая ЗЛП (5) - (7), может быть записана также в векторной форме:
0
;
max;
)
,
(
)
(
2 2
1 1







X
B
A
x
A
x
A
x
X
C
X
F
n
n
или более компактно – вматричной форме:


0
,
|
)
(
max



X
B
AX
CX
X
F
Любую ЗЛП можно привести к канонической форме.
Большинство алгоритмов, разработанных для решения ЗЛП, применяются для ее канонической формы.

Приведение общей ЗЛП к канонической форме
Чтобы перейти от общей формы записи ЗЛП к канонической, нужно в общем случае уметь:
1. сводить задачу минимизации к задаче максимизации,
2. переходить от ограничений-неравенств к ограничениям равенствам,
3. заменять переменные, которые не подчинены условию неотрицательности.
1.
В том случае, когда требуется найти минимум функции
n
n
x
c
x
c
x
c
F




2 2
1 1
, можно перейти к нахождению максимума функции
n
n
x
c
x
c
x
c
F
F







2 2
1 1
1
, поскольку
)
max(
min
F
F


2. Ограничения-неравенства исходной ЗЛП можно преобразовать в ограничения-равенства добавлением к их левой части дополнительной неотрицательной переменной со знаком "+" в случае неравенства вида "
" и со знаком "-" - в случае неравенства вида " ". Таким образом, ограничение-неравенство
i
n
in
i
i
b
x
a
x
a
x
a




2 2
1 1
преобразуется в ограничение-равенство
)
0
(
1 1
2 2
1 1








n
i
n
n
in
i
i
x
b
x
x
a
x
a
x
a
,
а ограничение-неравенство
i
n
in
i
i
b
x
a
x
a
x
a




2 2
1 1
- в ограничение-равенство
)
0
(
1 1
2 2
1 1








n
i
n
n
in
i
i
x
b
x
x
a
x
a
x
a
3. Если на переменную
j
x
не наложено условие неотрицательности, то эту переменную надо представить в виде разности двух новых неотрицательных переменных:
2 1




n
n
j
x
x
x
,
0
,
0 2
1




n
n
x
x
Пример 1. Записать в канонический форме следующую задачу линейного программирования: найти минимум функции
4 3
2 1
2
x
x
x
x
F





, при условиях




























0
,
0
,
15 3
5 3
,
10 2
2 3
,
8 2
,
6 2
2 1
4 3
2 1
4 3
2 1
4 3
2 1
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Так как на переменные
4 3
, x
x
не наложено условие неотрицательности, то необходимо произвести следующую замену переменных:
,
8 7
4 6
5 3
x
x
x
x
x
x




Вместо нахождения минимума функции F можно найти максимум функции
F
F


1
при ограничениях, получающихся из ограничений- неравенств исходной задачи с помощью дополнительных неотрицательных переменных с соответствующим знаком.
В первое ограничение системы добавим переменную
9
x со знаком «+», во второе ограничение – переменную
10
x со знаком «-» и в третье ограничение системы – переменную
11
x со знаком «+».
Следовательно, исходная задача может быть записана в канонической форме так: найти максимум функции
8 7
6 5
2 1
2
x
x
x
x
x
x
F







при условиях:






































11
,
1
,
0
,
15 3
3 5
5 3
,
10 2
2 2
2 3
,
8 2
,
6 2
8 7
6 5
2 1
11 8
7 6
5 2
1 10 8
7 6
5 2
1 9
8 7
6 5
2 1
i
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
i
Графический метод решения ЗЛП
Рассмотрим ЗЛП в канонической форме:


0
,
max



X
B
AX
CX
F
Пусть
)
,...,
,
(
2 1
n
c
c
c
C

- ненулевой вектор, тогда линейная форма задачи задает в пространстве
n
E семейство параллельных гиперплоскостей

линейной формы











,
CX
E
X
n
, нормальным вектором которых является вектор C. Если

- фиксированное значение, то гиперплоскость


CX
делит все пространство на два полупространства:
нижнее





CX
E
X
n
:
и верхнее





CX
E
X
n
:
Х
1
Х
2 f(X)
Плоскость CХ
Линия уровня λ
Гиперплоскость
CХ=λ
Проекция линии уровня λ
Опорная гиперплоскость
CХ=λ*
Рис. 1. Графическая иллюстрация параметров ЗЛП.
Если существует
*
X :
M
X
CX
CX
X
F





,
)
(
*
*

, то
*
X -
оптимальный опорный план. Гиперплоскость


*



CX
E
X
n
- опорная
гиперплоскость множества М в точке
*
X . Причем по отношению к опорной гиперплоскости все множество М находится в нижнем полупространстве, т.к.
*
)
(
:





CX
X
F
M
X
. Поэтому для графического решения задачи необходимо найти опорную гиперплоскость, по отношению к которой все множество М находится в нижнем полупространстве.
Таким образом, графический метод решения ЗЛП заключается в перемещении гиперплоскости линейной формы из некоторого начального положения
0


CX
по направлению вектора С до такого положения, когда

при дальнейшем смещении гиперплоскость уже не будет иметь общих с множеством М точек. Пересечение опорной гиперплоскости с множеством М
и будетявляется решением ЗЛП.
Для того чтобы решить графически ЗЛП необходимо выполнить следующие действия.
1.
Построить множество допустимых планов задачи. В общем случае оно представляет собой выпуклый многогранник. Если ограничения в задаче несовместны, множество допустимых планов является пустым множеством, а задача поиска экстремума не имеет смысла.
2.
Построить вектор С с началом в некоторой точке
0
X .
3.
Построить гиперплоскость линейной формы (линию уровня) проходящую через точку
0
X .
4.
Передвигать гиперплоскость линейной формы параллельно самой себе в направлении вектора C (так как вектор
)
( X
F
grad
C

задает направление возрастания F(X)) до получения опорной гиперплоскости.
Замечание. В случае непустого множества допустимых планов возможны три типовых ситуации: а) опорная гиперплоскость касается множества допустимых планов в одной точке (задача имеет единственное решение); б) опорная гиперплоскость касается множества допустимых планов вдоль стороны многоугольника (задача имеет бесконечное множество решений); в) опорная гиперплоскость не определяется (задача не имеет решения).
Пример 2. Решить графически двумерную задачу линейного программирования: max
4 2
)
(
2 1



x
x
X
F











0
,
0
,
1600 5
2
,
1700 4
3 2
1 2
1 2
1
x
x
x
x
x
x

1. Легко проверить, что четырехугольник OABC на рис 4.6 является областью содержащей точки, для которых выполнены все ограничения задачи. Точки, лежащие внутри и на границе этой области являются допустимыми планами.
2. Построим вектор С=(2,4), с началом в некоторой точке D с координатами (100; 100). Очевидно, что вектор С, в силу линейности функции
)
( X
F
, будет перпендикулярен линиям уровня.
3. Построим линию уровня, проходящую через выбранную точку D.
Подставим координаты точки D в целевую функцию
)
( X
F
:
600 100 4
100 2
)
100
,
100
(





F
Уравнение линии уровня, соответствующей данному значению
)
( X
F
будет иметь следующий вид
600 4
2 2
1


x
x
. Построим полученную прямую (на рис.4.6 она обозначена
(3')).
Рис.4.6. К примеру 4.6
4. Перемещая гиперплоскость линейной формы (линию уровня) из начального положения по направлению вектора С находим крайнее положение, определяющее опорную гиперплоскость. Поскольку полученная

нами опорная гиперплоскость пересекается с множеством М в точке В, то наша задача имеет единственное решение.
Точка
B
расположена на пересечении двух прямых (1') и (2'), поэтому, чтобы найти ее координаты необходимо решить следующую систему уравнений:













200
,
300
,
1600 5
2
,
1700 4
3 2
1 2
1 2
1
x
x
x
x
x
x
Таким образом
)
200
;
300
(
*

X
- точка, соответствующая оптимальному решению задачи со значением функции
1400
)
(
*

X
F

Лекция №9
Симплекс-метод решения ЗЛП.
Приведѐм описание алгоритма применительно к ЗЛП, записанной в канонической форме с односторонними ограничениями:

















n
j
j
i
j
ij
n
j
j
j
n
j
x
m
i
b
x
a
x
c
X
F
1 1
,...,
1
,
0
;
,...,
1
,
)
(
max
( 1)
Пусть известен начальный опорный план


0
,...
0
,...,
,
0 2
0 1
0
x
x
X

с базисом
)
,...,
,
(
2 1
0
m
A
A
A
P

, т.е.
m
j
x
j
,...,
1
,
0 0


- базисные компоненты,
n
m
j
x
j
,...,
1
,
0 0



- небазисные компоненты.
Вычисления удобно выполнять, заполняя следующую симплекс- таблицу:
C
1
c
…
k
c
…
n
c
№
x
C
P
B
1
A
…
k
A
…
n
A
t
1 1
c
1
A
0 1
x
11

…
k
1

…
n
1

… … … …
… … … … …
l
l
c
l
A
0
l
x
1
l

… …
n
l ,

0
t
… … … …
… … … … …
m
m
c
m
A
0
m
x
mk

…
mk

…
mn

1

m
)
(
0
X
F
1

…
k

…
n

Порядок вычислений по алгоритму:
Шаг 1. Найти обратную к
0
P
матрицу
1 0

P
Шаг 2. Вычислить коэффициенты разложения векторов условий
,
j
A
n
j
,...,
1

по базису
0
P
, используя расчѐтную формулу:
n
j
A
P
j
mj
j
,
1
,
1 0
1
















и заполнить ими столбцы
j
A симплекс-таблицы нулевой итерации.

Шаг 3. Вычислить значение линейной формы



m
j
j
j
x
c
X
F
1 0
0
)
(
, как скалярное произведение


B
C
x
,
соответствующих столбцов симплекс- таблицы, и значения оценок
j

векторов условий
j
A относительно базиса
0
P
в соответствии с формулой
n
j
c
c
m
i
j
i
ij
j
,...,
1
,
1







как скалярное произведение столбцов
x
C
и
j
A симплекс-таблицы без коэффициента
j
c , т.е. по расчѐтной формуле
,...,
1
,
)
,
(
n
j
c
A
C
j
j
x
j




Полученными значениями заполнить
)
1
(

m
строку симплекс-таблицы.
Шаг 4. Проверить оптимальность опорного плана.

Если
n
j
j
,
1
,
0




, то
0
X - оптимальный опорный план и, тогда, в столбце B симплекс-таблицы записано решение ЗЛП, а именно, значения базисных компонент оптимального опорного плана и соответствующее ему максимальное значение линейной формы. На этом процесс решения ЗЛП завершается.

Если хотя бы в одном столбце с отрицательной оценкой
)
0
(


s
все элементы меньше или равны 0
)
0
(

is

, то линейная форма
)
( X
F
не ограничена сверху и решения ЗЛП не существует. На этом процесс решения
ЗЛП также завершается.

Если же в каждом столбце с отрицательными оценками найдется хотя бы один положительный элемент
)
0
(


is

, то для построения нового опорного плана необходимо найти вектор, который будет вводиться в базис.
Он определяется по номеру наименьшей отрицательной оценки
j
j
k
j





0
:
min и, таким образом, определяется разрешающий столбец
k
A
Шаг 5. Определить вектор, исключаемый из базиса для чего необходимо заполнить последний столбец
t
симплекс-таблицы нулевой итерации путем деления элементов столбца B на соответствующие им по

номеру положительные элементы разрешающего столбца
k
A
, т.е.
0
,
0


ik
ik
i
i
x
t


,
При этом, в строках столбца
t
, соответствующих неположительным элементам
0

ik

, записываем


, не выполняя деления.
Далее необходимо выбрать
 
i
t
t
min
0

. Если
0
t
достигается на нескольких позициях столбца
t
, то из базиса может быть исключен любой из векторов
0
:
t
t
A
j
j

. Для определенности, договоримся исключать из них вектор с наименьшим номером.
Пусть
0
t
получился на
l -той позиции, т.е.
lk
l
x
t

0 0

, тогда соответствующий этому индексу вектор
l
A
должен выводиться из базиса.
Строка симплекс-таблицы, соответствующая этому индексу, называется разрешающей строкой. Элемент
lk

, стоящий на пересечении разрешающей строки и разрешающего столбца называется разрешающим элементом. На этом нулевая итерация завершена и надлежит приступить к выполнению следующей итерации.
Шаг 6.
Заполнить новую симплекс-таблицу в следующей последовательности.

На l -тых позициях столбцов
x
C
и
P записать соответственно
k
c
и
k
A
, а на остальных позициях этих столбцов оставить прежние элементы.

Заполнить l -тую строку новой симплекс-таблицы (в ней теперь стоит А
к
) элементами
n
j
x
lj
l
,...,
1
,
,
1 1


, получающимися делением соответствующих элементов (
n
j
x
lj
l
,...,
1
,
,


)
l -той строки старой симплекс-таблицы на разрешающий элемент
lk

, т.е. по формулам
n
j
a
x
x
lk
lj
lj
lk
l
l
,...,
1
,
,
1 1








Все остальные i -тые строки главной части новой симплекс- таблицы получить как результат вычитания из i -той строки старой симплекс- таблицы l -той строки новой симплекс-таблицы, умноженной на соответствующий i -тый элемент разрешающего столбца, т.е. в соответствии с рекуррентными формулами
,
1 1
lk
l
i
i
x
x
x



ik
lj
ij
ij




1 1


m
i
,...,
1

,
n
j
,...,
1

. По аналогичным формулам вычисляются также и элементы
)
1
(

m
-й строки новой таблицы:
k
l
x
X
F
X
F



1 1
)
(
)
(
,
k
lj
j
j





1 1

,
n
j
,...,
1

Этим завершается построение новой симплекс-таблицы.
Описанный процесс построения симплекс-таблиц повторяется до получения оптимального опорного плана или до установления неограниченности линейной формы, т.е. неразрешимости ЗЛП.
Если среди оценок
j

небазисных векторов условий
j
A относительно базиса найденного оптимального опорного плана найдется хотя бы одна равная нулю, то это означает, что ЗЛП имеет неединственное решение.