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

Тогда возникает новая задача ЛП – найти такие неотрицательные значения (n+m) переменных (х₁, х₂, …, х_n)и (y₁, y₂, …, y_m), чтобы они удовлетворяли системе (**) и обращали L в минимум.

2) Переход к классической постановке задачи.

В такой постановке (х₁, х₂, …, х_n) рассматриваются как свободные переменные, а (y₁, y₂, …, y_m) – базисные.

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

Пример (прикрепляю фото из лекции за 03.03)

6) Симплекс-метод решения задачи лп.

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

Пусть задача ЛП имеет n переменных и m уравнений-ограничений. Будем считать все уравнения независимыми. Мы знаем, что оптимальное решение достигается в одной из опорных точек ОДР, где по крайней мере k переменных (k=n-m) обращается в ноль.

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

1) Выберем k свободных переменных х₁, х₂, …, х_k

2) Оставшиеся (базисные) выразим через эти свободные, тогда получим m уравнений следующего вида:

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

3) Мы знаем, что опорное решение точно достигается в точке, в которой свободные переменные равны 0, т.е. х₁ = х₂ = … = х_k= 0, тогда базисные переменные будут равные свободным членам , такое опорное решение допустимо если все β_i, i = будут .

Если какое-то β_i< 0, то такое решение – недопустимо и нужно искать не оптимальное, а опорное решение.

Допустим, что все β_i, тогда мы нашли опорную точку.

4) Для того, чтобы определить оптимальное решение мы должны через свободные переменные выразить L. Тогда L = γ₀ + γ₁*x₁ + γ₂*x₂+ … + γ_n*x_n

Если все коэффициенты при х₁, х₂, …, х_k, то оптимум достигнут. При этом это оптимальное решение L_min = γ₀.

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

Иными совами, нужно обменять 2 переменных: свободную и базисную.

Допустим, что γ₁< 0. Переменную x₁ делаем положительной и меняем на базисную. Но из базисных переменных на обмен нужно выбрать ту, к которой:

1. Коэффициент при x₁также имеет отрицательное значение.

2. Которая быстрее всего обращается в 0 при увеличении x₁.

Допустим это строка x_l= .

В опорном решении х₂ = … = х_k= 0.

Тогда, решение в опорной точке: x_l= , нам нужно, чтобы x_l быстрее стремилось к 0, при возрастании x₁.

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

Искать оптимальное решение можно только если мы находимся в опорной точке.

5) Переразрешим систему уравнений-ограничений, относительно новых свободных переменных. Вместо x₁ используем x_l.

6) Переходим в новому опорному решению, в котором все переменные равны 0. x_l становится базисной.

7) Выразим функцию L через эти новые свободные переменные:

L = γ₀⁽¹⁾ + γ₂⁽¹⁾*x₂ + … + γ_k⁽¹⁾*x_k+ γ_l*x_l.

Пример (прикрепляю фото из лекции за 03.03)

7) Табличный алгоритм замены переменных.

Рассмотрим СУ ограничений следующего вида:

Пусть нужно вывести из свободных переменных, переменную x₂ и заменить ее на базисную переменную, т.е. x_j↔ у_i

Раньше бы выражали x₂ через y₃ и подставляли в каждое уравнение.

В пунктах ниже скобка системы не поставилась почему-то, НЕ забудьте ее поставить!

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

1) Перепишем нашу СЛ в следующем виде:

(свободный член – (остальное) )

2) Введем обозначения: (-a_ij= α_ij), тогда ( минус а = альфа)

В ЭТИХ ФОРМУЛАХ ВОЗЛЕ х СТОИТ АЛЬФА!

3) Представим полученную СУ в стандартной табличной форме.

	Св.член	X₁	X₂	X₃	X₄
Y₁		α₁₁	α₁₂	α₁₃	α₁₄
Y₂		α₂₁	α₂₂	α₂₃	α₂₄
Y₃		α₃₁	α₃₂	α₃₃	α₃₄
Y₄		α₄₁	α₄₂	α₄₃	α₄₄
Y₅		α₅₁	α₅₂	α₅₃	α₅₄

4) Произведем замену переменных x_j↔ у_i

Алгоритм замены х_j↔ у_i:

1) Выделим разрешающий элемент α_ij.

Элемент x_j определяет разрешающий столбец, а элемент у_iразрешающую строку. На пересечении этого столбца и строки лежит разрешающий элемент.

Вычислим λ, где (λ = 1/ α_ij) и запишем полученное число в нижней части разрешающей ячейки

2) Все элементы разрешающей строки (кроме α_ij) умножаем на λ и результат записываем в нижних частях ячеек.

3) Все элементы разрешающего столбца умножаем на (-λ) и также записываем в нижней части ячеек, также не трогая разрешающий элемент.

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

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

6) Переписываем таблицу, заменяя x_j↔ у_i(пусть для примера x₂↔ у₁)