2.4. Задача о смесях( о диете)

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

1. Известен перечень биологически необходимых питательных веществ и их минимальная норма (например, суточная);

2. Задан набор продуктов, из которых требуется составить пищевой рацион;

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

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

Формализуем описанную ситуацию:

Будем считать, что в рацион должно входить m биологически необходимых питательных веществ (индекс i). Таким образом, i=1,2,..,m.

Известно, что i-го питательного вещества в рационе должно быть не меньше, чем b_i единиц. Предположим, что мы располагаем n различными продуктами, из которых составляется пищевой рацион (индекс j, j=1,2,…,n). Норму содержания i-го питательного вещества в j-ом продукте обозначим через a_ij . Нам известна таблица-матрица, состоящая из m×n чисел a_ij .

Таблица 2.1

Пищевые продукты
1	2	…	…	…	n
Питательные вещества	1			…
	2			…
	…	…	…	…	…
	…	…	…	…	…
	m			…

Цены, которые установлены на продукты питания, обозначим c_j за единицу j-го продукта. Количество j-го продукта, входящего в пищевой рацион, обозначим через x_j .

В этих обозначениях выбор самого дешевого рациона, удовлетворяющего сформулированным выше требованиям, сводится к решению следующей математической задачи:

Найти вектор X = ( x₁ , x_2, …, x_n ), удовлетворяющий системе ограничений:

      ( (2.24)                       (2.25)

и доставляющий целевой функции   минимальное значение.

Ограничение для каждого i означает, что в выбираемом рационе i-го питательного вещества должно содержать не менее, чем b_i единиц. Второе ограничение формализует тот факт, что j-ый продукт может либо входить в рацион, и тогда x_i >0, либо не входить, и тогда x_i =0.

2.5. Задача оптимального раскроя материалов

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

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

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

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

i – вид заготовки;

m – число всех видов заготовок;

j – вариант раскроя рулона по ширине, n – число всех вариантов раскроя;

необходимое число заготовок i-го вида;

число заготовок i-го вида, которое можно получить из одного рулона материала согласно j-му варианту раскроя;

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

А - общее количество рулонов, имеющихся в наличии;

искомое число рулонов, раскраиваемых согласно j-му варианту.

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

(2.26)

(2.27)

(2.28)

(2.29)

это задача линейного программирования, для решения которой можно применить симплекс-метод.

Рассмотрим более сложную модель оптимального раскроя партий материалов для изготовления комплектов.

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

Для формирования модели введем обозначения:

s – номер партии материала, S – число всех партий материалов;

i – вид заготовки;

число заготовок i-го вида, необходимых для одного комплекта;

n – число всех комплектов;

количество материалов одного размера в одной партии s-го вида;

j – номер варианта раскроя;

число вариантов раскроя для каждой единицы s-й партии;

число заготовок i-го вида, которое можно получить из единицы материала s-й партии согласно j-му варианту раскроя;

искомое количество единиц материала s-й партии, раскраиваемых согласно j-му варианту.

При раскрое всех партий будет получено заготовок i-го вида. Их достаточно для комплектов.

Поскольку число комплектов минимизируется теми заголовками, которые позволяют составить наименьшее число комплектов, то число полных комплектов равно:

Задача состоит в максимизации числа комплектов

При условии выполнения плана раскроя заготовок

А также неотрицательности компонент

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

, (2.30)

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

(2.31)

(2.32)

(2.33)