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

Геометрический метод решения ЗЛП

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

Каждое из неравенств системы ограничений геометрически определяет полуплоскость допустимых значений переменных с граничными прямыми.

Алгоритм геометрического метода:

1. В системе ограничений знаки неравенств заменяются на знаки точных равенств и по полученным уравнениям строятся прямые на плоскости x₁Ox₂.

2. Определяются полуплоскости – области решения неравенств, и строится многоугольник решений (ОДР), который получается в результате пересечения полуплоскостей. Стороны этого многоугольника являются прямыми уравнений системы ограничений.

4. Из точки (0; 0) строится вектор , направление которого определяет направление возрастания целевой функции c₁x₁ + c₂x₂.

5. Строится начальная прямая (линия нулевого уровня) целевой функции c₁x₁ + c₂x₂ = 0, которую передвигают в направлении вектора до крайней угловой точки многоугольника решений. В этой точке целевая функция принимает max значение.

6. Определяются координаты точки максимума целевой функции как точки пересечения соответствующих прямых и вычисляется значение целевой функции в этой точке .

В нашем случае система уравнений будет иметь вид:

Построим по полученным уравнениям прямые и пронумеруем их (рис.1). Областью ОДР будет выпуклый многоугольник АBCDEF, каждая вершина которого является опорным планом. Из точки (0; 0) строим вектор . Начальная линия уровня будет иметь вид: 4x₁ + 3x₂ = 0. Перемещая линию уровня вдоль вектора , получим, что функция F принимает max значение в точке D – самой крайней справа вершине многоугольника ОДР. Точка D является точкой пересечения прямых (2) и (3). Находим координаты точки D, решая систему уравнений этих прямых:

.

Решением системы будут значения x₁ = 9, x₂ = 6, т.е. D(9; 6). Тогда

Рис. 1. Иллюстрация геометрического метода решения ЗЛП

Таким образом, решением задачи будет оптимальный план , дающий max значение функции 54 у.е. Максимальная прибыль 54 у.е. достигается при изготовлении 9 единиц изделий I вида и 6 единиц изделий II вида.

В данной задаче ОДР является выпуклый многоугольник. Однако возможны и следующие случаи:

1) ОДР – пустое множество (рис.2, а). В этом случае задача линейного программирования не имеет решения из-за несовместности системы ограничений.

2) ОДР – единственная точка, которая и будет единственным и оптимальным решением (рис.2, б).

3) ОДР – выпуклая неограниченная область (рис.2, в). В задаче на max оптимальное решение не существует, если целевая функция не ограничена сверху (F_max = ∞). В задаче на min оптимальное решение не существует, если целевая функция не ограничена снизу (F_min = –∞).

4) Может оказаться, что линия уровня функции F совпадает с одной из сторон многоугольника ОДР (экстремум целевой функции достигается на всем отрезке между двумя соседними вершинами ОДР) (рис.3). Тогда имеет место альтернативный оптимум: , где t є [0; 1] – параметр.

Рис. 3. Альтернативный оптимум

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

Существуют три формы записи ЗЛП: каноническая, стандартная, общая.

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

Графический (геометрический) метод решения задач ЛП

Пример 6.1. Решить следующую задачу ли-нейного программирования геометрическим методом:

.

Решение:

Задача линейного программирования задана в стандартной форме и имеет два проектных параметра, следовательно

, воз-можно ее решение геометрическим методом.

1 этап: построение прямых, ограничивающих область допустимых решений ( ОДР).

Рассмотрим систему ограничений задачи линейного програм-мирования (для удобства пронумеруем неравенства):

Рассмотрим первое ограничение, заменим знак неравенства знаком равенства и выразим переменную х2 через х1:

.

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

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

2 этап: определение решения каждого из нера-венств системы ограничений.

Определим полуплоскости – решения каждого из неравенств.

Рассмотрим первое неравенство системы ограничений задачи. Возьмем какую-либо точку (контрольную точку), не принадлежащую соответствующей данному неравенству прямой, например, точку (0; 0). Подставим ее в рассматриваемое неравенство:

.

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

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

3 этап: определение ОДР задачи линейного про- граммирования.

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

Рис. 1. Область допустимых решений задачи

4 этап: построение вектора-градиента.
Вектор-градиент показывает направление максимизации целевой функции . Определим его координаты: координаты начальной его точки (точки приложения) – (0; 0), координаты второй точки:

Построим данный вектор на графике (рис. 2).

5 этап: построение прямой целевой функ-ции.

Рассмотрим целевую функцию данной задачи:

.

Зададим ей какое-либо значение, к примеру, . Выразим переменную х2 через х1:

.

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

Построим прямую соответствующую целевой функции (рис. 2).

Рис. 2. Построение целевой функции F(X) и вектора-градиента С

6 этап: определение максимума целевой функ-ции.

Перемещая прямую F(X) параллельно са-мой себе по направлению вектора-градиента, определяем крайнюю точку (точки) ОДР. Согласно графику (рис. 3), такой точкой является точка С ­– точка пересечения прямых I и II.

Рис. 3. Определение точки максимума целевой функции F(X)

Определим координаты точки С, с этой целью, решим сле-дующую систему линейных уравнений:

Подставим найденные координаты в целевую функцию и найдем ее оптимальное (максимальное) значение:

Ответ: при заданных ограничениях макси-мальное значение целевой функции F(Х)=24, которое достигается в точке С, координаты которой х1=6, х2=4.

Пример 6.2. Решить задачу линейного про- граммирования геометрическим методом:

Решение:

Этапы 1-3 аналогичны соответствующим этапам предыдущей задачи.
4 этап: построение вектора-градиента.
Построение вектора-градиента осуществляется аналогично, как и в предыдущей задаче. Построим данный вектор на графике (рис. 4). Отметим также на данном графике стрелкой направление, обратное вектору-градиенту, – направление минимизации целевой функцииF (X).

5 этап: построение прямой целевой функ-ции.

Построение прямой целевой функции F(X) осуществляется аналогично, как и в предыдущей задаче (результат построения приведен на рис. 4).

Рис. 4. Построение целевой функции F(x) и вектора-градиента С

6 этап: определение оптимума целевой функ-ции.

Перемещая прямую F(x) параллельно са-мой себе в направлении, обратном вектору-градиенту, опреде-ляем крайнюю точку (точки) ОДР. Согласно графику (рис. 5), та- кой точкой является точка О с координатами (0; 0).

Рис. 5. Определение точки минимума целевой функции

Подставляя координаты точки минимума в целевую функ-цию, определяем ее оптимальное (минимальное) значение, которое равно 0.
Ответ: при заданных ограничениях минимальное значение целевой функции F(Х)=0, которое достигается в точке О (0; 0).

Пример 6.3. Решить следующую задачу ли-нейного программирования геометрическим методом:

Решение:

Рассматриваемая задача линейного программирования задана в канонической форме, выделим в качестве базисных переменные x 1 и x2.

Составим расширенную матрицу и выделим с помощью метода Жордана- Гаусса базисные переменныеx1 и x 2.

Умножим (поэлементно) первую строку на –3 и сложим со вто-рой:
.

Умножим вторую строку на :

.

Сложим вторую с первой строкой:

.

В результате система ограничений примет следующий вид:

Выразим базисные переменные через свободные:

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

.

Запишем полученную задачу линейного программирования:

Так как переменные x1 и x2 неотрицательные, то полученную систему ограничений можно записать в следующем виде:

Тогда исходную задачу можно записать в виде следующей эк- вивалентной ей стандартной задаче линейного программирования:

Данная задача имеет два проектных параметра, следовательно, возможно ее решение геометрическим мето-дом.

1 этап: построение прямых, ограничивающих область допустимых решений ( ОДР).

Рассмотрим систему ограничений задачи линейного програм-мирования (для удобства пронумеруем неравенства):

Построим прямые, соответствующие каждому неравенству (рис. 6). Прямые пронумеруем согласно принятой ранее схе-ме.

2 этап: определение решения каждого из нера-венств системы ограничений.

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

3 этап: определение ОДР задачи линейного про- граммирования.

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

Рис. 6. Фрагмент MathCAD-документа:

построение области допустимых решений задачи

Ответ: рассматриваемая задача линейного программирования не имеет решения в силу несовместности системы ограничений.

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

Направление, обратное вектору-градиенту, соответствует направлению минимизации целевой функции.

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

Геометрический метод решения ЗЛП – простой и наглядный способ решения стандартных ЗЛП с двумя переменными:

(18)

(19)

Рассмотрим следующие геометрические объекты.

Выпуклые множества и их свойства.

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

Справедливо утверждение: пересечение любого числа выпуклых множеств есть выпуклое множество.

Каждое неравенство системы ограничений (19) геометрически определяет полуплоскость с граничной прямой , или , или .

Поясним сказанное. Рассмотрим, например, неравенство .

Посмотрим прямую L: (см. рис.2).

Для того чтобы определить, какая полуплоскость удовлетворяет заданному неравенству, необходимо выбрать любую точку, не лежащую на L, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением, и полуплоскость, содержащая точку, удовлетворяет неравенству. Как правило, в качестве «пробной» берут точку .

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

Полуплоскости, описываемые неравенствами (19) – выпуклые множества. Их пересечение – область допустимых решений ЗЛП, которая является также выпуклым множеством.

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

Ввиду неравенств и многоугольник решений всегда находится в первом квадранте координатной плоскости .

Для нахождения экстремума целевой функции F воспользуемся вектором набла — градиентом F:

.

Он показывает направление наискорейшего изменения целевой функции F.

Прямая называется линией уровня функции F. Иными словами на множестве всех точек линии уровня функции F она сохраняет постоянное значение .

Алгоритм решения ЗЛП геометрическим методом.

1. Строится многоугольник решений.

2. Строится вектор набла, перпендикулярно ему проводятся линии уровня и при этом учитывают, что оптимальное решение ЗЛП находится в угловой точке многоугольника решений.

3. Первая точка встречи линии уровня с многоугольником решений определяет минимум целевой функции.

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

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

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

Пример 1. Экономико-математическая модель задачи о планировании производства.

Построим многоугольник решений. С этой целью запишем уравнения границ полуплоскостей из (17) в виде

или

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

Построим вектор набла . Последней точкой встречи линии уровня с многоугольником решений будет точка (см. рис.3) с координатами: , , являющимися решениями системы уравнений

Подставив координаты точки в целевую функцию, найдем

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

Построим многоугольник решений. С этой целью запишем уравнения границ полуплоскостей из (17) в виде

или

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

Построим вектор набла . Первой точкой встречи линии уровня с многоугольником решений будет точка (см. рис. 4) с координатами: , , являющимися решениями системы уравнений:

Подставив координаты точки в целевую функцию, найдем

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

Геометрический метод – самый простой и наглядный методрешения задач линейного программирования. Он позволяет быстро и легко получить ответ. Но к сожалению, он имеет недостатки, не позволяющие применять его широко:

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

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

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

Рассмотрим геометрический метод решения на примере. Пусть нам нужно решить следующую задачу: найти максимум функции F=2x₁-6x₂ при ограничениях:

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

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

Из множества точек ABCD нужно выбрать такую точку, для которой значение целевой функции F=2x₁-6x₂будет наибольшим. Заметим, что графиком целевой функции будет прямая, перпендикулярная вектору , расположенная тем дальше от начала координат, чем больше значение F. Отсюда следует, что максимальное значение целевой функции будет достигаться в одной из угловых точек, а именно в той, через которую проходит прямая, перпендикулярная вектору и находящаяся на наибольшем удалении от начала координат в направлении вектора . В данном случае это точка D(8,0). В этой точке достигается оптимальное (максимальное) значение целевой функции F=2x₁-6x₂=16.

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

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

1. оптимальное решение единственно. Прямая F=F_max имеет одну общую точку с ОДР ( рис.2, F – достигает максимума в точке С );

2. оптимальных решений бесконечное множество. Прямая F=F_max совпадает с одной из прямых ограничений. В этом случае каждая точка этой прямой является оптимальным решением ( рис.3, F – достигает максимума в каждой точке отрезка ВС);

3. оптимального решения не существует по причине неограниченности целевой функции ( рис.4 );

4. оптимального решения не существует по причине противоречивости системы ограничений ( ОДР является пустым множеством ) (рис 5).

Если мы перефразируем свойства задач линейного программирования для данного метода, то получим:

1. оптимальное решение, если оно существует, лежит на границе ОДР;

2. если решение единственно, то оно достигается в одной из вершин ОДР;

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

4. решение, лежащее в одной из вершин ОДР, является опорным, а сама вершина – опорной точкой.

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

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

Описание метода

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1) ;
(1.2)
Здесь , есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки , так и знаки .

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

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

Так, первое неравенство
(1.2.1)
определяет полуплоскость, ограниченную прямой . С одной стороны от этой прямой , а с другой стороны . На самой прямой . Чтобы узнать, с какой стороны выполняется неравенство (1.2.1), мы выбираем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1). Если неравенство выполняется, то полуплоскость содержит выбранную точку. Если неравенство не выполняется, то полуплоскость расположена с другой стороны (не содержит выбранную точку). Заштриховываем полуплоскость, для которой выполняется неравенство (1.2.1).

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

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

Можно упростить метод. Можно не заштриховывать каждую полуплоскость, а вначале построить все прямые
(2)
Далее выбрать произвольную точку, не принадлежащую ни одной из этих прямых. Подставить координаты этой точки в систему неравенств (1.2). Если все неравенства выполняются, то область допустимых решений ограничена построенными прямыми и включает в себя выбранную точку. Заштриховываем область допустимых решений по границам прямых так, чтобы оно включало в себя выбранную точку.

Если хотя бы одно неравенство не выполняется, то выбираем другую точку. И так далее, пока не будет найдены одна точка, координаты которой удовлетворяют системе (1.2).

Нахождение экстремума целевой функции

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

Теперь мы можем искать экстремум целевой функции
(1.1) .

Для этого выбираем любое число и строим прямую
(3) .
Для удобства дальнейшего изложения считаем, что эта прямая проходит через ОДР. На этой прямой целевая функция постоянна и равна . такая прямая называется линией уровня функции . Эта прямая разбивает плоскость на две полуплоскости. На одной полуплоскости
.
На другой полуплоскости
.
То есть с одной стороны от прямой (3) целевая функция возрастает. И чем дальше мы отодвинем точку от прямой (3), тем больше будет значение . С другой стороны от прямой (3) целевая функция убывает. И чем дальше мы отодвинем точку от прямой (3) в другую сторону, тем меньше будет значение . Если мы проведем прямую, параллельную прямой (3), то новая прямая также будет линией уровня целевой функции, но с другим значением .

Таким образом, чтобы найти максимальное значение целевой функции, надо провести прямую, параллельную прямой (3), максимально удаленную от нее в сторону возрастания значений , и проходящую хотя бы через одну точку ОДР. Чтобы найти минимальное значение целевой функции, надо провести прямую, параллельную прямой (3) и максимально удаленную от нее в сторону убывания значений , и проходящую хотя бы через одну точку ОДР.

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

Рассмотрим случай, когда крайняя прямая, параллельная произвольной прямой вида (3), проходит через одну вершину многоугольника ОДР. Из графика определяем координаты этой вершины. Тогда максимальное (минимальное) значение целевой функции определяется по формуле:
.
Решением задачи является
.

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

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

Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида — 10 м, третьего вида — 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В — 300 ден. ед.

Составить план производства, обеспечивающий фирме наибольший доход. Задачу решить графическим методом.

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

Тогда экономико-математическая модель задачи имеет вид:

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (8; 0).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.

Строим произвольную линию уровня целевой функции, например,
(П1.1) .
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).

Далее замечаем, что поскольку коэффициенты при и целевой функции положительны (400 и 300), то она возрастает при увеличении и . Проводим прямую, параллельную прямой (П1.1), максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку четырехугольника OABC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.

Пример 2

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

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).

Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).

Строим прямую .
Строим прямую (ось абсцисс).

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

Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.

Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и , то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Пример отсутствия решения

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

Решаем задачу графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (2,667; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.

Строим произвольную линию уровня целевой функции, например,
(П3.1) .
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .

Чтобы найти максимум, нужно провести параллельную прямую, максимально удаленную в сторону возрастания , и проходящую хотя бы через одну точку области ABCDE. Однако, поскольку область неограниченна со стороны больших значений и , то такую прямую провести нельзя. Какую бы прямую мы не провели, всегда найдутся точки области, более удаленные в сторону увеличения и . Поэтому максимума не существует. можно сделать сколь угодно большой.

Ищем минимум. Проводим прямую, параллельную прямой (П3.1) и максимально удаленную от нее в сторону убывания , и проходящую хотя бы через одну точку области ABCDE. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Максимального значения не существует.
Минимальное значение
.

Автор: Олег Одинцов . Опубликовано: 08-08-2016