Примеры задач ЛП

1. Задача о рационе кормления. Рассмотрим задачу о рациональном кормлении, которая возникает на любой животноводческой ферме. Для нормального роста рацион кормления животных должен содержать большое количество различных веществ: белки, жиры, углеводы, кальций, аминокислоты, микроэлементы, витамины и т.д. Присвоим каждому из этих веществ номер i = 1, 2, …, m. Количество i -го вещества, поступающего в организм животного со скармливаемыми ему пищевыми продуктами, обозначим N_i. Для кормления животных используется n видов пищевых продуктов, например, силос, сено, зерно, комбикорм, микроэлементы, витаминные добавки. Количество скармливаемого животному продукта j -го вида обозначим M_j (j = 1, 2, …, n). Через a_ij обозначим количество i -го вещества, содержащегося в одной единице продукта j -го вида.

Из указанных данных составим таблицу рациона следующего вида.

	M 1	M 2	…	Mj	…	Mn
N 1	a 11	a 12	…	a 1 j	…	a 1 n
N 2	a 21	a 22	…	a 2 j	…	a 2 n
…	…	…	…	…	…	…
Ni	ai 1	ai 2	…	aij	…	ain
…	…	…	…	…	…	…
Nm	am 1	am 2	…	amj	…	amn

Введем еще несколько обозначений: x_j - количество j -го продукта, скармливаемого животному за 1 единицу времени (например, неделю); c_j – стоимость единицы j -го продукта; b_i - минимальное количество i -го вещества, которое должно получить каждое животное.

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

Математически задача запишется так:

- - - - - - - - - - - - - - - - - - - - -

Это задача ЛП во второй стандартной форме записи.

2. Составление плана производства товаров. Пусть имеется предприятие, которое выпускает n видов товаров G ₁, G ₂, …, G_n. Для производства этих товаров используется m видов ресурсов R ₁, R ₂, …, R_m. Обозначим через a_ij количество ресурса R_i, которое необходимо при производстве одной единицы товара G_j. Составим матрицу

	G 1	G 2	…	Gj	…	Gn
R 1	a 11	a 12	…	a 1 j	…	a 1 n
R 2	a 21	a 22	…	a 2 j	…	a 2 n
…	…	…	…	…	…	…
Ri	ai 1	ai 2	…	aij	…	ain
…	…	…	…	…	…	…
Rm	am 1	am 2	…	amj	…	amn

Матрица A = [ a_ij ] полностью характеризует технологию производства, поэтому она называется технологической матрицей.

Запасы используемых ресурсов ограничены и характеризуются величинами b_i Пусть от продажи единицы товара G_j предприятие получает прибыль c_j Количество планируемого выпуска товара G_j будем обозначать x_j Требуется составить такой план производства товаров, чтобы получаемая при этом прибыль была максимальной. Математически эта задача записывается так:

- - - - - - - - - - - - - - - - - - - - -

Это задача ЛП в первой стандартной форме записи.

Дата добавления: 2014-01-11