ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1087
Скачиваний: 2
66
x
j
≥
0, j=1, 2, 3, 4.
А
1
,
А
2.
А
3.
Задача
4.
Найти
все
опорные
решения
для
системы
условий
канонической
задачи
линейного
программирования
:
4.1.
x
1
– 2x
2
– x
3
+ x
4
=–1,
2x
1
+ x
2
– x
3
+ 2x
4
=3,
x
j
≥
0, j=1, 2, 3, 4.
4.2.
x
1
+ 2x
2
+ x
3
=4
2x
1
+ 2
х
2
+ 5x
3
=5
x
j
≥
0, j=1, 2, 3.
4.3.
4x
1
+ 5x
2
+ x
3
+ x
4
=29,
6x
1
– x
2
– x
3
+ x
4
=11,
x
j
≥
0, j=1, 2, 3, 4.
4.4.
x
1
+ 2x
2
+ x
3
+ 3x
4
+
х
5
=5,
2x
1
+ x
3
– 2x
4
=3,
x
j
≥
0, j=1, 2, 3, 4, 5.
4.5.
5x
1
+ 2x
2
– x
3
+ x
4
=42,
4x
1
– 4x
2
+ x
3
+ x
4
=16,
4x
1
+ x
4
=32,
x
j
≥
0, j=1, 2, 3, 4.
4.6.
2x
1
– x
4
=3,
–
3x
1
+ 2x
2
+ x
4
=–1,
x
1
+ 2x
2
+ x
3
+ 2x
4
=3,
x
j
≥
0, j=1, 2, 3, 4.
4.7.
x
1
+ 2x
2
+ x
3
– 4x
4
=4,
2x
1
– x
2
+ x
3
– 2x
4
=2,
x
1
+ x
2
+ x
3
– 3x
4
=3,
x
j
≥
0, j=1, 2, 3, 4.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
67
2. 6.
Оптимальное
решение
канонической
задачи
линейного
программирования
Рассмотрим
каноническую
задачу
линейного
программирования
(1) f(X) =
n
j
1
γ
j
x
j
+
γ
0
,
(2)
n
j
1
А
j
x
j
=B,
(3) x
j
≥
0, j=1,2,…,n.
Задача
(1) – (3)
может
иметь
не
одно
оптимальное
решение
и
при
этом
имеет
место
Теорема
(
об
оптимальном
решении
).
Если
каноническая
задача
линейного
программирования
(1) – (3)
имеет
оптимальные
решения
,
то
одно
из
них
является
опорным
решением
этой
задачи
.
▲
Рассмотрим
оптимальное
решение
задачи
(1) – (3)
с
наименьшим
числом
ненулевых
координат
.
Пусть
таким
решением
будет
вектор
α
0
= (
α
1
, …,
α
, 0, …, 0),
где
координаты
α
1
> 0, ,
α
> 0 (
координаты
всегда
можно
перенумеровать
так
,
что
бы
первыми
из
них
стали
ненулевые
)
и
докажем
,
что
выбранный
вектор
является
опорным
решением
задачи
(1) – (3).
Предположим
противное
,
а
именно
,
что
вектор
α
0
не
является
опорным
решением
.
Тогда
по
определению
опорного
решения
,
векторы
A
1
, A
2
, … A
,
соответствующие
ненулевым
координатам
выбранного
вектора
α
0
,
образуют
линейно
зависимую
систему
,
то
есть
можно
указать
ненулевой
набор
чисел
k
1
,
k
2
, …k
такой
,
что
будет
выполняться
соотношение
A
1
k
1
+ A
2
k
2
+ … + A
k
=
Ө
.
Так
как
вектор
α
0
является
оптимальным
решением
,
то
он
является
и
допустимым
решением
рассматриваемой
задачи
,
то
есть
,
этот
вектор
является
решением
системы
линейных
уравнений
(2).
Тогда
по
определению
решения
системы
уравнений
должно
выполняться
соотношение
A
1
α
1
+ A
2
α
2
+ … + A
α
=
В
.
Прибавив
к
соотношению
(5)
соотношение
(4),
умноженное
на
δ
,
получим
А
1
(
α
1
δ
k
1
) +
А
2
(
α
2
δ
k
2
) + … +
А
(
α
δ
k
) = B.
Из
последнего
соотношения
по
определению
решения
системы
уравнений
следует
,
что
векторы
α
’
=(
α
1
+
δ
k
1
,
α
2
+
δ
k
2
, …
α
+
δ
k
)
и
α
”
=(
α
1
–
δ
k
1
,
α
2
–
δ
k
2
, …
α
–
δ
k
)
являются
решениями
системы
линейных
уравнений
(2).
Если
же
число
δ
выбрать
так
,
что
оно
удовлетворяет
арифметической
лемме
,
то
координаты
векторов
α
’
и
α
”
будут
удовлетворять
условию
(3),
а
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
68
сами
векторы
будут
являться
допустимыми
решениями
задачи
(1)–(3)
и
при
этом
,
хотя
бы
у
одного
из
этих
векторов
число
ненулевых
координат
будет
меньше
,
чем
.
Пусть
это
будет
вектор
α
’
.
Тогда
этот
вектор
не
будет
являться
оптимальным
решением
,
так
как
ранее
был
выбран
оптимальный
вектор
α
0
с
наименьшим
числом
ненулевых
координат
.
Поэтому
для
векторов
α
’
и
α
’’
должна
выполняться
система
неравенств
:
f(
α
0
) < f(
α
’
),
f(
α
0
)
≤
f(
α
’’
),
которая
равносильна
системе
:
n
j
1
γ
j
α
j
+
γ
0
<
n
j
1
γ
j
(
α
j
+
δ
k
j
) +
γ
0
,
n
j
1
γ
j
α
j
+
γ
0
≤
n
j
1
γ
j
(
α
j
δ
k
j
) +
γ
0
.
Откуда
получаем
противоречивую
систему
:
0
<
δ
n
j
1
γ
j
k
j
,
0
≤
–
δ
n
j
1
γ
j
k
j
.
Таким
образом
,
предположение
о
том
,
что
вектор
α
0
не
является
опорным
решением
не
верно
.
Следовательно
,
вектор
α
0
является
опорным
решением
задачи
(1) – (3).
■
Следствие
.
Если
каноническая
задача
линейного
программирования
имеет
оптимальное
решение
,
то
его
можно
найти
среди
опорных
решений
этой
задачи
,
так
как
число
опорных
решений
конечно
.
Для
этого
необходимо
действовать
так
:
найти
все
опорные
решения
данной
задачи
;
для
каждого
найденного
опорного
решения
вычислить
значение
целевой
функции
;
выбрать
среди
опорных
решений
то
,
которому
соответствует
наименьшее
(
наибольшее
)
значение
целевой
функции
для
задачи
на
минимум
(
максимум
).
Пример
.
Дана
КЗЛП
f(X) = 2x
1
+ x
2
– x
3
– 5x
4
(min)
x
1
– x
2
+ 2
3
– x
4
= 2,
2x
1
+ x
2
– 3x
3
+ x
4
= 6,
x
j
≥
0, j = 1, 2, 3, 4.
Найти
все
опорные
решения
,
вычислить
значение
целевой
функции
на
каждом
из
них
и
выбрать
среди
них
оптимальное
решение
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
69
▲
Разрешим
систему
векторов
условий
данной
задачи
относительно
различных
пар
векторов
,
входящих
в
эту
систему
:
А
1
А
2
А
3
А
4
В
А
1
А
2
А
3
А
4
В
А
1
А
2
А
3
А
4
В
1
–1 2 –1 2
1 –1
2 –1
2
1 0 –1/3 0 8/3
2 1 –3 1 6 0
3
–7
3 2 0 1
–7/3
1 2/3
А
1
А
2
А
3
А
4
В
А
1
А
2
А
3
А
4
В
1 –1/7
0 –1/7 54/21
–3
0 1 0 –8
0 –3/7
1 –3/7 –2/7 –7
1 0 1 –58/3
Данная
задача
имеет
только
два
опорных
решения
:
α
’ = (8/3, 2/3, 0, 0),
α
’’
= (8/3, 0, 0, 2/3),
на
которых
значение
целевой
функции
соответственно
равны
f(
α
’
) = 6, f(
α
’’
) = 2.
Следовательно
,
оптимальным
решением
является
вектор
α
’’
= (8/3, 0, 0, 2/3).
■
Замечание
.
Рассмотренный
способ
нахождения
оптимального
решения
может
быть
реализован
на
современной
компьютерной
технике
.
Однако
существуют
более
рациональные
способы
перебора
опорных
решений
с
целью
нахождения
оптимального
решения
задачи
линейного
программирования
.
К
таким
способам
относится
симплексный
метод
,
в
котором
при
решении
задачи
на
минимум
(
максимум
)
на
каждом
шаге
поиска
оптимального
решения
осуществляется
переход
от
одного
опорного
решения
к
другому
с
меньшим
(
большим
)
значением
целевой
функции
.
Ответьте
на
вопросы
1.
Сформулируйте
теорему
об
оптимальном
решении
канонической
задачи
линейного
программирования
.
2.
Приведите
схему
доказательства
теоремы
,
сформулированной
в
п
.1.
3.
Опишите
последовательность
отыскания
оптимального
решения
канонической
задачи
линейного
программирования
,
если
есть
возможность
найти
все
опорные
решения
этой
задачи
.
Решите
самостоятельно
Задачи
.
Для
данных
канонических
задач
линейного
программирования
найти
все
опорные
решения
и
выбрать
среди
них
оптимальные
решения
:
1.
f(X) = x
1
+ x
2
– x
3
(min),
x
1
– 2x
2
+
х
3
=4,
2x
1
+ 2x
2
+ 5x
3
=5,
x
j
≥
0, j = 1, 2, 3,.
2.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
70
f(X) = –3x
1
+ x
2
(min),
x
1
– 2x
2
+ x
3
+ x
4
=1,
2x
1
– x
2
– x
3
+ 2x
4
=3,
x
j
≥
0, j = 1, 2, 3, 4.
3.
f(X) = x
1
– 2x
2
– x
4
(min),
x
1
+ x
2
+ 3x
3
– 2x
4
=2,
x
1
+ x
2
+ x
3
– x
4
=1,
x
j
≥
0, j = 1, 2, 3, 4.
4.
f(X) = x
3
+ x
4
(min),
4x
1
– 5x
2
+ x
3
– x
4
=29,
6x
1
– x
2
– x
3
+ x
4
=11,
x
j
≥
0, j = 1, 2, 3, 4.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.