7. ОТЫСКАНИЕ ОПОРНОГО РЕШЕНИЯ ОСНОВНОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Пусть имеется ОЗЛП с ограничениями-равенствами, записанными в стандартной форме:

разрешенными относительно базисных переменных которые выражены через свободные переменные

В каждой вершине ОДР (опорном решении) по крайней мере переменных должны обращаться в нуль. Попробуем получить опорное решение, полагая в формулах (7.1) все свободные переменные равными нулю.

Имеем:

Если все свободные члены в уравнениях (7.1) неотрицательны, это значит, что опорное решение уже получено; этот случай нас не интересует. Рассмотрим случай, когда среди свободных членов есть отрицательные. Это значит, что решение (7.2) не является опорным — оно вообще недопустимо, и опорное решение еще предстоит найти. Для этого мы будем шаг за шагом обменивать местами базисные и свободные переменные в уравнениях (7.1) до тех пор, пока не придем к опорному решению или не убедимся, что его не существует. Последнее бывает в случае, когда система уравнений (7.1) несовместима с неравенствами

т. е. у нее нет неотрицательных решений.

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

Существует ряд способов выбора разрешающего элемента для приближения к опорному решению. Остановимся (без строгого доказательства) на одном из них.

Пусть имеется одно из уравнений (7.1) с отрицательным свободным членом. Ищем в этой строке отрицательный элемент Если такого элемента нет (все элементы это признак того, что система уравнений (7.1) несовместима с неравенствами (7.3). Действительно, при отсутствии отрицательных элементов в строке вся правая часть соответствующего уравнения может быть только отрицательной, а это противоречит условиям неотрицательности переменных.

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

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

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

Убедимся на примере, как совершается приближение к опорному решению при таком правиле выбора разрешающего элемента. Попутно мы убедимся в разумности этого правила.

Пример 1. Найти (если оно существует) опорное решение задачи линейного программирования с ограничениями-равенствами:

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

Решение. Записываем условия (7.4) в виде стандартной таблицы (см. табл. 7.1).

Таблица 7.1

В табл 7.1 имеется отрицательный свободный член —5 в строке столбца Согласно правилу, выбираем любой отрицательный элемент этой строки, например —2 (в табл. 7.1 он подчеркнут). Этим мы выбрали разрешающий столбец . В качестве «кандидатов» на роль разрешающего элемента рассмотрим все те элементы этого столбца, которые одинаковы по знаку со своим свободным членом; это будут —2 и 1 (нуль в качестве разрешающего элемента фигурировать не может).

Вычисляем для каждого из «кандидатов» отношение к нему свободного члена:

Наименьшее из этих отношений 2; значит, элемент 1 выбираем в качестве разрешающего и меняем местами (см. табл. 7.2).

После выполнения действий приходим к табл. 7.3.

В табл. 7.3 по-прежнему один отрицательный свободный член, но по абсолютной величине он уже меньше, чем в табл. 7.1 — значит, мы приближаемся к ОДР.

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

Таблица 7.2

Таблица 7.3

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

В табл 7.5 все свободные члены неотрицательны, и опорное решение найдено:

Пример 2. Найти (если оно существует) опорное решение системы

Таблица 7.4

Таблица 7.5

Таблица 7.6

Таблица 7 7

Решение. Записываем систему уравнений (7.5) в виде стандартной таблицы (см. табл. 7.6).

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

Последнее отношение минимально; значит, в качестве разрешающего берем элемент в строке и производим замену (см. табл. 7.7 и 7.8).

Обратим внимание на строку в табл. 7 8. В ней свободный член отрицателен, но нет ни одного отрицательного элемента (кроме самого свободного члена). Соответствующее уравнение имеет вид:

Может ли при каких бы то ни было неотрицательных значениях величина быть неотрицательной? Очевидно, нет: при получим а увеличение сверх нуля сделает еще меньше. Следовательно, система (7.5) несовместима с неравенствами, вытекающими из неотрицательности переменных, и задача линейного программирования с условиями-ограничениями (7.5) допустимых решений не имеет.

Таблица 7.8

О том же свидетельствует и строка табл. 7.8, где тоже нет ни одного отрицательного элемента (кроме самого свободного члена)

Таким образом, мы видим, что нет необходимости специально исследовать систему условий ОЗЛП на совместность в области неотрицательных решений: этот вопрос выясняется автоматически, в процессе нахождения опорного решения.