§2. Методы исследования функций численного анализа.

Идея симплексного метода (метода Данцига).

При больших значениях mиn трудно найти оптимальное решение путем перебора всех его допустимых решений. Поэтому существуетупорядоченная схема перебора, получившая название симплексного метода [1-4]. Поясним идею симплексного метода на следующем примере:

при условиях

По теореме Кронекера-Капелли [2] для совместности линейной системы необходимо и достаточно, чтобы ранг матрицы A r(A) был равен рангу расширенной матрицы R r(R).r(A) есть наибольший из порядков миноров, отличных от нуля (т.е. r(A) – целое число). Известно, что r(A) не меняется, если к какому-либо столбцу (строке) прибавить произвольную линейную комбинацию других столбцов (строк) этой матрицы. Кроме того, r(A) не изменится, если какой-либо столбец, состоящий из нулей, удалить. Итак

= ?

Прибавив первый столбец, умноженный на (-1), к пятому, а затем и к четвертому, получим

Выполняем аналогичные преобразования и, в итоге, получим

Соответственно, ранг расширенной матрицы будет равен также

= 3.

Следовательно, наша система совместна.

При формулировке задач ЛП могут быть два случая:

1. (– количество неизвестных в системе).

Решение системы единственное. Задача ЛП не имеет смысла.

2. .Этот случай представляет для нас интерес.Неизвестных больше, чем уравнений в системе. Задаваясь каждый разсвободными неизвестными, получим в итоге множество решений системы, из которых в соответствии с функцией цели выбирается то решение, которое дает оптимальный результат. В нашем примере

Линейная система уравнений называется системой с базисом, если в каждом уравнении содержится неизвестное с коэффициентом +1, отсутствующее в остальных уравнениях. Эти неизвестные называются базисными, оставшиеся – свободными. Число базисных неизвестных равно числу уравнений.

Линейная система уравнений называется канонической, если она является системой с базисом, а все В данном выше числовом примере система уравнений является канонической.

Примеры канонических систем:

1. 

2. 

Примеры неканонических систем:

1. 

Система неканоническая, так как один из свободных членов отрицателен.

2. 

Система неканоническая, так как в системе отсутствует базис.

3. 

Система неканоническая, так как в системе отсутствует базис.

Чтобы перейти к каноническому виду, необходимо в первом случае уравнение умножить на (-1), а затем во всех трех случаях ввести базис (полностью или частично). Как было показано выше, в исходном числовом примере система уравнений каноническая. Итак,

(1)

при условиях

В системе базисных переменных три , а свободных два. Выразим целевую функцию и базисные переменные через свободные переменные.

Но F уже выражена, а базисные переменные примут следующий вид:

( 2 )

( 3 )

Все должны быть неотрицательны, т.е..

Зададим наименьшие возможные значения , при этом получим.Эторешение, удовлетворяющее ограничениям, т.е. допустимое. Проанализируем, нельзя ли увеличением значений уменьшить? Из выражения

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

При этом Переменное выведено из базиса, вместо него в базис включен астали свободными переменными.

Выразим новые базисные переменные и функциюFчерез.найдём.Подставимв выражения

(1), (2), (3).Получим:

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

Достигнуто оптимальное решение:

Полученное решение называется базисным, так как свободные переменные равны нулю.Следует отметить, что оптимальное решение получено, когда в выражении дляFполученные значения коэффициентов при неизвестных положительны, а в процессе решения значениеFтолько понижалось от 3 до 1, т.е. перебор был организованным.

Пример. На множестве решений системы

Найти минимальное значение целевой функции

Решение.Перепишем систему ограничений (1) в виде

Исходным базисным решением является решение (7; 0; 0; 12; 0; 10), при котором значение функции равно нулю. Целевая функция уже выражена через небазисные переменные. Значение целевой функции может быть уменьшено за счет увеличения . Среди коэффициентов прив системе (2) имеются отрицательные:и. Находим отношения(из второго уравнения системы (2)):. Элемент 4 – разрешающий. Из старого базиса исключими введем в него из небазисных переменных. Для этого выразимчерезииз второго уравнения и найденное выражение подставим вместов первое и третье уравнения системы (2), а также в выражениеF.

Получим систему (3):

Новое базисное решение имеет вид: (10; 0; 3; 0; 0; 1). . ЗначениеF можно уменьшить за счет увеличения. Среди коэффициентов прив системе (3) только один отрицательный:Элементразрещающий. Перейдем к новому базису:

Новое базисное решение имеет вид: ,Дальнейшее уменьшение значения целевой функции невозможно.

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