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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

117
);1,0(1
1
1
11
1
1
=
=
=
=
+
vucvu
);1(1
4
14
4
1
=
=
=
+
vcvu
);3(4
3
34
4
3
=
=
=
+
ucvu
);3(5
3
33
3
3
=
=
=
+
vcvu
);3(4
2
21
1
2
=
=
=
+
ucvu
).2(1
2
22
2
2
−
=
=
=
+
vcvu
Полученная
система
потенциалов
позволяет
проверить
полученный
план
на
оптимальность
.
Составляем
разности
jiijij
vuc
−
−
=
∆
,
для
всех
клеток
таблицы
.
Поскольку
для
занятых
клеток
0
=
∆
ij
(
по
определению
),
то
остается
найти
ij
∆
для
незанятых
клеток
.
Эти
величины
(
числа
)
назы
-
ваются
оценками
клеток
распределительной
таблицы
,
или
плана
.
Теорема опти-
мальности
Опорный
план
X
оптимален
в
том
и
толь
-
ко
в
том
случае
,
если
среди оценок
ij
∆
этого
плана
нет отрицательных
.
Если
среди
оценок
ij
∆
есть
отрицательные
,
то
план
неоптимален
,
и
его
улучшают
методом перераспределения поставок по циклу
.
Отметим
клетку
с
наименьшей
отрицательной
оценкой
и
построим
цикл
с
начальной
вершиной
в
этой
клетке
.
Определение цик-
ла
Циклом
с
начальной
вершиной
в
данной
клетке
называется
замкнутая
ломаная
,
обладаю
-
щая
следующими
свойствами
:
1)
все
ее
вершины
,
кроме
начальной
,
расположены
в
занятых
клетках
;
2)
звенья
(
стороны
)
цикла
расположены
в
строках
и
столбцах
таблицы
;
3)
в
каждой
вершине
звенья
соединяют
-
ся
под
прямым
углом
.
4)
На
звеньях
цикла
могут
быть
занятые
инами
цикла
;
5)
Два
звена
могут
пересекаться
в
ка
-
кой
-
либо
клетке
,
но
эта
клетка
не
должна
быть
занятой
(
иначе
она
является
вершиной
).

Страницы