Табличный вид ЗЛП. Симплекс - таблицы.
СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП
3.1. Общая характеристика и основные этапы симплекс – метода
Основоположниками симплекс-метода являются советский математик Л.В. Канторович и американский математик Дж. Данциг.
Симплекс-методом можно решить любую ЗЛП или обнаружить ее неразрешимость. Многие специальные классы ЗЛП можно решить другими, более эффективными для этих классов методами. Однако преимущество симплекс-метода - его универсальность. Почти для всех ЭВМ разработаны стандартные программы для решения ЗЛП симплекс - методом.
Опишем общую идею симплекс-метода.
Считаем, что ЗЛП записана в каноническом виде и целевую функцию нужно минимизировать. Как мы уже знаем, оптимальный план следует искать среди опорных планов ЗЛП. Симплекс-метод не перебирает все опорные планы (что было бы часто невозможно из-за их огромного количества), а, начиная с некоторого исходного опорного плана, он последовательно переходит к другим опорным планам с уменьшением целевой функции. Симплекс-метод прекращает свою работу тогда, когда либо будет найден оптимальный опорный план, либо установлена неразрешимость задачи.
|
|
При решении ЗЛП симплекс-методом можно выделить следующие этапы:
1) приведение ЗЛП к каноническому виду;
2) приведение системы линейных уравнений к жордановой форме с неотрицательными правыми частями с одновременной проверкой на неразрешимость ЗЛП из-за противоречивости системы линейных ограничений;
3) исследование опорного плана на оптимальность;
4) исследование ЗЛП на неразрешимость из-за неограниченности снизу на ОДР целевой функции;
5) переход к новому, "лучшему" опорному плану.
Для сокращения и упорядочения записей при решении ЗЛП симплекс-методом используются так называемые симплекс-таблицы. Чтобы воспользоваться симплекс-таблицей, ЗЛП нужно привести к табличному виду. Делается это так.
Пусть ЗЛП записана в каноническом виде (2.3-2.5). Для приведения ЗЛП к табличному виду систему (2.4) следует сначала привести к жордановой форме с неотрицательными правыми частями. Предположим, что эта жорданова форма имеет вид (2.6). Выразим из (2.6) базисные переменные через свободные:
(3.1)
Подставив в целевую функцию (2.3) вместо базисных переменных их выражения через свободные переменные по формулам (3.1), исключим тем самым из целевой функции базисные переменные. Целевая функция примет вид:
(3.2)
В табличном виде целевая функция записывается так:
(3.3)
где .
Отметим следующие особенности табличного вида ЗЛП:
а) система линейных уравнений приведена к жордановой форме с неотрицательными правыми частями;
|
|
б) из целевой функции исключены базисные переменные и она записана в форме (3.3).
Перейдем теперь к описанию симплекс-таблицы. Пусть ЗЛП записана в табличном виде:
(3.4)
Тогда заполненная симплекс-таблица выглядит так.
Таблица 3.1.
Базис | Переменные | Свободные члены | |||||||
... | xk | ... | |||||||
... | ... | ||||||||
... | ... | ||||||||
. . . | .. | .. | ... | .. | .. | .. | ... | .. | ... |
... | ... | ||||||||
f | ... | .... |
Опорный план ЗПЛ: ..., называется опорным планом, соответствующим этой симплекс-таблице. Как видно из формулы (3.2), значение целевой функции при этом опорном плане равно γ0.
Рассмотрим пример. Привести к табличному виду следующую ЗЛП и заполнить симплекс-таблицу:
Вначале ЗЛП следует привести к каноническому виду. Для этого функцию fнужно заменить на - f:
Система уравнений должна быть записана в жордановой форме с неотрицательными правыми частями. Общий прием, с помощью которого это достигается, будет рассмотрен позднее (параграф 3.7). В нашем примере такая жорданова форма уже есть с базисными переменными и . Исключим базисные переменные из целевой функции - f. Для этого выразим их через свободные и подставим эти выражения в целевую функцию.
Табличный вид ЗЛП таков:
Заполним симплекс-таблицу (для сокращения записей первый столбец озаглавлен "Б", последний столбец - "Q").
Таблица 3.2.
Б | Q | ||||
-5 | |||||
-7 | -2 | ||||
-f | -4 | -20 |
Опорный план, соответствующий этой симплекс-таблице, имеет вид:
. Значение функции - f при этом опорном плане равно - 20.
Пусть имеется заполненная симплекс-таблица. Сформулируем условие оптимальности опорного плана.
Если в нижней строке симплекс-таблицы все числа, кроме, быть может, самого правого, неположительны, то опорный план, соответствующий этой таблице, оптимален.
Для простоты обоснуем справедливость этого утверждения на примере. Пусть заполненная симплекс-таблица имеет вид:
Таблица 3.3.
Б | Q | |||||
-1 | ||||||
-1 | ||||||
f | -5 | -3 | -1 |
Значение целевой функции при опорном плане, соответствующем симплекс-таблице, равно 6. Выпишем целевую функцию в табличном виде:, откуда . Так как при любом допустимом решении ЗЛП переменные принимают только неотрицательные значения, то из последней записи целевой функции видно, что ее значение в любой точке ОДР не меньше 6. Следовательно, минимальное значение целевой функции на ОДР равно 6 и оно достигается при опорном плане, соответствующем симплекс-таблице, .
3.4. Условие неразрешимости ЗЛП из-за неограниченности снизу на ОДР целевой функции.
Если для ЗЛП заполнена симплекс-таблица, то ОДР задачи непуста, так опорный план, соответствующий симплекс-таблице, принадлежит ОДР. Однако ЗЛП может быть неразрешимой из-за неограниченности снизу на ОДР целевой функции.
Условие неразрешимости формулируется так.
Если симплекс-таблица содержит хотя бы один столбец, отличный от самого правого, у которого в нижней строке стоит положительное число, а во всех остальных строках столбца - неположительные числа, то ЗЛП неразрешима из-за неограниченности снизу на ОДР целевой функции.
Для обоснования снова воспользуемся примером.
Таблица 3.4.
Б | Q | |||||
-2 | ||||||
-3 | -1 | |||||
f | -1 |
Столбец в нижней строке содержит положительное число, а в остальных строках - неположительные числа. Докажем неразрешимость ЗЛП.
Выпишем жорданову форму, соответствующую симплекс-таблице, и перенесем члены, содержащие , в правую часть. Получим
Пусть а - произвольное положительное число. Очевидно, ЗЛП имеет следующее допустимое решение:. Вычислим значение целевой функции при этом допустимом решении. Из таблицы 3.4 имеем:
|
|
. При указанном допустимом решении f = 4 - 2а. Отсюда видим, что значение целевой функции может стать как угодно малым при достаточно большом значении а. Иначе говоря, целевая функция не ограничена снизу на ОДР. Следовательно, ЗЛП неразрешима.
3.5. Переход к новому опорному плану.
Предположим, что условия оптимальности и неразрешимости не выполняются. Тогда симплекс-метод переходит к новому опорному плану. Этот переход совершается за счет выведения из базиса одной из базисных переменных и введения в базис одной из свободных переменных. При этом должны выполняться следующие два условия:
1) новый базис должен быть по-прежнему допустимым, т.е. правые части соответствующей жордановой формы должны быть по-прежнему неотрицательными;
2) при новом опорном плане значение целевой функции не должно превышать ее значения при прежнем опорном плане.
Столбец симплекс-таблицы, в котором стоит переменная, вводимая в базис, называется генеральным столбцом. Строка, в которой стоит переменная, выводимая из базиса, называется генеральной строкой. Элемент, стоящий на пересечении генеральной строки и генерального столбца, называется генеральным элементом.
Правило выбора генерального элемента.
В качестве генерального столбца выбирается любой столбец симплекс-таблицы, отличный от самого правого, у которого в нижней строке стоит положительное число. Затем рассматриваются только те строки симплекс-таблицы, отличные от самой нижней, у которых на пересечении с генеральным столбцом стоят положительные числа. Для каждой из таких строк вычисляется отношение свободного члена к элементу, стоящему в генеральном столбце. Строка, для которой это отношение минимально, выбирается в качестве генеральной. Элемент, стоящий на пересечении генеральной строки и генерального столбца, и будет генеральным элементом.
Проиллюстрируем это правило на примере.
|
|
Таблица 3.5.
Б | Q | |||||
2 | -1 | |||||
-2 | ||||||
F |
В качестве генерального столбца можно выбрать либо столбец , либо столбец . Выберем (чаще всего выбирают тот столбец, у которого внизу большее положительное число). Теперь приступим к выбору генеральной строки. Для этого рассмотрим две строки - и . Составляем отношения 4:2 и 8:3. Меньшее значение имеет отношение 4:2, поэтому первую строку выбираем в качестве генеральной. Следовательно, генеральный элемент равен 2 - он стоит на пересечении столбца и строки .
После выбора генерального элемента нужно перейти к новому опорному плану, при котором переменная становится базисной, а переменная х1- свободной. Коэффициент при в новой жордановой форме должен быть равен 1. Поэтому первая строка таблицы 3.5 делится на 2. Умножив затем полученную первую строку на (-3) и прибавив ко второй строке, исключим из второго уравнения. Аналогично, с помощью жордановой процедуры исключаем из третьего уравнения и из целевой функции (последнее требует табличный вид ЗЛП).
В результате получим следующую таблицу.