Линейное программирование постановка задач и графическое решение (стр. 2 из 3)

(2.3) х₁ 0, х₂ 0

Допустим, что система (2.2) при условии (2.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (2.2) и (2.3), как отмечалось выше, определяет полуплоскость с граничными прямыми: a_i1x₁+ a_i2x₂+ a_i3x₃ = b_i,(i = 1, 2, ..., n), х₁=0, х₂=0. Линейная функция (2.1) при фиксированных значениях Z является уравнением прямой линии: С₁х₁ + С₂х₂ = const. Построим многоугольник решений системы ограничений (2.2) и график линейной функции (2.1) при Z = 0 (рис. 2.1). Тогда поставленной задаче линейного прграммирования можно дать следующую интерпретацию. Найти точкумногоугольника решений, в которой прямая С₁х₁ + С₂х₂ = const опорная и функция Z при этом достигает минимума.

Значения Z = С₁х₁ + С₂х₂ возрастают в направлении вектора N =(С₁, С₂), поэтому прямую Z = 0передвигаем параллельно самой себе в направлении вектора Х. Из рис. 2.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х₁, х₂) находим, решая систему уравнений прямых АВ и АЕ.

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

Случай 1. Прямая С₁х₁ + С₂х₂ = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной кнему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.2).

Случай 2. Прямая, пере-двигаясь, все же становится опорной относительно многоу-гольника решений (рис. 2.2, а – 2.2, в). Тогда в зави-симости от вида области ли-нейная функция может быть ограниченной сверху и неограниченной снизу (рис. 2.2, а), ограниченной снизу и неограниченной сверху (рис. 2.2, б), либо ограниченной как снизу, так и сверху (рис. 2.2, в).

2.1. Примеры задач, решаемых графическим методом.

Решим графическим методом задачи использования сырья и составления рациона.

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

Таблица 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.