4.Примеры задач линейного программирования: задача о диете

Имеется n видов продуктов питания и m химических элементов, необходимых для суточного потребления. a_ij – содержание i-го (i=1,2,…,m) химического элемента в одной единице j-го (j=1,2,…,n) продукта питания. b_i – минимальное суточное потребление i-го химического элемента. c_j – стоимость одной единицы j-го продукта питания. Требуется составить суточный рацион питания – сколько продуктов каждого вида нужно приобрести, чтобы рацион имел минимальную стоимость, и питание было разнообразным. В задаче о диете стоимость можно заменить на калорийность продуктов питания, и сформулировать задачу в следующем виде: питание должно быть низкокалорийным, но содержать все необходимые для суточного потребления химические элементы. ^ Строим экономико-математическую модель. Управляемая переменная x_j – количество продукта j-го вида, которое будем приобретать (j=1,2,…,n). Функция цели – суммарная стоимость продуктов питания (1) Ограничения (2) x_j 0, j=1,2,…,n (3) Решить задачу – значит найти вектор , такой, что при условиях (2) и (3). Эта задача также является задачей линейного программирования. Можно формально свести эту задачу к предыдущей, если вместо минимизации функции рассматривать максимизацию функции , а ограничение вида свести к ограничению вида Имеется n видов продуктов питания и m химических элементов, необходимых для суточного потребления. a_ij – содержание i-го (i=1,2,…,m) химического элемента в одной единице j-го (j=1,2,…,n) продукта питания. b_i – минимальное суточное потребление i-го химического элемента. c_j – стоимость одной единицы j-го продукта питания. Требуется составить суточный рацион питания – сколько продуктов каждого вида нужно приобрести, чтобы рацион имел минимальную стоимость, и питание было разнообразным. В задаче о диете стоимость можно заменить на калорийность продуктов питания, и сформулировать задачу в следующем виде: питание должно быть низкокалорийным, но содержать все необходимые для суточного потребления химические элементы. ^ Строим экономико-математическую модель. Управляемая переменная x_j – количество продукта j-го вида, которое будем приобретать (j=1,2,…,n). Функция цели – суммарная стоимость продуктов питания (1) Ограничения (2) x_j 0, j=1,2,…,n (3) Решить задачу – значит найти вектор , такой, что при условиях (2) и (3). Эта задача также является задачей линейного программирования. Можно формально свести эту задачу к предыдущей, если вместо минимизации функции рассматривать максимизацию функции , а ограничение вида свести к ограничению вида .

5. Примеры задач линейного программирования: транспортная задача.

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

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

Поставщики	Потребители				Мощность поставщиков
	В1	В2	В3	В4
А1	c11 х11	c12 х12	c13 х13	c14 х14	M1
А2	c21 х21	c22 х22	c23 х23	c24 х24	M2
А3	c31 х31	c32 х32	c33х33	c34 х34	M3
Спрос потребителей	N1	N2	N3	N4

В левом верхнем углу каждой клетки стоит коэф-т затрат c_ij (тарифы) на перевозку единицы груза от i-го поставщика к j-му потребителю. Мощности поставщиков А₁,А₂,А₃ соответственно равны M₁, M₂, M₃. Спрос потребителей В₁,В₂,В₃,В₄ соответственно равны N₁, N₂, N₃, N₄.

Составим эк-математ. модель транспортной задачи. Учтем следующие условия:

1. мощности всех поставщиков должны быть полностью реализованы

2. спросы всех потребителей д.б. удовлетворены

3. суммарные затраты на перевозку д.б минимальны.

Определить суммарные и минимальные затраты на перевозку всех грузов.

Введем переменные: пусть х_ij – кол-во перевезенного груза от i-го поставщика к j-му потребителю (i=1,2…m; j=1,2…n), где m – число поставщиков, n – число потребителей.

Тогда эк-мат модель задачи примет вид:

(1)

Суммарные затраты F на перевозку выражаются через коэф-ты затрат и поставки следующим образом: F(x)= min (2)

Математическая интерпретация модели транспортной задачи: на множество неотрицательных (допустимых) решений системы ограничений (1) найти такое решение Х=(х₁₁,х₁₂…х_ij), при котором линейная функция (2) принимает минимальное значение.