Вводится переменная, которой соответствует наибольшая по абсолютной величине отрицательная оценка
Столбец, отвечающий переменной
Элементы разрешающего столбца обозначаются через
Выбранная переменная будет вводится в базис.
Если окажется несколько одинаковых наибольших по абсолютной величине
2.6.2. . Поиск разрешающей строки.
Выбираем переменную, которая выводится из базиса (обозначим индексом
по всем i для которых
Строку таблицы, в которой получено наименьшее отношение
элемента столбца
Элементы разрешающей строки обозначаются через
Выбранная переменная
2.6.3. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется главным.
2.6.4. Пересчет оставшихся элементов таблицы по правилу прямоугольника.
Результат заносится в новую симплекс-таблицу.
Выбранные переменные в новой таблице меняются местами вместе со своими коэффициентами в целевой функции.
Элементы новой симплекс-таблицы рассчитываются по формулам, приведенным в таблице 5.
Таблица 5. Расчёт элементов новой симплекс-таблицы
Элементы главной строки | |
Элементы главного столбца | |
Главный элемент | |
Все остальные элементы таблицы | |
2.6.5. После пересчета всех элементов таблицы в строке для дополнительной фиктивной функции
· Если
· Если
· Если
2.6.6. После исключения строки для функции
3. Поиск оптимального решения. После получения допустимого базисного решения исходной задачи по алгоритму, описанному выше, максимизируем целевую функцию
3.1. В строке для
Если отрицательных элементов нет, то получено оптимальное решение задачи.
Если среди элементов строки
Рассматриваем положительные значения отношений элементов столбца свободных членов к соответствующим элементам выбранного столбца и среди этих отношений берем наименьшее – разрешающая строка.
Элемент на пересечении разрешающих строки и столбца – главный.
Поиск оптимального решения ведется до тех пор пока в троке
Описание вычислительного эксперимента
Целевая функция задачи имеет вид:
1. Вычислительный эксперимент для первого сорта бензина
Целевая функция для первого сорта бензина (k=1):
Содержание фракции А, В, С для I-го сорта бензина:
Фракции А: Не менее 45% - 0.45
При испарении теряется 2% - 0.02
Фракции С: Не более 20% - 0.2
При испарении теряется 1% - 0.01
Формула баланса:
Ограничения с учетом испарения для I-го сорта бензина:
Сведем ограничения к определению максимума целевой функции:
Далее действуем по алгоритму симплекс-метода, приведённому нами в предыдущей главе.
Первый этап. Приведение к каноническому виду
Второй этап. Поиск допустимого решения.
Определим исходный базисный план
Вычисляем значения относительных оценок
Поскольку для данного плана существуют отрицательные оценки (по критерию оптимальности
Проверяем допустимость базисного решения: все базисные переменные (в столбце
Таблица 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 |
Далее переходим к максимизации фиктивной целевой функции.