Линейное программирование: постановка задач и графическое решение

 

Таблица 2.1.

Вид сырья	Запас сырья	Количество  единиц сырья, идущих на изготовление единицы продукции
		Р1	Р2
S1	20	2	5
S2	40	8	5
S3	30	5	6
Прибыль от единицы  продукции, руб.		50	40

 

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

 

 

 

Решение.

Обозначим через  х₁ количество единиц продукции Р₁, а через х₂ – количество единиц продукции Р₂. Тогда, учитывая количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений:

2х₁ + 5х₂   20

8х₁ + 5х₂   40

5х₁ + 6х₂   30

 

которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысит имеющихся запасов. Если продукция Р₁ не выпускается, то х₁=0; в противном случае x₁ 0. То же самое получаем и для продукции Р₂. Таким образом, на неизвестные х₁ и х₂ должно быть наложено ограничение неотрицательности: х₁  0, х₂  0.

Конечную цель решаемой задачи – получение максимальной прибылипри реализации продукции –  выразим как функцию двух переменных х₁ и х₂. Реализация х₁ единиц продукции Р₁ и х₂ единиц продукции Р₂ дает соответственно 50х₁ и 40х₂ руб. прибыли, суммарная прибыль Z = 50х₁ + 40х₂ (руб.)

Условиями не оговорена  неделимость единица продукции, поэтому х₁ и х₂ (план выпуска продукции) могут быть и дробными числами.

Требуется найти  такие х₁ и х₂, при которых функция Z достинает максимум, т.е. найти максимальное значение линейной функции Z = 50х₁ + 40х₂ при ограничениях

 

2х₁ + 5х₂   20

8х₁ + 5х₂   40

5х₁ + 6х₂   30

 

х₁  0, х₂  0.

 

Построим многоугольник  решений (рис. 2.3).    

Для этого в  системе координат х₁Ох₂ на плоскости  на плоскости изобразим граничные прямые

 

2х₁ + 5х₂ = 20 (L₁)

8х₁ + 5х₂ = 40 (L₂)

5х₁ + 6х₂ = 30 (L₃)

 

х₁ = 0, х₂ = 0.

 

Взяв какую-нибудь точку, например, начало координат, установим, какую  полуплоскость определяет соответствующее  неравенство (эти полуплоскости на рис. 2.3 показаны стрелками). Многоугольником решений данной  задачи является ограниченный пятиугольник ОАВСD.

Для построения прямой 50х₁ + 40х₂ = 0 строим радиус-вектор N = (50;40) = 10(5;4) и через точку O проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора N. Из риc. 2.3 следует, что опорной по отношению к многоугольнику решений эта прямая становится в точке С, где функция Z принимает максимальное значение. Точка С лежит на пересечении прямых L₁ и L₂. Для определения ее координат решим систему уравнений                         

 

8x₁ + 5х₂ = 40

5х₁ + 6х₂ = 30

 

 

Оптимальный план задачи: х₁ = 90/23 = 3,9; х₂ = 40/23 =  1,7. Подставляя значения х₁ и х₂ в линейную функцию, получаем Z_max = 50 3,9 + 40 1,7 = 260,3

Таким образом, для того чтобы получить максимальную прибыль в размере 260,3 руб., необходимо запланировать производство 3,9 ед. продукции  Р₁ и 1,7 ед. продукции Р₂.

 

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

 

 

Таблица 2.2.

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

 

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

 

Решение.

Для составления  математической модели обозначим через  х₁ и х₂ соответственно количество килограммов корма 1 и 2 в дневном рационе. Принимая во внимание значения, приведенные в таблице 2.2, и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений

 

3х₁ +  х₂   9

 х₁ + 2х₂   8

 х₁ + 6х₂   12

 

 х₁  0, х₂  0.

 

Если корм 1 не используется в рационе, то х₁=0; в противном случае x₁ 0. Аналогично имеем х₂  0. То есть должно выполняться условие неотрицательности переменных: х₁  0, х₂  0.

Цель данной задачи – добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции Z = 4х₁ + 6х₂ (коп.)

Требуется найти  такие х₁ и х₂, при которых функция Z принимает минимальное. Таким образом, необходимо найти минимальное значение линейной функции Z = 4х₁ + 6х₂ при ограничениях

3х₁ +  х₂   9

 х₁ + 2х₂   8

 х₁ + 6х₂   12

 

 х₁  0, х₂  0.

 

Построим многоугольник  решений (рис. 2.4). Для этого в системе  координат х₁Ох₂ на плоскости изобразим граничные прямые

3х₁ +  х₂ = 9  (L₁)

 х₁ + 2х₂ = 8 (L₂)

 х₁ + 6х₂ = 12 (L₃)

 

 х₁ = 0, х₂ = 0.

 

Взяв какую-нибудь точку, например, начало координат, установим, какую  полуплоскость определяет соответствующее  неравенство (эти полуплоскости  на рис. 2.4 показаны стрелками). В результате получим неограниченную многоугольную область с угловыми точками А, В, С, D.

 

Для построения прямой 4х₁ + 6х₂ = 0 строим радиус-вектор N = (4;6) и через точку O проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора N. Из риc. 2.4 следует, она впервые коснется многогранника решений  и станет опорной по отношению к нему в угловой точе В. Если прямую перемещать дальше в направлении вектора N, то значения линейной функции на многограннике решений возрастут, значит, в точке В линейная функция Z принимает минимальное значение.

Точка В лежит  на пересечении прямых L₁ и L₂. Для определения ее координат решим систему уравнений                         

3x₁ +  х₂ = 9

 х₁ + 2х₂ = 8

Имеем: х₁ = 2; х₂ = 3. Подставляя значения х₁ и х₂ в линейную функцию, получаем Z_min = 4 2 + 6 3 = 26.

Таким образом, для того, чтобы обеспечить минимум  затрат (26 коп. в день), необходимо дневной  рацион составить из 2 кг корма 1 и 3 кг корма 2.

 

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

 

Вообще, с помощью графического метода может быть ре-шена задача линейного программирования,  система ограниче-ний  которой содержит n неизвестных и m линейно независи-мых уравнений, если N и M связаны соотношением N – M = 2.

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

Найти минимальное  значение линейной функции Z = С₁х₁+С₂х₂+... +С_Nx_N при ограничениях

 

a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁

(2.3) a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂

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

a_М1x₁ + a_М2x₂ + ... + a_МNХ_N = b_М

 

x_j  0 (j = 1, 2, ..., N)

 

где все уравнения  линейно независимы и выполняется cоотношение N - M = 2.                                        

Используя метод  Жордана-Гаусса, производим M исключений, в результате которых базисными неизвестными оказались, например, M первых неизвестных х₁, х₂, ..., х_M, а свободными - два последних: х_М+1, и х_N, т. е. система ограничений приняла вид

 

x₁ + a_1,М+1x_М+1 + a_1NХ_N = b₁

(2.4) x₂ + a_2,М+1x_М+1 + a_2NХ_N = b₂

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

x_М + a_{М, М+1}x₂ + a_МNХ_N = b_М

 

x_j  0 (j = 1, 2, ..., N)

 

С помощью уравнений  преобразованной системы выражаем линейную функцию только через свободные  неизвестные и, учитывая, что все  базисные неизвестные - неотрицательные: х_j 0 (j = 1, 2, ..., M), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств. Таким образом, окончательно получаем следующую задачу.          

Найти минимальное  значение линейной функции Z = С_М+1х_М+1+С_Nx_N при ограничениях

 

a_1,М+1x_М+1 + a_1NХ_N   b₁

a_2,М+1x_М+1 + a_2NХ_N   b₂

. . . . . . . . . .

a_М,М+1x_М+1 + a_МNХ_N   b_М

 

x_М+1  0, х_N  0

 

Преобразованная задача содержит два неизвестных; решая  ее графическим методом, находим  оптимальные значения x_М+1 и х_N, а затем, подставляя их в (2.4), находим оптимальные значения х₁, х₂, ..., х_M.

 

Пример.

Графическим методом  найти оптимальный план задачи ли-нейного программирования, при котором линейная функция Z = 2х₁ - х₂ + х₃ - 3х₄ + 4х₅ достигает максимального значения при ограничениях

 

х₁ - х₂ + 3х₃ - 18х₄ + 2х₅ = -4

2х₁ - х₂ + 4х₃ - 21х₄ + 4х₅ = 2

3х₁ - 2х₂ + 8х₃ - 43х₄ + 11х₅ = 38

 

x_j  0 (j = 1, 2, ..., 5)

 

Решение.

Используя метод  Жордана-Гаусса, произведем три полных исключения неизвестных х₁, х₂, х₃. В результате приходим к системе

х₁ + х₄ - 3х₅ = 6

х₂ + 7х₄ + 10х₅ = 70

х₃ - 4х₄ + 5х₅ = 20

Откуда x₁ = 6 – х₄ + 3x₅, х₂ = 70 – 7х₄-10х₅, х₃ = 20 + 4х₄ -5х₅.

Подставляя  эти значения в функцию и отбрасывая в системе базисные переменные, получаем задачу, выраженную только через свободные  переменные х₄ и х₅: найти максимальное значение линейной функции Z = 6х₄ + 15х₅ – 38 при ограничениях

х₄ - х₅  6

7х₄ + 10х₅  70

- 4х₄ + 5х₅  20

 

х₄  0, х₅  0.

Построим многогранник решений и линейную функцию в  системе координат х₄Ох₅ (рис. 2.5). Из рис. 2.5 заключаем, что линейная функция принимает максимальное значение в угловой точке В, которая лежит на пересечении прямых 2 и 3. В результате решения системы

 

  7х₄ + 10х₅ = 70

• 4х₄ +  5х₅  = 20

находим: х₄ = 2, х₅ = 28/5. Максимальное значение функции Z_max = -38 + 12 + 84 = 58.

Для отыскания  оптимального плана исходной задачи подставляем найденные значения х₄ и х₅. Окончательно получаем: х₁ = 104/5, х₂ = 0, х₃ = 0, х₄ = 2, х₅ = 28/5.

ЛИТЕРАТУРА

 

1. Математические методы анализа экономики /под ред. А.Я.Боярского. М.,Изд-во Моск. Ун-та, 1983
2. А.И.Ларионов, Т.И.Юрченко “Экономико-математические методы в планировании: Учебник – М.: Высш.школа, 1984
3. Ашманов С.А. “Линейное программирование”,- М.: 1961