ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1085
Скачиваний: 2
81
таблицу
№
5,
соответствующую
базису
А
2
,
А
3
,
А
4
опорного
решения
α
’ = (0, 3, 4,
2, 0),
которое
также
не
является
оптимальным
,
из
–
за
наличия
положительной
оценки
δ
1
=2.
Для
перехода
к
следующему
опорному
решению
находим
min
0
'
is
a
{
is
i
a
'
}
для
1-
го
столбца
,
а
именно
, min {2/1; 4/1}=2.
Следовательно
,
за
разрешающий
элемент
для
преобразования
Жордана
.
берем
а
21
=1.
Получаем
симплекс
таблицу
№
6,
соответствующую
базису
А
1
,
А
2
,
А
3
опорного
решения
α
’’ = (2, 3, 2, 0, 0),
которое
является
оптимальным
,
так
как
все
оценки
векторов
условий
задачи
неположительные
.
■
Замечание
.
Решая
каноническую
задачу
линейного
программирования
на
минимум
,
мы
выполняем
ряд
шагов
.
При
этом
на
каждом
шаге
осуществляется
либо
переход
от
базиса
исходного
опорного
решения
к
базису
нового
опорного
решения
,
на
котором
значение
целевой
функции
меньше
,
чем
на
исходном
опорном
решении
,
либо
переход
к
очередному
базису
исходного
опорного
решения
,
если
это
опорное
решение
является
вырожденным
.
Так
как
опорных
решений
у
канонической
задачи
линейного
программирования
конечное
число
,
то
через
конечное
число
шагов
задача
будет
решена
,
т
.
е
.
либо
будет
найдено
оптимальное
решение
,
либо
будет
установлена
неограниченность
целевой
функции
на
множестве
допустимых
решений
этой
задачи
.
Если
задача
имеет
вырожденное
опорное
решение
,
то
,
переходя
от
одного
его
базиса
к
другому
,
можно
вернуться
к
базису
,
который
уже
встречался
ранее
,
и
продолжать
движение
по
уже
пройденной
последовательности
базисов
этого
опорного
решения
.
Такую
ситуацию
называют
«
зацикливанием
»
алгоритма
симплекс
метода
.
Чтобы
избежать
зацикливания
,
необходимо
при
переход
от
одного
базиса
к
другому
ввести
дополнительные
условия
.
Рассмотрим
симплекс
таблицу
,
приведенную
к
базису
В
1
, …,
В
l
, …,
В
k
, …,
В
r
опорного
решения
α
:
…
B
1
’
…
B
’
…
B
k
’
…
B
r
’
…
A
s
’
… B
’
…
1 … 0 … 0 … 0 … a’
1s
…
α
1
…
… …
… … … … … … … … …
… 0 … 1 … 0 … 0 … a’
s
…
α
… … … … … … … … … … … …
… 0 … 0 … 1 … 0 … a’
ks
…
α
k
… … … … … … … … … … … …
… 0 … 0 … 0 … 1 … a’
rs
…
α
r
…
0
… 0 … 0 … 0 …
δ
s
…
δ
0
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
82
Среди
положительных
одинаковых
оценок
в
симплекс
таблице
выбираем
оценку
δ
s
с
наименьшим
номером
.
Затем
среди
отношений
вида
{
is
i
a
'
}
для
всех
a’
is
> 0
выбираем
наименьшее
.
Если
указанное
отношение
не
является
единственным
,
то
выбираем
то
,
которое
имеет
наименьший
номер
i .
Применяя
это
правило
на
каждом
шаге
симплекс
метода
,
будем
получать
базис
системы
условий
задачи
,
который
не
встречался
ранее
.
Поэтому
через
конечное
число
шагов
задача
будет
решена
.
Теорема
. (
о
разрешимости
задачи
линейного
программирования
на
минимум
)
Если
каноническая
задача
линейного
программирования
на
минимум
имеет
допустимое
решение
,
а
целевая
функция
на
множестве
допустимых
решений
ограничена
снизу
,
то
эта
задача
имеет
оптимальное
решение
.
▲
В
теореме
о
существовании
опорного
решения
было
доказано
,
что
если
каноническая
задача
линейного
программирования
имеет
допустимое
решение
,
то
эта
задача
имеет
и
опорное
решение
.
Принимаем
это
опорное
решение
за
начальное
опорное
решение
и
решаем
задачу
симплекс
методом
.
Так
как
целевая
функция
ограничена
снизу
на
множестве
допустимых
решений
,
то
через
конечное
число
шагов
симплекс
метода
будет
найдено
оптимальное
решение
данной
задачи
.
■
Ответьте
на
вопросы
1.
Если
все
оценки
векторов
условий
в
симплекс
таблице
оказались
неположительными
,
то
каковы
последующие
действия
при
решении
канонической
задачи
линейного
программирования
на
минимум
симплекс
методом
?
2.
В
симплекс
таблице
среди
оценок
векторов
условий
КЗЛП
имеется
положительная
.
Каковы
последующие
действия
при
решении
канонической
задачи
линейного
программирования
на
минимум
симплекс
методом
?
3.
Каков
критерий
выбора
разрешающего
элемента
для
перехода
к
новому
опорному
решению
?
4.
Какой
критерий
используется
на
каждом
шаге
симплекс
метода
для
ускорения
процесса
нахождения
оптимального
решения
?
5.
Каков
результат
перехода
от
одной
симплекс
таблицы
к
другой
,
если
элемент
столбца
В
,
стоящий
в
одной
строке
с
разрешающим
элементом
,
равен
нулю
?
6.
Каков
результат
перехода
от
одной
симплекс
таблицы
к
другой
,
если
элемент
столбца
В
,
стоящий
в
одной
строке
с
разрешающим
элементом
,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
83
больше
нуля
?
7.
Запишите
выражение
для
любого
оптимального
решения
,
если
при
решении
КЗЛП
два
опорных
решения
оказались
оптимальными
?
8.
Докажите
теорему
о
разрешимости
задачи
линейного
программирования
на
минимум
.
Решите
самостоятельно
Задачи
1
.
Найти
оптимальное
решение
канонической
задачи
линейного
программирования
при
заданном
опорном
решении
.
1.1
f(X) = x
1
+ 2x
2
– x
3
(min),
x
1
+ 4x
2
+
х
3
= 5,
x
1
– 2x
2
+ x
3
= –1,
x
j
≥
0, j = 1, 2, 3,
α
= (1, 1, 0)
1.2
f(X) = x
1
+ x
2
+ x
3
(max),
–x
1
+ x
2
+
х
3
= 2,
3x
1
– 2x
2
+ x
3
= 0,
x
j
≥
0, j = 1, 2, 3,
α
= (0, 1, 1)
1.3.
f(X) = 2x
1
+ x
2
+ 3x
3
+ x
4
(max)
x
1
– 2x
2
+ 5x
3
– x
4
= 4,
x
1
– x
2
– x
3
+ 2x
4
= 1,
x
j
≥
0, j = 1, 2, 3, 4,
α
= (0, 0, 1, 1)
1.4.
f(X) = 6x
1
+ x
2
+ 4x
3
– 5x
4
(max)
3x
1
+ x
2
– 5x
3
+ x
4
= 4,
5x
1
+ x
2
+ x
3
– x
4
= 4,
x
j
≥
0, j = 1, 2, 3, 4,
α
= (1, 0, 0, 1)
1.5.
f(X) = x
1
+ x
2
+ x
3
– x
4
+ 3x
5
(min)
x
1
+ x
2
+ x
3
+ x
4
+
2x
5
= 4,
2x
1
+ x
2
+ x
3
+ 2x
4
= 5,
x
3
– x
4
+ 3x
5
= 2,
x
j
≥
0, j = 1, 2, 3, 4, 5,
α
= (1, 1, 2, 0, 0).
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
84
1.6.
f(X) = 5x
1
+ 10x
2
+ 3x
3
(max)
3x
1
+ 2x
2
– x
3
+ x
4
–
2x
5
= 23,
–x
1
+ 3x
2
– 2x
3
+ x
4
= 9,
x
1
+ 2x
2
+ x
3
+ x
5
= 29,
x
j
≥
0, j = 1, 2, 3, 4, 5,
α
= (0, 0, 24, 57, 5).
1.7.
f(X) = x
1
+ x
2
+ 13x
4
– x
5
+ 3x
6
(min)
x
1
– x
2
– x
3
– 9x
4
–
4x
5
+5x
6
=
–5,
x
1
+ 2x
2
– x
3
+ 3x
4
–
x
5
+2x
6
= 4,
x
3
+ 8x
4
+
2x
5
–2x
6
= 6,
x
j
≥
0, j = 1, 2, 3, 4, 5,6,
α
= (4, 3, 6, 0, 0, 0).
Задача
2.
Решить
задачи
симплекс
методом
f(X) = x
1
+ 4x
2
+ x
3
+ x
4
– 2x
5
+x
6
(min)
x
1
– x
2
– x
4
=
–0,
x
1
+ x
2
+ x
3
+ x
5
= 1,
x
2
+ x
3
+
x
6
= 1,
x
j
≥
0, j = 1, 2, 3, 4, 5,6.
f(X) =
x
1
– 4x
3
– 2x
6
(min)
–x
1
– x
2
– 2x
6
= –1,
–x
1
+ 2x
3
+
х
5
+ 3
х
6
= 0,
x
1
– x
3
+ x
4
–
x
6
= 1,
x
j
≥
0, j = 1, 2, 3, 4, 5,6.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
85
2. 9.
Метод
искусственного
базиса
для
нахождения
начального
опорного
решения
Решение
канонической
задачи
линейного
программирования
симплекс
методом
всегда
начинается
с
некоторого
начального
опорного
решения
.
До
сих
пор
начальное
опорное
решение
задавали
,
либо
для
его
нахождения
выбирался
такой
базис
системы
векторов
условий
,
чтобы
вектор
ограничений
линейно
раскладывался
с
неотрицательными
коэффициентами
.
Такой
способ
нахождения
начального
опорного
решения
может
потребовать
перебора
большого
числа
различных
базисов
.
Этого
можно
избежать
,
если
для
нахождения
начального
опорного
решения
использовать
более
эффективный
метод
–
метод
искусственного
базиса
.
Рассмотрим
каноническую
задачу
линейного
программирования
(1)
f(X) =
n
j
1
γ
j
x
j
+
γ
0
(min),
(2)
n
j
1
А
j
x
j
=B,
(3)
x
j
≥
0, j = 1, 2, …, n.
Построим
для
задачи
(1) – (3)
искусственную
каноническую
задачу
линейного
программирования
вида
:
(4)
φ
(X) = x
n+1
+ x
n+2
+ … +x
n+m
(min),
(5)
n
j
1
А
j
x
j
+E
1
x
n+1
+ E
2
x
n+2
+ … + E
m
x
n+m
=B,
(6)
x
j
≥
0, j=1,2,…,n, n+1, n+2, … , n+m,
где
E
j
–
единичный
вектор
(j = 1, 2, …, m) ,
а
x
n+1
, x
n+2
, … , x
n+m
–
искусственные
переменные
.
Основные
свойства
искусственной
задачи
1
0
.
Вектор
β
= (0, …, 0, b
1
, b
2
, …, b
m
)
является
опорным
решением
задачи
(4)–
(6).
▲
Заметим
,
что
по
определению
канонической
задачи
линейного
программирования
все
координаты
вектора
ограничений
В
= (b
1
, b
2
, …, b
m
)
должны
быть
неотрицательными
,
т
.
е
. b
i
≥
0, i = 1, 2, …, m.
Так
как
единичные
векторы
E
1
, E
2
, … , E
m
образуют
базис
системы
векторов
условий
А
1
,
А
2
, …,
А
n
, E
1
, E
2
, … , E
m
задачи
(4) – (6),
то
вектор
ограничений
В
можно
представить
в
виде
линейной
комбинации
векторов
E
1
,
E
2
, … , E
m
с
неотрицательными
коэффициентами
b
i
≥
0, i = 1, 2, …, m,
т
.
е
.
в
виде
В
= b
1
E
1
+ b
2
E
2
+ … + b
m
E
m
.
Следовательно
,
по
свойству
базиса
опорного
решения
вектор
β
= (0, …, 0, b
1
, b
2
, …, b
m
)
является
опорным
решением
задачи
(4) – (6).
■
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.