24. Транспортная задача линейного программирования.

Транспортная задача – это задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения. Является задачей линейного программирования специального вида. Транспортная задача может быть записана в виде прямоугольной таблицы. Алгоритм решения транспортной задачи: 1. Производится балансировка задачи. Если сумма запасов равна сумме потребностей,то транспортная задача называется закрытой. Если равенство не соблюдается, то задача называется открытой и необходимо, чтобы она была приведена к закрытому виду, то есть ввести фиктивного поставщика или фиктивного потребителя на недостающий или избыточный объем товара, которому нужно приписать нулевую цену доставки. 2. Поиск начального решения. Решение транспортной задачи начинается с поиска допустимого начального решения (плана перевозок), чтобы все запасы поставщиков были распределены по потребителям.Методы начального решения задачи: - Метод северо-западного угла; - Метод минимального элемента. 3. Нахождение функционала (F), сумма затрат на транспортировку груза. Для всех ячеек цена умножается на объем перевозки и полученный результат суммируется. 4. Решение транспортной задачи методомпотенциалов. Метод потенциалов позволяет за несколько шагов найти полностью оптимальное решение транспортной задачи.

- Разделение ячеек на базисные и свободные. Ячейки (клетки) транспортной таблицы с ненулевыми перевозками называются базисными, а клетки с нулевыми объемами перевозки - свободными.

- Проверка плана на вырожденность.

Базисных ячеек таблицы должно быть не менее m+n-1, где m и n -соответственно, число поставщиков и потребителей, иначе решение считается вырожденным и требует введения в базис одной из ячеек с нулевой перевозкой. - Вычисление потенциалов

Каждому поставщику A_i соответствует потенциал U_i, а каждому потребителю B_j соответствует потенциал V_j. Чтобы определить эти потенциалы, полагают, что U₁=0, а остальные потенциалы вычисляют из соотношения: U_i + V_j = C_ij

- Проверка решения на оптимальность

Для всех не занятых ячеек (с нулевым объемом перевозки) вычисляют оценки клеток распределительной таблицы Δij по формуле Δ_ij = С_ij – U_i – V_j Если в получившейся таблице нет отрицательных значений Δ_ij, то план перевозок оптимален и задача решена.

- Построение цикла.

Цикл перераспределения поставок представляет собой замкнутую ломаную линию, которая соединяет начальную вершину и занятые ячейки транспортной таблицы по определенным правилам. - Перераспределение поставок по циклу.

ячейке цикла с наименьшим потенциалом присваиваем знак (+), следующей по циклу (начать двигаться можно в любом направлении) - знак (–), следующей ячейке цикла - опять (+) и так далее. - Нахождение функционала (F), сумма затрат на транспортировку груза. Для всех ячеек цена умножается на объем перевозки и полученный результат суммируется, полученный результат сравнивается с предыдущим. -  Зацикливание решения

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

25. Теория игр. Теория игр - математический метод изучения оптимальных стратегий в играх. Под игрой понимается процесс, в котором участвуют две и более сторон, ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу - в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках. Классификация игр: - По количеству стратегий игры делятся на:а) конечные - когда в игре все игроки имеют конечное число возможных стратегий. б) бесконечные - когда хотя бы один из игроков имеет бесконечное количество возможных стратегий. - По характеру взаимодействия игры делятся на:а)бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;б)коалиционные (кооперативные) могут вступать в коалиции. - По характеру выигрышей игры делятся на:а)игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; б)сумма выигрышей всех игроков равна нулю; в)игры с ненулевой суммой. - По виду функций выигрыша игры делятсяна:матричные, биматричные, непрерывные, выпуклые, сепарабельные, типа дуэлей и др. 26. Понятие об игровых моделях. Игровая модель - это совокупность правил поведения при конфликтной ситуации и функции платежа для каждого игрока на любом этапе игры. В игровых моделях статистические данные либо вообще отсутствуют, либо носят весьма приблизительный характер. В очень редких (исключительных) случаях для игровых моделей можно определить количественную оценку или указать оптимальное решение. В игровых моделях не ставится задача найти какое-то числовое решение, а требуется лишь или очертить область возможных решений, или предоставить некоторые дополнительные сведения о возможном развитии событий и рекомендовать правила поведения. Различают два больших класса игровых моделей: 1. Модели без противодействия(или их еще называют "играми природой"). Игры с противодействием часто называют конфликтными ситуациями, которые широко распространены в обществе. Например, конкурентная борьба в экономике, в спортивных соревнованиях, состязание сторон в ходе судебного заседания и т.д. 2.Модели с противодействием(действия конкурентов на рынке). Игровая модель, в отличии от конфликтной ситуации, строится по определенным законам, а игроки придерживаются определенных правил. игра конфликт математический модель

27. Теория массового обслуживания. Теория массового обслуживания - область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которой однородные события повторяются многократно, например, в системах приема, переработки и передачи информации; автоматических линиях производства. Такие системы называют системами массового обслуживания (СМО). Все СМО делятся на: - СМО с отказами; - СМО с ограниченной длиной очереди; - СМО с неограниченной очередью. - По числу каналов: 1. Одноканальные - когда имеется один канал

обслуживания; 2. Многоканальные - n-канальные, когда количество каналов n≥ 2. - По ограничению потока заявок: 1. Замкнутая - если поток заявок ограничен и заявки, покинувшие систему, могут в нее возвращаться; 2. Открытая - если поток заявок неограничен и заявки, покинувшие систему, не могут в нее возвращаться; Предметом теории массового обслуживания является установление зависимостей между характером потока заявок, числом каналов обслуживания, производительностью отдельного канала и эффективным обслуживанием с целью нахождения наилучших путей управления этими процессами.

Задача  теории массового  обслуживания – установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что заявка будет обслужена)

28. Решение задач систем массового обслуживания(СМО). Этапы решения задачи: 1. Задаются исходные данные: - описание СМО (тип, параметры, критерии эффективности работы

системы);

- параметры закона распределения времени пребывания требования в

очереди (для СМО с ожиданием);

- параметры закона распределения времени обслуживания требований в

системе.

2. Вырабатывают равномерно распределенное случайное число;

3. Равномерно распределенные случайные числа преобразуют в величины с

заданным законом распределения:

- интервал времени между поступлениями требований в систему , время ухода заявки из очереди;

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

4. Определяют моменты наступления событий:

- поступление требования на обслуживание;

- уход требования из очереди;

- окончание обслуживания требования в каналах системы. 5.Моделируют функционирование СМО в целом и накапливают

статистические данные о процессе обслуживания.

6. Устанавливают новый момент поступления требования в систему, и

вычислительная процедура повторяется в соответствии с изложенным.

7. Определяют показатели качества функционирования СМО путем

обработки результатов моделирования методами математической статистики.