Применение симплекс-метода при определении состава смеси при переработке нефти (стр. 2 из 6)
Таблица 2. Алгоритм симплекс-метода
| 1 этап | Приводим задачу линейного программирования к канонической форме. |
| 2 этап | Определяем допустимое базисное решение |
| 3 этап | Поиск оптимального решения, реализуемый переходом от одного базисного плана к другому, приводящему либо к оптимальному решению, либо к выводу о том , что задача решения не имеет |
1. Необходимо задачу привести к канонической форме.
1.1. Введением неотрицательных слабых переменных все ограничения неравенства представляют в виде равенств
(
)1.2. Максимизируем целевую функцию (
).1.3. Задача в канонической форме имеет вид:
Левая часть каждого ограничения данной задачи меньше либо равна правой. Для того чтобы левая часть ограничения была равна правой, необходимо к левой части каждого ограничения прибавить соответственно неотрицательные переменные
, 
,…., 
. Эти переменные вводятся в целевую функцию с нулевыми коэффициентами, чтобы не изменить её значение.2. Поиск опорного базисного решения.
2.1. Определяем допустимое базисное решение.
2.2. Принимаем в качестве базисных, введённые слабые переменные.
2.3. Составляем исходную симплекс-таблицу (таблица 3) по следующей схеме (таблица 4):
Таблица 3. Симплекс-таблица
| Ci |  |  | C1 | Cj | … | Cn | Cn+1 | … | Cn+m |
 |   | … |  |  | … |  | |||
| C1 | |  |  |  | … |  | | … | 0 |
| Ci |  | |  |  | … |  | 0 | … | 0 |
| … | … | … | … | … | … | … | … | … | … |
| Cm |  |  |  |  | … |  | 0 | … | |
 |  |  |  |  | … |  |  | … |  |
| |  |  | | | … | | | … | |
Таблица 4. Схема заполнения симплекс-таблица
| Столбец Сi | записываются коэффициенты при базисных переменных (  ) |
Столбец  | базисные переменные. Количество базисных переменных равно количеству ограничений задачи (n) |
| Столбец | свободные члены ограничений (значения базисных переменных) |
| Строка | строка переменных, входящих в целевую функцию и в систему ограничений |
Столбцы  | В симплекс-таблице количество столбцов равно количеству базисных и свободных переменных задачи (m+n). Количество свободных переменных равно количеству неизвестных переменных задачи (n), количество базисных – количеству ограничений (m) |
Строка  | Для столбца  : содержит значение целевой функции, которое рассчитывается по формуле  , а столбцы  этой же строки (значения относительных оценок  ), рассчитывается по формуле  |
При определении значения функции
фактически нужно найти сумму произведений элементов столбца Ci на соответствующие элементы столбца . что равносильно подстановке базисного плана в целевую функциюСтрока оценок позволяет нам судить об оптимальности плана.
Условие оптимальности плана:
- При отыскании max функции в строке оценок должны быть нулевые и положительные оценки;
- При отыскании min функции в строке оценок должны быть нулевые и отрицательные оценки;
2.4. Проверяем допустимость базисного решения: все базисные переменные ( в столбце
) неотрицательны. Если все базисные переменные неотрицательны, то переходим к пункту 3.Если среди них есть отрицательные, то вводим фиктивную целевую функцию
и отводим ей дополнительную строку в симплекс-таблице (Таблица 1).2.5. Строим фиктивную целевую функцию
- элементы строки для являются суммой соответствующих элементов строк для выбранных базисных переменных, оказавшихся отрицательными.2.6. Максимизируем фиктивную целевую функцию
(алгоритм для максимизации начальной ц.ф. такой же, как и рассматривающийся для ).2.6.1. Поиск разрешающего столбца.
Для перехода к новому базисному плану в первую очередь из числа свободных переменных с отрицательными оценками
выбирается переменная, которая вводится в базис.