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

Развитие относится к 30-ым годам. Математик – Толстой . Бурное развитие после войны. Всюду, где возникает необходимость выбора среди множества вариантов, решения какой либо проблемы (получения максимальной прибыли, минимальный расходы и.т.д) , выбор наилучшего в каком-то смысле – там и возникают задачи математического программирования.

Задачи записанные на языке формул, уравнений представляет собой математическое моделирование

Найти max или min функции Z=f( ) , где φ( ) b_i , где (i=1,k); φ( )=b_i , где (i=1,k) (i=k+1, L);

- управляемый параметр. - неуправляемый параметр. (не учитывается)

Чтобы решить задачу имея математическую модель нужно знать математические метод (Гауса, Крамера, матричный и.т.д) Зная метод => нужно знать алгоритм.

КЛАССИФИКАЦИЯ МЕТОДОВ.

В зависимости от того какими являются функции f и φ_i , задачи делятся на два класса : 1) Если функции f и φ_iлинейны относительно параметров Х и У , то имеем задачу линейного программирования. (Л.П.)

2) Если хотя бы одна из функций f и φ_iнелинейная относительно параметров и , то имеем нелинейную задачу. (Н.П.)

Для Л.П. существует универсальный способ. Симплекс – метод Основ. разработку дал Дансон.

Х3

Х2

Х1

В Н.П. самым изученным является выпуклое программирование – это когда находится минимум выпуклой функции на выпуклом множестве или максимум вогнутой функции на выпуклом множестве. Существуют так же :1) Д.П. – динамическое программирование , вся задача разбивается на n-этапов. 2) Стохастическое программирование – случайные параметры. 3) Э.П. – эвристическое программирование , где оптимальное решение найти сложно из-за большого количества вариантов. 4) Ц.П. – целочисленное программирование.

Транспортная задача.

Имеется два пункта однородного продукта. Мощность 1^го 400т.; 2^го – 500т., имеется 3 пункта потребления этого продукта. Известны затраты на перевозку 1т. продукции . Из 1^го пункта к 1^му – 2млн. р. ; 2^му– 3 млн. р; 3^му – 4 млн. р. Из 2^го - 1^му– 5 млн. р.;2^му- 4 млн. р.; 3^му- 2 млн. р. Спланировать перевод таким образом, чтобы суммарные затраты были минимальными.

1) нужно 300 т. 2) нужно 400 3) нужно 200 т.

Математическая модель.

Х _ij – кол-во тонн продукции перевезенной из пункта i к пункту j- му потребителю. Найти план перевозок. (матрицу Х) Х= х₁₁ х₁₂ х₁₃ Предложение = спросу.