Построение математических моделей

Рассмотрим некоторые наиболее часто используемые в практических целях задачи линейного программирования.

Задача об оптимальном использовании ресурсов

Предприятие может выпускать n видов продукции, используя для этого m видов ресурсов. Известны затраты каждого вида ресурса на производство единицы каждого вида продукции и прибыль от реализации единицы каждого вида продукции. Требуется составить план выпуска продукции так, чтобы при данных запасах ресурсов получить максимальную прибыль.

Составим математическую модель данной задачи.

Введем обозначения:

b_i, - запасы i-го вида ресурса;

a_ij, ; - затраты i-го вида ресурса на производство единицы j-го вида продукции;

c_j, - прибыль от реализации единицы j-го вида продукции.

Данные задачи можно представить в виде таблицы:

Виды продукции Виды ресурсов	1 2 … j … n	Запасы ресурсов
1	a₁₁a₁₂ … a_1j … a_1n	b₁
2	a₂₁a₂₂ … a_2j … a_2n	b₂
…	…		…
i	a_i₁a_i₂ … a_ij … a_in		b_i
…	…		…
m	a_m₁a_m₂ … a_mj … a_mn		b_m
Прибыль от реализации единицы продукции	c₁ c₂ … c_j … c_n

Обозначим через x_j планируемый выпуск j-го вида продукции; - план выпуска продукции. Тогда прибыль от реализации всей выпускаемой продукции составит

c₁x₁ + c₂x₂ +…+c_jx_j +…+c_nx_n.

Составим ограничения по ресурсам. Найдем расход ресурса первого вида при данном плане выпуска:

a₁₁x₁+a₁₂x₂+…+a₁_jх_j +…+a₁_nx_n.

Ресурса первого вида имеется в наличии b₁ условных единиц, т.е. получаем ограничение

a₁₁x₁+a₁₂x₂+…+a_1jх_j +…+a_1nx_n£ b₁.

Аналогично составляем ограничения по всем остальным видам ресурсов.

Кроме того, x_j³ 0, , так как количество продукции не может быть отрицательным числом.

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

при ограничениях

Задача о диете

В продаже имеются различные виды продуктов. Известны цены продуктов, содержание питательных веществ в единице каждого вида продукта, медицинские требования на содержание питательных веществ в суточной диете. Требуется определить, какие продукты и в каком количестве нужно включить в диету, чтобы она соответствовала всем медицинским требованиям и чтобы стоимость диеты была минимальной.

Составим математическую модель данной задачи.

Введем обозначения:

a_ij -содержание i-го питательного вещества в единице j-го продукта;

b_i- минимальное содержание i-го питательного вещества в суточной диете;

c_j - цена единицы j-го продукта.

Данные задачи можно представить в виде таблицы:

Виды продуктов Виды питательных веществ	1 2 … j … n	Медицинские требования к диете
1	а₁₁a₁₂ … a_1j … a_1n	b₁
2	а₂₁a₂₂ … a_2j … a_2n	b₂
…	…	…
i	a_i₁a_i₂ … a_ij … a_in	b_i
…	…	…
m	a_m₁a_m₂ … a_mj … a_mn	b_m
Цена единицы продукта	с₁ c₂ … c_j … c_n

Пусть x_j единиц j-го продукта включается в суточную диету, тогда - суточная диета.

Цена диеты:

c₁x₁ + c₂x₂ +…+c_jx_j +…+c_nx_n.

Содержание первого питательного вещества в диете составит

a₁₁x₁+a₁₂x₂+…+a₁_jх_j +…+a₁_nx_n.

и это количество должно быть не менее чем b₁ единиц:

a₁₁x₁+a₁₂x₂+…+a_1jх_j +…+a_1nx_n£ b₁.

Аналогично составляем ограничения по всем видам питательных веществ.

Кроме того, x_j³ 0, так как количество продуктов не может быть отрицательным числом.

Математическая модель задачи: найти минимум функции

при ограничениях:

Таким образом, математической моделью данной задачи является задача линейного программирования.

Задача на оптимальный раскрой материала

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

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

Составим математическую модель данной задачи.

Введем обозначения:

i - номер вида заготовки, ;

j - номер варианта раскроя прутка, ;

a_ij - количество заготовок i-го вида, получаемых из одного прутка, разрезаемого по j-му варианту;

b_i- требуемое число заготовок i-го вида;

c_j - длина концевого отрезка, оставшегося от одного прутка при разрезании прутка по j-му варианту.

Данные задачи можно представить в виде таблицы:

Варианты раскроя Виды заготовок	1 2 … j … n	План по заготовкам
1	а₁₁a₁₂ … a_1j … a_1n	b₁
2	а₂₁a₂₂ … a_2j … a_2n	b₂
…	…	…
i	a_i₁a_i₂ … a_ij … a_in	b_i
…	…	…
m	a_m₁a_m₂ … a_mj … a_mn	b_m
Длина концевого отрезка	с₁ c₂ … c_j … c_n

Обозначим через х_j - число прутков, разрезаемых по j-му варианту, тогда - план раскроя прутков. Найдем общую длину концевых отрезков.

По первому варианту планируем разрезать x₁ прутков, концевой отрезок от одного прутка будет иметь длину с₁, тогда общая длина концевых отрезков от х₁ прутков составит c₁x₁. Аналогично общая длина концевых отрезков от х₂ прутков, разрезанных по второму варианту, будет равна c₂x₂ и т.д.

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

Составим ограничения по заготовкам.

Из одного прутка, разрезаемого по первому варианту, получают a₁₁ шт. заготовок первого вида, а из x₁ прутков - a₁₁x₁шт.; по второму варианту из одного прутка получают a₁₂ шт., а из x₂ прутков - a₁₂x₂ шт. и т.д., по n-му варианту - a₁_nx_n шт. Отсюда получаем первое ограничение

a₁₁x₁+a₁₂x₂+…+a₁_jх_j +…+a₁_nx_n= b₁.

Аналогично получаем ограничения по всем заготовкам.

Кроме того, так как число прутков не может быть отрицательным.

Математическая модель задачи: найти наименьшее значение функции

при ограничениях:

Таким образом, математической моделью данной задачи является задача линейного программирования.