Линейная алгебра. Линейное программирование. Тарбокова Т.В. - 103 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

103
Принцип выбора разрешающей строки следует соблюдать и при поис-
ке первого базисного решения.
Рассмотрим несколько ситуаций, в которых получение оптимального
решения недостижимо.
1) Предположим, что полученное базисное решение задачи на
максимум не оптимально: в индексной строке имеется, например, один по-
ложительный коэффициент. Тем самым определена переменная, которую
следует ввести в базис. Вместе с тем коэффициенты разрешающего столб-
ца неположительные. Следовательно, ввести эту переменную в базис нель-
зя: это приведет к недопустимому решению. В таком случае задача не име-
ет решения по причине неограниченности целевой функции в ОДР.
2) Предположим, что при поиске первого базисного решения на-
талкиваемся на недопустимые решения, и не удается получить допустимое
решение. В таком случае задача не имеет решения по причине несовмест-
ности условий ограничений задачи.
Пример 2.22.
→
−
−
−
+
=
5
4
3
2
1
73)( xxxxxXL max
=−+++
=+−−
=
−
+
+
+
−
.384
,44
,432
54321
532
54321
xxxxx
xxx
xxxxx
5,1,0 =≥ jx
j
Решение
.
Задача
задана
в
канонической
форме
.
Решение
задачи
удоб
-
но
оформить
в
виде
таблицы Гаусса 2.5
,
соответствующей
элементарным
преобразованиям
матрицы
данной
задачи
.
Блоки
таблицы
Гаусса
будем
отсчитывать
по
обведенной
индексной
строке
.
В
первом
блоке
первый
разрешающий
элемент
(
обведен
квадра
-
том
)
выбрали
в
первом
столбце
,
т
.
к
.
в
нем
есть
один
ноль
,
а
разрешающую
строку
выбрали
по
числу
=Θ=Θ
iq
i
iq
a
b
min .
Во
втором
блоке
разрешающий
столбец
выбрали
по
положительному
коэффициенту
индексной
строки
.

Страницы