Основы теории систем и системного анализа. Матвеев Ю.Н. - 93 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

93
Своб.
член
х
1
у
1
х
3
х
4
W
0 –1 –1 0 0
х
2
0 –1 1 0 0
у
2
2 1 –1 –1 0
у
3
1 0 0 –1 –1
При замене х
2
↔у
1
уменьшения линейной функции не произошло.
Переменную х
2
= 0 заменяем на переменную у
1
= 0 и получаем
оптимальное решение:
,1,2,0,0
0
3
0
2
0
2
0
4
0
3
0
1
0
1
======= yyxхxyx
.0
0
min
=W
При наличии «вырождения» может оказаться, что замена х
р
↔ у
r
приводит только к перестановке переменных. Линейная функция W не
уменьшается. В некоторых случаях последовательное применение правила
выбора разрешающего элемента приводит к тому, что после нескольких
итераций можно вернуться к исходной таблице. Это называется
«зацикливанием», эффективным способом борьбы с которым является
смена разрешающего элемента.
2.11. Двойственная задача линейного программирования
2.11.1. Понятие двойственности
С каждой задачей ЛП тесно связана другая задача, называемая
двойственной. Первоначальная задача называется исходной (основной,
прямой). Решение двойственной задачи может быть получено из решения
исходной и наоборот.
Связь исходной и двойственной задач состоит в том, что
коэффициенты
njС
j
,1, = целевой функции исходной задачи являются
свободными членами в системе ограничений двойственной задачи,
свободные члены
mib
i
,1, = системы ограничений исходной задачи служат
коэффициентами функции цели двойственной задачи. Матрица
коэффициентов системы ограничений двойственной задачи представлена
как транспонированная матрица коэффициентов системы ограничений
исходной задачи.
Рассмотрим постановку исходной и двойственной задач на примере
задачи использования ресурсов.
Предприятие имеет m видов ресурсов в количестве
mib
i
,1, = единиц.
Из этих m видов ресурсов производится n видов продукции. Для
производства единицы j-го вида продукции используется
ij
a единиц i-го
вида ресурса. Стоимость единицы j-го вида продукции –
njС
j
,1, = .
Следует рассчитать программу выпуска продукции, которая
обеспечила бы её максимальный выпуск в стоимостном выражении.

Страницы