SEMINAR2 (1155924), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

при ограничениях

Учебный вопрос № 3.

Жордановы исключения как метод линейной алгебры.

Пусть рассматривается система

из линейных форм с независимыми переменными . Эта система может быть записана в виде таблицы:

Определение: Шагом обыкновенного Жорданова исключения (ОЖИ), произведенным над таблицей, с разрешающим элементом , с -й разрешающей строкой и -м разрешающим столбцом называется схематизированная операция перемены ролями между зависимой переменной и независимой , т.е. операция решения уравнения относительно , подстановки его во все остальные уравнения системы и записи полученной системы в виде новой таблицы, аналогичной исходной. Легко убедится, что новая таблица имеет вид:

где , причем все элементы таблицы следует разделить на .

Действительно, если , то

Тогда

Таким образом один шаг ОЖИ с разрешающим элементом переводит исходную таблицу в новую по следующей схеме:

1. Разрешающий элемент заменяется единицей;

2. Остальные элементы разрешающего ( -го) столбца остаются без изменений;

3. Остальные элементы разрешающей ( -й) строки меняют свой знак;

4. «Обыкновенные» элементы , ( ) вычисляются по формуле ;

5. Все элементы новой таблицы делятся на разрешающий элемент .

Однако, как будет видно далее, при решении задач ЛП симплекс-методом гораздо удобнее использовать другой вид Жордановых исключений - т.н. модифицированные Жордановы исключения (МЖИ). В этом случае систему записывают как

и тогда один шаг МЖИ выполняется по следующей схеме:

1. Разрешающий элемент заменяется единицей;

2. Остальные элементы разрешающей строки остаются без изменений;

3. Остальные элементы разрешающего столбца меняют свой знак;

4. «Обыкновенные» элементы , ( ) вычисляются по формуле ;

5. Все элементы новой таблицы делятся на разрешающий элемент .

Действительно, из

находим

Учебный вопрос № 4.

Правило составления симплекс-таблицы.

При изучении учебного вопроса № 2 мы получили каноническую форму записи задачи ЛП. Теперь нам необходимо записать симплекс-таблицу и перейти к решению задачи. Для этого необходимо выполнить следующие действия:

• Выразим балансовые условия относительно зависимых переменных .

• Полученные выражения сведем в таблицу, в которой ( с учетом применения МЖИ) элементы есть коэффициенты при , столбец есть столбец элементов и -строка есть коэффициенты при в максимизируемой линейной форме.

Или в рамках числового примера:

Учебный вопрос № 5.

Применение МЖИ для нахождения опорного и оптимального решений.

А. Нахождение опорного решения.

В силу основного свойства решения задачи ЛП это решение содержит нулевых значений и - положительных. Такое решение называют «опорным» или «базисным». Рассмотрим исходную симплекс-таблицу. Положим значение независимых переменных и посмотрим, будут ли значения зависимых переменных положительны. Подобная проверка легко реализуется, т.к. при нулевых независимых переменных . Если все неотрицательны, то это означает, что опорное решение задачи получено. Если же среди есть отрицательные значения, то полученное решение не является опорным, т.к. не принадлежит области допустимых значений.

Таким образом, нахождение опорного решения задачи формально сводится к избавлению от отрицательных элементов в последнем столбце симплекс-таблицы. Эту операцию можно выполнить путем придания некоторого положительного значения одной из независимых переменных, находящихся в верху таблицы, причем на ее место с нулевым значением пойдет одна из зависимых переменных. Следует иметь в виду, что подобная перемена ролями двух переменных не должна привести к нарушению балансовых условий. Все это определяет следующее правило выбора разрешающего элемента для выполнения одного шага МЖИ:

• В строке, содержащей отрицательный элемент в последнем (свободном) столбце, находится отрицательный член (если его не существует, то задача несовместна). Пусть это будет член . Так отмечается разрешающий столбец . Придание некоторого положительного значения переменной должно привести к получению опорного решения. Для определения этого значения находим минимальное неотрицательное значение отношения по всем . Следует иметь в виду, что отношение типа не должны приниматься во внимание - они считаются «отрицательными». Строка таблицы, в которой достигается минимум и будет разрешающей строкой.

• Выполняется один шаг МЖИ и вновь проверяется последний (свободный) столбец таблицы. Эта процедура повторяется до тех пор, пока мы не получим опорное решение.

Б. Нахождение оптимального решения.

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

Если же в -строке матрицы есть отрицательные коэффициенты, то полученное решение может быть улучшено если соответствующая ему переменная вместо нулевого значения получит какое-либо положительное значение. Для определение допустимого положительного значения этой переменной находится минимальное неотрицательное значение отношения по всем , где - номер столбца: содержащего отрицательный элемент в -строке. Отношения вида опять не рассматриваем, считая их «отрицательными». Строка таблицы, в которой достигается минимум и будет разрешающей строкой. Если же столбец над отрицательным членом -строки не содержит ни одного положительного элемента, то это означает что задача не имеет решения. С найденным таким образом разрешающим элементом выполняется один шаг МЖИ и снова просматривается -строка до тех пор, пока в ней не окажутся только положительные элементы.

Занятия 5,6. Решение задач по оптимальному целераспределению.

Время: 4 часа.

Характеристики

Список файлов семинаров