Надо Знать

добавить знаний



Опорный план



Опорный план - решение системы линейных ограничений в задачи линейного программирования, который невозможно представить в виде линейной комбинации любых других решений.

Система ограничений задачи линейного программирования в канонической форме имеет вид

\ Sum_ {j = 1} ^ n A_i x_i = B; \ quad x_j \ geq 0, \; j = 1, \ dots, n , (1)

где B = (b 1,..., b m) T, A j = (a 1j,..., a mj) T, (j = 1, ..., n) - известные векторы, T - знак транспонирование, а X = (x 1,..., x n) - вектор переменных. Решение X * является опорным планом тогда и только тогда, когда множество векторов A j, для которых x j *> 0, линейно независима.

Количество положительных компонент опорного плана не превышает m. Если количество этих компонент равен m, опорный план называется невырожденным, а множество соответствующих векторов A j образует базис. Множество A j 1,..., A j m является базисом задачи линейного программирования с ограничениями (1) тогда и только тогда, когда система

\ Sum_ {i = 1} ^ m A_ {j_i} x_ {j_i} = B

имеет единственное решение, и x j i ≥ 0, i = 1, ..., m.

Различным опорным планам соответствуют разные базисы. Обратное утверждение верно только в случае невироджености всех опорных планов системы (1).


Источники информации

См.. также


Сигма Это незавершенная статья математики.
Вы можете помочь проекту, исправив и дополнив ее.

код для вставки
Данный текст может содержать ошибки.

скачать

© Надо Знать
написать нам