30. Нелинейное программирование. Методы решения задач.
Рассмотрим ЗНП и способы её решения. Математическая модель ЗНП в общем виде формулируется следующим образом:
f =(x1,x2, …,хn) → min (max). При этом переменные должны удовлетворять ограничениям:
g1(x1,x2, …,хn) ≤b1,
…………………………
gm(x1,x2, …,хn) ≤bm,
gm+1(x1,x2, …,хn) ≥bm+1,
…………………………
gk(x1,x2, …,хn) ≥bk,
gk+1(x1,x2, …,хn)=bk+1,
………………………
gp(x1,x2, …,хn)=bp.
x1,x2,…,хn ≥0, где хотя бы одна из функций f, gi нелинейная.
Для ЗЛП нет единого метода решения. В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, к которым относятся метод множителей Лагранжа, градиентные методы, приближённые методы решения, графический метод.
Рассмотрим основные идеи графического метода.
Максимум и минимум достигается в точках касания линии уровня с областью допустимых решений (ОДР), которая задается системой ограничений. Например, если линии уровня - прямые, то точки касания можно определить, используя геометрический смысл производной.
Рассмотрим на примерах решение ЗНП.
1. Найти экстремумы функции L(x1,x2)=x1+2x2 при ограничениях
, .
Р 5
=- ; ( ) =- ;
=- ; x0= ; x2=2 .
Тогда L= +2∙2 =5 .
О твет: Минимум достигается в точке О(0;0), глобальный максимум, равный 5 , в точке А( ;2 ) .
2. Найти экстремумы функции L=(x1-6)2+(x2-2)2 при ограничениях
x1+x2≤8
3 x1+x2 ≤15
x1+x2 ≥1
.
Решение. ОДР – многоугольник ABCDE. Линии уровня представляют собой окружности (x1-6)2+(x2-2)2=С с центром в точке О1(6;2). Возьмём, например, С=36, видим, что максимум достигается в точке А(0;4), которая лежит на окружности наибольшего радиуса, пересекающую ОДР. L(A)=(0-6)2+(4-2)2=40. Минимум - в точке F, находящейся на пересечении прямой 3x1+x2 =15 и перпендикуляра к этой прямой, проведённого из точки О1. Т.к. угловой коэффициент равен -3, то угловой коэффициент перпендикуляра равен . Из уравнения прямой, проходящей через данную точку О1 с угловым коэффициентом , получим (x2-2)= (x1-6). Найдём координаты точки Е
х 1-3х2=0
3 x1+x2 =15.
Решив систему, получаем Е(4.5; 1.5).
L (E) = (4.5-6)2+ (1.5-2)2=2.5.
Ответ: Минимум, равный 2.5 достигается в точке (4.5; 1.5), максимум, равный 40, в точке (0;4).
3. Найти экстремумы функции L=(x1-1)2+(x2-3)2
при ограничениях , .
Решение: ОДР является часть круга, с центром в начале координат, с радиусом 5, расположенная в I четверти. Линии уровня – это окружности с центром в точке О1 и радиуса С, т.к. (x1-1)2+(x2-3)2=С. Точка О1 – это вырожденная линия уровня, соответствующая минимальному значению С=0. глобальный максимум достигается в точке А, лежащей на пересечении ОДР с линией уровня наибольшего радиуса. При этом
L(A)=(5-1)2+(0-3)2=25.
Ответ: Минимум, равный 0, достигается в точке (1;3),
Максимум, равный 25, - в точке А(5;0).
4. Предприниматель решил выделить на расширение своего дела 150 тыс.руб. известно, что если на приобретение нового оборудования затратить х тыс. руб., а на зарплату вновь принятых работников у тыс. руб., то прирост объёма продукции составит Q=0.001x0.6·y0.4 . Как следует распределить выделенные денежные ресурсы, чтобы прирост объёма продукции был максимальным.
Решение: Целевая функция имеет вид 0.001x0.6·y0.4 →max при ограничениях x+y≤150,
.
ОДР – треугольник. Линии уровня будут иметь вид 0.001x0.6·y0.4 =С. Выразив отсюда у, получим у= . Т.к. максимум достигается в точке касания линии уровня с ОДР, то условие касания имеет вид =-1. Найдя производную, получаем =-1. Выразив х, получим х= . у= = .
Ответ: Факторы х и у следует распределить в отношении 2:3.
5.Предприятие выпускает изделия А и Б, при изготовлении которых используется сырьё S1 и S2. Известны запасы bi (i=1,2) сырья, нормы его расхода на единицу изделия aij (j=1,2), оптовые цены pj на изделия и их плановая себестоимость с . Как только объём выпускаемой продукции перестаёт соответствовать оптимальному размеру предприятия, дальнейшее увеличение выпуска хj ведёт к повышению себестоимости продукции b, в первом приближении фактическая себестоимость сj описывается функцией сj= с + с хj, где сj – некоторая постоянная. Все числовые данные приведены в таблице
b1 | b2 | a11 | a12 | a21 | a22 | p1 | p2 | с | с | с | с |
90 | 88 | 13 | 6 | 8 | 11 | 12 | 10 | 7 | 8 | 0.2 | 0.2 |
Найти план выпуска изделий, обеспечивающий предприятию наивысшую прибыль в условиях нарушения баланса между объёмом и оптимальным размером предприятия.
Решение: Составим математическую модель задачи.
Пусть Z – прибыль, получаемая предприятием после реализации х1 выпущенных изделий А и х2 изделий Б.
Z=( 12-( 7+ 0,2 х1)) х1+( 10-( 8+ 0,2 х2)) х2 →max,
п ри ограничениях 13 х1+ 6 х2≤ 90,
8 х1+ 11 х2≤88,
П реобразуя целевую функцию, получим:
Z=5х1-0,2х +2 х2-0,2х →max
ОДР – многоугольник ОАВD. Для построения линий уровня функции, приведём функцию к следующему виду:
(х1-12,5)2+(х2-5)2=181,25-5Z .
Л иниями уровня будут окружности с центром в точке О1(12,5; 5) и радиуса . Окружность наибольшего радиуса будет проходить через точку М, находящейся на пересечении прямой ВD и прямой O1М, перпендикулярной к BD. Найдём координаты точки М.
13х1+ 6х2=90
х2-5=6/13(х1-12,5). Решив систему, получим, М(6;2).
Z(М)=30-7,2-2,8+4=26.
Ответ: Для получения предприятием максимальной прибыли, составляющей 26 ден.ед., следует выпустить 6 ед. изделия А и 2 ед. изделия Б.
- Системы линейных уравнений. Разрешимость систем линейных уравнений (теорема Кронекера-Капелли).Методы решения.
- Основные алгебраические структуры: группы, кольца , поля. Основные свойства. Примеры.
- 1. Гомоморфный образ группы также является группой относительно своей операции.
- 2. Пусть f: g1®g2 – гомоморфизм групп. Тогда
- Композиция любых двух (или нескольких) гомоморфизмов (моно, эпи) является гомоморфизмом (моно, эпи).
- Определители и их свойства. Основные методы вычисления определителей.
- Линейные пространства, подпространства. Примеры. Свойства пространств. Линейная зависимость и независимость системы векторов. Базис пространства.
- 5. Линейные операторы. Собственные векторы и собственные значения линейного оператора, их свойства и отыскание.
- 6. Корни многочлена. Методы нахождения корней. Результант многочленов, его связь с корнями.
- 7. Поле комплексных чисел. Формула Муавра. Извлечение корня из комплексных чисел.
- 8. Линии второго порядка, их канонические уравнения, фокусы, директрисы, асимптоты.
- 9. Прямая и плоскость в пространстве, их уравнения. Взаимное расположение прямых и плоскостей.
- 10. Проективная плоскость. Координаты точки и прямой. Особенности линий второго порядка.
- 11. Операции над векторами векторного пространства v3. Векторный метод в решении геометрических задач.
- 12. Предел непрерывность функций одной и нескольких переменных. Свойства функций, непрерывных на отрезке.
- 13. Производная и дифференциал функции одной и нескольких переменных. Достаточные условия дифференцируемости.
- 14. Определенный интеграл, его свойства. Основная формула интегрального исчисления.
- 15. Числовые ряды. Абсолютная и условная сходимость. Признаки сходимости: Даламбера, интегральный, Лейбница.
- 18. Производная функция комплексного переменного. Условия Коши-Римана. Аналитическая функция.
- 19. Степенные ряды в действительной и комплексной области. Радиус сходимости.
- 20. Ряд Фурье по ортогональной системе функций. Неравенство Бесселя, равенство Парсеваля, сходимость ряда Фурье.
- 21. Уравнения в частных производных. Основные задачи математической физики. Метод Фурье.
- 23. Множества и способы их задания. Отношения и отображения. Понятие о мощности. Счетные и континуальные множества.
- Свойства счетных множеств
- Графическое представление
- 5. Основные тождества алгебры множеств
- Принципы математической индукции
- Отображение отношения функции
- 24. Коды постоянной и переменной длины, примеры их использования. Принцип работы архиватора.
- 25. Задача потребительского выбора и ее решение.
- 26. Понятие эластичности, геометрический смысл. Свойства эластичности, эластичность элементарных функций.
- 27. Производственная функция. Закон убывающей эффективности.
- 28. Транспортная логистика. Транспортная система России, ее особенности и характеристики. Маршруты движения автотранспорта. Математические методы для организации материала потока.
- 29. Задачи линейного программирования. Экономический анализ задач с использованием теории двойственности.
- 3) Двойственная задача.
- 30. Нелинейное программирование. Методы решения задач.