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