Математическое программирование

1. Основные понятия Математическое программирование – раздел математики, посвященный теории и методам решения задач о нахождении экстремумов (максимумов и минимумов) функций на множествах, определяемых некоторыми ограничениями (равенствами или неравенствами). Под программированием понимается планирование, т.е. получение оптимального плана-решения задачи. Математическое программирование называется также оптимальным программированием. Общий вид задачи математического программирования: f(x1, x2,…, xn)max (1) при условиях: g1(x1, x2,…, xn)0 g2(x1, x2,…, xn)0 ……………….. (2) gm(x1, x2,…, xn)0 x10, x20,…, xn0 (3) где x1, x2,…, xn – управляющие переменные; f(x1, x2,…, xn) – целевая функция; g1(x1, x2,…, xn)0, g2(x1, x2,…, xn)0,…, gm(x1, x2,…, xn)0 – специальные ограничения; x10, x20,…, xn0 – общие ограничения (условия неотрицательности управляющих переменных). Точка (x1, x2,…, xn), удовлетворяющая специальным и общим ограничениям, называется допустимым решением задачи математического программирования. Множество всех допустимых решений задачи математического программирования называется допустимым множеством этой задачи. Точка (x1, x2,…, xn) называется оптимальным решением задачи математического программирования, если 1) она есть допустимое решение этой задачи; 2) на этой точке целевая функция достигает глобального максимума (в случае задачи максимизации) среди всех точек, удовлетворяющих ограничениям; т.е. f(x1, x2,…, xn)f(x1, x2,…, xn) или на этой точке целевая функция достигает глобального минимума (в случае задачи минимизации) среди всех точек, удовлетворяющих ограничениям; т.е. f(x1, x2,…, xn)f(x1, x2,…, xn) (1), (2), (3) – задача максимизации. f(x1, x2,…, xn)min (1) при условиях: g1(x1, x2,…, xn) 0 g2(x1, x2,…, xn) 0 ……………….. (2) gm(x1, x2,…, xn) 0 x10, x20,…, xn0 (3) (1), (2), (3) – задача минимизации. По виду целевой функции и ограничений задачи математического программирования делятся на линейные, нелинейные и динамические. В линейных задачах целевая функция и ограничения линейны по управляющим переменным x1, x2,…, xn. Построение и расчет линейных задач является наиболее развитым разделом математического моделирования, поэтому часто к ним стараются свести и другие задачи либо на этапе постановки, либо в процессе решения. Для линейных задач любого вида и достаточно большой размерности известны стандартные методы решения. 2. Постановка задачи линейного программирования f=cjxj=с1х1+с2х2+…+сnxn max (min) при ограничениях: где xj, j=1, 2,…, n – управляющие переменные; f – целевая функция; aij, bj, сj (i=1, 2,…, m, j=1, 2,…, n) – параметры. Задача содержит n переменных и m ограничений. Замечание: В качестве специальных ограничений (*) могут быть равенства или неравенства любого знака. Решить задачу линейного программирования – это значит найти значения управляющих переменных, удовлетворяющие ограничениям (*), при которых целевая функция принимает минимальное или максимальное значение. Пример. Предприятие производит изделия трех видов, поставляет их заказчикам и реализует на рынке. Заказчикам требуется 1000 изделий I вида, 2000 изделий II вида и 2500 изделий III вида. Условия спроса на рынке ограничивают число изделий I вида 2000 единицами, II – 3000 и III – 5000 единицами. Для изготовления изделий используются 4 типа ресурсов. Количество ресурсов, потребляемых для производства одного изделия, общее количество ресурсов и прибыль от реализации каждого вида изделия заданы в таблице: тип ресурсов вид изделий всего ресурсов 1 2 3 1 500 300 1000 25000000 2 1000 200 100 30000000 3 150 300 200 20000000 4 100 200 400 40000000 прибыль 20 40 50 Как организовать производство, чтобы: 1) обеспечить заказчиков; 2) не допустить затоваривания; 3) получить максимальную прибыль? Решение (ограничимся составлением математической модели задачи): Пусть х1 – число изделий I вида; х2 – число изделий II вида; х3 – III вида.  х11000   х22000  неравенства соответствуют спросу заказчиков  х32500   х12000   х23000  неравенства соответствуют спросу на рынке  х35000   500х1+300х2+1000х325000000   1000х1+200х2+100х330000000  неравенства соответствуют ограничениям  150х1+300х2+200х320000000  по ресурсам  100х1+200х2+400х340000000  Р=20х1+40х2+50х3max Каждое слагаемое целевой функции определяет прибыль от реализации изделий каждого вида соответственно в количествах х1, х2, х3. Таким образом, математическая модель представляет собой задачу линейного программирования. Примеры некоторых типичных экономических и производственных задач, оптимальное решение которых может быть найдено с помощью построения и расчета соответствующих линейных математических моделей: планирование производства, формирование минимальной потребительской продовольственной корзины, расчет оптимальной загрузки оборудования, раскрой материала, составление плана реализации товара. 3. Графический метод решения задачи линейного программирования Графический метод применим для решения задач следующего вида: f=c1x1+c2x2max (min)  ai1x1+ai2x2bi i=1,2,…,m1 (**)  ai1x1+ai2x2bi i=m1+1,m1+2,…,m т.е. если число переменных в задаче равно двум, а ограничениями является система неравенств. Алгоритм решения задачи линейного программирования графическим методом: 1 Записывают уравнения прямых, соответствующие ограничениям (**), и строят их на координатной плоскости. 2 Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на координатной плоскости и подставляют ее координаты в первую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; в противном случае искомая полуплоскость лежит с противоположной стороны от прямой. Эти действия последовательно выполняются для всех неравенств системы (**). 3 Определяют область допустимых решений задачи как область пересечения m полуплоскостей, соответствующих m ограничениям задачи. Возможны следующие варианты области допустимых решений: многоугольник открытое пустое одна точка множество множество 4 Определяют координаты граничных точек области допустимых решений, решая совместно уравнения, задающие прямые, на пересечении которых находится эта точка. 5 Вычисляют значения целевой функции в граничных точках области допустимых решений. 6 Из этих значений выбирают максимальное (в случае задачи максимизации) или минимальное (в случае задачи минимизации). Пример. При продаже двух видов товара используется 4 типа ресурсов. Норма затрат ресурсов на реализацию единицы товара, общий объем каждого ресурса заданы в таблице: ресурсы нормы затрат ресурсов на товары общее кол-во ресурсов I вида II вида 1 2 2 12 2 1 2 8 3 4 16 4 4 12 Прибыль от реализации одной единицы товара I вида составляет 2 у.е., II вида – 3 у.е. Требуется найти оптимальный план реализации товаров, обеспечивающий торговому предприятию максимальную прибыль. Решение: Пусть х1 – количество проданных изделий I вида; х2 – количество проданных изделий II вида Целевой функцией задачи является функция прибыли, которая составляется из условия задачи. Если прибыль от реализации одной единицы товара I вида составляет 2 у.е., то прибыль от реализации всех изделий I вида в количестве х1 составит 2х1 у.е. Аналогично, если прибыль от реализации одной единицы товара II вида составляет 3 у.е., то прибыль от реализации всех изделий II вида в количестве х2 составит 3х2 у.е. Тогда суммарная прибыль Р=2x1+3x2 . Функция прибыли исследуется на максимум. Условиями задачи являются ограничения по каждому типу ресурсов. Если на одно изделие I вида расходуется 2 единицы ресурса №1, то на все изделия I вида расходуется 2х1 единиц этого ресурса. Если на одно изделие II вида расходуется также 2 единицы ресурса №1, то на все изделия II вида расходуется 2х2 единиц этого ресурса. Суммарный расход ресурса №1 составляет 2х1+2х2 единиц. Суммарный расход не должен превысить общий запас ресурса №1, т.е. 2х1+2х212. Аналогичны ограничения по другим типам ресурсов. Кроме того, по смыслу задачи х10, х20. Итак, математическая модель задачи: Р=2x1+3x2max  2x1+2x212  x1+2x28  4x116  4x212  x10  x20 Замечание: Общие ограничения x10 и x20 означают, что решение находится в первой координатной четверти. Перепишем каждое неравенство системы ограничений в такой форме, чтобы в левой части неравенства осталась переменная х2 с коэффициентом 1, а остальные слагаемые перешли в правую часть неравенства.  2x1+2x212  2x2-2х1+12  x2-х1+6  x1+2x28  2x2-х1+8  x2-1/2х1+4  4x116  x14  4x212  x23 Затем решение каждого неравенства укажем в одной и той же прямоугольной системе координат (см. чертеж). Для этого построим прямые, заданные уравнениями: x2=-х1+6, х2=-1/2х1+4, x1=4, x2=3 Чтобы построить прямую x2=-х1+6, необходимо указать две точки, через которые проходит эта прямая. Задавая произвольные значения для переменной х1, находим соответствующее значение х2 по формуле x2=-х1+6. Например, если х1=0, то х2=6, а если х1=6, то х2=0. Нанесем в прямоугольной системе координат точки с координатами (0, 6) и (6, 0) и проведем через эти точки искомую прямую. Вдоль прямой укажем ее уравнение. Чтобы построить прямую x2=-1/2х1+4, задавая произвольные значения для переменной х1, находим соответствующее значение х2 по формуле x2=-1/2х1+4. Например, если х1=0, то х2=4, а если х1=2, то х2=3. Нанесем в прямоугольной системе координат точки с координатами (0, 4) и (2, 3) и проведем через эти точки искомую прямую. Уравнение х1=4 задает вертикальную прямую, проходящую через отметку 4. Уравнение х2=3 задает горизонтальную прямую, проходящую через отметку 3. Решением соответствующего неравенства является одна из двух полуплоскостей, на которые прямая разбивает плоскость. Если знак неравенства , то выбирается полуплоскость, расположенная левее и ниже проведенной прямой. Если знак неравенства , то выбирается полуплоскость, расположенная правее и выше проведенной прямой. Выбранная полуплоскость отмечается на чертеже штриховкой. Пересечение всех одновременно штриховок определяет область допустимых решений задачи. Пятиугольник OABCD – область допустимых решений задачи. Чтобы установить точные координаты граничных точек (вершин пятиугольника), необходимо составить и решить системы двух уравнений тех прямых, на пересечении которых находится каждая граничная точка. Например, система уравнений:  4х2=12  х1+2х2=8 задает координаты вершины В. Система уравнений:  4х1=16  х1+2х2=8 задает координаты вершины С. Таким образом, O(0, 0); A(0, 3); B(2, 3); C(4, 2); D(4, 0) На последнем этапе решения задачи следует подставить в выражение целевой функции вместо х1 и х2 соответственно координаты каждой граничной точки области допустимых решений и выбрать из полученных пяти значений наибольшее: P(0, 0)=20+30=0 P(0, 3)=20+33=9; P(2, 3)=22+33=13; P(4, 2)=24+32=14; Р(4, 0)=24+30=8; max=14. Ответ: Для получения прибыли в размере 14 у.е. надо продать 4 изделия I вида и 2 изделия II вида.