Бщая постановка задач линейного программирования.

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

одели математического программирования.

бщая постановка задач линейного программирования.

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

Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение.

Если целевая функция в задаче является функцией n - переменной, то методы решения называются методами математического программирования.

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

Задачей линейного программирования называется задачей исследования операций, математическая модель которой имеет вид:

F(x) = c_jx_j=c₁x₁+c₂x₂+…+c_nx_n → min (max)

Линейная функция (целевая функция) стремится либо к min, либо к max.

a_ijx_j ≤ b_j (или ≥b), i = = 1,2…m

Все переменные должны быть x_j ≥ 0, j =

Название системы: система организации задачи линейного программирования (ЗЛП).

Если математическая модель ЗЛП имеет вид

x_j ≥ 0, b_i ≥ 0, то ЗЛП представлена в канонической форме.

ПРАВИЛО приведения ЗЛП к канонической форме:

1. Если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на минус единицу;

3. Если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства.

Пример: Привести ЗЛП к канонической форме.

F_max = 3x₁ + x₂ + 5x₃

F = -3x₁ - x₂ - 5x₃→ min

Всякое не отрицательное решение системы ограничений называется допустимым.

Допустимое решение, дающее минимум функции F называется оптимальным.

Оптимальное решение не всегда будет единственным.

Рассмотрим процесс математических моделей ЗЛП на примерах:

1. Задача о диете.

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

Рассмотрим простую математическую модель этой задачи.

Пусть имеются два вида продуктов Р₁ и Р₂ содержащих питательные вещества А, В, С. S₁ и S₂ стоимость 1 кг продукта Р₁ и Р₂ соответственно. В таблице указано сколько питательного вещества содержащихся в 1 кг продукта Р₁ и Р₂ . Требуется рассчитать количество продуктов P₁ и P₂, так чтобы обеспечить необходимое количество питательных веществ при минимальных затратах на продуктах.

Продукт	А	В	С
P1	А1	В1	С1
P2	А2	В2	С2
Ежесут. требн.	А	В	С

x₁ – количество продукта P₁

x₂ – количество продукта P₂

x₁ ≥ 0, x₂ ≥ 0

F(x) = s₁x₁ + s₂x₂ → min

2. Задача о распространении ресурсов.

Предприятие имеет в своем распоряжении определенное количество ресурсов (сырье, оборудование и т.д.), из этих ресурсов выполняется определенное количество товаров.

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

Ресурсы	Товары		Кол-во
	T1	T2	ресурсов
R1	A11	A12	B1
R2	A21	A22	B2
R3	A31	A32	B3

S₁, S₂ - стоимость T₁ , T₂

x₁ – количество продукта T₁

x₂ – количество продукта T₂

x₁ ≥ 0, x₂ ≥ 0

F(x) = s₁x₁ + s₂x₂ → max