В. 23 Алгоритм двойного симплексного метода

Двойственный симплексный метод предназначен для решения задачи линейной оптимизации вида: сх → min, Ах ≥ b, x ≥ 0

Пусть выполнены следующие условия:

1. задача ЛП имеет стандартный вид на минимум;

2. вектор коэффициентов целевой функции (с) неотрицателен;

3. ограничения должны быть типа «≥»;

4. ограничения на переменные должны быть типа «≥», (x_j≥0)

Тогда можно построить начальную симплексную таблицу:

Оценки Δ_j для переменных xj будут, очевидно, равны - с_j. Значение целевой функции Δ₀=0.

Алгоритм двойственного симплексного метода:

Шаг 0. Построить начальную симплексную таблицу. Перейти на шаг 1.

Шаг 1. Проверить значения базисных переменных в столбце «БДР». Если все значения неотрицательны, то найдено оптимальное решение перейти на шаг 7. Если хотя бы одно значение отрицательно, перейти на шаг 2.

Шаг 2. Среди отрицательных значений переменных столбца «БДР» выбрать максималь­ное по модулю значение (если их несколько, выбрать любое из них) и соответству­ющую строку объявить ведущей (r). Перейти на шаг 3.

Шаг 3. Проверить коэффициенты матрицы ограничения (а_rj, j=1,...,n) ведущей строки. Если все a_rj ≥0, то задача не имеет решения, перейти на шаг 7. Иначе перейти на шаг 4.

Шаг 4. Для отрицательных элементов ведущей строки рассчитать отношение соответству­ющих элементов строки оценок к элементам ведущей строки. Среди полученных отношений выбрать минимальное (если их несколько - любое). Столбец, соответ­ствующий минимальному отношению, объявить ведущим столбцом (s). Перейти на шаг 5.

Шаг 5. Элемент a_rs, стоящий на пересечении ведущей строки и ведущего столбца объявить ведущим элементом. Перейти на шаг 6.

Шаг 6. Нарисовать новую симплексную таблицу. В столбце "Базис" вместо переменной х_г записать переменную x_s. Применяя преобразование Жордана-Гаусса относи­тельно a_rs, рассчитать значения элементов новой симплексной таблицы. Перейти на шаг 1.

Шаг 7. Конец алгоритма.

Пример в распечатке!

В. 24 Определение выпуклого множества.

Опр1. Множество Х называется выпуклым, если вместе с двумя любыми точками ему принадлежит весь отрезок, соединяющий эти точки.

Опр2. Множество Х называется выпуклым, если для любых x’и x” из Х, и для любых α₁,α₂ Î R (множество всех действительных чисел) таких, что α₁+α₂=1, α₁, α₂ ≥0, точка α₁х’+ α₂х”Î X. Выпуклое множество:

1) α₁=1, α₂=0

Невыпуклое множество:

Окружность - не выпуклое множество, круг – выпуклое.

2) α₁= α₂=1/2; 1/2x’+1/2x”=x

α₁=1, α₂=0

Мы можем воспринимать значение α ₁, α₂ как силу притяжения к полюсам x’ и x”.