Вирішити задачу лінійного програмування графічним методом

Задачи к теме №5

7. Решить задачу линейного программирования графическим методом:​​ f (x1,x2) = x1​​ + 2x2 →​​ min

​​  ​​ ​​ ​​ ​​ ​​ ​​​​ x 1​​ + x2 ≤ 2,

 ​​ ​​ ​​ ​​ ​​ ​​ ​​​​ x 1​​ + x2 ≥ 1, ​​​​ x 1 ≥ 0, x2 ≥ 0.

Решение.

Построим уравнение x1+x2 = 2 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 2. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 2. Соединяем точку (0;2) с (2;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:​​ 

1 • 0 + 1 • 0 - 2 ≤ 0, т.е. x1+x2 - 2≤ 0 в полуплоскости ниже прямой.
Построим уравнение x1+x2 = 1 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 1. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 1.​​ 

Соединяем точку (0;1) с (1;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 1 • 0 - 1 ≤ 0, т.е. x1+x2 - 1≥ 0 в полуплоскости выше прямой.

​​ 

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

Рассмотрим целевую функцию задачи F = x1+2x2 → min. 
Построим прямую, отвечающую значению функции F = 0: F = x1+2x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора – точка (0; 0), конец – точка (1; 2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых(3) и (2), то ее координаты удовлетворяют уравнениям этих прямых:​​ x2=0, ​​ x1+x2=1

Решив систему уравнений, получим: x1 = 1, x2 = 0

Откуда найдем минимальное значение целевой функции:
F(X) = 1*1 + 2*0 = 1

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

f (x1,x2) = 2x1​​ + 2x2 → max

x 1​​ – 2x2 ≤ 1,

x 1​​ + 2x2​​ ≤ 4,

x 1 ≥ 1,

x 1 ≥ 0, x2 ≥ 0.

Решение.

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

Построим уравнение x1-2x2 = 1 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = -0.5.​​ 

Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 1.​​ 

Соединяем точку (0;-0.5) с (1;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:​​ 

1 • 0 - 2 • 0 - 1 ≤ 0, т.е. x1-2x2 - 1≤ 0 в полуплоскости ниже прямой.

Построим уравнение x1+2x2 = 4 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 2.​​ 

Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 4. Соединяем точку (0;2) с (4;0) прямой линией.​​ 

Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 2 • 0 - 4 ≤ 0, т.е. x1+2x2 - 4≤ 0 в полуплоскости ниже прямой

Построим уравнение x1 = 1.​​ Эта прямая проходит через точку x1 = 1 параллельно оси OX2. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 - 1 ≤ 0, т.е. x1 - 1≥ 0 в полуплоскости правее прямой.

или

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

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

Рассмотрим целевую функцию задачи F = 2x1+2x2 → min.

Построим прямую, отвечающую значению функции​​ 

F = 0: F = 2x1+2x2 = 0.​​ 

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора – точка (0; 0), конец – точка (2; 2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых(1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:​​ x1-2x2=1​​ ,​​ x1=1

Решив систему уравнений, получим: x1 = 1, x2 = 0

Откуда найдем минимальное значение целевой функции:

F(X) = 2*1 + 2*0 = 2

9. Решить задачу безусловной оптимизации. Определить экстремум функции:

F (x) = –12x2 – 2x + 4.

Решение.​​ 

Уравнение f'0(x) = 0 - это необходимое условие экстремума функции одной переменной, т.е. в точке x первая производная функции должна обращаться в нуль. Оно выделяет стационарные точки xс, в которых функция не возрастает и не убывает.

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

Пусть f0(x) дважды дифференцируемая по​​ x, принадлежащему множеству D.​​ 

Если в точке​​ x​​ выполняется условие:

f'0(x) = 0

f''0(x) > 0

то точка​​ x​​ является точкой локального (глобального) минимума функции.

Если в точке​​ x​​ выполняется условие:

f'0(x) = 0

f''0(x) < 0

то точка​​ x​​ - локальный (глобальный) максимум.

Находим первую производную функции:​​ 

y' = -24x-2

Приравниваем ее к нулю:

-24x-2 = 0

x1 = -1/12​​ = - 0,083

Вычисляем значения функции 

f(-1/12) = 49/12=4,083

Используем достаточное условие экстремума функции одной переменной. Найдем вторую производную:

y'' = -24

Вычисляем:
y''(-1/12) = -24<0 - значит точка x = -0,0833 -​​ точка максимума функции.

Производная функции равна:​​ -24х-2

Нули производной:​​ х= -1/12=-0,09

Функция возрастает на:​​ 

Функция убывает на:

Минимальное значение функции:​​ - ∞

Максимальное значение функции:​​ 49/12 или 4,09​​ (график).

10. Потребитель имеет доход 500 грн. в неделю и может покупать 2 блага в количествах X1 и X2 по ценам 40 и 50 грн. за единицу, соответственно. Функция полезности потребителя: U(X1,X2) = 2X12 + X22. Решить задачу потребительского выбора с помощью метода множителей Лагранжа.

Решение 1.​​ Для двух товаров целевая функция потребления имеет вид:
U = 2x12+x22

Вектор цен равен Р = (40; 50); величина дохода равна 500.

Предельные полезности имеют вид:

;​​ 

D = 500​​ грн. - доход потребителя.

Необходимые условия оптимума дают следующую систему уравнений (λ -множитель Лагранжа):

4x1​​ = 40λ

2x2​​ = 50λ

40x1 + 50x2 = 500

После подстановки первого уравнения во второе получим:
2x2​​ = 50*(4x1)/40

Выразив из третьего уравнения x1 и подставив в последнее равенство, будем иметь:

33/4x2​​ -​​ 125/2 = 0​​ или 8,25х2​​ –​​ 62,5 = 0

Решая его относительно x2 получим:

x2 = 250/33​​ = 7,58

При x2 = 250/33 или 7.58​​ x1 = 100/33 или 3.03

U(X) = 2500/33 или 75.76

Решение 2.​​ Найдем экстремум функции F(X) = 2∙x12+x2, используя функцию Лагранжа:

где​​ 

F(X) - целевая функция вектора X

φi(X) - ограничения в неявном виде (i=1..n)

В качестве целевой функции, подлежащей оптимизации, в этой задаче выступает функция:

U(х1, х2) = 2x12+x22

Перепишем ограничение задачи в неявном виде:

φ1(X) =​​ 40∙x1+50∙x2-500 = 0

Составим вспомогательную функцию Лагранжа:

L(X, λ) = 2∙x12+x2 + λ∙(40∙x1+50∙x2-500) 

Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным хi и неопределенному множителю λ.

Составим систему:

∂L/∂x1 = 4∙x1+4∙λ = 0

∂L/∂x2 = 2∙x2+5∙λ = 0

∂L/∂λ = 40∙x1+50∙x2-500 = 0

Решив данную систему, получаем стационарные точки​​ х0.

Решение :

Альтернативные формы :

х1= 3,03  ​​​​ х2​​ = 7,58 ​​ λ = - 3,03