7. Условие оптимальности дбр

Определение. Вектор-строка, на которую умножается слева x_N в уравнении для ЦФ (13), называется век­тором относительных оценок, т.к. он указывает, в какую сторону и насколько изменится ЦФ при изменении x_N.

Обозначим этот вектор через d_N. Его j-ый элемент определяется так:

Если относительная оценка (d_N)_j, то небазисной переменной (x_N)_j положительна или равна нулю, но значение ЦФ не увеличивается при увеличении (x_N)_j, начиная с нуля [11].

Теорема (условие оптимальности). Для ДБР x⁰ операция замещения, при которой (x_N)_p вводится в базис, изменяет значение ЦФ на величину

где

Если d_N≥0, то x⁰ оптимально.

ЗЛП будем называть невырожденной, если все ее ДБР не вырождены. Справедлива теорема, обратная последней теореме.

Теорема. Пусть ЗЛП является невырожденной, а x⁰ – ДБР, являющееся ее решением. Тогда d_N≥0.

В том случае, если ЗЛП не является невырожденной, предыдущая теорема приобретает вид:

Теорема. Для того, чтобы ДБР x⁰ являлось решением исходной ЗЛП, необходимо и достаточно су­ществование такого базиса для x⁰, для которого d_N≥0.

Теорема. Если некоторому ДБР исходной задачи соответствует задача, для которой существует не­базисная переменная (x_N)_p такая, что (d_N)_p<0 и (a_N)_*p≤0, то целевая функция исходной задачи не ограни­чена на множестве допустимых решений (θ не ограничено сверху и можно сколько угодно увеличивать целевую функцию).

Пример 7.1

Дана ЗЛП

.

Знайти всі компоненти перетвореної задачі для ДБР, який відповідає базису . Чи є оптимальним цей ДБР?

Розв’язок

Базисні, небазисні змінні та відповідні їм векторикоєфіцієнтів ЦФ:

.

Небазисна матриця та вектор правих частин обмежень:

.

Базисна матриця та матриця, обернена до неї:

.

Значення базисних змінних та ЦФ:

Вектор відносних оцінок небазисних змінних:

Оскільки вектор відносних оцінок небазисних змінних містить додатні компоненти, а задача на максимум, то поточний базисний розв'язок не є оптимальним.

8. Схема симплекс-метода

Рассмотренные в разделах 6-7 способы перехода от одного ДБР к другому и теоремы ЛП, позволяют построить так называемый симплекс-метод решения ЗЛП в канонической форме, который имеет сле­дующую схему:

Шаг 0. Построение начального ЗЛП.

Пусть задано ДБР x⁰ исходной ЗЛП (такое ДБР называется начальным). Пусть данному ДБР соот­ветствует базис ß, вектор базисных переменных x_B=B^–1β, небазисных переменных x_N, базисная матрица B, небазисная матрица N.

Шаг 1. Вычисление компонент вектора относительных оценок небазисных переменных.

Шаг 2. Проверка выполнения условия оптимальности.

Если выполняется d_N≥0, то прекратить вычисления – текущее ДБР является решением исходной задачи. Иначе – перейти на шаг 3.

Шаг 3. Выбор небазисной переменной (x_N)_p, вводимой во множество базисных переменных.

Выбрать p, для которого (d_N)_p<0 (обычно p соответствует максимальная по модулю отрицательная компонента d_N).

Шаг 4. Выбор базисной переменной, выводимой из множества базисных переменных.

Вычислить _*p=B^–1a_*p (пересчет столбца вводимого в базис).

Если _*p<0, то прекратить вычисления – целевая функция не ограничена сверху.

Выбрать q, для которого выполняется , т.е. переменная (x_B)_q будет выведена из множества базисных переменных.

Шаг 5. Операция замещения.

Построить базис нового ДБР путем замены q-го столбца _*p текущего базиса ß на столбец _*p. Построить новые базисную матрицу B и небазисную матрицу N. Найти новые значения базисных переменных x_B=B^–1b и ЦФ c_B^Tβ.

Перейти на шаг1.

Пример 4

Дана система ограничений:

Являются ли базисами данной системы, следующие множества векторов,

• ,

• ,

• . ?

если да , то какие решения им соответствуют:

Решение. Базисом β матрицы А называется набор из линейно-независимых столбцов β= .

Решение называется допустимым базисным решением если оно является базисным и все его компоненты не отрицательны.

В нашей задаче m=3, n=5. То есть количество претендентов на базис в нашей задаче будет не более, чем .

а) Рассмотрим первое множество векторов - . Составим матрицу из этих векторов, если её детерминант будет отличен от нуля, то эти векторы составляют базис:

.

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

Соответствующее базисное решение имеет вид:

- небазисные переменные

переменные

- базисные переменные;.так как они ≥ 0, то мы имеем допустимое БР

b) Рассмотрим множество векторов - .

Теперь составим матрицу из соответствующих векторов и найдём её определителю:

Значит множество векторов является базисом. Найдём соответствующее ему базисное решение, для этого выпишем уравнения системы с учетом того, что :

Итак, данному базису соответствует решение: