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

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

Имеется 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= ). Однако эту задачу можно легко свести к задаче линейного программирования.

4. Транспортная задача

В простейшем варианте эта задача возникает, когда речь идет о рациональной перевозке некоторого однородного продукта от производителей к потребителям. Предполагается, что потребителям безразлично, откуда (из каких пунктов производства будет поступать продукт), лишь бы он поступал в запрашиваемом объеме. Однако от того, насколько рациональным будет прикрепление пунктов потребления к пунктам производства, существенно зависит объем работы транспорта. В этой связи возникает задача о наиболее рациональном прикреплении, правильном направлении перевозок груза, при котором потребности удовлетворяются, а затраты на транспортировку минимальны/35/.

Математическая модель задачи описывается так.

Пусть имеется m пунктов производства в единицу времени (месяц, квартал), равными a_i=( ) и n пунктов потребления с объемами потребления b_i I( ). Естественно полагать, что a_i b_j, т.е. потребление не превышает возможностей производства. Известны также величины c_ij—затраты по перевозке единицы продукта из I-го пункта производства в j-й пункт потребления.

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

Обозначая через x_ij количество продукта, перевозимое из I –го пункта производства в j-й пункт потребления, приходим к следующей математической модели:

Найти значения величин x_ij, чтобы достигался min c_ij x_ij суммарных затрат на транспортировку при условиях:

1. _ij b_j, j=

—в каждый пункт потребления завозится требуемое количество продукта.

2. x_ij a_i, I=

— из каждого пункта производства вывозится не более произведенного количества продукта.

3. x_ij= ,

— перевозимый объем продукта, не может быть отрицательным.

Эта задача может быть поставлена и в параметрической постановке, например, зависеть от времени.