Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Математическое программирование

Покупка
Основная коллекция
Артикул: 787123.01.99
Конспект лекций содержит основные понятия и теоретические положения теории математического программирования. Конспект лекций предназначен студентам 3 курса ИТТСУ РУТ (МИИТ) специальности ТКИ.
Аверинцев, М. Б. Математическое программирование : конспект лекций / М. Б. Аверинцев, Н. А. Корниенко. - Москва : РУТ (МИИТ), 2018. - 66 с. - Текст : электронный. - URL: https://znanium.com/catalog/product/1895301 (дата обращения: 19.04.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
 

МИНИСТЕРСТВО ТРАНСПОРТА 
РОССИЙСКОЙ ФЕДЕРАЦИИ  

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ   
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ 
УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ  
«РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА  
(МИИТ)» 
___________________________________________________ 

Кафедра 
«Высшая и вычислительная математика» 

 

М. Б. Аверинцев, Н. А. Корниенко 

 

 

МАТЕМАТИЧЕСКОЕ 
ПРОГРАММИРОВАНИЕ 

 

 

 

Москва – 2018  

МИНИСТЕРСТВО ТРАНСПОРТА 
РОССИЙСКОЙ ФЕДЕРАЦИИ  

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ   
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ 
УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ  
«РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА  
(МИИТ)» 
___________________________________________________ 

Кафедра 
«Высшая и вычислительная математика» 

 

М. Б. Аверинцев, Н. А. Корниенко 

 

 

МАТЕМАТИЧЕСКОЕ 
ПРОГРАММИРОВАНИЕ 

Конспект лекций 
для студентов специальности ТКИ 

 

 

Москва – 2018  

УДК 519.8 

А-19 

 

       Аверинцев М. Б., Корниенко Н. А. Математическое 
программирование: Конспект лекций. – М.: РУТ (МИИТ), 
2018. – 66 с. 

 

         Конспект 
лекций 
содержит 
основные 
понятия             
и теоретические положения теории математического 
программирования. 
Конспект 
лекций 
предназначен 
студентам 3 курса ИТТСУ РУТ (МИИТ) специальности 
ТКИ. 

 

 

Рецензенты:  

доцент кафедры «Прикладная математика 1» РУТ (МИИТ) 
к.ф.-м.н. Зверкина Галина Александровна; 

доцент кафедры Прикладной математики ФГБОУ ВО 
МГТУ «Станкин», к.ф.-м.н. Петросян Наталья Семеновна. 

 

 

© РУТ (МИИТ), 2018

Содержание 

1. Основные понятия математического    
программирования .................................................................. 5 

1. 1. Задачи математического программирования ........... 5 

1. 2. Примеры задач оптимизации, сводящихся к  
задачам математического программирования .................. 7 

1. 3. Необходимые условия минимума в терминах 
направлений ......................................................................... 9 

1. 4. Теорема Каруша – Джона ......................................... 14 

2. Методы решения некоторых задач нелинейного 
программирования ................................................................ 17 

2. 1. Задача дробно-линейного программирования........ 17 

2. 2. Задача на условный экстремум ................................ 20 

2. 3. Смысл множителей Лагранжа .................................. 28 

2. 4.  Условия оптимальности в задачах выпуклого 
программирования ............................................................ 30 

2. 5. Задача квадратичного программирования .............. 36 

3. Вопросы существования решения ................................... 40 

3. 1. Условия существования минимума в задачах 
математического программирования .............................. 40 

3. 2. Достаточные условия экстремума ........................... 42 

3. 3. Принцип Ле Шателье – Самуэльсона ...................... 43 

3. 4. Условия оптимизации без условий на    
производные ....................................................................... 45 

3. 5. Двойственность в выпуклом программировании .. 47 

4. Методы приближенного решения задач  
математического программирования .................................. 49 

4. 1. Методы возможных перемещений .......................... 49 

4. 2.  Метод штрафных функций ...................................... 57 

4. 3. Метод барьерных функций....................................... 62 

 

 

 

 

 

 
 
 

1. Основные понятия математического 
программирования 

1. 1. Задачи математического программирования 

 

    Многие 
задачи 
оптимизации 
сводятся 
к 

математическим моделям следующего вида: 

����(����) → ������������,
���� ∈ ����. 

     В этом случае говорят об условной минимизации. В 

большинстве случаев множество ���� определяется системой 

равенств и (или) неравенств. В этом случае задача 

записывается следующим образом: 

����(����) → ������������ (������������)                                         (1.1.1) 

��������(����) = 0 ,        ���� ∈ ����1                                       (1.1.2) 

��������(����) = 0 ,        ���� ∈ ����2                                      (1.1.3) 

где      ����1 ∪ ����2 = {1, 2, … , ����} ,       ����1 ∩ ����2 = ∅ . 

           Задача 
(1.1.1) − (1.1.3)
 называется 
задачей 

математического программирования.  

           Отметим некоторые частные случаи этой задачи. 

 

 

1. Линейное программирование 

В (1) − (3) все функции линейные, кроме того �������� ≥ 0 для 
всех  ����,  где  ���� = (����1, ����2, … , ��������). 

2. Нелинейное программирование 

Хотя бы одна из функций в (1.1.1) − (1.1.3) не является 
линейной. 

3. Задача на условный экстремум 

Нет ограничений – неравенств, т. е.   ����1 = ∅ . 

4. Задача выпуклого программирования 

Все функции ����(����),  ��������(����) – выпуклые, а ограничения – 

равенства отсутствуют, т. е.   ����2 = ∅ . 

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

как правило, связано с большими трудностями, чем 

решение задач безусловной минимизации. 

 

 

 

 

1. 2. Примеры задач оптимизации, сводящихся к 
задачам математического программирования  

 

    Пример 1. Составить математическую модель 

следующей 
задачи. 
На 
двух 
предприятиях 
нужно 

изготовить ���� изделий некоторой продукции: затраты на 

производство 
����1
изделий 
на 
первом 
предприятии 

составляют (��������1
2 + ����)  рублей, а на производство ����2 

изделий на втором предприятии   ��������2  рублей. Определить 

сколько 
изделий 
на 
каждом 
предприятии 
нужно 

произвести, чтобы затраты на их производство были 

минимальными. 

    Объектом оптимизации является план выпуска 

продукции. 
Управляемые 
переменные 
����1
 и 
����2
,                

����1 ≥ 0,   ����2 ≥ 0,   ����1 + ����2 = ���� .   Целевая функция 

����(����1, ����2) = ��������1
2 + ���� + ��������2 → ������������ . 

           Данная 
задача 
является 
задачей 
нелинейного 

программирования. 

           Пример 2. Экспериментатор измеряет величину ����, 

зависящую от параметра  ���� , ����  раз при различных 

величинах  ���� = ��������,  ���� = 1, 2, … , ����. . В результате получены 

 ����   пар (��������, ��������) . Предполагаемая зависимость ����  от ���� 

задается линейной функцией  ���� = �������� + ���� , где  ���� ≥ 0 ,  

���� ≥ 0 . Необходимо подобрать коэффициенты  ����   и  ����  

таким образом, чтобы минимизировать расстояние по 

вертикали от точек  (��������, ��������)  до  прямой   ���� = �������� + ����.  

           Объектом 
оптимизации 
является 
выражение 

���� = �������� + ����, содержащее два неизвестных коэффициента  ���� 

и  ����. Управляемые переменные  ����, ����  и  ∆, определяющая 

максимальное 
расстояние 
между 
ординатами 

экспериментальных точек  (��������, ��������)  и точек  (��������, ������������ + ����),   

т. е.  

−∆ ≤ �������� − ������������ − ���� ≤ ∆ ,   ���� ≥ 0,   ���� ≥ 0,   ∆≥ 0. 

Целевая функция       ����(����, ����, ∆) = ∆→ ������������ . 

           Эта 
задача 
является 
задачей 
линейного 

программирования. 

 

 

 

 

 

 

 

 

1. 3. Необходимые условия минимума в терминах 
направлений 

 

     Рассмотрим 
задачу 
математического 

программирования в виде  ����(����) → ������������,   ���� ∈ ���� , где 

допустимое множество ����  выпукло и задается тем или 

иным способом. 

     Для точек множества ���� введем следующие понятия 

направлений, 
учитывающие 
локальные 
свойства 

множества  ����  и целевой функции  ����(����). 

     Определение 1. Вектор  ���� ∈ ��������   задает в точке  

����0 ∈ ��������
 возможное 
направление, 
если 
����0 + ���� ���� ∈ ����         

при всех достаточно малых  ���� > 0. 

     Если  ����0  – внутренняя точка множества  ���� , то, 

очевидно, возможным является любое направление. 

     Для граничной точки  ����0  множества  ����  возможные 

направления определяются видом границы в окрестности 

этой точки. 

Пример 1. Точка ����0  лежит на границе множества  ���� , 

определяемого неравенством   〈����, ����〉 ≤ ���� ,   т. е. ����0 

принадлежит 
гиперплоскости 
 
〈����, ����〉 = ����
. 
Тогда 

возможные 
направления 
удовлетворяют 
условию      

〈����, ����〉 ≤ 0. 

Здесь 〈����, ����〉  – скалярное произведение векторов 

���� 
⃗ = (����1, ����2, … , ��������) ∈ ��������   и   ���� ⃗ = (����1, ����2, … , ��������) ∈ ��������: 

〈����, ����〉 = ����1 ∙ ����1 + ����2 ∙ ����2 + ⋯ + �������� ∙ �������� . 

            Заметим, что каждой точке  ����(����1, ����2, … , ��������) ∈ �������� 

соответствует вектор   ��������
⃗,  где   ����(0,0, … ,0). 

Пример 2. Множество  ���� , на границе которого лежит 

точка  ����0 , задано неравенством   ����(����) ≤ 0, где ����(����) – 

нелинейная выпуклая функция, причем  ����(����0) = 0 , 

����′(����0) ≠ 0,   где   ����′(����0) = ����������������
⃗����(����0) . 

           Градиент ����′(����0)  является нормальным вектором к 

гиперплоскости, 
касательной 
к 
гиперповерхности     

����(����) = 0. Эта гиперплоскость проходит через точку ����0, а 

вектор ����′(����0)  вне множества  ���� . Поэтому возможные 

направления ����   в точке ����0  должны удовлетворять 

неравенству 

〈 ����′(����0), ���� 〉 < 0. 

           В граничных точках невыпуклого множества ���� 

возможные направления могут и не существовать. 

 

Пример 3. Рассмотрим плоскость ����2  и множество  ���� , 

задаваемое системой неравенств  

����2 − ����1
2 ≤ 0
����1
3 − ����2 ≤ 0
0 ≤ ����1 ≤ 1
   . 

Тогда точка   ����(0,0)   лежит во множестве  ����, но в этой 

точке нет ни одного допустимого направления. Множество  

����  не является выпуклым. 

           Для любой точки ����0 выпуклого множества  ���� всегда 

можно указать хотя бы одно возможное направление. 

Пусть  ���� ∈ ���� , ���� ≠ ����0 . Тогда направление ���� = ���� − ����0 

является возможным. В самом деле 

����0 + �������� = ����0 + ����(���� − ����0) = �������� + (1 − ����)����0 , 

а эта точка принадлежит ����  при всех 0 ≤ ���� ≤ 1  по 

определению выпуклого множества. 

           Определение 2. Вектор  ����   задает направление 

убывания функции  ����(����)  в точке  ����0 ∈ ���� , если ���� – 

возможное направление и   ����(����0 + ��������) < ����(����0)  для всех 

достаточно малых   ���� > 0.