ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1084
Скачиваний: 2
86
2
0
.
Задачи
(4) – (6)
всегда
имеет
оптимальное
решение
.
▲
Задачи
(4) – (6)
имеет
допустимые
решение
,
одним
из
которых
является
,
например
,
вектор
β
= (0, …, 0, b
1
, b
2
, …, b
m
),
так
как
опорное
решение
всегда
является
допустимым
.
Из
(6)
следует
,
что
все
искусственные
переменные
неотрицательны
,
т
.
е
.
х
n+i
≥
0, i = 1, 2, …, m.
Поэтому
целевая
функция
(4)
φ
(X) = x
n+1
+ x
n+2
+ … +x
n+m
ограничена
снизу
на
множестве
допустимых
решений
,
т
.
е
.
φ
(X)
≥
0.
Следовательно
,
по
теореме
о
разрешимости
канонической
задачи
линейного
программирования
,
задачи
(4) – (6)
имеет
оптимальное
решение
.
■
Замечание
.
Так
как
у
задачи
(4) – (6)
всегда
известно
начальное
опорное
решение
,
то
ее
можно
решить
симплекс
методом
,
который
через
конечное
число
шагов
приведет
к
оптимальному
решению
этой
задачи
.
Теорема
(
о
методе
искусственного
базиса
)
Пусть
вектор
β
= (
α
1
,
α
2
, …,
α
n
,
α
n+1
,
α
n+2
, …,
α
n+m
)
является
оптимальным
решением
искусственной
задачи
(4) –(6).
Тогда
:
1)
если
α
n+1
=
α
n+2
= …=
α
n+m
=0 ,
то
вектор
α
= (
α
1
,
α
2
, …,
α
n
)
является
опорным
решением
исходной
канонической
задачи
линейного
программирования
(1) – (3);
2)
если
среди
чисел
α
n+1
,
α
n+2
, …,
α
n+m
,
хотя
бы
одно
отличается
от
нуля
,
т
.
е
.
найдется
α
n+1
>0 , i = 1, 2, …, m ,
то
задача
(1) – (3)
не
имеет
ни
одного
допустимого
решения
,
т
.
е
.
система
ограничений
канонической
задачи
линейного
программирования
(1) – (3)
является
несовместной
.
▲
Докажем
первое
утверждение
.
По
условию
вектор
β
= (
α
1
,
α
2
, …,
α
n
,
α
n+1
,
α
n+2
, …,
α
n+m
)
является
оптимальным
решением
искусственной
задачи
(4) –
(6).
Тогда
вектор
β
является
опорным
решением
этой
задачи
,
а
,
следовательно
,
и
допустимым
решением
и
,
по
определению
,
является
решением
системы
линейных
уравнений
(5),
т
.
е
.
выполняется
соотношение
:
А
1
α
1
+
А
2
α
2
+…+
А
n
α
n
+E
1
α
n+1
+ E
2
α
n+2
+ … + E
m
α
n+m
=B,
Так
как
α
n+1
=
α
n+2
= …=
α
n+m
=0 ,
то
последнее
равенство
можно
записать
в
виде
А
1
α
1
+
А
2
α
2
+…+
А
n
α
n
=B.
Откуда
,
по
определению
,
следует
,
что
вектор
α
= (
α
1
,
α
2
, …,
α
n
)
является
допустимым
решением
исходной
задачи
(1) – (3).
Так
как
вектор
β
= (
α
1
,
α
2
, …,
α
n
, 0, 0, …, 0)
является
опорным
решением
искусственной
задачи
,
то
ненулевым
координатам
этого
вектора
соответствуют
линейно
независимые
векторы
условий
этой
задачи
.
Тогда
некоторые
из
указанных
линейно
независимых
векторов
соответствуют
ненулевым
координатам
вектора
α
= (
α
1
,
α
2
, …,
α
n
).
Следовательно
,
вектор
α
является
опорным
решением
исходной
задачи
(1) – (3).
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
87
Второе
утверждение
теоремы
будем
доказывать
от
противного
,
предположив
,
что
существует
число
α
n+i
>0 , i = 1, 2, …, m,
но
при
этом
исходная
задача
(1) – (3)
имеет
допустимое
решение
α
= (k
1
, k
2
, …, k
n
),
которое
удовлетворяет
системе
(2)
и
k
j
≥
0, j =1, 2, …, n .
Тогда
по
определению
допустимого
решения
выполняется
соотношение
:
А
1
k
1
+
А
2
k
2
+…+
А
n
k
n
= B,
которое
можно
переписать
в
виде
А
1
k
1
+
А
2
k
2
+…+
А
n
k
n
+A
n+1
0 + A
n+2
0 + … + A
n+m
0 = B.
Откуда
следует
,
что
вектор
β
’ = (k
1
, k
2
, …, k
n
, 0, 0, …, 0)
является
допустимым
решением
искусственной
задачи
(4) – (6).
Так
как
по
условию
вектор
β
= (
α
1
,
α
2
, …,
α
n
,
α
n+1
,
α
n+2
, …,
α
n+m
)
является
оптимальным
решением
искусственной
задачи
,
то
φ
(
β
)
≤
φ
(
β
’),
что
равносильно
неравенству
:
α
n+1
+
α
n+2
+ …+
α
n+m
≤
0 + 0 + … + 0.
Однако
,
по
предположению
,
существует
α
n+1
>0 , i = 1, 2, …, m,
а
,
следовательно
,
α
n+1
+
α
n+2
+ …+
α
n+m
> 0.
Получено
противоречие
.
Таким
образом
,
предположение
о
существовании
допустимого
решения
исходной
задачи
является
неверным
.
Следовательно
,
система
ограничений
исходной
задачи
является
несовместной
.
■
Замечание
.
Если
среди
векторов
условий
исходной
задачи
встречается
k
единичных
векторов
,
причем
k
≤
m,
то
при
составлении
искусственной
задачи
можно
ограничиться
(m – k)
искусственными
переменными
.
Например
,
исходная
задача
имеет
вид
:
(1) f(X) =
n
j
1
γ
j
x
j
+
γ
0
(min),
(2) E
1
x
1
+ E
2
x
2
+ … + E
k
x
k
+
А
k+1
x
k+1
+ … +
А
n
x
n
=B,
(3) x
j
≥
0, j=1,2,…,n; k
≤
m.
Тогда
искусственную
задачу
можно
записать
в
следующем
виде
:
(4)
φ
(X) = x
n+1
+ x
n+2
+ … +x
n+m–k
(min),
(5) E
1
x
1
+ … + E
k
x
k
+
А
k+1
x
k+1
+ … +
А
n
x
n
+E
1
x
n+1
+ + … + E
n+m–k
x
n+m–k
=B,
(6) x
j
≥
0, j=1,2,…,n, n+1, n+2, … , n+m–k.
Пример
.
Решить
задачу
f(x)= 2x
1
– x
2
+ x
3
– x
4
(max)
–2x
1
– x
3
+ x
4
= –2,
2x
1
+ x
2
+ x
3
+ x
4
=12,
3x
1
+ 2x
3
– x
4
=7,
x
j
≥
0, j = 1, 2, 3, 4.
▲
Приведем
данную
задачу
к
задаче
на
минимум
в
канонической
форме
:
f(x)= –2x
1
+ x
2
– x
3
+ x
4
(min)
2x
1
+ x
3
– x
4
=2,
2x
1
+ x
2
+ x
3
+ x
4
=12,
3x
1
+ 2x
3
– x
4
=7,
x
j
≥
0, j = 1, 2, 3, 4.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
88
Так
как
А
2
=
Е
2
,
то
искусственная
задача
примет
вид
:
φ
(x)= x
5
+ x
6
(min)
2x
1
+ x
3
– x
4
+ x
5
=2,
2x
1
+ x
2
+ x
3
+ x
4
=12,
3x
1
+ 2x
3
– x
4
+x
6
=7,
x
j
≥
0, j = 1, 2, 3, 4, 5, 6
Решим
искусственную
задачу
симплекс
методом
c
начальным
опорным
решением
β
1
=(0, 12, 0, 0, 2, 7).
Из
таблицы
1
видно
,
что
вектор
β
1
не
является
оптимальным
,
так
как
в
строке
оценок
существуют
положительные
числа
δ
1
=5
и
δ
3
=3.
Поэтому
разрешающий
элемент
а
13
=1
выбираем
в
1-
м
или
2-
м
столбце
,
используя
критерий
:
max{5*min{2/2,12/2,7/3};
3* min{2/1, 12/1, 7/2}}=6.
После
преобразования
Жордана
получаем
симплекс
таблицу
2,
из
которой
следует
,
что
опорное
решение
β
2
=(0, 10, 2, 0, 0,
3)
также
не
является
оптимальным
из
-
за
наличия
положительной
оценки
δ
4
=1.
Проводим
преобразование
Жордана
с
разрешающим
элементом
а
34
=1
и
получаем
симплексную
таблицу
3,
из
которой
следует
,
что
опорное
решение
Β
3
=(0, 4, 5, 3, 0, 0)
является
оптимальным
решением
искусственной
задачи
.
По
доказанной
теореме
вектор
α
1
=(0,4,5,3)
является
опорным
решением
исходной
задачи
,
но
не
является
оптимальным
ее
решением
,
так
как
среди
оценок
векторов
условий
исходной
задачи
в
симплекс
таблице
4,
приведенной
к
базису
опорного
решения
α
1
,
есть
положительная
δ
1
=2.
Выбираем
за
разрешающий
элемент
а
21
=2
и
проводим
преобразование
Жордана
.
Получаем
симплекс
таблицу
5,
из
которой
следует
,
что
опорное
решение
α
2
=(2,0,3,5)
является
оптимальным
решением
исходной
задачи
,
так
как
все
вектора
условий
имеют
неположительные
оценки
,
при
чем
f(
α
2
)=2.
■
А
1
А
2
А
3
А
4
А
5
А
6
В
2 0 1 –1 1 0 2
2 1 1 1 0 0 12
Таблица
1
3 0 2 –1 0 1 7
–
γ
0
0 0 0 –1 –1 0
δ
5
0 3 –2 0 0 9
Таблица
2 2 0 1 –1 1 0 2
0
1
0
2
–1 0
10
–1
0
0
1 –2 0 3
δ
–1
0 0 1 –3 0 3
Таблица
3
1
0 1 0 –1 1 5
2 1 0 0 3 –2 4
–1
0
0
1
–1 –1 0
δ
0
0 0 0 –1 –1 0
Таблица
4 A
1
A
2
A
3
A
4
B
1
0
1
0
5
2 1 0 0 4
–1
0
0
1
3
–
γ
2 –1 1 –1 0
δ
2
0
0 0 2
Таблица
5 0 –1/2 1 0 3
1
1/2
0
0
2
0
1
0
1
5
δ
0
–1
0 0 –2
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
89
Ответьте
на
вопросы
1.
Записать
искусственную
задачу
для
данной
канонической
задачи
линейного
программирования
.
2.
Выписать
начальное
опорное
решение
искусственной
канонической
задачи
линейного
программирования
.
3.
Когда
искусственной
канонической
задачи
линейного
программирования
имеет
оптимальное
решение
?
4.
Сформулируйте
теорему
о
методе
искусственного
базиса
.
5.
При
каком
решении
искусственной
канонической
задачи
линейного
программирования
исходная
задача
имеет
опорное
решение
?
6.
При
каком
решении
искусственной
канонической
задачи
линейного
программирования
исходная
задача
не
имеет
решений
?
7.
При
каких
условиях
число
искусственных
переменных
может
быть
меньше
,
чем
число
уравнений
в
исходной
канонической
задаче
линейного
программирования
?
Решите
самостоятельно
Задача
1.
Найти
опорное
решение
,
используя
метод
искусственного
базиса
,
для
следующих
задач
линейного
программирования
:
1.1.
f(X) = x
1
– x
2
+ x
3
(min),
x
1
– x
2
+
х
3
= 3,
x
1
– 4x
2
– 2x
3
= –3,
x
j
≥
0, j = 1, 2, 3,.
1.2.
f(X) = x
1
+ 2x
2
– x
3
+ 3x
4
(min),
x
1
+
2x
2
– x
3
+ x
4
= 1
–x
1
+ 2x
2
+ 3x
3
– x
4
= 2,
x
1
+ 5x
2
+ x
3
– x
4
= 5,
x
j
≥
0, j = 1, 2, 3, 4.
Задача
2.
Решить
задачи
:
2.1.
f(X) = x
1
– 5x
2
–
х
3
+
х
4
(max).
x
1
+ 3x
2
+ 3x
3
+ x
4
= 3,
2x
1
+ 3x
3
– x
4
= 4,
x
j
≥
0, j = 1, 2, 3, 4.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
90
2.2.
f(X) = 2x
1
+ 8x
2
+
х
3
– 2
х
4
(min).
x
1
+ 2x
3
= 6,
x
2
– x
3
+ x
4
= 5,
6x
2
+ x
3
=
9,
x
j
≥
0, j = 1, 2, 3, 4.
2.3.
f(X) = –x
1
+ x
2
+ 3x
3
– x
4
(min),
x
1
+
3x
2
+ 2x
3
+ x
4
= 6,
2x
1
– 2x
3
+ x
4
= 3,
x
2
+ x
3
+ x
4
= 5,
x
j
≥
0, j = 1, 2, 3, 4.
2.4.
f(X) = x
1
+ 4x
2
+ x
3
+ x
4
+ x
5
(min),
x
1
+
4x
2
+ 2x
3
+ 2x
4
+ x
5
= 1,
x
1
– 2x
2
+ 2x
3
– 2x
4
– x
5
= – 6,
x
1
+ 2x
2
+ 2x
4
– x
5
= 2,
x
j
≥
0, j = 1, 2, 3, 4,5.
2.5.
f(X) = 4x
1
+ x
2
+ x
3
+ x
4
(max),
x
1
+
x
2
+ 3x
4
+ 4x
5
= 13,
x
1
– x
2
+ x
4
+ 2 x
5
= 5,
3x
1
+ x
3
+ x
4
+ x
5
= 15,
x
j
≥
0, j = 1, 2, 3, 4,5.
2.6.
f(X) = x
1
+ x
2
+ 10x
3
+ x
4
+ 13x
5
(min),
x
1
+
x
2
+ 3x
3
– x
4
+ 3x
5
= 21,
x
2
+ x
3
+ 2x
5
= 8,
x
3
+ x
4
+ x
5
= 6,
x
j
≥
0, j = 1, 2, 3, 4,5.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.