Задача о распределении ресурсов

Имеются ресурсы R₁, R₂, R₃, ..., R_m в количествах b₁, b₂, b₃, ..., b_m соответственно. С помощью этих ресурсов могут производиться товары Т₁, Т₂, Т₃, ..., T_n. Для производства одной единицы товара T_ij необходимо a_ij единиц ресурса R_i (i=1, 2, ..., m; j=1, 2, ..., n), и каждая единица ресурса R_i стоит D_i рублей. Каждая единица товара может быть реализована по цене C_i (i=1, 2, ..., n). Cпрос составляет K_j единиц товара T_j (j=1, 2, ..., n). Необходимо определить, какое количество какого товара необходимо произвести, чтобы прибыль от реализации была максимальной.

Если x₁, x₂, …, x_n - количества товаров T₁, T₂, ..., T_n и положить x₁=K₁, x₂=K₂, ..., x_n=K_n, а также учесть достаточность ресурсов, получаем систему:

a₁₁x₁+a₁₂x₂+...+a_1nx_n=b₁

a₂₁x₁+a₂₂x₂+...+a_2nx_n=b₂

………............................

a_m1x₁+a_m2x₂+...+a_mnx_n=b_m

Себестоимость единицы товара T_j равна S_j=a_1jD₁+a_2jD₂+...+a_mjD_m.

Прибыль Q_j от реализации единицы товара T_jQ_j=C_j–S_j.

Общая прибыль L=Q₁x₁+Q₂x₂+...+Q_nx_n.

Задача: выбрать такие неотрицательные x₁, x₂, ..., x_n, которые удовлетворяют ограничениям и обращают в максимум функцию L этих переменных. Аналогично формулируются другие практически важные задачи – об оптимальной загрузке оборудования, об оптимальном планировании перевозок и т. д.

Задача планирования перевозок (транспортная задача)

В p пунктах-отправителях имеется по k_j единиц однотипных грузов, предназначенных для поставки в n пунктов – адресатов по g_i штук в каждый, а стоимости перевозок единицы груза в каждый пункт различны для различных комбинаций отправитель–поставщик и равны c_ij, где j – номер пункта-отправителя (j=1, 2, …, p), i – номер пункта-получателя (i=1, 2, …, n). Обозначим количество грузов, перевозимых от отправителя j получателю i через x_ij≥0. Составим n уравнений (по одному для каждого получателя):

=g_i, i=1, …, n.

плюс p ограничений по возможностям отправителей:

≤k_j, j=1, …, p.

и линейный критерий оптимальности решения – минимум общей стоимости перевозок:

L= → min

Эта задача носит название транспортной задачи линейного программирования – она значительно проще общей задачи, так как все коэффициенты основной системы уравнений равны 1.