Пример решения задачи методом искусственного базиса.

Найти минимум функции F=-2x₁+3x₂ - 6x₃ - x₄ при условиях

Решение. Запишем данную задачу в форме основной задачи: найти максимум функции F₁=2x₁ – 3x₂ + 6x₃ + x₄ при условиях

В системе уравнений последней задачи рассмотрим векторы из коэффициентов при неизвестных:

А₁ = А₂ = А ₃= А ₄= А ₅= А ₆=

Среди векторов А₁,…, А ₆ только два единичных (А ₄ и А ₅). Поэтому в левую часть третьего уравнения системы ограничений добавим дополнительную неотрицательную переменную x ₇ и рассмотрим расширенную задачу, состоящую в максимизации функции

F=2x₁ – 3x₂ + 6x₃ + x₄ – Mx₇

при условиях

Расширенная задача имеет опорный план X=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: А ₄ , А₅, А₇.

Таблица 1

Составляем таблицу (1) I итерации, содержащую пять строк. Для заполнения 4-й и 5-й строк находим F ₀ и значения разностей z_j – c_j (j= ):

F ₀ = 24–10M;

z₁–c₁ = 0– M;

z₂–c₂ = 4+ M;

z₃–c₃ = –8–2 M;

z₄–c₄ =0+ M;

z₅–c₅ =0+ M;

z₆–c₆ = 0+ M;

z₇–c₇ =0+ M;

Значения F ₀ и z_j–c_j состоят из двух слагаемых, одно из которых содержит M, а другое – нет. Для удобства итерационного процесса число, состоящее при M, записываем в 5-й строке, а слагаемое, которое не содержит M,– в 4-й строке.

В 5-й строке табл.1 в столбцах векторов А_j (j = ) имеется два отрицательных числа (-1 и -2). Наличие этих чисел говорит о том, что данный опорный план расширенной задачи не является оптимальным. Переходим к новому опорному плану расширенной задачи. В базис вводим вектор А₃. Чтобы определить вектор, исключаемый из базиса, находим θ=min(22/4; 10/2)=10/2. Следовательно, вектор А₇ исключаем из базиса. Этот вектор не имеет смысла вводить ни в один из последующих базисов, поэтому в дальнейшем столбец данного вектора не заполняется (табл. 2 и 3).

Составляем таблицу II итерации (табл. 2). Она содержит только четыре строки, так как искусственный вектор из базиса исключен.

Таблица2

Как видно из табл. 2, для исходной задачи опорным является план Х =(0;0;5;34;2).

Проверим его на оптимальность. Для этого рассмотрим элементы 4-й строки. В этой строке в столбце вектора А₆ имеется отрицательное число (-4). Следовательно, данный опорный план не является оптимальным и может быть улучшен благодаря введению в базис вектора А₆. Из базиса исключается вектор А₅. Составляем таблицу III итерации.

Таблица 3

В 4-й строке табл.3 среди чисел ∆_j нет отрицательных. Это означает, что найденный новый опорный план исходной задачи Х *=(0; 0; 11/2; 35; 0; 1) является оптимальным. При этом плане значение линейной формы F_max = 68.

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