конспект лекций, вопросы к экзамену

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


Алгоритм решения данной задачи следующий:

1) необходимо осуществить переход от стандартной к канонической форме

2) осуществляется выбор разрешающего столбца. 

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

3) выбирают разрешающую строку и разрешающий элемент. 

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

4) расчёт разрешающего столбца и разрешающей строки. 

Все коэффициенты разрешающий строки делят на разрешающий элемент. Все коэффициенты разрешающего столбца обнуляют.

5) расчёт всех остальных коэффициентов системы. 

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

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

19.01.2017; 08:00
просмотров: 308