![]() ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Метод искусственного базисаЧасто, после приведения ОЗЛП к каноническому виду расширенная матрица системы линейных уравнений (СЛУ) не является К-матрицей (нет начального опорного плана), и, следовательно, решать такую КЗЛП симплекс-методом нельзя. Суть метода искусственного базиса состоит в следующем: строится такая вспомогательная КЗЛП (ВКЗЛП) с заранее известным опорным планом, по решению которой либо определяется начальный опорный план исходной задачи, либо устанавливается, что ее множество планов пусто. Дано:
Найти: К-матрицу (начальный опорный план). Построим следующую ВКЗЛП:
Очевидно, начальный опорный план ВКЗЛП имеет вид:
Применяя симплекс-метод, находят
Замечание: ВКЗЛП всегда разрешима, так как множество ее планов не пусто, а целевая функция ограничена. Теорема: Если Пример: F(X) = 5×x1 + 3×x2 + 4×x3 - x4 x1 + 3×x2 + 2×x3 + 2×x4 = 3 2×x1 + 2×x2 + x3 + x4 = 3
x1 + 3×x2 + 2×x3 + 2×x4 + y1 = 3 x1 + 3×x2 + 2×x3 + 2×x4 + y2 = 3 xj
Таблица 1
Замечание: По мере выхода искусственных переменных из базиса, вычисления в соответствующих клетках симплекс-таблицы не проводятся. Получили оптимальный опорный план ВКЗЛП.
Теперь решаем симплекс-методом исходную задачу: F(X)= 5×x1 + 3×x2 + 4×x3 - x4 x2 + 3/4×x3 + 3/4×x4 = 3/4 x1 - 1/4×x3 - 1/4×x4 = 3/4 xj Таблица 2
Не нашли, что искали? Воспользуйтесь поиском:
|