Учебное пособие: Методы исследования операций
Алгоритм симплекс-метода состоит из следующих шагов:
Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю n-m (небазисных) переменных. При этом если матрица системы ограничений задачи линейного программирования содержит единичную подматрицу порядка m, то это решение очевидно. Переменные, столбцы которых образуют эту единичную матрицу, являются базисными, остальные – свободными. Если же такой единичной матрицы нет, то для получения начального базисного решения вводятся искусственные переменные. Затем базисные переменные выражаются через небазисные из соответствующих ограничений и полученные выражения подставляются в целевую функцию. Если используются искусственные переменные, то применяются специальные методы (метод больших штрафов, двухэтапный метод).
Шаг 1. Из числа текущих небазисных переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как полученное базисное решение оптимально. В противном случае переходят к шагу 2.
Шаг 2. Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна принять нулевое решение (стать небазисной) при введении в состав базисных новой переменной.
Шаг 3. С помощью метода исключения переменных или метода Гаусса-Жордана находится новое базисное решение, соответствующее новым составам базисных и небазисных переменных и осуществляется переход к шагу 1.
Пример. Решить симплекс-методом задачу
Максимизировать z=3x1+2x2
при ограничениях x1+2x2£ 6;
2x1+x2£ 8;
-x1+x2£ 1;
x1£ 2;
x1³ 0, x2³ 0.
Решение.
Запишем задачу в стандартном виде
z-3x1-2x2=0
x1+2x2+s1= 6;
2x1+x2+s2= 8;
-x1+x2+s3= 1;
x1+s4= 2,
где s1, s2, s3, s4 – дополнительные неотрицательные переменные, которые вводятся в правые части ограничений имеющих знак «£» и называются остаточными. Если задача линейного программирования является задачей оптимального распределения ограниченных ресурсов, и правые части каждого ограничения представляют запасы ресурсов, то значения остаточных переменных в любом решении показывают остаток этих ресурсов. Матрица системы ограничений содержит единичную матрицу порядка 4. Ее образуют коэффициенты при остаточных переменных, значит переменные s1, s2, s3, s4 будут базисными переменными, а x1, x2 – свободными или нулевыми.
Шаг 0. Заполняем начальную симплекс-таблицу.
|
Базисные переменные |
x1 |
x2 |
S1 |
s2 |
s3 |
s4 |
Решение К-во Просмотров: 617
Бесплатно скачать Учебное пособие: Методы исследования операций
|