Математическое программирование
Выбери формат для чтения
Загружаем конспект в формате doc
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
1. Основные понятия
Математическое программирование – раздел математики, посвященный теории и методам решения задач о нахождении экстремумов (максимумов и минимумов) функций на множествах, определяемых некоторыми ограничениями (равенствами или неравенствами).
Под программированием понимается планирование, т.е. получение оптимального плана-решения задачи.
Математическое программирование называется также оптимальным программированием.
Общий вид задачи математического программирования:
f(x1, x2,…, xn)max (1)
при условиях: g1(x1, x2,…, xn)0
g2(x1, x2,…, xn)0
……………….. (2) gm(x1, x2,…, xn)0
x10, x20,…, xn0 (3)
где x1, x2,…, xn – управляющие переменные;
f(x1, x2,…, xn) – целевая функция;
g1(x1, x2,…, xn)0, g2(x1, x2,…, xn)0,…, gm(x1, x2,…, xn)0 – специальные ограничения;
x10, x20,…, xn0 – общие ограничения (условия неотрицательности управляющих переменных).
Точка (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
x10, x20,…, xn0 (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 вида.
х11000
х22000 неравенства соответствуют спросу заказчиков
х32500
х12000
х23000 неравенства соответствуют спросу на рынке
х35000
500х1+300х2+1000х325000000
1000х1+200х2+100х330000000 неравенства соответствуют ограничениям
150х1+300х2+200х320000000 по ресурсам
100х1+200х2+400х340000000
Р=20х1+40х2+50х3max
Каждое слагаемое целевой функции определяет прибыль от реализации изделий каждого вида соответственно в количествах х1, х2, х3.
Таким образом, математическая модель представляет собой задачу линейного программирования.
Примеры некоторых типичных экономических и производственных задач, оптимальное решение которых может быть найдено с помощью построения и расчета соответствующих линейных математических моделей: планирование производства, формирование минимальной потребительской продовольственной корзины, расчет оптимальной загрузки оборудования, раскрой материала, составление плана реализации товара.
3. Графический метод решения задачи линейного программирования
Графический метод применим для решения задач следующего вида:
f=c1x1+c2x2max (min)
ai1x1+ai2x2bi i=1,2,…,m1 (**)
ai1x1+ai2x2bi 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х212. Аналогичны ограничения по другим типам ресурсов.
Кроме того, по смыслу задачи х10, х20.
Итак, математическая модель задачи:
Р=2x1+3x2max
2x1+2x212
x1+2x28
4x116
4x212
x10
x20
Замечание: Общие ограничения x10 и x20 означают, что решение находится в первой координатной четверти.
Перепишем каждое неравенство системы ограничений в такой форме, чтобы в левой части неравенства осталась переменная х2 с коэффициентом 1, а остальные слагаемые перешли в правую часть неравенства.
2x1+2x212 2x2-2х1+12 x2-х1+6
x1+2x28 2x2-х1+8 x2-1/2х1+4
4x116 x14
4x212 x23
Затем решение каждого неравенства укажем в одной и той же прямоугольной системе координат (см. чертеж). Для этого построим прямые, заданные уравнениями:
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)=20+30=0
P(0, 3)=20+33=9;
P(2, 3)=22+33=13;
P(4, 2)=24+32=14;
Р(4, 0)=24+30=8;
max=14.
Ответ: Для получения прибыли в размере 14 у.е. надо продать 4 изделия I вида и 2 изделия II вида.