1 Математические методы Математические методы Теоретический учебный материал по дисциплине

2 Линейное программирование Фрагмент курса Содержание

3 Содержание Примеры экономических задач Примеры экономических задач Основныеопределения Основные определения Графический метод решения Графический метод решения Симплекс метод Симплекс метод Содержание

4 Основные определения Исследование операций научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами. Линейное программирование - это область математического программирования, посвящённая теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными. Содержание

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

6 Оптимальным решением (планом) называется решение системы ограничений, удовлетворяющее условиям неотрицательности, при котором целевая функция принимает оптимальное (наибольшее или наименьшее) значение. Всякое другое решение называется допустимым (или допустимым планом). Основные определения Содержание

7 Примеры экономических задач Для перевозки строительных материалов на участок строящейся дороги транспортное предприятие имеет возможность использовать два типа грузовиков различной грузоподъемности. Расход ресурсов по дизельному топливу и машинному маслу для грузовика типа А составляет 0,2 т и 2 т, типа В – 0,3 т и 1 т. Расход денежных средств на техническое обслуживание каждого из грузовиков в расчете на один рабочий день составляет соответственно 2$ и 5$. Содержание Грузоподъемность автомобилей соответственно для типа А – 5 т, для типа В – 10 т. Прибыль за 1 тонну перевозимого груза для автомобиля типа А – 4$, типа В – 5$. Известно, что грузовик типа А в течение рабочего дня может выполнить 5 рейсов, а В – 4 рейса. Сколько грузовиков каждого типа следует задействовать, чтобы общая прибыль транспортного предприятия была максимальна?

8 Содержание Примеры экономических задач Составление математической модели задачи 1.Показатель эффективности – общая прибыль транспортного предприятия за 1 день. 2.Переменные x 1 - количество грузовиков типа А x 2 - количество грузовиков типа В 3. Целевая функция – функция прибыли транспортного предприятия за 1 день Z=100 x x 2 max 4. Ограничения 4.1 по использованию дизтоплива0,2 x 1 +0,3 x 2 2,8 4.2 по использованию машинного масла 2 x 1 + x по расходам на т/о 2 x x условия неотрицательности x 1 0, x 2 0 Непонятно? Могу помочь

9 Графический метод решения Содержание Отображаем на декартовой плоскости прямые, соответствующие следующим уравнениям 0,2 x 1 +0,3 x 2 = 2,8 2 x 1 + x 2 = 24 2 x x 2 = 40 x 1 = 0, x 2 = 0 заштриховываем область, в точках которой выполняются все ограничения. Непонятно? Могу помочь

10 Графический метод решения Перебор всех угловых точек области допустимых решений приводит к нахождению максимальной прибыли в точке с координатами (5, 6). Транспортное предприятие может извлечь максимальную прибыль в размере 1700 $, если для перевозки строительных материалов будет использовать Содержание 5 грузовиков типа А и 6 грузовиков типа В. И я хочу себе машину!

11 Симплекс - метод Содержание Для использования симплекс-метода необходимо систему ограничений привести к предпочтительному виду:предпочтительному виду: 0,2 x 1 +0,3 x 2 2,8 2 x 1 + x x x 2 40 x 1 0, x 2 0 0,2 x 1 +0,3 x 2 +x 3 = 2,8 2 x 1 + x 2 +x 4 = 24 2 x x 2 +x 5 = 40 x 1 0, x 2 0 переменные x 3, x 4, x 5 – базисные, а x 1 и x 2 – свободные. А целевую функцию преобразовать следующим образом: Z=100 x x2 max -Z= -100 x x2 min

12 Симплекс - метод Содержание Строим симплексную таблицу 1-x1-x2Свободныепеременные X32328 X42124 x52540 Z Сверху в симплекс – таблице располагаются свободные переменные, взятые с противоположными знаками, слева – базисные переменные. Нижняя строка таблицы называется строкой целевой функции. Критерии оптимальности допустимого базисного решения состоит в том, что в строке целевой функции не должно быть ни одного положительного коэффициента при свободных переменных. Так как 100>0, 200>0, то переходим к новому опорному плану.

13 Симплекс - метод Алгоритм перехода к новой симплекс – таблице 1.Выбираем ведущий столбец (столбец с положительным элементом в строке целевой функции). 2.Выбираем ведущую строку (в которой отношение свободных членов к положительным элементам ведущего столбца минимально, т.е. min{ 28/3, 24/1, 40/5}=40/5=8 ). 1-x1-x2Свободныепеременные X32328 X42124 x52540 Z Ведущий элемент – значение на пересечении ведущего столбца и ведущей строки. Содержание 4.Строится новая симплекс - таблица

14 Симплекс - метод Алгоритм перехода к новой симплекс – таблице 5.Переменные, соответствующие ведущему столбцу и ведущей строке, меняются местами (x2 становится базисной, а x5 - свободной). 6.Элементы ведущей строки заменяются их отношениями к ведущему элементу. 7.Элементы ведущего столбца (кроме ведущего элемента) 2-x1 -x5 Свободныепеременные X3-3/5 X4-1/5 x1x1x1x12/518 Z - 40 заменяются их отношениями к ведущему элементу, взятыми с противоположным знаком. Содержание 8.Все остальные элементы вычисляются по «правилу прямоугольника».

15 Симплекс - метод Элемент 1 (Э1) Старый элемент (СЭ) Ведущий элемент (ВЭ) Элемент 2 (Э2) Правило прямоугольника Содержание Формула НЭ = ВЭ – Э1*Э2/ВЭ, где НЭ – новый элемент2-x1 -x5 СвободныепеременныеX34/5-3/54 X48/5-1/516 x1x1x1x12/518 Z Так как 40>0, то полученный опорный план x=(0;8;4;16;0) не оптимален. Строим следующую симплекс таблицу (выполните расчеты самостоятельно). Непонятно? Могу помочь

16 Симплекс - метод 3 -x3 -x5 Свободныепеременные X1X1X1X15/4-3/45 X4-218 x1x1x1x1-1/21/26 Z Содержание Так как все коэффициенты в строке целевой функции отрицательны, то мы получили оптимальное решение X = (5;6;0;8;0) и Z = 1700$. Значения переменных x3, x4, x5 указывают на статус ресурсов. x3=0 и x5=0 означает, что первый и третий ресурсы (дизельное топливо и расходы на техническое обслуживание) потребляются полностью, т.е. являются дефицитными. Положительное значение x4=8 свидетельствует о неполном использовании второго ресурса (машинного масла). Значит, этот ресурс не дефицитный, причем его излишки составляют именно 8 литров. Анализ решения задачи

17 Сведения об авторе Рыжакова Ольга Евгеньевна Ст. преподаватель кафедры «Вычислительная техника и программирование» Азовского технологического института ДГТУ Выход