Основы линейного программирования

Наибольшее распространение в настоящее время получили методы линейного программирования.

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

Модель задачи линейного программирования (ЗЛП) должна иметь вполне определенный вид: требуется найти максимум (минимум) значения целевой функции L при переменных х_1,х₂ .. ., х_n

L(X) =с₁х₁ + c₂x₂ + .. . + с_пх_п max, min (1)

-при соблюдении системы линейных ограничений

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

a ₂₁x₁ + a ₂₂x₂+…+ a_2n x_n=b₂ (2)

………………………………

a _m1x₁ + a _m2x₂+…+ a_mnx_n=b_m

-условие неотрицательности

x _j 0; j=1,2,….,n (3)

Получили задачу линейного программирования (ЗЛП)

max L(x) =

при ограничениях по ресурсам

(i = 1, 2,……,m)

Функцию f(x₁,x_2, …,х_n) принято называть целевой, т.к. её максимизация (минимизация) часто есть выражение какой-то цели, систему ограничений– специальными ограничениями ЗЛП, неравенства x₁≥0 ,x≥0_2, …, х_n≥0 – общими ограничениями ЗЛП. Множество всех допустимых решений ЗМП (х_j≥0, j= ) называется допустимым множеством этой задачи.

При решении ЗЛП возможны следующие случаи:

1. задача имеет единственный оптимальный план;

2. задача имеет множество оптимальных планов;

3. линейная форма задачи не ограничена;

4. задача не имеет ни одного плана.

Если при решении задачи выполняется 2 и 3 условие, задача имеет множество допустимых решений. Если выполняются все три условия – задача имеет одно оптимальное решение.

При использовании ЗЛП в экономике:

x_j- объем выпуска j-го вида продукции (искомая величина);

j - номер продукта;

n – общее количество различных видов продукции;

a_ij – норма расхода i-го ресурса на j—й продукт

i – номер ресурса;

m – общее количество ресурса;

b_i – объем i-го вида ресурса;

с_j -цена, прибыль, доход, себестоимость, затраты единицы j—го вида продукции

Общая постановка ЗЛП

Пусть на предприятии выпускается два вида продукции П₁ и П₂.

На производство этой продукции расходуется 4-е вида сырья: S₁, S₂, S₃ и S₄.

Запасы каждого вида сырья (ресурсы) ограничены и составляют соответственно: в₁, в₂, в₃ и в₄.

Норма расхода на производство единицы первого вида продукции П₁: первого вида ресурса - а₁₁; второго вида ресурса – а₂₁; третьего вида ресурса – а₃₁; четвертого вида ресурса – а_41..

Норма расхода на производство единицы второго вида продукции П₂: первого вида ресурса - а₁₂; второго вида ресурса – а₂₂; третьего вида ресурса – а₃₂; четвертого вида ресурса – а₄₂

Доход от реализации продукта П₁ и П₂. – с₁ и с₂.

Цель: определить какое количество продукции вида П₁ и П₂ необходимо выпустить предприятию, чтобы получить max доход.

Исходную информацию лучше всего записать в табличной форме.

Вид ресурса	Вид продукции		Запас ресурса
	П1	П2.
S1	а11	а12	в1
S2	а21	а22	в2
S3	а31	а32	в3
S4	а41	а42	в4
Доход	с1	с2

Для составления ЗЛП введем неизвестные х₁ - П₁ и х₂ - П₂.

Составляем целевую функцию: L(X) =с₁х₁ + c₂x₂  max

Ограничительные уравнения (так как у нас четыре вида сырья, то и четыре ограничения): a₁₁x₁ + a ₁₂x₂ ≤b₁

a₂₁x₁ + a ₂₂x₂≤b₂

……………………

……………………

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

Условие неотрицательности: х₁ ≥ 0 и х₂ ≥ 0