XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 33
Текст из файла (страница 33)
На базы А1, Аэ, Аз поступил товар в количестве 140, 180 и 160 единиц (в единицах измерения товара). Этот товар необходимо доставить на пункты потребления В„ з = 1, 5, в количестве 60, 70, 120, 130 и 100 единиц, причем товар может быть доставлен с любой базы на любой пункт потребления. Воспользовавшись правилом северо-западного угла, составьте начальный план перевозок (найдите начальное базисное рещ ние) и представьте его в виде матрицы переменных задачи.
60 70 10 0 0 Ответ: Х= 0 0 110 70 0 0 0 0 60 100 5.14. Четыре предприятия района для производства своей продукции используют одинаковое сырье, запасы которого сосредоточены в трех различных пунктах и составляют 160, 140 и 170 единиц (в единицах измерения сырья). Воспользовавшись методом минимальной стоимости, составьте начальный план перевозок (см. задачу 5.13) сырья на предприятия, если их потребности в сырье составляют 120, 50, 190 и 110 единиц а \ стоимости перевозки единицы сырья от 1-го источника к з-му стоку представлены матрицей С= 4 5 9 8 0 0 160 0 Ответ: Х= 120 0 0 20 0 50 30 90 5. 15.
. Симплексным методом найдите решение задачи о назначениях, рассмотренной в примере П1.1. Сопоставьте полученный результат с результатом, приведенным в примере П1.2. 5.16. для л к ассической транспортной задачи, транспортная таблица которой представлена в табл. 5,23, найдите оптимальное решение, представьте его в виде матрицы переменных модели зо и вычислите оптимальное значение ее целевой функции 1п. 0 31 0 О Ответ: Хо= 22 3 3 20, г =668, 0 0 38 0 236 Вопросы и задачи Таблица 5.23 ставлены матрицей С= 4 2 6 Рнс.
а.в 9 6 5 8 4 8 6 2 6 7 9 4 2 7 3 1 0 0 0 1 1 0 0 0 Ответ: Хо —— 0 0 1 0 0 1 0 0 Л. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА 5.17. Классическая транспортная задача представлена своей сетью, изображенной на рис. 5.5. Найдите оптимальное решение этой задачи, представьте его в виде матрицы Хо и вычислите оптимальное значение То ее целевой фУнкции. 0 0 40 Ответ: Ха — — 20 0 3, 1о — — 355. 0 20 0 5.18. Для строительства дорог Вь, й = 1, 4, необходим гравий в количестве 130, 220, 60 и 70 единиц (в условных единицах измерения), который может быть поставлен иэ карьеров А„, и= 1,3.
Запасы гравия в этих карьерах составляют 120, 280 и 160 единиц соответственно, а тарифы перевозок (стоимостн перевозки единицы груза от 1-го источника к у-му стоку) пред- Составьте такой план перевозок гравия, при котором потребности в нем каждой из строящихся дорог были бы полностью удовлетворены при минимально возможной общей стоимости перевозок. У к а з а н и е: так как суммарные запасы гравия (120+ 280+ + 160 = 560) превышают спрос на него (130+ 220+ 60+ 70 = = 480), то, согласно замечанию 5.4, введите фиктивный пункт назначения Ва н считайте, что с„а = О, и = 1,3. 120 0 0 0 Ответ Ха О 220 0 0 10 О 60 70 5.19. Найдите решение транспортной задачи с промежуточными пунктами, рассмотренной в примере 5.4, если с~э = 3, сзз = 7~ сза = 3, сдз = 6, ода = 4, с47 = 5, са4 = 5, саа = 3, сау = 5, с78 = 2.
Ответ: с~э= 10, х~зз=2, хз~з — -3, х~за=7, хдз — О, х' =12, о а и о о о о а хда — — О, х4~ —— 2, хо4 — — О, хла —— 5, ха~а — — 7, хааа —— 5, ха = 6, х = 4 о хза — — 8. 5.20. Найдите решение задачи о назначениях (5.12) с мат- рицей 238 Ь. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА 6.21.'Задача выбора кратчайшего пути задана сетью, изображенной на рис. 5.3.
Найдите кратчайший путь от узла этой сети с номером 1 до узла с номером 8, если с,г = 1, сгз = 4, с14 = 6, сгэ = 3, сгь = 5, сгг = 1, сзь — — 3, сзь = 5, сьь = 1, сьв = 4 сь4 — — 1, сьь — — 1, сьв = 2, сьь —— 1, сег = 3, сьв = 4, стг = 1 сгь = 3 сгв= 7 О т в е т: 1 + 2 + 7 -+ 6 -+ 5 -ь 8. 6.22. Найдите самый короткий и самый длинный путь из узла с номером 1 в узел с номером 8 в ациклической сети, представленной на рис. 5.6. Ответ: самый короткий путь 1-+ 2-+ 3-+ 5-+6-> 7 — ь 8; самый длинный путь 1-> 4 -+ 5 -+ 6 + 8, или 1-+ 3 — ь 4 -+ 5 -+ -+ 6 -+ 8.
Рис. ь.в 6. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ В этой главе рассмотрены приложения методов математического программированил к многошаговым задачам принятия рсигсний в условиях риска, в которых процесс изменения состояния любой изучаемой системы является марковским процессом с конечным множеством возможных состояний и дискретным временем. Математические модели, приводящие к таким задачам, называют марковскими моделями приняпъия решений, а сами задачи — марковскими задачами прин*няня решений. В марковских моделях принятия решений поощрения (доход, потери) задают матриней доходов, элементами которой являются доходы (положительные значения) или затраты (отрицательные значения), возникающие вследствие перехода системы из одного возможного состояния в другое.
Матрицы переходных веролп1ностсй и матрипы доходов зависят от страгпегий, т.е. допустимых решений, которыми располагает „лицо, принимающее рсигснил". Основная цель — определение опьтьимальиой спьраиьееии (оптимального решения), максимизирующей ожидаемый доход за конечное или бесконечное число этапов марковского процесса изменения состояния изучаемой системы. Излагаемый теоретический материал иллюстрирован примером с садовником (см. пример 1.5), который, несмотря на его простоту, может быть полезен при анализе актуальных прикладных задач (управление запасами, замена оборудования, контроль и регулирование емкости водохранилища и т.д.).
Напомним, что садовник, проводя химический анализ почвы, каждый год в начале сезона оценивает продуктивность своего сада как хорошую, удовлетворительную или плохую. Оценка 240 б. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ состояния сада позволяет садовнику принять одно иэ допустимых решений: обойтись без дополнительной обработки или провести обработку, включающую, например, внесение удобрений. Это требует дополнительных затрат, а цель садовника— получить максимальный доход. Отметим, что садовник планирует поработать на своем участке еще Г!! лет н его интересует оптимальный вариант своих действий отражающий, в какие годы нужно проводить дополнительную обработку уча!стка.
6.1. Основные понятия б 1, Основные понятия Кроме того вектор 241 является вектором вероятностей состояни яний системы после ! этапов п и ! = 1 р —,."! и век!порам начальных вероятностей состояний системы о при ! = О. В соответствии с и х исходными допущениями условная ве оятность реализации случайного события в! „при условии в ! — ! зависит от принятого после (! — 1)-го этапа решения Х!,, из множества С допустимых решений.
Таким образом, Рассмотрим некоторую динамическую систему 5 с возможными дискретными состояниями з!, у = 1, т, которая в фиксированные последовательные моменты времени !! < 1з < ... случайным образом переходит скачком (мгновенно) из одного возможного состояния в другое или остается в прежнем. При этом будем предполагать, что сам процесс изменения состояния изучаемой системы 5 является марковским процессом, т.е. вероятность перехода системы 5 в любое возможное состояние в момент времени 1, определяется состоянием, достигнутым в момент времени 1; „и не зависит от того, когда и как она пришла в это состояние. Напомним, что фиксированные моменты времени 1; принято называть шагами илн этапами марковского скалярного процесса изменения состояния системы 5. Для удобства дальнейших рассуждений некоторый момент времени !а < !! будем считать начальным и введем случайное событие в'„, состоящее в том, что после ! этапов исходная система 5 находится в состоянии Яы й = 1, т.
При этом ! = 0 соответствует начальному этапу и при любом фиксированном ! события в'„, й = 1, т, образуют полную группу событий. Поэтому ~ р [,1„1 = 1, ! = О, М. ь=! руь(!)Х!, !) =Р(в' )в'. ';Х, и матрица переходных вероятностей Р(! ~ Х!,, ) = (Руь(!) Х!! !)) Е М (!ь).
При этом нетрудно убедиться в том, что верны следующие утверждения (ХАНЦ: а) сумма элементов любой строки мат м т ицы переходных вероятностей Р(ь!Х!,,) равна единице; б) вектор вероятностей состояний изучаемой системы после ! этапов павен п оизв р едению транспонированной матрицы переходных вероятностей Р!!!Х, !г! !,,' на вектор вероятностеи состояний после (! — 1)-го этапа„т.е. р(!) = Р (г) Х!,,) р(! — 1). Из приведенных асс ж р у дений, в значительной степени очес учае вектор вевидных, следует вывод о том, что в общем случ роятностей состояний системы 5 после этапов зависит от Ж некто а началь р альных вероятностей ее состоян " 0 ий р' и вектора б.
Е Осповпме попятив 243 0,3 0,6 0,1 Рз — 0,1 0,6 0,3 0,05 0,4 0,55 Таблица б 1 0,2 0,5 0,3 Р1 — — 0 0,5 0,5 0 0 1 242 6. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИИ который называют вемцзором релмеммб. Действительно, р(1ц) — Р Р(Х,„,) р(1Ц вЂ” 1) = р (1ц(Х, ) Р'(1ч — 1(Хип,)РР— 2) =". Рр р(Х ) р'р — 1(Х~„,)...Р'(1(ХН) Р(0). Праьлер 6.1. Каждый год в начале сезона садовник проводит химический анализ почвы на своем участке и по его результатам оценивает продуктивность сада на новый сезон как хорошую, удовлетворительную или плохую (табл.
6.1). По результатам многолетних наблюдений садовник установил, что продуктивность сада в текущем году можно считать зависящей лишь от состояния почвы в предыдущем году. Таким образом, процесс изменения состояния почвы представляет собой марковский процесс с тремя возможными состояниями и дискретным временем. Пусть в рассматриваемом примере матрица переходных вероятностей является постоянной: где номера строк и столбцов — зто номера состояний системы о„оз, оз (см. табл. 6.1) в текущем и последующем годах соответственно. Так, например, если в текущем (1-1)-м году состояние почвы хорошее, то вероятность ее перехода в плохое со- 1-11 стояние в последующем 1-м году равна р1з(1) = Р [яз (в, ] = 0,3. Садовник может принять решение о применении удобрений с целью повышения продуктивности сада, т.е. с целью улучшения состояния почвы так как в противном сл чае е чае переходные вероятности не изменятся.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
