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

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

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

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

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

Построить область допустимого решения (ОДР) можно также с помощью этого сервиса.

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

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

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

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

  2. Целевая функция принимает экстремальное значение в любой точке отрезка АВ.
  3. Целевая функция не ограничена сверху (при поиске на максимум) или снизу (на минимум)
  4. Система ограничений задачи несовместна

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

Таблица — Расход сырья на производство продукции

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

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

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

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

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

x1 – производство продукции П1, ед.

x2 – производство продукции П2, ед.
x1, x2 ≥ 0

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

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

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

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

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

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

F(X) = 3×1 — 2×2 + 5×3 — 4×5 → max при ограничениях:
x1 + x2 + x3=12
2×1 — x2 + x4=8
— 2×1 + 2×2 + x5=10
F(X) = 3×1 — 2×2 + 5×3 — 4×5
Переход к СЗЛП.

Расширенная матрица системы ограничений-равенств данной задачи: Приведем систему к единичной матрице методом жордановских преобразований.

1. В качестве базовой переменной можно выбрать x3.

2. В качестве базовой переменной можно выбрать x4.
3. В качестве базовой переменной можно выбрать x5.Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).Соответствующие уравнения имеют вид:

x1 + x2 + x3 = 12

2×1 — x2 + x4 = 8
— 2×1 + 2×2 + x5 = 10Выразим базисные переменные через остальные:

x3 = — x1 — x2+12

x4 = — 2×1 + x2+8
x5 = 2×1 — 2×2+10Подставим их в целевую функцию:

F(X) = 3×1 — 2×2 + 5(- x1 — x2+12) — 4(2×1 — 2×2+10)

или

F(X) = — 10×1 + x2+20 → max

Система неравенств:

— x1 — x2+12 ≥ 0

— 2×1 + x2+8 ≥ 0
2×1 — 2×2+10 ≥ 0Приводим систему неравенств к следующему виду:

x1 + x2 ≤ 12

2×1 — x2 ≤ 8
— 2×1 + 2×2 ≤ 10
F(X) = — 10×1 + x2+20 → max

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

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

f=x1+13×2-x3+2×4+3×5
-x2+x3-x5=-3
x1-4×2+3×3-x4+2×5=3
4×2-x3+x4-x5=6

Из первого уравнения выражаем x5:
x5 = -x2+x3+3 и подставим во все выражения:

f=x1+13×2-x3+2×4+3(-x2+x3+3)

x1-4×2+3×3-x4+2(-x2+x3+3)=3
4×2-x3+x4-(-x2+x3+3)=6 или

f=x1+10×2+2×3+2×4+9

x1-6×2+5×3-x4=-3
5×2-2×3+x4=9

Из второго уравнения выражаем x4:
x4=9-5×2+2×3 и подставим во все выражения:

f=x1+6×3+27

x1-x2+3×3=6

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

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

Пример №2
F(X) = 3×1 — 2×2 + 5×3 — 4×5 → max при ограничениях:
x1 + x2 + x3=12
2×1 — x2 + x4=8
— 2×1 + 2×2 + x5=10
F(X) = 3×1 — 2×2 + 5×3 — 4×5
Переход к СЗЛП.

Расширенная матрица системы ограничений-равенств данной задачи: Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x3.
2. В качестве базовой переменной можно выбрать x4.
3. В качестве базовой переменной можно выбрать x5.

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).Соответствующие уравнения имеют вид:

x1 + x2 + x3 = 12

2×1 — x2 + x4 = 8
— 2×1 + 2×2 + x5 = 10Выразим базисные переменные через остальные:

x3 = — x1 — x2+12

x4 = — 2×1 + x2+8
x5 = 2×1 — 2×2+10Подставим их в целевую функцию:

F(X) = 3×1 — 2×2 + 5(- x1 — x2+12) — 4(2×1 — 2×2+10)

или

F(X) = — 10×1 + x2+20 → max

Система неравенств:

— x1 — x2+12 ≥ 0

— 2×1 + x2+8 ≥ 0
2×1 — 2×2+10 ≥ 0Приводим систему неравенств к следующему виду:

x1 + x2 ≤ 12

2×1 — x2 ≤ 8
— 2×1 + 2×2 ≤ 10
F(X) = — 10×1 + x2+20 → max

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

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

Источник: https://math.semestr.ru/lp/index.php

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

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

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

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(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

Источник: https://1cov-edu.ru/lineynoe-programmirovanie/graficheskiy-metod/

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

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

Данное решение является образцом работы программы, представленной на сайте.

Задача:

Найти наименьшее значение функции

F = 2 x1 + 2 x2

при следующих ограничениях:

x1 + 2 x2 8
x1 x2 2
x1 + 2 x2 4
x1 1

x1 ≥ 0     x2 ≥ 0

Решение:

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

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

Последние два шага (см. шаг 5 — шаг 6) служат непосредственно для получения ответа.

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

По условию задачи: x1 ≥ 0     x2 ≥ 0.

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

Шаг №1

Рассмотрим неравенство 1 системы ограничений.

x1 + 2 x2  ≤  8

Построим прямую:   x1 + 2 x2 = 8

Пусть x1 =0 => 2 x2 = 8 => x2 = 4

Пусть x2 =0 => x1 = 8

Найдены коородинаты двух точек (0, 4) и (8 ,0). Соединяем их и получаем необходимую прямую (1).

Нас интересуют точки расположенные выше или ниже построенной прямой (1) ?
Вернемся к исходному неравенству.

x1 + 2 x2  ≤  8

Преобразуем неравенство, оставив в левой части только x2

2 x2  ≤  — x1 + 8

x2  ≤  — 1/2 x1 + 4

Знак неравенства  ≤ . Следовательно, нас интересуют точки расположенные ниже построенной прямой (1).

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

Шаг №2

Рассмотрим неравенство 2 системы ограничений.

x1 — x2  ≤  2

Построим прямую:   x1 — x2 = 2

Пусть x1 =0 => — x2 = 2 => x2 = -2

Пусть x2 =0 => x1 = 2

Найдены коородинаты двух точек (0, -2) и (2 ,0). Соединяем их и получаем необходимую прямую (2).

Нас интересуют точки расположенные выше или ниже построенной прямой (2) ?
Вернемся к исходному неравенству.

x1 — x2  ≤  2

Преобразуем неравенство, оставив в левой части только x2

— x2  ≤  — x1 + 2

x2  ≥  x1 — 2

Знак неравенства  ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (2).

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

Шаг №3

Рассмотрим неравенство 3 системы ограничений.

x1 + 2 x2  ≥  4

Построим прямую:   x1 + 2 x2 = 4

Пусть x1 =0 => 2 x2 = 4 => x2 = 2

Пусть x2 =0 => x1 = 4

Найдены коородинаты двух точек (0, 2) и (4 ,0). Соединяем их и получаем необходимую прямую (3).

Нас интересуют точки расположенные выше или ниже построенной прямой (3) ?
Вернемся к исходному неравенству.

x1 + 2 x2  ≥  4

Преобразуем неравенство, оставив в левой части только x2

2 x2  ≥  — x1 + 4

x2  ≥  — 1/2 x1 + 2

Знак неравенства  ≥ . Следовательно, нас интересуют точки расположенные выше построенной прямой (3).

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

Шаг №4

Рассмотрим неравенство 4 системы ограничений.

x1  ≥  1

Построим прямую: x1 = 1

Данная прямая параллельна оси OX2 и проходит через точку (1,0)   (4)

Знак неравенства  ≥ . Следовательно, нас интересуют точки расположенные правее построенной прямой (4).

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

Шаг №5

Строим вектор C = (2, 2), координатами которого являются коэффициенты функции F.

Шаг №6

Будем перемещать «красную» прямую, перпендикулярно вектору C, от левого нижнего угла к правому верхнему.

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

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

Функция F достигает наименьшего значения в точке A. (см. рисунок)

Найдем координаты точки A.
Точка A одновременно принадлежит прямым (3) и (4).

x1 + 2 x2 = 4   =>   x1 = 1
x1 = 1 x2 = 3/2

Вычислим значение функции F в точке A (1,3/2).

F (A) = 2 * 1 + 2 * 3/2 = 5

Ответ:

Замечание: если возникли сомнения, что функция F достигает своего минимума в точке А, необходимо найти значение функции в интересующей точке и сравнить с F(A).

Источник: http://reshmat.ru/example_ZLP_Graf_2.html

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

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

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

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

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

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

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

Для нахождениясреди допустимых решений оптимальногорешения используют линии уровня иопорные прямые.

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

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

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

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

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

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

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

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

4. Линию уровняпереместить до опорной прямой в задачена максимум в направлении нормали, взадаче на минимум – в противоположномнаправлении.

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

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

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

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

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

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

Для этого достаточнокоординаты какой-либо точки, не лежащейна прямой, подставить в неравенство.Так как данная прямая не проходит черезначало координат, подставляем координатыточкиО(0,0) в первое ограничение.Получим неравенство.Следовательно, точкаОне лежит вполуплоскости решений.

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

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

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

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

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

Источник: https://studfile.net/preview/5254831/page:7/

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

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

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

Ввиду того, что наглядность графического решения достигается лишь на плоскости, мы можем познакомиться с графическим представлением задачи только в двумерном пространстве. Это представление пригодно для системы ограничений-неравенств с двумя переменными или для систем уравнений, в которых число переменных на 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. Этот пример показывает, что в некоторых случаях единственность оптимального решения нарушается.

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

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

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

Этот способ иногда бывает удобным в случаях, когда точки пересечения прямых с осями координат — дробные числа и, неправильно отложив точку пересечения, можно получить ошибку и в поиске точек пересечения самих прямых.

Нет времени вникать в решение? Можно заказать работу!

Начало темы «Линейное программирование»

Задача и теоремы линейного программирования, примеры формулировки задач Симплекс-метод: случай, когда максимум целевой функции — бесконечность Симплекс-метод: случай, когда система не имеет ни одного решения Симплекс-метод: случай, когда оптимальное решение — не единственное Двойственная задача линейного программирования Решение задачи целочисленного программирования: методы и примеры Решение транспортной задачи распределительным методом на примерах

с друзьями

Источник: https://function-x.ru/graficheskij_metod.html

Scicenter1
Добавить комментарий