ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1086
Скачиваний: 2
76
(13)
А
’
1
a
’
1s
+
А
’
2
a’
2s
+ … +
А
’
r
a’
rs
– A
’
s
=
Ө
.
Помножив
соотношение
(13)
на
переменную
t > 0
и
вычтя
его
из
соотношения
(12),
получим
:
А
’
1
(
α
1
– t a
’
1s
) +
А
’
2
(
α
2
– t a’
2s
) + … +
А
’
r
(
α
r
– t a’
rs
) + A
’
s
t = B’.
Из
последнего
соотношения
и
с
учетом
того
,
что
a’
is
≤
0,
следует
,
что
вектор
Α
t
= (
α
1
– t a
’
1s
,
α
2
– t a’
2s
, …,
α
r
– t a’
rs
, 0, …, 0, t, 0, …, 0 )
является
допустимым
решением
задачи
(1) – (3).
По
лемме
о
целевой
функции
для
допустимого
решения
α
е
имеем
f(
α
t
) = f(
α
) –
δ
1
(
α
1
– t a
’
1s
) –
δ
2
(
α
2
– t a’
2s
) – …–
δ
r
(
α
r
– t a’
rs
) –
δ
s
t .
С
учетом
того
,
что
оценки
базисных
векторов
равны
нулю
,
т
.
е
.,
δ
1
=
δ
2
=
…=
δ
r
=0,
значение
целевой
функции
можно
записать
в
виде
: f(
α
t
) = f(
α
) –
δ
s
t.
Так
,
как
δ
s
> 0 ,
то
при
t
→
+
целевая
функция
неограниченно
уменьшается
,
т
.
е
., f(
α
t
)
→
–
,
и
,
следовательно
,
задача
не
имеет
оптимального
решения
.
■
Пример
.
Дано
опорное
решение
α
= ( 2, 0, 3, 0, 7)
КЗЛП
на
минимум
:
f(x)= –4x
1
– 9x
2
– x
3
+ x
4
– x
5
(min)
2x
1
+ 2x
2
+ x
3
– x
4
=7,
x
1
+ x
2
– x
3
– x
4
=5,
x
1
+ 6x
2
– x
3
– x
4
+ x
5
= 6,
x
j
≥
0, j= 1, 2, 3, 4, 5.
Выясним
,
имеет
ли
данная
задача
оптимальное
решение
?
▲
Приведя
систему
векторов
условий
к
симплексной
таблице
,
соответствующей
базису
А
1
,
А
3
,
А
5
данного
опорного
решения
α
= ( 2, 0, 3,
0, 7),
видим
,
что
оценка
δ
4
= 2 >
0,
а
все
остальные
координаты
вектора
А
4
неположительные
.
Следовательно
,
по
доказанной
теореме
,
целевая
функция
неограниченна
снизу
на
множестве
допустимых
решений
,
то
есть
исходная
задача
не
имеет
оптимального
решения
.
■
Ответьте
на
вопросы
1.
Как
получить
симплекс
таблицу
системы
векторов
условий
канонической
задачи
линейного
программирования
?
А
1
А
2
А
3
А
4
А
5
В
2 2 1 –1 0 7
1
1 –1 –1 0 5
1 6 –1 –1 1 6
–
γ
=
4 9 1 –1 1 0
А
1
’
А
2
’
А
3
’
А
4
’
А
5
’
В
’
0 0
–1
1 0 –3
1 1 1 –1 0 5
0 5 –2 0 1 1
0 5 –3 3 1 –20
А
1
’’
А
2
’’
А
3
’’
А
4
’’
А
5
’’
В
’’
0 0 1 –1 0 3
1 1 0 0 0 2
0 5 0 –2 1 7
δ
= 0 0 0 2 0 –18
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
77
2.
Чему
соответствуют
элементы
столбца
ограничений
В
симплекс
таблицы
,
приведенной
к
базису
опорного
решения
?
3.
Какова
величина
оценок
векторов
базиса
опорного
решения
в
соответствующей
симплекс
таблице
?
4.
Чему
соответствует
величина
оценки
столбца
ограничений
В
симплекс
таблицы
,
приведенной
к
базису
опорного
решения
?
5.
Сформулируйте
лемму
о
целевой
функции
.
6.
Приведите
схему
доказательства
леммы
о
целевой
функции
.
7.
Сформулируйте
теорему
о
достаточном
условии
оптимальности
опорного
решения
.
8.
Докажите
теорему
о
достаточном
условии
оптимальности
опорного
решения
.
9.
Сформулируйте
теорему
о
неограниченности
целевой
функции
канонической
задачи
линейного
программирования
на
минимум
.
10.
Докажите
теорему
о
неограниченности
целевой
функции
канонической
задачи
линейного
программирования
на
минимум
.
Решите
самостоятельно
Задача
1.
Доказать
,
что
опорное
решение
α
является
оптимальным
решением
для
данной
КЗЛП
.
1.1.
x
j
≥
0, j = 1, 2, 3,
α
= (1, 1, 0).
1.2.
f(X) =
x
1
+ 2x
2
– 5x
3
(max),
x
1
– 3x
2
+ 11
х
3
=–9,
3x
1
– x
2
+
9x
3
=5,
x
j
≥
0, j = 1, 2, 3,
α
= (3, 4, 0).
Задача
2.
Используя
опорное
решение
α
данной
КЗЛП
,
доказать
неограниченность
ее
целевой
функции
.
2.1.
f(X) = –x
1
– x
2
– x
3
(min),
–2x
1
+ x
2
+
х
3
=4,
–x
1
+ 2x
2
– x
3
=–1,
x
j
≥
0, j = 1, 2, 3,
α
= (0, 1, 3).
2.2.
f(X) = 2x
1
+ x
2
– x
4
(max),
x
1
– x
2
– x
3
=0,
x
1
+ x
2
– x
3
+ 2x
4
=2,
x
j
≥
0, j = 1, 2, 3, 4,
α
= (1, 1, 0, 0).
f(X) = x
1
– 2x
2
+
x
3
(min),
x
1
– x
2
+ 2
х
3
=0,
x
1
+
x
2
+ 5x
3
=2,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
78
2.8.
Решение
симплекс
методом
канонической
задачи
линейного
программирования
Рассмотрим
каноническую
задачу
линейного
программирования
3.
f(X) =
n
j
1
γ
j
x
j
+
γ
0
,
4.
n
j
1
А
j
x
j
=B,
5.
x
j
≥
0, j=1,2,…,n.
Пусть
вектор
α
опорное
решение
данной
задачи
.
Выберем
некоторый
базис
этого
опорного
решения
,
например
,
В
1
, …,
В
l
, …,
В
k
, …,
В
r
,
т
.
е
.,
опорное
решение
имеет
вид
α
= ( 0, …, 0,
α
1
, 0, …,, 0,
α
l
, 0, …, 0,
α
k
, 0,…, 0,
α
r
, 0, 0, .., 0).
Приведя
систему
векторов
условий
к
базису
выбранного
опорного
решения
,
получим
симплекс
таблицу
…
B
1
’
…
B
l
’
…
B
k
’
…
B
r
’
… A
s
’
…
B
’
…
1 … 0 … 0 … 0 … a’
1s
…
α
1
…
… …
… … … … … … … … …
(4) … 0 … 1 … 0 … 0 … a’
ls
…
α
l
… … … … … … … … … … … …
… 0 … 0 … 1 … 0 … a’
ks
…
α
k
… … … … … … … … … … … …
… 0 … 0 … 0 … 1 … a’
rs
…
α
r
…
0
… 0 … 0 … 0 …
δ
s
…
δ
0
1.
Если
любой
вектор
системы
условий
задачи
в
полученной
симплекс
таблице
имеет
неположительную
оценку
,
т
.
е
.,
δ
j
≤
0
для
всех
j=1, 2, …, n,
то
опорное
решение
α
является
оптимальным
решением
данной
задачи
(
теорема
о
достаточном
условии
оптимальности
опорного
решения
).
2.
Если
в
симплекс
таблице
существует
s-
й
столбец
с
положительной
оценкой
,
т
.
е
.
δ
s
> 0,
где
s=1, 2, …, n ,
а
все
остальные
элементы
s-
го
столбца
неположительные
,
т
.
е
,
α
is
≤
0, i=1, 2, …, r ,
то
целевая
функция
данной
задачи
неограниченна
на
множестве
допустимых
решений
,
и
,
следовательно
,
задача
не
имеет
оптимального
решения
(
теорема
о
неограниченности
целевой
функции
).
3.
Если
оценка
s-
го
столбца
положительная
,
т
.
е
.
δ
s
> 0,
где
s=1, 2, …, n,
но
при
этом
среди
элементов
этого
столбца
найдется
положительный
,
т
.
е
,
α
’
is
>0,
i=1, 2, …, r ,
то
рассматриваются
отношения
вида
is
i
a
'
для
всех
a’
is
> 0 ,
среди
которых
выбирается
наименьшее
.
Пусть
это
будет
отношение
ks
k
a
'
=
min
0
'
is
a
{
is
i
a
'
}.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
79
Затем
проводится
преобразование
Жордана
симплекс
таблицы
(4)
с
разрешающим
элементом
α
’
ks
.
При
этом
k-
ю
строку
помножаем
на
1 /
α
’
ks
,
далее
эту
же
строку
поочередно
прибавляем
к
строке
i,
где
i = 1, 2, …, r,
и
к
строке
оценок
,
предварительно
помножив
соответственно
на
величину
(–
α
’
is
)
и
на
(–
δ
s
) .
После
такого
преобразования
будет
получена
симплекс
таблица
(5),
приведенная
к
базису
,
отличному
от
предыдущего
,
так
как
вектор
В
k
уступил
место
вектору
А
s
.
…
B
1
’
’
…
B
l
’’
…
B
k
’’
…
B
r
’’
… A
s
’’
…
B
’’
…
1 … 0 … –a’
1s
/ a’
ks
…
0
…
0
…
α
1
–a’
1s
α
k
/ a’
ks
…
… …
…
… … … …
… …
… …
(5) … 0 … 1 … –a’
ls
/ a’
ks
…
0
…
0
…
α
l
–a’
1s
α
k
/ a’
ks
… … … … …
…
… … … … …
…
… 0 … 0 … 1
/ a’
ks
…
0 …
1
…
α
k
/ a’
ks
… … … … …
…
… … … … …
…
… 0 … 0 … –a’
rs
/ a’
ks
…
1
…
0
…
α
r
–a’
rs
α
k
/ a’
ks
… 0
… 0 … –
δ
s
/ a’
ks
…
0 …
0
…
δ
0
–
δ
s
α
k
/ a’
ks
Симплекс
таблица
(5)
обладает
следующими
свойствами
:
1
0
.
Она
приведена
к
базису
В
1
, …, B
l
, …, B
k–1
, B
k+1
, …, B
r
, …, A
s
.
2
0
.
Все
элементы
столбца
ограничений
неотрицательные
.
▲
Так
как
вектор
α
является
опорным
решением
рассматриваемой
задачи
,
то
α
k
≥
0.
По
выбору
α
’
ks
> 0,
следовательно
,
ks
k
a
'
≥
0.
Тогда
для
любых
a’
is
≤
0
будет
выполняться
неравенство
α
i
–a’
is
α
k
/ a’
ks
≥
0,
а
для
всех
a’
is
> 0
будем
иметь
α
l
–a’
1s
α
k
/ a’
ks
= a’
is
(
α
i
/ a’
is
–
α
k
/ a’
ks
)
≥
0,
т
.
к
.
ks
k
a
'
=
min
0
'
is
a
{
is
i
a
'
}.
■
3
0
.
Таблица
приведена
к
базису
опорного
решения
α
’ = (0, …, 0,
α
1
–a’
1s
α
k
/ a’
ks
,
0, …, 0,
α
l
–a’
1s
α
k
/ a’
ks
, 0, …, 0,
α
r
–a’
rs
α
k
/ a’
ks
, 0, …, 0,
α
k
/ a’
ks
, 0, …, 0),
на
котором
значение
целевой
функции
не
больше
,
чем
на
предыдущем
опорном
решении
α
,
т
.
е
., f(
α
’)
≤
f(
α
).
▲
Из
таблицы
(4)
следует
,
что
f(
α
) =
δ
0
.
Так
как
α
k
≥
0,
δ
s
> 0,
α
’
ks
> 0,
то
f(
α
’) =
δ
0
–
δ
s
ks
k
a
'
≤
δ
0
= f(
α
).
■
Замечания
1)
Если
α
k
> 0,
то
приходим
к
такому
новому
опорному
решению
α
’,
для
которого
f(
α
’) < f(
α
).
Если
же
α
k
=0,
то
α
’ =
α
и
произошел
переход
к
новому
базису
исходного
опорного
решения
α
.
2)
Поиск
оптимального
решения
симплекс
методом
можно
ускорить
,
если
при
переходе
от
одного
опорного
решения
к
другому
выбирать
тот
разрешающий
элемент
α
’
ks
,
который
соответствует
наибольшему
из
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
80
произведений
вида
{
δ
s
ks
k
a
'
}
по
всем
δ
s
> 0
и
по
всем
α
’
ks
>0.
При
этом
значение
целевой
функции
уменьшается
на
максимально
возможную
величину
.
3)
Если
с
помощью
симплекс
метода
будут
найдены
два
оптимальных
решения
α
’
opt
и
α
’’
opt
,
то
линейная
комбинация
этих
оптимальных
решений
вида
α
=
λ
1
α
’
opt
+
λ
2
α
’’
opt
,
где
λ
1
+
λ
2
= 1,
λ
1
≥
0,
λ
2
≥
0,
будет
также
оптимальным
решением
.
Принимая
симплекс
таблицу
(5)
за
исходную
,
повторяем
всю
процедуру
.
Пример
.
Дано
опорное
решение
α
= (0, 0, 4, 8, 3)
КЗЛП
вида
f(x)= –2x
1
– 5x
2
–
x
3
+ x
4
– 2x
5
(min)
x
1
+ 4x
2
– x
3
+ 2x
4
=12,
2x
1
+ 3x
2
+ 2x
4
– x
5
=13,
2x
1
+ 3x
2
+ x
3
+ x
4
+ x
5
=15,
x
j
≥
0, j=1, 2, 3, 4,5
Используя
симплекс
метод
,
найти
оптимальное
решение
.
▲
Приведем
систему
векторов
условий
задачи
и
строку
с
противоположенными
значениями
коэффициентов
целевой
функции
к
симплекс
таблице
,
соответствующей
базису
А
3
,
А
4
,
А
5
опорного
решения
α
= (0, 0, 4, 8, 3).
В
симплекс
таблице
№
4
векторы
А
1
и
А
2
имеют
положительные
оценки
δ
1
=2
и
δ
2
=5.
Следовательно
,
данное
опорное
решение
не
является
оптимальным
.
Для
перехода
к
новому
опорному
решению
выбираем
разрешающий
элемент
,
используя
оба
критерия
.
Сначала
находим
min
0
'
is
a
{
is
i
a
'
}
для
1-
го
min {8/1, 4/1}=4
и
2-
го
столбца
min{3/1, 8/2}=3.
Затем
для
уменьшения
числа
итераций
находим
max{
δ
1
* 4;
δ
2
*3}= max{2* 4; 5*3}=15.
Таким
образом
,
преобразование
Жордана
проводим
с
разрешающим
элементом
а
12
=1.
Получаем
симплекс
А
1
А
2
А
3
А
4
А
5
В
1 4 –1 2 0 12
2 3 0 2 –1 13
№
1
2 3
1
1 1 15
–
γ
=
2
5
1
–1
2
0
3 7 0 3
1
27
2 3 0 2 –1 13
№
2
2 3 1 1 1 15
0
2
0
–2
1
–15
3 7 0 3 1 27
5 10 0
5
0 40
№
3
–1 –4 1 –2 0 –12
–3
–5
0
–5
0
–42
0
1
0 0 1 3
1 2 0 1 0 8
№
4
1 0 1 0 0 4
δ
=
2
5
0
0
0
–2
0 1 0 0 1 3
1
0 0 1 –2 2
№
5
1 0 1 0 0 4
δ
=
2
0
0
0
–5 –17
0 1 0 0 1 3
1 0 0 1 –2 2
№
6
0 0 1 –1 2 2
δ
=
0
0
0
–2
–1 –21
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.