2. Задача о смесях (планирование состава продукции).

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

На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля.

Составьте ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион.

Представим условие задачи в таблице 2.2.

Таблица 2.2 - Исходные данные задачи о смесях

питательные вещества	содержание веществ в единице массы корма, ед.		требуемое количество в смеси, ед.
	корм I	корм II
А	1	4	1
В	1	2	4
С	1	-	1
цена единицы массы корма, р	2	4

Cформулируем задачу линейного программирования.

Обозначим: x₁ - количество корма I в дневном рационе птицы, x₂ - количество корма II в дневном рационе птицы.

Формулировка ЗЛП:

= 3x1 + 2x2 → min;
x1 + 4x2 ≥ 1, x1 + 2x2 ≥ 4, x1 ≥ 1;
x1 ≥ 0,   x2 ≥ 0.

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

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

Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно.

Обычно начальные условия транспортной задачи записывают в так называемую транспортную таблицу (см. таблицу 2.3). В ячейках таблицы в левом верхнем углу записывают показатели затрат (расходы по доставке единицы продукта между соответствующими пунктами), под диагональю каждой ячейки размещается величина поставки x_ij (т.е. x_ij - количество единиц груза, которое будет перевезено от i-го поставщика j-му потребителю).

Таблица 2.3 - Исходные данные транспортной задачи

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

Сформулируем ЗЛП:

= 7x11 + 6x12 + 4x13 + 3x21 + 8x22 + 5x23 + 2x31 + 3x32 + 7x33 → min;
x11 + x12 + x13 = 120, x21 + x22 + x23 = 100, x31 + x32 + x33 = 80, x11 + x21 + x31 = 90, x12 + x22 + x32 = 90, x13 + x23 + x33 = 120;
xij ≥ 0,   ( , ).