Метод искусственного базиса.
Метод искусственного базиса используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:
max{F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0}.
В ограничения и в функцию цели вводят так называемые «искусственные переменные» Rj следующим образом:
∑ajix+Rj=bj, j=1,m;F(x)=∑cixi-M∑Rj
При введении искусственных переменных в методе искусственного базиса в функцию цели им приписывается достаточно большой коэффициент M, который имеет смысл штрафа за введение искусственных переменных. В случае минимизации искусственные переменные прибавляются к функции цели с коэффициентом M. Введение искусственных переменных допустимо в том случае, если в процессе решения задачи они последовательно обращаются в нуль.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑cixi, , а другая – для составляющей M ∑Rj Рассмотрим процедуру решения задачи на конкретном примере.
Пример 1. Найти максимум функции F(x) = -x1 + 2x2 - x3 при ограничениях:
2x1+3x2+x3=3,
x1+3x3=2,
x1≥0, x2≥0, x3≥0 .
Применим метод искусственного базиса. Введем искусственные переменные в ограничения задачи
2x1 + 3x2 + x3 + R1 = 3;
x1 + 3x3 + R2 = 2 ;
Функция цели F(x)-M ∑Rj= -x1 + 2x2 - x3 - M(R1+R2).
Выразим сумму R1 + R2 из системы ограничений: R1 + R2 = 5 - 3x1 - 3x2 - 4x3, тогда F(x) = -x1 + 2x2 - x3 - M(5 - 3x1 - 3x2 - 4x3) .
Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x3, которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R2 должна быть из базиса исключена. Ведущий элемент обведен контуром.
В методе искусственного базиса искусственные переменные, исключенные из базиса, в него больше не возвращаются, поэтому столбцы элементов таких переменных опускаются. Табл. 2. сократилась на 1 столбец. Осуществляя пересчет этой таблицы, переходим к табл. 3., в которой строка M обнулилась, ее можно убрать. После исключения из базиса всех искусственных переменных получаем допустимое базисное решение исходной задачи, которое в рассматриваемом примере является оптимальным:
x1=0; x2=7/9; Fmax=8/9.
Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом. Рассмотрим пример, в котором присутствуют ограничения всех типов:≤,=,≥
Пример 2. Найти минимальное значение функции F(x) = 2x1 + 3x2 - x3 при следующих ограничениях
2x1+x2-3x3≥6,
x1-x2+2x3=4,
x1+x2+x3≤5,
x1≥0, x2≥0, x3≥0 .
Домножим первое из ограничений на (-1) и введем в ограничения дополнительные переменные x4 , x5 и искусственную переменную R следующим образом:
-2x1-x2+3x3+x4=-6,
x1-x2+2x3+R=4,
x1+x2+x3+x5=5,
Пусть x4 , R и x5 – базисные переменные, а x1, x2 , x3– небазисные. Функция цели F(x)=F(x)+M∑R=2x1+3x2-x3+M(4-x1+x2-2x3).
В первой симплекс-таблице (табл. 4.) коэффициенты при небазисных переменных в F-строке и M-строках знака не меняют, так как осуществляется минимизация функции. Свободный член в методе искусственного базиса в M-строке берется с противоположным знаком. Решение, соответствующее табл. 4, не является допустимым, так как есть отрицательный свободный член.
Выберем ведущий столбец и строку в соответствии с шагом 2 алгоритма решения . После пересчета получим табл. 5. Оптимизация решения в методе искусственного базиса (шаг 5 алгоритма) осуществляется вначале по M-строке. В результате x3 введем в базис, а переменную R исключим из рассмотрения, сократив количество столбцов. После пересчета получим табл. 6, которая соответствует оптимальному решению задачи.
Таблица 4
базисные переменные | Свободные члены | Небазисные переменные | ||
x1 | x2 | x3 | ||
x4 | -6 | -2 | -1 | 3 |
R | 4 | 1 | -1 | 2 |
x5 | 5 | 1 | 1 | 1 |
F | 0 | 2 | 3 | -1 |
M | -4 | -1 | 1 | -2 |
Таблица 5
базисные переменные | Свободные члены | Небазисные переменные | ||
x4 | x2 | x3 | ||
x1 | 3 | -1/2 | 1/2 | -3/2 |
R | 1 | 1/2 | -3/2 | 7/2 |
x5 | 2 | 1/2 | 1/2 | 5/2 |
F | -6 | 1 | 2 | 2 |
M | -1 | -1/2 | 3/2 | -7/2 |
Таблица 6
базисные переменные | Свободные члены | Небазисные переменные | |
x4 | x2 | ||
x1 | 24/7 | -2/7 | -1/7 |
x3 | 2/7 | 1/7 | -3/7 |
x5 | 9/7 | 1/7 | 11/7 |
F | -46/7 | 5/7 | 20/7 |
M | 0 | 0 | 0 |
Искомый минимум функции F(x) равен свободному члену F-строки табл. 6, взятому с обратным знаком, так как min F(x) = -max(-F(x)); x4 = x2 = 0;
x1=24/7; x3=2/7; x5=9/7; Fmin=46/7;
ДОБАВИТЬ КОММЕНТАРИЙ