Методы принятия упр. ...

2.2 Примеры задач линейного программирования

Задача об использовании ресурсов (задача планирования производства).

Для изготовления двух видов продукции Х1 и Х2 используют четыре вида ресурсов S1, S2, S3, S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице.

Необходимо составить такой план производства продукции (т.е. определить, сколько следует производить продукции первого и второго видов), при котором прибыль от ее реализации будет максимальной.

Решение:

х₁, х₂ – число единиц продукции (неизвестные задачи);

Для их изготовления потребуется:

(1* х₁+3* х₂) - единиц ресурса S1;

(2* х₁+1* х₂) – единиц ресурса S2;

(1* х₂) – единиц ресурса S3;

(3* х₁) – единиц ресурса S4.

Потребление ресурсов не должно превышать их запасов. Таким образом, можно записать следующую систему неравенств:

Суммарная прибыль составит:

С=2* х₁+3* х₂  max

Эту задачу легко обобщить на случай выпуска n видов продукции с использованием m видов сырья.

1. Заданы переменные задачи х₁,х₂, …x_j…x_n (j=1..n), где j – порядковый номер переменной.

2. Известны запасы ресурсов производства в количествах b₁, b₂, …b_i,…b_m (i=1..m), где i - порядковый номер ресурса.

3. Заданы технико-экономические коэффициенты затрат каждого вида ресурса на единицу каждой переменной, которые обозначаются a_ij, а – величина коэффициента, i – порядковый номер ресурса, j- порядковый номер переменной. Например, а21 – означает затраты второго вида ресурса на единицу первой переменной.

4. Известны показатели выхода продукции на единицу переменной. Они обозначаются c_j.

Общую задачу линейного программирования (оптимального планирования) можно сформулировать следующим образом:

Найти такие значения искомых переменных х1, х2,…,хn, которые обеспечивают максимум прибыли (критерия оптимальности), выражающегося линейной функцией:

C=С₁x₁+С₂x₂+…+С_nx_nmax

при соблюдении следующих линейных ограничивающих условий:

1. Ограничение по использованию 1-го вида ресурса

a₁₁x₁+a₁₂x₂+…+a_1nx_n    b₁

2. Ограничение по использованию 2-го вида ресурса

a₂₁x₁+a₂₂x₂+…+a_2nx_n    b₂

3. Ограничение по использованию m-го вида ресурса

a_m1x₁+a_m2x₂+…+a_mnx_n    b_m

4. Ограничения по не отрицательности неизвестных величин:

x₁    0, x₂    0, x_n    0

Задача составления рациона (задача о диете, задача о смесях)

Имеются два вида корма I и II, содержащие питательные вещества S1,S2, S3.

Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице.

Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.

Решение:

x₁, x₂ – количество кормов I и II, входящих в дневной рацион;

Рацион будет включать:

(3* x₁+1* x₂) – единиц питательного вещества S1;

(1* x₁+2* x₂) – единиц питательного вещества S2;

(1* x₁+6* x₂) – единиц питательного вещества S3;

Содержание питательных веществ должно быть не менее установленных минимумов, следовательно, получим следующую систему ограничений:

Общая стоимость рациона составит:

С=4 x₁+6 x₂  min

Для формулировки задачи в общем виде обозначим:

x₁, … x_j (j=1,…,n) – число единиц корма n-го вида;

b₁, …, b_i (i=1,…,m) – необходимый минимум содержания в рационе питательного вещества;

a_ij – число единиц i-го питательного вещества в единице корма j-го вида;

с_j – стоимость единицы корма j-го вида.

Тогда экономико-математическая модель задачи примет вид:

Найти такой рацион Х=(x₁,x₂,…,x_j,…,x_n), при котором целевая функция достигает минимального значения, при системе ограничений:

C=С₁x₁+С₂x₂+…+С_nx_nmin