Курсовой проект Вариант 20. "Решение оптимизационных задач линейного программирования"
 Скачать 0.59 Mb.
|
|
4 Решение задачи оптимизации на основе симплекс-таблиц Приведём математическую модель задачи к стандартной форме. Для этого в ограничения “меньше или равно” потребуется ввести остаточные переменные, а в ограничения “больше или равно” потребуется ввести избыточные переменные: Х1-Х4=40 (1) 0,8Х1+0,5Х2+0,6Х3+Х5=800 0,2Х1+0,4Х2+0,3Х3+Х6=600 0Х1+0,1Х2+0,1Х3+Х7=120 i ≥ 0, i = 1,…,3 , Е=314Х1+120Х2+128Х3 –>max. В ограничениях (1) отсутствует базисная переменная, т.е. переменная, которая входила бы только в одно из уравнений, причем с коэффициентом равным 1. Поэтому требуется ввести искусственную базисную переменную. Система ограничений с искусственными базисными переменными будет иметь вид: Х1-Х4+Х8=40 (1) 0,8Х1+0,5Х2+0,6Х3+Х5=800 0,2Х1+0,4Х2+0,3Х3+Х6=600 0Х1+0,1Х2+0,1Х3+Х7=120 i ≥ 0, i = 1,…,3 , Составляется искусственная целевая функция – сумма искусственных переменных: W= Х8→ min. Искусственная целевая функция выражается через небазисные переменные. Для этого сначала выразим искусственные переменные через небазисные переменные: Х8=40-Х1+Х4, и подставим их в искусственную целевую функцию: W = 40-Х1+Х4,→ min. Для приведения всей задаче к стандартной форме требуется перейти к искусственной целевой функции, подлежащей максимизации. Для этого она умножается на -1: -W = -40+Х1-Х4,→ max. Приведем полную математическую модель задачи в стандартной форме: Х1-Х4+Х8=40 (1) 0,8Х1+0,5Х2+0,6Х3+Х5=800 0,2Х1+0,4Х2+0,3Х3+Х6=600 0Х1+0,1Х2+0,1Х3+Х7=120 i ≥ 0, i = 1,…,8, Е=314Х1+120Х2+128Х3 –>max, -W = -40+Х1-Х4,→ max. Составим первую симплекс таблицу (таблица 1): Таблица 1
Приведённое в таблице 1 начальное решение является недопустимым: в базисе есть искусственные переменные, и искусственная целевая функция не равна нулю. В случае, когда строка искусственной целевой функции (-W) не будет содержать отрицательных значений, данное решение будет оптимальным. Иначе необходимо составлять следующую симплекс-таблицу. Определим переменную для включения в базис. Она имеет максимальный по модулю отрицательный коэффициент в строке искусственной целевой функции. Смысл такого выбора заключен в следующем. При включении переменной в базис мы тем самым увеличиваем её значение, что, приводим к росту целевую функцию. Очевидно, что при увеличении переменной с наибольшим коэффициентом целевая функция будет увеличиваться быстрее. В нашем случае это будет Х1. Определим переменную для исключения из базиса. Для этого необходимо поделить коэффициенты столбца решения на коэффициенты ведущего столбца (при этом необходимо помнить, чтобы коэффициенты ведущего столбца были положительны). В результате получатся симплексные отношения. Смысл поиска переменной, исключаемой из базиса в следующем. При включении новой переменной в базис, её значение увеличивается. При этом чтобы соблюдать исходные ограничения задачи необходимо уменьшать базисные переменные. Уменьшение переменных возможно только до 0. Симплексное отношение показывает, через сколько увеличений переменой, включаемой в базис, данная базисная переменная приблизится к нулю. Поэтому переменная, имеющая минимальное симплексное отношение, исключается из базиса. Из базиса исключаем X8. Строка с переменной, исключаемой из базиса, называется ведущей строкой. Элемент, находящийся на пересечении ведущей строки и ведущего столбца, называется ведущим элементом. Для данной таблицы ведущий элемент равен 1. Строим новую симплекс-таблицу. При её построении необходимо руководствоваться следующим. Все элементы ведущей строки делятся на ведущий элемент. Ведущий столбец заполняется нулями. Все остальные элементы высчитываются по правилу прямоугольника. Согласно правилу прямоугольника пересчитываемый элемент и ведущий составляют одну из диагоналей прямоугольника. На второй диагонали находим еще два элемента. Отношение разности произведений элементов диагонали к ведущему элементу и дадут искомую величину. Аналогично пересчитаем все элементы таблицы и получим новую (Таблица2): Таблица 2
Как видим, в строке искусственной целевой функции нет отрицательных переменных, сама целевая функция равна нулю, а все искусственные переменные исключены из базиса. Следовательно, найдено начальное допустимое базисное решение. Оно состоит в следующем: Х2=Х3=Х4=Х8=0, Х1=40, Х5=768, Х6=592, Х7=120, E=12560 (в этом легко убедиться, подставив значения исходных переменных задачи в математическую модель). Т.о. строку с искусственной целевой функцией и столбцы с искусственными переменными можно исключить из таблицы. Получаем следующую симплекс-таблицу (Таблица 3): Таблица 3
Полученное решение является допустимым, но не оптимальным, признак неоптимального решения – наличие в строке целевой функции отрицательных значений. Поэтому реализуется второй этап двухэтапного метода: максимизация основной целевой функции E. Определим переменную для включения в базис. Такой переменной станет X4. Определим переменную для исключения из базиса. Составляем симплексные отношения: 40/(-1)= -40, 768/0,8= 960, 592/0,2=2960. Переменная с минимальным симплексным отношением исключается из базиса, т.е. переменная Х5. Т.о. ведущий столбец X4, ведущая строка X5, ведущий элемент 0,8. Строим новую симплекс-таблицу (Таблица 4). Таблица 4
Последняя симплекс-таблица не содержит отрицательных элементов в строке целевой функции. Это указывает на оптимальность найденного решения. Проанализируем получившийся результат: X1=1000, т.е. 1000 т следует выпустить карамели «Мечта». X2=0, т.е. не нужно выпускать карамель «Заря». X3=0, т.е. не нужно выпускать карамель «Полёт». X4=960, т.е. карамели «Мечта» выпустят на 960 тон больше, чем минимально необходимо. X6=400, остаточная переменная закупки потока, т.е. из возможных 600 тонн, закупят только 200 тонн. X7=120,остаточная переменная закупки фруктового пюре. Расчёты базовой задачи на программе Simplex-M приведены в “Приложении А”, а проверка расчетов при помощи Excel приведена в “Приложении Б”. |