Сетевые методы планирования и управления

Таким образом,

С другой стороны, для с=4 будем иметь =20/5,217=3,83 и

  Следовательно,

Приведенные выше оценки показывают, что при централизации библиотек среднее время ожидания студентом заказанной книги сократится примерно вдвое. Значит, можно сделать вывод, что создание централизованной системы библиотек дает заметный операционный эффект, если его оценить с позиции потенциальных пользователей библиотек. Заметим, что этот результат получен в случае, когда коэффициент загруженности «обслуживающих приборов» (библиотек) в СМО весьма высок.

2.3  Теория игр

Задача

Швейное предприятие, выпускающее детские платья и костюмы, реализует свою продукцию через фирменный магазин. Сбыт продукции зависит от состояния погоды. Но данным прошлых наблюдений предприятие в течении апреля — мая в условиях теплой погоды может реализовать 600 костюмов и 1975 платьев, а при прохладной погоде 1000 костюмов и 625 платьев. Известно, что затраты на единицу продукции в течение указанных месяцев составили для костюмов 27 руб., для платьев 8 руб., а цена реализации равна соответственно 48 руб. и 16 руб. (цифры условные).

Задача заключается в максимизации средней величины прибыли от реализации выпущенной продукции с учетом неопределенности погоды в рассматриваемые месяцы. Таким образом, служба маркетинга предприятия должна в этих условиях определить оптимальную стратегию предприятия, обеспечивающую при любой погоде определенный средний доход. Решим эту задачу методами теории игр, игра в этом случае будет относиться к типу игр с природой.

Предприятие располагает в этих условиях двумя чистыми стратегиями: стратегия А — в расчете на теплую погоду и стратегия Б — в расчете на холодную погоду. Природу будим рассматривать как второго игрока также с двумя стратегиями: прохладная погода (стратегия В) и теплая погода (стратегия Г). Если предприятие выберет стратегию А, то в случае прохладной погоды (стратегия природы В) доход составит

600(48 - 27) + 625(16 - 8) - (1975 - 625)8 = 6 800 руб.,

а в случае теплой погоды (стратегия природы Г) доход равен

600(48 - 27) + 1 975(16 - 8) = 28 400 руб.

Если предприятие выберет стратегию Б, то реализация продукции в условиях прохладной погоды даст доход

1 000(48 - 27) + 625(16 - 8) = 26 000 руб.,

а в условиях теплой погоды

600(48 - 27) + 625(16 - 8) - (1 000 - 600)27 = 6 800

Следовательно, матрица данной игры (платежная матица) имеет вид:

Первая и вторая строки этой матрицы соответствуют стратегиям А и Б предприятия, а первый и второй стратегиям В и Г природы.

По платежной матрице видно, что первый игрок (предприятие) никогда не получит доход меньше 6800. Но если погодные условия совпадают с выбранной стратегией, то выручка (выигрыш) составит 26 000 или 28 400. Отсюда можно сделать вывод, что в условиях неопределенности погоды наибольший гарантированный доход предприятие обеспечит, если будет попеременно применять то А, то стратегию Б. Такая стратегия называется смешанной. Оптимизация смешанной стратегии позволит первому игроку всегда получать выигрыша независимо от стратегии второго игрока.

Пусть х означает частоту применения первым игроком стратегии А, тогда частота применения им стратегии Б равна (1 - х). В случае оптимальной смешанной стратегии первый игрок (предприятие) получит и при стратегии В (холодная погода), и при стратегии Г (теплая погода) второго игрока одинаковый средний доход:

6800х + 26 000(1 - х) = 28 400х + 6800(1 - х).

Отсюда можно найти, что х — 8/17; 1 - х = 9/17.

Следовательно, первый игрок, применяя чистые стратеги А и Б в соотношении 8:9, будет иметь оптимальную смешанную стратегию, обеспечивающую ему в любом случае средний доход в сумме

6800-8/17 + 26000-9/17 16965 руб.; эта величина и будет в данном случае ценой игры.

Легко рассчитать, какое количество костюмов и платьев должно выпускать предприятие при оптимальной стратегии:

(600 костюмов + 1975 платьев)*8/17 + (1000 костюмов + 625 платьев)*9/17 = 812 костюмов + 1260 платьев.

Следовательно, оптимальная стратегия предприятия заключи в выпуске 812 костюмов и 1260 платьев, что обеспечит три любой погоде средний доход в сумме 16 965 руб.

2.4  Сетевые методы планирования и управления

Задача

Дан сетевой график. График содержит 11 событий и 14 работ. Начальное событие (н.с) имеет номер 1, конечное событие (к.с.) - 11. Длительность работ  дана в табл. Найти критический путь.

Ответ:

2.5  Линейное программирование

Задача

Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 1 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 3 часа.

Для производства единицы изделия В оборудование первого типа используется в течении 2 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 1 час.

На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 часа, оборудование второго типа – 60 часов, оборудование третьего типа – 50 часов. Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы.

Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом путем преобразования симплекс-таблиц. Дать геометрическое истолкование задачи, используя для этого ее формулировку с ограничениями – неравенствами.

Перед нами – классическая задача линейного программирования. Под планом производства понимается ответ на простой вопрос: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна.

         Прибыль рассчитывается по формуле:

Запишем математическую модель задачи:

Чтобы проиллюстрировать применение симплекс-метода решения этой задачи, решим ее графически. Для этого построим на плоскости области, описываемые ограничениями-неравенствами, и прямую , которая называется целевой функцией. Три записанных выше неравенства ограничивают на плоскости многоугольник (построен красным цветом), ограниченный слева и снизу координатными осями (т.к. искомое количество изделий положительно). 

График целевой функции (построен синим цветом) передвигается в направлении, обозначенном стрелкой (по-научному – в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (15 ; 5).  В этой точке целевая функция будет достигать максимума.

А теперь решим эту задачу симплекс-методом. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, введя дополнительные переменные 

Симплекс-таблица составляется так:

В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – A3, A4, A5. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.

В следующий столбец Cб  записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов Аi при  i –й переменной.

Под столбцом свободных членов записывается начальная оценка

Остальные оценки записываются под столбцами соответствующих векторов .

Следует отметить, что оценки для базисных векторов всегда равны нулю.

Преобразование симплекс-таблицы ведется следующим образом:

Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.

Шаг 2: Для отрицательных оценок вычисляются величины:

Из этих элементов выбирается тот, для которого вычисленное произведение минимально, в нашем случае   минимально, поэтому в качестве так называемого разрешающего элемента выбирается третий элемент первого столбца – 3 (выделен в таблице).

Шаг 3: Третья строка таблицы делится на 3 и вычитается из первой и второй строк. В сущности, применяется метод исключения неизвестных, известный как метод Жордана – Гаусса. Таким образом, новыми базисными переменными становятся A3, A4, A1.

Возвращаемся к шагу 1 и повторяем весь процесс.

Под столбцом свободных членов записывается начальная оценка

Остальные оценки записываются под столбцами соответствующих векторов  .

Следует отметить, что оценки для базисных векторов всегда равны нулю. Опять проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А2. Вычисляем:

Разрешающим элементом будет второй элемент второго столбца – 2/3.

Новыми базисными переменными становятся A3, A2, A1. Делим вторую строку на 2 и вычитаем из третьей. Умножаем вторую строку на 5/2 и вычитаем из первой.

На этот раз отрицательных оценок нет, т.е. критерий оптимальности выполнен. Таким образом, получается искомое значение целевой функции F(15; 5; 7; 0; 0) = 70, т.е. возвращаясь к системе неравенств, получаем:

Ответы, полученные различными методами, совпадают.

Выводы

Таким образом, в данной работе мы рассмотрели основные понятия методов принятия оптимальных решений: динамического программирования, моделирования систем массового обслуживания, теории игр, сетевого планирования и управления, линейного программирования; а также мы увидели, как можно применять на практике данные методы.

С помощью данных методов, применяемых при моделировании процессов и экономических явлений, все сложные процессы могут быть представлены в таком виде, который позволяет либо судить о характере имеющихся взаимосвязей, либо определить возможность их развития. Решения по этим моделям с помощью определенных алгоритмов экономико-математических задач в большинстве случаев позволяет получить представление об оптимальном варианте развития того или иного процесса или явления.

На основе выполненной  работы можно сделать вывод о том, что:

      Динамическое программирование – это математический аппарат, позволяющий осуществлять оптимальное планирование многошаговых управляемых процессов и процессов, зависящих от времени;

      Системы массового обслуживания – это математические методы исследования стохастических сложных систем;

      Теория игр – это теория математических моделей, интересы участников которых различны, причем они достигают свои цели различными путями;

      Сетевое планирование и управление широко используется при планировании и управлении комплексами работ;

      Линейное программирование применяется для получения оптимального плана решения в задачах, имеющих линейную структуру.

Хотя математические методы и  ЭВМ, а также неразрывно связанные с ними и предшествующие им методы математического моделирования и открывают огромные возможности для развития теории, но сами по себе они не могут полностью вскрыть экономическую  сущность явлений и характер их взаимосвязей. Выбор тех или иных средств математической обработки исходного материала должен происходить на основе глубокого качественного анализа экономических процессов и технологических способов производства, подвергающихся количественному измерению. Без этого даже превосходная математическая модель, блестящий математический аппарат могут превратиться в формальные.