Задача линейного программирования и анализ ее решения

Задача  линейного программирования и анализ ее решения

Вопрос 1. Задача линейного программирования.

Линейное программирование решает задачи, относящиеся к таким  сферам человеческой деятельности, как  промышленное производство, военное  дело, сельское хозяйство, транспорт, здравоохранение.

 

Линейное программирование- это наука о методах исследования и отыскания максимума и минимума линейной функции, на неизвестные которой наложены линейные ограничения.

 

Линейность – свойство математических выражений и функций. Выражение ax+by, где a и b некоторые постоянные, называется линейным, относительно переменных x и y.

 

Определение. Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

(1)

при условиях

  (2)

  (3)

  (4)

где - заданные постоянные величины и к m.

 

Определение. Функция (1) называется целевой функцией (или линейной формой) задачи (1) – (4), а условия (2) – (4) – ограничениями данной задачи.

Определение. Стандартной (или симметрической) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (2) и (4), где к=m и t=n.

Определение. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (3) и (4), где к=0 и t=n.

Определение. Совокупность чисел , удовлетворяющих ограничениям задачи (2) - (4) называется допустимым решением (или планом).

Определение. План , при котором целевая функция задачи (1) принимает своё максимальное (минимальное) значение, называется оптимальным.

В случае, когда требуется найти минимум функции , можно перейти к нахождению максимума функции , поскольку min F=-max(-F).

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

Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений-неравенств в ограничения-равенства равно  числу преобразуемых неравенств.

 

Вопрос 2 .Свойства основной задачи линейного программирования.

Рассмотрим задачу линейного  программирования. Она состоит в определении максимального значения функции при условиях .

 Перепишем задачу в  векторной форме: найти максимум  функции 

F=CX    (5)

 При условиях

,   (6)

X ,   (7)

 Где  СX – скалярное произведение; и - m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи:

; ; …; .

Определение. План называется опорным планом основной задачи линейного программирования, если система векторов , входящих в разложение (6) с положительными коэффициентами , линейно независима.

Определение. Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае он называется вырожденным.

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

Теорема. Если основная задача линейного программирования имеет оптимальный план, то максимальное значение целевая функция принимает в одной из вершин многогранника решений. Если максимальное значение целевая функция задачи принимает более чем в одной вершине, то она принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин.

Теорема. Если система векторов в разложении (6) линейно независима и такова, что

,

где все  , то точка является вершиной многогранника решений.

Теорема. Если - вершина многогранника решений, то векторы , соответствующие положительным в разложении (6), линейно независимы.