Решение оптимизационных экономических задач методами линейного программирования

                                             x₁ + 2x₂ ≥ 4,                                                     (5)

                                            x₁ ≥ 1;

                                             x₁ ≥ 0,   x₂ ≥ 0.   

 

Задача  об использовании ресурсов (задача планирования производства)

Для изготовления двух видов  продукции P1 и P2 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице 2.

Прибыль, получаемая от единицы  продукции P1 и P2, — соответственно 2 и 3 руб.

 

Таблица 2 – Исходные данные к задаче об использовании  ресурсов

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых  на изготовление единицы продукции
		P1	P2
S1	18	1	3
S2	16	2	1
S3	5	0	1
S4	21	3	0

 

Необходимо составить такой  план производства продукции, при котором  прибыль от ее реализации будет максимальной.

Решение. Составим экономико-математическую модель задачи.

Обозначим x₁, x₂ — число единиц продукции соответственно P1 и P2, запланированных к производству. Для их изготовления потребуется (1x₁ + 3x₂) единиц ресурса S1, (2x₁ + 1x₂) единиц ресурса S2, (1x₂) единиц ресурса S3 и 3x₁ единиц ресурса S4. Так как потребление ресурсов S1, S2, S3 и S4 не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

 

 

 

x₁ +3x₂ ≤ 18

2x₁ +x₂ ≤ 16                                                 (6)

x₂ ≤ 5

3x₁ ≤ 21

 

По смыслу задачи переменные

 

                                                x₁ ≥ 0, x₂  ≥ 0                                             (7)

 

Суммарная прибыль F составит 2x₁ руб. от реализации продукции P1 и 3x₂ руб. — от реализации продукции P2, т.е.

 

                                           F = 2x₁ + 3x₂                                                   (8)

 

Итак, экономико-математическая модель задачи:

найти такой план выпуска продукции  X = (x₁,x₂), удовлетворяющий системе (3) и условию (4), при котором функция (5) принимает максимальное значение.

Эту задачу (как и другие приведенные  примеры) можно легко обобщить на случай выпуска n видов продукции с использованием m видов ресурсов.

Обозначим x_j (j = 1,2,...,n) — число единиц продукции Pj, запланированной к производству;

bi (i = 1, 2, . . . , m) — запас ресурса Si,

a_ij — число единиц ресурса Si, затрачиваемого на изготовление единицы продукции Pj (числа a_ij часто называют технологическими коэффициентами);

c_j — прибыль от реализации единицы продукции Pj.

Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план X = (x₁,x₂,...,x_n) выпуска продукции, удовлетворяющий системе:

a₁₁x₁ + a₁₂x₂ + . . . + a_1nx_n ≤ b₁

a₂₁x₁ + a₂₂x₂ + . . . + a_2nx_n ≤ b₂                                     (9)

. . . . . . . . . . . . . . . . . . . . . . . .

a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ b_m

 

и условию

 

                                   x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0,                                      (10)

 

при котором функция

 

                                   F = c₁x₁ + c₂x₂ + . . . + c_nx_n                                      (11)

 

принимает максимальное значение.

Задача  об использовании мощностей (задача о запуске оборудования)

Предприятию задан план производства продукции по времени и номенклатуре: требуется за время T выпустить n₁, n₂, ..., n_k единиц продукции P1, P2, ..., Pk. Продукция производится на станках S1, S2, ..., Sm. Для каждого станка известны производительность a_ij (т.е. число единиц продукции Pj, которое можно произвести на станке Si) и затраты b_ij на изготовление продукции Pj на станке Si в единицу времени.

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

Составим экономико-математическую модель задачи.

Обозначим x_ij — время, в течение которого станок Si будет занят изготовлением продукции Pj (i =1, 2, . . . , m; j = 1, 2, . . . , k).

Так как время работы каждого станка ограничено и не превышает T, то справедливы неравенства:

x₁₁ + x₁₂ + . . . + x_1k ≤ T

x₂₁ + x₂₂ + . . . + x_2k ≤ T                                          (12)

. . . . . . . . . . . . . . . . . . . . . . . .

x_m1 + x_m2 + ... + x_mk ≤ T

 

Для выполнения плана выпуска по номенклатуре необходимо, чтобы выполнялись следующие неравенства:

a₁₁x₁₁ + a₂₁x₂₁ + . . . + a_m1x_m1 ≤ n₁

a₁₂x₁₂ + a₂₂x₂₂ + . . . + a_m2x_m2 ≤ n₂                          (13)

. . . . . . . . . . . . . . . . . . . . . . . .

a_1kx_1k + a_2kx_2k + . . . + a_mkx_mk ≤ n_k

 

Кроме того,

 

                                  x_ij ≥ 0 (i = 1, 2, . . . , m; j = 1, 2, . . . , k)                  (14)

 

Затраты на производство всей продукции выразятся функцией

 

                                 F = b₁₁x₁₁ + b₁₂x₁₂ + . . . + b_mkx_mk                              (15)

 

Экономико-математическая модель задачи об использовании мощностей  примет вид: найти такое решение X = (x₁₁, x₁₂, . . . , x_mk), удовлетворяющее системам (9) и (10) и условию (11), при котором функция (12) принимает минимальное значение.

Транспортная  задача

Имеются 2 поставщика и 3 потребителя одного груза. Запасы груза у поставщиков (мощности поставщиков), спросы потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик-потребитель» сведены в таблицу поставок (таблица 4).

В левом верхнем углу произвольной (i;j)-клетки стоит так называемый коэффициент затрат (тариф) — затраты на перевозку единицы груза от i-го поставщика к j-му потребителю.

Задача ставится следующим  образом. Найти объемы перевозок  для каждой пары «поставщик-потребитель» так, чтобы:

а) мощности всех поставщиков  были реализованы;

б) спросы всех потребителей были удовлетворены;

в) суммарные затраты  на перевозку были бы минимальны.

 

Таблица 3 – Таблица поставок

Поставщики	Мощность поставщиков	Потребители и их спрос
		1	2	3
		50	30	80
1	60	1	2	4
		х11	х12	х13
2	100	3	1	6
		х21	х22	х23

 

Составим экономико-математическую модель задачи.

Обозначим x_ij — объем груза, перевозимого от i-го поставщика к j-му потребителю.

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

Так, например, объем груза, забираемого от 1-го поставщика, должен быть равен мощности этого поставщика — 60 ед., т.е. x₁₁ + x₁₂ + x₁₃ = 60. Аналогичное ограничение можно получить и для второго поставщика. Получим ограничения по поставщикам:

 

                                                 x₁₁ + x₁₂ + x₁₃ = 60                                     (13)

                                                 x₂₁ + x₂₂ + x₂₃ = 100

 

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

 

x₁₁ + x₂₁ = 50

x₁₂ + x₂₂ = 30                                              (14)

x₁₃ + x₂₃ = 80

 

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому

 

                                       x_ij ≥ 0 (i = 1, 2; j = 1, 2, 3)                                   (15)

 

Суммарные затраты F на перевозку выражаются через коэффициенты затрат и поставки следующим образом:

 

                               F = 1x₁₁ + 2x₁₂ + 4x₁₃ + 3x₂₁ + 1x₂₂ + 6x₂₃                  (16)

 

Итак, экономико-математическая модель задачи: необходимо найти такой  план перевозок груза X = (x₁₁, x₁₂, x₁₃, x₂₁, x₂₂, x₂₃), удовлетворяющий системам (13), (14) и условию (15), при котором функция (16) принимает минимальное значение.

 

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

 

Наиболее простым и  наглядным методом линейного  программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными.

Рассмотрим задачу ЛП в стандартной форме записи:

 

                                            max F(x) =                                            (17)

                                                   

                                                                                                (18)

                                                              

                                                                                                       (19)

           

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

Каждое неравенство этой системы  геометрически определяет полуплоскость  с граничной прямой  a_i1 x₁ + a_i2 x₂  =  b_i   , i=1,2,…m. Условия неотрицательности определяют полуплоскости, соответственно, с граничными прямыми x₁ = 0, x₂ = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

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

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

 

                                            .                                      (20)

 

Этот вектор показывает направление наискорейшего изменения  целевой функции. Прямая , перпендикулярная вектору–градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине “a”. Меняя значение “a”,  получим семейство параллельных прямых, каждая из которых является линией уровня.

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

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