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

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

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

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

Решение:

X1 + 2X2 ≥ 14

X1 + 3X2 ≥ 15

2X1 + X2 ≥ 10

X1, X2 ≥ 0

3 X1 + 7 X2 → min

X1 + 2X2 = 14

X1 + 3X2 =15

2X1 + X2 = 10

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

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

Таблица 2.

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

Решение:

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. Запишем первоначальный опорный план:

Х0 (0, 0, 0, 0, 3,7), F0 = 9*0 + 14*0 +15*0 +10*0 + 0*3 +0*7 = 0

Составим соответствующую плану 1 симплексную таблицу:

Вычислим оценки:

∆ = (Сб*А) - С

∆1 = (0 *1 + 0*1) - 9 = - 9; ∆2 = (0 *1 + 0*2) - 14 = - 14; ∆3 = (0 *1 + 0*3) - 15 = - 15; ∆4 = (0 *2 + 0*1) - 10 = - 10; ∆5 = (0 *1 + 0*0) - 0 = 0; ∆6 = (0 *0 + 0*1) - 0 = 0

Критерием оптимальности является условие, что все ∆ ≥ 0, т.к. это не так, решение не оптимально.

Выберем вектор, который будем включать в базис:

min1 = (3/1; 7/1) = 3; min2 = (3/1; 7/2) =3; min3 = (3/1; 7/3) = 2 1/3; min4 = (3/2; 7/1) = 1 1/2,

теперь посмотрим соотношение min c ∆:

∆f = - ∆*min

∆f 1 = - (-9) *3 = 27; ∆f 2 = - (-14) *3 = 42; ∆f 3 = - (-15) *2 1/3 = 34.95; ∆f 4 = - (-10) *1 1/2 = 15,

Отсюда следует, что менять будем Р5 на Р2.

5. Составим 2 симплексную таблицу:

7- (3*2) /1 = 1; 1 - (1*2) /1 = - 1; 3 - (2*1) /1 = 1; 1- (2*1) /1 = - 1; 0- (1*1) /1 = - 1; 1- (0*1) /1 = 1

∆1 = 14*1+0* (-1) - 9 = 5; ∆3 = 14*1+0*1-15 = - 1; ∆4 = 14*2+0* (-1) - 10 = 4;

∆5 = 14*1+0* (-1) - 0 = 14; ∆6 = 14*0+0*1-0 = 0;

Х1 (0,3,0,0,0,1); F1 = 9*0+14*3+15*0+10*0+0*0+0*1 = 42