32. Специальные злп. Транспортная задача.

Однородный груз сосредоточен у k поставщиков в объемах a₁, а₂,..., а_k. Данный груз необходимо доставить и потребителям в объемах b₁, b₂, ..., b_n. Известны с_ij i= 1, 2, ..., k и j = 1, 2, ..., n — стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны . Исходные данные задачи могут быть представлены таблицей и в виде вектора запасов поставщиков А = (a₁, а₂,..., а_k), вектора запросов потребителей В= (b₁, b₂, ..., b_n) и матрицы стоимостей C={с_ij}.В транспортных задачах под поставщиками и потребителями понимаются предприятия, заводы, фабрики, и т.д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время и т.п. Математическая модель транспортной задачи. Переменными (неизвестными) транспортной задачи являются x_ij..,i-(=1,2, ..., k), j= 1,2, ..., n — объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок:Так как произведение c_ijx_ij. определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция задачи имеет вид: Система ограничений задачи состоит из двух групп уравнений. Первая группа из k уравнений описывает тот факт, что запасы всех k поставщиков вывозятся полностью, а вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей. Такая задача называется закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой.

33. Основные понятия и определения математической теории игр. Антагонистическая игра (игра с нулевой суммой).

Игровые модели – это упрощенные математические модели конфликтов. В отличие от реального конфликта игра ведётся по четким правилам. Для моделирования конфликтных ситуаций разработан специальный аппарат – математическая теория игр. Стороны, участвующие в конфликте, называются игроками. Каждая формализованная игра (модель) характеризуется: количеством субъектов - игроков, участвующих в конфликте; вариантом действий для каждого из игроков, называемых стратегиями; функциями выигрыша или проигрыша (платежа) исхода конфликта; Игра, в которой участвуют два игрока A и B называется парной. Если же количество игроков больше двух, то это игра множественная. Игра, в которой выигрыш одного из игроков точно равен проигрышу другого, называется антагонистической игрой или игрой с нулевой суммой. Смоделировать (решить) антагонистическую игру – значит, для каждого игрока указать стратегии, удовлетворяющие условию оптимальности, т.е. игрок A должен получить максимальный гарантированный выигрыш, независимо от игрока B, а игрок B должен получить минимальный проигрыш, независимо от игрока A. Оптимальные стратегии характеризуются устойчивостью, то есть ни одному из игроков не выгодно отклоняться от своей оптимальной стратегии.