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

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

Пример 1.
 
max;
48 56 25 30 4
3 2
1





x
x
x
x
X
F


9
,
1 0
50 30 18 14 22 106 16 8
14 10 268 30 18 14 22 51 4
2 5
3 9
8 4
3 2
1 7
4 3
2 1
6 4
3 2
1 5
4 3
2 1























j
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
j
Определим начальный опорный план полученной задачи. При постановке этой задачи сформирован единичный базис


4 4
9 7
6 5
,
,
,


E
A
A
A
A
искомого начального опорного плана задачи. Его компоненты
8 4
3 2
1
,
,
,
,
x
x
x
x
x
являются небазисными и поэтому приравниваются нулю. Тогда из системы ограничений найдутся значения базисных компонент
50
,
106
,
268
,
51 9
7 6
5




x
x
x
x
Итак, в качестве начального опорного плана задачи может быть взят вектор



50
;
0
;
106
;
268
;
51
;
0
;
0
;
0
;
0 0

X
Решение задачи будем проводить в соответствии с первым алгоритмом симплекс-метода. Составим таблицу, соответствующую исходному опорному плану (0-й итерации). Так как


9 7
6 5
0
,
,
,
A
A
A
A
P

- базис начального опорного плана


50
,
0
,
106
,
268
,
51
,
0
,
0
,
0
,
0 0

X
, является единичной матрицей, то обратная матрица
1 0

P также является единичной и поэтому коэффициентами разложения векторов условий
j
A по этому базису
0
P
являются коэффициенты системы ограничений.
Для заполнения


1

m
-й строки симплекс-таблицы вычислим значения линейной формы
 
0
X
F
и оценок
j

,
9
...,
,
1

j
векторов условий
9
...,
,
1
,

j
A
j
по приведѐнным в описании первого алгоритма формулам следующим образом:
 
0 0
1 0
0 0
0 0
0 0
;
25 25 14 0
14 0
14 0
5 0
;
30 30 22 0
10 0
22 0
3 0
;
0 50 0
106 0
268 0
51 0
9 2
1 0
0














































X
F
F
Весь процесс решения приведен в табл. 3.1, которая состоит из двух частей, отвечающих 0-й (исходная таблица) и 1-й итерациям.
Заполняем таблицу 0-й итерации.
Среди оценок
9
...,
,
1
,


j
j
имеются отрицательные. Значит, исходный опорный план не является оптимальным. Перейдем к новому базису путѐм операции однократного замещения. В базис будет введѐн вектор
3
A
с наименьшей оценкой
56 3



. Значения t вычисляются для всех позиций столбца t (так как все элементы разрешающего столбца положительны). Наименьший элемент
9 7
2 0

t
достигается на четвертой позиции базиса. Значит, четвертая строка является разрешающей строкой, и

вектор
9
A
подлежит исключению из базиса. Разрешающий элемент – элемент
(4;3), равный 18.
0 итерация
C
30 25 56 48 0
0 0
0 0
N
x
C
P
B
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
A
9
A
t
1 0
5
A
51 3
5 2
4 1
0 0
0 0
25 1/2 2
0 6
A
268 22 14 18 30 0
1 0
0 0
14 8/9 3
0 7
A
106 10 14 8
16 0
0 1
0 0
13 1/4 4
0 9
A
50 22 14 18 30 0
0 0
-1 1
2 7/9
=
0
t
m+1
-
-
0
-30
-25
-56
-48 0
0 0
0 0
-
1 итерация
Составим таблицу, отвечающую первой итерации.
В столбце P, в четвертой позиции место вектора
9
A
займѐт вектор
3
A
Соответствующий ему коэффициент линейной формы
56 3

c
помещаем в четвертой позиции столбца
x
C
. Затем заполняется строка А3 новой симплекс-таблицы. Для этого все элементы этой строки старой таблицы делятся на разрешающий элемент (на 18).
N
x
C
P
B
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
A
9
A
t
1 0
5
A
2 0
6
A
3 0
7
A
4 56 3
A
2 7/9 1 1/9 7/9 1
1 2/3 0
0 0
-1/18 1/18 m+1
-
-
Все остальные
i
-тые строки главной части новой симплекс-таблицы получить как результат вычитания из
i
-той строки старой симплекс-таблицы четвертой строки новой симплекс-таблицы, умноженной на соответствующий
i
-тый элемент разрешающего столбца:

N
x
C
P
B
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
A
9
A
t
1 0
5
A
45 4/9 5/9 3 4/9 0
2/3 1
0 0
1/9
-1/9 409 2
0 6
A
218 0
0 0
0 0
1 0
1
-1 218 3
0 7
A
83 7/9 2/9 7 7/9 0
2 2/3 0
0 1
4/9
-4/9 188 1/2 4
56 3
A
2 7/9 1 1/9 7/9 1
1 2/3 0
0 0
-1/18 1/18
+∞ m+1
-
-
155 5/9 38 4/9 18 5/9 0
45 1/3 0
0 0
-3 1/9 3 1/9
-
В симплекс-таблице первой итерации также есть отрицательные оценки, поэтому опорный план опять не оптимален. Минимальное отрицательное значение получаем для столбца А
8
, следовательно, в базис будет введен столбец А
8
(А
8
-разрешающий столбец). При определении разрешающей строки получили, что из базиса будет выведена строка А
7
Таблица второй итерации будет иметь вид:
2 итерация
N
x
C
P
B
1
A
2
A
3
A
4
A
5
A
6
A
7
A
8
A
9
A
1 0
5
A
24 1/2 1/2 1 1/2 0
0 1
0
-1/4 0
0 2
0 6
A
29 1/2
-1.2
-17 1/2 0
-6 0
1
-2 1/4 0
0 3
0 8
A
188 1/2 1.2 17 1/2 0
6 0
0 2 1/4 1
-1 4
56 3
A
13 1/4 1 1/4 1 3/4 1
2 0
0 1/8 0
0 m+1
-
-
742 40 73 0
64 0
0 7
0 0
Так как после завершения второй итерации все оценки
0


j
, то полученный опорный план







0
,
2 1
188
,
0
,
2 1
29
,
2 1
24
,
0
,
4 1
13
,
0
,
0 2
X
является оптимальным опорным планом задачи. Максимальное значение линейной формы равно
 
742 2

X
F
Методы построения начального опорного плана
Алгоритм построения начального опорного плана
Метод последовательного улучшения плана, который применяется для решения ЗЛП, предполагает знание некоторого исходного опорного плана.
Однако, далеко не всегда такой начальный опорный план может быть указан

без каких-либо вычислений. Это возможно лишь в случае, когда среди столбцов
j
A матрицы условий
A найдѐтся достаточное количество таких столбцов, из которых составится единичная матрица и эта матрица будет являться базисом искомого начального плана.
Если же такой возможности нет, то для построения начального опорного плана ЗЛП решается вспомогательная ЗЛП (так называемая

L
задача) с расширенным вектором X , состоящим из вектора X исходной
ЗЛП, дополненного искусственными неотрицательными компонентами
m
i
x
i
n
...,
,
1
,


. Последние вводятся в систему ограничений так, чтобы сформировался искусственный единичный базис.
Итак, начальный опорный план задачи может быть найден с помощью следующей вспомогательной ЗЛП (L - задачи):
 
max;
1






m
i
i
n
x
X
L
( 2)


;
,
1 1
m
i
b
x
x
a
i
i
n
n
j
j
ij






( 3)


,
1 0
m
n
j
x
j



( 4)
Так как матрица условий ЗЛП (4.41)-(4.43) уже содержит единичную подматрицу


,
...,
,
,
2 1
m
n
n
n
A
A
A
E




которая может быть взята в качестве базиса опорного плана, то начальным опорным планом этой

L задачи будет являться вектор


m
b
b
b
X
...,
,
,
,
0
...,
,
0
,
0 2
1 0

, у которого небазисные компоненты
,
...,
,
2
,
1
,
0
n
j
x
j


а базисные
m
i
b
x
i
i
n
...,
,
2
,
1
,



Решая сформулированную

L
задачу, например, первым алгоритмом симплекс - метода, с указанным начальным планом
0
X , в силу ограниченности линейной формы
 
X
L
сверху на множестве своих планов (

 
0

X
L
) окажется, что процесс решения через конечное шагов приведет к оптимальному опорному плану вспомогательной задачи.
Пусть


*
*
1
*
*
1
*
...,
,
,
,
,
m
n
n
n
x
x
x
x
X




- оптимальный опорный план

L
задачи, у которого все искусственные компоненты равны нулю. Тогда вектор


*
*
1 0
,
,
n
x
x
X


является опорным планом исходной задачи. Действительно, все дополнительные переменные
m
i
x
i
n
...,
,
1
,
0
*



. Значит, компоненты вектора
0
X удовлетворяют ограничениям исходной задачи, т.е. вектор
0
X является некоторым планом исходной задачи. По построению план
0
X является также опорным.
Алгоритм искусственного базиса
Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М-задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача.
Расширенная
М-задача применительно к исходной задаче записывается следующим образом:
 


max
1 1








m
i
i
n
n
j
j
j
x
M
x
c
X
L
;
( 5)
i
n
j
i
n
j
ij
b
x
x
a





1


m
i
,
1

;
( 6)
0

j
x


m
n
j


,
1
( 7)
Здесь
0

M
- достаточно большое число.
Начальный опорный план задачи (5) – (7) может быть назначен непосредственно, так как в матрице условий этой задачи уже сформирована единичная подматрица, которая и составит его базис



m
n
n
n
A
A
A
P




,...,
,
2 1
0
. Поэтому вектор


m
b
b
b
X
...,
,
,
,
0
...,
,
0
,
0 2
1 0

с компонентами
0

j
x


n
j
,
1

,
i
i
n
b
x




m
i
,
1

и будет являться начальным опорным планом задачи (4.44) – (4.46). Переменные
i
n
x



m
i
,
1

называются
искусственными переменными.
Таким образом, исходная задача линейного программирования с неизвестным заранее начальным опорным планом сводится к М-задаче, начальный опорный план которой может быть указан непосредственно. В процессе решения этой расширенной задачи можно либо вычислить оптимальный план исходной задачи, либо убедиться в еѐ неразрешимости, если оказывается неразрешимой М-задача.