Г л а в а 3

Метод искусственного базиса

Основной целью данной главы является изложение решения задач линейного программирования методом искусственного базиса, который удобен в случае, если в исходной задаче не выделен допустимый базис. Начнем же с напоминания алгоритма решения задач линейного программирования симплекс-методом.

3.1. Симплекс-метод решения задач линейного программирования

Сформулируем сначала общий алгоритм решения задачи линейного программирования симплекс-методом. Предположим, система ограничений приведена к каноническому виду, в ней выделен допустимый базис (все правые части – неотрицательные числа), из целевой функции исключены базисные переменные и все слагаемые, кроме константы, перенесены в левую часть. Записав все данные в сим- плекс-таблицу, получим (далее предполагается, что рассматривается задача на максимум, а альтернатива в скобках дана для задачи на минимум)

1.Если в последней строке нет отрицательных (положительных) оценок, то оптимальное решение достигнуто.

2.Если в оценочной строке есть хотя бы одна отрицательная

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

держащий отрицательную (положительную) оценку, а в качестве разрешающего выбирается положительный элемент alj > 0, дающий ми-

3. Если в симплекс-таблице имеется отрицательная (положительная) оценка, а в соответствующем столбце нет положительных элементов, то исходная задача не имеет решения, т.е. zmax = +∞

(zmin = −∞).

43

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

Пример 3.1. Решить задачу линейного программирования

z = 3x1 +3x2 +21 → max

−2x1 + x2 + x3 =1,

x1 − x2 + x4 = 3,x1 + x2 + x5 = 7,

x ≥ 0.

симплексным методом.

Решение. Задача приведена к каноническому виду, допустимый базис уже выделен (переменные x3 , x4 , x5 ) и из целевой функ-

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

44

и альтернативным оптимальным решением является X2 = (5,2,9,0,0).

Заметим, что других альтернатив нет, так как, вводя в базис переменную x4 , мы вновь получаем альтернативное решение X1 . Итак, оп-

тимальным множеством исходной задачи является отрезок, соединяющий точки X1 и X2 :

X = (1−t)X1 +tX2 = (1−t)(2,5,0,6,0)+t (5,2,9,0,0)=

= (2 +3t,5 −3t,9t,6 −6t,0),t [0,1]. Получаем, что zmax = 42 при X = (2 +3t,5 −3t,9t,6 −6t,0),t [0,1].

Задачи для самостоятельного решения

Решить задачи линейного программирования симплексным

методом

46