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

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


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


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




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


Москва - 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

  3. 5. Двойственность в выпуклом программировании .. 47
4. Методы приближенного решения задач математического программирования..............49
  4. 1. Методы возможных перемещений..........49
  4. 2. Метод штрафных функций................57
  4. 3. Метод барьерных функций...............62

4

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




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


     Многие задачи оптимизации сводятся к математическим моделям следующего вида:
/(%) ^ min,  xEU.
     В этом случае говорят об условной минимизации. В большинстве случаев множество U определяется системой равенств и (или) неравенств. В этом случае задача записывается следующим образом:

f(x) ^ min (max)          (1.1.1)
gt (х) = 0 ,     i. е 1-1 (1.1.2)
gt (x) = 0, it 12         (1.1.3)

где  /1 U /2 = {1, 2,..., т} , 11 П 12 = 0 .
      Задача (1.1.1) — (1.1.3) называется задачей
математического программирования.

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

5

1. Линейное программирование
В (1) — (3) все функции линейные, кроме того Х[ > 0 для всех i, где х = (х1,х₂,..., хп).
2. Нелинейное программирование
Хотя бы одна из функций в (1.1.1) — (1.1.3) не является линейной.
3. Задача на условный экстремум
Нет ограничений - неравенств, т. е. 11 = 0 .
4. Задача выпуклого программирования
Все функции /(%), gi (х) - выпуклые, а ограничения -равенства отсутствуют, т. е. 12 = 0 .
      Решение задач математического программирования, как правило, связано с большими трудностями, чем решение задач безусловной минимизации.

6