Симплекс метод

Сентябрь 2, 2022

Главная
Алгебра
Симплекс метод

Содержание

2. Приведение записи задачи к каноническому виду Рассмотрим в качестве исходной задачу определения оптимальной производственной программы, записанную
4. Убедимся в том, что мы располагаем неотрицательным базисным решением. Признак наличия такого решения следующий: в каждом
5. Как получить неотрицательное базисное решение 1. Приведение к каноническому виду симметричной задачи на максимум Z позволяет
6. Что представляет собой базисное решение Каждый вектор единичной подматрицы образован коэффициентами переменных, которые именуются базисными. Остальные
7. Как реализуется симплекс-метод Получив начальное базисное решение, проверяем запись целевой функции. Если значение целевой функции нельзя
8. Как определить, что оптимум достигнут Через конечное число шагов получаем такую запись целевой функции, которая подтверждает
9. Что представляет собой симплексная таблица Симплексная таблица является компактной записью решения задачи симплекс-методом. Для ее заполнения
11. В данной таблице: БП – совокупность базисных переменных; – вектор коэффициентов, стоящих в целевой функции при
12. Процедура начинается с анализа заключительной строки таблицы, именуемой индексной, строкой оценок Если в данной строке при
13. Среди отрицательных при решении задачи на максимум (среди положительных при решении на min) выбираем наибольшую по
14. Как заполнить новую симплексную таблицу Изменяем состав базисных переменных, а также состав компонентов вектора Замену определяет
15. Пример. Пусть в качестве разрешающего выбран элемент . Для вычисления элемента новой таблицы применяем следующую процедуру:
16. Общая формулировка «правила прямоугольника» Из строк и столбцов разрешающего элемента и пересчитываемого элемента формируем прямоугольник; Из
17. Приведем в качестве образца пример заполнения новой таблицы при выборе в качестве разрешающего элемента.
18. Если в результате преобразований все оценки индексной строки оказались неотрицательны при решении на max (или неположительны
19. Симплекс-метод с искусственным базисом Применяется при решении задач, у которых получение исходного неотрицательного базисного решения сопряжено
21. Скачать презентацию

Слайд 2

Приведение записи задачи к каноническому виду
Рассмотрим в качестве исходной задачу

определения оптимальной производственной программы, записанную в симметричном виде. Для изменения формы записи задачи используем неотрицательные балансовые переменные, которые добавим к левым частям неравенств. В целевую функцию введем балансовые переменные с нулевыми коэффициентами.

Слайд 3

Слайд 4

Убедимся в том, что мы располагаем неотрицательным базисным решением. Признак наличия

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

Слайд 5

Как получить неотрицательное базисное решение
1. Приведение к каноническому виду симметричной задачи

на максимум Z позволяет сразу выделить единичную подматрицу и базисное решение.
2. Матрицу системы можно преобразовать методом «Жордана-Гаусса» и получить в итоге единичную подматрицу и базисное решение
3. Можно ввести искусственные переменные и сформировать единичную подматрицу их коэффициентами

Слайд 6

Что представляет собой базисное решение
Каждый вектор единичной подматрицы образован коэффициентами переменных,

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

Слайд 7

Как реализуется симплекс-метод
Получив начальное базисное решение, проверяем запись целевой функции. Если

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

Слайд 8

Как определить, что оптимум достигнут
Через конечное число шагов получаем такую запись

целевой функции, которая подтверждает невозможность получения дальнейшего прироста ее значения. Так, при решении задачи на максимум Z, это будет выражение, в котором все переменные имеют отрицательные коэффициенты. Делаем вывод: данное базисное решение является оптимальным.

Слайд 9

Что представляет собой симплексная таблица
Симплексная таблица является компактной записью решения задачи

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

Слайд 10

Слайд 11

В данной таблице: БП – совокупность
базисных переменных; – вектор

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

Слайд 12

Процедура начинается с анализа заключительной строки таблицы, именуемой индексной, строкой

оценок
Если в данной строке при решении задачи на максимум целевой функции все

а при решении на min все

то начальное базисное решение и является оптимальным.
Если существуют

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

Слайд 13

Среди отрицательных
при решении задачи на максимум (среди положительных

при решении на min) выбираем наибольшую по модулю. В соответствующем ей столбце

среди положительных коэффициентов

выделяем разрешающий элемент, для которого отношение

является минимальным.

Слайд 14

Как заполнить новую симплексную таблицу
Изменяем состав базисных переменных, а также состав

компонентов вектора Замену определяет местоположение разрешающего элемента;
Переносим без изменений столбцы тех переменных, которые остались базисными;
На месте разрешающего элемента ставим 1, на остальные места в данном столбце ставим 0. Остальные места в строке заполняем числами, полученными путем деления прежних компонентов на разрешающий элемент;
Остальные компоненты таблицы определяем по «правилу прямоугольника»

Слайд 15

Пример.
Пусть в качестве разрешающего выбран элемент
. Для вычисления

элемента

новой таблицы применяем следующую процедуру:

Слайд 16

Общая формулировка «правила прямоугольника»
Из строк и столбцов разрешающего элемента и пересчитываемого

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

Слайд 17

Приведем в качестве образца пример заполнения новой таблицы при выборе

в качестве разрешающего элемента.

Слайд 18

Если в результате преобразований все оценки индексной строки оказались неотрицательны

при решении на max (или неположительны при решении на min), то оптимальное решение получено. В противном случае процедура повторяется.
Ответ задачи состоит из оптимальных значений переменных

и экстремального значения Z. Экстремум целевой функции размещен в ячейке

оптимальные значения базисных переменных находятся в столбце

значения свободных переменных равны нулю.

Слайд 19