Производственная задача

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

Круг задач:

-задача об оптимальном использовании ресурсов при производственном планировании;

-задача о смесях (планирование состава продукции);

-задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

-транспортные задачи (анализ размещения предприятия, перемещение грузов).

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать;ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

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

Задана система m линейных ограничений с n переменными:

a₁₁x₁ + a₁₂x₂ +… + a_1nx_n≤ (≥) b₁,

a₂₁x₁ + a22x2 +… + a2nxn≤ (≥) b₂,

…………………... ... ... ... ... ... ...,

a_k1x1 + ak2x2 +… + aknxn≤ (≥) b_k,

a_k+1,₁x₁ + a_k+1,2x₂ +… + a_k+1,nx_n = b_k+1,

a_k+2,₁x₁ + a_k+2,2x₂ +… + a_k+2,nx_n = b_k+2,

… … … … … … … ... ... ... ... ... ... ...,

a_m1x₁ + a_m2x₂ +… + a_mnx_n = b_m,

где: x₁≥ 0, x₂≥ 0,…, x_n≥0,

а линейная функция Z = c₁x₁ + c₂x₂ +… + c_nx_n→mаx (min).

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

Стандартная форма задачи линейного программирования:

a₁₁x₁ + a₁₂x₂ +… + a_1nx_n≤ (≥) b₁,

a₂₁x₁ + a₂₂x₂ +… + a_2nx_n≤ (≥) b₂,

… … … … … … … … … ... ...,

a_m1x₁ + a_m2x₂ +… + a_mnx_n≤ (≥) b_m,

где: x₁≥ 0, x₂≥ 0,…,x_n≥0,

а линейная функция Z = c₁x₁ + c₂x₂ +… + c_nx_n→ mаx (min)

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

Каноническая форма задачи линейного программирования:

Форма, в которой Z = c₁x₁ + c₂x₂ +… + c_nx_n→mаx,

a₁₁x₁ + a₁₂x₂ +… + a_1nx_n = b₁,

a₂₁x₁ + a₂₂x₂ +… + a_2nx_n = b₂,

… … … … … … … … … ...,

a_m1x₁ + a_m2x₂ +… + a_mnx_n= b_m,

все переменные неотрицательные: x1≥ 0, x2≥ 0,…, xn≥ 0, система ограничений представляет собой систему уравнений, а целевая функция стремится к максимуму.

Производственная задача

сырьё	Норма расхода на 1 кг			Запасы
сырьё	Карамель 1			Запасы
сах. песок	0,8	0,5	0,6
патока	0,4	0,4	0,3
фрукт. пюре	-	0,1	0,1
прибыль
	x1	x2	x3

0,8x1 + 0,5x2 + 0,6x3 ≤ 80

0,4x1 + 0,4x2 + 0,3x3 ≤ 60

0,1x2 + 0,1x3 ≤ 12

x1, x2, x3 ≥ 0

z = 1080x1 + 1120x2 + 1260x3 → max

12 Следующая ⇒