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

2x1 + x2 + x3 + 3x4 = 3;

4x1 + 5x2 + 3x3 + 5x4 = 9.

Расширенная матрица имеет вид:

Первая итерация. В качестве первого направляющего элемента возьмем a11= 1 , умножим первую строку матрицы А на 2 и на 4 , затем вычитая результаты из второй и третьей строк, получим

Вторая итерация. Поскольку главная часть матрицы Ap(1) содержит ненулевые элементы, продолжим процесс исключения. Выберем элемент a22(1)=-3.

После аналогичных преобразований получим

Как видим, главная часть матрицы Ap(2), состоящая из элементов a33(2) и a34(2) , содержит только нули. Следовательно, процесс исключения заканчивается.

Исследуем матрицу A(2). Поскольку третья строка содержит лишь нулевые элементы, то она может быть отброшена. Тогда эквивалентная матрица системы уравнений будет иметь вид

Соответственно формулам (2.2.13), (2.2.14) имеем базисное решение

x1*=1; x2*=1; x3=0; x4=0.

Общее решение данной системы имеет такой вид:

X1=1- X2=1- X3= X4=

где a3, a4- произвольные скаляры.

3. Табличный симплекс метод.

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

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

A1x1+.+Anxn+e1xn+e1xn+1+.+emxn+m=A0=[ai0],

где

. - единичный базис, ai0³0

для всех i = 1, 2,., n.

Применим одну итерацию метода полного исключения к расширенной матрице ограничений Ap=[A1, ., An, e1, ., em, A0].

Пусть aij- направляющий элемент преобразования на данной итерации. Тогда в результате преобразований в соответствии с (3.3.18) получим новые значения свободных членов:

. (3.3.19)

Исследуем выражения (3.3.19). и выясним условия, при которых al0(k+1)>0 для всех l, то есть новое базисное решение будет также допустимым.

По предположению al0(k)>0; l=1,.,m,