Строка оценок позволяет нам судить об оптимальности плана.

Условие оптимальности плана:

- При отыскании max функции в строке оценок должны быть нулевые и положительные оценки;

- При отыскании min функции в строке оценок должны быть нулевые и отрицательные оценки;

2.4. Проверяем допустимость базисного решения: все базисные переменные ( в столбце ) неотрицательны. Если все базисные переменные неотрицательны, то переходим к пункту 3.

Если среди них есть отрицательные, то вводим фиктивную целевую функцию и отводим ей дополнительную строку в симплекс-таблице (Таблица 1).

2.5. Строим фиктивную целевую функцию - элементы строки для

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

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

2.6.1. Поиск разрешающего столбца.

Для перехода к новому базисному плану в первую очередь из числа свободных переменных с отрицательными оценками выбирается переменная, которая вводится в базис.

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

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

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

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

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

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. Исходная симплекс-таблица для первого сорта бензина

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

Для этого необходимо определить:

- разрешающий столбец. В строке оценок находим максимальную по модулю переменную, которая будет переводиться из свободных в базисные. Наибольшей является 0,75, следовательно в базис переходит х1.

- разрешающая строка. Определяется путём нахождения наименьшего отношения элемента из bi к разрешающему столбцу. Наименьшим отношением является 0.586(6), строка, соответствующая переменной x5.

Строим новую симплекс-таблицу (см. табл. 7), в которой меняются местами переменных х5 и х1, вместе с коэффициентами целевой функции.

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

Элементы разрешающей строки определяются путем деления каждого элемента этой строки на главный (-0,8). Главный элемент рассчитывается путем деления единицы на самого себя. Элементы разрешающего столбца рассчитываются путем деления каждого элемента этого столбца на главный.

Все остальные элементы Таблицы 7 определяют по правилу прямоугольника.

Строка для фиктивной функции в расчётах более не участвует. После расчёта целевой функции видно, что остались отрицательные оценки, следовательно план не оптимален. Все элементы столбца bi положительны, следовательно полученный план опорный.

Для получения оптимального решения повторяем описанный выше алгоритм пока все оценки не будут положительными (см. табл. 8).

Таблица 8. Оптимальная симплекс-таблица для бензина первого сорта

Страницы: 1, 2, 3, 4