Задача составления рациона (задача о диете, задача о смесях).

Имеется два вида корма I и II, содержащих питательные вещества ресурсов S ₁, S ₂ и S ₃. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице (Таблица 2).

Таблица 2

Питательные вещества	Число единиц питательных веществ в 1 кг корма	Необходимый минимум питательных веществ в день
Корм I	Корм II
S 1
S 2
S 3

 

Стоимость одного кг корма I и II соответственно равна 4 и 6 рублей.

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

 

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

Обозначим через х ₁ и х ₂ – количество кормов I и II, входящих в дневной рацион (в килограммах). Тогда этот рацион (согласно Таблице 2) будет включать:

единиц питательного вещества S ₁;

единиц питательного вещества S ₂;

единиц питательного вещества S ₃.

Т.к. содержание питательных веществ S ₁, S ₂ и S ₃ в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим систему неравенств:

По смыслу задачи переменные х ₁ и х ₂ неотрицательны, т.е.

.

Общая стоимость рациона F составит: 4 х ₁ рублей – затраты на покупку корма I и 6 х ₂ рублей – затраты на покупку корма II, т.е.

.

Итак, экономико-математическая модель задачи: найти такое решение системы неравенств (при условии неотрицательности переменных), при котором функция затрат принимает минимальное значение.

При записи решения это оформляется кратко:

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

.

 

§ 4. Общая задача линейного программирования

 

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

Дана система т линейных уравнений и неравенств с п неизвестными:

a 11 x 1	+	a 12 x 2	+ … +	a 1 n xn	³	b 1
…	…	…	…	…	…	…
ak 1 x 1	+	ak 2 x 2	+ … +	akn xn	³	bk
a k +1,1 x 1	+	ak +1,2 x 2	+ … +	ak +1, n xn	£	bk +1
…	…	…	…	…	…	…
ai 1 x 1	+	ai 2 x 2	+ … +	ain xn	£	bi
a i +1,1 x 1	+	ai +1,2 x 2	+ … +	ai +1, n xn	=	bi +1
…	…	…	…	…	…	…
am 1 x 1	+	am 2 x 2	+ … +	amn xn	=	bm

и линейная функция

F = c ₁ x ₁ + c ₂ x ₂ + …+ c_n x_n.

Требуется найти такое решение системы Х = (x ₁, x ₂, …, x_n ), где x ₁ ≥ 0, x ₂ ≥ 0, …, x_n ≥ 0, при котором функция F принимает оптимальное (т.е. наименьшее наибольшее) значение.

Систему уравнений и неравенств называют системой ограничений данной задачи; функцию F — целевой функцией (или функцией цели, или линейной формой).

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

a_{i 1} x ₁ + a_{i 2} x₂ + …… + a_iп x_n ≥ b_i,

то, вводя неизвестное х_{n+ 1} ≥ 0, получим:

a_{i 1} x ₁ + a_{i 2} x₂ + …… + a_iп x_n – х_{n+ 1} = b_i,

а если имеется неравенство

a_{j 1} x ₁ + a_{j 2} x₂ + …… + a_jп x_n £ b_j,

то, вводя неизвестное х_{n+ 2} ≥ 0, получим:

a_{j 1} x ₁ + a_{j 2} x₂ + …… + a_jп x_n + х_{n+ 2} = b_j.

Таким образом, систему ограничений любой ЗЛП можно привести к системе, содержащей только линейные уравнения:

a 11 x 1	+	a 12 x 2	+ … +	a 1 n xn	=	b 1
a 21 x 1	+	a 22 x 2	+ … +	a 2 n xn	=	b 2
…	…	…	…	…	…	…
am 1 x 1	+	am 2 x 2	+ … +	amn xn	=	bm

В этом случае говорят, что задача линейного программирования записана в канонической форме.

Кроме того, так как min F = – max (– F), то любая задача на максимизацию сводится к задаче минимизации (и наоборот).

 

Линейное программирование