Файл: Материалы по курсу (часть 1).docx

Определитель Δ = 5 (перебираем все определители матрицы системы и расширенной матрицы) они все между собой будут равны, следовательно, система совместна, т.к. r_c = r_p_.

На самом деле r показывает число независимых линейных уравнений.

Рассмотрим следующие случаи:

1) r = n (ранг равен числу неизвестных) Система имеет единственно решение: x_j = Δ_j / Δ

(определитель матрицы, где j-тый столбец заменили на свободные члены / обычный определитель)

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

Если хоть какой-то x отрицательный, то система решений не имеет.

2) r = m (ранг равен числу уравнений)

Система имеет бесконечное множество решений, т.е. совокупность значений x₁, x₂, …, x_n, удовлетворяющий уравнениям – ограничениям.

Если среди этих решений нет ни одного, для которого все x₁, x₂, …, x_n неотрицательны, это значит, что основная задача не имеет допустимого решения.

Если же есть какие-то решения системы, для которых все x₁, x₂, …, x_nнеотрицательны, то каждое из них допустимо.

Возникает вопрос – какое из допустимых решений будет оптимальным. Решение производится в зависимости от соотношения n и m.

n – m = 2	n – m > 2
Геометрический способ решения	Вычислительные способы решения

Используется прием:

1) (n-m) – количество свободных переменных, остальные переменные – базисные.

2) В области этих свободных переменных ищем ОДР.

4) Геометрическая интерпретация озлп.

Пусть имеется задача ЛП с n независимыми x₁, x₂, …, x_nи m линейно-независимыми уравнениями, в которой n-m = 2.

Алгоритм решения:

1) Выбираем 2 свободные переменные (пусть x₁ и x₂).

2) Остальные переменные (базисные) выражаем через эти 2, используя метод Гаусса (последовательного исключения переменных).

3) Получаем m уравнений следующего вида:

m штук уравнений

4) В области свободных переменных (координаты x₁ и x₂) находим ОДР, для которой все базисные переменные будут не отрицательными (х_j ≥ 0, j = , т.е.работает в 1 квадранте).

5) Для каждой базисной переменной проделываем следующее:

x₃ = 0, ( = 0), т.е. приравниваем правую часть к нулю и строим прямые.

– по одну сторону соответствующая базовая переменная будет ≥ 0, эту часть и заштриховываем;

– по другую сторону соответствующая базовая переменная будет < 0.

6) Совмещаем все положительные полуплоскости и получаем ОДР.

(Как правило, ОДР представляет собой выпуклый многоугольник и стороны его ограничивают область. Всякая ОДР удовлетворяет системе ограничений (*)).

7) Для нахождения оптимального решения, необходимо построить L и проанализировать ее положение относительно ОДР.

Анализ положения l относительно одр.

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

L = (**), где x_j – элементы решения

k = n – m = 2 (свободные переменные)

Каждая базисная переменная выражена через свободные

Если x₁ и x₂– свободные переменные, то базисные переменные –

Дадим геометрическую интерпретацию поиска оптимального решения.

1) Выразим L через свободные переменные: L = γ₀ + γ₁*x₁ + γ₂*x₂ (1)

Очевидно, что минимум L достигается при тех же значениях x₁ и x₂, что и для функции L’ = L – γ₀= γ₁*x₁ + γ₂*x₂

2) Придадим L’ некоторое постоянное значение: L’ = С.

Тогда γ₁*x₁ + γ₂*x₂= С – уравнение прямой.

х₂ = – (γ₁/ γ₂)* x₁ + (С / γ₂), т.е. угловой коэффициент = – (γ₁/ γ₂)

3) На самом деле, основная прямая определяется выражением L’ = 0 и проходит через начало координат. Её легко построить по двум точкам: (0;0) и (γ₂; – γ₁)

Положение основной прямой на плоскости Х₁ОХ₂ и направление уменьшения значения L’ будет зависеть от величин и знаков коэффициентов γ₁и γ₂.

Если знаки γ₁и γ₂одинаковые, то прямая лежит во 2 и 4 квадрантах.

Зелеными стрелочками показано направление УМЕНЬШЕНИЯ L’.

(Для примера: если знаки γ₁и γ₂одинаковые (положительные), то

С = γ₁*x₁ + γ₂*x₂и для уменьшения значения С нужно x₁иx₂уменьшать, т.е. двигать вниз)

4) Мысленно перемещаем и находим наиболее удаленную точку, в которой L’ минимальна. Эта точка должна принадлежать ОДР.

Найденная нами точка определяет оптимальное решение.

5) Опустим перпендикуляры на оси x₁ и x_2,таким образом найдем x₁^*и x₂^*. Подставим эти значения в выражения для базисных переменных и найдем полный набор все x₃^*, x₄^*, …, x_n^*

Тогда (x1, x2, …, xn*) – оптимальное решение

L_min = γ₀ + γ₁*x₁^* + γ₂*x₂^*

Пример (метода стр.13 – там условие не надо, а сразу на уравнения смотрим)

Выпишу из лекции некоторые вывода (вдруг в развернутом ответе она потребует)

Некоторые выводы

1) Решение основной задачи ЛП не может лежать внутри ОДР, а может лежать только на границе, т.к. находим экстремально удаленную точку.

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

3) Основная задача может не иметь решения, даже если существует ОДР. Когда ОДР не ограничена сверху (открытая область), в таком случае решения не существует.

4) Оптимальное решение всегда достигается в одной из вершин многоугольника ОДР. Решение, лежащее в одной из вершин – опорное решение, а сама вершина – опорная точка.

5) Для того, чтобы найти оптимальное решение достаточно перебрать все вершины (все опорные точки) и выбрать из них ту, в которой L минимальна.

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

7) Если (m<n) на 3, т.е. n-m=3, то мы приходим к случаю геометрической интерпретации в трехмерном пространстве.

Изменится: - каждое условие-ограничение не прямая, а плоскость

- ОДР если существует – выпуклый многогранник, ограничивающий часть пространства, для которой х₁ ≥ 0, х₂ ≥ 0, …, х_n ≥ 0.

- Вместо основной прямой L’=0 имеем основную плоскость, которую также мысленно будем перемещать относительно самой себя.

Опорные точки заменяются на опорные вершины.

Такую же интерпретацию можем распространить и на n-мерное пространство.