Оптимальное распределение взаимозаменяемых ресурсов

Имеются m видов взаимозаменяемых ресурсов a₁,a₂,…a_m, используемых при выполнении n различных работ (задач). Объемы работ, которые должны быть выполнены, составляют b₁,b₂,…,b_i,…, b_n единиц. Заданы числа λ _ij, указывающие, сколько единиц j- й работы можно получить из единицы i -го ресурса, а также C_ij – затраты на производство j -й работы из единицы i -го ресурса. Требуется распределить ресурсы по работам таким образом, чтобы суммарная эффективность выполненных работ была максимальной (или суммарные затраты – минимальными).

Данная задача называется общей распределительной задачей. Количество единиц i -го ресурса, которое выделено на выполнение работ j- го вида, обозначим x_ij.

Математическая модель рассматриваемой задачи такова:

Минимизировать функцию при ограничениях (2).

(3) Ограничение (2) означает, что план всех работ должен быть выполнен полностью, а (3) – что ресурсы должны быть израсходованы целиком.

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