![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Метод искусственного базисаПри решении задач симплексным методом необходимо, чтобы модель задачи была канонической и система ограничений была приведена к единичному неотрицательному базису. Встречаются случаи, когда эти преобразования оказываются громоздкими[19]. Метод искусственного базиса дает возможность решать задачи, приведенные к каноническому виду, без предварительного нахождения опорного решения. Дана задача линейного программирования:
Из этой задачи составим вспомогательную задачу следующим образом: 1) систему ограничений вспомогательной задачи получаем из системы ограничений исходной, добавляя в каждое ограничение, не содержащее базисную переменную, искусственную базисную переменную; 2) целевая функция равна алгебраической сумме искусственных переменных, взятых с коэффициентом (-1); 3) условие неотрицательности распространяется на все переменные, в том числе и искусственные. Математическая модель вспомогательной задачи:
Система ограничений вспомогательной задачи приведена к единичному базису, поэтому она имеет решение:
при этом Между оптимальным решением вспомогательной задачи и опорным решением исходной задачи существует зависимость: 1) если 2) если max
|