Применение симплекс-метода при определении состава смеси при переработке нефти (стр. 3 из 6)

Вводится переменная, которой соответствует наибольшая по абсолютной величине отрицательная оценка

:

Столбец, отвечающий переменной

, назовем разрешающим столбцом.

Элементы разрешающего столбца обозначаются через

.

Выбранная переменная будет вводится в базис.

Если окажется несколько одинаковых наибольших по абсолютной величине

, то выбирается любая из соответствующих им переменных.

2.6.2. . Поиск разрешающей строки.

Выбираем переменную, которая выводится из базиса (обозначим индексом

). Находится из соотношения:

по всем i для которых

)

Строку таблицы, в которой получено наименьшее отношение

элемента столбца

к элементу разрешающего столбца, назовем разрешающей строкой.

Элементы разрешающей строки обозначаются через

Выбранная переменная

будет выводится из базиса.

2.6.3. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется главным.

2.6.4. Пересчет оставшихся элементов таблицы по правилу прямоугольника.

Результат заносится в новую симплекс-таблицу.

Выбранные переменные в новой таблице меняются местами вместе со своими коэффициентами в целевой функции.

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

Таблица 5. Расчёт элементов новой симплекс-таблицы

Элементы главной строки
Элементы главного столбца
Главный элемент
Все остальные элементы таблицы	; ; ; .

2.6.5. После пересчета всех элементов таблицы в строке для дополнительной фиктивной функции

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

· Если

и все коэффициенты в строке для равны 0, то полученное при этом базисное решение является опорным. Исключают строку для и переходят к п. 3.

· Если

то система ограничений противоречива и задача не имеет решений. Переходят к п. 4.

· Если

, а среди элементов строки для есть ненулевые, то соответствующие этим элементам переменные всегда равны 0. Исключают строку для и переходят к п.3.

2.6.6. После исключения строки для функции

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

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

исходной задачи.

3.1. В строке для

ищем отрицательные элементы.

Если отрицательных элементов нет, то получено оптимальное решение задачи.

Если среди элементов строки

есть отрицательные, то выбирают столбец, содержащий наименьший отрицательный элемент в строке , - он будет разрешающим.

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

Элемент на пересечении разрешающих строки и столбца – главный.

Поиск оптимального решения ведется до тех пор пока в троке

не будут положительными все оценки .

Описание вычислительного эксперимента

Целевая функция задачи имеет вид:

1. Вычислительный эксперимент для первого сорта бензина

Целевая функция для первого сорта бензина (k=1):

Содержание фракции А, В, С для I-го сорта бензина:

Фракции А: Не менее 45% - 0.45

При испарении теряется 2% - 0.02

Фракции С: Не более 20% - 0.2

При испарении теряется 1% - 0.01

Формула баланса:

Ограничения с учетом испарения для I-го сорта бензина:

Сведем ограничения к определению максимума целевой функции:

Далее действуем по алгоритму симплекс-метода, приведённому нами в предыдущей главе.

Первый этап. Приведение к каноническому виду

- свободные переменные.

– базисные переменные (искусственные величины).

Второй этап. Поиск допустимого решения.

Определим исходный базисный план

Вычисляем значения относительных оценок

Поскольку для данного плана существуют отрицательные оценки (по критерию оптимальности

), то план не оптимален. Необходим переход к другому базисному плану.

Проверяем допустимость базисного решения: все базисные переменные (в столбце

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

Таблица 6. Исходная симплекс-таблица для первого сорта бензина

7	11	6	9	0	0	0
Ci	B	bi	X1	X2	X3	X4	X5	X6	X7
0	X5	-0,44	-0,75	-0,3	-0,65	-0,45	1	0	0	0,586(6)
0	X6	0,198	0,05	0,35	0,2	0,2	0	1	0	3,96
0	X7	1	1	1	1	1	0	0	1	1
		0	-7,5	-11,5	-6,5	-9,5	0	0	0
		-0,44	-0,75	-0,35	-0,65	-0,45	0	0	0

Далее переходим к максимизации фиктивной целевой функции.