4. Признак достижения максимума целевой функции, понятие опорного решения.

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

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

Только 6 из приведенных 15–ти симплексных таблиц содержат допустимое базисному решению. Эти таблицы соответствуют вершинам многоугольника ограничений OABCEF (см. рис. 1). Остальные 9 таблиц соответствуют недопустимым базисным решениям. Этим таблицам на рис. 1 соответствуют 9 точек, не являющихся вершинами многоугольника OABCEF.

5. Обоснование симплех –метода.

Задачу линейного программирования, в которой требуется найти максимум целевой функции F, запишем в виде

А₁₁X₁ + A₁₂X₂ + . . . + A_1nX_n = B₁,

A₂₁X₁ + A₂₂X₂ + . . . + A_2nX_n = B₂,

. . . . . . . . . . . . . . . . . . . . (4)

A_m1X₁ + A_m2X₂ + . . . + A_mnX_n = B_m,

X ₁³ 0, X₂ ³ 0, . . ., X_n ³ 0,

F = C₁X₁ + C₂X₂ +. . .+ C_nX_n  max,

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

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

Как перейти к другому допустимому базисному решению? Ясно, что для этого нужно какую-нибудь свободную переменную превратить в базисную, а какую-нибудь базисную переменную следует сделать свободной переменной. Посмотрим, что представляет собой процесс превращения свободной переменной в базисную переменную. Мы договорились, что свободная переменная всегда равна нулю. Допустим, она превращается в базисную не равную нулю переменную со значением X₀ > 0. Итак, превращение свободной переменной в базисную переменную означает увеличение ее значения от нуля до некоторого значения X₀, которое она примет, став базисной переменной. Что касается превращения базисной переменной в свободную переменную, то базисная переменная, наоборот, должна уменьшиться до нуля.

Как выбрать свободную переменную, которую нужно перевести в базисную? Если в число базисных перевести свободную переменную, которой в выражении целевой функции F = C₁X₁ + C₂X₂ +. . .+ C_nX_n , выраженной через свободные переменные, соответствует отрицательное значение коэффициента С_j (j = 1, 2,...,n). то такое преобразование может привести лишь к уменьшению значения целевой функции. В самом деле, превращение свободной переменной в базисную означает увеличение ее значения от нуля до некоторого В₀. Но при отрицательных значениях С_j величина С_jХ_j убывает с увеличением Х_j, а это означает, что функция F тоже убывает, а нашей целью является достижение ее максимума.

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

Итак, в число базисных переменных следует переводить свободную переменную, которой в выражении целевой функции соответствует положительное значение коэффициента С_j. Такой выбор приближает нас к цели, приводит к увеличению значения целевой функции. Выбрав свободную переменную, подлежащую переводу в базисные переменные, мы тем самым указываем соответствующий ей столбец матрицы ограничений. Для определенности пусть это будет столбец с номером j.

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

X₁ X₂

1.000 .000 .000 .000 2.000 3.000 35.000

.000 1.000 .000 .000 2.000 1.000 21.000

.000 .000 1.000 .000 1.000 4.000 40.000

.000 .000 .000 1.000 5.000 1.000 45.000

.000 .000 .000 .000 7.000 5.000 .000

Далее будем считать, что элементы этой таблицы соответствуют обозначениям задачи (4), т. е. , , , и т. д.

Оба коэффициента целевой функции в последней строке (“7.000” и “5.000”) положительны. Поэтому в качестве j-го столбца (столбца новой базисной переменной) можно выбрать либо пятый столбец, либо шестой столбец. Допустим, выбрали пятый столбец, соответствующий переменной X₁, т. е. j = 5.

Теперь предстоит разобраться с тем, как выбрать базисную переменную, подлежащую переводу в категорию свободных. Для этого нужно указать номер строки i, где она находится.

Пусть в категорию свободных переменных переводится соответствующая значению i=2 базисная переменная . Возьмем строку, которая представляет базисную переменную выраженную через свободные переменные X₁ и X₂.

.000 1.000 .000 .000 2.000 1.000 21.000 (5)

Переменная X₁ отличается от свободной переменной X₂ лишь тем, что претендует стать базисной переменной. При “плавном переходе” в базисные переменные значение X₁ должно нарастать от нуля до некоторого значения X₀, которое она примет, став базисной переменной. Учитывая, что свободная переменная X₂ так и останется свободной переменной (X₂ =0), получим из строки (5)

+ 2X₁ = 21. . (6)

Но с другой стороны, если переменная станет свободной переменной, то в новой таблице ей будет соответствовать значение, равное нулю. При “плавном переходе” в свободные переменные значение должно уменьшиться до нуля. Но тогда, как следует из (6), новая базисная переменная X₁ должна удовлетворять условию 2X₁ = 21 или

X₁ =10.5. (7)

Дадим экономическую интерпретацию “плавному переходу” в базисные переменные свободной переменной X₁. Увеличение X₁ от нуля до некоторого значения X₀ означает, что начался процесс производства первого изделия.

С другой стороны, “плавный переход” переменной в свободные переменные означает, что в связи с производством первого изделия запасы второго ресурса стали уменьшаться.

Аналогично, если в категорию свободных переменных переводится соответствующая значению i =3 базисная переменная , получим

X₁ =40.0. (8)

Если в категорию свободных переменных переводится соответствующая значению i =4 базисная переменная , получим

X₁ =9.0. (9)

Если в категорию свободных переменных переводится соответствующая значению i =1 базисная переменная , получим

X₁ =17.5. (10)

Полученные 4 отношения (числа)

=17.5 - (для ), =10.5 - (для ),

=40,0 - (для ), =9.0 - (для )

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

Оказывается, при ”плавном увеличении” свободной переменной X₁ первой обратится в нуль базисная переменная , для которой отношение меньше, чем аналогичные величины для остальных базисных переменных. С экономической точки зрения это означает, что при начавшемся “плавном” производстве первого изделия первым исчерпает свой ресурс сырье . Поэтому переменную надо первой переводить в свободные, т. е., переменные и X₁ должны изменить свой статус.

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

Итак, если в выбранном j-ом столбце имеется несколько положительных коэффициентов , то в качестве новой свободной переменной следует выбрать переменную в строке с номером i, для которого отношение наименьшее. Такой выбор означает, что при ”плавном увеличении” свободной переменной X_j первой обратится в нуль базисная переменная X_i, для которой отношение меньше, чем для остальных базисных переменных. Требование минимума позволяет отсеять все недопустимые базисные решения.

Отметим, что соотношение не может быть использовано для определения номера i при A_ij  0, так как в этом случае X_i становится отрицательным, а деление на ноль невозможно.

А как поступить в случае, если в выбранном j-ом столбце положительные коэффициенты A_ij отсутствуют? В этом случае увеличением X_j нельзя добиться уменьшения базисных переменных, претендующих на роль свободных переменных, оптимального значения целевой функции не существует.