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

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

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

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

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

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

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

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

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

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

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

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