2.2 Примеры задач линейного программирования
2.2 Примеры задач линейного программирования
Задача об использовании ресурсов (задача планирования производства).
Для изготовления двух видов продукции Х1 и Х2 используют четыре вида ресурсов S1, S2, S3, S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице.
Необходимо составить такой план производства продукции (т.е. определить, сколько следует производить продукции первого и второго видов), при котором прибыль от ее реализации будет максимальной.
Решение:
х1, х2 – число единиц продукции (неизвестные задачи);
Для их изготовления потребуется:
(1* х1+3* х2) - единиц ресурса S1;
(2* х1+1* х2) – единиц ресурса S2;
(1* х2) – единиц ресурса S3;
(3* х1) – единиц ресурса S4.
Потребление ресурсов не должно превышать их запасов. Таким образом, можно записать следующую систему неравенств:
Суммарная прибыль составит:
С=2* х1+3* х2 max
Эту задачу легко обобщить на случай выпуска n видов продукции с использованием m видов сырья.
-
Заданы переменные задачи х1,х2, …xj…xn (j=1..n), где j – порядковый номер переменной.
-
Известны запасы ресурсов производства в количествах b1, b2, …bi,…bm (i=1..m), где i - порядковый номер ресурса.
-
Заданы технико-экономические коэффициенты затрат каждого вида ресурса на единицу каждой переменной, которые обозначаются aij, а – величина коэффициента, i – порядковый номер ресурса, j- порядковый номер переменной. Например, а21 – означает затраты второго вида ресурса на единицу первой переменной.
-
Известны показатели выхода продукции на единицу переменной. Они обозначаются cj.
Общую задачу линейного программирования (оптимального планирования) можно сформулировать следующим образом:
Найти такие значения искомых переменных х1, х2,…,хn, которые обеспечивают максимум прибыли (критерия оптимальности), выражающегося линейной функцией:
C=С1x1+С2x2+…+Сnxnmax
при соблюдении следующих линейных ограничивающих условий:
-
Ограничение по использованию 1-го вида ресурса
a11x1+a12x2+…+a1nxn b1
-
Ограничение по использованию 2-го вида ресурса
a21x1+a22x2+…+a2nxn b2
-
Ограничение по использованию m-го вида ресурса
am1x1+am2x2+…+amnxn bm
-
Ограничения по не отрицательности неизвестных величин:
x1 0, x2 0, xn 0
Задача составления рациона (задача о диете, задача о смесях)
Имеются два вида корма I и II, содержащие питательные вещества S1,S2, S3.
Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице.
Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.
Решение:
x1, x2 – количество кормов I и II, входящих в дневной рацион;
Рацион будет включать:
(3* x1+1* x2) – единиц питательного вещества S1;
(1* x1+2* x2) – единиц питательного вещества S2;
(1* x1+6* x2) – единиц питательного вещества S3;
Содержание питательных веществ должно быть не менее установленных минимумов, следовательно, получим следующую систему ограничений:
Общая стоимость рациона составит:
С=4 x1+6 x2 min
Для формулировки задачи в общем виде обозначим:
x1, … xj (j=1,…,n) – число единиц корма n-го вида;
b1, …, bi (i=1,…,m) – необходимый минимум содержания в рационе питательного вещества;
aij – число единиц i-го питательного вещества в единице корма j-го вида;
сj – стоимость единицы корма j-го вида.
Тогда экономико-математическая модель задачи примет вид:
Найти такой рацион Х=(x1,x2,…,xj,…,xn), при котором целевая функция достигает минимального значения, при системе ограничений:
C=С1x1+С2x2+…+Сnxnmin