Методы оптимальных решений решить графически. Графический метод решения злп

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

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

Поэтому графический метод имеет такие узкие рамки применения, что о нём как об особом методе решения задач линейного программирования говорить нельзя.

Однако для выработки наглядных представлений о решениях задач линейного программирования графический метод представляет определённый интерес. Кроме того, он позволяет геометрически подтвердить справедливость теорем линейного программирования .

Теоретические основы графического метода

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

при которых линейная форма принимает оптимальное значение.

Пример 3.

Пример 4. Решить графическим методом задачу линейного программирования, в которой требуется найти минимум функции при ограничениях

Продолжаем решать задачи графическим методом вместе

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

Пример 5. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях

Решение. На рисунке изображены: неограниченная многогранная область решений данной системы ограничений, исходная линия уровня (чёрного цвета), вектор (бордового цвета), указывающий направление движения исходной линии уровня для нахождения максимума целевой функции.

Легко заметить, что функция F может неограниченно возрастать при заданной системе ограничений, поэтому можно условно записать, что .

Пример 6. Решить графическим методом задачу линейного программирования, в которой требуется найти максимум функции при ограничениях

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

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

Инструкция . Выберите количество строк (количество ограничений).

Количество ограничений 1 2 3 4 5 6 7 8 9 10

Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. пример и пример №2). Если ограничение двойное, например, 1 ≤ x 1 ≤ 4 , то оно разбивается на два: x 1 ≥ 1 , x 1 ≤ 4 (т.е. количество строк увеличивается на 1).
Построить область допустимого решения (ОДР) можно также с помощью этого сервиса .

Вместе с этим калькулятором также используют следующие:
Симплексный метод решения ЗЛП

Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Вычисление пределов

Решение задачи линейного программирования графическим методом включает следующие этапы :

1. На плоскости X 1 0X 2 строят прямые.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c 1 ,c 2), который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c 1 x 2 + c 2 x 2 = 0 в направлении вектора N до крайней точки многоугольника решений.
6. Вычисляют координаты точки и значение целевой функции в этой точке.

При этом могут возникать следующие ситуации:

Пример . Компания изготавливает два вида продукции - П1 и П2. Для производства продукции используются два вида сырья - С1 и С2. Оптовые цены единицы продукции равна: 5 д.е. для П1 и 4 д.е. для П2. Расход сырья на единицу продукции вида П1 и вида П2 дан в таблице.
Таблица - Расход сырья на производство продукции

Установлены ограничения на спрос продукции: ежедневный объем производства продукции П2 не должен превышать ежедневный объем производства продукции П1 не более чем на 1 тонну; максимальный ежедневный объем производства П2 не должен превышать 2 т.
Требуется определить:
Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?

1. Сформулировать математическую модель задачи линейного программирования.
2. Решить задачу линейного программирования графическим способом (для двух переменных).

Решение.
Сформулируем математическую модель задачи линейного программирования.
x 1 - производство продукции П1, ед.
x 2 - производство продукции П2, ед.
x 1 , x 2 ≥ 0

Ограничения по ресурсам
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6

Ограничения по спросу
x 1 +1 ≥ x 2
x 2 ≤ 2

Целевая функция
5x 1 + 4x 2 → max

Тогда получаем следующую ЗЛП:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1 , x 2 ≥ 0
5x 1 + 4x 2 → max

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

Будем рассматривать решение этой задачи на плоскости. Каждое неравенство системы функциональных ограничений геометрически определяет полуплоскость с граничной прямой а п х, + + a j2 х 2 = b n i = 1, т. Условия неотрицательности определяют полуплоскости с граничными прямыми х { = 0, х 2 = 0 соответственно. Если система совместна, то полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек; координаты каждой из этих точек являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограниченным многоугольником.

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

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

Определим, какую часть плоскости описывает неравенство 2х { + Зх 2 12.

Во-первых, построим прямую 2х, + Зх 2 = 12. Она проходит через точки (6; 0) и (0; 4). Во-вторых, определим, какая полуплоскость удовлетворяет неравенству. Для этого выбираем любую точку на графике, не принадлежащую прямой, и подставляем ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать начало координат. Подставим х { = х 2 = 0 в неравенство 2х, + Зх 2 12. Получим 2 0 + 3 0

Аналогично графически можно изобразить все ограничения задачи линейного программирования.

Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений (ОДР) или областью определения.

Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (Xj > 0, j = 1, п). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.

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

Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая c [ x l + с 2 х 2 = f(x 0), перпендикулярная вектору-градиенту, является линией уровня целевой функции (рис. 2.2.2). В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине а. Меняя значение а, получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.

Рис. 2.2.2.

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

Графический метод решения ЗЛП состоит из четырех этапов:

• 1. Строится область допустимых решений (ОДР) ЗЛП.
• 2. Строится вектор-градиент целевой функции (ЦФ) с началом в точке х 0 (0; 0): V = (с, с 2).
• 3. Линия уровня CjXj + с 2 х 2 = а (а - постоянная величина) - прямая, перпендикулярная вектору-градиенту V, - передвигается в направлении вектора-градиента в случае максимизации целевой функции f(x v х 2) до тех пор, пока не покинет пределов ОДР. При минимизации /(*, х 2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Крайняя точка (или точки) ОДР при этом движении и является точкой максимума (минимума) f(x p jc 2).

Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимума (максимума) функции f(x р х 2) не существует.

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

4. Определяются координаты точки максимума (минимума). Для этого достаточно решить систему уравнений прямых, дающих в пересечении точку максимума (минимума). Значение f(x { , х 2), найденное в полученной точке, является максимальным (минимальным) значением целевой функции.

Возможные ситуации графического решения ЗЛП представлены в табл. 2.2.1.

Таблица 2.2.1

Вид ОДР	Вид оптимального решения
Ограниченная	Единственное решение
	Бесконечное множество решений
Неограниченная	ЦФ не ограничена снизу
	ЦФ не ограничена сверху
	Единственное решение
	Бесконечное множество решений
	Единственное решение
	Бесконечное множество решений

Пример 2.2.1. Планирование выпуска продукции пошивочного предприятия (задача о костюмах).

Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человекодень трудозатрат; на мужской - 3,5 м шерсти, 0,5 м лавсана и 1 человекодень трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человекодней трудозатрат.

Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 ден. ед., а от мужского - 20 ден. ед. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Экономико-математическая модель задачи

Переменные : х, - число женских костюмов; х 2 - число мужских костюмов.

Целевая функция :

Ограничения :

Первое ограничение (по шерсти) имеет вид х { + 3,5х 2 х { + 3,5х 2 = 350 проходит через точки (350; 0) и (0; 100). Второе ограничение (по лавсану) имеет вид 2х { + 0,5х 2 2х х + 0,5х 2 = 240 проходит через точки (120; 0) и (0; 480). Третье ограничение (по труду) имеет вид х у +х 2 150. Прямая х { + х 2 = 150 проходит через точки (150; 0) и (0; 150). Четвертое ограничение (по количеству мужских костюмов) имеет вид х 2 > 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х 2 = 60.

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

На рис. 2.2.3 затенена область допустимых решений (ОДР). Для определения направления движения к оптимуму построим вектор- градиент V, координаты которого являются частными производными целевой функции:

Чтобы построить такой вектор, нужно соединить точку (10; 20) с началом координат. Для удобства можно строить вектор, пропорциональный вектору V. Так, на рис. 2.2.3 изображен вектор (30; 60).

Затем построим линию уровня 10xj + 20х 2 = а. Приравняем целевую функцию постоянной величине а. Меняя значение а , получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.

Решение задачи линейного программирования (ЗЛП) графическим методом

Общая постановка злп

Найти значения n переменных x 1 , x 2 , …,x n , доставляющих экстремум (минимум или максимум) линейной функции Z=C 1 x 1 ,+ C 2 x 2+…+ C n x n

и одновременно удовлетворяющих m ограничениям вида

a 1,1 x 1 +a 1,2 x 2 +…+a 1,n x n £ =≥b 1 ,

a 2,1 x 1 +a 2,2 x 2 +…+a 2,n x n £ = ≥b 2 ,

. . . . . . . . . . . . . . . . . . . . . . .,

a m,1 x 1 +a m,2 x 2 +…+a m,n x n £ = ≥b m ,

при заданных a i,j , b i, C j (i=1,2,…,m; j=1,2,…,n). Знак отношения может принимать любое из трех приведенных значений.

Пример задачи линейного программирования

Рассмотрим следующую задачу. Менеджер предприятия, изготавливающего два вида красок, описал исследователю операций ситуацию, сложившуюся на производстве и рынке сбыта красок. Оказалось, что фабрика изготавливает два вида красок: для внутренних и внешних работ. Обе краски поступают в оптовую продажу. Для производства красок используются два исходных продукта – А и В. Максимально возможные суточные запасы этих продуктов 6 и 8 тонн соответственно. Опыт показал, что суточный спрос на внешнюю краску никогда не превышает спрос на внутреннюю более чем на 1 тонну. Кроме того, установлено, что спрос на внешнюю краску никогда не превышает 2 тонны в сутки. Оптовые цены одной тонны красок сложились следующим образом: 3 тысячи рублей на внешнюю краску и 2 тысячи рублей – на внутреннюю. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации был максимальным?

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

При построении математической модели специалист по исследованию операций ставит перед собой три вопроса.

• Для каких величин должна быть построена модель? Иначе говоря, нужно идентифицировать переменные задачи.
• Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?
• В чем состоит цель, для достижения которой из всех возможных (допустимых) значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?

Введем переменные:

x 1 – суточный объем производства внешней краски (в тоннах),

x 2 – суточный объем производства внутренней краски (в тоннах).

Учитывая оптовые цены на тонну каждого вида краски, суточный доход от продажи произведенной продукции задается линейной целевой функцией Z = 3x 1 + 2x 2 .

Целью производства является получение максимальной прибыли, значит, необходимо найти значения x 1 и x 2 , которые максимизируют целевую функцию Z.

Поскольку производитель красок не может распорядиться значениями переменных произвольным образом, постольку необходимо выделить множество возможных значений этих переменных, которое определяется конкретными условиями производства и сбыта. Это множество называется областью допустимых значений.

Первый тип ограничений определяется запасами продуктов А и В, из которых производятся краски. Из технологии производства известно, что на производство тонны внешней краски идут две части продукта А, а на тонну внутренней – одна часть. Для продукта В соотношение обратное. Эти технологические условия описываются неравенствами

2x 1 + x 2 £ 6 (на складе 6 тонн продукта А),

x 1 + 2x 2 £ 8 (на складе 8 тонн продукта В).

Последние два ограничения означают очевидное обстоятельство: нельзя использовать для производства красок больше продуктов А и В, чем их имеется фактически на складе.

Ситуация с реализацией красок на рынке приводит к следующим ограничениям: x 1 – x 2 £ 1 (внешней краски реализуется не более, чем на одну тонну больше внутренней), x 1 £ 2 (внешней краски продается не более двух тонн в день).

Суммируя все сказанное, можно математическую модель, описывающую сложившуюся производственную ситуацию, задать в следующей форме:

найти ® max{ Z=2× x 1 + 3× x 2 } при следующих ограничениях на значения переменных x 1 и x 2

2 × x 1 + x 2 £ 6 ограничение (1),

X 1 + 2 × x 2 £ 8 ограничение (2),

X 1 - x 2 £ 1 ограничение (3),

X 1 £ 2 ограничение (4)

и требование неотрицательности переменных x 1 ³ 0 (5), x 2 ³ 0 (6).

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

Графический метод решения злп

Графический метод решения злп может быть реализован только в двумерном случае.

Математическая модель, полученная для сформулированной типовой задачи, требует исследования, так как заранее не известно, имеет ли она (как математическая задача) решение. Исследование проведем с использованием графических построений. Одновременно с таким исследованием найдем (если оно есть) и решение.

1 этап. Построение области допустимых решений

Цель – построить область, каждая точка которой удовлетворяет всем ограничениям.

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

• · заменить в ограничении знак неравенства на равенство (получим уравнение прямой);

• · построить прямую по двум точкам;

• · определить, какую полуплоскость задает знак неравенства. Для этого подставить в неравенство какую-нибудь точку (например, начало координат). Если она удовлетворяет неравенству – закрашиваем полуплоскость, ее содержащую.

Такие действия выполняем для всех ограничений. Каждую из прямых обозначим номерами, принятыми при нумерации ограничений (см. рис).

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

Множество точек, удовлетворяющих всем шести ограничениям задачи – многоугольник AFEDCB.

2 этап Построение линий уровня целевой функции и определение точки максимума

Цель - найти в построенном многоугольнике A FEDCB точку, в которой функция цели Z=2x 1 + 3x 2 принимает максимальное значение.

Проведем прямую 2x 1 + 3x 2 = Сonst (линию уровня) так, чтобы она пересекала многоугольник AFEDCB (например, Const=10). Эта линия уровня на рисунке изображена пунктирной линией.

Если рассматривать значения линейной целевой функции Z на множестве точек (x 1 ,x 2), принадлежащих отрезку пунктирной прямой, расположенному внутри шестиугольника, то все они равны одному и тому же значению (Const=10).

Определим направление возрастания функции. Для этого построим линию уровня с бОльшим значением. Это будет прямая, параллельная с построенной, но расположенная правее. Значит, в заданном направлении значение целевой функции возрастает, и в наших интересах сдвинуть ее как можно дальше в этом направлении.

Сдвиг можно продолжать до тех пор, пока перемещаемая прямая пересекает многоугольник допустимых решений. Последнее положение прямой, когда она имеет одну общую точку с многоугольником AFEDCB (точка С), соответствует максимальному значению целевой функции Z и достигается в точке С с координатами x 1 = 4/3 (» 1.333), x 2 =10/3 (» 3.333). При этом Z = 38/3 (» 12.667).

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

Первое . Область допустимых решений – выпуклый многоугольник (Почему выпуклый? Может ли область допустимых решений представлять собой пустое множество? Точку? Отрезок? Луч? Прямую? Если да, приведите пример системы ограничений ).

Второе . Максимум целевой функции достигается в вершине многоугольника допустимых решений (а может ли быть не единственное решение? Может ли решения не быть? )

Задание 1 (выполнить на занятии, показать преподавателю)

Решить графическим методом

А) F =2 x 1 +3 x 2 è max При ограничениях x 1 +3 x 2 ≤ 18 2 x 1 + x 2 ≤ 16 x 2 ≤ 5 3 x 1 ≤ 21 x 1 ≥ 0 x 2 ≥ 0	B ) F =4 x 1 +6 x 2 è min При ограничениях 3 x 1 + x 2 ≥ 9 x 1 +2 x 2 ≥ 8 x 1 +6x 2 ≥ 12 x 1 ≥ 0 x 2 ≥ 0
C ) F =3 x 1 +3 x 2 è max При ограничениях x 1 +x 2 ≤ 8 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 2 x 1 ≥ 0 x 2 ≥ 0	D ) F =2 x 1 -3 x 2 è min При ограничениях x 1 +x 2 ≥ 4 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 1 x 1 ≥ 0 x 2 ≥ 0

A) x1=6 x2=4 F=24

B) x1=2 x2=3 F=26

C) x1Î x2=8-x1 F=24

Задание 2 (выполнить на занятии, показать преподавателю)

Ответить на вопросы, выделенные курсивом.

Задание 3 (домашнее)

Написать программу.

Дан текстовый файл вида

2 3 (коэффициенты целевой функции)

4 (количество ограничений)

2 2 12 (ограничения)

1 2 8

4 0 16

0 4 12

Построить прямые так, чтобы многоугольник допустимых решений был целиком на экране (определение масштаба см. в кн. Онегова). Прямые могут быть параллельны осям!

Построить несколько линий уровня целевой функции (нажимаем клавишу – прямая перемещается, отображается значение целевой функции). Отобразить масштаб.

Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи ЛП определяет на координатной плоскости (х 1 ,х 2 ) некоторую полуплоскость (рис. 1), а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена, выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

Примечание № 1. Все вышесказанное относится и к случаю, когда система ограничений (1.1) включает равенства, поскольку любое равенство

a il x 1 +a i 2 x 2 =b

можно представить в виде системы двух неравенств (рис. 1)

A i 2 x 2 <Ь 1э +a i 2 x 2 >bj.

ЦФ L(x)= с1х1 + с2х2 при фиксированном значении L(х)=L определяет на плоскости прямую линию с1х1 + с2х2 = L. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси х2 (начальная ордината), а угловой коэффициент прямой tgа = -- останется постоянным (рис. 1).

Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор C = (c1;c2) с координатами из коэффициентов ЦФ при х1 и х2 перпендикулярен к каждой из линий уровня (см. рис. 1). Направление вектора С совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора С.

Суть графического метода заключается в следующем. По направлению (против направления) вектора С в ОДР производится поиск оптимальной точки X = (х1; х2). Оптимальной считается точка, через которую проходит линия уровня L max (L min), соответствующая наибольшему (наименьшему) значению функции L(x). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.

Допустимая область - полуплоскость

Рисунок 1

1.2. Методика решения задач лп графическим методом

I. Вограничениях задачи замените знаки неравенств на знаки точных равенств и постройте соответствующие прямые.

II. Найдите и заштрихуйте полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого подставьте в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверьте истинность полученного неравенства.

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

Поскольку х1 и х2 должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси х 1 и правее оси х2, т.е. в 1-м квадранте.

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

Определите ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделите ее. При отсутствии ОДР задача не имеет решений, о чем сделайте соответствующий вывод.

Если ОДР - не пустое множество, то постройте целевую прямую, т.е. любую из линий уровня с 1 х 1 + с 2 х 2 = L, где L - произвольное число, например, кратное с 1 и с 2 , т.е. удобное для проведения расчетов. Способ построения аналогичен построению прямых ограничений.

V. Постройте вектор C = (c 1 ,с 2), который начинается в точке (0;0), заканчивается в точке (c 1 ,с 2). Если целевая прямая и вектор С построены верно, то они будут перпендикулярны.

VI. При поиске max ЦФ передвигайте целевую прямую в направлении вектора С, при поиске min ЦФ - против направления вектора С. Последняя по ходу движения вершина ОДР будет точкой max или min ЦФ. Если такой точки (точек) не существует, то сделайте вывод о неограниченности ЦФ на множестве планов сверху (при поиске шах) или снизу (при поиске min).

Определите координаты точки max (min) ЦФ X = (х1 * ; х2 * ) и вычислите значение ЦФ l(x *). Для вычисления координат оптимальной точки X * решите систему уравнений прямых, на пересечении которых находится X * .

Задача 1

Найдем оптимальное решение задачи, математическая модель которой имеет вид

L(Х) = 3x 1 + 2x 2 → max

х 1 + 2х 2 < 6, (1)

2х 1 + х 2 < 8, (2)

Х 1 +х 2 <1, (3)

х 2 < 2, (4)

х 1 >0,х 2 >0.

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис. 2).

х 1 + 2х 2 = 6,(1)

2х1 + х2= 8,(2)

(1) х1=0, х1=6, х2=3, х2=0,

(2) х1=0, х1=4, х2=8, х2=0,

(3) х1=0, х1=-1, х2=1, х2=0,

Прямая (4) проходит через точку х 2 = 2 параллельно оси L(Х).

Рис. 2. Графическое решение задачи

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (3), получим 0 < 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (рис. 2). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDEF.

Целевую прямую можно построить по уравнению

Строим вектор С из точки (0;0) в точку (3;2). Точка Е- это последняя вершина многоугольника допустимых решений ABCDEF, через которую проходит целевая прямая, двигаясь по направлению вектора С. Поэтому Е -это точка максимума ЦФ. Определим координаты точки Е из системы уравнений прямых ограничений (1) и (2)

Х1 +2х 2 =6, (1) х1=10/3=3 1/3, х2=4/3=1 1/3

2 Х1 +х 2 =8, (2) Е 3 1/3; 1 1/3

Максимальное значение ЦФ равно L(E) = 3*10/3+2*4/3 = 12 2 / 3