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

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

Z=C1X1+C2X2+...+CnXn

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

a11x1+a12x2+...+a1nxn=b1

a21x1+a22x2+...+a2nxn=b2

............................................

am1x1+am2x2+amnxn=bm

xj≥0(j=1,2,...n)

bi≥0(i=1,2,...m)

Предполагается, что система ограничений задачи содержит m единичных векторов, причем без ограничения общности можно положить, что единичными являются первые m векторов.

Z=C1X1+C2X2+...+CnXn

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

x1+a1,m+1 xm+1+...+a1nxn=b1

x2+a2,m+1 xm+1+...+a2nxn=b2

.....................................................

xm+am,m+1+xm+1+...+amnxn=bm

xj≥0(j=1,2,...n)

Алгоритм симплексного метода представляет собой способ целенаправленного перебора планов, чтобы значения линейной формы в задачах на минимум уменьшалось при переходе от одного опорного плана к другому, число шагов для достижения этой цели m≤k≤2m, где m-число уравнений или размеренность базиса.

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

- Подсчитывается Zj-Cj и определяется, не является ли рассматриваемый план оптимальным, т.е. не выполняется ли для всех xj условие: Zj-Cj≤0

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

- Выбирается вектор, который подлежит исключению из базиса. Это вектор для которого: для всех xik>0, тогда Pi –исключается из базиса.

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

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

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

Вычисления сводятся в табл.2

Таблица №2