Задача о загрузке оборудования

Имеется m станков, на каждом из которых можно выпускать любые из n деталей. Известно максимально возможное время работы каждого станка: b_i , i=1,…, m. Известна длительность изготовления каждой детали на каждом из станков: a_{i j}, i=1,…, m, j=1, …, n, т.е. a_{i j} - длительность обработки j–ой детали, если она изготавливается на i-ом станке. Заданы также затраты на выпуск каждой детали на каждом из станков u_ij , i=1, …,m, j=1, …, n, и цены, по которым продаются детали: c_j , j=1, …,n. Требуется найти, сколько деталей каждого вида следует изготовить на каждом из станков, чтобы получить максимальную прибыль.

Обозначим через x_ij количество деталей j–го вида, которые требуется выпустить на i–ом станке. Тогда a₁₁x₁₁ – время работы 1-го станка над производством 1-ой детали, a₁₂x₁₂ – над производством 2-ой детали и т.д. Общее время работы 1-го станка над запланированной для него программой выпуска деталей составит

a₁₁x₁₁+ a₁₂x₁₂+ . . . + a_1nx_1n.

Поскольку время работы 1-го станка ограничено величиной b₁, возникает ограничение

a₁₁x₁₁+ a₁₂x₁₂+ . . . + a_1nx_1n≤ b₁.

Понятно, что аналогичные ограничения возникают для 2-го, 3-го, . . . , m-го станка:

a_i1x_i1+ a_i2x_i2+ . . . + a_inx_in≤ b_i, i=2,3, . . . ,m.

Рассмотрим целевую функцию задачи. Количество деталей j-го вида составит x_1j+ x_2j+ . . . + x_mj штук; c_j(x_1j+ x_2j+ . . . + x_mj) – выручка от их продажи. Затраты на производство деталей j-го вида составят u_1j x_1j + u_2j x_2j+ . . . + u_mj x_mj. Поэтому прибыль от производства деталей j-го вида, будет определяться формулой

Суммируя по всем видам деталей, получаем целевую функцию задачи:

.

C учетом неотрицательности искомых переменных математическая модель задачи формулируется следующим образом:

.

Если также задано условие, что деталей k-го вида необходимо выпустить не менее S_k единиц, то вводится следующее ограничение:

x_1k + x_2k … + x_mk > = S_k.

Задача о рационе

В рацион для откорма сельскохозяйственных животных должны входить m питательных веществ. Известны величины минимально необходимого потребления каждого из этих веществ: b_i, i=1, …, m. Рацион составляется из n видов продуктов. Содержание питательных веществ в единице каждого из продуктов известно: a_{i j} , i=1, …, m, j =1, …, n, где a_ij – содержание i-го питательного вещества в единице j-го продукта. Известны цены на продукты, которые могут входить в рацион: c_j, j=1,…, n. Требуется составить рацион минимальной стоимости, обеспечивающий выполнение всех требований к содержанию питательных веществ.

Обозначим через x_j количество единиц j-го продукта, которое должно входит в рацион минимальной стоимости. Тогда математическая модель задачи формулируется следующим образом:

Задача о раскрое

Для изготовления изделий m типов выполняется раскрой одинаковых заготовок материала. Имеется n способов раскроя. Для каждого способа раскроя известно количество изделий каждого типа, получаемых из одной заготовки: a_ij, i=1,…,m, j=1,…, n; здесь a_ij – количество изделий i-го типа, получаемых из одной заготовки при ее раскрое j-м способом. Известны величины отходов для каждого способа раскроя: c_j, j=1, … , n. Задано количество изделий каждого типа, которые требуется получить при раскрое: b_i, i=1,…,m. Требуется составить оптимальный план раскроя материала, т.е. найти сколько заготовок требуется раскроить каждым из способов, чтобы получить заданное количество изделий при минимальных отходах.

Обозначим количество заготовок, раскраиваемых по j–му способу, как x_j. Тогда математическая модель задачи формулируется следующим образом:

Задача о смеси

Требуется составить смесь, в которою должны входить m компонентов. Заданы нижние (d_i) и верхние (D_i) ограничения на содержание компонентов в смеси, i=1,…,m. Для составления смеси могут использоваться n веществ. Известно содержание каждого компонента в каждом из веществ: a_ij, i=1,..,m, j=1,...,n; здесь a_ij- содержание i-го компонента в j-м веществе (в долях или процентах ). Заданы также цены единицы каждого из веществ: c_j, j=1,…,n. Требуется определить состав смеси, стоимость которого была бы минимальной.

Обозначим через x_j содержание j-го вещества в единице смеси. Тогда математическая модель задачи формулируется следующим образом:

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

Имеется m поставщиков однотипной продукции. Каждый из поставщиков обладает запасами в a_i единиц этой продукции, i=1,…,m. Эту продукцию потребляют n потребителей. При этом каждый потребитель может использовать b_j единиц продукции, j=1,…,n. Доставка единицы продукции от i-го поставщика к j-му потребителю обходится c_ij денежных единиц.

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

Введем в рассмотрение переменные x_ij — план поставки продукции от i-го поставщика к j-му потребителю. Тогда c_ijx_ij - транспортные затраты, связанные с этой поставкой. Общая сумма транспортных затрат будет представлять целевую функцию транспортной задачи:

.

Рассмотрим вопрос об ограничениях. Во-первых, каждый поставщик обладает ограниченными запасами продукции. Поэтому общая сумма выполняемых им поставок не может превышать имеющихся у него запасов:

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

С учетом естественных ограничений (x_ij≥0) математическая модель задачи принимает вид: