Семестр ру графический способ

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

Чтобы найти ее оптимальное решение, нужно выполнить следующие действия:

1. Найти ОДР, определяемую ограничениями задачи. Если окажется, что эта область пуста, то это означает, что задача не имеет решения.
2. Построить семейство линий уровня целевой функции f(х₁, х₂) = C при различных значениях числового параметра С.
3. При решении задачи на минимум определить направление убывания, а для задачи на максимум — направление возрастания линий уровня ЦФ.
4. Найти точку ОДР, через которую проходит линия уровня с наименьшим в задаче на минимум (соответственно, наибольшим в задачи на максимум) значением параметра С. Эта точка будет оптимальным решением. Если ЦФ не ограничена снизу в задаче на минимум (сверху — в задаче на максимум), то это означает, что задача не имеет оптимального решения.
5. Найти координаты точки оптимума и определить в ней значение ЦФ.

Отметим, что в отличие от задачи ЛП точка оптимума в задаче НП не обязательно находится на границе ОДР. Ею также может быть внутренняя точка этого множества.

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

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

F(X) = x₁ 2 +(x₂-2) 2
2x₁+x₂ ≥ 7
x₁+2x₂ ≥ 5

Решение. 1) Строим два ограничения, тем самым определяя ОДР. Можно использовать этот калькулятор. Также удобно строить ограничения через этот сервис.

Затем строим функцию цели. В данном случае это окружность.

Поскольку задача минимума, то ищем первое касание линии уровня области ОДР. В данном случае это точка пересечения с прямой 2x₁+x₂-7=0.
Найдем точку пересечения. Для этого построим уравнение касательной, проходящей через центр окружности O(0;2) и перпендикулярно прямой 2x₁+x₂-7=0 (можно использовать этот калькулятор). Получаем: 2x₂-x₁-4=0. Решая систему уравнений:
2x₁+x₂-7=0
2x₂-x₁-4=0,
получаем: x₁=2, x₂=3.

2) Найдем экстремум функции F(X) = x₁ 2 +(x₂-2) 2 , используя калькулятор Функция Лагранжа :
L( X , λ )=F( X )+∑(λ_i·φ_i)
где F( X ) — целевая функция вектора X; φ_i(X) — ограничения в неявном виде (i=1..n)
В качестве целевой функции, подлежащей оптимизации, в этой задаче выступает функция: F(X) = x₁ 2 +(x₂-2) 2
Перепишем ограничение задачи в неявном виде:
φ₁(X) = 7 — (2*x₁+x₂) = 0 (X₁)
φ₂(X) = 5 — (x₁+2*x₂) = 0 (X₂)
Составим вспомогательную функцию Лагранжа: L(X, λ) = x₁ 2 +(x₂-2) 2 — λ₁*(7 — (2*x₁+x₂)) — λ₂*(5 — (x₁+2*x₂))
Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным х_i и неопределенным множителям λ.
Составим систему:
∂L/∂x₁ = 2*λ₁+λ₂+2*x₁ = 0
∂L/∂x₂ = λ₁+2*λ₂+2*x₂-4 = 0
∂L/∂λ₁ = 2*x₁+x₂-7 = 0
∂L/∂λ₂ = x₁+2*x₂-5 = 0
Решив данную систему, получаем:
а) для случая X₁: x₁ = λ₁/2 + λ₂ + 2; x₂ = 7 — 2x₁
Откуда можно найти такие λ₁ ≥ 0, λ₂ ≥ 0. Пусть λ₂ = 0. Тогда λ₁ = 2; x₁ = 2; x₂ = 3.
Поскольку λ₂ ≥ 0, то данное решение удовлетворяет условиям Куна-Таккера. Z_min(2;3)=5

б) для случая X₂: x₂ = λ₁/2 + λ₂ + 2; x₁ = 5 — 2x₂
Откуда можно найти такие λ₁ ≥ 0, λ₂ ≥ 0. Пусть λ₂ = 0. Тогда λ₁ = 2/5; x₁ = 11/5; x₂ = 3/5.
Поскольку λ₁ ≥ 0, то данное решение удовлетворяет условиям Куна-Таккера. Z_min(11/5;3/5)=6.8

Минимальное значение составит Z_min(2;3)=5.

Источник

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

Пример №1 . Решить задачу линейного программирования графически в трехмерном пространстве.
f(x) = 3x₁ + 5x₂ – x₃
при ограничениях
x₁ + x₂ + 2x₃ = 6
x₂ + x₃ – x₄ = 4
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0
Решение. Проведем анализ задачи. В задаче 4 переменные и 2 основных ограничения в виде равенств (не считая условия неотрицательности). Так как ограничения даны в виде равенств, то задача в канонической форме. В данном виде геометрически задачу не решить, так как много переменных.
Решим задачу графически, преобразовав каноническую форму задачи линейного программирования к стандартному виду. У нас два ограничения и есть две переменные, каждая из которых встречается только в одном уравнении. Эти переменные можно исключить из задачи, тем самым упростив её формулировку. Исключаемыми переменными объявим первую и последнюю.
Для этого из первого условия системы ограничений выразим x₁ = 6- x₂ — 2x₃ , а из второго уравнения x₄ = x₂ + x₃ — 4.
Подставим x₁ = 6- x₂ — 2x₃ в целевую функцию и получим новую целевую функцию
F = 18 + 2x₂ – 7x₃ и новую систему ограничений без переменных x₁, x₄:
x₂ + 2x₃ ≤6
x₂ + x₃ ≥ 4
x₂ ≥ 0, x₃ ≥ 0
За счет неотрицательности исключаемых переменных получили неравенства в разные стороны.
Полученную задачу линейного программирования стандартного вида на плоскости решим графически. На плоскости x₂Ox₃ изобразим множество допустимых планов, которое удовлетворяет системе ограничений. Получим треугольник с вершинами в точках B(4,0), C(6,0), A(2,2).

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

Пример №2 . Найти графическим методом или симплекс-методом какое-нибудь решение системы.
x + y + z = 10
5x +2y +z ≥ 26
6x + 5y + 3z ≤ 57

Здесь не задана целевая функция. Однако графическим методом можно найти область допустимых значений (ОДР). Для этого выразить z=10-x-y и подставить в другие уравнения:
5x+2y+10-x-y ≥ 26
6x+5y+30-3x-3y ≤ 57
или
4x+y ≥ 16
3x+2y ≤ 27
Таким образом, осталось две переменные.

Источник

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

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

В силу этих определений задача ЛП может быть сформулирована следующим образом: среди всех точек выпуклой области, являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную функцию F = с₁x + с₂y.
Заметим, что переменные x, y в ЗЛП принимают, как правило, неотрицательные значения (x≥ 0, y ≥ 0), поэтому область расположена в I четверти координатной плоскости.

Рассмотрим линейную функцию F = с₁x + с₂y и зафиксируем какое-нибудь ее значение F. Пусть, к примеру, F = 0, т.е. с₁x + с₂y = 0. Графиком этого уравнения будет прямая, проходящая через начало координат (0;0) (рис.).

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

Случай 1
Рисунок 6
При перемещении прямой с₁x + с₂y= d «вход» или «выход» (как на рисунке) произойдет по стороне многоугольника. Это случится, если в многоугольнике есть стороны, параллельные прямой с₁х + с₂у = d .
В этом случае точек «выхода» (« входа») бесчисленное множество, а именно – любая точка отрезка АВ. Это означает, что целевая функция принимает максимальное(минимальное) значение не в одной точке, а во всех точках, лежащих на соответствующей стороне многоугольника D.

Случай 2
Рассмотрим случай, когда область допустимых значений неограниченна.
В случае неограниченной области целевая функция может быть задана таким образом, что соответствующая ей прямая не имеет точки «выхода» (или «входа»). Тогда максимальное значение функции (минимальное) не достигается никогда – говорят, что функция не ограничена.
Рисунок
Необходимо найти максимальное значение целевой функции F = 4x+6y → max , при системе ограничений
x+y≤18
0,5x+y≤12
x≤12
y≤9
x≥0, y≥0
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
x + y = 18

x	12	9
y	6	9

0,5x + y = 12

x	12	18
y	6	3

x = 12 – параллельна оси OY ;
y = 9 – параллельна оси OX ;
x = 0 – ось OY ;
y = 0 – ось OX;
x≥ 0 – полуплоскость правее оси OY;
y ≥ 0 – полуплоскость выше оси OX;
y ≤ 9 – полуплоскость ниже y = 9;
x ≤ 12 – полуплоскость левее x = 12;
0,5x + y≤ 12 – полуплоскость ниже прямой 0,5x + y = 12;
x + y≤ 18 – полуплоскость ниже прямой x + y = 18.

Рассмотрим целевую функцию задачи F = 4x + 6y → max.

Построим прямую, отвечающую значению функции F = 0 : 4x + 6y = 0. Будем двигать эту прямую параллельным образом. Из всего семейства прямых 4x+ 6y = const последней вершиной, через которую пройдет прямая при выходе за границу многоугольника, будет вершина С (12; 6). Именно в ней F = 4x + 6y достигнет своего максимального значения.
Значит, при x = 12, y = 6 функция F достигает своего максимального значения F = 4 ∙ 12 + 6 ∙ 6 = 84, равного 84. Точка с координатами (12; 6) удовлетворяет всем неравенствам системы ограничений, и в ней значение целевой функции оптимально F* = 84 (оптимальное значение будем обозначать «*»).
Задача решена. Итак, необходимо выпустить 12 изделий I вида и 6 изделий II вида, при этом прибыль составит 84 тыс. руб.

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

Пример №2 . Шахта разрабатывает два пласта. Выход штыба по первому пласту составляет а1 %; по второму — а2 %. Максимальная производительность очистного забоя по первому пласту составляет В1 тыс.тонн в год, по второму пласту — В2 тыс.тонн в год. По технологии работ добыча со второго пласта не может превышать добычу с первого пласта. Выход штыба по шахте не должен превышать С1 тыс.тонн в год. Общая нагрузка по двум пластам за год должна быть не меньше С2 тыс.тонн в год. Составить математическую модель и построить множество допустимых значений нагрузки по первому и второму пластам за год.

Пример №3 . Магазин продает 2 вида безалкогольных напитков : Колу и лимонад. Доход от одной банки колы составляет 5 центов, тогда как доход от одной банки лимонада 7 центов. В среднем магазин за день продает не более 500 банок обоих напитков. Несмотря на то, что колу выпускает известная торговая марка, покупатели предпочитают лимонад, поскольку он значительно дешевле. Подсчитано, что объем продаж колы и лимонада должны соотноситься не менее 2:1 кроме того , известно что магазин продает не менее 100 банок колы в день. Сколько банок каждого напитка должен иметь магазин в начале рабочего дня для максимизации дохода?

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

Пример №5 . Туристской фирме требуется не более а трехтонных автобусов и не более в пятитонных автобусов. Отпускная цена автобусов первой марки 20000 у.е., второй марки 40000 у.е. Туристская фирма может выделить для приобретения автобусов не более с у.е. Сколько следует приобрести автобусов каждой марки в отдельности, чтобы их общая (суммарная) грузоподъёмность была максимальной. Решить задачу графическим методом.

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

Пример №7 . Решить графическим методом задачу линейного программирования, подвергнув систему ограничений задачи преобразованиям Жордано-Гаусса. Система ограничений задачи имеет вид:
a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + a₁₄x₄ + a₁₅x₅ = b₁
a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + a₂₄x₄ + a₂₅x₅ = b₂
a₃₁x₁ + a₃₂x₂ + a₃₃x₃ + a₃₄x₄ + a₃₅x₅ = b₃
Методические рекомендации. Преобразования Жордано-Гаусса можно выполнить с помощью этого сервиса или через исследование СЛАУ.

Пример №8 . Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида а1, а2, а3 кг соответственно, а для единицы изделия В — в1, в2, в3 кг. Производство обеспечено сырьем каждого вида в количестве Р1, Р2, Р3 кг, соответственно. Стоимость единицы изделия А составляет С1 руб., а единицы изделия В — С2 руб. Требуется составить план производства изделий А и В, обеспечивающий максимальную стоимость готовой продукции.

Пример №9 . Необходимо найти максимальное значение целевой функции F = 4x+6y → max, при системе ограничений:
x+y≤18
0,5x+y≤12
x≤12
y≤9
x≥0, y≥0

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

Затем заполняем коэффициенты при переменных и сами ограничения (рисунок 2).

Пересечением всех этих полуплоскостей является пятиугольник ABCDE, с вершинами в точках A(0; 0), B(0;9), C(6; 9), D(12;6), E(12;0). Этот пятиугольник и образует область допустимых решений задачи.

Рассмотрим целевую функцию задачи F = 4x+6y → max.

x	3	0
y	–2	0

Построим прямую, отвечающую значению функции F = 0 : 4x + 6y = 0. Будем двигать эту прямую параллельным образом. Из всего семейства прямых 4x + 6y = const последней вершиной, через которую пройдет прямая при выходе за границу многоугольника, будет вершина С (12; 6). Именно в ней F = 4x + 6y достигнет своего максимального значения.

Источник