Общая постановка задачи линейного программирования. Основные понятия и определения.
Введение в линейное программирование
В общем виде математическая постановка оптимальной задачи состоит в определении наибольшего или наименьшего значения целевой функции. Цель обязательно выражается количественным показателем (стоимость валовой продукции, сумма затрат и т.д.) Этот показатель называется критерием оптимальности.
С (x1, x2,…, xj…, xn) → max (min)
при условиях
gi (x1, x2…, xj…, xn) ≤ bi (i = 1… m), где
С, gi – заданные функции;
xj(j = 1… n) – искомые переменные;
bi (i = 1… m) – некоторые действительные числа.
В зависимости от функций C и gi экономико-математические модели подразделяются на: линейные и нелинейные.
На практике широкое применение получили задачи, в которых условия и критерий оптимальности представлены в виде системы линейных уравнений и неравенств.
Линейными называются уравнения и неравенства, в которых неизвестные входят только в первой степени. Такого рода задачи изучаются в разделе математического программирования, который так и называется - линейное программирование.
Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.
Линейное программирование – наиболее обширный, хорошо разработанный и практически важный раздел.
Использование этих методов имеет ряд существенных преимуществ перед традиционными методами.
1. возможность рассмотрения всех вариантов решения и выбора среди них оптимального;
2. реализация методов линейного программирования входит сейчас во все основные математические пакеты прикладных программ, что позволяет средне подготовленному пользователю реализовывать решение таких задач на компьютере;
3. высокая степень автоматизации таких задач позволяет одновременно учитывать в задачах большое количество факторов.
Знакомство с задачами линейного программирования начнем с рассмотрения примеров таких задач.
Примеры задач линейного программирования
Задача об использовании ресурсов (задача планирования производства).
Для изготовления двух видов продукции Х1 и Х2 используют четыре вида ресурсов S1, S2, S3, S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в табл.
Виды ресурса
Запас ресурса
Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
Х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. Заданы переменные задачи х1,х2, …xj…xn (j=1..n), где j – порядковый номер переменной.
2. Известны запасы ресурсов производства в количествах b1, b2, …bi,…bm (i=1..m), где i - порядковый номер ресурса.
3. Заданы технико-экономические коэффициенты затрат каждого вида ресурса на единицу каждой переменной, которые обозначаются aij, а – величина коэффициента, i – порядковый номер ресурса, j- порядковый номер переменной. Например, а21 – означает затраты второго вида ресурса на единицу первой переменной.
4. Известны показатели выхода продукции на единицу переменной. Они обозначаются cj.
Общую задачу линейного программирования (оптимального планирования) можно сформулировать следующим образом:
Найти такие значения искомых переменных х1, х2,…,хn, которые обеспечивают максимум прибыли (критерия оптимальности), выражающегося линейной функцией:
C=С1x1+С2x2+…+Сnxn®max
при соблюдении следующих линейных ограничивающих условий:
1. Ограничение по использованию 1-го вида ресурса
a11x1+a12x2+…+a1nxn£b1
2. Ограничение по использованию 2-го вида ресурса
a21x1+a22x2+…+a2nxn£b2
3. Ограничение по использованию m-го вида ресурса
am1x1+am2x2+…+amnxn£bm
4. Ограничения по не отрицательности неизвестных величин:
x1³0, x2³0, xn³0
Задача составления рациона (задача о диете, задача о смесях)
Имеются два вида корма I и II, содержащие питательные вещества S1,S2, S3. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице.
Питательное вещество
Необходимый минимум пит. вещества
Число единиц питательных веществ в 1 кг. корма
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), при котором целевая функция достигает минимального значения, при системе ограничений: