Реферат: Симлекс-метод

соответствует следующее значение целевой функции

z1 = с1(x1*-xrx1r) + с2(x2*-xrx2r) +.+сrxr =

= (с1x1*+с2x2*+.+сmxm*)+xr(сr-с1x1r-.-сmxmr)=

=z0+xr(сr-с1x1r-.-сmxmr), (2.2.8)

где z0 - значение целевой функции для начального ДБР;

сr-с1x1r -с2x2r - . - сmxmr - симплекс-разность для переменной хr.

Симплекс-разность вычисляют для каждой переменной, не входящей в базисное решение, и выбирают такую небазисную переменную хr, для которой симплекс-разность положительна и максимальна.

Таким образом, алгоритм симплекса-метода состоит из следующих этапов:

1) находят начальный базис и связанное с ним допустимое базисное решение;

2) вычисляют симплекс-разность для каждой переменной, не входящей в базисное решение;

3) вводят в базис наиболее 'выгодную' переменную с максимальной положительной симплексом-разностью; ее значение xrmax определяют из соотношения

для всех xir > 0,

4) выводят из базисного решения переменную xj, соответствующую

а из базиса - вектор A j;

5) переходят к этапу 2 новой итерации.

Этапы 2) - 4) повторяют до тех пор, пока симплекс-разности для всех переменных, не входящих в базис, не станут отрицательными.

Это и есть признак оптимальности текущего базисного решения.

Пример 2.2. Решить симплексом-методом такую задачу:

максимизировать (2x1+5x2)

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

x1£400, x2£300, x1+x2£500 .

Расширенная форма задачи имеет вид

Ограничения задачи запишем в виде табл. 2.1.

Первая итерация. 1. Выбрав в качестве начального базиса векторы { A3, A4, A5}, находим первое допустимое базисное решение:

A3x3*+A4x4*+A5x5*=A0,

откуда x3*=400, x4*=300, x5*=500,