Линейное программирование как метод оптимизации (стр. 2 из 4)

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

(2.1)

(2.2)

(2.3)

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

В обоих случаях А есть матрица размерности m x n, i-я строка которой совпадает с вектором а_i.

Задача ЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим понимается существование общего способа построения по исходной задаче (в общей форме) новой задачи ЛП (в нужной нам форме), любое оптимальное решение которой "легко" преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной). Тем самым мы получаем возможность, не теряя общности, заниматься изучением задач ЛП, представленных либо в канонической, либо в стандартной форме. Ввиду этого наши дальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в канонической форме.

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

Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1, X2, Xn, удовлетворяющих ограничениям в виде равенств:

A11X1 + A12X2 + … + A1nXn = B1;

A21X1 + A22X2 + … + A2nXn = B2;

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

Am1X1 + Am2X2 + … + AmnXn = Bm;

Xj≥ 0, j=1,…,n

и обращающих в максимум линейную функцию этих переменных:

E= C1X1 + C2X2 + … + CnXnÞmax

При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:

Bj≥ 0, j=1,…,n

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

перейти от минимизации целевой функции к ее максимизации;

изменить знаки правых частей ограничений;

перейти от ограничений-неравенств к равенствам;

избавиться от переменных, не имеющих ограничений на знак.

Для решения нашей задачи воспользуемся симплекс-методом, так как этот метод предназначен для решения задач линейного программирования любой размерности.

3. Примеры экономических задач, приводящихся к задачам ЛП

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

Рассмотрим некоторые из них.

Определение оптимального ассортимента. Имеются m видов ресурсов в количествах b1, b2,., b_i, b_m и n видов изделий. Задана матрица A=||a_ij||, i=1,.,m, j=1,.,n, где a_ij характеризует нормы расхода i-го ресурса на единицу j-го вида изделий. Эффективность производства j-го вида изделий характеризуется показателем C_j, удовлетворяющим условию линейности. Нужно определить такой план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности будет наибольший.

Обозначим количество единиц k-го вида изделий, выпускаемых предприятием, через x_k,

. Тогда математическая модель этой задачи будет иметь такой вид:

(3.1)

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

(3.2)

Кроме ограничений на ресурсы (3.2) в эту модель можно ввести дополнительные ограничения на планируемый уровень выпуска продукции

, x_i: x_j: x_k = b_i: b_j: b_k для всех i, j, k и т.д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеются m видов взаимозаменяемых ресурсов а₁, а₂,., а_m, используемых при выполнении n различных работ (задач). Объемы работ, которые должны быть выполнены, составляют b₁, b₂,., b_i, b_n единиц. Заданы числа

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

Данная задача называется общей распределительной задачей. Количество единиц i-го ресурса, которое выделено на выполнение работ j-го вида, обозначим через x_ij.

Математическая модель рассматриваемой задачи такова:

(3.3)

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

(3.4)

(3.5)

Ограничение (3.4) означает, что план всех работ должен быть выполнен полностью, а (3.5) означает, что ресурсы должны быть израсходованы целиком.

Примером этой задачи может быть задача о распределении самолетов по авиалиниям.

Задача о смесях. Имеется р компонентов, при сочетании которых в разных пропорциях получают разные смеси. Каждый компонент, а следовательно и смесь, содержит q веществ. Количество k-го вещества k = 1, 2,., q, входящее в состав единицы і-го компонента и в состав единицы смеси, обозначим через а_ik и а_k соответственно.

Предположим, что а_k зависит от а_ik линейно, то есть если смесь состоит из x₁ единиц первого компонента, x₂ - единицу второго компонента и т.д., то

Задано р величин C_i, характеризующих стоимость, массу или калорийность единицы i-го компонента, и q величин b_k, указывающих минимально необходимое процентное содержание k-го вещества в смеси. Обозначим через x₁, x₂,.,x_р значение компонента р-го вида, входящего в состав смеси.

Математическая модель этой задачи имеет такой вид:

(3.6)

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

(3.7)

Ограничение (3.7) означает, что процентное содержание k-го вещества в единице смеси должно быть не меньше b_k.

К этой же модели принадлежит также задача определения оптимального рациона кормления скота.

4. Геометрический метод решение задач ЛП

Задача 1. При откорме каждое животное должно получить не менее 14 ед.питательного вещества S₁, не менее 15 ед. вещества S₂ и не менее 10 вещества S₃. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 килограмме каждого вида корма и стоимость одного килограмма корма дана в таблице 1.

Таблица 1

Питательные вещества	Количество единиц питательных веществ в 1 кг. корма
	корм 1	корм 2
S1	1	2
S2	1	3
S3	2	1
Стоимость 1 кг. корма	3	7

Составить рацион минимальной стоимости.

Решение:

X1 + 2X2 ≥ 14

X1 + 3X2 ≥ 15

2X1 + X2 ≥ 10

X1, X2 ≥ 0

3X1 + 7 X2 → min

X1 + 2X2 = 14

X1 + 3X2 =15

2X1 + X2 = 10

5. Симплексный метод решения задач ЛП

Задача 2. Для изготовления 4-ёх видов продукции P₁, P₂, P₃, P₄ используют два вида сырья: S₁ и S₂. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.

Таблица 2.

Вид сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
		P1	P2	P3	P4
S1	3	1	1	1	2
S2	7	1	2	3	1
Прибыль от единицы продукции		9	14	15	10

Составить план производства, обеспечивающий получений максимальной прибыли.

Решение:

1. Формальная постановка задачи имеет следующий вид:

9X1 + 14X2 + 15 X3 + 10X4 → max

X1 + X2 + X3 + 2X4 ≤ 3

X1 + 2X2 + 3X3 + X4 ≤ 7

X1, X2, X3, X4 ≥ 0

2. Приведем к стандартной (канонической) форме:

F = 9X1 + 14X2 +15X3 + 10X4 + 0X5 + 0X6

X1 + X2 + X3 + 2X4 + X5 = 3

X1 + 2X2 +3X3 + X4 + X6 = 7

X1, X2, X3, X4 ≥ 0

3. Запишем систему ограничений в векторной форме:

X1 (1/1) + X2 (1/2) + X3 (1/3) + X4 (2/1) + X5 (1/0) + X6 (0/1) = (3/7)

P1 P2 P3 P4 P5 P6 P0

P5, P6 - базисные

4. Запишем первоначальный опорный план: