- •По предмету «математические методы»
- •1. Основные понятия: решение, множество возможных решений, оптимальное решение, показатель эффективности.
- •2. Математ-е модели, осн-е принципы постр-я моделей, аналит-е и статич-е модели.
- •3. Классиф-я задач, возник-х в практ-й деятел-ти и подходы к их решению: прямые и обрат-е з-и.
- •5. Классиф-я задач, возникающих в практической деят-ти и подходы к их решению: однокритер-е и многокритер-е задачи.
- •7. Общий вид задач лин-го программир-я (лп).
- •4. Классиф-я задач, возник-х в практ-й деятельности и подходы к их решению: детерминир-е задачи и задачи в условиях неопредел-ти.
- •6. Методы решения многокритер-х задач.
- •9. Симплекс–метод при решении озлп.
- •10. Транспортная задача.
- •11. Методы нахож-я начал-го реш-я трансп-й з-чи.
- •12. Метод потенц-в в решении трансп-й задачи.
- •13. Общий вид задач нелинейного программир-я. Графический метод решения задач нелинейного программир-я.
- •14. Метод множителей Лагранжа для решения задач нелинейного программирования.
- •16. Идея метода динам-го програм-я. Простейшие задачи, решаемые методом дин-го прогр-я.
- •17. Опред-е графа и его осн-е характер-ки. Вершины и ребра. Графич-я интерпр-я графа. Смежность и инцидентность. Локальная степень. Подграф. Полный подграф.
- •18. Опред-е графа. Матрицы смежностей и инциденций. Методы хранения графов в памяти эвм.
- •19. Путь в графе и связные комп-ты графа. Цепи, простые цепи, циклы, простые циклы. Операции удал-я вершины, уд-я ребра. Дерево и его особ-ти.
- •29. Сети и потоки в сетях. Задача о максимальном потоке и алгоритм Форда–Фалкерсона.
- •20. Определение паросочетаний в графе и их разновидностей. Двудольные графы и алгоритм выбора наибольшего паросочетания в двудольном графе.
- •24. Ориентир-й граф и его графическая интерпретация. Локал-е степени. Матрица смежн-й. Ориентиров-е пути и связность в ориентир-м графе.
- •25. Задача о коммивояжере.
- •26. Понятие системы массового обслуживания, классификация систем массового обслуживания. Простейшие системы массового обслуживания и их параметры.
- •28. Предмет и задачи теории игр. Основные понятия теории игр: игра, игроки, партия, выигрыш, проигрыш, ход, личные и случайные ходы, стратегические игры, стратегия, оптимальная стратегия.
- •29. Антагонистические матричные игры: чистые и смешанные стратегии. Методы решения конечных игр: сведение игры mxn к задаче линейного программирования.
- •30. Назначение и области применения сетевого планирования и управления. Сетевая модель и её основные элементы. Порядок и правила построения сетевых графиков.
10. Транспортная задача.
# Имеется m пунктов отправления (пунктов произв-ва) Аi …, Аm, в ктр сосредоточены запасы однород.продуктов в кол-ве a1, ..., аm ед-ц. Имеется n пунктов назнач-я (пунктов потребления) В1, ..., Вn, потреб-ть ктр в указанных продуктах составляет b1, ..., bn ед-ц. Известны также транспорт.расходы Сij, связанные с перевозкой ед-цы продукта из пункта Ai в пункт Вj, (i 1, …, m; j 1, ..., n). Постановка задачи: Найти V перевозок д/кажд.пары «поставщ.-потреб.» так, чтобы: 1)мощ-ти всех пост-ков были реализованы; 2)спросы всех потреб-лей были удовлетворены; 3)затраты на перевозку были min. Особен-ти эк.-мат.модели ТЗ: 1)сис-мы огранич-й – есть сис-мы ур-ий; 2)коэф-ты при неизвестных в сис-мах огранич-й = 1 или 0; 3)кажд.переменная входит в сис-му огранич-й 2раза – 1раз в I сис-му и 1раз во II. Всякое неотриц.реш-е сис-мы лин.ур-й, опр-мое матрицей X=(xij) (i=1, …, m; j=1, ..., n), наз-ся планом ТЗ. План X=(xij)(i=1, …, m; j=1, ..., n), при ктр f-я принимает свое min значение, наз-ся оптимал.планом ТЗ. Если мощ-ть всех пост-ков=сум.мощ-ти потреб-лей, то такие задачи наз-ся закрытыми, в против.случае – открытого типа. Т: число r осн.(базисных) переменных закрытой ТЗ = m+n-1 (m-число пост-ков, n-потреб-лей). Кажд.разбиению переменных xij задачи на осн.(базисные) и неосн.(свобод.) соотв-ет базис.реш-е и, как следствие, заполнение таблицы поставок, ктр также наз-ся базисным. Др.словами, распред-е поставок наз-ся базисным, если переменные, соотв-щие заполненным клеткам, можно принять за осн.переменные. Клетки, отвечающие базис.переменным, наз-ся базисными, а клетки, соотв-щие свобод.перемен., свободными или пустыми.
11. Методы нахож-я начал-го реш-я трансп-й з-чи.
Д/начала нахождения оптимал.решения требуется найти исх.базисное распред-е поставок – опорный план. Рассмотрим метод «сев.-запад.угла» д/нахожд-я опор.плана. Переносим все коэф-ты из ур-й в таблицу – опорное реш-е выполнено. При этом цел.f-я принимает знач-е суммы произведений верх.угла клетки на нижний угол. Надо, чтобы число заполненных клеток было = m (мощ-ть пост-ков) + n (спрос потреб-лей) - 1. Недостаток этого метода в том, что он построен без учета знач-й коэф-тов затрат задачи. С др.стороны дан.метод допускает модификацию, лишенную этого недостатка, т.е. на кажд.шаге max-возможную поставку следует давать не в сев.-запад.клетку оставшейся таблицы, а в клетку с наим.коэф-том затрат. При этом распред-е поставок оказыв-ся ближе к оптимуму, чем распред-е, полученное методом сев.-запад.угла. Метод минимального элемента. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.