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

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

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

В каждой вершине ОДР (опорном решении) по крайней мере переменных должны обращаться в нуль. Попробуем получить опорное решение, полагая в формулах (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, где тоже нет ни одного отрицательного элемента (кроме самого свободного члена)

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