Опорное решение задачи линейного программирования и его взаимосвязь с угловыми точками

Рассмотрим на примере.

Пусть у нас есть система ограничений:

То же самое можем записать в векторной форме:

Векторы А_i называются векторами условий. Данная система имеет бесконечное множество решений. В частности Х=(7, 15, 0, 0) – базисное решение. Если базисных решений несколько, то есть несколько правил:

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

Определение. Опорным решением задачи ЛП называется такое допустимое решение, для a векторы условий, соответствующие положительным координатам А₁-А_m линейно независимы.

- число отличных от нуля координат опорного решения не может быть больше r-ранга системы ограничений. Будучи рассматривать, когда система ограничений состоит из линейно-независимых уравнений, т.е. m=r. В том случае, если число отличных от нуля координат равно m, то такое решение называется невырожденным. Если m<0, то – вырожденным.

Определение. Базисом опорного решения называется базис системы векторов условий задачи, в состав a входят векторы, соответствующие отличным от 0 координатам опорного решения.

Теорема 4. Любое опорное решение является угловой точкой области допустимых решений. (ОДР)

Теорема 5. Любая угловая точка ОДР является опорным решением.

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

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

1. Способ выбора первоначального опорного решения;

2. Способ перехода от одного опорного решения к другому с целью приближения целевой функции к оптимальному значению;

3. Заданные критерии a позволяют своевременно прекратить перебор на оптимальном решении или сделать вывод об отсутствии такового.

Название симплексный произошло от англ. simple – простейший, т.к. первые задачи ЛП имели вид (области) ОДР.

Дата добавления: 2014-01-11