Лаба 1. ЛР 1. Исследование и решение задач линейного программирования си. Лабораторная работа 1 Исследование и решение задач линейного программирования симплексным методом Цель работы
 Скачать 442.49 Kb.
|
|
Лабораторная работа № 1 Исследование и решение задач линейного программирования симплексным методом Цель работы Целью лабораторной работы является приобретение студентами практических навыков решения задач линейного программирования симплексным методом в программе Excel и использования среды Scilab для решения задач об оптимальной производственной программе. 1. Формулировка задачи линейного программирования Компания «Краски» производит краску для внутренних и наружных работ из сырья двух типов: М1 и М2 (табл. 1.1.). Таблица 1.1. Расход сырья (в тоннах) на тонну краски Максимально возможный ежесуточный расход сырья Наружные работы Внутренние работы Сырье 1 6 4 24 Сырье 2 1 2 6 Доход (тыс. р.) на тонну краски 5 4 Ежедневное производство краски для внутренних работ ограничено 2 тоннами. Ежедневное производство краски для внутренних работ не должно превышать более чем на тонну аналогичный показатель производства краски для внешних работ. Компания хочет определить оптимальное соотношение между видами выпускаемой продукции для максимизации общего ежедневного дохода. 2. Математическая модель задачи линейного программирования Математически рассматриваемая задача записывается следующим образом: где x 1 – ежедневный объем производства краски для наружных работ; x 2 – ежедневный объем производства краски для внутренних работ; Z – целевая функция. 3. Симплексный метод решения задачи линейного программирования Решение задачи проведем с применением симплексных таблиц. С помощью дополнительных переменных перейдем к системе уравнений. В данном случае дополнительные переменные вводятся со знаком «+», так как все неравенства имеют вид «≤». В случае наличия неравенств, имеющих вид «≥» дополнительные переменные в них вводят со знаком «–». Эта задача в стандартной форме записывается так: максимизировать , при ограничениях , где s i (i=1..4) – дополнительные переменные. Целевую функцию представим в виде уравнения Перейдем к табличной форме представления задачи (табл. 1.2). Таблица 1.2. Первая симплекс-таблица Начальная итерация симплекс-метода начинается из точки (x 1 ,x 2 )=(0,0), что определяет множества базисных и небазисных переменных. Небазисные (нулевые) переменные: (x 1 , x 2 ) Базисные переменные: (s 1 , s 2 , s 3 , s 4 ). Для точки (0,0) получим решение: В таблице базисные переменные перечислены в левом столбце "Базис", а их значения приведены в правом столбце "Решение". Данное начальное решение не является оптимальным, поскольку переменные x 1 и x 2 равны нулю, а возрастание их приводит к увеличению значения целевой функции. Коэффициент при переменной x 1 в формуле целевой функции больше, чем коэффициент при x 2 . Поэтому, в число базисных переменных следует ввести переменную x 1 По симплекс-таблице, вводимая переменная определяется среди множества небазисных как переменная, имеющая наибольший отрицательный коэффициент в Z -строке. Если так случится, что все коэффициенты в Z -строке будут неотрицательными, то дальнейшее увеличение значения целевой функции будет невозможно; это будет означать, что достигнуто оптимальное решение. Чтобы определить исключаемую переменную из симплекс-таблицы, надо вычислить точки пересечения всех функций ограничений с положительным направлением оси x 1 . Координаты этих точек пересечения можно вычислить как отношения правых частей равенств (значение в столбце "Решение") к коэффициентам при переменной x 1 в этих равенствах, как показано в таблице 1.3. Таблица 1.3. Фрагмент первой симплекс-таблицы На рис. 1.1 видно, что неотрицательные отношения порождают точки пересечения на положительной полуоси x 1 . Отношения, соответствующие переменным s 3 и s 4 , исключаются из рассмотрения, поскольку для них точка пересечения лежит или на отрицательной полуоси, или отсутствует. Минимальное неотрицательное отношение соответствует базисной переменной s 1 . Это определяет переменную s 1 как исключаемую и на следующей итерации ее значение будет равно нулю. Значение вводимой переменной равно минимальному неотрицательному отношению x 1 = 4 (точка В на рис. 1.1). При этом значение целевой функции возрастет до 20. Замена исключаемой переменной s 1 на вводимую переменную x 1 приводит к новым множествам базисных и небазисных переменных и новому решению в точке В. Небазисные (нулевые) переменные: (s 1 , x 2 ) Базисные переменные: ( x 1 , s 2 , s 3 , s 4 ) Теперь необходимо выполнить преобразования в первой симплекс- таблице так, чтобы в столбцах "Базис" и "Решения" получить новое решение, соответствующее точке В. Определим ведущий столбец, ассоциируемый с вводимой переменной, и ведущую строку, ассоциируемую с исключаемой переменной. Элемент, находящийся на пересечении ведущего столбца и ведущей строки, назовем ведущим элементом (табл. 1.4). Рисунок 1.1 – Графическая интерпретация отношений как точек пересечения. Таблица 1.4. Модифицированная первая симплекс-таблица. Процесс вычисления нового базисного решения состоит из двух этапов. 1. Вычисление элементов новой ведущей строки. Новая ведущая строка = текущая ведущая строка / ведущий элемент. 2. Вычисление элементов остальных строк, включая Z -строку. Новая строка = текущая строка – ее коэффициент в ведущем столбце × × новая ведущая строка. В рассматриваемом примере выполняем такие вычисления. 1. Новая ведущая s 1 -строка = текущая ведущая s 1 -строка / 6. 2. Новая Z -строка = текущая Z -строка – (–5) × новая ведущая строка. 3. Новая s 2 -строка = текущая s 2 -строка – (1) × новая ведущая строка. 4. Новая s 3 -строка = текущая s 3 -строка – (–1) × новая ведущая строка. 5. Новая s 4 -строка = текущая s 4 -строка. В итоге получим новую симплекс-таблицу, соответствующую новому базисному решению (x 1 , s 2 , s 3 , s 4 )(табл. 1.5). Таблица 1.5. Вторая симплекс-таблица В столбце "Решение" представлено новое базисное решение x 1 =4, s 2 =2, s 3 =5, s 4 =2 и новое значение целевой функции Z = 20. Полученное базисное решение не является оптимальным, поскольку в Z- строке переменная x 2 имеет отрицательный коэффициент. Как и в первой симплекс-таблице, строку Z можно интерпретировать как уравнение: Соответственно увеличение значения переменной x 2 (ее текущее значение равно нулю) приведет к увеличению значения целевой функции. Переменная x 2 выбирается в качестве вводимой в базис. Для определения исключаемой переменной, вычислим отношения правых частей равенств, соответствующих ограничениям, к коэффициентам, стоящим при x 2 в этих равенствах (табл. 1.6). Таблица 1.6. Фрагмент второй симплекс-таблицы Вычисления показывают, что минимальное неотрицательное отношение x 2 =3/2 соответствует переменной s 2 , которая становится исключаемой. Значения целевой функции составит В этой ситуации ведущей строкой будет s 2 -строка, а ведущим столбцом будет столбец, соответствующий переменной x 2 . Ведущий элемент равен 4/3 (табл. 1.5). Вычислим элементы третьей симплекс-таблицы. 1. Новая ведущая s 2 -строка = текущая ведущая s 2 -строка / (4/3). 2. Новая Z -строка = текущая Z -строка – (-2/3) × новая ведущая строка. 3. Новая x 1 -строка = текущая x 1 -строка – (2/3) × новая ведущая строка. 4. Новая s 3 -строка = текущая s 3 -строка – (5/3) × новая ведущая строка. 5. Новая s 4 -строка = текущая s 4 -строка – 1 × новая ведущая строка. В итоге получим новую симплекс-таблицу, соответствующую новому базисному решению (x 1 , x 2 , s 3 , s 4 ) (табл. 1.7). Таблица 1.7. Третья симплекс-таблица Поскольку Z -строка не имеет отрицательных коэффициентов, соответствующих небазисным переменным s 1 , s 2 , полученное решение оптимально (табл. 1.8). Таблица 1.8 – Результаты симплексного метода В данном примере велся поиск максимума целевой функции. В случае минимизации целевой функции Z, исключаемые переменные определяются точно так же, как и при ее максимизации. Вводимая переменная выбирается как небазисная с наибольшим положительным коэффициентом в Z -строке симплекс-таблицы, а минимум целевой функции будет достигнут тогда, когда все коэффициенты в Z -строке будут неположительными. 4. Проверка результатов в Scilab 1. Запускаем Scilab. Создаем новый командный файл (Файл – Создать новый). 2. В открывшемся окне вводим свои значения, согласно своему варианту. 3. Запускаем командный файл и сравниваем результаты работы Scilab и Excel. Если вычисления в Excel проведены верно, то результаты должны совпасть. 5. Порядок выполнения лабораторной работы 1. Получить у преподавателя № задания и выбрать условия задачи в таблице 1.9. 2. Решить симплексным методом задачу линейного программирования в программе Excel. 3. Производим проверку результатов в Scilab. Требования к отчету: Прописывать как в основной части методички все ваши шаги (как будут вычисляться новые элементы строк, кто ведущий элемент). Вычисления проводите в Excel. Отчет, файл Excel назвать «Фамилия_группа_ЛР1» (Лагранж_799_ЛР1.docx, Лагранж_799_ЛР1.xlsx). Проверку результатов в Scilab в отчете оформляете скриншотами вашего командного файла, окна выходных файлов и текстом кода. Таблица 1.9. Варианты |