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

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

Поделись  

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

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

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

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

1. Записать в виде y=kx+b уравнения прямых, ограничивающих область допустимых значений переменных.

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

3. Построить для одного или нескольких значений С линии уровня целевой функции f(x, y)=C (несколько линий уровня необходимо построить для того, чтобы понять, имеет ли задача решение и где достигается искомый экстремум).

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

5. Вычислить значение целевой функции в найденной точке.

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

7. Сформулировать общий вывод по задаче линейного программирования.

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

Фрагменты рабочего документа MathCAD с решением данной задачи представлены на рис. 44 – 49.

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

 

Рис. 45. Фрагмент MathCAD-документа: область допустимых решений задачи

Для удобства работы MathCAD позволяет перемещать любые графические объекты на передний или задний план рисунка. Для этого необходимо навести курсор мыши на графической объект, щелкнуть правой кнопкой мыши и выбрать пункт меню Bring to Front (на передний план), Send to Back (на задний план). Поэтому для того, чтобы в дальнейшем буквы, обозначающие точки на графике, или стрелки были доступны для редактирования и перемещения необходимо график, на который они наложены, поместить на задний план. Для этого на графике необходимо щелкнуть правой кнопкой мыши и выбрать пункт меню Send to Back (рис. 46).

Рис. 46. Фрагмент MathCAD-документа: использование контекстного меню для перемещения графических объектов на передний или задний план

Рис. 47. Фрагмент MathCAD-документа: построение целевой функции F(x) и вектора-градиента С

Рис. 48. Фрагмент MathCAD-документа: нахождение координат точки С и максимума целевой функции

Рис. 49. Фрагмент MathCAD-документа: построение окончательного графика

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

Фрагменты рабочего документа MathCAD с решением данной задачи представлены на рис. 50 – 53.

Рис. 50. Фрагмент MathCAD-документа: приведение исходной задачи линейного программирования к стандартной форме

Рис. 51. Фрагмент MathCAD-документа: исходная задача линейного программирования в стандартной форме

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

Рис. 53. Фрагмент MathCAD-документа: построение области допустимых решений задачи



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

Цель:

Пример 2.1.

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

Для изготовления двух видов продукции Р1 и P2 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, число еди­ниц ресурсов, затрачиваемых на изготовление единицы продук­ции, приведены в табл. 2.1 (цифры условные).

Таблица 2.1 – Данные об использовании ресурсов

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
		Р1	Р2
S1	18	1	3
S2	16	2	1
S3	5	—	1
S4	21	3	—

Прибыль, получаемая от единицы продукции Р1 и Р2, – соот­ветственно 2 и 3 грн.

Решение

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

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

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

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

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

Заметим, что для построения прямых достаточно определить две произвольные точки. Так, например, для прямой возьмем для первой точки x₁ = 3, тогда . Для второй точки возьмем x₁ = 6, тогда . Через точки (3; 5) и (6; 4) единственным образом можно провести прямую (прямая BC на рис. 2.1).

Рисунок 2.1 – Область допустимых решений

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

ВС. Аналогично поступают и с остальными неравенствами. На рис. 2.1 область допустимых решений заштрихована.

Этап 2. Поиск оптимального решения.

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

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

Для того чтобы найти оптимальное решение, необходимо определить направление возрастания целевой функции (напомним, что функцию F следует максимизировать). Для этого строится вектор градиента, который начинается в точке (0; 0) и направлен в точку . То есть вектор градиента строится по координатам, совпадающим с коэффициентами целевой функции , и показывает направление ее максимального возрастания. Перпендикулярно ему в направлении градиента откладываются линии уровня (изоцели), на точках которой целевая функция принимает одинаковые значения. На рис. 2.1 видно, что самой крайней изоцелью в пределах ОДР будет изоцель, проходящая через точку С, находящейся на пересечении прямых BC и СD.

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

откуда x₁ = 6, x₂ = 4, то есть С(6; 4).

Итак, при выпуске 6 единиц продукции P1 и 4 единиц P2 прибыль достигает максимального значения: F = 2·6+3·4 = 24.

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

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

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

Напоминаю, вот задача линейного программирования, над которой мы работаем.

Развернуть	Р	=	40x	+	30 лет
Тема:			х	+	2 года	≤	16
			х	+	г	≤	9
			3x	+	2 года	≤	24
			х	,	г	≥	0

Эскиз граничных линий

Первым шагом является набросок линий, соответствующих границам областей. Их можно найти, заменив неравенства ≤ и ≥ знаком равенства =.

Не размещайте целевую функцию на графике. Мы отображаем только ограничения или линейные неравенства на этом графике.

Если вы строите графики функций вручную, приведение неравенств в стандартную форму Ax + By = C для линии, а затем нахождение точек пересечения x и y, вероятно, является самым быстрым способом построения графика. Если вы хотите изобразить их графически с помощью технологии, то решение их явно для y, чтобы они были в форме пересечения наклона, вероятно, является самым простым методом.

График показан справа.

Посмотрите видеоролик Flash: Как построить график с помощью Winplot [2,1 МБ].

Закрасьте неравенства

Затенение неравенства приводит к затенению полуплоскости. Для большинства неравенств, которые мы получаем из задач линейного программирования, довольно легко сказать, в каком направлении нужно заштриховать, просто взглянув на неравенство. При записи в стандартной форме Ax + By ≤ C или Ax + By ≥ C вы будете закрашивать ниже или влево, если меньше или равно или выше, или вправо, если больше или равно неравенству.

Однако эта логика не работает, если A или B отрицательны. Например, -3x + 2y ≤ -2 закрашивается справа (ниже) от линии, а 3x — 2y ≤ 4 закрашивается слева (над) линией. Надежный способ определить, в каком направлении следует заштриховывать, — выбрать контрольную точку, которая не находится на граничной линии, и подставить это значение в неравенство. Начало (0,0) обычно легко использовать, если оно не является решением линейного уравнения. В наших примерах выше левая часть -3x + 2y ≤ -2 становится -3(0) + 2(0) = 0, что не меньше -2, поэтому точка (0,0) не является решением к линейному неравенству. Поскольку (0,0) находится над линией и не работает, мы заштриховываем ниже линии.

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

Посмотрите видеоролик Flash: Как закрасить неравенства с помощью Winplot [1,1 МБ].

Основная теорема линейного программирования

Допустимая область довольно велика. В области бесконечное число точек, где может быть решение. Все точки (0,0), (0,1), (0,2), (1,2), (1,7), (2,16,4,92) и т. д. находятся в допустимой области. К счастью, у нас есть фундаментальная теорема линейного программирования.

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

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

---

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

1. Последнее обновление

2. Сохранить как PDF

Идентификатор страницы

37814

• Рупиндер Секон и Роберта Блум
• Колледж Де Анза

В этой главе вы научитесь:

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

• 3.1: Максимизация приложений

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

  • 3.1.1: Приложения максимизации (упражнения)

• 3.2: Приложения минимизации

  Задачи линейного программирования минимизации решаются почти так же, как задачи максимизации.

  • 3.2.1: Приложения минимизации (упражнения)

• 3.3: Обзор главы

Thumbnation. Множество допустимых решений изображено желтым цветом и образует многоугольник, двумерный многогранник.