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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

62
2.3. Основная задача линейного программирования
Задача линейного программирования (ЗЛП) с ограничениями-
равенствами называется основной задачей линейного программирования
(ОЗЛП) [10].
ОЗЛП ставится следующим образом: имеется ряд переменных
n
xxx ,...,,
21
. Требуется определить такие неотрицательные значения этих
переменных, которые удовлетворяли бы системе линейных уравнений
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=+++
=+++
=+++
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
...
..............................................
,...
,...
2211
22222121
11212111
(2.15)
и, кроме того, обращали бы в минимум линейную функцию
....
2211 nn
xCxCxCW
+
+
+
= (2.16)
Случай, когда необходимо определить максимум линейной функции,
легко сводится к предыдущему. Для этого необходимо только изменить
знак функции
W и рассматривать функцию
nn
xCxCxCWW
−
−
−
−
=
−=
′
...
2211
, (2.17)
т.е.
()
WW −= minmax и
(
)
WW minmax
−
=
.
Будем называть допустимым решением ОЗЛП любую совокупность
переменных 0,...,0,0
21
≥≥≥
n
xxx , которая удовлетворяет уравнениям-
ограничениям (2.15).
Оптимальным решением будем называть то из допустимых решений
00
2
0
1
,...,,
n
xxx , при котором линейная функция (2.17) обращается в минимум.
Рассмотрим прежде всего вопрос о существовании допустимых
решений ОЗЛП.
Определение
Рангом матрицы называется наибольший порядок отличного от нуля
определителя, который можно получить, вычёркивая из матрицы какие-то
строки и столбцы.
Матрицей системы уравнений
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=+++
=+++
=+++
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
...
..............................................
,...
,...
2211
22222121
11212111
(2.18)
называется матрица, составленная из коэффициентов
njmia
ij
,1,,1, == при
njx
j
,1, = :

Страницы