Симплекс метод. Лекция 5

Основная задача ЛП со смешенными ограничениями:
Филиппова А.С., каф. ИТ, БГПУ

Математический аппарат задач ЛП
Когда ограничения области допустимых решений в мат.модели задачи записаны в виде неравенств, то выполняют следующие преобразования:
Филиппова А.С., каф. ИТ, БГПУ

Пример.
Филиппова А.С., каф. ИТ, БГПУ

Пример.
Филиппова А.С., каф. ИТ, БГПУ

В матричном виде задача ЛП (ЗЛП):
Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ

Симплексный метод решения ЗЛП
Используется математическое описание задачи в канонической форме и матричном виде
Алгоритм состоит из последовательности построения матриц. Каждый шаг приближает к получению решения:
определить ведущий столбец;
определить ведущий элемент;
определить ведущую строку;
составить уравнения пересчета матрицы;
выполнить пересчет матрицы;
проверить результата пересчета матрицы на оптимальность;
если найденное решение оптимально, то выписать ответ, если найденное решение не оптимально, но на п. 1)
Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ

Определение ответа задачи по симплекс таблице:
каждому отрицательному коэффициенту в векторе решений C ставится в соответствие нулевой коэффициент для соответствующей переменной в ответе;
для каждого нулевого коэффициента в векторе решений (т.е. правильного столбца) ставится в соответствие значение свободного члена (из вектора b) из строки содержащей «1» в столбце данной переменной.
Филиппова А.С., каф. ИТ, БГПУ

Ведущим столбцом м.б. Назначен любой столбец t матрицы, удовлетворяющий одному из условий:
Первый столбец, содержащий элемент >0 в строке (векторе С ) решений;
Столбец, содержащий наибольший положительный элемент в строке (векторе С) решений;
Если столбец t содержит элемент удовлетворяющий условию:
Филиппова А.С., каф. ИТ, БГПУ
При решении задачи на max
При решении задачи на min

Ведущим столбцом м.б. Назначен любой столбец t матрицы, удовлетворяющий одному из условий:
Первый столбец, содержащий элемент >0 в строке (векторе С ) решений;
Столбец, содержащий наибольший положительный элемент в строке (векторе С) решений;
Если столбец t содержит элемент удовлетворяющий условию:
Филиппова А.С., каф. ИТ, БГПУ
При решении задачи на max
При решении задачи на min
способ 3) самый короткий!
1) и 2) – произвольный
характер

Ведущим столбцом м.б. Назначен любой столбец t матрицы, удовлетворяющий одному из условий:
Первый столбец, содержащий элемент >0 в строке (векторе С ) решений;
Столбец, содержащий наибольший положительный элемент в строке (векторе С) решений;
Если столбец t содержит элемент удовлетворяющий условию:
Филиппова А.С., каф. ИТ, БГПУ
При решении задачи на max
При решении задачи на min
!!! Вычисления 3) выполняют только для >0 элементов столбца

Филиппова А.С., каф. ИТ, БГПУ
Замечание. Этот критерий для задач, целевая функция которых содержит только положительны коэффициенты (для общего случая критерий нужно уточнять)

Филиппова А.С., каф. ИТ, БГПУ
Пример.

Филиппова А.С., каф. ИТ, БГПУ
Пример.
Приведем к задаче канонического вида (добавим фиктивные переменные)

Филиппова А.С., каф. ИТ, БГПУ
Пример.
Приведем к задаче канонического вида (добавим фиктивные переменные)

Филиппова А.С., каф. ИТ, БГПУ
Условие задачи в матричном виде:

Филиппова А.С., каф. ИТ, БГПУ
Условие задачи в матричном виде:
Определим ведущий столбец. У 4-х столбцов коэф-ты > 0,
Т.е. Любой столбец м.б. ведущим.
Используем 3) :

Филиппова А.С., каф. ИТ, БГПУ
Условие задачи в матричном виде:
Определим ведущий столбец. У 4-х столбцов коэф-ты > 0,
Т.е. Любой столбец м.б. ведущим.
Используем 3) :

Филиппова А.С., каф. ИТ, БГПУ
Условие задачи в матричном виде:
Определим ведущий столбец. У 4-х столбцов коэф-ты > 0,
Т.е. Любой столбец м.б. ведущим.
Используем 3) :

Филиппова А.С., каф. ИТ, БГПУ
Условие задачи в матричном виде:
Определим ведущий столбец. У 4-х столбцов коэф-ты > 0,
Т.е. Любой столбец м.б. ведущим.
Используем 3) :

Филиппова А.С., каф. ИТ, БГПУ
Условие задачи в матричном виде:
Определим ведущий столбец. У 4-х столбцов коэф-ты > 0,
Т.е. Любой столбец м.б. ведущим.
Используем 3) :

Филиппова А.С., каф. ИТ, БГПУ
Условие задачи в матричном виде:
Определим ведущий столбец. У 4-х столбцов коэф-ты > 0,
Т.е. Любой столбец м.б. ведущим.
Используем 3) :
! мах

Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ
В остальных строках матрицы коэффициент при второй переменной д.б. =0
Такое преобразование строк матрицы называется преобразованием
ЖОРДАНА- ГАУССА

Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ
Т.к. есть еще элементы вектора решений >0, то выполняем аналогичные шаги для этих столбцов

Филиппова А.С., каф. ИТ, БГПУ
Т.к. есть еще элементы вектора решений >0, то выполняем аналогичные шаги для этих столбцов
Max!!!

Филиппова А.С., каф. ИТ, БГПУ
Т.к. есть еще элементы вектора решений >0, то выполняем аналогичные шаги для этих столбцов
Max!!!

Филиппова А.С., каф. ИТ, БГПУ
Т.к. есть еще элементы вектора решений >0, то выполняем аналогичные шаги для этих столбцов

Филиппова А.С., каф. ИТ, БГПУ
Т.к. есть еще элементы вектора решений >0, то выполняем аналогичные шаги для этих столбцов
Max!!!

Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ

Филиппова А.С., каф. ИТ, БГПУ
Общий случай решения задач ЛП симплексным методом

Филиппова А.С., каф. ИТ, БГПУ
1) Мат.модель приводят ко 2-ой канонической форме, потом добавляют один шаг – применяют процедуру Жордана-Гауса поочередно к тем столбцам, которые в последней строке матрицы содержит отрицательные коэффициенты, добиваясь при этом замены отрицательных значений коэффициентов на нулевые
Общий случай решения задач ЛП симплексным методом

Филиппова А.С., каф. ИТ, БГПУ
Общий случай решения задач ЛП симплексным методом