Линейное программирование

 

Шаг 6. Проверка условия: все a_ir ≤ 0. Если ДА - целевая функция неограничена и решения нет, если НЕТ - переход к шагу 7.

Таким образом, необходимо проверить  элементы разрешающего столбца. Если среди  них нет положительных, то задача неразрешима.

В нашем примере все  элементы разрешающего столбца положительны (6, 6 и 1), следовательно, необходимо перейти  к шагу 7.

 

Шаг 7. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:

для air > 0,

где s - номер разрешающей  строки.

Таким образом, для тех  строк, где элементы разрешающего столбца  положительны, необходимо найти частное  от деления элемента b_i (последний столбец таблицы) на элемент, находящийся в разрешающем столбце. В качестве разрешающей выбирается строка, для которой результат такого деления будет наименьшим.

Проиллюстрируем выполнение шага 7, обратившись к нашему примеру.

Для первой строки: D₁ = 120 / 6 = 20.

Для второй строки: D₂ = 72 / 6 = 12.

Для третьей строки: D₃ = 10 / 1 = 10.

Наименьший результат  деления - в третьей строке, значит именно эту строку мы выбираем в  качестве разрешающей, т.е. исключать  из базисного решения будем переменную x₅.

Элемент, стоящий на пересечении  разрешающей строки и разрешающего столбца, называется разрешающим элементом. В нашем случае таковым является единица, стоящая на пересечении третьей строки и второго столбца.

Исходная симплекс-таблица  нашего примера с выделенными  цветом разрешающей строкой и  разрешающим столбцом представлена ниже (таблица 2.6).

Таблица 2.6 - Исходная симплекс-таблица  с выделенными разрешающей строкой  и столбцом, а также с иллюстрацией к применению правила прямоугольника

Шаг 8. Пересчет элементов симплекс-таблицы (переход к новому базисному решению). Порядок пересчета различных элементов таблицы несколько отличается.

Для элементов  разрешающей строки используются следующие формулы:

где s - номер разрешающей  строки,

r - номер разрешающего  столбца, 

, - новые значения пересчитываемых элементов,

a_sj, b_s - старые значения пересчитываемых элементов,

a_sr - старое значение разрешающего элемента.

Таким образом, при пересчете  элементов разрешающей строки каждый ее элемент делится на разрешающий  элемент.

Еще проще пересчитать элементы разрешающего столбца. Все они (кроме разрешающего элемента) становятся равными нулю:

.

Элементы, не принадлежащие  разрешающим столбцу и строке, пересчитываются по так называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором элемент, подлежащий пересчету и разрешающий элемент образуют одну из диагоналей. Формулы будут иметь следующий вид:

где , , , - новые значения пересчитываемых элементов,

a_ij, b_i, c_j, L - старые значения пересчитываемых элементов.

Применение правила прямоугольника проиллюстрируем, используя таблицу 2.6. Пересчитаем элемент a₁₁ (в исходной симплекс-таблице его значение равно 4). В таблице 2.6 можно видеть прямоугольник (прочерчен пунктиром), соединяющий четыре элемента, участвующих в пересчете:

,   т.е.

Аналогичным образом пересчитываются  остальные элементы.

По окончании пересчета  осуществляется возврат к шагу 4.

 

Полностью результат пересчета  для нашего примера можно видеть в таблице 2.7

Таблица 2.7 - Симплекс-таблица  для задачи о хоккейных клюшках  и шахматных наборах (второе базисное решение)

базис	переменные					bi
	x1	x2	x3	x4	x5
x3	4	0	1	0	-6	60
x4	2	0	0	1	-6	12
x2	0	1	0	0	1	10
cj	2	0	0	0	-4	-40

Таким образом, в новом  базисном решении базисными переменными  являются: x₂ = 10, x₃ = 60, x₅ = 12 (соответствующие значения можно видеть в последнем столбце таблицы). Неосновные переменные x₁ и x₅ равны нулю. Значение целевой функции в этом случае равно 40 (значение можно видеть в правой нижней ячейке таблицы).

 

Доведем решение нашего примера  до конца.

Вернемся к шагу 4 симплекс-алгоритма. Рассмотрим последнюю строку таблицы 2.7. В ней есть положительные элементы, значит полученное решение не является оптимальным.

Шаг 5. Выберем разрешающий  столбец. Им окажется столбец x₁, поскольку здесь содержится единственный положительный элемент нижней строки. Стало быть, переменную x₁ будем переводить в основные.

Далее. Шаг 6. Проверка показывает, что в разрешающем столбце  есть положительные элементы, следовательно, можно продолжать решение.

Шаг 7. Определим разрешающую  строку. При этом будем рассматривать  лишь первую и вторую строки, поскольку  для третьей строки в разрешающем  столбце находится нуль. Найдем частное  от деления элемента b_i на элемент, находящийся в разрешающем столбце:

Для первой строки: D₁ = 60 / 4 = 15.

Для второй строки: D₂ = 12 / 2 = 6.

Наименьший результат  деления - во второй строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную x₄.

Ниже приведена симплекс-таблица  с выделенными разрешающей строкой  и столбцом (таблица 2.8).

Таблица 2.8 - Симплекс-таблица (второе базисное решение) с выделенными  разрешающей строкой и столбцом

базис	переменные					bi
	x1	x2	x3	x4	x5
x3	4	0	1	0	-6	60
x4	2	0	0	1	-6	12
x2	0	1	0	0	1	10
cj	2	0	0	0	-4	-40

Далее перейдем к шагу 8 и  осуществим пересчет элементов симплексной  таблицы в соответствии с правилами, приводимыми выше. Результат пересчета  представлен в таблице 2.9.

Таблица 2.9 - Симплекс-таблица  для задачи о хоккейных клюшках  и шахматных наборах (третье базисное решение)

базис	переменные					bi
	x1	x2	x3	x4	x5
x3	0	0	1	-2	6	36
x1	1	0	0	1/2	-3	6
x2	0	1	0	0	1	10
cj	0	0	0	-1	2	-52

Таким образом, в очередном (третьем) базисном решении основными  переменными являются: x₁ = 6, x₂ = 10, x₃ = 36. Неосновные переменные x₄ и x₅ равны нулю. Значение целевой функции для этого решения равно 52.

Вернемся к шагу 4 симплекс-алгоритма. Рассмотрим последнюю строку таблицы 2.9. В ней все еще есть положительные  элементы, значит полученное решение  не является оптимальным, и необходимо продолжить выполнение симплекс-алгоритма.

Шаг 5. Выберем разрешающий  столбец. Им окажется столбец x₅, поскольку здесь содержится единственный положительный элемент нижней строки. Переменную x₅ будем переводить в основные.

Шаг 6. Проверка показывает, что в разрешающем столбце  есть положительные элементы, следовательно, можно продолжать решение.

Шаг 7. Определим разрешающую  строку. При этом будем рассматривать  лишь первую и третью строки, поскольку  для второй строки в разрешающем  столбце находится отрицательное  число. Найдем частное от деления  элемента b_i на элемент, находящийся в разрешающем столбце:

Для первой строки: D₁ = 36 / 6 = 6.

Для третьей строки: D₂ = 10 / 1 = 10.

Наименьший результат  деления - в первой строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную x₃.

Ниже приведена симплекс-таблица  с выделенными разрешающей строкой  и столбцом (таблица 2.10).

Таблица 2.10 - Симплекс-таблица (третье базисное решение) с выделенными  разрешающей строкой и столбцом

базис	переменные					bi
	x1	x2	x3	x4	x5
x3	0	0	1	-2	6	36
x1	1	0	0	1/2	-3	6
x2	0	1	0	0	1	10
cj	0	0	0	-1	2	-52

Далее перейдем к шагу 8 и  осуществим пересчет элементов симплексной  таблицы в соответствии с правилами, приводимыми выше. Результат пересчета  представлен в таблице 2.11.

Таблица 2.11 - Симплекс-таблица  для задачи о хоккейных клюшках  и шахматных наборах (четвертое  базисное решение)

базис	переменные					bi
	x1	x2	x3	x4	x5
x5	0	0	1/6	-1/3	1	6
x1	1	0	1/2	-1/2	0	24
x2	0	1	-1/6	1/3	0	4
cj	0	0	-1/3	-1/3	0	-64