Метод реализации модели

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

при ограничениях

Алгоритм симплексного метода представляет собой способ целенаправленного перебора планов. Через конечное число шагов линейная форма достигает max или min.

Заполняется исходная таблица. После чего производится вычисления в последовательности:

· Подсчитывается и определяется, не является ли рассматриваемый план оптимальным, т.е. не выполняется ли для всех x условие: 0

· Если для некоторого j значение >0, то выбирается вектор, который может быть введен в базис. Для этого разыскивается какое-нибудь j, для которого max()=>0, тогда P- вводится в базис.

; : j=1,2,…,n

· Выбирается вектор, который подлежит исключению из базиса. Это вектор для которого: q = min= для всех X>0 , тогда P- исключается из базиса.

· Если все X< 0, то линейная форма неограниченна снизу.

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

В результате каждой итерации образуется новый опорный план. В конце концов, либо придем к оптимальному плану, либо убедимся в неограниченности линейной формы задачи. Вычисления сводятся в табл.2:

Таблица №2