Форум Поща Карта на сайта Търсене Връзки Контакти
Начало Обучение Дисциплини в учебните планове на специалностите Математика (бакалавър) Учебен план Математическо оптимиране    English
Факултет по математика и информатика - Математическо оптимиране
Специалност
Форма на оценяване
Дисциплината
се води
Математика (бакалавър) редовно обучение
изпит
 
Анотация
Сравнително новата математическа дисциплина изследване на операциите, датираща от 30-те години, изучава и разработва теорията на методите за решаване на различни класове екстремални задачи. Изключително широк кръг проблеми от най-разнообразни области на реалния живот се свеждат до математически модели, представляващи екстремални задачи, за които класическият математически ана.чиз не предлага приемливи практически методи за решаване. Задачите са разнообразни и обемни и методите за тяхното решаване трябва да бъдат пригодни за компютърна реализация, със всичките изисквания свързани с това, че трябва да бъдат реално решени в реално време. Поради това в последните десетилетия изучаването на възможностите за практическото им решаване доби особено голяма популярност и привлича вниманието на широк кръг специалисти от математическите и нематематическите среди, свързани пряко с решаването на подобен род задачи. Поради това, че това е една сравнително нова математическа дисциплина и разнообразието на задачите е изключително голямо, все още има много класове екстремални задачи, които не са добре изучени. В областта на изследването на операциите се обособиха самостоятелни математически дисциплини като Математическото оптимиране, Вариационното смятане, Оптималното управление, Теорията на игрите, Динамичното оптимиране и др.
Математическото оптимиране би трябвало да бъде неотменна част от математическата култура на всеки специалист, занимаващ се с математика и с информатика. Запознава с идеологията на създаване на теорията на методите за практическото решаване на едни от най-популярните математически модели на екстремални задачи, отчитайки и най малките специфични особености на всеки клас задачи. Изучава се тази математическа теория, която обсновава предложените методи и алгоритми за решаване, както и самите методи и алгоритми.
В рамките на предвидения хорариум от учебни часове в учебната програма са подбрани едни от най-популярните основни класове задачи на математическото оптимиране, които са с изключително широко приложение, както в практиката, така и с това че много други класове екстремални задачи в даден етап на тяхното решаване се свеждат до прилагането на включените в учебната програма методи. Предложения курс може да служи за сериозна основа на всеки специалист за по-нататъшно запознаване с теорията и методи на решаване на други, невключени в курса класове задачи. Предвидените курсови работи изискват компютърна реализация на изучаваните методи, както и на подобни или близки до тях. Дават възможност да се оценят качествата и проблемите възникващи в последния етап от веригата "реален проблем, математически модел, решаване на модела, връщане на резултатите към реалния проблем". По този начин, поне на учебно ниво, се окомплектова представата на съвременния специалист по .математика и информатика за връзката между реалните проблеми, математиката и информатиката.
 
Съдържание
1. Увод в теорията на линейното оптимиране. Предмет на математическото оптимиране. Формулировка и класификация на задачите. Някои производствено-икономически задачи и техните математически модели:
  • Планово-производствена задача.
  • Задача за оптимална дажба.
  • Задача за оптимално разкрояване на материали.
  • Задaча за минимална себестойност.

2. Избрани елементи от изпъкналия анализ.

  • Изпъкнали множества.
    • Основни свойства. Теореми за отделимост.
    • Крайни точки. Теорема за представяне.
    • Изпъкнали конуси. Свойства. Теорема за представяне.
  • Полупространства. Теорема за представяне.
  • Изпъкнали функции.
    • Екстремални свойства.

3. Геометрична интерпретация на задачата на математическото
оптимиране.
Геометрично решаване на задачата на изпъкналото програмиране в R2. Геометрично решаване на задачата на линейното програмиране в R2.

4. Задача на линейното оптимиране. Формулировка на най-общата задача на линейното оптимиране.Терминология. Стандартна и канонична форма на задачата на линейното оптимиране. Стандартизиране и канонизиране. Еквивалентност между различните форми.

5. Задача на линейното оптимиране в каноничен вид. Свойства на множеството от планове. Въвеждане на основни понятия -опорен план, базис. базисно представяне. Свойства. Основни теореми характеризиращи множеството от планове. Екстремални свойства на целевата функция в множеството от планове. Основни теореми на линейното оптимиране и следствия от тях.

6. Симплекс-метод

  • Основна идея на симплекс-метода. Основни алгоритмични моменти.
  • Теоретични основи на симплекс-метода.
  • Изключване на базисните променливи от целевата функция.
  • Критерий за оптималност. Доказателство и формулировка.
  • Критерий за неограниченост. Доказателство и формулировка.
  • Правило за преминаване от един опорен план в друг по-добър опорен план.
  • Доказателство и формулировка.
  • Алгоритъм на симплекс-метода.
  • Описание.
  • Изчислителна схема.
  • Симплекс-таблици.
  • Намиране на начален опорен план.
  • Съставяне на помощна задача.
  • Основна теорема за връзката между помощната задача и решаваната линейна канонична задача.
  • Алгоритъм за намиране на начален опорен план.
  • Зацикляне при симплекс-метода.
  • Причини за зациклянето.
  • Лексикографска наредба.
  • Избягване на зациклянето. Предложение и доказателство.

7. Модификации на симплекс-метода. *

  • М-метод за решаване на линейни оптимизационни задачи.*
  • Теоретични основи.*
  • Алгоритъм.*
  • Модифициран симплекс-метод.*
  • Теоретични основи.*
  • Алгоритъм.*

8. Двойственост в линейното оптимиране.

  • Дефиниция на понятието двойственост. Двойки взаимно-двойствени (дуални) задачи.
  • Свойства на двойките дуални задачи. Основни теореми за двойственост. Едно приложение на теоремите за двойственост за едновременно решаване на двойка дуални задачи.

9. Двойствен симплекс-метод.

  • Основна идея на метода. Основни понятия и основни алгоритмични моменти.
  • Намиране на начален псевдоплан. Доказателство.
  • Критерий за оптималност. Доказателство и формулировка.
  • Критерий за неразрешимост. Доказателство и формулировка.
  • Правило за преминаване от един псевдоплан в друг по-добър псевдоплан.
  • Доказателство и формулировка. Алгоритъм на двойствения симплекс-метод. Описание.
  • Изчислителна схема. Симплекс-таблици.

10. Транспортна задача по критерий минимални транспортни разходи.

  • Формулировка и съставяне на математически модел на транспортна задача по критерий минимални транспортни разходи. Записване на информацията в транспортни таблици.
  • Специфични свойства на транспортна задача.
  • Критерий за разрешимост.
  • Теорема за ранга на матрицата от ограничения. Изводи. Bидове транспортни задачи.
  • Привеждане на задачи от отворен тип към задачи от затворен тип. Въвеждане на понятията цикъл, цикличен набор от клетки.
  • Връзка между понятията ацикличност на набор от клетки и линейна независимост на вектори на условията. Изводи.
  • Методи за намиране на начален опорен план на транспортна задача.
  • Метод на северозападния ъгъл.
  • Метод на минималния елемент.
  • Метод на двойното предпочитане и др.
  • Особености в случаите на изроденост. Разпределителен метод за намиране на оптимален опорен план на транспортна задача.
  • Основна идея.
  • Алгоритъм. Доказателство на основните алгоритмични моменти.
  • Изчислителна схема.
  • Особености в случаите на изроденост.
  • Двойствен модел на транспортната задача. Конкретна формулировка на теоремите за двойственост. Изводи. Метод на потенциалите за намиране на оптимален опорен план на транспортната задача.
  • Основна идея.
  • Алгоритъм. Доказателство на основните алгоритмични моменти.*
  • Изчислителна схема.
  • Транспортни задачи с блокирани превози. Транспортни задачи с приоритет.

11. Транспортна задача по критерий време.

  • Свойства. Алгоритъм за решаване.*

12. Задача на квадратичното оптимиране.

  • Геометрично решаване в R2.
  • Основни екстремални свойства на целевата функция в множеството от планове. Метод на Бил за решаване на задачата на квадратичното оптимиране.
  • Основна идея. Теоретична обосновка на идеята.*
  • Правило за преминаване от един план в друг. Формулировка и доказателство.*
  • Критерий за оптималност. Формулировка и доказателство.*
  • Критерий за неограниченост. Формулировка и доказателство.*

13. Задача на хиперболичното оптимиране. Формулировка.

  • Геометрично решаване на хиперболични линейни задачи в R2. Изводи и заключения.
  • Екстремални свойства на хиперболичната функция в множеството от планове.* Свеждане на решаването на хиперболична задача до решаването на съответна линейна оптимизационна задача.* Теореми за еквивалентност.*
  • Алгоритъм за решаване.*

14. Една задача от теорията на игрите и свеждането й до линейна оптимизационна задача.* Формулировка. Основни понятия. Свойства. Теорема за еквивалентност на задачата на теорията на игрите и задачата на линейното оптимиране.

15. Идея за решаване на оптимизационни задачи с параметър.

  • Линейна оптимизационна задача с параметър в целевата функция. Геометрична интерпретация. Метод за решаване.*
  • Линейна оптимизационна задача с параметър в описанието на множеството от ограничения.
  • Геометрична интерпретация.* Метод за решаване.
Актуално
Още новини
Архив на новините
© 2009 ФМИ