Задача Конторовича о выборе производственной программы

Эта задача была одной из первых практических задач линейного программирования, решенных в 1939 году известным отечественным математиком Л. Канторовичем.

Имеется m предприятий, на которых нужно произвести n продуктов в заданном ассортименте l( ). Известна производительность a_ij I-го предприятия в единицу времени, если оно выпускает j-й продукт. Предполагается, что max a_ij >0, т.е. каждый продукт выпускается хотя бы на одном предприятии.

Требуется составить программу работы предприятий (указать время, отведенное на производство каждого вида продукта на данном предприятии) так, чтобы получить максимальный суммарный объем продукции в заданном ассортименте в единицу времени. Иначе говоря, имеется ввиду случай, когда продукция дефицитна (max спрос), производственные мощности ограничены и должны использоваться максимально полно.

Математическая модель данной задачи описывается следующим образом.

Обозначим через x_ij (I= , j= ) рабочее время I-го предприятия, отводимое под j-й продукт. Тогда поиск оптимальной программы загрузки предприятий сводится к решению следующей задачи.

Найти числа x_ij из условий:

x_ij 0 (время не может быть отрицательным)

x_ij 1 (сумма всех долей не превосходит полного времени работы предприятия).

y_j= a_ij x_ij (количество j-го продукта, произведенного на всех предприятиях).

Тогда, если z=min (количествo ассортиментных наборов продуктов), то z достигает max.

Примечание. В такой постановке эта задача не является задачей линейного программирования, т.к. min — нелинейная функция y_j (j= ). Однако эту задачу можно легко свести к задаче линейного программирования.

Дата добавления: 2015-07-26; просмотров: 188; Нарушение авторских прав

Мы поможем в написании ваших работ!