Решение задачи линейного программирования методом последовательного улучшения плана ( Симплексный методом )

Презентация:



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

Симплекс-метод Симплексный метод – это вычислительная процедура, основанная на принципе последовательного улучшения решений при переходе от одной базисной.
1 Стандартная задача Матричная форма записи § 1.4. Специальные виды задач ЛП максимизацииминимизации Обозначения.
Математика Экономико-математические методы Векслер В.А., к.п.н.
Прямая и двойственная задачи и их решение симплекс-методом Лекции 8, 9.
Транспортная задача частный случай задачи линейного программирования.
Симплекс-метод. Сущность метода Первый шаг. Найти допустимое решение (план), соответствующее одной из вершин области допустимых решений. Второй.
Транспонирование матрицы переход от матрицы А к мат­рице А', в которой строки и столбцы поменялись местами с сохранением порядка. Матрица А' называется.
Симплекс-метод Лекции 6, 7. Симплекс-метод с естественным базисом Симплекс –метод основан на переходе от одного опорного плана к другому, при котором.
1 Математические методы Математические методы Теоретический учебный материал по дисциплине.
Метод искусственного базиса. Сущность метода Если в системе ограничений, приведенной к каноническому виду, не удается сразу выделить базисные переменные,
LOGO Примеры задач линейного программирования. Для изготовления двух видов продукции Р1 и Р2 используют четыре вида ресурсов: S1, S2, S3 и S4. Задача.
1/ 23 Это развёрнутая форма записи Это развёрнутая форма записи Линейная целевая функция Линейные ограни- чения Условия неотрицательности переменных.
Двойственные задачи. Каждой задаче линейного программирования соответствует задача, называемая двойственной или сопряженной по отношению к исходной задаче.
Примеры задач линейного программирования. Для изготовления двух видов продукции Р 1 и Р 2 используют четыре вида ресурсов: S1, S2, S3 и S4. Задача об.
Основная задача линейного программирования Симплекс-метод.
Высшая математика Кафедра математики и моделирования Преподаватель Никулина Л. С. Четвертый семестр.
Задача о назначениях. Венгерский метод решения задачи о назначениях. Малофеевой Екатерины гр. ММ-61.
Задача линейного программирования. Табличный симплекс-метод.
Транспортная задача линейного программированияТранспортная задача линейного программирования.
Транксрипт:

Решение задачи линейного программирования методом последовательного улучшения плана ( Симплексный методом )

Пример Прибыль от реализации 1 т кефира составляет 2 млн руб., а от 1 т молока – 1 млн руб. Затраты рабочего времени на молоко 4 ч / т, а на кефир – 2 ч/т. Рабочий день – 8 часов. Расход сырья: 5 ед. на 1 т кефира и 1 ед. на 1 т молока. Всего имеется в запасе 5 ед. сырья. Составить такой план производства продукции, чтобы прибыль от ее реализации была максимальной.

Экономико-математическая модель задачи

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

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

На каждой итерации (на каждом шаге) может увеличиваться лишь одна свободная переменная. Это приводит к увеличению f(x), если перед этой переменной стоит знак «+».

Табличный симплекс-метод Удобно использовать так называемые симплексные таблицы, то есть преобразовывать не сами уравнения, а коэффициенты при переменных Х1Х1 Х2Х2 Х3Х3 Х4Х4 Q Х3Х3 Х4Х4 f(x)

Табличный симплекс-метод Х1Х1 Х2Х2 Х3Х3 Х4Х4 Q Х3Х Х4Х f(x)0–2–100

Табличный симплекс-метод Х1Х1 Х2Х2 Х3Х3 Х4Х4 Q Х3Х /2 Х4Х /5 f(x)0–2–100–

Алгоритм 1. Проверка оптимальности. Если все элементы последней строки таблицы неотрицательны, то план оптимален. 2. Если в последней строке есть отрицательные элементы, перейти к пункту Выбор ведущего столбца. В последней строке таблицы найти максимальный по абсолютному значению отрицательный элемент. Столбец, в котором находится этот элемент, будет ведущим. 4. Нахождение ведущей строки. Разделить элементы столбца на соответствующие положительные элементы ведущего столбца и найти минимальное из этих отношений. Строка, соответствующая этому минимальному отношению, будет ведущей. Элемент, расположенный на пересечении ведущего столбца и ведущей строки, – ведущий. 5. Преобразование таблицы. Разделить ведущую строку на ведущий элемент. Остальные строки таблицы преобразовываются по следующим правилам: пусть надо преобразовать i-ю строку, для этого необходимо умножить преобразованную ведущую строку на элемент i-й строки и ведущего столбца и результат вычесть из i-й строки. В преобразованной таким образом таблице изменить номера базисных переменных: ведущей строке будет соответствовать теперь номер ведущего столбца.

СПАСИБО ЗА ВНИМАНИЕ! к.т.н., доц. Калашникова Т.В.