Область применения.
Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного простран6тва, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств.
Задачу пространства размерности больше трех изобразить графически вообще невозможно.
Пусть задача линейного программирования задана в двумерном пространстве, т. е. ограничения содержат две переменные. Найти минимальное значение функции (2.1) Z = С 1 х 1 +С 2 х 2 при a 11 x 1 + a 22 x 2 b 1 (2.2) a 21 x 1 + a 22 x 2 b 2 a M1 x 1 + a M2 x 2 b M (2.3) х 1 0, х 2 0 Допустим, что система (2.2) при условии (2.3) совместна и ее многоугольник решений ограничен.
Каждое из неравенств (2.2) и (2.3), как отмечалось выше, определяет полуплоскость с граничными прямыми: a i1 x 1 + a i2 x 2 + a i3 x 3 = b i ,(i = 1, 2, n), х 1 =0, х 2 =0. Линейная функция (2.1) при фиксированных значениях Z является уравнением прямой линии: С 1 х 1 + С 2 х 2 = const. Построим многоугольник решений системы ограничений (2.2) и график линейной функции (2.1) при Z = 0 (рис. 2.1). Тогда поставленной задаче линейного прграммирования можно дать следующую интерпретацию.
Найти точку многоугольника решений, в которой прямая С 1 х 1 + С 2 х 2 = const опорная и функция Z при этом достигает минимума. Значения Z = С 1 х 1 + С 2 х 2 возрастают в направлении вектора N =(С 1 , С 2 ), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора Х. Из рис. 2.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х 1 , х 2 ) находим, решая систему уравнений прямых АВ и АЕ. Если многоугольник решений представляет собой неограниченную многоуголь-ную область, то возможны два случая.
Случай 1. Прямая С 1 х 1 + С 2 х 2 = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.2). Случай 2. Прямая, пере-двигаясь, все же становится опорной относительно многоу-гольника решений (рис. 2.2, а – 2.2, в). Тогда в зави-симости от вида области ли-нейная функция может быть ограниченной сверху и неограниченной снизу (рис. 2.2, а), ограниченной снизу и неограниченной сверху (рис. 2.2, б), либо ограниченной как снизу, так и сверху (рис. 2.2, в). 2.1. Примеры задач, решаемых графическим методом. Решим графическим методом задачи использования сырья и составления рациона.
Задача использования сырья. Для изготовления двух видов продукции Р 1 и Р 2 используют три вида сырья: S 1 , S 2 , S 3 . Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукци, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.1. Таблица 2.1. Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции Р 1 Р 2 S 1 20 2 5 S 2 40 8 5 S 3 30 5 6 Прибыль от единицы продукции, руб. 50 40 Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.
Решение.
Обозначим через х 1 количество единиц продукции Р 1 , а через х 2 – количество единиц продукции Р 2 . Тогда, учитывая количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений: 2х 1 + 5х 2 20 8х 1 + 5х 2 40 5х 1 + 6х 2 30 которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысит имеющихся запасов. Если продукция Р 1 не выпускается, то х 1 =0; в противном случае x 1 0. То же самое получаем и для продукции Р 2 . Таким образом, на неизвестные х 1 и х 2 должно быть наложено ограничение неотрицательности: х 1 0, х 2 0. Конечную цель решаемой задачи – получение максимальной прибылипри реализации продукции – выразим как функцию двух переменных х 1 и х 2 . Реализация х 1 единиц продукции Р 1 и х 2 единиц продукции Р 2 дает соответственно 50х 1 и 40х 2 руб. прибыли, суммарная прибыль Z = 50х 1 + 40х 2 (руб.) Условиями не оговорена неделимость единица продукции, поэтому х 1 и х 2 (план выпуска продукции) могут быть и дробными числами.
Требуется найти такие х 1 и х 2 , при которых функция Z достинает максимум, т.е. найти максимальное значение линейной функции Z = 50х 1 + 40х 2 при ограничениях 2х 1 + 5х 2 20 8х 1 + 5х 2 40 5х 1 + 6х 2 30 х 1 0, х 2 0. Построим многоугольник решений (рис. 2.3). Для этого в системе координат х 1 Ох 2 на плоскости на плоскости изобразим граничные прямые 2х 1 + 5х 2 = 20 (L 1 ) 8х 1 + 5х 2 = 40 (L 2 ) 5х 1 + 6х 2 = 30 (L 3 ) х 1 = 0, х 2 = 0. Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство (эти полуплоскости на рис. 2.3 показаны стрелками). Многоугольником решений данной задачи является ограниченный пятиугольник ОАВСD. Для построения прямой 50х 1 + 40х 2 = 0 строим радиус-вектор N = (50;40) = 10(5;4) и через точку O проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора N. Из риc. 2.3 следует, что опорной по отношению к многоугольнику решений эта прямая становится в точке С, где функция Z принимает максимальное значение.
Точка С лежит на пересечении прямых L 1 и L 2 . Для определения ее координат решим систему уравнений 8x 1 + 5х 2 = 40 5х 1 + 6х 2 = 30 Оптимальный план задачи: х 1 = 90/23 = 3,9; х 2 = 40/23 = 1,7. Подставляя значения х 1 и х 2 в линейную функцию, получаем Z max = 50 3,9 + 40 1,7 = 260,3 Таким образом, для того чтобы получить максимальную прибыль в размере 260,3 руб необходимо запланировать производство 3,9 ед. продукции Р 1 и 1,7 ед. продукции Р 2 . Задача составления рациона.
При откорме каждое животное ежедневно должно получать не менее 9 ед. питательного вещества S 1 , не менее 8 ед. вещества S 2 и не менее 12 ед. вещества S 3 . Для составления рациона используют два вида корма.
Содержание количества елиниц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 2.2. Таблица 2.2. Питательные вещества Количество единиц питательных веществ в 1 кг корма.
Корм 1 Корм 2 S 1 3 1 S 2 1 2 S 3 1 6 Стоимость 1 кг корма, коп. 4 6 Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными.
Решение. Для составления математической модели обозначим через х 1 и х 2 соответственно количество килограммов корма 1 и 2 в дневном рационе. Принимая во внимание значения, приведенные в таблице 2.2, и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений 3х 1 + х 2 9 х 1 + 2х 2 8 х 1 + 6х 2 12 х 1 0, х 2 0. Если корм 1 не используется в рационе, то х 1 =0; в противном случае x 1 0. Аналогично имеем х 2 0. То есть должно выполняться условие неотрицательности переменных: х 1 0, х 2 0. Цель данной задачи – добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции Z = 4х 1 + 6х 2 (коп.) Требуется найти такие х 1 и х 2 , при которых функция Z принимает минимальное.
Таким образом, необходимо найти минимальное значение линейной функции Z = 4х 1 + 6х 2 при ограничениях.