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

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

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

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

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

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

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

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

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

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

Линейная форма графически означает семейство параллельных между собой прямых. При конкретном числовом значении F линейная форма изобразится в виде некоторой прямой. Каждую из прямых этого семейства принято называть линией уровня. На рисунке построена линия уровня (чёрного цвета, проходит через начало координат), соответствующая значению F =0.

Если исходную линию уровня передвигать вправо, то значение F при этом возрастает. Нужное направление движения исходной линии уровня можно установить следующим образом. Коэффициенты при переменных в уравнении прямой служат координатами вектора, перпендикулярного этой прямой. Таким образом, получаем градиент — вектор (на рисунке бордового цвета). Значения функции F возрастают при перемещении исходной линии уровня в направлении вектора .

Среди прямых упомянутого семейства параллельных прямых прямые mn (зелёного цвета) и MN (красного цвета), которые назовём опорными. Опорными обычно называют такие прямые, которые имеют с многоугольником ABCDE хотя бы одну общую точку, и многоугольник ABCDE целиком лежит по одну сторону от этой прямой. Как видно из чертежа, прямая mn является опорной, так как она касается многоугольника в точке A и многоугольник целиком лежит правее (или выше) этой прямой. Прямая MN также является опорной, так как имеет с многоугольником общую точку С и многоугольник целиком лежит левее этой прямой.

Из основных теорем линейного программирования известно, что линейная форма достигает максимального и минимального значений в крайних точках многогранника решений. Это значит, что опорные прямые mn и MN характеризуют экстремальные значения линейной формы (функции цели), то есть в точках А и С линейная форма достигает оптимальных значений. В точке А, находящейся ближе к началу координат, функция цели достигает минимального значения, а в точке С, находящейся дальше от начала координат, — максимального значения.

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

1. Построить многоугольник решений системы неравенств.

2. Начертить из семейства прямых, соответствующих линейной форме, линию равных значений функции цели. Для построения линии равных значений придадим F некоторое числовое значение. Во многих задачах удобно принять, что F =1. Тогда получим . Запишем это уравнение прямой в отрезках:

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

3. Двигать прямую (или линейку) вдоль градиента — вектора параллельно линии равных значений в сторону многоугольника решений до соприкосновения с многоугольником решений. Если первая встреча с многоугольником решений произойдёт в крайней точке с координатами , то в этой точке функция цели достигает минимального значения. Если первая встреча произойдёт со стороной многоугольника, то данная функция цели достигает минимума во всех точках этой стороны.

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

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

Примеры решения задач графическим методом

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

Построим многоугольник решений. Для этого начертим граничные прямые. Из первого неравенства запишем уравнение . Это уравнение первой граничной прямой. Найдём точки пересечения этой прямой с осями координат. При из уравнения получим , при получим . Это значит, что первая прямая отсекает от осей координат отрезки и .

Аналогично строим остальные граничные прямые. Вторая прямая от осей координат отсекает отрезки, равные 6. Третья прямая проходит параллельно оси , отсекая на оси отрезок, равный 2. Четвёртая прямая имеет уравнение . Она совпадает с осью .

Из рисунка ниже видно, что множество точек четырёхугольника ABDE удовлетворяет всем четырём неравенствам системы.

Следовательно, четырёхугольник ABDE является многоугольником решений системы (заштрихован вовнутрь).

Начертим линию равных значений функции цели. Приняв в равенстве F =1, получим, что эта линия отсекает отрезки 1 и 1/3 соответственно на оси и на оси . Проведём прямую через эти точки (на чертеже она чёрного цвета).

Двигая эту прямую параллельно самой себе в направлении градиента — вектора (бордового цвета), получим опорные прямые. Первая прямая (зелёного цвета) имеет с многоугольником общую точку A. Здесь функция цели достигает минимума. Двигаясь дальше, придём к точке В. Здесь максимум. Координаты точки В: (2, 4). Подставляя в функцию цели координаты точки В, т. е. , , получим максимальное значение функции цели: .

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

Решение. Многогранником решений является открытая область

Проведём линию равных значений функции цели при F =1, как в предыдущем примере (она опять чёрного цвета).

Из рисунка видно, что прямая ближайшнее от начала координат опорное положение займёт в точке В. Следовательно, в этой точке функция цели имеет минимум. Координаты точки В: (2, 2). Подставляя в функцию цели и , получим минимальное значение функции: .

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

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

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

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

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

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

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

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

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

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

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

Решение. Всем неравенствам системы ограничений удовлетворяют точки треугольника ABC, который и является областью решений. За исходную линию уровня взята прямая (на рисунке ниже — чёрного цвета), с тем чтобы она пересекала область решений. Как видно из рисунка, максимальное значение F = 8 достигается в точке С(8; 0) . При построении треугольника ABC не была использована прямая , соответствующая первому неравенству, хотя все точки треугольника удовлетворяют этому неравенству. Таким образом, этот пример отличается от предыдущих тем, что одно из неравенств системы ограничений оказалось лишним.

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

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

Все точки отрезка CD дают одно и то же значение функции цели, которое и служит её оптимальным значением: . Следовательно, имеется не одно, а бесчисленное множество оптимальных решений, совпадающих с точками отрезка CD, в частности, с двумя угловыми точками C и D. Этот пример показывает, что в некоторых случаях единственность оптимального решения нарушается.

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

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

1. Долгополова А. Особенности применения методов математического моделирования в экономических исследованиях / А.Ф. Долгополова, Т.А. Гулай, Д.Б. Литвин // Кант: экономика и управление. – 2013. – №1. – С. 62-66.

2. Долгополова А.Ф. Перспективы применения математических методов в экономических исследованиях / А.Ф. Долгополова, Т.А. Гулай, Д.Б. Литвин // Аграрная наука, творчество, рост: сб. науч. тр. – Ставрополь: CтГАУ, 2013. – С. 255-257.

3. Гулай Т.А. Совершенствование профессиональной подготовки экономистов через направленность содержания математического образования / Т.А. Гулай, А.Ф. Долгополова, Д.Б. Литвин // Аграрная наука, творчество, рост: сб. науч. тр. – Ставрополь: CтГАУ, 2013. – С. 252-254.

4. Гулай Т.А. Использование математических методов для анализа динамических свойств управляемого объекта / Т.А. Гулай, А.Ф. Долгополова, Д.Б. Литвин // Моделирование производственных процессов и развитие информационных систем: сб. науч. тр. – Ставрополь: CтГАУ, 2012. – С. 167-170.

5. Гулай Т.А. Личностно-ориентированное обучение математики студентов экономических направлений как средство повышения качества обучения / Т.А. Гулай, А.Ф. Долгополова, Д.Б. Литвин // Теоретические и прикладные проблемы современной педагогики: сб. науч. тр. – Ставрополь: CтГАУ, 2013. – С. 28-33.

6. Гулай Т.А. Руководство к решению задач по математическому анализу. Часть 1 / А.Ф. Долгополова, Т.А. Колодяжная // Международный журнал экспериментального образования. – 2011. – №12. – С. 62-63.

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

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

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

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

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

Пусть x и y – количество выпускаемых мониторов и мышек. Тогда следует, что общая прибыль от продажи всей продукции составит Z = 4X + 7Y → max. При этом общий расход обшивки равен 3x + 2y и он не должен быть больше имеющегося запаса 27. Таким образом они ограничиваются 3x + 2y ≤ 27. Так же учитываются ограничения по USB проводу и материнской плате: 2x + 4y ≤ 28, 2x + 3y ≤ 23. Следовательно, если объем больше нуля, то x ≥ 0, y ≥ 0. Тогда математическая модель задачи имеет вид:

Таким образом, цель данной задачи состоит в том, чтобы найти положительные значения x ≥ 0, y ≥ 0, где Z принимает наивысшее значения.

Для начала составим ОДР, затем найдем Zmax. Начнем решение задачи с геометрического представления ОДР. Уравнение x ≥ 0, y ≥ 0 ограничивают ОДР 1 четвертью. Система уравнений составляет на координатной плоскости xOy некоторую полуплоскость. Найдем полуплоскости на которых выполняются эти уравнения. Для этого нужно просто взять некую произвольную точку, через которую не проходит граничная прямая и проверить, удовлетворяет ли данная точка уравнению. Если данная точка подходит,то это уравнение выполняется на полуплоскости, на которой находится произвольная точка. В обратном случае берется полуплоскость, на которой не находится произвольная точка. Берем в качестве произвольной точки начало координат О (0;0). Обратим внимание, что при построении ОДР систему уравнений удобнее выражать в отрезках.

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

Составим геометрическую интерпретацию уравнения Z = 4X + 7Y →max.

Уравнение Z = C1X + C2Y = 4X + 7Y , при значении Z = Z1, то Z1 = 4X + 7Y. Если изменить значение Z, то получим семейство параллельных прямых, называемых линями уровня. C̄ = (С1; С2) перпендикулярен каждой из линий уровня.

Вектор C показывает направление наивысшего возрастания уравнения. Перпендикулярно к вектору С нужно провести линию уровня Z = 0. Параллельно перенесем прямую Z = 0 и найдем крайнюю точку, где Z = 4X + 7Y достигает максимума (pис. 2).

Из-за то, что точка U находится на пересечении прямых 2 и 3, координаты U определяются системой

где U (4, 5), Zmax = Z (U)= 4×4 + 7×5 = 51. Этот способ решения задачи называется графическим.

Ответ: необходимо выпускать 4 монитора и 5 мышек, тогда прибыль составит 51 денежных единиц.

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

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

Существуют два наиболее распространенных способа решения задач линейного программирования (ЗЛП): графический метод и симплекс-метод. Графический метод существенно нагляднее и обычно проще для понимания и решения (хотя занимает много времени, так как требует тщательного построения чертежа). Также этот метод позволяет практически одновременно найти решение на минимум и максимум, тогда как симплекс-методом придется делать «два подхода».

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

А за конкретикой — к примерам ниже: вы найдете там решенные графическим способом задачи линейного программирования. Примеры решений выложены бесплатно для вашего удобства — изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении заданий по методам оптимальных решений, перейдите в раздел: Решение задач ЛП на заказ (решаем для студентов очников и заочников).

Полезная страница? Сохрани или расскажи друзьям

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

Задача 1. Колхоз имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика — 4000 руб., пятитонного — 5000 руб. Колхоз может выделить для приобретения автомашин 141 тысяч рублей. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?
Задачу решить графическими и аналитическими методами.

Решение ЗЛП графическим и аналитическим методом (pdf, 156 Кб)

Задача 2. Решить задачу графическим методом на минимум и на максимум

Решение ЗЛП графическим методом (pdf, 164 Кб)

Задача 3. Решить задачу графическим методом на минимум и на максимум

Задача 4. Среди чисел x и y, удовлетворяющих условиям

найти такие, при которых разность этих чисел y-x принимает наибольшее значение.

Задача 5. Решить графическим методом ЗЛП, заданную указанной математической моделью.

Решение ЗЛП графическим методом (pdf, 151 Кб)

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

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

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

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

• Шаг №1
• Шаг №2
• Видеоинструкция
• Оформление Word
• Также решают

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

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

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

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

Целевая функция принимает экстремальное (минимальное или максимальное) значение в единственной точке А.

Сырье	Расход сырья на 1 ед. продукции		Максимальный запас сырья, ед.
	П1	П2
М1	6	4	24
М2	1	2	6

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

Если количество переменных в задаче линейного программирования больше двух, то задачу предварительно сводят к стандартной ЗЛП.
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅ → max при ограничениях:
x₁ + x₂ + x₃=12
2x₁ — x₂ + x₄=8
— 2x₁ + 2x₂ + x₅=10
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₃.
2. В качестве базовой переменной можно выбрать x₄.
3. В качестве базовой переменной можно выбрать x₅.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x₁ + x₂ + x₃ = 12
2x₁ — x₂ + x₄ = 8
— 2x₁ + 2x₂ + x₅ = 10
Выразим базисные переменные через остальные:
x₃ = — x₁ — x₂+12
x₄ = — 2x₁ + x₂+8
x₅ = 2x₁ — 2x₂+10
Подставим их в целевую функцию:
F(X) = 3x₁ — 2x₂ + 5(- x₁ — x₂+12) — 4(2x₁ — 2x₂+10)
или
F(X) = — 10x₁ + x₂+20 → max
Система неравенств:
— x₁ — x₂+12 ≥ 0
— 2x₁ + x₂+8 ≥ 0
2x₁ — 2x₂+10 ≥ 0
Приводим систему неравенств к следующему виду:
x₁ + x₂ ≤ 12
2x₁ — x₂ ≤ 8
— 2x₁ + 2x₂ ≤ 10
F(X) = — 10x₁ + x₂+20 → max

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

Пример №1 . Записать задачу в стандартной форме и решить ее графическим методом.

Переменную x₂ принимаем в качестве дополнительной переменной и делаем замену на знак «≥»:
f=x₁ + 6x₃+ 27
x₁ + 3x₃≥6

Далее задача решается графическом способом.

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₃.
2. В качестве базовой переменной можно выбрать x₄.
3. В качестве базовой переменной можно выбрать x₅.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x₁ + x₂ + x₃ = 12
2x₁ — x₂ + x₄ = 8
— 2x₁ + 2x₂ + x₅ = 10
Выразим базисные переменные через остальные:
x₃ = — x₁ — x₂+12
x₄ = — 2x₁ + x₂+8
x₅ = 2x₁ — 2x₂+10
Подставим их в целевую функцию:
F(X) = 3x₁ — 2x₂ + 5(- x₁ — x₂+12) — 4(2x₁ — 2x₂+10)
или
F(X) = — 10x₁ + x₂+20 → max
Система неравенств:
— x₁ — x₂+12 ≥ 0
— 2x₁ + x₂+8 ≥ 0
2x₁ — 2x₂+10 ≥ 0
Приводим систему неравенств к следующему виду:
x₁ + x₂ ≤ 12
2x₁ — x₂ ≤ 8
— 2x₁ + 2x₂ ≤ 10
F(X) = — 10x₁ + x₂+20 → max

• Составить систему математических зависимостей (неравенств) и целевую функцию.
• Изобразить геометрическую интерпретацию задачи.
• Найти оптимальное решение.
• Провести аналитическую проверку.
• Определить существенные и несущественные ресурсы и их избытки.
• Определить значение целевой функции.
• Вычислить объективно обусловленные оценки.
• Составить соотношение устойчивости.

Наимен. показат.	Нормы на одно изделие			Прибыль на одно изделие
	Рес. 1	Рес. 2	Рес. 3
Изделие 1	10.0	14.0	3.8	40
Изделие 2	22.0	7.5	14.5	75
Наличие ресурсов	450	310	360	—