Материал: 4-1

В примере 2 найдено одно базисное решение этой системы (-1, 1, 3, 0). Ему соответствует расширенная матрица системы

можно сделать, так как коэффициент при x4 в первом уравнении, разрешенном относительно x1, отличен от нуля. Исключим x4 из второго и третьего уравнений. Для этого добавим ко второй и третьей строке первую, умноженную соответственно на (-3) и (-2). Получим

Давая свободной неизвестной x1 значение 0, получим базисное решение (0, 3, 6, -1).

Введем далее в число базисных неизвестных x1 вместо x3. Для этого разделим вторую строку на (-3), а к первой и третьей строкам добавим преобразованную вторую, умноженную на (-1) и 2 соответственно. Матрица примет вид

все возможные базисные системы неизвестных. Это означает, что найдены все базисные решения.

Ответ: (-1, 1, 3, 0); (0, 3, 6, -1); (-2, -1, 0, 1); (−32 , 0 , 32 , 12 .)

V. Неотрицательные (допустимые) решения системы линейных уравнений. Метод последовательного замещения для нахождения допустимых базисных решений

Решение x01, x02, ..., x0n системы (5) называется допустимым, если все значения x01, x02, ..., x0n неотрицательны.

Система уравнений может иметь допустимые решения, а может их и не иметь. Справедлива

Теорема существования допустимого базисного решения. Если система

(5)имеет допустимое решение, то она имеет и базисное допустимое решение.

Впункте IV было показано как, исходя из одного базисного решения, находить другие. Теперь нас будут интересовать только допустимые базисные решения. Для простоты рассмотрим лишь невырожденный случай.

Пусть нам известно невырожденное допустимое базисное решение

x01 > 0, ..., x0m > 0, x0m+1 = 0, ..., x0n = 0. Преобразуем систему

(5) методом Гаусса-Жордана к виду (6).Если подставить в эту систему значения неизвестных, получим x01 = f1 > 0, ..., x0m = fm > 0. Предположим теперь, что мы хотим вывести из числа базисных неизвестных xr и ввести xs, но так, чтобы новое базисное решение осталось допустимым. Для этого необходимо, чтобы hrs 6= 0. Проделав шаг по методу Гаусса-Жордана,

мы приходим к системе (8),из которой найдется новое базисное решение, для которого x01 = f10, ..., x0r−1 = fr0−1, x0s = fr0, x0r+1 = fr0+1, ..., x0m = fm0 . Оно будет допустимым, если все fi0 ≥ 0. Отсюда по формулам (9)

получаем

Из первого неравенства следует, что hrs > 0. Однако это не гарантирует выполнение следующих неравенств. Если his ≤ 0, тогда автоматически

fi − fr his > 0. Если же his > 0, то наше неравенство можно переписать

hrs

в виде

Следовательно,мы не можем произвольно выбирать переменную xr, которую выводим из числа базисных. Чтобы новое базисное решение было допустимым, нужно xr выбирать при условии выполнения неравенств (10), которые можно записать в виде одного равенства

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

отношения к ним правых частей fi. Тот номер, для которого fi −

his

наименьшее и будет номером r ключевой строки. Тогда преобразование Гаусса-Жордана приведет к новому допустимому базисному решению.

VI. Каноническая задача линейного программирования

Каноническая задача линейного программирования состоит в следующем: требуется найти максимум (или минимум) линейной функции F (X) = c1x1 + c2x2 + ... + cnxn, которую в дальнейшем будем называть линейной формой, при условиях, что все переменные неотрицательны и удовлетворяют системе ограничений (5).

Сокращенно эта задача записывается так:

n

X

F (X) = cjxj − max,

j=1

n

X

aijxj = bi (i = 1, 2, ..., m),

j=1

xj ≥ 0 (j = 1, 2, ..., n).

Всякое неотрицательное (допустимое) решение системы (5) назовем планом. Если X0 = (x01, x02, ..., xon) план, то числа xoi называются компонентами плана. Допустимое базисное решение системы (5) называется опорным планом. Наконец, план, при котором форма F (X) принимает максимальное значение, называется оптимальным.

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

Для решения задач линейного программирования важнейшее значение имеет

Основная теорема линейного программирования: если для канонической задачи линейного программирования существует оптимальный план, то для нее существует и оптимальный опорный план.

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

(не больше, чем Cnm) и из них выбрать наилучший.

Однако, обычно числа m и n велики и опорных планов так много, что задача об их вычислении очень трудоемка и требует больших затрат времени даже на самых мощных компьютерах. В дальнейшем мы сократим число опорных планов, для которых нужно вычислять значения формы

иполучим алгоритм, который может быть эффективно реализован.

Оценки свободных неизвестных

Пусть дан опорный план X0, в котором x01, ..., x0m− базисные неизвестные,

а свободные неизвестные x0m+1, ..., x0n− равны нулю. Предположим, что методом Гаусса-Жордана система уравнений-ограничений (5) приведена к виду (7), то есть разрешена относительно базисных неизвестных. Тогда

x01 = f1, x02 = f2, ..., x0m = fm и линейная форма F (X) принимает на заданном опорном плане X0 значение

F (X0) = c1x01 + ... + cmx0m = c1f1 + ... + cmfm.

Пусть теперь X = (x1, ..., xn)− произвольный план. Выразим значение формы F (X) на этом плане через свободные неизвестные. Базисные неизвестные из системы (7) подставим в выражение для формы. Получим

F (X) = c1x1 + ...+ cmxm + cm+1xm+1 + ...+ cnxn = c1(f1 −h1(m+1)xm+1 −...

−h1nxn)+...+cm(fm −hm(m+1)xm+1 −...−hmnxn)+cm+1xm+1 +...+cnxn = = c1f1 + ... + cmfm − (c1h1(m+1) + ... + cmhm(m+1) − cm+1)xm+1−

−... − (c1h1n + ... + cmhmn − cn)xn.

Вводя обозначение

m

X

j = cihij − cj, j = m + 1, ..., n,

i=1

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

выражающей линейную форму через свободные неизвестные.

m

P

Величина j = cihij−cj называется оценкой свободной неизвестной

i=1

xj. Она равна сумме произведений коэффициентов формы при базисных неизвестных на коэффициенты в соответствующих уравнениях при данной свободной неизвестной минус коэффициент формы при этой неизвестной. Из формулы (12) легко видеть, что оценка j свободной неизвестной xj равна величине, на которую изменяется значение формы при изменении

этой свободной неизвестной на единицу.

Критерий оптимальности опорного плана

Признак оптимальности опорного плана: для оптимальности опорного плана достаточно, чтобы оценки свободных неизвестных были неотрицательными.

Доказательство. Пусть все оценки j ≥ 0. Для всякого плана X компоненты xj ≥ 0, поэтому

Это означает, что F (X0)− наибольшее значение нашей формы и, следовательно, план X0− оптимальный. Утверждение доказано.

Если исходный план X0 невырожденный, то есть x01 = f1 > 0, ..., x0m = fm > 0, то условие неотрицательности оценок j является необходимым для его оптимальности.

Доказательство. Дадим всем свободным неизвестным нулевые значения за исключением неизвестной xj, которую положим равной малому положительному числу β. Получим решение системы

X = (f1 − h1jβ, ..., fm − hmjβ, 0, ..., β, 0, ..., 0).

При достаточно малом β > 0 все значения неизвестных будут неотрицательными (так как fi > 0), то есть получится план. По формуле (12) для этого плана

F (X) = F (X0) − jβ.

Однако по условию план Xo оптимальный и, значит, F (X) ≤ F (X0) или F (X0) − jβ ≤ F (X0). Отсюда − jβ ≤ 0 и так как β > 0, то

j ≥ 0. Оценки неотрицательны. Утверждение доказано. Из доказанных утверждений следует

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

Замечание. Мы рассматриваем задачу на максимум F (X). В случае задачи на минимум F (X) для оптимальности плана оценки свободных неизвестных должны быть неположительны.

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

Доказательство. Пусть j < 0 и все коэффициенты hij ≤ 0. Положим снова все свободные неизвестные решения равными нулю кроме неизвестной